0. 제거 알고리즘

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

1. 제거 알고리즘 리스트

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

1. 원소를 수정하는 알고리즘 리스트

2. 예시

1. copy()

vector<int> v1 = {10,20,30,40,50};
vector<int> v2(5);

auto iter = copy(v1.begin(), v1.end(), v2.end());
// v2에 v1의 값을 복사
// iter - 1 이 50을 가리킴

2. copy_backward()
   • v2의 마지막 위치 부터 데이터를 복사함

vector<int> v1 = {10,20,30,40,50};
vector<int> v2(10);

auto iter = copy_backward(v1.begin(), v1.end(), v2.end());
// v2 = 0, 0, 0, 0, 0, 10, 20, 30, 40, 50
// iter 는 10의 위치 가리킴

3. fill , fill_n
   • fill : 구간 [begin, end) 를 x로 채움
   • fill_n : begin부터 n개 개수만큼 x로 채움

vector<int> v = {10,20,30,40,50};
fill(v.begin(), v.end(), 0);
// v를 0으로 채움
fill_n(v.begin(), 3, 55);
// v.begin 부터 3개 만큼을 55로 채움

4. for_each()
   • functor의 인자를 &로 줘서 값 변경 가능

void Func(int& r){
   r += 5;
}  // 원소값에 5를 더함

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

for_each(v.begin(), v.end(), Func);
// v의 모든 원소에 5를 더함

5. generate, generate_n
   • 순차열의 모든 원소를 단순한 동작의 값으로 수정
   • for_each와의 차이 => 함수의 매개변수로 순차열의 원소를 전달하지 않음
   • generate(b,e,f) : 구간[b,e)의 모든 원소를 f()로 채움
   • generate(b,n,f) : b부터 n개 만큼 원소를 f()로 채움

class Integer{
   int data;
public:
   explicit Integer(int d= 0) : data(d) {}
   int operator()(){
      return data++;
   }
};

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

generate(v.begin(), v.end(), Integer(1));
// v를 1,2,3,4,5 로 채움

generate_n(v.begin(), 3, Interger(100));
// v 의 시작부터 3개까지 원소를 100, 101, 102로 채움

6. swap , iter_swap

   • swap(a, b) : a와 b를 교환
   • iter_swap(p,q) : iter p와 q의 값을 교환

7. merge(b,e,b2,e2,t)

   • 정렬된 구간 [b,e) 와 [b2,e2)를 합병 정렬
   • 결과는 [t,t+(e-b)+(e2-b2))의 순차열
   • 반드시 정렬되어 있어야 가능함
   • default는 less(오름차순 정렬)

vector<int> v1 = {10,30,50,60,80};
vector<int> v2 = {20,40,70};
vector<int> v3(10);
iter = merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
//v3 = 10,20,30,40,50,60,70,80,0,0
//iter -1 => 80을 가리킴

8. merge(b,e,b2,e2,t,f)
   • f는 [b,e), [b2,e2)의 정렬 기준

template<typename T>
struct Greater{
   bool operator()(const T& left, const T& right) const{
      return left > right;
   }
};

vector<int> v1 = {80,60,50,30,10};
vector<int> v2 = {70,40,20};
vector<int> v3(10);

iter = merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin(), Greater<int>());
// v3 = 80,70,60,50,40,30,20,10,0,0
// iter - 1 => 10 가리킴

9. replace(b,e,x,x2)
   • 순차열의 특정 원소를 다른 값으로 수정
   • [b,e)구간의 x인 원소를 x2로 수정

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

replace(v.begin(), v.end(), 30, 0);
// v 모든 원소 중 30을 0으로 변경
// v = {10,20,0,40,0,0,50};

10. replace_if(b,e,f,x2)

    • [b,e) 구간에서 f(*p)가 참인 원소를 x2로 변경

bool Pred(int n){
   return 30 <= n && n <= 50;
} // n이 30~50 인 경우 true

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

replace_if(v.begin(), v.end(), Pred, 0);
// v의 모든 원소 중 Pred가 참인 원소를 0으로 변경
// v = {10,20,0,0,0,60,70,80}

11. replace _copy, replace _copy_if
    • replace_copy(b,e,t,x,x2) : 구간 [b,e)에서 x를 x2로 변경 후 [t,p)로 복사
    • replace _copy_if(b,e,t,f,x2) : 구간 [b,e)에서 f가 참인 원소를 x2로 변경 후 [t,p)로 복사

bool Pred(int n){
   return n <= 30;
} // 30보다 작으면 참

vector<int> v1 = {10,20,30,40,30,50};
vector<int> v2(6);
vector<int> v3(6);

auto iter = replace_copy(v1.begin(), v1.end(), v2.begin(), 30, 0);
// v1의 모든 원소에서 30인 원소를 0으로 변환하여 [v2.begin(), iter) 에 저장

iter = replace_copy_if(v1.begin(), v1.end(), v3.begin(), Pred, 0);
// v1의 모든 원소에서 Pred가 참인 원소를 0으로 변환하여 [v3.begin(), iter) 에 저장

12. swap_ranges(b,e,b2)
    • 구간 [b,e)의 순차열과 [b2,b2+e-b)의 모든 원소를 교환

vector<int> v1 = {10,20,30,40,50};
vector<int> v2 = {11,22,33,44,55};

swap_ranges(v1.begin(), v1.end(), v2.begin());
// v1의 모든 원소와 v2의 원소를 교환
// v1 = {11,22,33,44,55}
// v2 = {10,20,30,40,50}

13. transform(b,e,t,f)
    • for_each()와의 차이점 => 원본의 순차열 변화 없이 목적지의 순차열로 저장
    • 구간 [b,e) 의 원소를 인자로 하는 함수 f를 호출
    • 반환값을 순차열 [t, t+(e-b))로 저장

int Func(int n){
   return n+5;
} // n에 5를 더함

vector<int> v = {10,20,30,40,50};
auto iter = transform(v.begin(), v.end(), v.begin(), Func);
// v의 모든 원소에 5를 더함
// v => {15,25,35,45,55}
// iter - 1 => 50을 가리킴

14. transform(b,e,b2,t,f)
    • 두 순차열의 원소에 함수 적용
    • 구간 [b-e) 와 [b2, b2+(e-b))의 순차열 반복자를 함수 f에 인자로 전달
    • 그 결과를 순차열[t, t+(e-b))에 저장

int Plus(int left, int right){
   return left+right;
}// left와 right를 더하는 함수

vector<int> v1 = {10,20,30,40,50};
vector<int> v2 = {1,2,3,4,5};
vector<int> v3(5);

auto iter = transform(v1.begin(), v1.end(), v2.begin(), v3.begin(), Plus);
// v1와 v2의 원소를 더해서 v3에 저장
// v3 => {11,22,33,44,55}
// iter - 1 => 55의 위치를 가리킴

참고

뇌를 자극하는 C++ STL

1. 원소를 수정하지 않는 알고리즘 리스트

2. 범위 내에 순차열 포함 여부 찾기

1. iter = find_end(v1.begin(), v1.end(), v2.begin(), v2.end())
   • v1의 [begin,end) 범위에서 v2의 [begin,end) 순차열을 포함하는 제일 마지막 반복자 반환

vector<int> v1 = {30,40,10,30,40};
vector<int> v2 = {30,40};

iter = find_end(v1.begin(), v1.end(), v2.begin(), v2.end());
// iter는 30의 두번째 위치를 반환

iter = search(v1.begin(), v1.end(), v2.begin(), v2.end());
// iter는 30의 첫번째 위치를 반환

2. iter = search(v1.begin(), v1.end(), v2.begin(), v2.end())

   • 위와 동일하지만 처음에 위치한 30의 위치 반환

3. iter = find_end(v1,begin(), v2.end(), v2.begin(), v2.end(), Pred)

   • Pred : d이항 함수(인자가 두개)
   • 범위 내에 비교하여 Pred함수가 모두 참인 구간 중 마지막 구간의 첫 원소의 위치를 반환

4. iter = search_n(v,begin(), v.end(), 3, 30)

   • [v.begin(), v.end()) 에서 30이 3번 연속한 첫 원소의 반복자 반환

5. iter = find _first_of(v1.begin(), v1.end(), v2.begin(), v2.end())

   • v1의 구간 [begin, end) 순차열에서 v2의 구간 [begin,end) 원소 중 같은 원소가 처음으로 발견되는 첫 원소의 반복자 반환

vector<int> v1 = {10,20,30,40,50};
vector<int> v2 = {40,80,20};

iter = find_first_of(v1.begin(), v1.end(), v2.begin(), v2.end())
// 20의 위치를 반환

6. iter = find _first_of(v1.begin(), v1.end(), v2.begin(), v2.end(), Pred)
   • Pred : 이항 연산자
   • Pred 함수가 청므으로 참이 나오는 위치 반환

bool Pred(int left, int right){
   return left > right;
} // 왼쪽 요소가 오른쪽 요소보다 크면 참

vector<int> v1 = {10,20,30,40,50};
vector<int> v2 = {40,80,20};

iter = find_first_of(v1.begin(), v1.end(), v2.begin(), v2.end(), Pred)
// 30이 처음으로 20보다 크모 30 위치 반환
// 10 < 40, 20 < 80, 30 >20

3. 기타

1. iter=adjacent(v.begin(),v.end())
   • v의 연속된 원소가 같아지는 첫 원소의 반복자 반환
   • 10,20,30,30인 경우 첫 30의 반복자 반환
   • 못찾으면 v.end()를 반환
   • 이항 조건자를 인자로 줘서 여러 조건으로 판단 가능

bool Pred(int a, int b){
   return abs(b-e) > 10;
} // 연속된 두 수의 절대값이 10보다 크면 참

iter = adjacent_find(v.begin(), v.end(), Pred)
// Pred 함수가 처음으로 참인 반복자 반환

2. int n = count(v.begin(), v.end(), 30)

   • [v.begin(),v.end()) 범위에서 30의 개수 리턴

3. int n = count_if(v.begin(), v.end(), Pred)

   • [v.begin(),v.end()) 범위에서 Pred 함수가 참인 개수 리턴

4. equal(v1.begin(),v1.end(),v2.begin())

   • v1의 begin~end 범위의 데이터가 v2와 같으면 참

5. eqaul(v1.begin(),v1.end(),v2.begin(),Pred)

   • v1의 begin~end 범위의 데이터와 v2의 데이터가 Pred 함수 인자로 들어가서 모두 참이면 참

bool Pred(int left, int right){
   return abs(right-left) < 5;
} // 두 원소의 차이가 5보다 작으면 참

vector<int> v1 = {10,21,30};
vector<int> v2 = {10,20,33};

bool b = equal(v1.begin(), v1.end(), v2.begin(), Pred)
// b는 true

6. for_each(v.begin(), v.end(), Print)
   • Print : 요소와 같은 형태의 인자를 가지는 단항 함수
   • v의 [begin,end) 범위의 요소를 Print 함수에 전달하여 함수 수행
   • 함수 객체를 전달하면 다양한 형태로 사용 가능

struct PrintFunctor{
   char fmt;
   explicit PrintFunctor(char c='') : fmt(c){}
   void operator()(int n)const {
      cout<<n<<fmt;
   }
}

for_each(v.begin(), v.end(), PrintFunctor());
// 원소 구분을 ''로 하여 출력
for_each(v.begin(), v.end(), PrintFunctor(,));
// 원소 구분을 ,로 하여 출력

7. 순차열 사전순 비교

   • lexicographical_compare(v1.begin(), v1.end(), v2.begin(), v2.end())
     • v1과 v2의 순차열 비교하여 v2가 크면 true 반환
     • ex) v1 = [10,20,30], c2=[10,20,50] => true 반환
   • greater() 를 인자로 추가하여 비교 기준 변경

8. max(pt1, pt2, XCompare)

   • Xcompare는 Point의 x좌표를 비교하는 이항 함수
   • Point 객체의 x좌표를 비교해 큰 객체 반환

9. iter = max_element(v.begin(), v.end())

   • v의 구간 [begin,end)에서 max값의 위치 반환

10. iter = min_element(v.begin(), v.end())

    • v의 구간 [begin,end)에서 min값의 위치 반환

11. iter = max_element(v.begin(), v.end(), Comp)

    • 벡터의 원소가 객체일 경우 비교 방법 Com 함수(이항 함수) 정의

12. iter_p = mismatch(v1.begin(), v1.end(), v2.begin())

    • v1과 v2의 원소가 다른 첫 위치를 반환
    • 반환값은 v1과 v2의 위치를 담은 pair 객체

참고

뇌를 자극하는 C++ STL