STL Algorithm
C++ 표준 라이브러리에서 제공하는 범용 알고리즘 함수들의 모음이다
컨테이너의 요소들을 처리하기 위한 다양한 연산을 제공
특징
- 반복자 기반 : 컨테이너에 독립적으로 동작하며, 반복자를 통해 요소에 접근
- 재사용성 : 다양한 컨테이너(vector,list,set 등)에 동일하게 사용
- 효율성 : 최적화된 구현으로 성능이 우수하다
- 타입 안정성 : 템플릿 기반으로 타입 안전성을 보장한다
- 비변경 알고리즘 : 컨테이너를 수정하지 않는 알고리즘
- 변경 알고리즘 : 컨테이너의 요소를 수정하는 알고리즘
알고리즘 분류
1. 비변경 시퀀스 연산(Non-modifying sequence operations)
컨테이너의 요소를 변경하지 않고 조회/검색/비교하는 알고리즘
검색 관련
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> v1 = { 1,3,5,32,7,35,3 }; std::vector<int> v2 = { 1,2,0,0,3,4,0,0,5 }; std::vector<int> v3 = { 0 }; // find() : 특정 값을 찾음 // 반환 타입 : iterator auto it4 = std::find(v1.begin(), v1.end(), 5); int val = 30; // find_if() : 조건을 만족하는 첫 번째 요소를 찾음 // 반환 타입 : iterator auto it1 = std::find_if(v1.begin(), v1.end(), [val](int _a) {return val < _a; }); if (it1 != v1.end()) { std::cout << *it1 << std::endl; } // find_if_not() : 조건을 만족하지 않는 첫 번째 요소를 찾음 // 반환 타입 : iterator auto it2 = std::find_if_not(v1.begin(), v1.end(), [val](int _a) {return val < _a; }); if (it2 != v1.end()) { std::cout << *it2 << std::endl; } // find_end() : 한 범위 내에서 다른 범위(부분 수열)가 마지막으로 나타나는 위치를 찾음 // 반환 타입 : iterator // std::find_end(A_begin, A_end, B_begin, B_end): // A (범위1): 검색 대상 큰 범위 (여기서 찾는다) // B (범위2): 패턴 작은 범위 (이걸 찾는다) // v2 = 1,2,0,0,3,4,0,0,5 // v3 = 0 // v2에서 v3의 범위가 나타나는 위치를 v2의 7번째이다. auto it3 = std::find_end(v2.begin(), v2.end(), v3.begin(), v3.end()); if (it3 != v2.end()) { // std::distance() : 두 반복자 사이의 거리(요소 개수)를 계산 std::cout << std::distance(v2.begin(), it3) << std::endl; } return 0; }
- find() : 특정 값을 찾음
- find_if() : 조건을 만족하는 첫 번째 요소를 찾음
- find_if_not() : 조건을 만족하지 않은 첫 번째 요소를 찾음
- find_end() : 부분 범위의 마지막 출현 위치를 찾음
1. find_first_of() : 여러 값 중 하나를 찾음
시간 복잡도 - O(N × M) : N은 첫 번째 범위의 크기, M은 두 번째 범위의 크기
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> v1 = { 1,3,5,6,32,7,35,3 }; std::vector<int> v2 = { 1,5,4,2,3,3,4,5,6,6,7 }; std::vector<int> v3 = { 35,5,7 }; std::vector<int> v4 = { 3,4,5,4,6,5 }; std::vector<int> v5 = { 3,3 }; // 함수 시그니처 // template< class ForwardIt1, class ForwardIt2 > // ForwardIt1 find_first_of(ForwardIt1 first1, ForwardIt1 last1, // ForwardIt2 first2, ForwardIt2 last2); // template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > // ForwardIt1 find_first_of(ForwardIt1 first1, ForwardIt1 last1, // ForwardIt2 first2, ForwardIt2 last2, // BinaryPredicate p); // find_first_of() : 한 범위에서 다른 범위의 요소 중 어느 하나라도 일치하는 첫 번째 요소를 찾음 // 반환 타입 : iterator // // [first1, last1] 범위의 각 요소를 순회하면서 // [first2, last2] 범위의 요소 중 하나라도 일치하면 그 위치를 반환 // BinaryPredicate p: 비교함수 (선택적) auto it1 = std::find_first_of(v1.begin(), v1.end(), v3.begin(), v3.end()); if (it1 != v1.end()) { std::cout << std::distance(v1.begin(), it1) << std::endl; } return 0; }
2. adjacent_find() : 인접한 중복 요소를 찾음
시간 복잡도 - O(N) : N은 범위의 크기
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> v1 = { 1,3,5,6,32,7,35,3 }; std::vector<int> v2 = { 1,5,4,2,3,3,4,5,6,6,7 }; std::vector<int> v3 = { 35,5,7 }; std::vector<int> v4 = { 3,4,5,4,6,5 }; std::vector<int> v5 = { 3,3 }; // 함수 시그니처 // template< class ForwardIt > // ForwardIt adjacent_find(ForwardIt first, ForwardIt last); // template< class ForwardIt, class BinaryPredicate > // ForwardIt adjacent_find(ForwardIt first, ForwardIt last, // BinaryPredicate p); // adjacent_find() : 범위 내에서 연속된(인접한) 두 요소가 같거나 특정 조건을 만족하는 첫 번째 위치를 찾음 // 반환 타입 : iterator // BinaryPredicate p: 비교함수 (선택적) auto it2 = std::adjacent_find(v2.begin(), v2.end()); if (it2 != v2.end()) { std::cout << *it2 << ", " << *(it2 + 1) << std::endl; } auto it3 = std::adjacent_find(v4.begin(), v4.end(), [](int _a, int _b) {return (_b - _a) < 1; }); if (it3 != v4.end()) { std::cout << *it3 << ", " << *(it3 + 1) << std::endl; } // 인접 요소 비교: 연속된 두 요소만 비교 // 첫 번째 발견: 조건을 만족하는 요소 쌍만 반환 // 유연성: 사용자가 정의한 함수로 다양한 조건 검사 가능 // 효율성: 정렬된 데이터에서 특정 찾기에 유용 return 0; }
3. search() : 부분 범위를 찾음
시간 복잡도 - 최악의 경우 O(N × M): N은 검색 대상 범위 크기, M은 패턴 크기
평균적으로는 더 빠름
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> v1 = { 1,3,5,6,32,7,35,3 }; std::vector<int> v2 = { 1,5,4,2,3,3,4,5,6,6,7 }; std::vector<int> v3 = { 35,5,7 }; std::vector<int> v4 = { 3,4,5,4,6,5 }; std::vector<int> v5 = { 3,3 }; // 함수 시그니처 // template< class ForwardIt1, class ForwardIt2 > // ForwardIt1 search(ForwardIt1 first1, ForwardIt1 last1, // ForwardIt2 first2, ForwardIt2 last2); // template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > // ForwardIt1 search(ForwardIt1 first1, ForwardIt1 last1, // ForwardIt2 first2, ForwardIt2 last2, // BinaryPredicate p); // search() : 한 범위 안에서 다른 범위(패턴)가 처음 나타나는 위치를 찾음 // 반환 타입 : iterator // first1, last1: 검색 대상 범위 // first2, last2: 찾을 패턴 범위 // BinaryPredicate p: 비교함수 (선택적) // 찾지 못하면 last1 반환 auto it4 = std::search(v2.begin(), v2.end(), v5.begin(), v5.end()); if (it4 != v2.end()) { std::cout << *it4 << std::endl; } return 0; }
4. search_n() : 연속된 n개의 동일한 값을 찾음
시간 복잡도 - O(N): N은 범위의 크기
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> v1 = { 1,3,5,6,32,7,35,3 }; std::vector<int> v2 = { 1,5,4,2,3,3,4,5,6,6,7 }; std::vector<int> v3 = { 35,5,7 }; std::vector<int> v4 = { 3,4,5,4,6,5 }; std::vector<int> v5 = { 3,3 }; // 함수 시그니처 // template< class ForwardIt, class Size, class T > // ForwardIt search_n(ForwardIt first, ForwardIt last, // Size count, const T & value); // template< class ForwardIt, class Size, class T, class BinaryPredicate > // ForwardIt search_n(ForwardIt first, ForwardIt last, // Size count, const T & value, // BinaryPredicate p); // search_n() : 특정 값이 연속으로 N번 나타나는 첫 번째 위치를 찾음 // 반환 타입 : iterator // first, last : 검색 대상 범위 // count : 연속으로 나타나야 하는 횟수 // value : 찾을 값 // BinaryPredicate p : 비교함수 (선택적) // 찾지 못하면 last1 반환 auto it5 = std::search_n(v2.begin(), v2.end(), 2, 3); if (it5 != v2.end()) { std::cout << it5 - v2.begin() << std::endl; } // 연속 패턴 : 값이 연속으로 count번 나타나야 함 // 첫 번째 출력 : 조건을 만족하는 첫 번째 위치 반환 // count=0: count가 0이면 항상 first 반환 return 0; }
개수 관련
1. count() : 특정 값의 개수
시간 복잡도 - O(N): N은 범위의 크기
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> v1 = { 1,3,5,6,32,7,35,3 }; std::vector<int> v2 = { 1,5,4,2,3,3,4,5,6,6,7 }; std::vector<int> v3 = { 35,5,7 }; std::vector<int> v4 = { 3,4,5,4,6,5 }; std::vector<int> v5 = { 3,3 }; // 함수 시그니처 // template< class InputIt, class T > // typename iterator_traits<InputIt>::difference_type // count(InputIt first, InputIt last, const T & value); // first, last : 검색할 범위 // value : 찾을 값 // 반환 값 : value와 일치하는 요소의 개수 auto count1 = std::count(v2.begin(), v2.end(), 6); std::cout << "6과 일치하는 요소의 개수: " << count1 << std::endl; return 0; }
2. count_if() : 조건을 만족하는 요소의 개수
시간 복잡도 - O(N) : N은 범위의 크기
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> v1 = { 1,3,5,6,32,7,35,3 }; std::vector<int> v2 = { 1,5,4,2,3,3,4,5,6,6,7 }; std::vector<int> v3 = { 35,5,7 }; std::vector<int> v4 = { 3,4,5,4,6,5 }; std::vector<int> v5 = { 3,3 }; // 함수 시그니처 // template< class InputIt, class UnaryPredicate > // typename iterator_traits<InputIt>::difference_type // count_if(InputIt first, InputIt last, UnaryPredicate p); // count_if() : 범위 내에서 특정 조건을 만족하는 요소의 개수를 세어 반환 // first, last : 검색할 범위 // p : 조건 함수 (하나의 인수를 받아 bool 반환) // 반환 값 : 조건을 만족하는 요소의 개수 auto count1 = std::count_if(v2.begin(), v2.end(), [](int _a) {return _a > 2 && _a < 5; }); std::cout << "3 ~ 4과 일치하는 요소의 개수: " << count1 << std::endl; // 특징 // 조건 기반: 사용자 정의 조건으로 유연하게 검색 // 단일 인수: 조건 함수는 하나의 요소만 받음 // 비파괴적: 원본 데이터 변경 없음 // 다양한 활용: 복잡한 조건도 표현 가능 return 0; }비교
1. mismatch() : 두범위에서 첫 번째 불일치 위치를 찾음
시간 복잡도 - O(N) : N은 비교하는 요소의 개수 (더 짧은 범위 기준)
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> v1 = { 1,3,5,6,32,7,35,3 }; std::vector<int> v2 = { 1,5,4,2,3,3,4,5,6,6,7 }; std::vector<int> v3 = { 35,5,7 }; std::vector<int> v4 = { 3,4,5,4,6,5 }; std::vector<int> v5 = { 3,4,5,5,6,4 }; // 함수 시그니처 // template< class InputIt1, class InputIt2 > // std::pair<InputIt1, InputIt2> // mismatch(InputIt1 first1, InputIt1 last1, // InputIt2 first2); // template< class InputIt1, class InputIt2, class BinaryPredicate > // std::pair<InputIt1, InputIt2> // mismatch(InputIt1 first1, InputIt1 last1, // InputIt2 first2, InputIt2 last2, // BinaryPredicate p); // C++14 // template< class InputIt1, class InputIt2 > // std::pair<InputIt1, InputIt2> // mismatch(InputIt1 first1, InputIt1 last1, // InputIt2 first2, InputIt2 last2); // mismatch() : 두 범위를 비교하여 처음으로 다른 요소가 나타나는 위치를 찾음 // first1, last1 : 첫 번째 범위 // first2, last2 : 두 번째 범위 // p : 비교 함수 (선택적) // 반환 값 : std::pair: 두 범위에서 처음으로 다른 요소를 가리키는 반복자 쌍 // 두 요소가 같으면 {last1, first2 + (last1 - first1)} 반환 auto pair = std::mismatch(v4.begin(), v4.end(), v5.begin(), v5.end()); if (pair.first != v4.end()) { std::cout << *pair.first << ", " << *pair.second << std::endl; std::cout << "위치: " << pair.first - v4.begin() << std::endl; } // 특징 // 두 범위 비교: 두 시퀀스를 동시에 비교 // 첫 불일치 차이: 처음 다른 위치만 반환 // 결과 반환: 양쪽 범위의 반복자를 모두 반환 return 0; }2. equal() : 두 범위가 같은지 비교
시간 복잡도 - O(N) : N은 비교하는 요소의 개수
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> v1 = { 1,3,5,6,32,7,35,3 }; std::vector<int> v2 = { 1,5,4,2,3,3,4,5,6,6,7 }; std::vector<int> v3 = { 35,5,7 }; std::vector<int> v4 = { 3,4,5,4,6,5 }; std::vector<int> v5 = { 3,4,5,5,6,4 }; // 함수 시그니처 // template< class InputIt1, class InputIt2 > // bool equal(InputIt1 first1, InputIt1 last1, // InputIt2 first2); // template< class InputIt1, class InputIt2, class BinaryPredicate > // bool equal(InputIt1 first1, InputIt1 last1, // InputIt2 first2, BinaryPredicate p); // C++14부터 // template< class InputIt1, class InputIt2 > // bool equal(InputIt1 first1, InputIt1 last1, // InputIt2 first2, InputIt2 last2); // equal() : 두 범위의 요소들이 모두 같은지 확인 // first1, last1 : 첫 번째 범위 // first2, last2 : 두 번째 범위 // p : 비교 함수 (선택적) // 반환 값 : bool - true : 모든 요소가 같음, false : 하나라도 다름 auto check = std::equal(v4.begin(), v4.end(), v5.begin(), v5.end()); if (check) { std::cout << "v4, v5 모든 요소가 같음" << std::endl; } else { std::cout << "v4, v5 하나라도 다름" << std::endl; } // 특징 // bool 반환: 같으면 true, 다르면 false // 전체 비교: 모든 요소를 비교 // 조기 종료: 다른 요소를 발견하면 즉시 false 반환 return 0; }순회
1. for_each() : 각 요소에 함수를 적용
시간 복잡도 - O(N) : N은 범위의 크기
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> v1 = { 1,3,5,6,32,7,35,3 }; std::vector<int> v2 = { 1,5,4,2,3,3,4,5,6,6,7 }; std::vector<int> v3 = { 35,5,7 }; std::vector<int> v4 = { 3,4,5,4,6,5 }; std::vector<int> v5 = { 3,4,5,5,6,4 }; // 함수 시그니처 // template< class InputIt, class UnaryFunction > // UnaryFunction for_each(InputIt first, InputIt last, UnaryFunction f); // C++17부터: 실행 정책 지원 // template< class ExecutionPolicy, class ForwardIt, class UnaryFunction > // void for_each(ExecutionPolicy && policy, // ForwardIt first, ForwardIt last, UnaryFunction f); // for_each() : 범위의 각 요소에 대해 함수를 실행 // first, last : 처리할 범위 // f : 각 요소에 적용할 함수 // 반환 값 : 전달된 함수 객체 f를 반환 (C++17 이전) auto f = std::for_each(v4.begin(), v4.end(), [](int& _a) { _a *= 2; }); for (const auto& val : v4) { std::cout << val << " "; } std::cout << std::endl; // 특징 // 각 요소 처리: 범위의 모든 요소에 함수 적용 // 순차 실행: 순서대로 처리 // 수정 가능: 참조를 사용하면 요소 수정 가능 // 함수 객체 반환: 상태를 가진 함수 객체의 최종 상태 반환 return 0; }2. for_each_n() : 처음 n개 요소에 함수를 적용(C++17)
시간 복잡도 - O(N) : N은 처리할 요소의 개수
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> v1 = { 1,3,5,6,32,7,35,3 }; std::vector<int> v2 = { 1,5,4,2,3,3,4,5,6,6,7 }; std::vector<int> v3 = { 35,5,7 }; std::vector<int> v4 = { 3,4,5,4,6,5 }; std::vector<int> v5 = { 3,4,5,5,6,4 }; // 함수 시그니처 // template< class InputIt, class Size, class UnaryFunction > // InputIt for_each_n(InputIt first, Size n, UnaryFunction f); // C++17부터: 실행 정책 지원 // template< class ExecutionPolicy, class ForwardIt, class Size, class UnaryFunction > // ForwardIt for_each_n(ExecutionPolicy && policy, // ForwardIt first, Size n, UnaryFunction f); // for_each_n() : C++17에서 추가된 알고리즘으로, 시작 위치부터 N개의 요소에 대해 함수를 실행 // first : 시작 위치 // n : 처리할 요소의 개수 // f : 각 요소에 적용할 함수 // 반환 값 : first + n (n개 요소 다음 위치를 가리키는 반복자) // for_each_n()은 범위를 자동으로 검사하지 않습니다. // n이 실제 요소 개수보다 크면 **정의되지 않은 동작(UB)**이 발생합니다. // 사전 검사 필수 auto f = std::for_each_n(v4.begin(), 5, [](int& _a) { _a *= 2; }); for (const auto& val : v4) { std::cout << val << " "; } std::cout << std::endl; // 특징 // 정확한 개수 제어: 정확히 n개 요소만 처리 // 반복자 반환: 처리 후 다음 위치 반환 // 범위 안정성: 끝 반복자 불포함 return 0; }
2. 변경 시퀀스 연산(Modifying sequence operations)
컨테이너의 요소를 수정하는 알고리즘
복사
1. copy() : 범위를 복사
#include <list> #include <iostream> #include <algorithm> int main() { std::list<int> list1 = { 1,2,1,1,2,2,3,4,4,4,5,5,6,6,6,7,77 }; std::list<int> list2(20); // copy() : 범위의 요소를 다른 위치로 복사 // template<class InputIt, class OutputIt> // OutputIt copy(InputIt first, InputIt last, OutputIt d_first) // first : 복사할 범위의 시작, last : 복사할 범위의 끝 (포함 안 됨), d_first : 목적지의 시작 // 반환값 : 복사된 마지막 요소 다음 위치 std::copy(list1.begin(), list1.end(), list2.begin()); // 얕은 복사: 요소를 그대로 복사, 포인터는 같은 객체를 가리킴 // 시간복잡도: O(n) // 출력 std::cout << "list1" << std::endl; for (auto& val : list1) { std::cout << val << " "; } std::cout << std::endl; std::cout << "list2" << std::endl; for (auto& val : list2) { std::cout << val << " "; } std::cout << std::endl; return 0; }2. copy_if() : 조건을 만족하는 요소만 복사
3. copy_n : n개의 요소를 복사
#include <list> #include <iostream> #include <algorithm> int main() { std::list<int> list1 = { 1,2,1,1,2,2,3,4,4,4,5,5,6,6,6,7,77 }; std::list<int> list2(20); // copy_n() : 지정한 개수만큼 요소를 복사 // template<class InputIt, class Size, class OutputIt> // OutputIt copy_n(InputIt first, Size count, OutputIt d_first); // first : 복사할 범위의 시작, count : 복사할 요소 개수, d_first : 목적지의 시작 // 반환값 : 복사된 마지막 요소 다음 위치 std::copy_n(list1.begin(), 5, list2.begin()); // count가 0이면 아무것도 복사 안 함, 음수는 정의되지 않은 동작 // 시간복잡도: O(n) // 출력 std::cout << "list2" << std::endl; for (auto& val : list2) { std::cout << val << " "; } std::cout << std::endl; return 0; }
4. copy_backward() : 역순으로 복사
#include <list> #include <iostream> #include <algorithm> int main() { std::list<int> list1 = { 1,2,1,1,2,2,3,4,4,4,5,5,6,6,6,7,77 }; std::list<int> list2(20); // copy_backward() : 범위를 역방향으로 복사 // template<class BidirIt1, class BidirIt2> // BidirIt2 copy_backward(BidirIt1 first, BidirIt1 last, BidirIt2 d_last); // first : 복사할 범위의 시작, last : 복사할 범위의 끝 (포함 안 됨), d_last : 목적지의 끝 (중요!) // 반환값 : 복사된 첫 번째 요소 위치 std::copy_backward(list1.begin(), list1.end(), list2.end()); // 시간복잡도: O(n) // 출력 std::cout << "list2" << std::endl; for (auto& val : list2) { std::cout << val << " "; } std::cout << std::endl; return 0; }이동
1. move() : 범위를 이동
#include <list> #include <iostream> #include <algorithm> int main() { std::list<int> list1 = { 1,2,1,1,2,2,3,4,4,4,5,5,6,6,6,7,77 }; std::list<int> list2(20); // move() : 범위의 요소들을 이동하는 알고리즘 // template<class InputIt, class OutputIt> // OutputIt move(InputIt first, InputIt last, OutputIt d_first); // first : 이동할 범위의 시작, last : 이동할 범위의 끝 (포함 안 됨), d_first : 목적지의 시작 // 반환값 : 이동된 마지막 요소 다음 위치 std::move(list1.begin(), list1.end(), list2.begin()); // 이동 후 원본은 비어있음! // 시간복잡도: O(n) // 출력 std::cout << "list2" << std::endl; for (auto& val : list2) { std::cout << val << " "; } std::cout << std::endl; return 0; }2. move_backward() : 역순으로 이동
#include <list> #include <iostream> #include <algorithm> int main() { std::list<int> list1 = { 1,2,1,1,2,2,3,4,4,4,5,5,6,6,6,7,77 }; std::list<int> list2(20); // move_backward() : 범위를 역방향으로 이동 // template<class BidirIt1, class BidirIt2> // BidirIt2 move_backward(BidirIt1 first, BidirIt1 last, BidirIt2 d_last); // first : 이동할 범위의 시작, last : 이동할 범위의 끝 (포함 안 됨), d_last : 목적지의 끝 // 반환값 : 이동된 첫 번째 요소 위치 std::move_backward(list1.begin(), list1.end(), list2.end()); // 이동 후 원본은 비어있음! // 시간복잡도: O(n) // 출력 std::cout << "list2" << std::endl; for (auto& val : list2) { std::cout << val << " "; } std::cout << std::endl; return 0; }변환
1. transform() : 각 요소에 함수를 적용하여 변환
교체
1. replace() : 특정 값을 다른 값으로 교체
2. replace_if() : 조건을 만족하는 요소를 교체
3. replace_copy() : 교체하면서 복사
4. replace_copy_if() : 조건부 교체하면서 복사
채우기
1. fill() : 범위를 특정 값으로 채움
2. fill_n() : n개의 요소를 특정 값으로 채움
3. generate() : 함수 호출 결과로 채움
4. generate_n() : n개의 요소를 함수 호출 결과로 채움
제거
1. remove() : 특정 값을 제거(논리적 제거)
2. remove_if() : 조건을 만족하는 요소를 제거
3. remove_copy() : 제거하면서 복사
4. remove_copy_if() : 조건부 제거하면서 복사
중복 제거
1. unique() : 연속된 중복 요소를 제거
2. unique_copy() : 중복 제거하면서 복사
순서 변경
1. reverse() : 범위를 역순으로 변경
2. reverse_copy() : 역순으로 복사
3. rotate() : 범위를 회전
4. rotate_copy() : 회전하면서 복사
5. shift_left() : 요소를 왼쪽으로 이동(C++ 20)
6. shift_right() : 요소를 오른쪽으로 이동(C++ 20)
무작위화
1. shuffle() : 무작위로 섞음(C++11)
샘플링
1. sample() : 무작위로 n개의 요소를 선택(C++17)
3. 분할 연산 (Partitioning operations)
범위를 조건에 따라 분할하는 알고리즘
1. is_partitioned() : 범위가 분할되어 있는지 확인
2. partition() : 조건에 따라 분할(순서 보장 안함)
3. stable_partition() : 조건에 따라 분할(순서 보장)
4. partition_copy() : 분할하면서 복사
5. partition_point() : 분할 지점을 찾음
4. 정렬 연산 (Sorting operations)
범위를 정렬하는 알고리즘
정렬
1. sort() : 범위를 정렬(순서 보장 안함)
2. stable_sort() : 범위를 정렬(순서 보장)
3. partial_sort() : 부분적으로 정렬
4. partial_sort_copy() : 부분 정렬하면서 복사
5. is_sorted() : 정렬되어 있는지 확인
6. is_sorted_until() : 정렬된 부분의 끝을 찾음
n번째 요소
1. nth_element() : n번째 요소를 올바른 위치에 배치
5. 이진 탐색 연산 (Binary search operations)
정렬된 범위에서 사용하는 이진 탐색 알고리즘
1. binary_search() : 값이 존재하는지 확인
2. lower_bound() : 값 이상인 첫 번째 위치를 찾음
3. upper_bound() : 값 초과인 첫 번째 위치를 찾음
4. equal_range() : -lower_bound와 upper_bound의 쌍을 반환(pair)
6. 병합 연산 (Merge operations)
정렬된 범위를 병합하는 알고리즘
1. merge() : 두 정렬된 범위를 병합
2. inplace_merge() : 한 범위 내에서 두 정렬된 부분을 병합
7. 집합 연산 (Set operations)
정렬된 범위에서 집합 연산을 수행하는 알고리즘
1. includes() : 한 범위가 다른 범위를 포함하는지 확인
2. set_difference() : 차집합
3. set_intersection() : 교집합
4. set_symmetric_difference() : 대칭 차집합
5. set_union() : 합집합
8. 힙 연산 (Heap operations)
힙 자료구조를 관리하는 알고리즘
1. make_heap() : 범위를 힙으로 만듬
2. push_heap() : 힙에 요소를 추가
3. pop_heap() : 힙에서 최대 요소를 제거
4. sort_heap() : 힙을 정렬
5. is_heap() : 힙인지 확인
6. is_heap_until() : 힙인 부분의 끝을 찾음
9. 최소/최대 연산 (Min/max operations)
최소값과 최대값을 찾는 알고리즘
1. min() : 두 값중 작은 값을 반환
2. max() : 두 값중 큰 값을 반환
3. minmax() : 최소값과 최대값의 쌍을 반환
4. min_element() : 범위에서 최소 요소를 찾음
5. max_element() : 범위에서 최대 요소를 찾음
6. minmax_element() : 최소와 최대 요소의 쌍을 찾음
7. clamp() : 값을 범위 내로 제한(C++17)
10. 비교 연산 (Comparison operations)
범위를 사전식으로 비교하는 알고리즘
1. lexicographical_compare() : 사전식 비교
2. lexicographical_compare_three_way() : 3-way 비교(C++20)
11. 순열 연산 (Permutation operations)
순열을 생성하는 알고리즘
1. next_permutation() : 다음 순열 생성
2. prev_permutation() : 이전 순열 생성
3. is_permutation() : 순열인지 확인
12. 수치 연산 (Numeric operations)
헤더파일 : #include <numeric>
누적
1. accumulate() : 범위의 합을 계산
2. reduce() : 범위를 축약(병렬 가능, C++17)
내적
1. inner_product() : 두 범위의 내적을 계산
2. transform_reduce() : 변환 후 축약(C++17)
부분합
1. partial_sum() : 부분합을 계산
2. inclusive_scan() : 포괄적 스캔(C++17)
3. exclusive_scan() : 배타적 스캔(C++17)
4. transform_inclusive_scan() : 변환 후 포괄적 스캔(C++17)
5. transform_exclusive_scan() : 변환 후 배타적 스캔(C++17)
인접 차이
1. adjacent_difference() : 인접한 요소 간의 차이를 계산
기타
1. iota() : 증가하는 값으로 범위를 채움
2. gcd() : 최대공약수(C++17)
3. lcm() : 최소공배수(C++17)
13. 범위 연산 (Ranges, C++20)
헤더파일 : #include <ranges>
