References
- Professional C++
- https://en.cppreference.com/w/
Contents
- 불변형 순차 알고리즘 (non-modifying sequence algorithm)
- 탐색 알고리즘 (default_searcher, boyer_moore_searcher, boyer_moore_horspool_searcher)
- 비교 알고리즘
- 카운팅 알고리즘
- 가변형 순차 알고리즘 (modifying sequence algorithm)
- transform, transform
- copy, copy_backward, copy_if, copy_n
- move, move_backward
- replace, replace_if
- remove, remove_if, erase(C++20), erase_if(C++20)
- unique, unique_if
- shuffle
- sample
- reverse
이전 포스팅에 이어서 이번에는 대표적으로 자주 사용되는 알고리즘에 대해서 예제와 함께 알아보겠습니다. 아마도 여기서 소개하는 알고리즘만 잘 알아두면 다른 알고리즘도 쉽게 사용하실 수 있을 것이라 생각됩니다 !
1. Non-modifying Sequence Algorithm
불변형 순차 알고리즘(non-modifying sequence algorithm)이란 주어진 범위에서 원소를 검색하거나 두 범위를 서로 비교하는 함수를 의미합니다. 또한 개수를 세는 카운팅 알고리즘도 이에 속합니다.
1.1 Search Algorithms
이전 포스팅에서 find()와 find_if()라는 탐색(검색) 알고리즘의 예를 살펴봤습니다. 표준 라이브러리는 순차적으로 나열된 원소를 처리하는 기본 find() 알고리즘을 다양하게 변형한 버전을 제공합니다.
| ALGORITHM NAME | ALGORITHM SYNOPSIS | COMPLEXITY |
| adjacent_find() | 조건으로 입력한 값과 같거나 조건식에 대입한 결과가 같은 연속된 두 원소 중 처음 나온 것을 찾는다 | O(N) |
| find() find_if() |
조건으로 입력한 값과 같거나 조건식의 결과가 true인 원소 중 첫 번째 원소를 찾는다 | O(N) |
| find_first_of() | find()와 비슷하지만 여러 원소를 동시에 찾는다 | O(N * M) |
| find_if_not() | 조건식의 결과가 false인 원소 중 첫 번째 원소를 찾는다 | O(N) |
| find_end() | 입력한 시퀀스나 조건식에 맞는 시퀀스 중에서 마지막 서브시퀀스를 찾는다 | O(M * (N-M)) |
| search() | 입력된 시퀀스와 일치하거나 입력한 조건식을 기준으로 같다고판단되는 시퀀스 중에서 첫 번째 서브시퀀스를 찾는다 | O(N * M) |
| search_n() | 입력한 값과 같거나 입력한 조건식을 기준으로 같다고 판단되는 원소 중 n번 연속해서 일치하는 결과 중 첫 번째 결과를 찾는다 | O(N) |
(C++17부터 search()는 optional 매개변수를 이용해서 default_searcher, boyer_moore_searcher, boyer_moore_horsepool_searcher 등과 같은 탐색 알고리즘을 지정할 수 있습니다. 보이어-무어 알고리즘을 이용하면 패턴을 찾지 못할 때(최악의 경우)는 복잡도가 O(N+M)이고, 패턴을 찾을 때는 O(NM) 입니다.)
표준 라이브러리 알고리즘은 모두 operator==이나 operator<를 디폴트 연산자로 사용합니다. 또한 비교 콜백 함수를 직접 지정할 수 있도록 오버로딩된 버전도 있습니다.
몇 가지 탐색 알고리즘에 대한 예를 살펴보겠습니다.
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
std::vector myVector{ 5, 6, 9, 8, 8, 3 };
auto beginIter{ myVector.cbegin() };
auto endIter{ myVector.cend() };
// 주어진 람다 표현식을 만족하지 않는 첫 번째 원소를 찾는다.
auto it{ std::find_if_not(beginIter, endIter, [](int i) { return i < 8; }) };
if (it != endIter) {
std::cout << "First element not < 8 is " << *it << std::endl;
}
// 같은 값이 연속된 첫 번째 원소 쌍을 찾는다.
it = std::adjacent_find(beginIter, endIter);
if (it != endIter) {
std::cout << "Found two consecutive equal elements with value " << *it << std::endl;
}
// 두 값 중 첫 번째 값을 찾는다.
std::vector targets{ 8, 9 };
it = std::find_first_of(beginIter, endIter, targets.cbegin(), targets.cend());
if (it != endIter) {
std::cout << "Found one of 8 or 9: " << *it << std::endl;
}
// 첫 번째 부분열을 찾는다.
std::vector sub{ 8, 3 };
it = std::search(beginIter, endIter, sub.cbegin(), sub.cend());
if (it != endIter) {
std::cout << "Found subsequence {8,3}" << std::endl;
}
else {
std::cout << "Unable to find subsequence {8,3}\n";
}
// 마지막 부분열을 찾는다(여기서는 위의 부분열과 같음)
auto it2{ std::find_end(beginIter, endIter, sub.cbegin(), sub.cend()) };
if (it != it2) {
std::cout << "Error: search and find_end found different subsequences "
<< "even though there is only one match.\n";
}
// 8이 두 번 연속된 첫 번째 부분열을 찾는다.
it = std::search_n(beginIter, endIter, 2, 8);
if (it != endIter) {
std::cout << "Found two consecutive 8s\n";
}
else {
std::cout << "Unable to find two consecutive 8s\n";
}
}위 코드를 실행한 결과는 다음과 같습니다.
어떤 컨테이너에는 제너릭 알고리즘과 똑같은 기능을 수행하는 메소드가 있다는 것을 명심해야 합니다. 컨테이너에서 이런 메소드가 있다면 제너릭 알고리즘 대신 그 메소드를 사용하는 것이 좋은데, 컨테이너에서 직접 제공하는 메소드의 성능이 훨씬 더 좋기 때문입니다.
1.2 Specialized Searchers
C++17부터 search() 알고리즘에 원하는 탐색 알고리즘을 지정할 수 있도록 매개변수가 추가되었습니다. 이러한 옵션은 크게 3가지(default_searcher, boyer_moore_searcher, boyer_moore_horspool_searcher)가 있으며 모두 <functional>에 정의되어 있습니다. 두 번째와 세 번째 알고리즘은 각각 유명한 보이어-무어 탐색 알고리즘과 보이어-무어-호스풀 탐색 알고리즘을 구현한 것입니다. 모두 성능이 뛰어나며 방대한 텍스트에서 서브스트링을 검색하는 데 주로 사용됩니다.
보이어-무어 알고리즘의 성능은 다음과 같습니다(여기서 N은 탐색할 대상의 크기, M은 그 안에서 찾으려는 패턴의 크기를 의미합니다.)
- 패턴을 찾지 못한 경우: 최악의 복잡도는 O(N+M)
- 패턴을 찾은 경우: 최악의 복잡도는 O(NM)
각각에 대한 최악의 복잡도는 이론적으로 위와 같습니다. 실전에서 이런 특수 검색 알고리즘을 사용해보면 O(N)보다 뛰어난 준선형(sublinear) 시간이 나옵니다. 다시 말해 기본 탐색 알고리즘보다 훨씬 빠릅니다. 이렇게 준선형 시간에 실행할 수 있는 이유는 탐색 범위에 있는 문자를 모두 검사하지 않고 중간에 건너뛸 수 있기 때문입니다. 또한 탐색할 패턴이 길수록 성능이 높아지는데, 이는 탐색 대상에서 건너뛸 문자가 많아지기 때문입니다. 보이어-무어와 달리 보이어-무어-호스풀 알고리즘은 초기화와 루프를 한 바퀴 도는 데 걸리는 오버헤드가 적습니다. 하지만 최악의 복잡도는 보이어-무어 알고리즘보다 훨씬 큽니다. 따라서 둘 중 어느 것을 적용할 지는 주어진 작업의 성격에 맞게 판단합니다.
보이어-무어 탐색 알고리즘을 사용하는 예는 다음과 같습니다.
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
int main()
{
std::string text{ "This is the haystack to search a needle in." };
std::string toSearchFor{ "needle" };
std::boyer_moore_searcher searcher{ toSearchFor.cbegin(), toSearchFor.cend() };
auto result{ std::search(text.cbegin(), text.cend(), searcher) };
if (result != text.cend()) {
std::cout << "Found the needle.\n";
}
else {
std::cout << "Needle not found.\n";
}
}
1.3 Comparison Algorithms
주어진 범위의 원소를 비교할때 equal(), mismatch(), lexicographical_compare()라는 세 가지 알고리즘 중 하나를 적용할 수 있습니다. C++20에서는 lexicographical_compare_three_way()라는 알고리즘이 추가되었습니다. 이 알고리즘들은 비교할 범위가 속한 컨테이너가 달라도 적용할 수 있다는 장점이 있습니다. 예를 들어 vector에 있는 원소와 list의 원소를 비교할 수 있습니다. 일반적으로 비교 알고리즘은 순차 컨테이너에 적용할 때 성능이 가장 뛰어나며, 각 컬렉션에서 동일한 위치에 있는 값끼리 비교하는 방식으로 실행됩니다.
각 알고리즘의 동작 방식은 다음과 같습니다.
- equal() : 주어진 원소가 모두 같으면 true를 리턴합니다. 기존에 equal()은 3가지 이터레이터(첫 번째 범위의 begin과 end, 두 번째 범위의 begin)만 인수로 받을 수 있었습니다. 이 버전은 비교할 범위의 원소 개수가 일치해야 합니다. C++14부터는 4가지 이터레이터(첫 번째 범위의 begin과 end, 두 번째 범위의 begin과 end)를 받도록 오버로딩된 버전이 추가되었습니다. 이 버전은 서로 크기가 다른 범위를 비교할 수 있습니다. 4가지 이터레이터를 받는 버전이 훨씬 안전하기 때문에 항상 이 버전을 사용하는 것이 좋습니다.
- mismatch() : 주어진 범위에서 일치하지 않는 범위를 가리키는 이터레이터를 리턴합니다. equal()과 마찬가지로 3가지 이터레이터를 받는 버전과 4가지 이터레이터를 받는 버전이 있습니다. mismatch()도 마찬가지로 4가지 이터레이터를 받는 버전이 훨씬 안전하므로 이 버전을 사용하는 것이 좋습니다.
- lexicographical_compare() : 첫 번째로 일치하지 않는 양쪽 범위의 원소 중에서 첫 번째 범위의 원소가 두 번째 범위의 원소보다 작거나, 첫 번째 범위의 원소 수가 두 번째 원소 수보다 적으면서 첫 번째 범위의 원소가 모두 두 번째 범위의 앞부분과 일치하면 true를 리턴합니다. lexicographical_compare란이름이 붙은 이유는 문자열을 나열하는 방식이 사전과 비슷하기 때문입니다. 이 알고리즘은 모든 타입의 객체를 다룰 수 있도록 규칙을 확장했습니다.
- lexicographical_compare_three_way() : lexicographical_compare()과 유사하지만, C++20의 three-way 비교(<=>)를 수행하고 boolean 대신 비교 카테고리 타입(strong_ordering, weak_ordering, partial_ordering)을 리턴합니다.
타입이 서로 다른 컨테이너 원소 두 개를 비교할 때는 equal()이나 lexicographical_compare()보다는 operator==이나 operator<를 사용하는 것이 좋습니다. 표준 라이브러리 알고리즘은 서로 타입이 다른 컨테이너의 부분 범위나 C 스타일의 배열을 비교하는 데 적합합니다.
비교 알고리즘을 사용하는 예는 다음과 같습니다.
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
template<typename Container>
void populateContainer(Container& cont)
{
int value;
while (true) {
std::cout << "Enter a number (0 to quit): ";
std::cin >> value;
if (value == 0) { break; }
cont.push_back(value);
}
}
int main()
{
std::vector<int> myVector;
std::list<int> myList;
std::cout << "Populate the vector\n";
populateContainer(myVector);
std::cout << "Populate the list\n";
populateContainer(myList);
// Compare the two containers
if (std::equal(myVector.cbegin(), myVector.cend(),
myList.cbegin(), myList.cend())) {
std::cout << "The two containers have equal elements\n";
}
else {
// If the containers were not equal, find out why not
auto miss{ std::mismatch(myVector.cbegin(), myVector.cend(),
myList.cbegin(), myList.cend()) };
std::cout << "The following initial elements are the same in "
<< "the vector and the list:\n";
for (auto i{ myVector.cbegin() }; i != miss.first; ++i) {
std::cout << *i << '\t';
}
std::cout << "\n";
}
// Now order them
if (std::lexicographical_compare(myVector.cbegin(), myVector.cend(),
myList.cbegin(), myList.cend())) {
std::cout << "The vector is lexicographically first.\n";
}
else {
std::cout << "The list is lexicographically first.\n";
}
}위 코드를 실행한 결과는 다음과 같습니다.
1.4 Counting Algorithms
불변형(non-modifying) 카운팅 알고리즘에는 all_of(), any_of(), none_of(), count(), count_if()가 있습니다.
처음 3개의 알고리즘의 사용 예제는 다음과 같습니다.
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
// all_of()
std::vector vec1{ 1,1,1,1 };
if (std::all_of(vec1.cbegin(), vec1.cend(), [](int i) { return i == 1; })) {
std::cout << "All elements are == 1\n";
}
else {
std::cout << "Not all elements are == 1\n";
}
// any_of()
std::vector vec2{ 0, 0, 1, 0 };
if (std::any_of(vec2.cbegin(), vec2.cend(), [](int i) { return i == 1; })) {
std::cout << "At least one element == 1\n";
}
else {
std::cout << "No elements are == 1\n";
}
// none_of()
std::vector vec3{ 0, 0, 0, 0 };
if (std::none_of(vec3.cbegin(), vec3.cend(), [](int i) { return i == 1; })) {
std::cout << "All elements are != 1\n";
}
else {
std::cout << "Some elements are == 1\n";
}
}위 코드의 실행 결과는 다음과 같습니다.
다음 예제 코드는 count_if() 알고리즘을 보여줍니다. 이 알고리즘은 vector에서 특정 조건을 만족하는 원소의 수를 카운트합니다. 이 조건은 다음과 같인 람다 표현식으로 주어지고 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
std::vector values{ 1,2,3,4,5,6,7,8,9 };
int value{ 3 };
auto tally{ std::count_if(values.cbegin(), values.cend(),
[value](int i) { return i > value; }) };
std::cout << "Found " << tally << " values > " << value << ".\n";
}
실행 결과는 다음과 같습니다.
다음 예제 코드는 레퍼런스로 캡처된 변수에 대해 설명하고 있습니다. 아래 코드에서람다 표현식은 레퍼런스로캡처된 변수를 호출될 때마다 증가시켜 몇 번 호출되었는지 카운트합니다.
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
std::vector values{ 1,2,3,4,5,6,7,8,9 };
int value{ 3 };
int callCounter{ 0 };
auto tally{ std::count_if(values.cbegin(), values.cend(),
[value, &callCounter](int i) { callCounter++; return i > value; }) };
std::cout << "The lambda expression was called " << callCounter << " times.\n";
std::cout << "Found " << tally << " values > " << value << ".\n";
}
2. Modifying Sequence Algorithms
표준 라이브러리는 가변형 순차 알고리즘(modifying sequence algorithms)도 다양하게 제공합니다. 예를 들어 한 범위에 있는 원소를 다른 범위로 복사하거나, 원소를 삭제하거나, 주어진 범위의 원소 순서를 반대로 바꾸는 것도 있습니다.
가변형 알고리즘 중 일부는 원본(source)와 대상(destination)의 범위를 모두 지정합니다. 그래서 원본 범위에 있는 원소를 읽어서 변경한 내용을 대상 범위에 저장합니다. copy()가 이 예에 해당합니다.
나머지 알고리즘들은 주어진 범위에서 곧바로 수정합니다(in place). 그래서 범위를 하나만 지정해주어도 됩니다. generate()가 이 예에 속합니다.
가변형 알고리즘은 대상 범위에 원소를 추가하는 작업은 할 수 없습니다. 대상 범위에 있는 원소를 수정하거나 덮어쓸 수만 있습니다. 반복자 어댑터(iterator adaptor)를 사용하면 대상 범위에 원소를 추가하게 만들 수 있습니다.
가변형 알고리즘의 대상 범위를 map과 multimap의 범위로 지정할 수 없습니다. 가변형 알고리즘에 map을 적용하면 키/값 쌍으로 구성된 원소를 모두 덮어쓰기 때문입니다. 그런데 map과 multimap은 키를 const로 지정하기 때문에 다른 값을 대입할 수 없습니다. set과 multiset도 마찬가지입니다. 따라서 map이나 set류의 컨테이너에 가변형 알고리즘을 적용하려면 insert iterator로 처리해야 합니다.
interator adaptor(or insert iterator)에 대한 내용은 지난 포스팅에서 다룬 적이 있습니다. 필요하시다면 참조바랍니다 !
2.1 generate
generate() 알고리즘은 이터레이터 범위를 인수로 받아서 그 범위에 있는 값을 세 번째 인수로 지정한 함수의 리턴 값으로 교체합니다. 다음 코드에서는 generate() 알고리즘에 람다 표현식을 이용하여 2, 4, 8, 16 등과 같은 값을 vector에 넣도록 구현했습니다.
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
std::vector<int> values(10);
int value{ 1 };
std::generate(values.begin(), values.end(), [&value] { value *= 2; return value; });
for (const auto& i : values) { std::cout << i << " "; }
}위 코드는 "2 4 8 16 32 64 128 256 512 1024"를 출력합니다.
2.2 transform
transform()에는 여러 가지 오버로드된 버전이 있습니다. 첫 번째 버전은 주어진 범위에 있는 모든 원소마다 콜백을 적용해서 새 원소를 생성합니다. 이렇게 생성된 원소는 인수로 지정한 대상 범위에 저장됩니다. 원본과 대상 범위를 똑같이 지정하면 그 범위 안에 담긴 원소를 그 원소에 대해 콜백을 호출한 결과로 대체할 수 있습니다. 이때 원본 범위의 시작과 끝 이터레이터, 대상 범위의 시작 이터레이터, 콜백을 매개변수로 지정합니다.
예를 들어, vector의 모든 원소에 100씩 더하려면 다음과 같이 작성하면 됩니다.
int main()
{
std::vector<int> myVector;
populateContainer(myVector);
std::cout << "The vector contains:\n";
for (const auto& i : myVector) { std::cout << i << " "; }
std::cout << "\n";
std::transform(myVector.begin(), myVector.end(), myVector.begin(),
[](int i) { return i + 100; });
std::cout << "The vector contains:\n";
for (const auto& i : myVector) { std::cout << i << " "; }
}
transform()의 또 다른 버전은 주어진 범위의 원소 쌍에 대해 이항 함수(binary function)를 호출합니다. 그래서 첫 번째 범위에 대한 시작과 끝 이터레이터, 두 번째 범위에 대한 시작 이터레이터, 대상 범위에 대한 시작 이터레이터를 인수로 지정해야 합니다.
이번 예제는 vector를 두 개 생성해서 transform()으로 두 vector에서 같은 위치의 원소끼리 더한 결과를 첫 번째 vector에 저장하는 방법을 보여줍니다.
int main()
{
std::vector<int> vec1, vec2;
std::cout << "Vector1:\n"; populateContainer(vec1);
std::cout << "Vector2:\n"; populateContainer(vec2);
if (vec2.size() < vec1.size()) {
std::cout << "Vector2 should be at least the same size as Vector1.\n";
return 1;
}
// Create a lambda to print the contents of a container
auto printContainer{ [](const auto& container) {
for (auto& i : container) { std::cout << i << " "; }
std::cout << "\n";
} };
std::cout << "Vector1: "; printContainer(vec1);
std::cout << "Vector2; "; printContainer(vec2);
std::transform(vec1.begin(), vec1.end(), vec2.begin(), vec1.begin(),
[](int a, int b) { return a + b; });
std::cout << "Vector1: "; printContainer(vec1);
std::cout << "Vector2; "; printContainer(vec2);
}위 코드의 실행 결과는 다음과 같습니다.
transform()을 비롯한 가변형 알고리즘 중에는 대상 범위의 마지막 바로 다음 번째 항목을 가리키는 반복자를 리턴하는 것이 많습니다. 여기서는 대부분 리턴값을 무시합니다.
2.3 copy
copy() 알고리즘은 한 범위의 원소를 다른 범위로 복사합니다. 이때 주어진 범위의 첫 번째 원소부터 시작해서 마지막 원소까지 순차적으로 처리합니다. 원본과 대상의 범위는 반드시 달라야 하지만 일정한 제약을 만족한다면(예를 들어 copy(b, e, d)에서 d가 b보다 앞에 나온다면) 중첩되어도 됩니다. 하지만 d가 [b, e) 범위 안에 있으면 어떤 결과가 나올지 알 수 없습니다. 다른 가변형 알고리즘과 마찬가지로 copy()도 대상 범위에 추가할 수 없습니다. 기존에 있던 원소를 그냥 덮어쓰기만 하며, iterator adaptor를 사용하면 원소를 추가할 수 있습니다.
아래 예제 코드는 copy()를 사용하는 간단한 방법을 보여줍니다. 여기서 copy()는 대상 컨테이너에 공간이 충분한지 확인하는 작업을 vector의 resize() 메소드로 처리합니다. 그런 다음 vec1의 원소를 모두 vec2로 복사합니다.
int main()
{
std::vector<int> vec1, vec2;
populateContainer(vec1);
vec2.resize(vec1.size());
std::copy(vec1.cbegin(), vec1.cend(), vec2.begin());
for (const auto& i : vec2) { std::cout << i << " "; }
}
copy_backward()라는 알고리즘도 제공합니다. 이 알고리즘은 원본의 마지막 원소부터 시작 원소 순으로 복사합니다. 다시 말해 원본의 마지막 원소를 복사해서 대상의 마지막 원소에 저장하고, 그다음에는 마지막 바로 전 원소를 처리하는 식으로 거슬러 올라가며 복사합니다. copy_backward()도 원본과 대상 범위가 서로 달라야하며, 일정한 제약 조건을 만족하면 중첩해도 됩니다. 제약 조건도 copy()와 비슷합니다. copy_backward(b,e,d)가 있을 때 d가 e보다 뒤에 나오면 중첩해도 됩니다. 하지만 d가 (b, e]에 포함될 때는 결과를 예측할 수 없습니다. 방금 살펴본 예제에서 copy()가 아닌 copy_backward()로 복사하도록 수정하면 다음과 같습니다. 여기서 세 번째 인수를 vec2.begin()이 아닌 vec2.end()로 지정했습니다.
std::copy_backward(vec1.cbegin(), vec1.cend(), vec2.end());결과는 동일합니다.
copy_if() 알고리즘은 이터레이터 두 개로 지정한 입력 범위, 이터레이터 하나로 지정한 출력 대상 범위, 그리고 predicate를 인수로 받아 처리합니다. 이 알고리즘은 지정한 predicate를 만족하는 원소를 모두 대상 범위로 복사합니다. 단 복사 과정에서 컨테이너를 생성하거나 확장하지는 않습니다. 기존 원소를 바꾸기만 합니다. 따라서 대상 범위는 복사할 원소를 모두 담을 수 있도록 충분히 커야 합니다. 물론 원소를 복사한 뒤, 마지막 원소를 복사한 지점 이후의 공간을 삭제하는 것이 좋습니다. 이를 위해 copy_if()는 대상 범위에 마지막으로 복사한 원소의 바로 다음 지점을 가리키는 이터레이터를 리턴합니다. 다음 코드는 짝수만 vec2로 복사하는 예를 보여줍니다.
int main()
{
std::vector<int> vec1, vec2;
populateContainer(vec1);
vec2.resize(vec1.size());
auto endIterator{ std::copy_if(vec1.cbegin(), vec1.cend(), vec2.begin(),
[](int i) { return i % 2 == 0; }) };
vec2.erase(endIterator, vec2.end());
for (const auto& i : vec2) { std::cout << i << " "; }
}
copy_n() 알고리즘은 원본에서 n개의 원소를 대상으로 복사합니다. copy_n()의 첫 번째 매개변수는 시작 이터레이터, 두 번째 매개변수는 복사할 원소 수를 지정하는 정수, 세 번째 매개변수는 대상 이터레이터입니다. copy_n() 알고리즘은 경계값 검사를 하지 않습니다. 따라서 시작 이터레이터부터 원소의 수만큼 위치를 하나씩 증가사면서 복사해도 end()를 초과하지 않도록 검사하는 코드는 직접 작성해야 합니다. 그렇지 않으면 예상치 못한 결과가 나올 수 있습니다.
예를 들면 다음과 같습니다.
int main()
{
std::vector<int> vec1, vec2;
populateContainer(vec1);
size_t tally{ 0 };
std::cout << "Enter number of element you want to copy: ";
std::cin >> tally;
tally = std::min(tally, vec1.size());
vec2.resize(tally);
std::copy_n(vec1.cbegin(), tally, vec2.begin());
for (const auto& i : vec2) { std::cout << i << " "; }
}
2.4 move
표준 라이브러리는 move()와 move_backward()라는 두 가지 이동 알고리즘을 제공합니다. 이 두 알고리즘은 이동 의미론을 적용합니다. 따라서 이 알고리즘을 적용할 컨테이너의 원소 타입을 직접 정의하려면 원소 타입에 대한 클래스에 반드시 이동 대입 연산자를 구현해야 합니다. 구체적인 방법은 다음에 소개하는 코드와 같습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
class MyClass
{
public:
MyClass() = default;
MyClass(const MyClass& src) = default;
MyClass(std::string str) : m_str{ std::move(str) } {}
virtual ~MyClass() = default;
// Move assignment operator
MyClass& operator=(MyClass&& rhs) noexcept {
if (this == &rhs) { return *this; }
m_str = std::move(rhs.m_str);
std::cout << "Move operator= (m_str=" << m_str << ")\n";
return *this;
}
void setString(std::string str) { m_str = std::move(str); }
const std::string& getString() const { return m_str; }
private:
std::string m_str;
};
int main()
{
std::vector<MyClass> vecSrc{ MyClass{"a"}, MyClass{"b"}, MyClass{"c"} };
std::vector<MyClass> vecDst(vecSrc.size());
std::move(vecSrc.begin(), vecSrc.end(), vecDst.begin());
for (const auto& c : vecDst) { std::cout << c.getString() << " "; }
}위 코드를 실행한 결과는 다음과 같습니다.
move_backward() 알고리즘의 동작도 move()와 비슷합니다. 단, 마지막 원소부터 첫 번째 원소 순으로 원소를 이동시킨다는 점만 다릅니다. move()와 move_backward()도 모두 일정 조건만 만족한다면 원본과 대상으 범위가 겹쳐도 됩니다. 이 조건은 copy()와 copy_backward()의 조건과 동일합니다.
2.5 replace
replace()와 replace_if() 알고리즘은 주어진 범위에서 값이나 predicate로 지정한 조건에 일치하는 원소를 새로운 값으로 교체합니다. 예를 들어 place_if()는 첫 번째와 두 번째 매개변수로 컨테이너의 원소 범위를 지정합니다. 세 번째 매개변수는 true나 false를 리턴하는 함수나 람다 표현식입니다. 여기서 true가 리턴되면 컨테이너의 값을 네 번째 매개변수로 지정한 값으로 교체하고 false가 리턴되면 원래대로 놔둡니다.
다음 예제 코드는 컨테이너에서 홀수 값을 가진 원소를 모두 0으로 교체합니다.
int main()
{
std::vector<int> vec;
populateContainer(vec);
std::replace_if(vec.begin(), vec.end(), [](int i) {return i % 2 != 0; }, 0);
for (const auto& i : vec) { std::cout << i << " "; }
}
replace()와 replace_if()를 각각 변형한 replace_copy()와 replace_copy_if()도 있습니다. 이 알고리즘은 다른 대상 범위에 교체 결과를 복사합니다.
2.6 remove
주어진 범위에서 특정한 조건을 만족하는 원소를 삭제하는 경우를 생각해보겠습니다. 한 가지 방법은 표준 라이브러리 문서에 현재 컨테이너가 erase() 메소드를 제공한다고 나와 있다면모든 원소에 대해 반복문을 돌면서 조건에 일치하는 원소에 대해 erase()를 호출하는 것입니다. erase() 메소드를 제공하는 컨테이너 중에는 vector가 있습니다. 하지만 vector 컨테이너를 이렇게 처리하면 굉장히 비효율적입니다. vector에서 메모리를 연속적으로 사용하기 위해 메모리 연산이 상당히 발생하기 때문에 O(n^2)의 성능이 나옵니다. 게다가 에러를 발생하기도 쉽습니다.
예를 들어 vector에 담긴 string 원소 중에서 공백 string을 제거하는 함수를 다음과 같이 표준 라이브러리 알고리즘을 사용하지 않고 구현한 경우를 살펴보겠습니다. 이때 for문 안에서 iter를 굉장히 주의깊게 다루어야 합니다.
void removeEmptyStringsWithoutAlgorithms(std::vector<std::string>& strings)
{
for (auto iter{ strings.begin() }; iter != strings.end(); ) {
if (iter->empty()) {
iter = strings.erase(iter);
}
else {
iter++;
}
}
}이렇게 구현하면 성능이 상당히 떨어지기 때문에 바람직하지 않습니다. 이 문제는 소위 remove-erase 패턴으로 구현하는 것이 좋습니다. 그러면 선형 시간에 처리할 수 있습니다.
표준 라이브러리 알고리즘은 컨테이너를 다룰 때 이터레이터 인터페이스로만 접근합니다. 그래서 remove() 알고리즘은 컨테이너에서 원소를 직접 삭제하지 않고, 주어진 값이나 predicate를 만족하는 원소를 그렇지 않은 원소와 교체합니다. 이 작업은 이동 대입 연산으로 처리합니다. 그러면 주어진 범위가 두 집합으로 분할됩니다. 하나는 그대로 유지할 원소 집합이고, 다른 하나는 삭제할 원소 집합입니다. remove()는 삭제할 범위의 첫 번째 원소를 가리키는 반복자를 리턴합니다. 이 원소를 컨테이너에서 실제로 살제하려면 먼저 remove() 알고리즘부터 적용한 뒤 리턴된 반복자를 이용하여 컨테이너에 대해 erase()를 호출해서 반복자가 가리키는 원소들을 모두 지웁니다. 이것이 바로 remove-erase 패턴입니다.
예를 들어, 다음 함수를 살펴보겠습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
void removeEmptyStrings(std::vector<std::string>& strings)
{
auto it{ std::remove_if(strings.begin(), strings.end(),
[](const std::string& str) { return str.empty(); }) };
// erase the removed elements
strings.erase(it, strings.end());
}
int main()
{
std::vector<std::string> myVector{ "", "one", "", "two", "three", "four" };
for (auto& str : myVector) { std::cout << "\"" << str << "\" "; }
std::cout << "\n";
removeEmptyStrings(myVector);
for (auto& str : myVector) { std::cout << "\"" << str << "\" "; }
std::cout << "\n";
}위 코드를 실행한 결과는 다음과 같습니다.
remove()와 remove_if()를 변형한 remove_copy()와 remove_copy_if()란 알고리즘도 있습니다. 이 알고리즘은 원본 범위를 변경하지 않고, 원소를 모두다른 대상 범위에 복사합니다.
2.7 erase (C++20)
C++20에서는 erase()와 erase_if()를 모든 표준 라이브러리 컨테이너에 대해 지원합니다. 공식적으로 이 연산은 uniform container erasure이라고 합니다. erase() 함수는 컨테이너에서 주어진 값과 일치하는 모든 원소들을 삭제하고, erase_if()는 주어진 predicate에 일치하는 모든 원소를 삭제합니다. 이 알고리즘은 이터레이터 범위가 아닌 컨테이너의 레퍼런스를 매개변수로 받습니다. C++20부터는 컨테이너로부터 원소를 삭제하기 위해서 이 함수들을 사용하는 것을 권장합니다.
예를 들어, 위에서 살펴본 removeEmptyString() 함수를 erase_if()를 사용하여 다음과 같이 간단하게 작성할 수 있습니다.
void removeEmptyStrings(std::vector<std::string>& strings)
{
std::erase_if(strings, [](const std::string& str) { return str.empty(); });
}
int main()
{
std::vector<std::string> myVector{ "", "one", "", "two", "three", "four" };
for (auto& str : myVector) { std::cout << "\"" << str << "\" "; }
std::cout << "\n";
removeEmptyStrings(myVector);
for (auto& str : myVector) { std::cout << "\"" << str << "\" "; }
std::cout << "\n";
}결과는 remove-erase 패턴과 동일합니다.
2.8 unique
unique() 알고리즘은 remove()의 특수한 버전으로, 같은 원소가 연달아 나오는 부분을 모두 삭제합니다. list 컨테이너의 경우에는 unique()라는 메소드를 통해 이 알고리즘과 똑같은 기능을 제공합니다. unique()는 주로 정렬 컨테이너에 대해 사용하지만, 비정렬 컨테이너에도 적용할 수 있습니다.
unique()의 기본 버전은 in-place로 동작하지만, 대상 범위에 결과를 복사하는 unique_copy()도 있습니다.
예를 들면, 다음과 같이 사용할 수 있습니다. 이 함수는 현재 대학에 등록된 모든 학생을 각 과정에 따라 묶어서 리스트로 출력합니다. 이때 학생 이름에 대한 list를 담은 vector와 등록금을 내지 않아서 등록이 취소된 학생에 대한 list를 인수로받는 메소드를 사용합니다. 이 메소드는 소속에 관계없이 모든 학생을 빠짐없이 담은 list를 생성합니다. 물론 학생이 중복되면 안되고, 한 학생이 여러 과정에 속할 수는 있습니다.
std::list<std::string> getTotalEnrollment(const std::vector<std::list<std::string>>& courseStudents,
const std::list<std::string>& droppedStudents)
{
std::list<std::string> allStudents;
// 각 과정에 대한 리스트를 모두 마스터 리스트에 합침
for (auto& lst : courseStudents) {
allStudents.insert(allStudents.end(), lst.cbegin(), lst.cend());
}
// 리스트 정렬
allStudents.sort();
// 중복 제거
allStudents.unique();
// 등록 취소된 학생 제거
for (auto& str : droppedStudents) {
allStudents.remove(str);
}
return allStudents;
}
2.9 shuffle
shuffle() 알고리즘은 주어진 범위의 원소를 무작위 순으로 재정렬하며 성능은 선형 시간입니다. 이 알고리즘은 카드를 섞는 것과 같은 작업에 유용합니다. shuffle()은 재정렬할 범위를 나타내는 begin/end 이터레이터, 무작위수를 생성하는 방법을 지정하는 uniform random number generator를 인수로 받습니다. 무작위수를 생성하는 제너레이터는 다른 포스팅에서 다루어 보도록 하고, 여기서 자세한 설명은 생략하겠습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
int main()
{
std::vector values{ 1,2,3,4,5,6,7,8,9,10 };
std::random_device seeder;
const auto seed{ seeder.entropy() ? seeder() : time(nullptr) };
std::default_random_engine engine{
static_cast<std::default_random_engine::result_type>(seed) };
for (int i = 0; i < 6; i++) {
std::shuffle(values.begin(), values.end(), engine);
for (const auto& value : values) { std::cout << value << " "; }
std::cout << "\n";
}
}실행 결과는 다음과 같습니다.
2.10 sample
sample() 알고리즘은 인수로 지정한 원본 범위에서 무작위로 n개의 원소를 골라서 리턴하고, 이를 대상 범위에 저장합니다. 이 알고리즘은 다섯 개의 매개변수를 받습니다.
- 샘플링할 범위를 나타내는 begin과 end 이터레이터
- 무작위로 고른 원소를 저장할 대상 범위의 begin 이터레이터
- 고를 원소의 수
- 무작위수 생성 엔진(random number generation engine)
예를 들면, 다음과 같습니다. 무작위수 제너레이터에 대한 설명은 생략합니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
int main()
{
std::vector values{ 1,2,3,4,5,6,7,8,9,10 };
const size_t numberOfSamples{ 5 };
std::vector<int> samples(numberOfSamples);
std::random_device seeder;
const auto seed{ seeder.entropy() ? seeder() : time(nullptr) };
std::default_random_engine engine{
static_cast<std::default_random_engine::result_type>(seed) };
for (int i = 0; i < 6; i++) {
std::sample(values.cbegin(), values.cend(), samples.begin(), numberOfSamples, engine);
for (const auto& sample : samples) { std::cout << sample << " "; }
std::cout << "\n";
}
}실행 결과는 다음과 같습니다.
2.11 reverse
reverse() 알고리즘은 주어진 범위에 있는 원소의 순서를 반대로 바꿉니다. 범위의 첫 번째 원소를 마지막 원소와 바꾸고, 두 번째 원소를 끝에서 두 번째 원소와 바꾸는 식으로 진행합니다.
reverse()의 기본 버전은 원본을 바로 수정하며 범위를 표현하는 begin 이터레이터와 end 이터레이터를 인수로 받습니다. 이와 달리 reverse_copy()는 결과를 대상 범위에 복사하며, 원본 범위에 대한 begin과 end 이터레이터와 대상 범위에 대한 begin 이터레이터를 인수로 받습니다. 여기서 대상 범위는 반드시 새 원소를 담을 만큼 공간이 충분해야 합니다.
reverse()를 사용하는 예제 코드는 다음과 같습니다.
int main()
{
std::vector<int> values;
populateContainer(values);
std::reverse(values.begin(), values.end());
for (const auto& i : values) { std::cout << i << " "; }
}실행 결과는 다음과 같습니다.
다음 포스팅에 이어서 연산, 분할, 정렬, 집합 등 여러 알고리즘들을 추가로 알아보도록 하겠습니다 !
'프로그래밍 > C & C++' 카테고리의 다른 글
| [C++] String Localization (0) | 2022.02.27 |
|---|---|
| [C++] 알고리즘 (Algorithms) (3) (0) | 2022.02.26 |
| [C++] 알고리즘 (Algorithms) (1) (0) | 2022.02.26 |
| [C++] 템플릿 (Templates) (0) | 2022.02.24 |
| [C/C++] 가변 인자 리스트 (0) | 2022.02.23 |
댓글