전문가를 위한 C++/ C++ 표준 라이브러리 둘러보기

컨테이너 클래스 이름

컨테이너 타입

사용 시기

vector

순차 컨테이너

기본 컨테이너로 사용한다. 프로파일러로 분석한 결과 이보다 낫다고 판단될 때만 다른 컨테이너를 사용한다.

list

순차

사용할 일이 거의 없다. 프로파일러로 분석한 결과 list가 vector 보다 낫다고 판단되지 않으면 웬만하면 vector를 쓴다.

forward_list

순차

사용할 일이 거의 없다. 프로파일러로 분석한 결과 forward_list가 vector 보다 낫다고 판단되지 않으면 웬만하면 vector를 쓴다.

deque

순차

사용할 일이 많지 않다. 주로 vector를 쓴다.

array

순차

표준 C 스타일 배열 대신 고정 크기 배열이 필요할 때

queue

컨테이너 어댑터

FIFO 구조가 필요할 떄

priority_queue

컨테이너 어댑터

우선순위가 있는 queue를 구현하고 싶을 때

stack

컨테이너 어댑터

FILO이나 LIFO 구조를 구현하고 싶을 때

set multiset

정렬 연관

원소를 정렬된 묶음에 담고, 조회/추가/삭제 성능도 모두 같게 만들고 싶을 때. 원소의 중복을 허용하지 않으려면 set을 이용한다.

map multimap

정렬 연관

원소를 키와 값이 연관된 순서쌍으로 키 값에 대해 정렬된 상태, 즉 연관 배열로 저장하면서 조회/추가/삭제 성능도 모두 같게 만들고 싶을 때

unodered_map unordered_multimap

비정렬 연관

키와 값을 묶어서 저장하고 조회, 추가, 삭제 성능이 모두 같게 만들고 싶으면서 원소를 정렬하지 않아도 될 때. 일반 map 보다 성능이 좋지만 원소의 종류에 따라 달라질 수 있다.

unorderd_set unorderd_multiset

비정렬 연관

조회, 추가, 삭제 성능이 모두 같게 만들고 싶으면서 우너소를 정렬하지 않아도 될 때, 일반 set보다 성능이 좋지만 원소의 종류에 따라 달라질 수 있다.

bitset

특수

플래그 묶음을 표현하고 싶을 때

컨테이너 클래스 이름

추가 연산 성능

삭제 연산 성능

조회 연산 성능

vector

끝에서는 분할 상환 성능이 O(1), 나머지는 O(N)

끝에서는 O(1), 나머지는 O(N)

O(1)

list

시작과 끝점 그리고 추가할 위치가 정확히 결정된 상태에는 O(1)

시작과 끝점 그리고 추가할 위치가 정확히 결정된 상태에는 O(1)

첫 번째와 마지막 원소를 조회할 때는 O(1), 나머지는 O(N)

forward_list

추가할 지점이 시작점이거나 정확한 위치를 안다면 O(1)

삭제할 지점이 시작점이거나 정확한 위치를 안다면 O(1)

첫 번째 원소를 조회할 때는 O(1), 나머지는 O(N)

deque

시작과 끝에서는 O(1), 나머지는 O(N)

시작과 끝에서는 O(1), 나머지는 O(N)

O(1)

array

N/A

N/A

N/A

queue

내부 컨테이너의 종류에 따라 다르다. list나 deque로 구현할 때는 O(1)

내부 컨테이너의 종류에 따라 다르다. list나 deque로 구현할 때는 O(1)

N/A

priority_queue

내부 컨테이너에 따라 다르다 vector를 사용할 때는 분할 상환 성능이 O(log(N))이고 deque를 사용할 때는 O(log(N))이다.

내부 컨테이너에 따라 다르다. vector나 deque를 사용할 때는 O(log(N))

N/A

stack

내부 컨테이너에 따라 다르다. list나 deque를 사용하면 O(1), vector를 사용하면 분할 상환 성능으로 O(1)

내부 컨테이너에 따라 다르다. list, vector, deque일 때 O(1),

N/A

setmultiset

O(log(N))

O(log(N))

O(log(N))

mapmultimap

O(log(N))

O(log(N))

O(log(N))

unodered_mapunordered_multimap

평균 O(1),최악 O(N)

평균 O(1),최악 O(N)

평균 O(1),최악 O(N)

unorderd_setunorderd_multiset

평균 O(1),최악 O(N)

평균 O(1),최악 O(N)

평균 O(1),최악 O(N)

bitset

N/A

N/A

N/A

함수 이름

설명

begin() end()

첫 번째 원소부터 마지막 항목의 바로 다음 원소까지 순차적으로(정방향으로) 탐색하는 non-const 반복자를 리턴한다.

cbegin() cend()

첫 번째 원소부터 마지막 항목의 바로 다음 원소까지 순차적으로(정방향으로) 탐색하는 const 반복자를 리턴한다.

rbegin() rend()

마지막 원소부터 첫 번째 항목의 바로 전 원소까지 순차적으로(역방향으로) 탐색하는 non-const 반복자를 리턴한다.

crbegin() crend()

마지막 원소부터 첫 번째 항목의 바로 전 원소까지 순차적으로(역방향으로) 탐색하는 const 반복자를 리턴한다.

알고리즘 이름

설명

복잡도

adjacent_find()

조건으로 입력한 값과 같거나 조건식에 대입한 결과가 같은 연속된 두 원소 중 처음 나온 것을 찾는다.

O(N)

find() find_if()

조건으로 입력한 값과 같거나 조건식의 결과가 true인 원소 중 첫 번째 원소를 찾는다.

O(N)

find_first_of()

find()와 비슷하지만 여러 원소를 동시에 찾는다.

O(NM)

find_if_not()

조건식의 결과가 false인 원소 중 첫 번째 원소를 찾는다.

O(N)

find_end()

입력한 시퀀스나 조건식에 맞는 시퀀스 중에서 마지막 부분을 찾는다.

O(M*(N-M))

search()

입력된 시퀀스와 일치하거나 입력한 조건식을 기준으로 같다고 판단되는 시퀀스 중에서 첫 번째 항목을 찾는다.

O(NM)*

search_n()

입력한 값과 같거나 입력한 조건식을 기준으로 같다고 판단되는 원소 중 n번 연속해서 일치하는 결과 중 첫 번째 결과를 찾는다.

O(N)

알고리즘 이름

설명

equal()

입력한 두 시퀀스가 서로 같거나, 입력한 조건식을 모두 만족하는지 검사한다.

mismatch()

입력한 시퀀스와 일치하지 않는 지점의 첫 번째 원소를 리턴한다.

lexicographical_compare()

입력한 두 시퀀스를 사전 나열 순서대로 비교한다. 이 알고리즘은 첫 번째 인수와 두 번째 인수로 입력한 시퀀스의 모든 항목을 하나씩 비교한다. 각 원소를 비교할 때마다 어느 하나가 사전 순으로 더 작다고 판단되면 그 시퀀스가 먼저다. 두 원소가 같으면 그 다음 번째의 원소를 비교한다.

알고리즘 이름

설명

all_of()

입력 시퀀스에 있는 모든 원소에 대해 조건식이 true를 리턴하거나 입력 시퀀스가 공백이면 true를 리턴한다. 나머지는 false를 리턴한다.

any_of()

입력 시퀀스에 있는 원소 중 최소 하나에 대해 조건식이 true를 리턴하면 true를 리턴한다. 나머지는 false를 리턴한다.

none_of()

입력 시퀀스에 있는 모든 원소에 대해 조건식이 false를 리턴하거나 입력 시퀀스가 공백이면 true를 리턴한다. 나머지는 false를 리턴한다.

count() count_if()

입력한 값과 일치하는 원소나 입력한 조건식의 결과가 true가 되는 원소 수를 센다.

알고리즘 이름

설명

copy() copy_backward()

원본 시퀀스를 대상 시퀀스로 복제한다.

copy_if()

원본 시퀀스에서 조건식이 true를 리턴하는 원소를 대상 시퀀스로 복제한다.

copy_n()

원본 시퀀스에서 n개 원소를 대상 시퀀스로 복제한다.

fill()

시퀀스의 원소를 모두 새 값으로 설정한다.

fill_n()

시퀀스에서 n개 원소를 새 값으로 설정한다.

generate()

지정한 함수를 호출해서 시퀀스의 원소에 채울 새 값을 생성한다.

generate_n()

지정한 함수를 호출해서 시퀀스의 앞부터 n개 원소에 채울 새 값을 생성한다.

move() move_backward()

원본 시퀀스의 원소를 대상 시퀀스로 옮긴다. 효율적으로 옮기도록 이동 의미론을 적용한다.

revmove() remove_if() remove_copy() remove_copy_if()

지정한 값과 일치하거나 지정한 조건식이 true가 되는 원소를 바로 그 자리에서 삭제하거나 다른 시퀀스로 복제해서 삭제한다.

replace() replace_if() replace_copy() replace_copy_if()

지정한 값과 일치하거나 지정한 조건시기 true가 되는 원소를 모두 그 자리에서 새 원소로 교체하거나 다른 시퀀스로 복제해서 교체한다

reverse() reverse_copy()

원본 시퀀스에 나열된 원소의 순서를 그 자리에서 반대로 바꾸거나 다른 시퀀스에 복제해서 바꾼다.

rotate() rotate_copy()

주어진 시퀀스를 두 개로 나눠서 앞부분과 뒷부분의 위치를 그 자리에서 바꾸거나 결과를 다른 시퀀스에 복제한다. 이때 두 시퀀스의 길이는 서로 달라도 된다.

sample()

주어진 시퀀스에서 n개 원소를 무작위로 선택한다.

shuffle() random_shuffle()

주어진 시퀀스에 담긴 원소의 순서를 무작위로 바꾼다. 이때 사용할 무작위수 생성기를 직접 지정할 수 있다. random_shuffle()은 C++ 14부터 폐기 됐고, C++ 17부터 완전히 삭제됐다.

transform()

주어진 시퀀스의 각 우너소에 대해 단항 함수를 호출하거나 두 시퀀스에서 위치가 같은 원소에 대해 이항 함수를 호출한다. 변환은 그 자리에서 수행한다.

unique() unique_copy()

주어진 시퀀스에서 연속적으로 중복되는 항목을 그 자리에서 제거하거나 다른 시퀀스로 복제해서 제거한다.

알고리즘 이름

설명

for_each()

주어진 시퀀스에 담긴 원소마다 함수를 실행한다. 시퀀스는 시작 반복자와 끝 반복자로 지정한다.

for_each_n()

for_each()와 비슷하지만 주어진 시퀀스에서 첫 n개 원소만 처리한다. 시퀀스는 시작 반복자와 원소 수(n)로 지정한다.

알고리즘 이름

설명

iter_swap()swap_ranges()

두 원소 또는 시퀀스를 맞바꾼다.

swap()

두 값을 맞바꾼다.

exchage()

지정한 값을 새 값으로 교체하고 기존 값을 리턴한다.

알고리즘 이름

설명

복잡도

is_partitioned()

조건식이 true가 되는 원소가 모두 조건식이 false가 되는 원소보다 앞에 있으면 true를 리턴한다.

선형

partition()

조건식이 true가 되는 원소가 모두 조건식이 false가 되는 원소보다 앞에 있도록 시퀀스를 정렬한다. 각 파티션의 원소는 원본 순서를 유지하지 않는다.

선형

stable_partition()

조건식이 true가 되는 원소가 모두 조건식이 false가 되는 원소보다 앞에 있도록 시퀀스를 정렬한다. 각 파티션의 원소는 원본 순서를 유지한다.

선형 로그

partition_copy()

원본 시퀀스에 있는 원소를 서로 다른 두 시퀀스로 복제한다. 대상 시퀀스는 조건식의 결과가 true인지 false인지에 따라 결정한다.

선형

partition_point()

반복자 앞에 나온 원소가 모두 조건식에 대해 true가 되고 반복자 뒤에 나온 원소가 모두 조건식에 대해 false가 되는 반복자를 리턴한다.

로그

알고리즘 이름

설명

복잡도

is_sorted() is_sorted_until()

시퀀스 또는 부분 시퀀스가 정렬된 상태인지 검사한다.

선형

nth_element()

시퀀스를 정렬했을 때 인수로 지정한 원소가 n번째 원소가 되도록 위치를 이동하고, 그 앞에 나온 원소가 모두 n번째 원소보다 작고, 그 뒤에 나온 원소가 n번째 원소보다 크도록 정렬한다.

선형

partial_sort() partial_sort_copy()

시퀀스의 일부분, 즉 첫 n개 원소만 정렬한다(지정한 반복자를 기준으로) 나머지는 그대로 둔다. 그 자리에서 곧바로 정렬하거나 새 시퀀스에 복제해서 정렬한다.

선형 로그

sort() stable_sort()

원소를 그 자리에서 곧바로 정렬한다. 중복된 원소는 순서가 바뀔수도 있고(sort()), 유지될 수도 있다(stable_sort())

선형 로그

알고리즘 이름

설명

lower_bound()

주어진 값보다 작지 않은(크거나 같은) 첫 번째 원소를 시퀀스에서 찾는다.

upper_bound()

주어진 값보다 큰 첫 번째 원소를 시퀀스에서 찾는다.

equal_range()

lower_bound()와 upper_bound()의 결과를 모두 담은 pair를 리턴한다.

컨테이너 클래스 이름

컨테이너 타입

사용 시기

vector

순차 컨테이너

기본 컨테이너로 사용한다. 프로파일러로 분석한 결과 이보다 낫다고 판단될 때만 다른 컨테이너를 사용한다.

list

순차

사용할 일이 거의 없다. 프로파일러로 분석한 결과 list가 vector 보다 낫다고 판단되지 않으면 웬만하면 vector를 쓴다.

forward_list

순차

사용할 일이 거의 없다. 프로파일러로 분석한 결과 forward_list가 vector 보다 낫다고 판단되지 않으면 웬만하면 vector를 쓴다.

deque

순차

사용할 일이 많지 않다. 주로 vector를 쓴다.

array

순차

표준 C 스타일 배열 대신 고정 크기 배열이 필요할 때

queue

컨테이너 어댑터

FIFO 구조가 필요할 떄

priority_queue

컨테이너 어댑터

우선순위가 있는 queue를 구현하고 싶을 때

stack

컨테이너 어댑터

FILO이나 LIFO 구조를 구현하고 싶을 때

set multiset

정렬 연관

원소를 정렬된 묶음에 담고, 조회/추가/삭제 성능도 모두 같게 만들고 싶을 때. 원소의 중복을 허용하지 않으려면 set을 이용한다.

map multimap

정렬 연관

원소를 키와 값이 연관된 순서쌍으로 키 값에 대해 정렬된 상태, 즉 연관 배열로 저장하면서 조회/추가/삭제 성능도 모두 같게 만들고 싶을 때

unodered_map unordered_multimap

비정렬 연관

키와 값을 묶어서 저장하고 조회, 추가, 삭제 성능이 모두 같게 만들고 싶으면서 원소를 정렬하지 않아도 될 때. 일반 map 보다 성능이 좋지만 원소의 종류에 따라 달라질 수 있다.

unorderd_set unorderd_multiset

비정렬 연관

조회, 추가, 삭제 성능이 모두 같게 만들고 싶으면서 우너소를 정렬하지 않아도 될 때, 일반 set보다 성능이 좋지만 원소의 종류에 따라 달라질 수 있다.

bitset

특수

플래그 묶음을 표현하고 싶을 때

컨테이너 클래스 이름

추가 연산 성능

삭제 연산 성능

조회 연산 성능

vector

끝에서는 분할 상환 성능이 O(1), 나머지는 O(N)

끝에서는 O(1), 나머지는 O(N)

O(1)

list

시작과 끝점 그리고 추가할 위치가 정확히 결정된 상태에는 O(1)

시작과 끝점 그리고 추가할 위치가 정확히 결정된 상태에는 O(1)

첫 번째와 마지막 원소를 조회할 때는 O(1), 나머지는 O(N)

forward_list

추가할 지점이 시작점이거나 정확한 위치를 안다면 O(1)

삭제할 지점이 시작점이거나 정확한 위치를 안다면 O(1)

첫 번째 원소를 조회할 때는 O(1), 나머지는 O(N)

deque

시작과 끝에서는 O(1), 나머지는 O(N)

시작과 끝에서는 O(1), 나머지는 O(N)

O(1)

array

N/A

N/A

N/A

queue

내부 컨테이너의 종류에 따라 다르다. list나 deque로 구현할 때는 O(1)

내부 컨테이너의 종류에 따라 다르다. list나 deque로 구현할 때는 O(1)

N/A

priority_queue

내부 컨테이너에 따라 다르다 vector를 사용할 때는 분할 상환 성능이 O(log(N))이고 deque를 사용할 때는 O(log(N))이다.

내부 컨테이너에 따라 다르다. vector나 deque를 사용할 때는 O(log(N))

N/A

stack

내부 컨테이너에 따라 다르다. list나 deque를 사용하면 O(1), vector를 사용하면 분할 상환 성능으로 O(1)

내부 컨테이너에 따라 다르다. list, vector, deque일 때 O(1),

N/A

set multiset

O(log(N))

O(log(N))

O(log(N))

map multimap

O(log(N))

O(log(N))

O(log(N))

unodered_map unordered_multimap

평균 O(1),최악 O(N)

평균 O(1),최악 O(N)

평균 O(1),최악 O(N)

unorderd_set unorderd_multiset

평균 O(1),최악 O(N)

평균 O(1),최악 O(N)

평균 O(1),최악 O(N)

bitset

N/A

N/A

N/A

함수 이름

설명

begin() end()

첫 번째 원소부터 마지막 항목의 바로 다음 원소까지 순차적으로(정방향으로) 탐색하는 non-const 반복자를 리턴한다.

cbegin() cend()

첫 번째 원소부터 마지막 항목의 바로 다음 원소까지 순차적으로(정방향으로) 탐색하는 const 반복자를 리턴한다.

rbegin() rend()

마지막 원소부터 첫 번째 항목의 바로 전 원소까지 순차적으로(역방향으로) 탐색하는 non-const 반복자를 리턴한다.

crbegin() crend()

마지막 원소부터 첫 번째 항목의 바로 전 원소까지 순차적으로(역방향으로) 탐색하는 const 반복자를 리턴한다.

알고리즘 이름

설명

복잡도

adjacent_find()

조건으로 입력한 값과 같거나 조건식에 대입한 결과가 같은 연속된 두 원소 중 처음 나온 것을 찾는다.

O(N)

find() find_if()

조건으로 입력한 값과 같거나 조건식의 결과가 true인 원소 중 첫 번째 원소를 찾는다.

O(N)

find_first_of()

find()와 비슷하지만 여러 원소를 동시에 찾는다.

O(NM)

find_if_not()

조건식의 결과가 false인 원소 중 첫 번째 원소를 찾는다.

O(N)

find_end()

입력한 시퀀스나 조건식에 맞는 시퀀스 중에서 마지막 부분을 찾는다.

O(M*(N-M))

search()

입력된 시퀀스와 일치하거나 입력한 조건식을 기준으로 같다고 판단되는 시퀀스 중에서 첫 번째 항목을 찾는다.

O(NM)*

search_n()

입력한 값과 같거나 입력한 조건식을 기준으로 같다고 판단되는 원소 중 n번 연속해서 일치하는 결과 중 첫 번째 결과를 찾는다.

O(N)

알고리즘 이름

설명

equal()

입력한 두 시퀀스가 서로 같거나, 입력한 조건식을 모두 만족하는지 검사한다.

mismatch()

입력한 시퀀스와 일치하지 않는 지점의 첫 번째 원소를 리턴한다.

lexicographical_compare()

입력한 두 시퀀스를 사전 나열 순서대로 비교한다. 이 알고리즘은 첫 번째 인수와 두 번째 인수로 입력한 시퀀스의 모든 항목을 하나씩 비교한다. 각 원소를 비교할 때마다 어느 하나가 사전 순으로 더 작다고 판단되면 그 시퀀스가 먼저다. 두 원소가 같으면 그 다음 번째의 원소를 비교한다.

알고리즘 이름

설명

all_of()

입력 시퀀스에 있는 모든 원소에 대해 조건식이 true를 리턴하거나 입력 시퀀스가 공백이면 true를 리턴한다. 나머지는 false를 리턴한다.

any_of()

입력 시퀀스에 있는 원소 중 최소 하나에 대해 조건식이 true를 리턴하면 true를 리턴한다. 나머지는 false를 리턴한다.

none_of()

입력 시퀀스에 있는 모든 원소에 대해 조건식이 false를 리턴하거나 입력 시퀀스가 공백이면 true를 리턴한다. 나머지는 false를 리턴한다.

count() count_if()

입력한 값과 일치하는 원소나 입력한 조건식의 결과가 true가 되는 원소 수를 센다.

알고리즘 이름

설명

copy() copy_backward()

원본 시퀀스를 대상 시퀀스로 복제한다.

copy_if()

원본 시퀀스에서 조건식이 true를 리턴하는 원소를 대상 시퀀스로 복제한다.

copy_n()

원본 시퀀스에서 n개 원소를 대상 시퀀스로 복제한다.

fill()

시퀀스의 원소를 모두 새 값으로 설정한다.

fill_n()

시퀀스에서 n개 원소를 새 값으로 설정한다.

generate()

지정한 함수를 호출해서 시퀀스의 원소에 채울 새 값을 생성한다.

generate_n()

지정한 함수를 호출해서 시퀀스의 앞부터 n개 원소에 채울 새 값을 생성한다.

move() move_backward()

원본 시퀀스의 원소를 대상 시퀀스로 옮긴다. 효율적으로 옮기도록 이동 의미론을 적용한다.

revmove() remove_if() remove_copy() remove_copy_if()

지정한 값과 일치하거나 지정한 조건식이 true가 되는 원소를 바로 그 자리에서 삭제하거나 다른 시퀀스로 복제해서 삭제한다.

replace() replace_if() replace_copy() replace_copy_if()

지정한 값과 일치하거나 지정한 조건시기 true가 되는 원소를 모두 그 자리에서 새 원소로 교체하거나 다른 시퀀스로 복제해서 교체한다

reverse() reverse_copy()

원본 시퀀스에 나열된 원소의 순서를 그 자리에서 반대로 바꾸거나 다른 시퀀스에 복제해서 바꾼다.

rotate() rotate_copy()

주어진 시퀀스를 두 개로 나눠서 앞부분과 뒷부분의 위치를 그 자리에서 바꾸거나 결과를 다른 시퀀스에 복제한다. 이때 두 시퀀스의 길이는 서로 달라도 된다.

sample()

주어진 시퀀스에서 n개 원소를 무작위로 선택한다.

shuffle() random_shuffle()

주어진 시퀀스에 담긴 원소의 순서를 무작위로 바꾼다. 이때 사용할 무작위수 생성기를 직접 지정할 수 있다. random_shuffle()은 C++ 14부터 폐기 됐고, C++ 17부터 완전히 삭제됐다.

transform()

주어진 시퀀스의 각 우너소에 대해 단항 함수를 호출하거나 두 시퀀스에서 위치가 같은 원소에 대해 이항 함수를 호출한다. 변환은 그 자리에서 수행한다.

unique() unique_copy()

주어진 시퀀스에서 연속적으로 중복되는 항목을 그 자리에서 제거하거나 다른 시퀀스로 복제해서 제거한다.

알고리즘 이름

설명

for_each()

주어진 시퀀스에 담긴 원소마다 함수를 실행한다. 시퀀스는 시작 반복자와 끝 반복자로 지정한다.

for_each_n()

for_each()와 비슷하지만 주어진 시퀀스에서 첫 n개 원소만 처리한다. 시퀀스는 시작 반복자와 원소 수(n)로 지정한다.

알고리즘 이름

설명

iter_swap() swap_ranges()

두 원소 또는 시퀀스를 맞바꾼다.

swap()

두 값을 맞바꾼다.

exchage()

지정한 값을 새 값으로 교체하고 기존 값을 리턴한다.

알고리즘 이름

설명

복잡도

is_partitioned()

조건식이 true가 되는 원소가 모두 조건식이 false가 되는 원소보다 앞에 있으면 true를 리턴한다.

선형

partition()

조건식이 true가 되는 원소가 모두 조건식이 false가 되는 원소보다 앞에 있도록 시퀀스를 정렬한다. 각 파티션의 원소는 원본 순서를 유지하지 않는다.

선형

stable_partition()

조건식이 true가 되는 원소가 모두 조건식이 false가 되는 원소보다 앞에 있도록 시퀀스를 정렬한다. 각 파티션의 원소는 원본 순서를 유지한다.

선형 로그

partition_copy()

원본 시퀀스에 있는 원소를 서로 다른 두 시퀀스로 복제한다. 대상 시퀀스는 조건식의 결과가 true인지 false인지에 따라 결정한다.

선형

partition_point()

반복자 앞에 나온 원소가 모두 조건식에 대해 true가 되고 반복자 뒤에 나온 원소가 모두 조건식에 대해 false가 되는 반복자를 리턴한다.

로그

알고리즘 이름

설명

복잡도

is_sorted() is_sorted_until()

시퀀스 또는 부분 시퀀스가 정렬된 상태인지 검사한다.

선형

nth_element()

시퀀스를 정렬했을 때 인수로 지정한 원소가 n번째 원소가 되도록 위치를 이동하고 그 앞에 나온 원소가 모두 n번째 원소보다 작고, 그 뒤에 나온 원소가 n번째 원소보다 크도록 정렬한다.

선형

partial_sort() partial_sort_copy()

시퀀스의 일부분, 즉 첫 n개 원소만 정렬한다(지정한 반복자를 기준으로) 나머지는 그대로 둔다. 그 자리에서 곧바로 정렬하거나 새 시퀀스에 복제해서 정렬한다.

선형 로그

sort() stable_sort()

원소를 그 자리에서 곧바로 정렬한다. 중복된 원소는 순서가 바뀔수도 있고(sort()), 유지될 수도 있다(stable_sort())

선형 로그

알고리즘 이름

설명

lower_bound()

주어진 값보다 작지 않은(크거나 같은) 첫 번째 원소를 시퀀스에서 찾는다.

upper_bound()

주어진 값보다 큰 첫 번째 원소를 시퀀스에서 찾는다.

equal_range()

lower_bound()와 upper_bound()의 결과를 모두 담은 pair를 리턴한다.

binary_search()

지정한 값이 시퀀스에 있으면 true, 아니면 false를 리턴한다.

알고리즘 이름

설명

복잡도

inplace_merge()

정렬된 시퀀스 두 개를 그 자리에서 병합한다.

선형 로그

merge()

정렬된 시퀀스 두 개를 새 시퀀스에 복제해서 병합한다.

선형

includes()

어떤 정렬된 시퀀스가 다른 정렬된 시퀀스에 완전히 포함되는지 검사한다.

선형

set_union() set_intersection() set_difference() set_symmetric_difference()

정렬된 시퀀스 두 개에 대해 합집합, 교집합, 차집합, 대칭 차집합 연산을 수행해서 제 3의 정렬된 시퀀스로 복제한다.

선형

알고리즘 이름

설명

복잡도

is_heap()

주어진 범위의 원소가 힙을 만족하는지 검사한다.

선형

is_heap_until()

주어진 범위의 원소에서 힙을 만족하는 최대 범위를 찾는다.

선형

make_heap()

주어진 범위의 원소에서 힙을 생성한다.

선형

push_heap() pop_heap()

힙에 원소를 추가하거나 힙에서 원소를 삭제한다.

로그

sort_heap()

힙을 오름차순으로 정렬된 시퀀스로 변환한다.

선형 로그

알고리즘 이름

설명

clamp()

주어진 값 v가 최솟값(lo)과 최댓값(hi) 사이에 있는지 확인한다. v < lo면 lo에 대한 레퍼런스를 리턴하고, v > hi면 hi에 대한 레퍼런스를 리턴하고, 둘 다 아니면 v에 대한 레퍼런스를 리턴한다.

min() max()

주어진 두 개 이상의 값 중에서 최댓값 또는 최솟값을 리턴한다.

minmax()

주어진 두 개 이상의 값 중에서 최댓값과 최솟값을 pair로 묶어서 리턴한다.

min_element() max_element()

주어진 시퀀스에서 최대 원소 또는 최소 원소를 리턴한다.

minmax_element()

주어진 시퀀스에서 최대 원소와 최소 원소를 pair로 묶어서 리턴한다.

알고리즘 이름

설명

iota()

시퀀스를 주어진 값에서 싲가해서 연속적으로 증가하는 값으로 채운다.

gcd()

주어진 두 정수의 최대 공약수를 리턴한다.

lcm()

주어진 두 정수의 최소 공배수를 리턴한다.

adjacent_difference()

주어진 시퀀스에서 인접한 두 원소를 골라서 뒤쪽 원소에서 앞쪽 원소를 뺀(또는 다른 바이너리 연산을 적용한) 결과가 원소가 되는 시퀀스를 생성한다. (ex a0, a1, … -> a0, a1-a0, a2-a1, …)

partial_sum()

주어진 시퀀스의 각 원소를 그 앞에 나온 모든 원소와 더한 (또는 다른 바이너리 연산을 적용한) 결과가 원소가 되는 시퀀스를 생성한다. (ex a0, a1, … -> a0, a0+a1, a0+a1+a2, …)

exclusive_scan() inclusive_scan()

기본 기능은 partial_sum()과 같지만 inclusive_scan()은 주어진 합 연산이 결합법칙을 만족할 때만 partial_sum()과 같다. 그런데 inclusive_sum()을 더하는 순서는 일정하지 않은 반면 partial_sum은 항상 왼쪽에서 오른쪽 순서로 더한다. 따라서 결합법칙을 만족하지 않는 합 연산을 적용하면 결과가 일정하지 않다. exclusive_scan() 알고리즘도 합 연산의 순서가 일정하지 않다. inclusive_scan()을 수행할 때 i번째 원소는 i번째 합에 포함된다. 이는 partial_sum()과 같다. 반면 exclusive_scan()에서는 i번째 원소가 i번째 합에 포함되지 않는다.

transform_exclusive_scan() transform_inclusive_scan()

주어진 시퀀스의 각 원소마다 변환을 적용한 다음 exclusive_scan() 또는 inclusive_scan()을 적용한다.

accumulate()

주어진 시퀀스의 모든 원솟값을 누적한다. 기본적으로 원소의 합을 구하지만 얼마든지 다른 이항 함수를 지정할 수 있다.

inner_product()

accumulate()와 비슷하지만 두 개의 시퀀스에 대해 적용한다. 이 알고리즘은 두 시퀀스에서 위치가 같은 원소를 이항 함수(디폴트 함수는 곱셈)에 적용한 뒤 그 결과를 다른 이항 함수(디폴트 함수는 덧셈)에 적용해서 결과를 누적한다. 주어진 시퀀스가 수학의 벡터라면 두 벡터의 내적을 구한다.

reduce()

accumulate()와 비슷하지만 병렬 실행을 지원한다. reduce() 연산의 실행 순서는 일정하지 않지만 accumulate()는 항상 왼쪽에서 오른쪽 순으로 처리한다. 따라서 reduce()에 주어진 이항 함수가 결합법칙이나 교환법칙을 만족하지 않으면 결과가 일정하지 않다.

transform_reduce()

주어진 시퀀스에 있는 각 원소를 변환한 다음 reduce()를 수행한다.

알고리즘 이름

설명

복잡도

is_Permutation()

두 시퀀스 중 하나가 다른 시퀀스의 순열이면 true를 리턴한다.

제곱(quadratic)

next_permutation() prev_permutation()

주어진 시퀀스를 사전 순으로 다음 또는 이전에 나오는 순열로 변환한다. 어느 하나에 대해 연속적으로 호출하면 모든 경우의 순열을 구할 수 있다. 단, 제대로 정렬된 시퀀스로 호출하기 싲가해야 한다. 더는 나올 수 있는 순열이 없으면 false를 리턴한다.

선형