STL - 변경 불가 시퀀스 알고리즘

 변경불가 시퀀스 알고리즘은 대상 컨테이너를 직접 수정 할 수 없는 알고리즘입니다. 이러한 알고리즘에는 시퀀스를 검색하여 원하는 원소를 찾아내는 알고리즘은 find, 상등 여부를 검사하는 equal, 그리고 시퀀스에 담긴 원소의 원소 개수를 세는 count 같은 알고리즘 등이 있습니다. 일단 우리가 알아볼 변경불가 시퀀스 알고리즘에는 find, adjacent_find, find_if, count,count_if,  for_each, mismatch, equal, search 이렇게 여러 알고리즘이 있는데, 여기 에서 언급된 변경불가 시퀀스들의 시간복잡도는 선형적입니다. (선형은 무엇인가? 아래 표를 한번 참고해 보시죠)

  

find

 : 우선은 find 알고리즘에 관해서 알아 보겠습니다. find 알고리즘은 시퀀스를 검색하여 원하는 원소를 찾아내는 알고리즘으로 다음과 같이 씁니다. 

#include <iostream> #include <algorithm> #include <vector> #include <iterator> using namespace std; int main () { vector<int> number; number.push_back(10); number.push_back(20); number.push_back(30); ostream_iterator<int> out(cout, ", "); copy(number.begin(), number.end(), out); cout<<endl; auto it = find(number.begin(), number.end(), 10); cout<<"당신이 찾은 값은 ? "<<*it<<endl; return 0; }

 copy와 ostream_iterator는 출력을 위한 것이므로, 여기서는 find를 쓴 부분만 집중해서 보면 됩니다. 인자값으로는 컨테이너의 처음과 끝을 넣고 자신이 찾고 싶은 값을 마지막 인자값으로 넣어주면 위와 같이 무리없이 결과가 출력되는 것을 알 수 있습니다.

 find에는 find_if라는게 잇는데 find_if는 시퀀스에 담긴 원소 중에서 주어진 조건자를 true가 되게 하는(만족하는) 첫번째 원소를 찾아내는 알고리즘입니다. 일단 여기선 단항 조건자 객체 타입인 Biggerthan30(30보다 큰수)을 정의하고 find_if의 인자로 넘겨 주는데, 굳이 클래스를 만들지 않아도 아래와 같이 사용이 가능합니다.

#include <iostream> #include <algorithm> #include <vector> #include <iterator> using namespace std; bool Biggerthan30(int i) { return (i >30); } int main () { vector<int> number; number.push_back(10); number.push_back(60); number.push_back(20); number.push_back(30); ostream_iterator<int> out(cout, ", "); copy(number.begin(), number.end(), out); cout<<endl; vector<int>::iterator it_if = find_if(number.begin(), number.end(), Biggerthan30); cout<<"30보다 큰 값은 ? "<< *it_if<<endl; return 0; }

 그 다음 알아 볼 것은 adjacent_find인데요, 이 알고리즘은 시퀀스에서 동일한 원소가 서로 이웃하고 있는 쌍을 찾아내는 알고리즘 입니다. 서로 인전합 두 원소가 동일한 부분을 찾아내면 앞쪽 원소를 가리키는 반복자를 리턴합니다.

#include <iostream> #include <algorithm> #include <vector> #include <iterator> using namespace std; int main () { vector<int> number; number.push_back(10); number.push_back(20); number.push_back(30); number.push_back(20); number.push_back(20); number.push_back(10); ostream_iterator<int> out(cout, ", "); copy(number.begin(), number.end(), out); cout<<endl; vector<int>::iterator it_af = adjacent_find(number.begin(), number.end()); cout<<"인접한 값들은? "<<*it_af <<endl; cout<<"인접한 값의 다음값은 ? " <<*(++it_af) <<endl; it_af = adjacent_find(number.begin(), number.end(), greater<int>() ); cout<<"여기에 들어갈 값은? "<< *it_af <<endl; return 0; }

  여기서에서는 adjacent_find의 두가지 버전이 모두 사용되고 있는데, 우선 비조건자 버전이 먼저 사용되었고, 비조건자 버전은 비교시에 string::oeprator==을 사용하기 때문에 동일한 운소가 인접한 첫뻔째 쌍을 찾고 됩니다. 그리고 다음은 이항 조건자인 greater<int>()를 사용하여 비교를 수행합니다. (내부 구조는 left > right 이므로 여기서는 30을 찾게 되는거죠) 

count

  : 카운트는 시퀀스를 검색하여 특정 값과 일치하는 원소의 개수를 세는 알고리즘입니다.

#include <iostream> #include <algorithm> #include <vector> #include <iterator> using namespace std; bool function(int i) { return (i % 20 == 0); } int main () { vector<int> number; number.push_back(10); number.push_back(20); number.push_back(30); number.push_back(20); number.push_back(20); number.push_back(10); ostream_iterator<int> out(cout, ", "); copy(number.begin(), number.end(), out); cout<<endl; int cnt = count(number.begin(), number.end(), 20); cout<<"20의 값을 가진 시퀀스의 갯수 "<<cnt <<endl; int cnt_if = count_if(number.begin(), number.end(), function); cout<< "20 % i == 0인 시퀀스의 갯수는? : "<< cnt_if<<endl; return 0; }

위 소스 코드에서는 그냥 count와 count_if라는것을 썼습니다. count_if는 find_if와 마찬가지로 단항 조건자 객체 타입을 선언하고 이 조건자를 만족하게 되는 시퀀스의 갯수를 세는 알고리즘입니다. 

for_each

 : for_each 는 시퀀스에 담긴 모든 원소에 함수 F를 적용하는 제네릭 알고리즘입니다.

#include <iostream> #include <algorithm> #include <vector> #include <iterator> using namespace std; void print(int i) { cout << "값 : "<<i <<endl; } int main () { vector<int> number; number.push_back(10); number.push_back(20); number.push_back(30); number.push_back(20); number.push_back(20); number.push_back(10); for_each(number.begin(), number.end(), print); return 0; }

 print 함수는 단순하게 값을 출력하는 함수입니다. for_each는 이런 함수를 적용해 값들을 형식에 맞게 출력해주는 것을 알 수 있습니다. (함수를 시퀀스에 적용하는 것입니다.)

mismatch 와 equal

 : mismatch와 equal 은 두개의 구간을 비교할 떄 사용하는데, 세개의 반복자를 필요로 합니다. 

#include <iostream> #include <algorithm> #include <vector> #include <string> using namespace std; int main () { vector<string> A; vector<string> B; vector<string> C; A.push_back("A"); A.push_back("B"); A.push_back("C"); B.push_back("A"); B.push_back("B"); B.push_back("C"); B.push_back("D"); C.push_back("A"); C.push_back("D"); //A와 B의 처음 3개의 워소가 서로 일치함을 보여준다. if ( equal( A.begin(), A.end(), B.begin() ) == true) { cout<<"A와 B의 처음 3개의 원소가 서로 일치합니다. "<<endl; } //C와 A의 처음 2개의 원소가 서로 일치 하지 않는다. if( equal( C.begin(), C.end(), A.begin() ) == false ) { cout<<"C와 A의 처음 2개의 원소가 서로 일치하지 않습니다. "<<endl; } //서로 일치 하지 않는 첫번째 원소의 위치를 찾는다. mismatch는 C와 A의 pair를 리턴하게 됩니다. pair<vector<string>::iterator, vector<string>::iterator> pair1 = mismatch (C.begin(), C.end(), A.begin()); if(pair1.first != C.end()) cout<< "첫 불일치 리스트 "<< *pair1.first << " 와 " <<*pair1.second <<endl; return 0; }

 여기서 유의해야할 점은 equal 알고리즘과 mismatch 알고리즘 중 어떠한 것을 사용해도 두개의 컨테이너가 완전히 일치하는지를 알 수 없다는 점입니다. 왜냐하면, 알고리즘에서 두 컨테이너의 사이즈가 서로 일치하는가에 관해서는 검사를 하지 않기 때문이죠. 따라서 두개 컨테이너가 완전히 동일한 원소들로 구성되어 있는지 검사 할려면 아래와 같이 써서 검사를 체크 하면 되겠죠

if ( A.size() == C.size() && equal(C.begin(), C.end(), A.begin()) ) cout<<"Equal 알고리즘을 적용할 수 있습니다."<<endl; else cout<<"Equal 알고리즘을 적용할 수 없습니다."<<endl;

 두 개의 컨테이너가 서로 같은 타입이라면 c1 == c2 이런 식으로도 가능하죠. 이건 내부적으로 ==연산자가 정의 되어 있기 때문에 가능한 일입니다. 그리고 또 한가지 유의 해야 할 점은 알고리즘을 수행하는동안 B부터 시작해 차례로 참조되는 원소의 개수는 적어도 A의 사이즈보다 크거나 같아야 한다는 것이죠. 그렇지 않으면 B에서 시작해 도달한 특정 원소와 구간 A의 begin과 end에 위치한 원소 간에 불일치가 있었다는 것을 의미하게 됩니다. 이 두 가지 조건 어디에도 해당되지 않는 경우라면 equal과 mismatch는 예측할 수 없는 결과 같을 리턴하게 됩니다. 

 아래는 이치에 맞는 코드 입니다.

int c; c = equal(A.begin(), A.end(), B.begin()); cout<< c<<endl;

 아래는 잘못된 예입니다.

int c; c = equal(B.begin(), B.end(), A.begin()); cout<< c<<endl;

 왜냐하면, A의 사이즈가 B의 사이즈보다 더 작아서 불일치를 발견하지 못하고 A의 끝에 도달한 것이기 때문입니다. mismatch 와 equal은 모두 조건자 버전을 가지고 있으며, 네 번째 인자로 이항 조건자를 사용하여 상등의 의미를 변경할 수도 있습니다.

search

 : Search 알고리즘은 두개의 반복자 구간을 인자로 받아, 두번째 구간에 담겨진 서브 시퀀스를 첫번째 구간 내에서 찾아 그 위치를 알아내는 알고리즘입니다. 

#include <iostream> #include <algorithm> #include <vector> #include <deque> #include <iterator> using namespace std; int main () { vector<int> vector1(20); deque<int> deque1(5); ostream_iterator<int> out(cout, " ,"); for(int i=0; i<20 ; ++i) { vector1[i] = i; } //벡터에 0~19까지 들어간다. copy(vector1.begin(), vector1.end(), out); cout<<endl; for(int i=0; i<5; ++i) deque1[i] = i+5; //데큐에는 5~9까지 들어간다. copy(deque1.begin(), deque1.end(), out); cout<<endl; //벡터 내에서 데큐와 동일한 시퀀스가 맨 처음 나타나는 위치를 찾는것 vector<int>::iterator k = search (vector1.begin(), vector1.end(), deque1.begin(), deque1.end()); for(int i =0; i<5; ++i) { cout<<(*(k + i )) <<endl; } return 0; }

search 알고리즘도 역시 조건자 버전을 가지고 있습니다.