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

0. 연관 컨테이너

1. 모든 연관 컨테이너는 노드 기반 컨테이너
2. 모든 연관 컨테이너는 균형 이진 트리
3. 모든 연관 컨테이너는 같은 인터페이스 제공
4. 찾기 연산에 뛰어난 성능을 보임(로그 시간)
5. 삽입 또한 로그 시간 복잡도
6. 기본 정렬은 less(오름차순 정렬)
7. 종류
   • set : key값의 집합, 중복 허용 안함
   • multiset : set인데 중복 허용
   • map : key, value쌍의 집합, 중복 허용 안함
   • multimap : map인데 중복된 key값 허용

1. set 컨테이너

1. key값의 집합을 가지는 컨테이너
2. 템플릿 형식

template<typename key,
         typename Pred=less<Key>,
         typename Allocator=allocator<Key>
>
class set

3. 생성자

   코드	내용
   set s	s는 빈 컨테이너
   set s(pred)	s는 빈 컨테이너로 정렬 기준은 pred 조건자 사용
   set s(s2)	s는 s2 컨테이너의 복사본(복사 생성자 호출)
   set s(b,e)	s는 반복자 구간 [b,e)로 초기화된 원소 가짐
   set s(b,e,Pred)	s는 반복자 구간[b,e)로 초기화된 원소 가짐(정렬 기준은 pred 조건자 사용)

4. 멤버 함수

   코드	내용
   p=s.begin()	p는 s의 첫원소를 가리키는 반복자
   p=s.end()	p는 s의 끝을 나타내는 반복자
   s.clear()	s의 모든 원소 제거
   s.empty()	s가 비었는지 조사
   n=s.count(k)	원소 k의 개수 반환
   pr=s.equal_range(k)	pr은 k 원소의 반복자 구간인 pair 객체
   q=s.erase(p)	p가 가리키는 원소 제거(q는 다음 원소 가리킴)
   q=s.erase(b,e)	반복자 구간[b,e)의 모든 원소를 제거(q는 다음 원소)
   n=s.erase(k)	k 원소를 모두 제거, n은 제거 개수
   pr=s.insert(k)	s 컨테이너에 k 삽입. pr은 삽입한 원소를 가리키는 반복자와 성공 여부의 bool값인 pair 객체
   q=s.insert(p,k)	p가 가리키는 위치부터 빠르게 k를 삽입. q는 삽인한 원소를 가리킴
   s.insert(b,e)	반복자 구간[b,e)의 원소를 삽입
   pred=s.key_comp()	s의 key 정렬 기준인 조건자 반환(pred)
   pred=s.value_comp()	s의 value 정렬 기준인 조건자 반환(pred)
   p=s.lower_bound(k)	p는 k의 시작 구간을 나타내는 반복자
   p=s.upper_bound(k)	p는 k의 끝 구간을 가리키는 반복자
   n=s.max_size()	n는 s가 담을 수 있는 최대 원소 개수(메모리 크기)
   p=s.rbegin()	p는 s의 역 순차열의 첫 원소를 가리키는 반복자
   p=s.rend()	p는 s의 역 순차열의 끝을 표식하는 반복자
   s.size()	s 원소의 개수
   s.swap(s2)	s와 s2를 swap

5. 연산자

   코드	내용
   s1==s2	s1과 s2의 모든 원소가 같은가?
   s1!=s2	s1과 s2의 원소중 하나라도 다른가?
   s1 < s2	문자열 비교처럼 s2가 s1보다 큰가?

6. 멤버 형식

   코드	내용
   allocator_type	메모리 관리자 형식
   const_iterator	const 반복자 형식
   const_pointer	const value_type* 형식
   const_reference	const value_type& 형식
   const _reverse_iterator	const 역 반복자 형식
   difference_type	두 반복자 차이의 형식
   iterator	반복자 형식
   key_compare	키 조건자 형식
   key_type	key의 형식
   pointer	value_type* 형식
   reference	value_type& 형식
   reverse_iterator	역 반복자 형식
   size_type	첨자(index)나 원소의 개수 등의 형식
   value_compare	원소 조건자 형식
   value_type	원소의 형식

2 상세 내용

1. 원소 추가는 insert() 만 제공
   • push _back() , pop_front() 등의 함수 제공 안함
   • 반환값은 pair객체이면 first는 키의 위치를 가리키는 반복자
   • second 는 성공 실패를 나타내는 bool
   • 중복값이 있을 경우 second의 false 리턴
   • 예제

set<int> s;
pair<set<int>::iterator, bool> pr;
pr = s.insert(50);
// pr.first : 50이 삽입된 위치를 가리키는 반복자
// pr.second : true
pr = s.insert(50);
// pr.first : 존재하는 50의 위치를 가리키는 반복자
//pr.second : false

2. s.insert(pr.first, 85)

   • pr.first 위치부터 탐색 시작하여 85 삽입

3. set<int, greater<int>> s

   • 정렬 기준을 greater(내림차순)으로 s 생성

4. set의 조건자 반환(정렬 기준 함수 객체)

   • key_compare : 정렬 기준 함수를 담는 형식
   • key_comp() : set의 정렬 기준 함수 반환

set<int, less<int>> s_less;
set<int, less<int>>::key_compare l_cmp = s_less.key_comp();

5. s.count(50)

   • 50의 원소 개수 반환
   • set은 중복 허용 안하므로 1개

6. s.find(30)

   • 30을 찾아 반복자 반환
   • 찾는게 없으면 s.end() 반환
   • s.find(30) != s.end() 이면 찾은 것!

7. find 원리

   • 정렬 기준 조건자를 이용

if(s.key_comp()(a,b)) && !(s.key_comp()(b,a))
// 위의 조건이 참이면 두 원소는 같다고 판단함
// 정렬 기준으로 a가 b보다 앞서있지 않고,
// b도 a보다 앞서 있지 않다면 같다고 판단

8. 구간 반복자
   • lower_bound(k) : k의 시작 구간
   • upper_bound(k) : k의 끝 구간
   • equal_range(k) : lower, upper 를 가지는 pair

set<int> s = {10, 30, 40, 50, 70};
iter_lower = s.lower_bound(30);
// => 30을 가리킴
iter_upper = s.upper_bound(30)
// => 40을 가리킴
iter_lower = s.lower_bound(55);
// => 70을 가리킴
iter_upper = s.upper_bound(55);
// => 70을 가리킴

if (iter_lower == iter_upper)
   //찾는 원소 없음

s.equal_range(30)
// lower 와 upper 반복자를 pair 객체로 반환

3. multiset 컨테이너

1. set과의 차이점
   • 중복 원소를 허용
2. ms.count(30)
   • 원소 30의 개수(중복 허용)
3. ms.find(30)
   • 원소 30의 첫 위치(중복일 경우)
4. lower _iter = ms.lower_bound(30)
   • 원소 30이 시작되는 위치
5. upper _iter = ms.uppter_bound(30)
   • 원소 30의 끝 다음 위치
   • 30, 30, 50 의 경우 50

4. map 컨테이너

1. set과의 차이점
   • key, value 쌍(pair)으로 객체 저장
2. m.insert(pair<int, int>(5,100))
   • key : 5, value : 100을 가지는 원소 추가
   • 반복자와 성공여부를 가지는 pair 리턴
3. m[5] = 100
   • 키값 5가 없으면 100 추가, 있으면 값을 100으로 업데이트
4. m.find(5)
   • key값 5를 찾아 그 위치 반복자 반환
   • 반복자가 m.end()이면 key값 없음

5. multimap 컨테이너

1. map과의 차이점
   • 중복된 key값을 허용

참고

뇌를 자극하는 C++ STL

1. list 컨테이너

1.1 list의 주요 특징

1. 원소가 노드 단위로 저장

2. list는 이중 연결 리스트로 구현

3. 앞/뒤 원소 추가/제거 가능

4. 임의 접근 반복자가 아닌 양방향 반복자

   • 원소 탐색을 위해 ++ 또는 -- 사용
   • at, [] 연산자 없음

5. 중간에 원소 추가 제거 시 효율적

   • vector, deque와 다르게 노드만 연결/삭제

6. 다른 리스트와 결합이 용이함

7. 템플릿 형식

   • T 는 list 컨테이너 원소의 형식

template<typename T, typename Allocator = allocator<T>>
class list

3. 생성자

   코드	내용
   list lt	lt는 빈 컨테이너
   list lt(n)	lt는 기본값으로 초기화된 n개의 원소 가짐
   list lt(n, x)	lt는 x값으로 초기화된 n개의 원소 가짐
   list lt(lt2)	lt는 lt2컨테이너의 복사본(복사 생성자 호출)
   list lt(b,e)	lt는 반복자 구간 [b,e)로 초기화된 원소 가짐

3. 멤버 함수

   코드	내용
   lt.assign(n,x)	lt에 x값으로 n개의 원소를 할당
   lt.assign(b,e)	lt를 반복자 구간 [b,e)로 할당
   lt.front()	lt의 첫 번째 원소 참조
   lt.back()	lt의 마지막 원소 참조
   p=lt.begin()	p는 lt의 첫원소를 가리키는 반복자
   p=lt.end()	p는 lt의 끝을 나타내는 반복자
   lt.clear()	lt의 모든 원소 제거
   lt.empty()	lt가 비었는지 조사
   q=lt.erase(p)	p가 가리키는 원소 제거(q는 다음 원소 가리킴)
   q=lt.erase(b,e)	반복자 구간[b,e)의 모든 원소를 제거(q는 다음 원소)
   q=lt.insert(p,x)	p가 가리키는 위치에 x값 삽입(q는 삽입한 원소 가리킴)
   lt.insert(p,n,x)	p가 가리키는 위치에 n개의 x값 삽입
   lt.insert(p,b,e)	p가 가리키는 위치에 반복자 구간[b,e)의 원소를 삽입
   x=lt.max_size()	x는 lt가 담을 수 있는 최대 원소 개수(메모리 크기)
   lt.merge(lt2)	lt2를 lt로 합병 정렬(오름차순 : less)
   lt.merge(lt2, pred)	lt2를 lt로 합병 정렬(pred를 기준으로 합병)
   lt.pop_back()	lt의 마지막 원소 제거
   lt.pop_front()	lt의 첫 원소 제거
   lt.push_back(x)	lt의 끝에 x 추가
   lt.push_front(x)	lt의 앞에 x 추가
   p=lt.rbegin()	p는 lt의 역 순차열의 첫 원소를 가리키는 반복자
   p=lt.rend()	p는 lt의 역 순차열의 끝을 표식하는 반복자
   lt.remove(x)	x 원소를 모두 제거
   lt.remove_if(pred)	pred(단항조건자)가 참인 모든 원소 제거
   lt.resize(n)	lt의 크기를 n으로 변경(크기가 커지면 기본값으로 초기화)
   lt.resize(n,x)	lt의 크기를 n으로 변경(크기가 커지면 x로 초기화)
   lt.reverse()	lt 순차열을 뒤집음
   lt.size()	lt 원소의 개수
   lt.sort()	lt의 모든 원소를 오름차순으로 정렬
   lt.sort(pred)	lt의 모든 원소를 pred를 기준으로 정렬
   lt.splice(p, lt2)	p가 가리키는 위치에 lt2의 모든 원소를 잘라 붙임
   lt.splice(p, lt2, q)	p가 가리키는 위치에 lt2의 q가 가리키는 원소를 잘라 붙임
   lt.splice(p, lt2, b, e)	p가 가리키는 위치에 lt2의 순차열 [b,e)를 잘라 붙임
   lt.swap(lt2)	lt와 lt2를 swap
   lt.unique()	인접한 원소의 값이 같다면 유일한 원소의 순차열로 만듦
   lt.unique(pred)	인접한 원소가 pred(이항 조건자)의 기준에 맞다면 유일한 원소의 순차열로 만듦

3. 연산자

   코드	내용
   lt1==lt2	lt1과 lt2의 모든 원소가 같은가?
   lt1!=lt2	lt1과 lt2의 원소중 하나라도 다른가?
   lt1 < lt2	문자열 비교처럼 lt2가 lt1보다 큰가?

3. 멤버 형식

2 상세 내용

1. lt.remove(10)

   • 원소값 10을 가지는 모든 노드 찾아 삭제
   • 값기반 삭제는 list만 보유

1. lt.remove_if(Pred)

   • 모든 원소에 Pred 함수 적용하여 참인 원소 삭제

1. lt1.splice(iter, lt2)

   • iter위치에 lt2의 모든 원소를 lt1에 잘라 붙임
   • 노드를 연결만 하기 때문에 속도 빠름

1. lt1.splice(iter, lt2, iter2)

   • iter 위치에 iter2가 가리키는 lt2 원소 붙임

1. lt1.splice(lt1.end(), lt2, lt2,begin(), lt2.end())

   • lt1의 끝에 lt2를 잘라 붙임

1. lt.unique()

   • 인접한 중복 원소를 하나만 남기고 삭제

1. lt.unique(Pred)

   • Pred(이항 조건자)가 참이면 원소 삭제
   • Ex)

bool Pred(int first, int second){
   return second - first <= 0;
}
// 뒤의 원소가 현재 원소보다 작거나 같으면 삭제

8. 정렬

   • 알고리즘의 sort는 임의 접근 반복자 지원
   • vector와 deque는 알고리즘 사용하여 정렬 가능
   • 리스트는 양방향 접근 반복자여서 알고리즘 sort 사용 못함
   • 리스트는 멤버 함수로 sort 함수 지원
   • lt.sort() : 오름차순 정렬
   • lt.sort(greater<int>()) : 내림 차순 정렬

8. lt1.merge(lt2)

   • lt2를 lt1에 합병 정렬
   • 정렬 기준은 less(오름차순)
   • 합병할 리스트가 정렬 안되어 있으면 오류 발생
   • lt1과 lt2의 정렬 기준 다르면 오류 발생
   • Ex) lt1 = {10,20,30,40,50}
   • lt2 = {25, 35, 60}
   • 합병 정렬 하면
   • lt1 = {10,20,25,30,35,40,50,60}

참고

뇌를 자극하는 C++ STL

1. deque 컨테이너

1. 벡터와의 차이

   • 여러 개의 메모리 블록을 할당
   • 사용자에게는 하나의 블록처럼 보이게 함 -원소 추가시 메모리 부족해도 이전 메모리 제거 및 원소 복사 안함

1. deque의 주요 특징

   • 여러 메모리 블록에 나뉘어 원소 저장
   • 앞/뒤 모두 원소 추가/제거 가능
   • vector보다 원소 추가/제거 시에 성능 효율적

1. 템플릿 형식

   • T 는 deque 컨테이너 원소의 형식

template<typename T, typename Allocator = allocator<T>>
class deque

3. 생성자

   코드	내용
   deque dq	dq는 빈 컨테이너
   deque dq(n)	dq는 기본값으로 초기화된 n개의 원소 가짐
   deque dq(n, x)	dq는 x값으로 초기화된 n개의 원소 가짐
   deque dq(dq2)	dq는 dq2컨테이너의 복사본(복사 생성자 호출)
   deque dq(b,e)	dq는 반복자 구간 [b,e)로 초기화된 원소 가짐

3. 멤버 함수

   코드	내용
   dq.assign(n,x)	dq에 x값으로 n개의 원소를 할당
   dq.assign(b,e)	dq를 반복자 구간 [b,e)로 할당
   dq.at(i)	dq의 i번째 원소를 참조
   dq.front()	dq의 첫 번째 원소 참조
   dq.back()	dq의 마지막 원소 참조
   p=dq.begin()	p는 dq의 첫원소를 가리키는 반복자
   p=dq.end()	p는 dq의 끝을 나타내는 반복자
   dq.clear()	dq의 모든 원소 제거
   dq.empty()	dq가 비었는지 조사
   q=dq.erase(p)	p가 가리키는 원소 제거(q는 다음 원소 가리킴)
   q=dq.erase(b,e)	반복자 구간[b,e)의 모든 원소를 제거(q는 다음 원소)
   q=dq.insert(p.x)	dq가 가리키는 위치에 x값 삽입(q는 삽입한 원소 가리킴)
   dq.insert(p,n,x)	p가 가리키는 위치이 n개의 x값 삽입
   dq.insert(p,b,e)	p가 가리키는 위치에 반복자 구간[b,e)의 원소를 삽입
   x=dq.max_size()	x는 dq가 담을 수 있는 최대 원소 개수(메모리 크기)
   dq.pop_back()	dq의 마지막 원소 제거
   dq.pop_front()	dq의 첫 원소 제거
   dq.push_back(x)	dq의 끝에 x 추가
   dq.push_front(x)	dq의 앞에 x 추가
   p=dq.rbegin()	p는 dq의 역 순차열의 첫 원소를 가리키는 반복자
   p=dq.rend()	p는 dq의 역 순차열의 끝을 표식하는 반복자
   dq.resize(n)	dq의 크기를 n으로 변경(크기가 커지면 기본값으로 초기화)
   dq.resize(n,x)	dq의 크기를 n으로 변경(크기가 커지면 x로 초기화)
   dq.size()	dq 원소의 개수
   dq.swap(dq2)	dq와 dq2를 swap

3. 연산자

   코드	내용
   dq1==dq2	dq1과 dq2의 모든 원소가 같은가?
   dq1!=dq2	dq1과 dq2의 원소중 하나라도 다른가?
   dq1 < dq2	문자열 비교처럼 dq2가 dq1보다 큰가?
   dq[i]	dq의 i 번째 원소를 참조

3. 멤버 형식

   코드	내용
   allocator_type	메모리 관리자 형식
   const_iterator	const 반복자 형식
   const_pointer	const value_type* 형식
   const_reference	const value_type& 형식
   const _reverse_iterator	const 역 반복자 형식
   difference_type	두 반복자 차이의 형식
   iterator	반복자 형식
   pointer	value_type* 형식
   reference	value_type& 형식
   reverse_iterator	역 반복자 형식
   size_type	첨자(index)나 원소의 개수 등의 형식
   value_type	원소의 형식

2 상세 내용

1. dq.push_front(100)
   • deque 앞에 100을 원소로 추가

1. 삽입 제거 사용 방법 벡터와 동일
   • vector 보다 효율적으로 동작
   • 삽입, 제거 시 원소가 적은 쪽으로 밀어냄
   • ex)10, 20, 30, 40, 50, 60 원소
   • 30의 위치에 50을 추가시에
   • 앞쪽으로 밀어냄

참고

뇌를 자극하는 C++ STL

1. Vector 컨테이너

1. 템플릿 형식
   • T 는 vector 컨테이너 원소의 형식

template<typename T, typename Allocator = allocator<T>>
class vector

3. vector의 주요 특징

   • 원소가 메모리 블록에 연속하게 저장됨
   • 조회 속도는 빠름
   • insert, erase 느림

3. 생성자

   코드	내용
   vector v	v는 빈 컨테이너
   vector v(n)	v는 기본값으로 초기화된 n개의 원소 가짐
   vector v(n, x)	v는 x값으로 초기화된 n개의 원소 가짐
   vector v(v2)	v는 v2컨테이너의 복사본(복사 생성자 호출)
   vector v(b,e)	v는 반복자 구간 [b,e)로 초기화된 원소 가짐

3. 멤버 함수

   코드	내용
   v.assign(n,x)	v에 x값으로 n개의 원소를 할당
   v.assign(b,e)	v를 반복자 구간 [b,e)로 할당
   v.at(i)	v의 i번째 원소를 참조
   v.front()	v의 첫 번째 원소 참조
   v.back()	v의 마지막 원소 참조
   p=v.begin()	p는 v의 첫원소를 가리키는 반복자
   p=v.end()	p는 v의 끝을 나타내는 반복자
   x=v.capacity()	x는 v에 할당된 공간의 크기
   v.clear()	v의 모든 원소 제거(할당된 공간은 유지)
   v.empty()	v가 비었는지 조사
   q=v.erase(p)	p가 가리키는 원소 제거(q는 다음 원소 가리킴)
   q=v.insert(p.x)	p가 가리키는 위치에 x값 삽입(q는 삽입한 원소 가리킴)
   v.insert(p,n,x)	p가 가리키는 위치이 n개의 x값 삽입
   v.insert(p,b,e)	p가 가리키는 위치에 반복자 구간[b,e)의 원소를 삽입
   x=v.max_size()	x는 v가 담을 수 있는 최대 원소 개수(메모리 크기)
   v.pop_back()	v의 마지막 원소 제거
   v.push_back(x)	v의 끝에 x 추가
   p=v.rbegin()	p는 v의 역 순차열의 첫 원소를 가리키는 반복자
   p=v.rend()	p는 v의 역 순차열의 끝을 표식하는 반복자
   v.reserve(n)	n개의 원소를 저장할 공간 예약
   v.resize(n)	v의 크기를 n으로 변경(크기가 커지면 기본값으로 초기화)
   v.resize(n,x)	v의 크기를 n으로 변경(크기가 커지면 x로 초기화)
   v.size()	v 원소의 개수
   v.swap(v2)	v와 v2를 swap

3. 연산자

   코드	내용
   v1==v2	v1과 v2의 모든 원소가 같은가?
   v1!=v2	v1과 v2의 원소중 하나라도 다른가?
   v1 < v2	문자열 비교처럼 v2가 v1보다 큰가?
   v[i]	v의 i 번째 원소를 참조

3. 멤버 형식

2. 상세 내용

1. vector::size_type

   • 벡터 사이즈, 첨자를 나태내기 위한 typedef 멤버

1. v.reserve(8)

   • 벡터 메모리 크기 설정
   • capacity 를 8로 설정

1. v.resize(10)

   • 벡터의 사이즈 변경
   • 사이즈가 커지면 capacity 같이 커짐
   • 사이즈 작아지면 capacity는 그대로

1. v.resize(10, 100)

   • size변경 시 크기가 커지면 100으로 초기화

1. v.clear()

   • 벡터 원소 삭제
   • capacity는 그대로

1. vector().swap(v)

   • 벡터 원소 삭제
   • capacity도 0으로 초기화

1. 임의의 원소 참조

   • v.at(0) : 벡터 범위 검사, 안정적, 속도 느림
   • v[0] : 벡터 범위 검사 X, 위험, 속도 빠름

1. v.assign(5,2)

   • 사이즈 5로 변경 및 5 요소에 2로 할당
   • 사이즈가 줄어들면 capacity는 그대로

1. vector::iterator iter

iter = v.begin() // iter를 시작 위치로 설정
(*iter); // 현재 iter 위치의 원소값
iter +=2; // iter의 위치를 2 이동

10. vector::const_iterator citer
    • 원소의 값을 변경하지 않을 때 선언

vector<int>::const_iterator citer
(*citer) = 100 // (X) 값 변경 못함

11. vector::reverse_iterator
    • 역방향 반복자 선언

// 마지막 원소를 가리키는 역방향 반복자 선언
vector<int>::reverse_iterator riter = v.rbegin();

12. iter2 = v.insert(iter, 100)

    • iter 위치에 100을 추가
    • iter2는 추가된 위치를 가리킴

12. v.insert(iter, 3, 100)

    • iter위치에 100값 3개 추가

12. iter2 = v.erase(iter)

    • iter 위치 원소를 삭제
    • iter2는 삭제된 원소 다음 위치

12. iter2 = v.erase(v.begin() + 1, v.end())

    • 시작 원소만 두고 모두 삭제
    • v.end()가 iter2에 저장됨

참고

뇌를 자극하는 C++ STL

1.컨테이너

1. 컨테이너 : 객체를 저장하는 객체

1.1 삽입 순서에 따른 분류

1. 표준 시퀀스 컨테이너 : 삽입 순서를 가지는 것
   • vector, deque, list 등
2. 표준 연관 컨테이너 : 삽입 순서 없이 자동 정렬
   • map, set, multiset, multimap 등

1.2 메모리 단위 저장에 따른 분류

1. 배열 기반 컨테이너 : 연속된 메모리에 저장
   • vector, deque
2. 노드 기반 컨테이너 : 각 메모리 단위에 저장
   • list, set, multiset, map, multimap

2.반복자

1. 반복자 : 컨테이너 원소를 순회하고 접근하는 방법
2. 특징
   • 컨테이너 원소를 가리킨다.
   • 다음 원소로 이동하고 모든 원소를 순회 가능
   • begin()과 end()로 시작과 끝을 가리킴

2.1 반복자의 범주

1. 입력 반복자
   • 현위치 원소를 한번만 읽는 반복자
   • ex)istream
2. 출력 반복자
   • 현위치 원소를 한번만 쓰는 반복자
   • ex)ostream
3. 순방향 반복자
   • 순반향으로 이동 가능한 반복자
4. 양방향 반복자
   • 순/역방향으로 이동 가능한 반복자
   • ex) list, set, map, multimap, multiset
5. 임의 접근 반복자
   • +, - , [] 연산이 가능한 반복자
   • ex) vector, deque

3. 알고리즘

1. 범주
   • 원소를 수정하지 않는 알고리즘
   • 원소를 수정하는 알고리즘
   • 제거 알고리즘
   • 변경 알고리즘
   • 정렬 알고리즘
   • 정렬된 범위 알고리즘
   • 수치 알고리즘

4. 함수 객체

1. operator()을 오버로딩한 객체

5. 어댑터

1. 구성요소의 인터페이스를 변경해 새로운 인터페이스를 갖는 요소로 변경

2. 컨테이너 어댑터

   • stack, queue, priority_queue

3. 반복자 어댑터

   • reverse _iterator, insert_iterator
   • back _insert _iterator, front _insert_iterator

4. 함수 어댑터

   • 바인더, 부정자, 함수 포인터 어댑터

6. 할당기

1. 메모리 할당 정보와 정책을 캡슐화 한 것

참고

뇌를 자극하는 C++ STL