[전문가를 위한 C++] 표준 라이브러리 알고리즘 완전 정복

‘전문가를 위한 C++ - Marc Gregoire 지음, 남기혁 옮김’ 책을 참고하여 작성한 포스트입니다.

---

표준 라이브러리는 거의 모든 컨테이너에 적용 가능한 제네릭 알고리즘을 다양하게 제공한다.
모든 작업을 반복자 인터페이스만으로 처리한다.
각 원소의 타입뿐만 아니라 컨테이너 타입에도 독립적이다.

---

알고리즘 개요

• 표준 라이브러리 알고리즘의 강력함은 컨테이너를 직접 다루지 않고 반복자라는 매개체로 작동하는 데 있다. 특정 컨테이너에 종속되지 않는다.
• 모두 함수 템플릿으로 구현되었고, 템플릿 타입 매개변수도 대부분 반복자이다.
• 반복자 자체는 함수의 인수로 지정하고, 함수 템플릿은 전달된 인수를 보고 템플릿 타입을 유추하기 때문에 알고리즘이 템플릿이 아닌 일반 함수인 것처럼 호출 가능하다.
• 반복자가 알고리즘의 요건에 맞아야 한다.
• 대부분 <algorithm>에 정의되어 있음. 일부 수치 관련은 <numeric>에 정의되어 있음. 모두 std 네임스페이스에 속해 있음
• c++20 부터는 대부분의 알고리즘이 constexpr 이다.
• 제네릭 알고리즘과 동일한 기능을 제공하는 메서드가 컨테이너에 있다면 컨테이너 메서드를 사용하는 것이 좋다.
• 예를 들어 map의 경우 제네릭 알고리즘인 find()는 선형 시간인 반면, map에서 제공하는 find()는 로그 시간에 수행한다.

find(), find_if()

find()

• 주어진 반복자 범위 내에서 특정한 원소를 찾는다. 모든 컨테이너에 사용 가능
• 원소를 찾으면 그 원소를 참조하는 반복자르 리턴하고, 그렇지 않으면 주어진 반복자 범위의 끝 반복자를 리턴함.

find_if()

• 인수로 predicate function callback을 받는다. predicate은 true나 false를 리턴하며, 지정한 범위 안에 있는 원소에 대해 predicate가 true를 리턴할 때까지 계속 호출한다.
• true를 리턴하면 그 원소를 가리키는 반복자를 리턴함

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool PerfectScore(int Num) { return (Num >= 5); }

int main()
{
	vector<int> MyVector {1, 2, 3, 4, 5};
	int NumberToFind = 3;
	if(auto iter = find(cbegin(MyVector), cend(MyVector), NumberToFind); iter == cend(MyVector))
	{
		cout << "Could not find " << NumberToFind << endl;
	}
	else 
	{
		cout << *iter <<" " << NumberToFind << endl;
	}

	auto iter2 = find_if(cbegin(MyVector), cend(MyVector), PerfectScore);
	auto iter3 = find_if(cbegin(MyVector), cend(MyVector), [](int i) -> bool {return i >= 5;});

	cout << "iter 2 = " << *iter2 << endl;
	cout << "iter 3 = " << *iter3 << endl;
}

/* 출력결과
3 3
iter 2 = 5
iter 3 = 5
*/

accumulate()

• <numeric> 에 정의되어 있음
• 디폴트는 컨테이너에 있는 원소들을 모두 더한 값을 리턴한다.
• 세번째 인수로 초깃값을 받는다.
• 네번째 인수로 이진(인수가 두개) 콜백함수(binary callback)를 넣으면 다른 사칙 연산 수행이 가능하다.

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int ArithmeticSum(const vector<int> values)
{
	int sum = accumulate(cbegin(values), cend(values), 0);
	return sum;
}

int Product(int value1, int value2) { return value1 * value2 ;}

int ArithmeticProduct(const vector<int> values)
{
	int mult = accumulate(cbegin(values), cend(values), 1, Product);
	// 투명 multiplies 함수 객체 이용
	int mult2 = accumulate(
		cbegin(values), cend(values), 1,
		multiplies<>{}
	);

	return mult2;
}

int main()
{
	vector<int> MyVector {1, 2, 3, 4, 5};
	cout << ArithmeticSum(MyVector) << endl;
	cout << ArithmeticProduct(MyVector) << endl;
}

/* 출력결과
15
120
*/

알고리즘과 의미 이동론

• 표준 라이브러리 컨테이너와 마찬가지로 알고리즘도 필요에 따라 이동 의미론 적용해 최적화 가능하다.

알고리즘 콜백(나중에 내용 추가)

• 펑터나 람다 표현식 등으로 주어진 콜백에 대해 복제본을 여럿 만들어 다양한 원소에 대해 별도 호출 가능하다.
• 기본적으로 콜백은 상태가 없어야 한다.
• 콜백이 알고리즘에 의해 복제되지 않게 하려면 std::ref() 헬퍼 함수를 이용해 콜백 레퍼런스를 전달하면 된다.

---

표준 라이브러리 알고리즘 심층 분석

불변형 순차 알고리즘(non-modifying sequence algorithm)

• 주어진 범위에서 원소 검색하거나 두 범위를 서로 비교하는 함수

탐색 알고리즘(searching algorithm)

• 표준 라이브러리 알고리즘은 모두 operator== 나 operator<를 이폴트 연산자로 사용한다.
• 콜백을 직접 지정할 수 있는 오버로딩 버전을 제공한다.

특수 탐색 알고리즘

• c++17 부터 search() 알고리즘에 원하는 탐색 알고리즘을 옵션으로 지정할 수 있도록 매개변수가 추가 되었다.
• 크게 default_searcher, boyer_moore_searcher, boyer_moore_horspool_searcher 가 있다.
• 모두 <functional>에 정의되어 있다.
• 두, 세번째는 방대한 텍스트에서 부분 문자열을 검색하는 데 유용하다.

비교 알고리즘

• equal(), mismatch(), lexicographical_compare(), lexicographical_compare_three_way()(c++20) 이 있다
• 컨테이너가 달라도 적용 가능한 장점이 있다. vector와 list 비교 가능
• 순차 컨테이너에 적용할 때 성능이 가장 뛰어나며, 각 컨테이너에서 동일한 위치에 있는 값끼리 비교하는 방식으로 실행된다.
  • equal()
    • 주어진 원소가 모두 같으면 true
    • 첫 번째 범위의 시작, 끝 반복자, 두 번째 범위의 시작, 끝 반복자 총 네개의 인수
  • mismatch()
    • 주어진 범위에서 일치하지 않는 범위를 가리키는 반복자를 리턴
    • 네개의 인수 버전 사용하는 것이 좋음
  • lexicographical_compare()
    • 제공된 두 범위에서 동일한 위치에 있는 원소를 순차적으로 서로 비교한다.
    • 첫 번째로 일치하지 않는 양쪽 범위의 원소 중 첫 번째 범위의 원소가 두 번쨰 범위의 원소보다 작거나,
    • 첫 번째 범위의 원소 개수가 두 번째 범위의 원소 개수보다 적으면서 첫 번째 범위의 원소가 모두 두 번째 범위의 앞부분과 일치하면 true 반환
    • 사전식이라 생각하면 됨
  • lexicographical_compare_three_way()
    • 3방향 비교 연산 사용.
    • 부울 타입대신 비교 카테고리 타입 리턴

집계 알고리즘

• 불변형 집계 알고리즘에는 all_of(), any_of(), none_of(), count(), count_if() 가 있다.

예시 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>

using namespace std;

int main()
{
	vector<int> MyVector { 1, 2, 5, 4, 4, 3};
	auto BeginIter = cbegin(MyVector);
	auto EndIter = cend(MyVector);

	// 람다 표현식을 만족하지 않는 첫 번째 원소를 찾음
	auto Iter1 = find_if_not(BeginIter, EndIter,
		[](int i){return i<5;});
	if (Iter1 != EndIter) cout << "find_if_not - number < 5 : " << *Iter1 << endl;
	// 같은 값이 연속된 첫 번째 원소 쌍을 찾음
	auto Iter2 = adjacent_find(BeginIter, EndIter);
	if (Iter2 != EndIter)  cout << "not consecutive equal elements : " << *Iter2 << endl;
	// 두 값 중 첫 번째 값을 찾음
	vector<int> Targets {4, 5};
	auto Iter3 = find_first_of(BeginIter, EndIter, cbegin(Targets), cend(Targets));
	if (Iter3 != EndIter) cout << "Found number of Targets at MyVector : " << *Iter3 << endl;
	// 첫 번째 부분열을 찾음
	vector Sub {2, 5};
	auto Iter4 = search(BeginIter, EndIter, cbegin(Sub), cend(Sub));
	if (Iter4 != EndIter) cout << "Found Subsequence [2, 5]"<< endl;

	// 마지막 부분열을 찾음
	auto Iter5 = search(BeginIter, EndIter, cbegin(Sub), cend(Sub));

	// 4가 두 번 연속된 첫 번째 부분열을 찾음
	auto Iter6 = search_n(BeginIter, EndIter, 2, 4);
	if (Iter6 != EndIter) cout << "Found two consecutive 4s"<< endl;

	string Text = "The sky is blue.";
	string ToSearchFor = "sky";
	boyer_moore_searcher Searcher(cbegin(ToSearchFor), cend(ToSearchFor));
	auto Result = search(cbegin(Text), cend(Text), Searcher);
	if (Result != cend(Text)) cout << "Found the 'sky'" << endl;

	vector<int> MyVector2 { 1, 1, 1, 3};
	auto BeginIter2 = cbegin(MyVector2);
	auto EndIter2 = cend(MyVector2);

	if (all_of(BeginIter2, EndIter2, [](int i){return i == 1;})) cout << " ! " << endl;
	else cout<<"the vector is not all of 1"<<endl;

	if (any_of(BeginIter2, EndIter2, [](int i){return i == 3;}))
	{
		cout << "At least one element == 3"<< endl;
	}

	if (none_of(BeginIter2, EndIter2, [](int i){return i == 4;}))
	{
		cout<< "All elements are not 4" << endl;
	}

	int Number = 2;
	int CallCounter = 0;
	auto Tally = count_if(BeginIter2, EndIter2,
		[Number, &CallCounter](int i) -> int {++CallCounter; return i < Number;});
	cout << "Found " << Tally << " numbers that less than " << Number << endl;
	cout << "The lambda expression was called " << CallCounter << " times." <<endl;
}

/* 출력 결과
find_if_not - number < 5 : 5
not consecutive equal elements : 4
Found number of Targets at MyVector : 5
Found Subsequence [2, 5]
Found two consecutive 4s
Found the 'sky'
the vector is not all of 1
At least one element == 3
All elements are not 4
Found 3 numbers that less than 2
The lambda expression was called 4 times.
*/

가변형 순차 알고리즘(modifying sequence algorithm)

• 대상 범위에 원소를 추가할 수는 없다. 수정하거나 덮어쓰기만 가능하다. 추가하려면 반복자 어댑터를 이용해야 한다.(17장)
• map, set은 키를 const로 지정하는데, 가변형 알고리즘은 키도 덮어쓰기 때문에 일반적으로 적용이 불가능하다. 적용하려면 추가 반복자(insert iteratro)로 처리해야 한다.(17장)
• 대부분 대상 범위의 마지막 바로 다음 번쨰 항목을 가리키는 반복자를 리턴한다.

generate

• 반복자 범위를 인수로 받아 그 범위에 있는 값을 세 번째 인수로 지정한 함수의 리턴값으로 교체한다.

transform

• 여러 오버로드가 있다.
  1. 주어진 범위에 있는 모든 원소마다 콜백을 적용해 새 원소를 생성 후, 인수로 지정한 대상 범위에 저장됨
  2. 주어진 원소 쌍에 대해 이항 함수를 호출해 네 번째 인수 범위에 덮어씀

copy

• 주어진 범위에 있는 원소를 다른 범위로 복제함
• 원본과 대상 범위는 반드시 달라야 한다. 일정 제약을 만족하면 중첩할 순 있다.
  • ex) copy(b, e, d) 에서 d가 b 보다 앞에 나오는 경우
• 대상 컨테이너의 공간 확인 작업을 resize() 메서드 등으로 해주면 좋다.
• copy_backward() 는 마지막 원소부터 시작 원소 순으로 복제한다. 세번째 인수는 end() 로?
• copy_if() 는 predicate도 인수로 받는다.
• copy_n() 은 원본 원소 n개를 대상으로 복제함. 경곗값 검사를 하지 않으므로 검사하는 코드를 추가해 주어야 함.

move

• 이동 의미론을 사용한다.
• 원소 타입을 직접 정의하려면 원소 타입에 대한 클래스에 반드시 이동 대입 연산자를 구현해야 한다.(9장)
• 이동 연산 수행 후 원래 담긴 모든 원소를 확실한 상태로 만들지 않았다면 사용하지 말아야 한다.
• move_backward()는 마지막 원소부터 첫 번째 원소 순으로 원소를 이동시킨다.

replace

• 주어진 범위에서 값을 새 값으로 교체한다. repalce_if 의 경우 predicate 이용
• replace_copy, repalce_copy_if 는 교체한 값을 다른 대상 범위로 복제함

erase(c++20)

• std::erase, std::erase_if 는 인자로 지정한 값이나, predicate을 만족하는 원소를 모두 제거한다.
• 반복자 범위 대신 컨테이너에 대한 레퍼런스를 사용한다.
• erase() 는 정렬 연관 비정렬 연관 컨테이너에서 사용할 수 없다. 더 성능 뛰어난 erase(key) 메서드를 갖고 있다.
• erase_if() 는 다 가능.

remove

• c++20 이 아닌 경우.. 이걸 쓰자
• erase 컨테이너 메서드를 지원하는 경우 반복문을 돌며 원하는 원소들을 삭제할 수도 있지만,
• 삭제시마다 원소의 이동이 일어나 복잡도가 제곱이다. 그리고 반복자 유지도 까다롭다.
• 이럴 때는 remove를 이용한 제거 후 삭제 패턴(remove-erase idiom)으로 구현하는 것이 좋다.
• remove()는 원소를 실제로 지우는 것이 아닌 predicate을 만족하는 원소와 이동 대입 연산으로 교체한다.
• 원소의 순서는 유지되며 유지될 원소들은 모두 주어진 범위의 앞으로 이동한다.
• 그러면 범위는 유지할 원소집합과 삭제될 원소 집합으로 나뉜다.
• 삭제될 원소 집합의 시작 반복자를 리턴하는데, 이를 이용해 erase를 호출하여 삭제하면 된다.
• 이때 당연한거지만 erase 의 두번째 인수를 지정하지 않으면 원소 하나만 삭제 된다.
• remove_copy, remove_copy_if 도 있다.

unique

• 같은 원소가 연달아 나오는 부분을 모두 삭제한다.
• 비정렬 컨테이너에도 적용 가능하대
• unique_copy 도 있다.
• 얘도 유지할 원소집합과 삭제할 원소집합 나누는 모양이다.

shuffle

• 주어진 범위의 원소를 무작위 순으로 재정렬하며 시간 복잡도는 선형이다.
• 세번째 인수로 균등 분포 무작위수 생성기를 인수로 받는다.(23장)

sample

• 원본 범위의 원소를 무작위로 n개 골라 리턴하고, 대상 범위에 저장한다.

reverse

• reverse_copy 도 있다.
• 주어진 범위에 있는 원소의 순서를 반대로 바꿈

shift(c++20)

• 주어진 범위의 원소를 새로운 위치로 이동시키는 방식으로 시프트하는 shift_left(), shift_right() 가 있다.
• 주어진 범위의 끝을 넘어서는 원소는 제거된다.
• shift_left는 새로운 범위의 끝을 가리키는 반복자를 리턴하고, shift_right는 새로운 범위의 시작점을 가리키는 반복자를 리턴한다.

예시 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	vector<int> Values(10);
	int Value = 1;
	generate(begin(Values), end(Values), [&Value](){return Value *= 2;});
	for (const auto& i : Values) cout << i << " ";
	cout << endl;
	//2 4 8 16 32 64 128 256 512 1024 

	vector<int> Values2(7); // 0 이면 에러.
	transform(begin(Values), end(Values), begin(Values2), 
		[](int i){return i + 100;});
	for (const auto& i : Values2) cout << i << " ";
	cout << endl;
	// 102 104 108 116 132 164 228 
	transform(begin(Values), end(Values), begin(Values2),
		begin(Values), [](int a, int b) {return a + b;});
	for (const auto& i : Values) cout << i << " ";
	cout << endl;
	// 104 108 116 132 164 228 356 612 1124 2148 
	for (const auto& i : Values2) cout << i << " ";
	cout << endl;
	// 102 104 108 116 132 164 228 

	Values2.resize(size(Values));
	copy(cbegin(Values), cend(Values), begin(Values2));
	for (const auto& i : Values2) cout << i << " ";
	cout << endl;
	// 104 108 116 132 164 228 356 612 1124 2148 

	vector<int> Values3(5);
	copy_backward(cbegin(Values3), cend(Values3), end(Values2));
	for (const auto& i : Values2) cout << i << " ";
	cout << endl;
	// 104 108 116 132 164 0 0 0 0 0 

	Values2.resize(10);
	auto Iter = copy_if(cbegin(Values), cend(Values), begin(Values2),
		[](int i) { return i < 500;});
	// 뒷부분은 지워주기
	Values2.erase(Iter, end(Values2));
	for (const auto& i : Values2) cout << i << " ";
	cout << endl;
	// 104 108 116 132 164 228 356 

	copy_n(cbegin(Values), 3, begin(Values3));
	for (const auto& i : Values3) cout << i << " ";
	cout << endl;
	// 104 108 116 0 0 

	move_backward(cbegin(Values3), cend(Values3), end(Values));
	for (const auto& i : Values) cout << i << " ";
	cout << endl;
	// 104 108 116 132 164 104 108 116 0 0 

	replace_if(begin(Values3), end(Values3),
		[](int i) {return  i < 105; }, 3);
	for (const auto& i : Values3) cout << i << " ";
	cout << endl;
	// 3 108 116 3 3 

	auto Iter2 = remove_if(begin(Values3), end(Values3),
		[](int i) {return i == 3;});
	Values3.erase(Iter2, end(Values3));
	for (const auto& i : Values3) cout << i << " ";
	cout << endl;
	// 108 116 

	vector<int> Values4 {1, 1, 2, 2, 3, 4};
	unique(begin(Values4), end(Values4));
	for (const auto& i : Values4) cout << i << " ";
	cout << endl;
	// 1 2 3 4 3 4 

	reverse(begin(Values4), end(Values4));
	for (const auto& i : Values4) cout << i << " ";
	cout << endl;
	// 4 3 4 3 2 1 
}

연산 알고리즘

• for_each(), for_each_n()이 있다.
• for_each()
  • 주어진 범위에 있는 원소마다 콜백 실행
• for_each_n()
  • 첫 번째 부터 n번째 원소까지 콜백 실행
• 실전에서는 for문을 사용하는 것이 낫다. 구현도 쉽고 가독성도 높음

분할 알고리즘

• parition_copy()는 원본에 있는 원소를 복제해 다른 두 대상으로 분할(partition)한다.
• 둘 중 어느 대상으로 보낼지는 predicate의 true, false 에 따라 결정된다.
• 반복자 쌍을 리턴하는데, 하나는 첫 번째 대상 범위에서 마지막으로 복제한 원소의 바로 다음 지점, 다른 하나는 두 번째 대상..
• parition() 알고리즘은 predicate에서 true를 리턴하는 원소가 false 리턴하는 함수보다 앞에 나오도록 정렬한다. 원래 순서가 유지되지 않는다.

정렬 알고리즘(sorting algorithm)

• 특정 조건을 기준으로 순서에 맞게 유지하도록 재배치한다.
• 순차 컨테이너에만 정렬 알고리즘 적용이 가능하다.
• 정렬 연관 컨테이너는 항상 정렬되어 있는 상태니 적용할 수 없고, 비정렬 연관 컨테이너도 적용할 수 없다.
• list, forward_list는 자체 정렬 메서드를 이용하는 것이 낫다.
• stable_sort()는 원본에 나온 순서를 그대로 유지한다.
• 선택 알고리즘인 nth_element() 가 있다.

이진 탐색 알고리즘

• binary_search(), lower_bound(), upper_bound(), equal_range() 등이 있다.
• map, set은 자체 메서드 제공한다.
• lower_bound()
  • 주어진 값보다 작지 않은 원소 중 첫 번째를 찾는다.
• binary_search()
  • 탐색 범위 시작, 끝 반복자, 탐색할 값, 옵션으로 비교 콜백을 인수로 받는다.
  • 찾으면 true, 없으면 false 를 반환한다.

집합 알고리즘(set algorithm)

• 모든 정렬된 범위에 적용 가능하다.
• includes()
  • 부분 집합을 판별하는 표준 함수이다.
  • 순서를 고려하지 않는다.
• set_union()
  • 합집합
• set_intersection()
  • 교집합
• set_difference()
  • 차집합
• set_symmetric_difference()
  • 대칭차집합
  • XOR 연산을 적용한 결과로 집합을 만듬
• merge()
  • 정렬된 두 범위를 하나로 합칠 수 있다.
  • 정렬 순서는 그대로 유지된다.
  • 선형 복잡도를 가진다.

최대/최소 알고리즘

• min(), max()
• operator< 또는 사용자가 정의한 이항 predicate으로 비교해서 각각 최소 원소와 최대 원소에 대한 const 레퍼런스를 리턴
• minmax()
  • 최솟값과 최댓값을 쌍으로 묶어 리턴
• 반복자로 지정한 범위에 대해 처리하려면 min_element(), max_element()를 사용해야 한다.
• std::clamp()는 주어진 값이 최솟값과 최댓값 사이에 있는지 검사해서, 최솟값 보다 작으면 최솟값에 대한 레퍼런스를 리턴하고, 최댓값보다 크면 최댓값에 대한 레퍼런스를 리턴하며, 사이에 있다면 주어진 값에 대한 레퍼런스를 리턴한다.

병렬 알고리즘(나중에 추가)

제한 버전 알고리즘(C++20) (나중에 추가)

수치 처리 알고리즘(나중에 추가)