1. STL에서 제공하는 연산 조건자

1. 비교 연산 조건자
   • 아래 함수 객체는 모두 이항 조건자

2. 논리 연산 조건자

2. 연산 조건자 사용 법

1. less<T>
   • 헤더 추가 : <functional>
   • 일반적으로 아래 방법 사용
   • less<int>()(10, 20);

less<int> oLess;   // 객체 생성

// 1. 암묵적 호출
oLess(10, 20);

// 2. 명시적 호출
oLess.operator()(10,20);

// 3. 임시 객체로 암묵적 호출(일반적인 사용)
less<int>()(10,20);

// 4. 임시 객체로 명시적 호출
less<int>().operator()(10,20);

2. logical_and
   • 헤더 추가 : <functional>

int n = 30;
logical_and<bool> oAnd;

// 1. 암묵적 호출
oAnd(
   greator<int>()(n,10),
   less<int>()(n, 50)
);
// n이 10보다 크고, 50 보다 작은가? true

// 2. 명시적 호출
oAnd.operator()(
   greator<int>()(n,10),
   less<int>()(n, 50)
);

// 3. 임시 객체로 암묵적 호출(일반적 사용)
logical_and<bool>()(
   greator<int>()(n,10),
   less<int>()(n, 50)
);

// 4. 임시 객체로 명시적 호출
logical_and<bool>().operator()(
   greator<int>()(n,10),
   less<int>()(n, 50)
);

3. 사용자 정의 구현

1. less
   • binary_function 상속
   • 첫번째 , 두번째 인자 : T
   • 리턴 인자 : bool
   • operator 함수는 const

template<typename T>
struct Less: public binary_function<T,T,bool>{
   bool operator()(const T& left, const T& right) const{
      return left < right;
   }
};

2. logical_and
```cpp
template<typename T>
struct Logical_and: public binary_function<T,T,bool>{
   bool operator()(const T& left, const T& right) const{
      return left && right;
   }
}

4. 알고리즘과 같이 사용하는 예

1. count_if 로 같이 사용 예
   • count_if는 단항 조건자를 요구
   • bind2nd<T> 어댑터 사용하여 이항 조건자를 단항 조건자로 변경

vector<int> v = {10,20,30,40,50};
// 1. 20보다 작은 원소 개수
count_if(
   v.begin(),
   v.end(),
   bind2nd<less<int>>(
      less<int>(), 20
      )
);
// 1개

// 2. 20보다 작거나 같은 원소 개수
count_if(
   v.begin(),
   v.end(),
   bind2nd<less_equal<int>>(
      less_equal<int>(), 20
      )
);
// 2 개

// 3. 20보다 큰 원소 개수
count_if(
   v.begin(),
   v.end(),
   bind2nd<greater<int>>(
      greater<int>(), 20
      )
);
// 3개

// 4. 20보다 크거나 같은 원소 개수
count_if(
   v.begin(),
   v.end(),
   bind2nd<greater_equal<int>>(
      greater_equal<int>(), 20
      )
);
// 4개

// 5. 20과 같은 원소 개수
count_if(
   v.begin(),
   v.end(),
   bind2nd<equal_to<int>>(
      equal_to<int>(), 20
      )
);
// 1 개

// 5. 20과 다른 원소 개수
count_if(
   v.begin(),
   v.end(),
   bind2nd<not_equal_to<int>>(
      not_equal_to<int>(), 20
      )
);
// 4 개

참고

1. 뇌를 자극하는 C++ STL

1. STL에서 제공하는 산술 연산 함수 객체

2. 사용 법

1. plus<T>
   • 헤더 추가 : <functional>
   • 일반적으로 아래 방법 사용
   • plus<int>()(10, 20);

plus<int> Plus;   // 객체 생성

// 1. 암묵적 호출
oPlus(10, 20);

// 2. 명시적 호출
oPlus.operator()(10,20);

// 3. 임시 객체로 암묵적 호출(일반적인 사용)
plus<int>()(10,20);

// 4. 임시 객체로 명시적 호출
plus<int>().operator()(10,20);

3. 알고리즘과 같이 사용하는 예

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

//1. plus<int>()
transform(v1.begin(), v1.end(), v2.begin(), v3.begin(), plus<int>());
// v3 = {11,22,33,44,55}

//2. multiplies<int>()
transform(v1.begin(), v1.end(), v2.begin(), v3.begin(), multiplies<int>());
// v3= {10, 40, 90,  160, 250}

//3. negate<int>() : 부호 변경
transform(v1.begin(), v1.end(), v3.begin(), negate<int>());
// v3 = {-10, -20, -30, -40, -50}

// 4. minus<int>() + 인접 원소와의 차이
adjacent_difference(
   v1.begin(),
   v1.end(),
   v3,begin(),
   minus<int>()
);
// v3 = {10, 10, 10, 10, 10}

// 5.multiplies<int>() + 곱 누적
partial_sum(
   v1.begin(),
   v1.end(),
   v3.begin(),
   multiplies<int>()
);
// v3 = {10, 200, 6000, 240000, 12000000}

// 6.multiplies<int>() + 모든 원소 곱
int mul = accumulate(
   v1.begin(),
   v1.end(),
   1,
   muliplies<int>()
);
// mul = 12000000

참고

1. 뇌를 자극하는 C++ STL

1. 용어 정리

1. 함수 객체란?
   • operator() 연산자를 오버로딩한 클래스 객체
   • 다른 이름으로 functor(함수자)라고 불림
2. 함수류 : 함수 객체, 함수, 함수 포인터

2. 함수 객체 종류

1. 일반 함수 객체 : 특정 기능을 수행

   • 산술 연산 함수 객체 : 산술 연산 기능 수행
   • 비교 연산 함수 객체 조건자 : 비교 조건자

2. 함수 어댑터 : 함수류를 인자로 받아 다른 함수 객체로 변환

   • 바인더: 이항 함수 객체를 단항 함수 객체로 변환
   • 부정자 : 함수 객체 조건자를 반대로 변환
   • 함수 포인터 어댑터 : 함수 포인터를 STL이 요구하는 함수 객체로 변환
   • 멤버 함수 포인터 어댑터 : 멤버 함수 포인터를 함수 객체로 변환

3. 조건자

1. bool 형식을 반환하는 함수류
   • 함수 객체 조건자
   • 함수 조건자
   • 함수 포인터 조건자
2. STL에서 조건자?
   • 모두 함수 객체 조건자
   • 조건자는 객체의 상태값을 변경할 수 없음
   • operator() 연산자 오버로딩 함수는 모두 const

4. 어댑터

1. 함수 객체를 다른 함수 객체로 변환할 때 사용
2. 어댑터 인자로 사용되는 단항 함수 필요 조건
   • argument_type 정의 필요
   • result_type 정의 필요
3. 어댑터 인자로 사용되는 이항 함수 필요 조건
   • first_argument_type 정의
   • second_argument_type 정의
   • result_type 정의

template<typename T>
struct Plus{
   typedef T first_argument_type;
   typedef T second_argument_type;
   typedef T result_type;

   T operator()(const T& left, const T& right) const{
      return left + right;
   }
};

vector<int> v1 = {10,20,30};
vector<int> v3(3);

// Plus 함수를 단항 함수로 변경
transform(
   v1.begin(),
   v1.end(),
   v3.begin(),
   binder1st<Plus<int>> (Plus<int>(), 100)
   );
// v3 = {110, 120 , 130}

4. 단항, 이항 함수 형식 정의 방법
   • 위 조건 정의 대신 아래 클래스 상속
   • unary_function : 단항 함수 정의시
   • binary_function : 이항 함수 정의시

template<typename T>
struct Plus: public binary_function<T,T,T>{
   T operator()(const T& left, const T& right) const{
      return left+right;
   }
};

vector<int> v1 = {10,20,30};
vector<int> v3(3);

// Plus 함수를 단항 함수로 변경
transform(
   v1.begin(),
   v1.end(),
   v3.begin(),
   binder1st<Plus<int>> (Plus<int>(), 100)
   );
// v3 = {110, 120 , 130}

참고

1. 뇌를 자극하는 C++ STL

0. 수치 알고리즘

1. <numeric> 헤더에 포함됨

1. 수치 리스트

2. 상세 내용

1. accumulate(b,e,x)
   • 순차열 원소의 합을 구함

vector<int> v = {10,20,30,40,50};
int sum = accumulate(v.begin(), v.end(), 0);
// sum = 150 = 0+10+20+30+40+50

int sum2 = accumulate(v.begin(), v.end(), 100);
// sum = 250 = 100+10+20+30+40+50+

2. accumulate(b,e,x,f)
   • 순차열 원소에 f함수 적용 가능
   • f는 이항 함수
   • 함수에 따라 누적합,누적곱 등 연산 가능

// 1. Functor
template<typename T>
struct Plus{
   T operator() (const T& left, const T& right){
      return left+right;
   }
};

// 2. 클라이언트
void main(){
   vector<int> v = {1,2,3,4,5};
   // 사용자가 정의한 합함수
   int a = accumulate(v.begin(), v.end(), 0, Plus<int>());
   // a = 15 = 0+1+2+3+4+5

   // stl multiplies
   int mul = accumulate(v.begin(), v.end(), 1, multiplies<int>());
   // mul = 120 = 1 * 1 * 2 * 3 * 4 * 5
}
// 3. 서버
T accumulate(Iterator first, Iterator last, T x, Function fun){
   T ret = x;
   for(Iterator p = first; p != last ; ++p){
      ret = fun(ret, *p);
   }
   return ret;
}

3. inner_product(b,e,b2,x)
   • 두 순차열의 내적 계산

vector<int> v1 = {1,2,3,4,5};
vector<int> v2 = {2,2,2,2,2};

int in = inner_product(v1.begin(), v1.end(), v2.begin(), 100);
// in = 130 = 100 + 1*2 + 2*2 + 3*2 + 4*2 + 5*2

4. inner_product(b,2,b2,x,f1,f2)
   • 다양한 원소 간의 연산과 누적 연산 수행 가능
   • 두 순차열의 원소끼리의 차이의 합을 계산하는 예제

int Plus(int left, int right){
   return left+right;
}

int Minus(int left, int right){
   return left-right;
}

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

int a = inner_product(
   v1.begin(), v1.end()
   , v2.begin(), 0, Plus, Minus);
// a = 140 = 0 + 10 -2 + 20 - 2 + 30 -2 + 40 -2 + 50 - 2

//서버 예시
T inner_product(Iter first, Iter first2, T x, Func1 fun1, Func2 fun2){
   T ret = x;
   for(Iter p = first, q = first2; p != last; ++p, ++q){
      ret = fun1(ret, fun2(*p,*q))
   }
   return ret;
}

5. adjacent_difference(b,e,t)
   • 순차열에서 연속한 원소 간의 차 계산

vector<int> v1 = {10,20,30,40,50};
vector<int> v2(5);
auto iter = adjacent_difference(
   v1.begin(), v1.end(), v2.begin()
);
// v2 = {10, 10, 10, 10, 10}
// 1번 10 => 10
// 2번 10 => 20 - 10
// ...
// iter - 1 = > 마지막 10을 가리킴

6. adjacent_difference(b,e,t,f)
   • 인접 원소와의 사용자 정의 함수 수행
   • EX) 인접 원소 합을 저장

int Plus(int left, int right){
   return left + right;
}

vector<int> v1 = {10,20,30,40,50}
vector<int> v2(5);
auto iter = adjacent_difference(
   v1.begin(), v1.end(), v2.begin(), Plus
);
// v2 = {10, 30, 50, 70, 90}
// 10 => 10
// 30 => 10 + 20
// ...
// iter - 1 = 90을 가리킴

7. partial_sum(b,e,t)
   • 순차열에서 시작부터 매 현재 원소까지의 합을 구함

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

auto iter = partial_sum(
   v1.begin(), v1.end(), v2.begin()
);
// v2 = {10, 30, 60, 100, 150}
// 10 => 10
// 30 => 10 + 20
// 60 => 10 + 20 + 30
// ...
// iter - 1 => 150을 가리킴

8. partial_sum(b,e,t,f)
   • 순차열에서 시작부터 매 현재 원소까지의 사용자 정의 연산을 수행함

int Multi(int left, int right){
   return left * right;
}

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

auto iter = partial_sum(v1.begin(), v1.end(), v2.begin(), Multi);
// v2 = { 10, 200, 6000, 240000, 12000000}
// 10 => 10
// 200 => 10 * 20
// 6000 => 10 * 20 * 30
// ...
// iter - 1 => 12000000을 가리킴

참고

1. 뇌를 자극하는 C++ STL

0. 정렬된 범위 알고리즘

1. 정렬된 구간에서만 동작하는 알고리즘
2. 원소가 같음 비교시 a==b 연산 사용 안함
3. 원소가 같은 비교시 !(a<b) && !(b<a) 사용

1. 정렬 알고리즘 리스트

2. 상세 예시

1. binary_search(b,e,x)

   • 구간 [b,e)에서 x와 같은 원소가 있음 true

vector<int> v = {10,20,30,40,50};
bool b = binary_search(v.begin(), v.end(), 20);
// b = true

2. binary_search(b,e,x,f)
   • f를 조건자(이항 함수)로 사용하여 찾음

bool Pred(int left, int right){
   return 3 < right - left;
} // 오른쪽이 왼쪽보다 3보다 크면 참

vector<int> v = {40,46,12,80,10,47,30,55,90,53};
sort(v.begin(), v.end(), Pred);
// 조건자에 의한 정렬
// v = {12,10,30,40,46,47,55,53,80,90}
// 12와 10의 차이가 3보다 작기 때문에 12가 앞
// 55와 53의 차이가 3보다 작기 때문에 55가 앞

bool b = binary_search(v.begin(), v.end(), 32, Pred);
// b = true
// !Pred(30,32) => true 이고,
// !Pred(32,30) => true 이므로,
// 참조건 (!Pred(30,32)&&!Pred(32,30)) = true

3. includes(b,e,b2,e2)
   • [b,e) 에 [b2,e2)가 포함되면 true

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

bool b1 = includes(v1.begin(), v1.end()
                  ,v2.begin(), v2.end());
// b1 = true
// v2는 v에 포함되므로

bool b2 = includes(v1.begin(), v1.end(), v2.begin(), v2.end());
// b2 = false
// v3의 60은 v에 포함되지 않으므로

//조건자 사용
sort(v1.begin(), v1.end(), greater<int>());
sort(v2.begin(), v2.end(), greater<int>());
b1 = includes(v1.begin(), v1.end()
            , v2.begin(), v2.end()
            , greater<int>())

4. lower _bound, upper _bound, equal_range
   • 찾는 원소가 여러 개 일 때 반복자 반환
   • lower_bound : 첫 원소의 반복자 반환
   • upper_bound : 마지막 다음 원소 반복자 반환
   • equal_range : [lower_bound, upper_bound) pair 반환

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

auto lower = lower_bound(v.begin(), v.end(), 30);
auto upper = upper_bound(v.begin(), v.end(), 30);
auto eual = equal_range(v.begin(), v.end(), 30);
// lower = 첫 30을 가리킴
// upper = 마지막 30의 다음 40을 가리킴
// eqaul = (lower,upper)의 pair 형태

5. merge(b,e,b2,e2,t)
   • 정렬된 두 순차열을 목적지 순차열로 병합

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

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

6. inplace_merge(b,m,e)
   • 하나의 순차열이 두 구간으로 정렬되어 있을 때
   • 하나의 구간으로 정렬 가능

vector<int> v = {10,20,30,40,50,20,30,60};
// v => 10,20,30,40,50 과
// 20,30,60 의 두 개의 구간으로 정렬되어 있음

inplace_merge(v.begin(), v.begin()+5, v.end());
// v = {10,20,20,30,30,40,50,60} 으로 정렬됨

3. 집합 관련 알고리즘

1. set_union(b,e,b2,e2,t)
   • 두 순차열의 합집합을 구함
2. set_intersection(b,e,b2,e2,t)
   • 두 순차열의 교집합을 구함
3. set_difference(b,e,b2,e2,t)
   • 두 순차열의 차집합을 구함
4. set_ symmetric_difference(b,e,b2,e2,t)
   • 두 순차열의 대칭 차집합을 구함

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

// 1. 합집합
auto iter = set_union(
   v1.begin(), v1.end()
  ,v2.begin(), v2.end()
  ,v3.begin());
// v3 = {10,20,30,40,50,60,0,0,0,0}
// iter - 1 => 60을 가리킴

// 2. 교집합
auto iter = set_intersection(
   v1.begin(), v1.end()
  ,v2.begin(), v2.end()
  ,v3.begin());
// v3 = {20,30,0,0,0,0,0,0,0,0}
// iter - 1 => 30을 가리킴

// 3.차집합
auto iter = set_difference(
   v1.begin(), v1.end()
  ,v2.begin(), v2.end()
  ,v3.begin());
// v3 = {10,40,50,0,0,0,0,0,0,0}
// iter - 1 => 50을 가리킴

// 4. 대칭 차집합
auto iter = set_symmetric_difference(
   v1.begin(), v1.end()
  ,v2.begin(), v2.end()
  ,v3.begin());
// v3 = {10,40,50,60,0,0,0,0,0,0}
// iter - 1 => 60을 가리킴

참고

1. 뇌를 자극하는 C++ STL

0. 정렬 알고리즘

1. 변경 알고리즘의 특수한 형태
2. 특정 정렬 기준으로 원소의 순서를 변경 및 정렬

1. 정렬 알고리즘 리스트

2.힙 관련 알고리즘

1. 자료 구조 힙
   • 완전 이진 트리로 구성
   • 트리 내의 모든 원소가 부모 노드보다 큰 값(또는 작은 값)을 가짐
   • 루트 노드는 항상 가장 작은 값(또는 가장 큰 값)을 가짐
   • 최대값, 최소값 연산이 빠름
2. 힙의 연산
   • 추가 연산
     • 완전 이진 트리 가장 끝에 원소 추가
     • 힙의 규칙을 깨지 않게 교환하여 힙을 유지
   • 제거 연산
     • 루트 노드를 삭제
     • 삭제된 루트 노드에 힙의 마지막 노드 가져옴
     • 힙의 규칙 깨지 않게 교환하여 힙을 유지
3. heap 예제
   • min heap : v = {1,3,2,4,6,5}
   • max heap : v = {6,5,3,4,2,1}
     

     

4. make_heap(b,e)
   • 구간 [b,e)의 순차열을 힙 구조로 만듦

vector<int> v = {10,20,30,40,50,60};
// 1. 최대 heap 생성
make_heap(v.begin(), v.end());
// v = {60,50,30,40,20,10}

// 2. 최소 heap 생성
make_heap(v.begin(), v.end(), greater<int>());
// v= {10,20,50,30,40,60}

5. push_heap(b,e)
   • 원소가 추가된 상태에서 사용
   • 추가된 구간 [b,e) heap을 교환하여 heap을 유지함.
   • 일반적으로 push_back()과 함께 사용

//위의 예제 수행 후
v.push_back(35);
// 마지막에 단순 원소 추가
// v = {60,50,30,40,20,10,35}
push_heap(v.begin(), v.end());
// v = {60,50,35,40,20,10,30}
// heap 형태를 재계산

6. pop_heap(b,e)
   • root node를 (논리적)제거(제일 마지막으로 이동)
   • 원리
     • root node와 마지막 node를 교환
     • heap을 유지하도록 교환 반복

vector<int> v = {10,20,30,40,50,60};
make_heap(v.begin(), v.end());
// v = {60,50,30,40,20,10}
pop_hep(v.begin(), v.end());
// v= {50,40,30,10,20,60}

7. sort_heap(b,e)
   • 구간 [b,e)를 heap 정렬
   • 구간 [b,e)가 heap 구조여야 함

vector<int> v = {10,20,30,40,50,60};
make_heap(v.begin(), v.end());
// v = {60,50,30,40,20,10}
sort_heap(v.begin(), v.end());
// v= {10,20,30,40,50,60}

3. 기타 정렬 알고리즘 상세

1. nth_element(b,m,e)
   • 전체 구간 [b,e) 에서 구간 [b,m) 만큼의 순차열을 부분적으로 정렬
   • 주로 n 개의 요소를 선별할 때 사용
   • 또는 n 번째 요소가 필요할 때 사용

vector<int> v = {10,30,20,40,50,60};
nth_element(v.begin(), v.begin() + 1, v.end());
// 두번째로 작은 값 : v[1] = 20

2. sort(b,e)
   • 퀵 정렬을 기반으로 정렬

vector<int> v = {5,1,3,2,7,9,8};
//오름차순 정렬(less: defualt)
sort(v.begin(), v.end());
// v = {1,2,3,5,7,8,9}

//내림차순 정렬(greater)
sort(v.begin(), v.end(), greater<int>());
// v = {9,8,7,5,3,2,1}

3. stable_sort(b,e)
   • 머지 정렬을 기반으로 정렬
   • 같은 원소의 상대적인 순서를 유지할 때 사용

vector<int> v= {30,50,30,20,40,10,40};
//오름차순 정렬(less: defualt)
stable_sort(v.begin(), v.end());
// v = {10,20,30,30,40,40,50}

//내림차순 정렬(greater)
stable_sort(v.begin(), v.end(), greater<int>());
// v = {50,40,40,30,30,20,10}

4. partial_sort(b,m,e)
   • heap정렬 기반으로 정렬
   • 순차열의 상위 구간만 정렬할 때 사용
   • heap정렬의 특징이 필요할 때 사용
   • m과 e가 같다면 전체 원소를 정렬함

vector<int> v = {10,30,20,40,50,60};
partial_sort(v.begin(), v.begin() + 3, v.end());
// v.begin() 부터 3개까지만 heap 정렬함
// v = {10,20,30,40,50,60}

5. partial _sort_copy(b,e,b2,e2)
   • 구간 [b,e) 를 heap정렬 하고,
   • 구간 [b2,e2)에 정렬 결과를 저장함.

vector<int> v = {10,30,20,40,50,60};
vector<int> v2(3);
partial_sort_copy(v.begin(), v.end(), v2.begin(), v2.end());
// v.begin() 부터 3개까지만 heap 정렬함
// v2 = {10,20,30}

참고

1. 뇌를 자극하는 C++ STL
2. https://velog.io/@nninnnin7/HEAP

0. 변경 알고리즘

1. 순차열 원소의 '순서'를 변경하는 알고리즘
   • 순차열의 원소를 교환
   • 순차열의 원소를 이동

1. 변경 알고리즘 리스트

2. 상세 예시

1. next_permutation(b,e)
   • 예시) v = 10,20,30
   • 6가지 순열을 만듦

vector<int> v = {10,20,30}
while(next_permutation(v.begin(), v.end())){
// 1. v = {10, 30, 20} , b = true
// 2. v = {20, 10, 30} , b = true
// 3. v = {20, 30, 10} , b = true
// 4. v = {30, 10, 20} , b = true
// 5. v = {30, 20, 10} , b = true
// 6. v = {10, 20, 30} , b = false
}

2. next_permutation(b,e,f)
   • 이항 조건자 f를 기준으로 순열 만듦

bool Pred(const Point& left, const Point& right){
   return left.getY() < right.getY();
}  // Point의 y좌표가 오른쪽이 더 크면 true

vector<Point> v;
v.push_back(Point(5,1));
v.push_back(Point(7,2));
v.push_back(Point(5,3));

while(next_permutation(v.begin(), v.end(), Pred)){
   // 1. v = {(5,1), (5,3), (7,2)}, b = true
   // 2. v = {(7,2), (5,1), (5,3)}, b = true
   // 3. v = {(7,2), (5,3), (5,1)}, b = true
   // 4. v = {(5,3), (5,1), (7,2)}, b = true
   // 5. v = {(5,3), (7,2), (5,1)}, b = true
   // 6. v = {(5,1), (7,2), (5,3)}, b = false
}

3. partition(b,e,f)
   • 순차열의 원소를 특정 조건에 따라 분류
   • 원리 : quick sort 에서 pivot 값을 기준으로 큰값과 작은값을 분류하듯 분류함
   • 30,40,50,10,20,60 => 30 그대로
   • 30,20,50,10,40,60 => 40,20 교환
   • 30,20,10,50,40,60 => 50,10 교환

bool Pred(int n){
   return n < 40;
} // 40 작으면 참

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

// 2.stable_partition
vector<int> v2 = {30,40,50,10,20,60};
iter = stable_partition(v2.begin(), v2.end(), Pred);
// v = 30,10,20,40,50,60
// iter -1 => 20을 가리킴
// [begin,iter) => {30,10,20}
// [iter,end) => {40,50,60}

4. stable_partition(b,e,f)

   • partition와의 차이 => 원소의 상대적인 순서를 변경안함
   • 위의 예제 참고
   • 원리
   • 30,40,50,10,20,60 => 30 그대로
   • 30,10,50,40,20,60 => 40, 10 교환
   • 30,10,20,40,50,60 => 50, 20 교환

5. random_suffle(b,e)

   • 구간 [b,e)의 순차열을 랜덤으로 섞음
   • 초기화는 <cstdlib> 헤더의 srand() 사용

vector<int> v = {10,20,30,40,50};
random_shuffle(v.begin(), v.end());
// {50,20,40,30,10} : 랜덤으로 값 뒤섞임

6. reverse(b,e)
   • 구간 [b,e)의 원소를 뒤집는다.

vector<int> v = {10,20,30,40,50};
reverse(v.begin(), v.end());
// v = {50,40,30,20,10}

7. reverse_copy(b,e,t)
   • 뒤집은 순차열을 구간 [t,p)에 저장

vector<int> v1 = {10,20,30,40,50};
vector<int> v2(5);
auto iter = reverse_copy(v1.begin(), v1.end(), v2.begin());
// v2 = {50,40,30,20,10}
// iter - 1 => 10을 가리킴

8. rotate(b,m,e)
   • 순차열을 회전
   • m 이 begin이 되고, (m-b) 만큼 이동함

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

rotate(v.begin(), v.begin() + 2, v.end());
// v = {30,40,50,10,20} : 2만큼 회전

9. rotate_copy(b,m,e,t)
   • 순차열을 회전하여 [t,p)에 복사

vector<int> v1 = {10,20,30,40,50};
vector<int> v2(5);
auto iter = rotate_copy(v1.begin(), v1.begin() + 2, v1.end(), v2.begin());
//v2 = {30,40,50,10,20}

참고

뇌를 자극하는 C++ STL

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