[ 혼연 정리 ] STL 알고리즘 - 5 [ 변경 알고리즘 ]

ㅇ 요소 제거
 - 요소를 제거하는 함수는 조건에 맞는 요소를 찾아 제거하는 시늉을 한다.
 - 실제로 요소를 제거하지는 못한다. ==> 일반성을 가진 알고리즘이 조작할 권한이 없기 때문

ㅇ remove(), removeif

FwdIt remove(FwdIt first, FwdIt last, const Type& val);
FwdIt remove_if(FwdIt first, FwdIt last, UniPred F);
OutIt remove_copy(FwdIt first, FwdIt last, OutIt result, const Type& val);
OutIt remove_copy_if(FwdIt first, FwdIt last, OutIt result, UniPred F);

 - remove  함수는 작업 대상이 되는 반복자 구간과 제거할 값을 인수로 전달받아 first ~ last 사이의 값을 제거한다.
 - remove_if는 단항 조건자 F가 true를 리턴하는 요소를 선택한다는 점이 다르다.
 - remove 는 실제로 요소를 제거하지는 않으며 제거 대상이 아닌 요소들을 골라 구간의 앞쪽으로 이동시키고 남은 요소의 시작을 가리키는 반복자를 리턴
 - 제거 대상이 아닌 \요소의 원래 순서는 유지되므로 안정성이 있다. 요소가 실제로 제거 되지 않고 위치만 바뀌므로  컨테이너 크기는 변하지 않음
 - 요소를 실제로 제거하려면 컨테이너의 erase 멤버 함수를 호출

1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4
5 using namespace std;
6
7 template<typename C> void dump(const char *desc, C c)
8 {
9     cout.width(12);cout << left << desc << "==> ";
10     copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," "));
11     cout << endl;
12 }
13
14 void main()
15 {
16     int ari[]={3,1,4,1,5,9,2,6,5};
17     vector<int> vi(&ari[0],&ari[sizeof(ari)/sizeof(ari[0])]);
18     vector<int>::iterator it;
19
20     dump("원본",vi);
21     it=remove(vi.begin(),vi.end(),1);
22
23     dump("remove",vi);
24     vi.erase(it,vi.end());
25
26     dump("erase",vi);
27 }

 - 동작이 다소 복잡하다 밑의 그림을 보면 이해가 될것이다.

- remove는 왜 이렇게 복잡한 과정을 거쳐서 요소를 삭제하도록 되었을까?
- remove는 지금 자신이 검색하고 있는 컨테이너가 벡터라는 것을 모른다. 따라서 실제로 요소를 삭제하기 위해 어떻게 컨테이너를 조작해야 하는지 알지 못한다.
- 즉 조작 컨테이너가 어떤 구조를 가지는지도 모르고 어떻게 조작하는지도 알 수 없으며 오로지 반복자로 값을 읽고 쓰고 교환하는 것만 가능하다.
- 그래서 remove가 해줄 수 있는 일은 고작 삭제 대상 요소와 그렇지 않은 요소를 구분해 놓고 그 경계의 반복자를 리턴하는 것뿐이다
- 실제 삭제는 해당 컨테이너의 erse 멤버 함수가 처리해야 한다.
- 리스트의 remove멤버 함수는 멤버이므로 검색과 동시에 삭제가 가능하다.

ㅇ remove_copy()
 - 새로운 컨테이너를 만들면서 제거를 겸할 수 있다.


1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4
5 using namespace std;
6
7 template<typename C> void dump(const char *desc, C c)
8 {
9     cout.width(12);cout << left << desc << "==> ";
10     copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," "));
11     cout << endl;
12 }
13
14 void main()
15 {
16      int ari[]={3,1,4,1,5,9,2,6,5};
17      vector<int> vi(&ari[0],&ari[sizeof(ari)/sizeof(ari[0])]);
18      vector<int> vi2;
19
20      remove_copy(vi.begin(),vi.end(),back_inserter(vi2),1);
21      dump("vi",vi);
22      dump("vi2",vi2);
23 }

ㅇ unique()
  - 일종의 제거 함수 , remove와 동작방식이 유사

FwdIt unique(FwdIt first, FwdIt last [,BinPred F]);
OutIt unique(FwdIt first, FwdIt last, OutIt result [,BinPred F]);

  - 반복자 구간에서 연속된 중복 요소를 제거한다.
  - 중복되었다는 조건의 디폴트는 == 이지만 이항 조건 F로 사용자가 중복 조건을 지정할 수도 있다.
  - remove 와 마찬가지로 실제로 요소를 삭제하는 않으며 중복되지 않은 요소들만 앞쪽으로 이동시킨다.

1 #include <iostream>
2 #include <algorithm>
3
4 using namespace std;
5
6 void main()
7 {
8      char str[]="abcccddefggaghi";
9      char *p;
10     
11 puts(str); 12      p=unique(&str[0],&str[strlen(str)]);
13     *p=0;
14      puts(str);
15 }

- unique 는 구간내의 중복 된것을 모두 제거하는 것이 아니라 인접된 중복 요소만 제거한다.



ps : 출처 및 자세한 내용은  www.WinAPI.co.kr 참고