[STL-08] 알고리즘3-제거 알고리즘

0. 제거 알고리즘

1. 원소를 수정하는 알고리즘의 특수한 형태
2. 원소를 실제로 제거하지 않음
3. 논리적으로 제거(다음 원소로 덮어쓰기)함
4. 순차열의 size를 실제로 변경하지 않음
5. 실제 size 변경 필요시 컨테이너의 erase함수 사용

1. 제거 알고리즘 리스트

알고리즘	설명
p=remove(b,e,x)	구간 [b,e)의 순차열에서 x 원소가 남지 않도록 덮어쓰기로 이동. 알고리즘 수행 후 순차열은 [b,p)가 됨
p=remove_if(b,e,f)	구간 [b,e)의 순차열을 f(*p)가 참인 원소가 남지 않도록 덮어쓰기로 이동. 알고리즘 수행 후 순차열을 [b,p)가 됨
p=remove_copy(b,e,t,x)	구간 [b,e)의 순차열에서 *p==x가 아닌 원소만 순차열 [t,p)에 복사
p=remove _copy_if(b,e,t,f)	구간 [b,e)의 순차열에서 f(*p)가 참이 아닌 원소만 순차열 [t,p) 에 복사
p=unique(b,e)	구간 [b,e) 순차열을 인접한 중복 원소가 남지 않게 덮어쓰기로 이동. 알고리즘 수행 후 순차열은 [b,p)가 됨
p=unique(b,e,t)	구간 [b,e) 순차열에서 인접한 중복 원소가 아닌 원소를 순차열 [t,p)에 복사
p=unique(b,e,t,f)	구간 [b,e)의 순차열에서 f(*p)가 참인 인접한 중복 원소가 아닌 원소를 순차열 [t,p)에 복사

2. 상세 예시

1. remove(b,e,x)
   • 구간 [b,e) 순차열에서 x인 원소가 남지 않게 함

vector<int> v = {10,20,30,40,50};
auto iter = remove(v.begin(), v.end(), 30);
// v => 10,20,40,50,50
// iter - 1 => 첫번째 50을 가리킴
// 실제로 [v.begin,iter)는 10,20,40,50 이 됨

2. remove_if(b,e,f)
   • 구간 [b,e) 순차열에서 f(*p) 가 참인 원소가 남지 않게 함

bool Pred(int n){
   return 30 <= n && n <= 40;
} // 30~40 인 원소만 참

vector<int> v = {10,20,30,40,50};

auto iter = remove_if(v.begin(), v.end(), Pred);
// v => 10,20,50,40,50
// iter - 1 => 첫번째 50을 가리킴

3. remove_copy(b,e,t,x)
   • 순차열의 원본을 변경하지 않고 특정 원소를 제거하여 목적지 순차열에 복사

vector<int> v1 = {10,20,30,40,50};
vector<int> v2(5);
auto iter = remove_copy(v1.begin(), v1.end(), v2.begin(), 30);
// v1에서 30을 제거하고 v2에 복사
// v2 = {10,20,40,50,0}
// iter -1 => 50을 가리킴

4. unique(b,e)
   • 구간 [b,e)의 순차열을 인접한 중복 원소가 남지 않게 함
   • 원소를 삭제하지 않고 논리적으로만 제거

vector<int> v = {10,20,30,30,40,40,30,50};
auto iter = unique(v.begin(), v.end());
// v = {10,20,30,40,30,50,30,50}
// iter -1 => 첫 번째 50을 가리킴
// [v.begin(), iter) = {10,20,30,40,30,50}

5. unique(b,e,f)
   • 인접한 원소를 인자로 받은 이항 함수 f를 사용
   • 구간 [b,e) 의 인접한 원소의 함수 f가 참인 원소를 제거

bool Pred(int left, int right){
   return abs(right-left) < 10;
}// 인접한 원소 차이가 10 미만이면 삭제

vector<int> v = {10,11,30,32,40,50};

auto iter = unique(v.begin(), v.end(), Pred);
// v => {10,30,40,50,40,50}
// iter - 1 => 첫 번째 50을 가리킴
// [v.begin(), iter) => {10,30,40,50}

참고

뇌를 자극하는 C++ STL