알고리즘 라이브러리
알고리즘 라이브러리는 다음을 포함한 다양한 목적(예: 검색, 정렬, 카운팅, 조작)의 함수를 정의하며, 이 함수들은 ranges 의 요소에 대해 작동합니다.
제약된 알고리즘 (C++20부터)
C++20는 제약된 버전의 대부분의 알고리즘을 std::ranges 네임스페이스에 제공합니다. 이 알고리즘들에서, 범위는 반복자-센티널 쌍 또는 단일 범위 인수로 지정할 수 있으며, 프로젝션과 멤버 포인터 호출 가능 객체가 지원됩니다. 또한, 대부분의 알고리즘의 반환 유형이 알고리즘 실행 중 계산된 모든 잠재적으로 유용한 정보를 반환하도록 변경되었습니다.
std::vector<int> v{7, 1, 4, 0, -1};
std::ranges::sort(v); // constrained algorithm
병렬 알고리즘 (C++17부터)
하나의 병렬 알고리즘은 알고리즘 라이브러리의 함수 템플릿으로, ExecutionPolicy라는 이름의 템플릿 매개변수를 가지거나 execution-policy (C++26부터)에 의해 제한됩니다. 이러한 템플릿 매개변수를 실행 정책 템플릿 매개변수 라고 하며, 이는 병렬 알고리즘의 실행이 병렬화될 수 있는 방식을 설명합니다.
별도로 명시되지 않는 한, 병렬 알고리즘은 std::is_trivially_copy_constructible_v<T>과 std::is_trivially_destructible_v<T>가 모두 true인 경우 범위의 요소를 임의로 복사할 수 있습니다. 여기서 T는 요소의 유형입니다.
실행 정책
표준 라이브러리 알고리즘은 여러 실행 정책을 지원하며, 라이브러리는 해당 실행 정책 유형과 객체를 제공합니다. 사용자는 해당 유형의 실행 정책 객체를 사용하여 병렬 알고리즘을 호출함으로써 실행 정책을 정적으로 선택할 수 있습니다.
표준 라이브러리 구현체(사용자는 아님)는 확장으로 추가 실행 정책을 정의할 수 있습니다. 구현 정의 유형의 실행 정책 객체로 호출된 병렬 알고리즘의 의미는 구현 정의입니다.
헤더
<execution> | |
에 정의됨
std::execution | |
(C++17)(C++17)(C++17)(C++20) |
실행 정책 유형 (클래스) |
(C++17)(C++17)(C++17)(C++20) |
전역 실행 정책 객체 (상수) |
네임스페이스
std | |
is_execution_policy |
(C++17) 클래스가 실행 정책을 나타내는지 테스트 |
execution-policy |
(C++26) 유형이 실행 정책을 나타냄을 지정합니다(설명 전용 개념* |
비수정 시퀀스 연산
배치 연산
헤더에 정의됨
<algorithm> | |
| 단항을 적용합니다 함수 객체 의 요소에 범위 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
(C++17) |
시퀀스의 처음 N개 요소에 함수 객체를 적용합니다 (함수 템플릿 & 알고리즘 함수 객체) |
(C++20) |
|
탐색 연산
헤더에 정의됨
<algorithm> | |
(C++11)(C++11)(C++11) |
조건자가 true 범위 내 모든 요소, 일부 요소, 또는 아무 요소에 대해 확인합니다(함수 템플릿 & 알고리즘 함수 객체) |
(C++20)(C++20)(C++20) |
|
(C++23)(C++23) |
범위가 주어진 요소 또는 부분 범위를 포함하는지 확인합니다 (알고리즘 함수 객체) |
(C++11) |
특정 조건을 만족하는 첫 번째 요소를 찾습니다 (함수 템플릿 & 알고리즘 함수 객체) |
(C++20)(C++20)(C++20) |
|
(C++23)(C++23)(C++23) |
특정 조건을 만족하는 마지막 요소를 찾습니다 (알고리즘 함수 객체) |
| 특정 범위에서 마지막으로 나타나는 요소 시퀀스를 찾습니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 요소 집합 중 하나를 검색합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 동일한 (또는 주어진 조건을 만족하는) 처음 두 개의 인접 항목을 찾습니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 특정 조건을 만족하는 요소의 개수를 반환합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20)(C++20) |
|
| 두 범위가 다른 첫 번째 위치를 찾습니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 두 요소 집합이 동일한지 확인합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 요소 범위의 첫 번째 발생을 검색합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 범위에서 요소의 연속된 복사본이 처음 나타나는 위치를 검색합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
(C++23) |
범위가 다른 범위로 시작하는지 확인합니다 (알고리즘 함수 객체) |
(C++23) |
범위가 다른 범위로 끝나는지 확인합니다 (알고리즘 함수 객체) |
폴드 연산 (C++23부터)
|
헤더 파일에 정의됨
<algorithm>
|
|
|
(C++23)
|
요소 범위를 왼쪽으로 폴딩
(알고리즘 함수 객체) |
|
(C++23)
|
첫 번째 요소를 초기값으로 사용하여 요소 범위를 왼쪽으로 폴딩
(알고리즘 함수 객체) |
|
(C++23)
|
요소 범위를 오른쪽으로 폴딩
(알고리즘 함수 객체) |
|
(C++23)
|
마지막 요소를 초기값으로 사용하여 요소 범위를 오른쪽으로 폴딩
(알고리즘 함수 객체) |
|
(C++23)
|
요소 범위를 왼쪽으로 폴딩하고
pair
(반복자, 값)을 반환
(알고리즘 함수 객체) |
|
첫 번째 요소를 초기값으로 사용하여 요소 범위를 왼쪽으로 폴딩하고
pair
(반복자,
optional
)을 반환
(알고리즘 함수 객체) |
|
시퀀스 수정 연산
복사 연산
헤더에 정의됨
<algorithm> | |
(C++11) |
요소 범위를 새 위치에 복사합니다 (함수 템플릿 & 알고리즘 함수 객체) |
(C++20)(C++20) |
|
(C++11) |
지정된 개수의 요소를 새 위치에 복사합니다 (함수 템플릿 & 알고리즘 함수 객체) |
(C++20) |
|
| 요소 범위를 역순으로 새 위치에 복사합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
(C++11) |
요소 범위를 새 위치로 이동합니다 (함수 템플릿 & 알고리즘 함수 객체) |
(C++20) |
|
(C++11) |
요소 범위를 역순으로 새 위치로 이동합니다 (함수 템플릿 & 알고리즘 함수 객체) |
(C++20) |
|
Swap 연산
헤더
<algorithm> 에 정의됨 (C++11까지) | |
헤더
<utility> 에 정의됨 (C++11부터) | |
| 두 객체의 값을 교환합니다 (함수 템플릿) | |
헤더
<algorithm> | |
| 두 요소 범위를 교환합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 두 반복자가 가리키는 요소를 교환합니다 (함수 템플릿) | |
변환 연산
헤더
<algorithm> | |
| 범위의 요소에 함수를 적용하고 결과를 대상 범위에 저장합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 특정 조건을 만족하는 모든 값을 다른 값으로 대체합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20)(C++20) |
|
| 범위를 복사하고 특정 조건을 만족하는 요소를 다른 값으로 대체합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20)(C++20) |
|
생성 연산
헤더에 정의됨
<algorithm> | |
| 주어진 값을 범위 내 모든 요소에 복사 할당합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 주어진 값을 범위 내 N개 요소에 복사 할당합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 연속적인 함수 호출 결과를 범위 내 모든 요소에 할당합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 연속적인 함수 호출 결과를 범위 내 N개 요소에 할당합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
제거 연산
헤더에 정의됨
<algorithm> | |
| 특정 조건을 만족하는 요소들을 제거합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20)(C++20) |
|
| 특정 조건을 만족하는 요소들을 생략하여 범위의 요소들을 복사합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20)(C++20) |
|
| 범위에서 연속된 중복 요소들을 제거합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 연속된 중복이 없는 요소들의 범위의 복사본을 생성합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
순서 변경 연산
헤더에 정의됨
<algorithm> | |
| 범위 내 요소들의 순서를 반전시킵니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 반전된 범위의 복사본을 생성합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 범위 내 요소들의 순서를 회전시킵니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 요소 범위를 복사하고 회전시킵니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
(C++20)(C++20) |
범위 내 요소들을 이동시킵니다 (함수 템플릿 & 알고리즘 함수 객체) |
(C++23)(C++23) |
|
(until C++17)(C++11) |
범위 내 요소들을 무작위로 재정렬합니다 (함수 템플릿 & 알고리즘 함수 객체) |
(C++20) |
|
샘플링 연산
헤더에 정의됨
<algorithm> | |
(C++17) |
시퀀스에서 N개의 무작위 요소를 선택합니다 (함수 템플릿 & 알고리즘 함수 객체) |
(C++20) |
|
요구 사항
일부 알고리즘은 인수로 표현된 시퀀스가 "정렬(sorted)" 또는 "분할(partitioned)"되어 있어야 합니다. 요구 사항이 충족되지 않으면 동작이 정의되지 않습니다.
|
시퀀스는 비교자에 대해 정렬됨 |
(C++20까지) |
|
시퀀스는 정렬됨, 시퀀스는 비교자 |
(C++20부터) |
시퀀스 [start, finish)는 표현식 f(e)에 대해 분할됨을 만족합니다. 만약 정수 n이 존재하여 i에 있는 모든 [0, std::distance(start, finish))에 대해 f(*(start + i))[1]이 true인 것과 i < n인 것이 동치인 경우.
분할 연산
헤더에 정의됨
<algorithm> | |
(C++11) |
주어진 조건자에 의해 범위가 분할되었는지 확인합니다 (함수 템플릿 & 알고리즘 함수 객체) |
(C++20) |
|
| 요소 범위를 두 그룹으로 나눕니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
(C++11) |
요소를 두 그룹으로 나누어 범위를 복사합니다 (함수 템플릿 & 알고리즘 함수 객체) |
(C++20) |
|
| 각 그룹 내에서 상대적 순서를 유지하면서 요소를 두 그룹으로 나눕니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
(C++11) |
분할된 범위의 분할 지점을 찾습니다 (함수 템플릿 & 알고리즘 함수 객체) |
(C++20) |
|
정렬 연산
헤더에서 정의됨
<algorithm> | |
| 요소의 범위를 정렬합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 요소의 범위를 정렬하되 동등한 요소 간의 상대적 순서를 유지합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 범위의 처음 N개 요소를 정렬합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 요소의 범위를 복사하고 부분적으로 정렬합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
(C++11) |
범위가 정렬되었는지 확인합니다 (함수 템플릿 & 알고리즘 함수 객체) |
(C++20) |
|
(C++11) |
가장 큰 정렬된 부분 범위를 찾습니다 (함수 템플릿 & 알고리즘 함수 객체) |
(C++20) |
|
| 범위가 정렬되었을 때 N번째 요소를 찾습니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
이진 탐색 연산 (분할된 구간에 대해)
헤더에 정의됨
<algorithm> | |
| 이진 탐색을 사용하여 주어진 값보다 작지 않은 첫 번째 요소를 찾습니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 이진 탐색을 사용하여 주어진 값보다 큰 첫 번째 요소를 찾습니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 이진 탐색을 사용하여 주어진 값과 일치하는 요소의 범위를 찾습니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 이진 탐색을 사용하여 요소가 범위에 존재하는지 확인합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
집합 연산 (정렬된 범위에 대해)
헤더에 정의됨
<algorithm> | |
| 하나의 시퀀스가 다른 시퀀스의 부분 시퀀스인지 결정합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 두 집합의 합집합을 계산합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 두 집합의 교집합을 계산합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 두 집합 간의 차집합을 계산합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 두 집합의 대칭 차집합을 계산합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
병합 연산 (정렬된 범위에 대해)
헤더에 정의됨
<algorithm> | |
| 두 개의 정렬된 범위를 병합합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 두 개의 정렬된 범위를 제자리에서 병합합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
힙 연산
|
무작위 접근 범위 |
(C++20까지) |
|
무작위 접근 범위 무작위 접근 범위 |
(C++20부터) |
힙은 다음으로 생성될 수 있습니다: std::make_heap 및 ranges::make_heap(C++20부터).
힙의 더 많은 속성에 대해서는 최대 힙.
헤더에 정의됨
<algorithm> | |
| 최대 힙에 요소를 추가합니다 (함수 템플릿 &알고리즘 함수 객체) | |
(C++20) |
|
| 최대 힙에서 가장 큰 요소를 제거합니다 (함수 템플릿 &알고리즘 함수 객체) | |
(C++20) |
|
| 요소 범위로 최대 힙을 생성합니다 (함수 템플릿 &알고리즘 함수 객체) | |
(C++20) |
|
| 최대 힙을 오름차순으로 정렬된 요소 범위로 변환합니다 (함수 템플릿 &알고리즘 함수 객체) | |
(C++20) |
|
(C++11) |
주어진 범위가 최대 힙인지 확인합니다 (함수 템플릿 &알고리즘 함수 객체) |
(C++20) |
|
(C++11) |
최대 힙인 가장 큰 부분 범위를 찾습니다 (함수 템플릿 &알고리즘 함수 객체) |
(C++20) |
|
최소/최대 연산
헤더에 정의됨
<algorithm> | |
| 주어진 값들 중 더 큰 값을 반환합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 범위 내에서 가장 큰 요소를 반환합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 주어진 값들 중 더 작은 값을 반환합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 범위 내에서 가장 작은 요소를 반환합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
(C++11) |
두 요소 중 더 작은 값과 더 큰 값을 반환합니다 (함수 템플릿 & 알고리즘 함수 객체) |
(C++20) |
|
(C++11) |
범위 내에서 가장 작은 요소와 가장 큰 요소를 반환합니다 (함수 템플릿 & 알고리즘 함수 객체) |
(C++20) |
|
(C++17) |
값을 한 쌍의 경계 값 사이로 고정합니다 (함수 템플릿 & 알고리즘 함수 객체) |
(C++20) |
|
사전식 비교 연산
헤더에 정의됨
<algorithm> | |
| 두 범위를 사전식으로 비교합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
| 세 방향 비교를 사용하여 두 범위를 비교합니다 (함수 템플릿) | |
순열 연산
헤더에 정의됨
<algorithm> | |
| 요소 범위의 사전식 순서에서 다음으로 큰 순열을 생성합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 요소 범위의 사전식 순서에서 다음으로 작은 순열을 생성합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
(C++11) |
시퀀스가 다른 시퀀스의 순열인지 확인합니다 (함수 템플릿 & 알고리즘 함수 객체) |
(C++20) |
|
숫자 연산
헤더에 정의됨
<numeric> | |
(C++11) |
시작 값의 연속적인 증가분으로 범위를 채웁니다 (함수 템플릿 & 알고리즘 함수 객체) |
(C++23) |
|
| 범위의 요소를 합산하거나 축소합니다 (함수 템플릿) | |
| 두 요소 범위의 내적을 계산합니다 (함수 템플릿) | |
| 범위 내 인접 요소 간의 차이를 계산합니다 (함수 템플릿) | |
| 요소 범위의 부분 합을 계산합니다 (함수 템플릿) | |
(C++17) |
와 유사함 std::accumulate, 순서에 상관없이 처리하는 점이 다름 (함수 템플릿) |
(C++17) |
와 유사함 std::partial_sum, 제외합니다 i번째 입력 요소를 i번째 합계에서 (함수 템플릿) |
(C++17) |
와 유사함 std::partial_sum, 포함합니다 i번째 입력 요소를 i번째 합계에 (함수 템플릿) |
(C++17) |
호출 가능 객체를 적용한 후, 순서에 상관없이 축소합니다 (함수 템플릿) |
(C++17) |
호출 가능 객체를 적용한 후, 배타적 스캔을 계산합니다 (함수 템플릿) |
(C++17) |
호출 가능 객체를 적용한 후, 포괄적 스캔을 계산합니다 (함수 템플릿) |
특화된 <memory> 알고리즘
특수화된 <random>알고리즘 (C++26부터)
헤더에 정의됨
<random> | |
(C++26) |
균일 난수 비트 생성기로부터 난수를 사용하여 범위를 채웁니다 (알고리즘 함수 객체) |
참고 사항
| 기능 테스트 매크로 | 값 | 표준 | 기능 |
|---|---|---|---|
__cpp_lib_algorithm_iterator_requirements
|
202207L
|
(C++23) | 비-레인지 알고리즘에 대한 입력으로서의 레인지 반복자 |
__cpp_lib_clamp
|
201603L
|
(C++17) | std::clamp |
__cpp_lib_constexpr_algorithms
|
201806L
|
(C++20) | 알고리즘에 대한 constexpr |
202306L
|
(C++26) | Constexpr 안정 정렬 | |
__cpp_lib_algorithm_default_value_type
|
202403L
|
(C++26) | 목록 초기화 for algorithms |
__cpp_lib_freestanding_algorithm
|
202311L
|
(C++26) | <algorithm> 내의 독립형 기능 |
__cpp_lib_robust_nonmodifying_seq_ops
|
201304L
|
(C++14) | 비수정 시퀀스 연산의 강화 (두 범위 오버로드 for std::mismatch , std::equal and std::is_permutation) |
__cpp_lib_sample
|
201603L
|
(C++17) | std::sample |
__cpp_lib_shift
|
201806L
|
(C++20) | std::shift_left and std::shift_right |
C 라이브러리
|
헤더 파일에 정의됨
<cstdlib>
|
|
|
지정되지 않은 타입의 요소 범위를 정렬합니다
(함수) |
|
|
배열에서 지정되지 않은 타입의 요소를 검색합니다
(함수) |
|
결함 보고서
다음의 동작 변경 결함 보고서들은 이전에 발표된 C++ 표준에 소급 적용되었습니다.
| DR | 적용 대상 | 게시된 동작 | 올바른 동작 |
|---|---|---|---|
| LWG 193 | C++98 | 힙이 * first 가 가장 큰 요소여야 함 |
*
first
와 동일한 요소가
존재할 수 있음 |
| LWG 2150 | C++98 | 정렬된 시퀀스의 정의가 부정확했음 | 수정됨 |
| LWG 2166 | C++98 |
힙 요구사항이
최대 힙 정의와 충분히 일치하지 않았음 |
요구사항 개선됨 |
참고 항목
|
C 문서
참조:
Algorithms
|