STL: <algorithm> 헤더파일
-
STL 컨테이너의 원소를 탐색, 변경, 관리, 처리할 목적으로 제공되는 함수 집합.
-
컨테이너 뿐만 아니라 일반 배열 구조(int[] 등)에도 적용 가능.
-
2개의 인자 (first, last)를 이용해서 컨테이너의 범위를 지정하므로, 2개의 인자에 배열의 주소를 직접 주어도 됨.
-
보통 주어진 범위는 [first, last) 로 지정됨. 마지막 위치는 제외.
-
-
100 여가지 알고리즘을 제공하며, 대부분의 함수들은 C++11 부터 제공됨.
-
알고리즘의 분류
-
변경 불가 알고리즘: 원소 값을 변경하지 않음.
-
변경 가능 알고리즘: 원소 값을 변경.
-
파티셔닝 알고리즘: 원소들을 두 그룹으로 나눔.
-
정렬 알고리즘: 원소의 순서를 변경.
-
이진 탐색 알고리즘: 정렬된 상태에서 원소를 탐색.
-
병합 알고리즘: 정렬된 상태의 원소들을 병합.
-
집합 연산 관련 알고리즘: 집합 연산을 제공.
-
힙 연산 관련 알고리즘: 최대 힙, 최소 힙을 탐색.
-
최대, 최소 원소 탐색 알고리즘: 주어진 범위의 최댓값과 최솟값을 탐색.
-
비교 알고리즘: 주어진 두 개의 범위가 동일한지 비교.
-
순열 알고리즘: 순열 관련 알고리즘.
-
수치 알고리즘: 부분 합 등 집계 수치 연산 제공.
-
초기화되지 않은 메모리에 대한 연산
-
변경 불가 알고리즘 (Non-modifying Sequence Algorithm)
-
all_of 범위 안의 모든 원소가 조건을 만족하는 경우 true를 반환, 그렇지 않으면 false를 반환.
-
아래의 3번째 매개변수인 UnaryPredicate 는 범위에 적용될 함수 객체인데, 함수 포인터로 이해하면 될 듯. 미리 선언된 함수의 이름을 넘기거나, Lambda 식을 넘기면 됨.
-
any_of 범위 안의 원소 중 하나라도 조건을 만족하는 경우 true를 반환, 그렇지 않으면 false를 반환.
-
none_of 범위 안의 원소 중 어떤 것도 조건을 만족하지 않으면 true를 반환, 그렇지 않으면 false를 반환.
-
// since C++ 11
template< class InputIt, class UnaryPredicate >
bool all_of( InputIt first, InputIt last, UnaryPredicate p );
// until C++ 20
template< class InputIt, class UnaryPredicate >
constexpr bool all_of( InputIt first, InputIt last, UnaryPredicate p );
// until C++ 20
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
bool all_of( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
UnaryPredicate p );
// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool isEven(int i) { return ~(i & 1); }
int main() {
vector<int> v(10, 2);
cout << "Lambda as the third parameter: ";
cout << all_of(v.begin(), v.end(), [](int i){ return i % 2 == 0; }) << endl;
cout << "Function name as the third parameter: ";
cout << all_of(v.begin(), v.end(), isEven) << endl;
return 0;
}
/*
$ g++ test.cpp -std=c++11
$ ./a.out
Lambda as the third parameter: 1
Function name as the third parameter: 1
*/-
for_each 범위 안의 각각의 원소에 대해 전달된 함수를 호출.
-
3번째 사용법을 살펴보면, 클래스(struct) 내 오버로딩된 함수(operator())를 넘겼을 때 최종 반환 결과가 객체임에 주의할 것.
-
for_each_n 첫번째 인자에서 두번째 인자로 주어진 개수만큼 전달된 함수를 호출. (C++17 부터 지원)
-
// until C++20
template< class InputIt, class UnaryFunction >
UnaryFunction for_each( InputIt first, InputIt last, UnaryFunction f );
// since C++20
template< class InputIt, class UnaryFunction >
constexpr UnaryFunction for_each( InputIt first, InputIt last, UnaryFunction f );
// since C++17
template< class ExecutionPolicy, class ForwardIt, class UnaryFunction2 >
void for_each( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
UnaryFunction2 f );
// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Sum {
void operator()(int n) { sum += n; }
int sum{0};
};
int main() {
vector<int> nums{3, 4, 2, 8, 15, 267};
auto print = [](const int& n) { cout << " " << n; };
cout << "before:";
for_each(nums.cbegin(), nums.cend(), print);
cout << endl;
for_each(nums.begin(), nums.end(), [](int &n){ n++; });
// calls Sum::operator() for each number
Sum s = for_each(nums.begin(), nums.end(), Sum());
cout << "after: ";
for_each(nums.cbegin(), nums.cend(), print);
cout << endl;
cout << "sum: " << s.sum << endl;
return 0;
}
/*
$ g++ test.cpp -std=c++11
$ ./a.out
before: 3 4 2 8 15 267
after: 4 5 3 9 16 268
sum: 305
*/-
find 범위 안에서 3번째 인자로 주어진 값과 일치하는 원소의 iterator를 반환.
-
find_if 조건과 일치하는 원소의 iterator 를 반환.
-
find_if_not 조건과 일치하지 않는 원소의 iterator 를 반환.
- set이나 map처럼 연관 컨테이너에서는 find 함수보다 멤버 함수로 제공되는 find 함수를 쓰는 것이 더 효율적임. 멤버 함수는 연관 컨테이너가 정렬된 상태임을 활용하기 때문에 훨씬 빠르게 동작함.
-
// until C++20
template< class InputIt, class T >
InputIt find( InputIt first, InputIt last, const T& value );
// since C++20
template< class InputIt, class T >
constexpr InputIt find( InputIt first, InputIt last, const T& value );
// since C++17
template< class ExecutionPolicy, class ForwardIt, class T >
ForwardIt find( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
const T& value );
// until C++20
template< class InputIt, class UnaryPredicate >
InputIt find_if( InputIt first, InputIt last, UnaryPredicate p );
// since C++20
template< class InputIt, class UnaryPredicate >
constexpr InputIt find_if( InputIt first, InputIt last, UnaryPredicate p );
// since C++17
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
ForwardIt find_if( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
UnaryPredicate p );
// find_if_not 은 find_if 과 인자가 동일
// ----------------------------------------------------------------------------------
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int n1 = 3, n2 = 5;
vector<int> v{0, 1, 2, 3, 4};
auto result1 = find(begin(v), end(v), n1);
auto result2 = find(begin(v), end(v), n2);
if (result1 != end(v)) {
cout << "v contains: " << n1 << endl;
} else {
cout << "v does not contain: " << n1 << endl;
}
if (result2 != end(v)) {
cout << "v contains: " << n2 << endl;
} else {
cout << "v does not contain: " << n2 << endl;
}
auto result3 = find_if(v.begin(), v.end(), [](int i){ return i & 1; });
if (result3 != end(v)) {
cout << "odd number: " << *result3 << endl;
}
auto result4 = find_if_not(v.begin(), v.end(), [](int i){ return i & 1; });
if (result4 != end(v)) {
cout << "even number: " << *result4 << endl;
}
return 0;
}
/*
$ g++ test.cpp -std=c++11
$ ./a.out
v contains: 3
v does not contain: 5
odd number: 1
even number: 0
*/-
adjacent_find 처음에 연속해서 나타나는 원소의 시작 위치의 iterator를 반환.
-
3번째 인자로 비교자 함수를 greater<자료형> 으로 줄 경우, 끝에서 최초로 연속해서 나타나는 원소의 시작 위치를 반환.
-
// until C++20
template< class ForwardIt >
ForwardIt adjacent_find( ForwardIt first, ForwardIt last );
template< class ForwardIt, class BinaryPredicate>
ForwardIt adjacent_find( ForwardIt first, ForwardIt last, BinaryPredicate p );
// since C++20
template< class ForwardIt >
constexpr ForwardIt adjacent_find( ForwardIt first, ForwardIt last );
template< class ForwardIt, class BinaryPredicate>
constexpr ForwardIt adjacent_find( ForwardIt first, ForwardIt last,
BinaryPredicate p );
// since C++17
template< class ExecutionPolicy, class ForwardIt >
ForwardIt adjacent_find( ExecutionPolicy&& policy,
ForwardIt first, ForwardIt last );
template< class ExecutionPolicy, class ForwardIt, class BinaryPredicate>
ForwardIt adjacent_find( ExecutionPolicy&& policy,
ForwardIt first, ForwardIt last, BinaryPredicate p );
// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;;
int main() {
vector<int> v1{0, 1, 2, 3, 40, 40, 41, 41, 5};
auto i1 = adjacent_find(v1.begin(), v1.end());
if (i1 == v1.end()) {
cout << "No matching adjacent elements\n";
} else {
cout << "The first adjacent pair of equal elements at: ";
cout << distance(v1.begin(), i1) << endl;
}
auto i2 = adjacent_find(v1.begin(), v1.end(), greater<int>());
if (i2 == v1.end()) {
cout << "The entire vector is sorted in ascending order" << endl;
} else {
cout << "The last element in the non-decreasing subsequence is at: ";
cout << distance(v1.begin(), i2) << endl;
}
return 0;
}
/*
$ g++ test.cpp -std=c++11
$ ./a.out
The first adjacent pair of equal elements at: 4
The last element in the non-decreasing subsequence is at: 7
*/-
find_end 주어진 순열이 탐색 범위에서 마지막으로 나타난 위치의 iterator를 반환.
-
시간 복잡도: O(S * (N - S + 1)), N은 탐색 범위, S는 탐색 대상의 범위
-
내부적으로 search() 함수를 사용함.
-
주어진 순열이 포함되었는지 비교하는 함수는 BinaryPredicate p라는 마지막 인자로 넘겨서 커스텀 비교자를 구현할 수 있음.
-
// until C++20
template< class ForwardIt1, class ForwardIt2 >
ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last );
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );
// since C++20
C++20)
template< class ForwardIt1, class ForwardIt2 >
constexpr ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last );
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
constexpr ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last,
BinaryPredicate p );
// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last );
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
class BinaryPredicate >
ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );
// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v{1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4};
vector<int>::iterator result;
vector<int> t1{1, 2, 3};
result = find_end(v.begin(), v.end(), t1.begin(), t1.end());
if (result == v.end()) {
cout << "sequence not found" << endl;
} else {
int dist = distance(v.begin(), result);
cout << "last occurrence is at: " << dist << endl;
}
vector<int> t2{4, 5, 6};
result = find_end(v.begin(), v.end(), t2.begin(), t2.end());
if (result == v.end()) {
cout << "sequence not found" << endl;
} else {
int dist = distance(v.begin(), result);
cout << "last occurrence is at: " << dist << endl;
}
return 0;
}
/*
$ g++ test.cpp -std=c++11
./a.out
last occurrence is at: 8
sequence not found
*/-
count 범위 안에 주어진 값과 일치하는 원소의 개수를 반환
-
count_if 주어진 조건과 일치하는 원소의 개수를 반환.
-
// until C++20
template< class InputIt, class T >
typename iterator_traits<InputIt>::difference_type
count( InputIt first, InputIt last, const T &value );
template< class InputIt, class UnaryPredicate >
typename iterator_traits<InputIt>::difference_type
count_if( InputIt first, InputIt last, UnaryPredicate p );
// since C++20
template< class InputIt, class T >
constexpr typename iterator_traits<InputIt>::difference_type
count( InputIt first, InputIt last, const T &value );
template< class InputIt, class UnaryPredicate >
constexpr typename iterator_traits<InputIt>::difference_type
count_if( InputIt first, InputIt last, UnaryPredicate p );
// since C++17
template< class ExecutionPolicy, class ForwardIt, class T >
typename iterator_traits<ForwardIt>::difference_type
count( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
const T &value );
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
typename iterator_traits<ForwardIt>::difference_type
count_if( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
UnaryPredicate p );
// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v{ 1, 2, 3, 4, 4, 3, 7, 8, 9, 10 };
// determine how many integers in a vector match a target value.
int target1 = 3, target2 = 5;
int num_items1 = count(v.begin(), v.end(), target1);
int num_items2 = count(v.begin(), v.end(), target2);
cout << "number: " << target1 << " count: " << num_items1 << endl;
cout << "number: " << target2 << " count: " << num_items2 << endl;
// use a lambda expression to count elements divisible by 3.
int num_items3 = count_if(v.begin(), v.end(), [](int i){return i % 3 == 0;});
cout << "number divisible by three: " << num_items3 << endl;
return 0;
}
/*
$ g++ test.cpp -std=c++11
$ ./a.out
number: 3 count: 2
number: 5 count: 0
number divisible by three: 3
*/-
search 범위 안에서 주어진 순열이 포함되는 첫번째 위치의 iterator를 반환.
-
시간 복잡도: O(S * N), 범위의 크기 = N, 주어진 순열의 크기 = S
-
// until C++20
template< class ForwardIt1, class ForwardIt2 >
ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last );
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );
// since C++20
template< class ForwardIt1, class ForwardIt2 >
constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last );
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last,
BinaryPredicate p );
template<class ForwardIt, class Searcher>
constexpr ForwardIt search( ForwardIt first, ForwardIt last,
const Searcher& searcher );
// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt1 search( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last );
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
class BinaryPredicate >
ForwardIt1 search( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );
// since C++17 until C++20
template<class ForwardIt, class Searcher>
ForwardIt search( ForwardIt first, ForwardIt last, const Searcher& searcher );
// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
template <typename Container>
bool in_quote(const Container& cont, const string& s) {
return search(cont.begin(), cont.end(), s.begin(), s.end()) != cont.end();
}
int main() {
string str = "why waste time learning, when ignorance is instantaneous?";
// str.find() can be used as well
cout << boolalpha << in_quote(str, "learning") << endl;
cout << in_quote(str, "lemming") << endl;
vector<char> vec(str.begin(), str.end());
cout << boolalpha << in_quote(vec, "learning") << endl;
cout << in_quote(vec, "lemming") << endl;
// The C++17 overload demo:
string in = "Lorem ipsum dolor sit amet, consectetur adipiscing elit,"
" sed do eiusmod tempor incididunt ut labore et dolore magna aliqua";
string needle = "pisci";
auto it = search(in.begin(), in.end(), boyer_moore_searcher(needle.begin(), needle.end()));
if(it != in.end()) {
cout << "The string " << needle << " found at offset ";
cout << it - in.begin() << endl;
} else {
cout << "The string " << needle << " not found" << endl;
}
return 0;
}
/*
$ g++ test.cpp -std=c++17
$ ./a.out
true
false
true
false
The string pisci found at offset 43
*/-
search_n 범위 안에서 주어진 순열을 count번 반복한 순열의 위치(iterator)를 반환.
-
시간 복잡도: O(N), 범위의 크기 = N
-
// until C++20
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 );
// since C++20
template< class ForwardIt, class Size, class T >
constexpr ForwardIt search_n( ForwardIt first, ForwardIt last, Size count,
const T& value );
template< class ForwardIt, class Size, class T, class BinaryPredicate >
constexpr ForwardIt search_n( ForwardIt first, ForwardIt last, Size count,
const T& value, BinaryPredicate p );
// since C++17
template< class ExecutionPolicy, class ForwardIt, class Size, class T >
ForwardIt search_n( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
Size count, const T& value );
template< class ExecutionPolicy, class ForwardIt, class Size, class T,
class BinaryPredicate >
ForwardIt search_n( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
Size count, const T& value, BinaryPredicate p );
// ----------------------------------------------------------------------------------
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
template <class Container, class Size, class T>
bool consecutive_values(const Container& c, Size count, const T& v) {
return search_n(begin(c),end(c),count,v) != end(c);
}
int main() {
const char sequence[] = "1001010100010101001010101";
cout << boolalpha;
cout << "Has 4 consecutive zeros: " << consecutive_values(sequence,4,'0') << endl;
cout << "Has 3 consecutive zeros: " << consecutive_values(sequence,3,'0') << endl;
return 0;
}
/*
$ g++ test.cpp -std=c++11
$ ./a.out
Has 4 consecutive zeros: false
Has 3 consecutive zeros: true
*/-
mismatch 범위 안에서 주어진 순열과 처음으로 일치하지 않는 위치의 iterator를 반환
'Programming Language > C++' 카테고리의 다른 글
| 표준 템플릿 라이브러리(STL) - 파티셔닝 알고리즘 (0) | 2020.11.20 |
|---|---|
| 표준 템플릿 라이브러리(STL) - 변경 가능 알고리즘 (0) | 2020.11.20 |
| 표준 템플릿 라이브러리(Standard Template Library) (0) | 2020.11.17 |
| 템플릿(Template) (0) | 2020.11.16 |
| 예외 처리(Exception Handling) (0) | 2020.11.16 |