전문가를 위한 C++/ 표준 라이브러리 알고리즘 마스터하기

Contents

(전체가 아니라 C#과 차이가 있는 부분을 중심으로 요약 정리)

표준 라이브러리는 거의 모든 컨테이너에 적용할 수 있는 제네릭 알고리즘을 다양하게 제공한다. 이러한 알고리즘을 활용하면 컨테이너에 담긴 원소를 검색하고, 정렬하고, 가공하고, 다양한 연산을 수행할 수 있다.

표준 라이브러리 알고리즘의 가장 큰 장점은 각 원소의 타입이나 컨테이너의 타입과는 독립적이라는 점이다. 게다가 모든 작업을 반복자 인터페이스만으로 처리한다.

알고리즘 개요

표준 라이브러리 알고리즘은 모두 함수 템플릿으로 구현됐으며, 여기 나온 템플릿 타입 매개변수는 반복자 타입인 경우가 많다. 반복자 자체는 이 함수에 전달된 인수로 결정한다. 함수 템플릿은 대부분 함수에 전달된 인수를 보고 템플릿 타입을 추론하기 때문에 알고리즘을 템플릿이 아닌 일반 함수처럼 호출해서 쓸 수 있다.

반복자 인수는 주로 반복자 범위 (시작과 끝의 쌍)로 표현한다. 반복자 범위를 표현할 때는 첫 번째 원소는 포함하고 마지막 원소는 제외한 반개방(half-open) 범위로 받는 컨테이너가 많다. 끝 반복자(end iterator)는 실제로 ‘마지막 바로 다음’ 항목을 가리킨다.

알고리즘에 전달할 반복자는 일정한 요건을 갖춰야 한다. 예컨대 copy_backward()는 양방향 반복자를 지정해야 하며, stable_sort()는 랜덤 액세스 반복자를 지정해야 한다. 다시 말해 이런 알고리즘은 요건을 갖추지 못한 반복자를 가진 컨테이너에 대해서는 작동하지 않는다..

(이하 설명 생략)

find()와 find_if() 알고리즘

find()는 주어진 반복자 범위에서 특정한 원소를 검색한다. 이 알고리즘은 모든 종류의 컨테이너 원소를 찾을 때 활용할 수 있다. find()는 원소를 찾으면 그 원소를 참조하는 반복자를 리턴하고, 원소를 찾지 못하면 주어진 범위의 끝을 가리키는 반복자(끝 반복자)를 리턴한다. 참고로 find()를 호출할 때는 지정한 범위에 컨테이너의 모든 원소를 담지 않아도 된다. 다시 말해 부분 집합만 지정해도 된다.

Caution) find()에서 원소를 찾지 못하면 내부 컨테이너의 끝 반복자가 아니라 함수를 호출할 때 지정한 끝 반복자를 리턴한다.

#include <algorithm>
#include <vector>
#include <iostream>
using namesapce std;

int main()
{
int num;
vector<int> myVector;

while(true)
{
cout << "Enter a number to add (0 to stop): ";
cin >> num;

if (num == 0)
{
break;
}
myVector.push_back(num);
}

while(true)
{
cout << "Enter a number to lookup (0 to stop): ";
cin >> num;

if (num == 0)
{
break;
}

auto endIt = cend(myVector);
auto it = find(cbegin(myVector), endIt, num);

if (it == endIt)
{
cout << "Could not find " << num << endl;
}
else
{
cout << "Found " << *it << endl;
}
}

return 0;
}

find()를 호출할 떄 cbegin(myVector)와 endIt을 인수로 지정했다. 여기서는 vector에 있는 원소를 모두 검색하도록 endIt을 cend(myVector)로 정의한다. 일부분만 검색하려면 이 두 반복자를 적절히 변경한다.

C++ 17부터 추가된 if 문의 이니셜라이저를 적용하면 find()를 호출하고 결과를 검사하는 작업을 다음과 같이 한 문장으로 표현할 수 있다.

if (auto it = find(cbegin(myVector), endIt, num); it == endIt)
{
cout << "Could not find " << num << endl;
}
else
{
cout << "Find " << *it << endl;
}

참고로 map과 set처럼 find()를 자체적으로 정의해서 클래스 메서드로 제공하는 컨테이너도 있다.

Caution) 제네릭 알고리즘과 동일한 기능을 제공하는 메서드가 컨테이너에 있다면 컨테이너의 메서드를 사용하는 것이 좋다. 훨씬 빠르기 때문이다.

find_if()는 인수로 검색할 원소가 아닌 프레디케이트 함수 콜백(predicate function callback)을 받는다는 점을 제외하면 find()와 같다. 프레디케이트는 true나 false를 리턴한다. find_if() 알고리즘은 지정한 범위 안에 있는 원소에 대해 인수로 지정한 프레디케이트가 true를 리턴할 때가지 계속 호출한다. 프레디케이트가 true를 리턴하면 find_if()는 그 원소를 가리키는 반복자를 리턴한다.

bool perfectScore(int num)
{
return num >= 100;
}

int main()
{
int num;
vector<int> myVector;

while(true)
{
cout << "Enter a number to add (0 to stop): ";
cin >> num;

if (num == 0)
{
break;
}
myVector.push_back(num);
}

auto endIt = cend(myVector);
auto it = find(cbegin(myVector), endIt, perfectScore);

if (it == endIt)
{
cout << "Not perfect scores" << endl;
}
else
{
cout << "Found a \"perfect\" score of " << *it << endl;
}

return 0;
}

find_if()를 호출할 때 다음과 같이 람다 표현식을 지정해도 된다. 여기서 람다 표현식의 강력함을 엿볼 수 있다. 이렇게 하면 perfectScore()란 함수를 따로 정의할 필요가 없다.

auto it = find_if(cbegin(myVector), endIt, [](int i) { return i => 100; });

accumulate() 알고리즘

컨테이너에 있는 원소를 모두 더할 때 accumulate() 함수를 이용한다. 다음 예는 vector에 담긴 정수의 산술 평균을 구한다.

double arithmeticMean(const vector<int>& nums)
{
double sum = accumulate(cbegin(nums), cend(nums), 0);
return sum / num.size();
}

accumulate() 알고리즘은 합에 대한 초깃값을 세 번째 매개변수로 받는다. 여기서는 처음부터 새로 구하도록 덧셈의 항등원인 0을 지정했다.

accumulate()의 두 번째 형태는 디폴트 연산인 덧셈 대신 다른 연산을 직접지정할 수 있다. 이때 연산을 이진(인수가 두 개인) 콜백으로 표현한다. 예컨대 주어진 원소에 대한 기하 평균을 구하는 코드는 다음과 같다.

int product(int num1, int num2)
{
return num1 * num2;
}

double geometricMean(const vector<int>& nums)
{
double mult = accumulate(cbegin(nums), cend(nums), 1, product);
return pow(mult, 1.0 / num.size());
}

여기서 product() 함수를 accumulate() 의 콜백으로 전달하고, accumulate()의 초깃값을 곱셈의 항등원인 1로 지정했다.

람다 표현식을 이용하면 다음과 같이 작성할 수 있다.

double geometricMeanLabda(const vector<int>& nums)
{
double mult = accumulate(cbegin(nums), cend(nums), 1, [](int num1, int num2) { return num1 * num2; });

return pow(mult, 1.0/num.size());
}

알고리즘과 이동 의미론

표준 라이브러리의 컨테이너와 마찬가지로 알고리즘도 이동 의미론을 적용해서 최적화할 수 있다. 이동 의미론을 구현하려면 클래스에 이동 생성자와 이동 대입 연산자를 구현하고 noexcept로 지정해야 한다.

std::function

<functional> 헤더 파일에 정의된 std::function 템플릿을 이용하면 함수를 가리키는 타입, 함수 객체, 람다 표현식을 비롯하여 호출 가능한 모든 대상을 가리키는 타입을 생성할 수 있다. std::function을 다형성 함수 래퍼(polymorphic function wrapper)라고 부르며, 함수 포인터로 사용할 수도 있고, 콜백을 구현하는 함수를 나타내는 매개변수로 사용할 수도 있다.

std::function의 템플릿 매개변수는 다른 템플릿 매개변수와 모양이 다르다. 문법은 다음과 같다.

std::function<R(ArgTypes...)>

여기서 R은 리턴 타입이고 ArgTypes는 각각을 콤마로 구분한 매개변수의 타입 목록이다.

std::function으로 함수 포인터를 구현하는 방법은 다음과 같다. 여기서는 func()를 가리키는 f1이란 함수 포인터를 생성한다. f1을 정의한 뒤에는 func나 f1이란 이름만으로 func()를 호출할 수 있다.

void func(int num, const string& str)
{
cout << "func(" << num << ", " << str << ")" << endl;
}

int main()
{
function<void(int, const string&)> f1 = func;
f1(1, "test");
return 0;
}

물론 위 예제에서 auto 키워드를 사용하면 f1 앞에 굳이 타입을 지정하지 않아도 된다. 위와 같이 작성하면 컴파일러는 f1의 타입이 std::function이 아니라 함수 포인터라고 판단한다. 그래서 void (*f1) (int, const string&) 라고 변환해버린다.

std::function 타입은 함수 포인터처럼 작동하기 떄문에 표준 라이브러리 알고리즘에 인수로 전달할 수 있다. find_if() 알고리즘에 이를 적용한 예는 다음과 같다.

bool isEven(int num)
{
return num % 2 == 0;
}

int main()
{
vector<int> vec { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

function<bool(int)> fcn = isEven;
auto result = find_if(cbegin(vec), cend(vec), fcn);

if (result != cend(vec))
{
cout << "First even number: " << *result << endl;
}
else
{
cout << "No even number found" << endl;
}

return 0;
}

이 예제를 보고 나서 std::function을 굳이 사용할 필요가 없다고 생각할 수도 있지만 std::function의 진가는 콜백을 클래스 멤버 변수에 저장할 때 드러난다. 또한 함수 포인터를 매개변수로 받아야 할 때도 유용하다.

다음 코드에 나온 process() 함수는 vector에 대한 레퍼런스와 std::function을 인수로 받는다. process() 함수는 인수로 전달된 vector의 모든 원소에 대해 루프를 돌면서 각 원소에 대해 process()인 인수로 지정한 함수를 호출한다. 여기서 매개변수 f는 콜백이다.

그 뒤에 나오는 print() 함수는 인수로 지정한 값을 콘솔에 출력한다. main() 함수는 가장 먼저 정수에 대한 vector를 생성한다. 그러고 나서 process() 함수에 print()를 함수 포인터로 전달해서 호출한다. 그러면 vector에 담긴 원소를 화면에 출력한다.

main() 함수는 람다 표현식을 process() 함수의 std::function 매개변수의 값으로 지정하는 예를 보여준다. 여기서 std::function의 진가가 드러난다. 일반 함수 포인터로는 이렇게 처리할 수 없다.

void process(const vector<int>& vec, function<void(int)> f)
{
for (auto& i : vec)
{
f(i);
}
}

void print(int num)
{
cout << num << " ";
}

int main()
{
vector<int> vec { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

process(vec, print);
cout << endl;

int sum = 0;
process(vec, [&sum](int num){ sum += num; });
cout << "sum = " << sum << endl;

return 0;
}

콜백 매개변수로 std::function을 사용하지 않고 다음과 같이 함수 템플릿으로 만들어도 된다.

template <typename F>
void processTemplate(const vector<int>& vec, F f)
{
for (auto& i : vec)
{
f(i);
}
}

이렇게 정의한 함수 템플릿은 비템플릿 process() 함수와 기능이 같다. 다시 말해 processTemplate()은 일반 함수 포인터와 람다 표현식을 모두 받을 수 있다.

람다 표현식

람다 표현식(lambda expression)이란 함수나 함수 객체를 별도로 정의하지 않고 필요한 지점에서 곧바로 함수를 직접 만들어 쓸 수 있는 일종의 익명 함수다. 람다 표현식을 잘 활용하면 코드를 깔끔하게 만들 수 있다.

문법

람다 표현식은 람다 선언자(lambda introducer)라 부르는 대괄호 []로 시작하고, 그 뒤에 람다 표현식의 본문을 담는 중괄호 {}가 나온다.

아래 예시의 람다 표현식은 auto 타입 변수인 basicLabda에 대입된다. 이렇게 정의한 람다 표현식은 두 번째 줄처럼 일반 함수를 호출하는 방식으로 실행한다.

auto basicLambda = [] { cout << "Hello from Lambda" << endl; };
basicLambda();

람다 표현식도 매개변수를 받을 수 있다. 람다 표현식의 매개변수는 일반 함수와 마찬가지로 소괄호로 묶어서 표현한다. 매개변수가 여러 개면 각각을 콤마로 구분한다. 

auto parametersLambda = [] (int value) { cout << "The value is " << value << endl; };
parametersLambda(42);

람다 표현식에서 매개변수를 받지 않을 때는 빈 소괄호만 적거나 소괄호를 생략한다. 

람다 표현식은 값을 리턴한다. 이러한 리턴값의 타입은 다음과 같이 화살표 뒤에 지정한다. 이러한 표기법을 후행(후위) 리턴 타입(trailing return type)이라 부른다. 다음 코드는 두 매개변수로부터 받은 정수를 더한 결과를 리턴하는 예이다.

auto returningLambda = [](int a int b) -> int { return a + b; };
int sum = returningLambda(11, 22);

람다 표현식은 자신이 속한 스코프에 있는 변수에 접근할 수 있다. 예컨대 다음 코드는 data라는 변수를 람다 표현식의 본문에서 사용한다.

double data = 1.23;
auto capturingLambda = [data] { cout << "Data = " << data << endl; };

대괄호 부분은 람다 캡쳐 블록(capture block)이라 부른다. 앞의 코드처럼 어떤 변수를 대괄호 안에 지정해서 람다 표현식의 본문 안에서 그 변수를 사용하게 만들 수 있다. 이를 캡쳐한다고 한다. 캡쳐 블록을 []와 같이 비워두면 람다 표현식이 속한 스코프에 있는 변수를 캡쳐하지 않는다. 앞의 코드처럼 캡쳐 블록에 변수 이름만 쓰면 그 변수를 값으로 캡쳐한다.

컴파일러는 람다 표현식을 이름 없는 펑터(함수 객체)로 변환한다. 캡쳐한 변수는 이 펑터의 데이터 멤버가 된다. 값으로 캡쳐한 변수는 펑터의 데이터 멤버로 복제된다. 이렇게 복제된 데이터 멤버는 캡쳐한 변수의 const 속성을 그대로 이어받는다. 

앞서 본 capturingLambda 예제에서 펑터는 non-const 데이터 멤버(data)를 갖게 된다. 캡처한 변수인 data가 non-const이기 때문이다. 하지만 다음 코드에서는 변수가 const이기 때문에 펑터는 const 데이터 멤버를 갖게 된다.

const double data = 1.23;
auto capturingLambda = [data] { cout << "Data = " << data << endl; };

펑터마다 함수 호출 연산자인 operator()가 구현돼있다. 람다 표현식의 경우 이 연산자는 기본적으로 const로 설정된다. 따라서 non-const 변수를 람다 표현식에 값으로 캡쳐해도 람도 표현식 안에서 이 값의 복제본을 수정할 수 없다. 다음과 같이 람다 표현식을 mutable로 지정하면 함수 호출 연산자를 non-const로 만들 수 있다.

double data = 1.23;
auto capturingLambda = [data] () mutable { data *=2 ; cout << "Data = " << data << endl; };

이 코드에서 non-const data 변수를 값으로 캡쳐했다. 따라서 data의 복제본으로 생성되는 펑터의 데이터 멤버는 non-const다. 여기서 mutable 키워드를 지정했기 때문에 함수 호출 연산자도 non-const다. 따라서 람다 표현식의 본문에서 data의 복제본을 수정할 수 있다. 참고로 mutable을 지정할 때는 매개변수가 없더라도 소괄호를 반드시 적어야 한다.

변수 이름 앞에 &를 붙이면 레퍼런스로 캡쳐한다.

double data = 1.23;
auto capturingLambda = [&data] { data *= 2; }; 

변수를 레퍼런스로 캡쳐하려면 람다 표현식을 실행하는 시점에 레퍼런스가 유효한지 반드시 확인해야 한다.

람다 표현식이 속한 스코프의 변수를 모두 캡쳐할 수도 있다. 방법은 다음과 같이 두 가지가 있다.

  • [=]: 스코프에 있는 변수를 모두 값으로 캡쳐한다.
  • [&]: 스코프에 있는 변수를 모두 레퍼런스로 캡쳐한다.

캡쳐 리스트를 지정하면 캡쳐할 변수를 골라서 지정할 수 있다. 이때 캡쳐 디폴트(capture default)도 함께 지정할 수 있다. 캡쳐 리스트에서 앞에 &가 붙은 변수를 레퍼런스로 캡쳐한다. &가 없는 변수는 값으로 캡쳐한다. 변수 이름 앞에 &나 =를 붙이려면 반드시 캡쳐 리스트의 첫 번째 원소가 캡쳐 디폴트(& 또는 =)여야 한다. 캡쳐 블록에 대한 예를 몇 가지 들면 다음과 같다.

  • [&x]: 변수 x만 레퍼런스로 캡쳐한다.
  • [x]: 변수 x만 값으로 캡쳐한다.
  • [=, &x, &y]: x와 y는 캡쳐하고, 나머지는 값으로 캡쳐한다.
  • [&, x]: x만 값으로 캡쳐하고 나머지는 레퍼런스로 캡쳐한다.
  • [this]: 현재 객체를 캡쳐한다. 람다 표현식의 본문 안에서 이 객체에 접근할 때 this->를 붙이지 않아도 된다.
  • [*this]: 현재 객체의 복제본을 캡쳐한다. 람다 표현식을 실행하는 시점에 객체가 살아 있지 않을 때 유용하다.

Note) 캡쳐 디폴트를 지정할 때는 람다 표현식의 본문에서 실제로 쓸 것만 값(=) 또는 레퍼런스(&)로 캡쳐해야 한다. 사용하지 않을 변수는 캡쳐하지 않는다..

Caution) 캡쳐 디폴트가 람다 표현식에서 실제로 사용된 변수만 캡쳐하더라도 캡쳐 디폴트를 사용하지 않는 것이 좋다. = 캡쳐 디폴트를 사용하면 자칫 복제 연산이 발생할 수 있는데 그러면 성능에 지장을 준다. & 캡쳐 디폴트를 사용할 때는 스코프에 있는 변수를 실수로 수정해 버릴 수 있다. 가능하면 캡쳐할 변수를 직접 지정하기 바란다.

람다 표현식의 문법을 정리하면 다음과 같다.

[캡쳐 블록] (매개변수) mutable constexpr noexcept 속성 -> 리턴타입 { 본문 }
  • 캡쳐블록: 스코프에 있는 변수를 캡쳐하는 방식을 지정하고, 람다 표현식의 본문에서 그 변수에 접근할 수 있게 만든다.
  • 매개변수(생략 가능): 람다 표현식에 대한 매개변수 목록. 매개변수를 받지 않고 mutable, const 표현식, noexcept 지정자, 속성, 리턴 타입을 지정하지 않는다면 생략해도 된다. 매개변수 목록을 지정하는 방식은 일반 함수와 같다.
  • mutable(생략 가능): 람다 표현식을 mutable로 지정한다.
  • constexpr(생략 가능): 람다 표현식을 const로 지정한다. 그러면 컴파일 시간에 평가된다. 명싲거으로 지정하지 않더라도 람다 표현식이 일정한 요건을 충족하면 내부적으로 const로 처리된다.
  • noexcept(생략 가능): noexcept 구문을 지정할 때 사용한다. 기능은 일반 함수에 대한 noexcept와 같다.
  • 속성(생략 가능): 람다 표현식에 대한 속성을 지정한다. 
  • 리턴타입(생략 가능): 리턴값의 타입을 지정한다. 생략하면 컴파일러가 추론한다.

제네릭 람다 표현식

람다 표현식에서 매개변수의 타입을 구체적으로 지정하지 않고 auto 타입 추론을 적용할 수 있다. 매개변수에 auto 타입 추론을 적용하려면 타입 자리에 auto라고만 쓰면 된다. 이때 적용되는 타입 추론 규칙은 템플릿 인수 추론과 같다.

다음 코드는 isGreaterThan100 이란 이름의 제네릭 람다 표현식을 정의하고 있다. 이 표현식을 find_if() 알고리즘에 적용하는데, 한 번은 정수 vector에 대해 또 한번은 double vector에 대해 적용한다.

// 값이 100보다 큰지 판단하는 제네릭 람다 표현식 정의
auto isGreaterThan100 = [] (auto i) { return i > 100; };

// 위에서 정의한 제네릭 람다 표현식을 정수 벡터에 적용한다.
vector<int> ints { 11, 55, 101, 200 };
auto it1 = find_if(cbegin(ints), cend(ints), isGreaterThan100);
if (it1 != cend(ints))
{
cout << "Found a value > 100: " << *it1 << endl;
}

// 위에서 정의한 제네릭 람다 표현식을 double vector에 적용한다.
vector<double> doubles { 11.1, 55.5, 200.2 };
auto it2 = find_if(cbegin(doubles), cend(doubles), isGreaterThan100);
if (it2 != cend(ints))
{
cout << "Found a value > 100: " << *it2 << endl;
}

람다 캡처 표현식

람다 캡쳐 표현식(lambda capture expression)은 표현식에 사용할 캡쳐 변수를 초기화한다. 스코프에 있는 변수 중에서 캡쳐하지 않았던 것을 람다 표현식에 가져오는데 사용할 수 있다.

예컨대 다음 코드를 보면 람다 캡쳐 표현식으로 myCapture란 변수를 ‘Pi:’로 초기화하고, 람다 표현식과 같은 스코프에 있던 pi 변수를 캡쳐한다. 참고로 myCapture처럼 비레퍼런스(non-reference) 캡쳐 변수를 캡쳐 이니셜라이저(capture initializer)로 초기화할 때는 복제 방식으로 생성된다. 그래서 const 지정자가 사라진다.

double pi = 3.1415;
auto myLambda = [myCpature = "Pi: ", pi] { cout << myCapture << pi; };

람다 캡쳐 변수는 std::move()를 비롯한 모든 종류의 표현식으로 초기화할 수 있다. unique_ptr처럼 복제할 수 없고 이동만 가능한 객체를 다룰 때 이 점을 반드시 명심해야 한다. 기본적으로 값으로 캡쳐하면 복제 방식이 적용된다. 그래서 unique_ptr를 람다 표현식에 값으로 캡쳐할 수 없다. 하지만 람다 캡쳐 표현식을 사용하면 다음과 같이 이동 방식으로 복제할 수 있다.

auto myPtr = std::make_unique<double>(3.1415);
auto myLambda = [p = std::move(myPtr)] { cout << *p; };

권장하는 방법은 아니지만 캡쳐 대상인 변수 이름과 캡쳐해서 람다 표현식 안에 사용할 변수 이름을 똑같이 정해도 된다. 위 코드를 이렇게 수정하면 다음과 같다.

auto myPtr = std::make_unique<double>(3.1415);
auto myLambda = [myPtr = std::move(myPtr)] { cout << *myPtr; };

람다 표현식을 리턴 타입으로 사용하기

std::function을 이용하면 함수가 람다 표현식을 리턴하게 만들 수 있다. 예컨대 다음 코드를 보자.

function<int(void)> multiplyBy2Lambda(int x)
{
return [x] { return 2 * x; };
}

이 함수의 본문을 보면 스코프에 있는 x라는 변수를 값으로 캡쳐하고 multiplyBy2Lambda의 인수에 2를 곱한 정숫값을 리턴하는 람다 표현식을 생성한다. 이 함수의 리턴 타입은 인수를 받지 않고 정수를 리턴하는 함수인 function<int(void)>다. 이 함수의 본문에서 정의한 람다 표현식은 함수 프로토타입과 정확히 일치한다. 변수 x는 값으로 캡쳐하기 때문에 이 함수가 람다 표현식을 리턴하기 전에 람다 표현식 안의 x는 x값의 복제본에 바인딩된다. 이 함수를 호출하는 방법은 다음과 같다.

function<int(void)> fn = multiplyBy2Lambda(5);
cout << fn() << endl;

auto 키워드를 사용하면 더 간결하게 표현할 수 있다.

auto fn = multiplyBy2Lambda(5);
cout << fn() << endl;

함수 리턴 타입 추론을 활용하면 multiplyBy2Lambda() 함수를 다음과 같이 좀 더 세련되게 표현할 수 있다.

auto multiplyBy2Lambda(int x)
{
return [x] { return 2 * x; };
}

multiplyBy2Lambda() 함수는 변수 x를 값으로 캐쳐한다([x]). 만약 다음과 같이 x를 레퍼런스로 캡쳐하면 ([&x]) 문제가 생긴다. 여기서 리턴한 람다 표현식은 대부분 이 함수가 끝난 뒤에 사용된다. 그래서 multiplyBy2Lambda() 함수의 스코프는 더는 존재하지 않기 때문에 x에 대한 레퍼런스는 이상한 값을 가리키게 된다.

auto multiplyBy2Lambda(int x)
{
return [&x] { return 2 * x; }; // 버그 발생
}

람다 표현식을 매개변수로 사용하기

std::function 타입의 함수 매개변수는 람다 표현식을 인수로 받을 수 있다. 그때 소개한 예제를 보면 process() 함수가 콜백을 람다 표현식으로 받았다. 또한 std::function 대신 함수 템플릿을 사용하는 방법도 소개했다. processTemplate() 함수 템플릿은 인수를 람다 표현식으로 받을 수 있다.

표준 라이브러리 알고리즘 활용 예제

(생략)

함수 객체

어떤 클래스의 함수 호출 연산자를 오버로딩해서 그 클래스의 객체를 함수 포인터처럼 사용하게 만들 수 있다. 이렇게 사용하는 객체를 함수 객체 또는 펑터라 부른다.

표준 라이브러리 알고리즘 중에서 find_if(), accumulate()를 비롯한 여러 알고리즘은 함수 포인터, 람다 표현식, 펑터 등을 비롯한 호출 가능 개체(callable)를 인수로 받아서 알고리즘의 동작을 변경할 수 있다.

펑터의 개념은 간단하지만 작성 과정은 상당히 번거롭다. 함수나 펑터 클래스를 생성해서 다른 것과 중복되지 않게 이름을 정한 다음 그 이름을 사용하도록 작성해야 한다. 이럴 때는 람다 표현식을 이용하여 익명 함수로 만들면 편하다.

Note) 가능하면 함수 객체보다 람다 표현식을 사용하기 바란다. 표현식이 코드를 작성하기 쉬울 뿐 아니라 읽거나 이해하기도 쉽기 때문이다.

산술 함수 객체

C++는 다섯 가지 이항 산술 연산자(plus, minus, multiplies, divides, modulus)에 대한 펑터 클래스 템플릿을 제공한다. 여기에 추가로 단항 negate도 제공한다.

이러한 클래스 템플릿을 피연산자의 타입으로 템플릿화해서 클래스를 만들면 실제 연산자에 대한 래퍼로 사용할 수 있다. 템플릿 타입의 매개 변수를 한 개 또는 두 개 받아서 연산을 수행한 뒤 결과를 리턴한다. plus 클래스 템플릿을 사용하는 방법은 다음과 같다.

plus<int> myPlus;
int res = myPlus(4, 5);
cout << res << endl;

이렇게 해서 더 나아지는 점이 없다. plus 클래스 템플릿을 사용할 필요 없이 곧바로 operator+를 사용해도 된다. 하지만 이렇게 산술 함수 객체를 사용하면 알고리즘으로 콜백을 전달하기 좋다. 산술 연산자를 곧바로 쓸 때는 이렇게 할 수 없기 때문이다.

예컨대 앞서 본 geometricMean() 함수는 accumulate()에 두 정수를 곱하는 product() 콜백을 함수 포인터로 전달하도록 구현했다. 이 부분을 다음과 같이 C++에서 제공하는 multiplies 함수 객체를 사용하도록 수정할 수 있다.

double geometricMean(const vector<int>& nums)
{
double mult = accumulate(cbegin(nums), cend(nums), 1, multiplies<int>());
return pow(mult, 1.0 / nums.size());
}

multiplies<int>()라는 표현식은 multiplies 펑터 클래스 템플릿으로부터 int 타입에 대한 인스턴스를 새로 만든다. 다른 산술 함수 객체의 기능과 사용법도 이와 비슷하다.

Caution) 산술 함수 객체는 산술 연산자에 대한 래퍼에 불과하다. 알고리즘에서 함수 객체를 콜백으로 사용하려면 반드시 컨테이너에 담긴 객체가 해당 연산(예: operator*나 operator+ 등)을 구현해야 한다.

투명 연산자 펑터

C++은 투명 연산자(transparent operator) 형태의 펑터도 제공한다. 이 펑터를 이용하면 템플릿 타입 인수를 생략해도 된다. 예컨대 multiplies<int>() 대신 multiplies<>()라고만 적어도 된다.

double geometricMean(const vector<int>& nums)
{
  double mult = accumulate(cbegin(nums), cend(nums), 1, multiplies<>());
  return pow(mult, 1.0 / nums.size());
}

투명 연산자에서 굉장히 중요한 특징은 이종 타입을 지원한다는 점이다. 다시 말해 비투명 펑터 보다 간결할 뿐만 아니라 실질적인 기능도 더 뛰어나다. 예컨대 다음 코드는 vector가 정수를 담고 있지만 투명 연산자 펑터를 사용해서 1.1이라는 double 값으로 초기화하도록 지정했다. 그러면 accumulate()는 결과를 double로 계산해서 6.6이란 값을 리턴한다.

vector<int> nums { 1, 2, 3 };
double result = accumulate(cbegin(nums), cend(nums), multiplies<>());

이 코드를 다음과 같이 비투명 연산자 펑터로 작성하면 accumulate()는 결과를 정수로 계산해서 6을 리턴한다. 이 코드를 컴파일하면 데이터 손실이 발생할 수 있다는 경고 메시지가 출력된다.

vector<int> nums { 1, 2, 3 };
double result = accumulate(cbegin(nums), cend(nums), multiplies<int>());

Note) 항상 투명 연산자 펑터를 사용하기 바란다.

비교 함수 객체

C++는 산술 함수 객체 클래스뿐만 아니라 표준 비교 연산(equal_to, not_equal_to, less, greater, less_equal, greater_equal)도 제공한다. 그중에서 less를 사용하는 방법은 앞 장에서 priority_queue와 연관 컨테이너의 원소를 비교할 때 디폴트 연산자로 지정하는 과정에서 살펴본 적 있다. 이번에는 priority_queue의 비교 기준을 변경하는 방법을 소개한다. 먼저 std::less를 디폴트 비교 연산자로 사용하는 priority_queue를 이용하는 방법은 다음과 같다.

priority_queue<int> myQueue;
myQueue.push(3);
myQueue.push(4);
myQueue.push(2);
myQueue.push(1);

while(!myQueue.empty())
{
cout << myQueue.top() << " ";
myQueue.pop();
}

// 실행 결과
// 4 3 2 1

여기서 볼 수 있듯이 less로 비교하기 때문에 큐에 담긴 원소가 내림차순으로 삭제된다. 템플릿 인수에 greater를 지정해서 비교 연산자를 변경할 수 있다. priority_queue 템플릿은 다음과 같이 정의돼 있다.

template <class T, class Container = vector<T>, class Compare = less<T>>

그런데 Compare 타입 매개변수가 마지막에 있다. 그래서 이 값을 지정하려면 컨테이너 타입 매개변수도 지정해야 한다. 앞에서 본 priority_queue가 greater를 기준으로 원소를 오름차순으로 정렬하게 만들려면 priority_queue를 다음과 같이 선언한다.

priority_queue<int, vector<int>, greater<>> myQueue;

여기서 myQueue를 투명 연산자인 greater<>로 정의했다. 비교자(비교 함수) 타입을 인수로 받는 표준 라이브러리 컨테이너를 사용할 때는 항상 투명 연산자를 사용하는 것이 좋다. 투명 연산자가 대체로 비투명 연산자보다 성능이 좋다.

예컨대 map<string>에서 스트링 리터럴로 주어진 키로 조회 연산을 수행할 때 비투명 연산자를 이용하면 불필요한 복제 연산이 발생할 수 있다. 스트링 리터럴로부터 string 인스턴스를 생성하기 때문이다. 투명 연산자로 된 비교자를 사용하면 이런 복제 연산을 피할 수 있다.

이 장에서 소개하는 알고리즘 중 몇 가지는 비교자 콜백을 지정해야 한다. 이럴 때 미리 정의된 비교자가 있으면 처리하기 편하다.

논리 함수 객체

C++은 logical_not(operator!), logical_and(operator&&), logical_or(operator||)라는 세 가지 논리 비교 연산자에 대한 함수 객체 클래스를 제공한다. 이러한 논리 연산자는 true나 false 값만 다룬다. 비트 함수 객체는 다음 절에서 설명한다.

논리 연산자에 대한 펑터는 컨테이너에 있는 부울 타입 플래그가 모두 true인지 검사하는 allTrue() 함수를 구현하는데 활용할 수 있다.

bool allTrue(const vector<bool>& flags)
{
return accumulate(begin(flags), end(flags), true, logical_and<>());
}

마찬가지로 컨테이너의 부울 플래그가 최소한 하나라도 true면 true를 리턴하는 anyTrue() 함수를 logical_or 펑터로 구현할 수 있다.

bool anyTrue(const vector<bool>& flags)
{
return accumulate(begin(flags), end(flags), false, logical_or<>());
}

Note) 여기서 소개한 allTrue()와 anyTrue() 함수는 단지 예를 보여주기 위해 만든 것이다. 표준 라이브러리는 std::all_of()와 any_of()란 알고리즘으로 이런 연산을 제공하고 있다. 게다가 단락 평가(short-circuiting, 축약 평가)도 지원하기 때문에 성능이 훨씬 뛰어나다.

비트 연산 함수 객체

C++는 bit_and(operator&), bit_or(operator|), bit_xor(operator^), bit_not(operator~)과 같은 모든 비트 연산자에 대한 함수 객체도 제공한다. 비트 연산자에 대한 펑터는 컨테이너에 담긴 모든 원소에 대해 비트 연산을 수행하는 transform() 같은 알고리즘에서 사용할 수 있다.

어댑터 함수 객체

표준에서 제공하는 함수 객체가 자신의 요구사항에 딱 맞지 않을 수 있다. 예컨대 find_if()로 어떤 값보다 작은 원소를 찾을 때 less 함수 객체를 사용할 수 없다. find_if()는 콜백을 호출할 때마다 인수를 단 하나만 지정할 수 있기 때문이다. 

이러한 단점을 보완하기 위해 어댑터 함수 객체(adaptor function object)를 제공한다. 어댑터 함수 객체는 함수 객체, 람다 표현식, 함수 포인터를 비롯한 모든 호출 가능 개체에 적용할 수 있다. 이러한 어댑터는 미약하게나마 함수 합성(functional composition)을 지원한다. 다시 말해 여러 함수를 하나로 합쳐서 원하는 기능을 구현할 수 있다.

바인더

바인더(binder)를 이용하면 호출 가능 개체의 매개변수를 일정한 값으로 묶어둘(바인딩) 수 있다. 이를 위해 <functional> 헤더 파일에 정의된 std::bind()를 이용하면 호출 가능 개체의 매개변수를 원하는 방식으로 바인딩할 수 있다. 이때 매개변수를 고정된 값에 바인딩할 수도 있고, 매개변수의 순서를 바꿀 수도 있다. 

다음과 같이 인수 두 개를 받는 func() 함수를 살펴보자.

void func(int num, string_view str)
{
cout << "func(" << num << ", " << str << ")" << endl;
}

다음 코드는 func()의 두 번째 인수를 myString이란 고정된 값으로 바인딩하도록 bind()를 사용하는 방법을 보여주고 있다. 결과는 f1()에 저장된다. 여기서는 auto 키워드를 사용했는데, C++ 표준에 bind()의 리턴 타입이 명확히 정의돼 있지 않기 때문이다.

특정한 값에 바인딩되지 않은 인수는 반드시 std::placeholders 네임스페이스에 정의된 _1, _2, _3 등으로 지정해야 한다. f1()의 정의에서 _1은 func()를 호출할 때 f1()의 첫 번째 인수가 들어갈 지점을 지정한다. 그러면 다음과 같이 f1()에 정수 타입 인수 하나만 지정해서 호출할 수 있다.

string myString = "abc";
auto f1 = bind(func, placeholders::_1, myString);
f1(16);

// 실행 결과
// func(16, abc)

bind()로 인수의 순서를 바꿀 수도 있다. 예컨대 다음 코드와 같다. 여기서 _2는 func()를 호출할 때 f2()의 두 번째 인수가 들어갈 지점을 지정한다. 다시 말해 f2()의 첫 번째 인수는 func()의 두 번째 인수가 되고, f2()의 두 번째 인수는 func()의 첫 번째 인수가 된다.

auto f2 = bind(func, placeholders::_2, placeholders::_1);
f2("Test", 32);

// 실행결과
// func(32, Test)

앞서 설명했듯이 <functional> 헤더 파일에 std::ref()와 cref() 헬퍼 템플릿 함수가 정의돼 있다. 이를 사용하면 레퍼런스나 const 레퍼런스를 바인딩할 수 있다. 예컨대 다음과 같은 함수를 살펴보자.

void increment(int& value) {++ value; }

이 함수를 다음과 같이 호출하면 index 값이 1이 된다.

int index = 0;
increment(index);

이 함수를 다음과 같이 bind()로 호출하면 index 값이 증가하지 않는다. index의 복제본에 대한 레퍼런스가 increment() 함수의 첫 번째 매개변수로 바인딩되기 때문이다.

int index = 0;
auto incr = bind(increment, index);
incr();

다음과 같이 std::ref()로 레퍼런스를 제대로 지정하면 index 값이 증가한다.

int index = 0;
auto incr = bind(increment, ref(index));
incr();

바인딩 매개변수를 오버로딩된 함수와 함께 사용할 때 사소한 문제가 발생하 ㄹ수 있다. 예컨대 다음과 같은 두 가지 overloaded() 함수가 있다고 하자. 하나는 정수를 받고 다른 하나는 부동소수점수를 받는다.

void overloaded(int num) {}
void overloaded(float f) {}

이렇게 오버로딩된 함수에 대해 bind()를 사용하려면 둘 중 어느 함수에 바인딩할지 명시적으로 지정해야 한다. 예컨대 다음과 같이 작성하면 컴파일 에러가 발생한다.

auto f3 = bind(overloaded, placeholders::_1);  // error

부동소수점 인수를 받는 오버로딩 함수의 매개변수를 바인딩하고 싶다면 다음과 같이 작성한다.

auto f4 = bind((void(*)(float))overloaded, placeholders::_1);

bind()의 또 다른 예로 find_if() 알고리즘으로 컨테이너에서 100보다 크거나 같은 원소 중 첫 번째를 찾는 경우를 들 수 있다. 앞에 나온 perfectScore() 함수 예제에서는 find_if()에 perfectScore()에 대한 포인터를 전달하는 방식으로 처리했다. 이번에는 greater_equal이란 비교 연산 펑터와 bind()로 구현해보자. 다음 코드는 bind()로 greater_equal의 두 번째 매개변수를 100이란 고정된 값으로 바인딩한다.

// 벡터에 점수를 입력하는 코드는 이전과 같으므로 생략한다.
auto endIter = end(myVector);
auto it = find_if(begin(myVector), endIter, bind(greater_equal<>(), placeholders::_1, 100));

if (it == endIter)
{
cout << "No perfect scores" << endl;
}
else
{
cout << "Found a \"perfect\" score of " << *it << endl;
}

다음과 같이 람다 표현식으로 작성하면 훨씬 좋다.

auto it = find_if(begin(myVector, endIter, [](int i) { return i> 100; });

Caution) C++ 11이전에는 bind2nd()와 bind1st()도 제공했다. 둘 다 C++ 11부터 폐기됐고 C++ 17부터는 표준에서 완전히 삭제됐다. 이 함수 대신 람다 표현식이나 bind()를 사용하기 바란다.

부정 연산자

not_fn

부정 연산자(negator)는 바인더와 비슷하지만 호출 가능 개체의 결과를 반전시킨다는 점이 다르다. 예컨대 컨테이너에서 100보다 작은 원소 중 첫 번째를 찾고 싶다면 다음과 같이 perfectScore()에 not_fn()이란 부정 연산자 어댑터를 적용하면 된다.

// 벡터에 점수를 추가하는 부분은 이전과 같으므로 생략한다.
auto endIter = end(myVector);
auto it = find_if(begin(myVector), endIter, not_fn(perfectScore));

if (it == endIter)
{
cout << "All perfect scores" << endl;
}
else
{
cout << "Found a \"less-than-perfect"\ score of " << *it << endl;
}

not_fn() 펑터는 매개변수로 받은 호출 가능 개체의 호출 결과를 모두 반전시킨다. 참고로 이 예제를 find_if_not() 알고리즘으로 구현해도 된다.

여기서 볼 수 있듯이 펑터와 어댑터를 사용하면 코드가 좀 복잡해진다. 그래서 필자는 가능하면 펑터보다는 람다 표현식을 사용하길 권장한다. 예컨대 앞의 not_fn() 펑터로 find_if()를 호출하는 부분을 람다 표현식으로 작성하면 다음과 같다.

auto it = find_if(begin(myVector), endIter, [](int i) { return i < 100; });
not1과 not2

std::not_fn() 어댑터는 C++ 17부터 지원한다. C++ 17 버전에서는 std::not1()과 std::not2() 어댑터를 사용해야 한다. not1()에서 ‘1’은 피연산자가 반드시 하나인 단항 함수여야 한다는 것을 의미한다. 이항 함수에 대해서는 반드시 not2()를 사용해야 한다.

// vector에 점수를 입력하는 부분은 이전과 같으므로 생략
auto endIter = end(myVector);
function<bool(int)> f = perfectScore;
auto it = find_if(begin(myVector), endIter, not1(f));

자신이 직접 정의한 펑터 클래스에 not1()을 사용하려면 펑터 클래스 정의에 argument_type과 result_type이란 두 가지 typedef를 반드시 정의해야 한다. 또한 not2()를 사용하려면 펑터 클래스 정의에 first_argument_type, second_argument_type, result_type이란 세 가지 typedef를 정의해야 한다.

이러한 typedef를 제공하기 위한 가장 쉬운 방법은 인수가 하나면 unary_function을, 두 개면 binary_function을 상속해서 함수 클래스를 정의하는 것이다. 두 클래스 모두 <functional> 헤더에 정의돼 있으며, 지정한 함수의 매개변수와 리턴 타입에 대해 템플릿화 할 수 있다. 예컨대 다음과 같다.

class PerfectScore : public std::unary_function<int, bool>
{
public:
result_type operator()(const argument_type& score) const
{
return score >= 100;
}
};

이 펑터의 사용법은 다음과 같다.

auto it = find_if(begin(myVector), endIter, not1(PerfectScore());

Note) not1()과 note2()는 C++ 17부터 폐기됐다. unary_function과 binary_function도 C++ 11부터 폐기됐고 C++17 부터는 공식적으로 삭제됐다.

멤버 함수 호출하기

컨테이너에 대해 알고리즘을 적용할 때 클래스 메서드에 대한 포인터를 알고리즘으로 콜백으로 전달할 때가 있다. 예컨대 vector에 담긴 string 원소마다 empty()를 호출해서 첫 번째 공백 string을 찾는다고 하자. 이때 find_if()에 string::empty()에 대한 포인터만 전달하면 알고리즘 입장에서는 그 포인터가 일반 함수 포인터나 펑터가 아닌 메서드에 대한 포인터라는 사실을 알아낼 방법이 없다. 메서드 포인터를 호출하는 코드는 일반 함수 포인터를 호출할 때와 다르다. 메서드 포인터는 반드시 객체의 문맥에서 호출해야 하기 때문이다.

C++은 이를 위해 mem_fn()이란 변환 함수를 제공한다. 알고리즘의 콜백으로 메서드 포인터를 전달할 때 이 함수로 변환한 결과를 알고리즘의 콜백으로 전달하면 된다. 예컨대 다음 코드에서 &string::empty라고 메서드 포인터를 지정한 부분과 같다. 여기서 &string:: 부분은 생략하면 안 된다.

void findEmptyString(const vector<string>& strings)
{
auto endIter = end(strings);
auto it = find_if(begin(strings), endIter, mem_fn(&string::empty));

if (it == endIter)
{
cout << "No emtpy strings!" << endl;
}
else
{
cout << "Empty string at position: " << static_cast<int>(it = begin(strings)) << endl;
}
}

mem_fn()은 find_if()에서 콜백으로 사용할 함수 객체를 생성한다. 그러면 콜백이 호출될 때마다 인수(여기서는 스트링)에 대해 empty() 메서드가 호출된다.

컨테이너에 객체를 직접 넣지 않고 객체에 대한 포인터를 지정해도 mem_fn()은 똑같이 작동한다. 예컨대 다음과 같다.

void findEmptyString(const vector<string*>& strings)
{
auto endIter = end(strings);
auto it = find_if(begin(strings), endIter, mem_fn(&string::empty));

// 나머지 코드는 이전과 같으므로 생략
}

mem_fn()으로 findEmptyString() 함수를 구현하면 코드를 이해하기 쉽지 않을 수 있다. 이때 람다 표현식을 사용하면 훨씬 세련되고 이해하기 쉽게 표현할 수 있다.

void findEmptyString(const vector<string>& strings)
{
auto endIter = end(strings);
auto it = find_if(begin(strings), endIter, [](const string& str) { return str.empty(); });

// 나머지 코드는 이전과 같으므로 생략
}

마찬가지로 객체의 포인터를 담은 컨테이너에 대한 작업도 다음과 같이 람다 표현식으로 작성할 수 있다.

void findEmptyString(const vector<string*>& strings)
{
auto endIter = end(strings);
auto it = find_if(begin(strings), endIter, [](const string* str){ return str->empty(); });

// 나머지 코드는 이전과 같으므로 생략
}

invoke()

C++ 17부터 std::invoke()가 추가됐다. 이를 사용하면 모든 종류의 호출 가능 개체에 매개변수를 지정해서 호출할 수 있다. 다음 코드는 invoke()를 세 번 사용한다. 한 번은 일반 함수를, 한 번은 람다 표현식을, 나머지 한 번은 string 인스턴스의 멤버 함수를 호출한다.

void printMessage(string_view message) { cout << message << endl; }

int main()
{
invoke(printMessage, "Hello invoke");
invoke([](const auto& msg) { cout << msg << endl;}, "Hello invoke");
string msg = "Hello invoke";
cout << invoke(&string::size, msg) << endl;
}

invoke()의 기능만 보면 그리 유용하지 않아 보일 수 있다. 그냥 함수나 람다 표현식을 직접 호출해도 되기 때문이다. 하지만 임의의 호출 가능 개체를 호출하는 템플릿 코드를 작성할 때는 굉장히 유용하다.

함수 객체 직접 만들기

미리 정의된 펑터에서 제공하는 함수 객체나 람다 표현식으로 처리하기 힘든 작업을 수행하려면 함수 객체를 직접 작성해야 한다. 다음과 같이 간단히 작성된 함수 객체를 보자.

class myIsDigit
{
public:
bool operator()(char c) const { return ::isdigit(c) != 0; }
};

bool isNumber(string_view str)
{
auto endIter = end(str);
auto it = find_if(begin(str), endIter, not_fn(myIsDigit()));
return (it == endIter);
}

참고로 myIsDigit 클래스에서 오버로딩한 함수 호출 연산자를 반드시 const로 지정해야 이 클래스의 객체를 find_if()에 전달할 수 있다.

Caution) 표준 라이브러리 알고리즘은 펑터나 람다 표현식으로 전달된 프리디케이트를 복제해서 각각의 복제본마다 별도로 원소를 지정해서 호출할 수 있다. 그러면 이러한 프리디케이트로 인해 부작용이 발생하는 것을 방지한다. 펑터로 지정할 때는 함수 호출 연산자를 반드시 const로 지정해야 한다. 그래야 여러 번 호출해도 객체의 내부 상태를 일관성 있게 유지할 수 있다. 람다 표현식도 마찬가지이므로 mutable을 지정하면 안 된다. 

C++ 11 이전에는 함수 스코프 안에서 로컬로 정의한 클래스를 템플릿 인수로 지정할 수 없었다. 현재는 이러한 제약이 삭제됐기 때문에 다음과 같이 작성해도 된다.

bool isNumber(string_view str)
{
class myIsDigit
{
public:
bool operator()(char c) const { return ::isdigit(c) != 0; }
};

auto endIter = end(str);
auto it = find_if(begin(str), endIter, not_fn(myIsDigit()));

return it == endIter;
}

Note) 람다 표현식을 사용하면 코드를 읽기 쉽고 세련되게 작성할 수 있으므로 함수 객체보다 람다 표현식을 사용하는 것이 바람직하다. 함수 객체는 람다 표현식으로 할 수 없는 복잡한 작업을 처리할 때만 사용하기 바란다.

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

반복자

반복자는 입력, 출력, 정방향, 양방향, 랜덤 액세스 등 다섯 가지 종류가 있다. 이러한 반복자에 대해 정식으로 정의한 클래스 계층은 없다. 컨테이너에 대한 구현은 표준 계층 구조에 속하지 않기 때문이다.

하지만 제공할 기능에 따라 어떤 계층에 속할지 추론할 수는 있다. 좀 더 구체적으로 설명하면 랜덤 액세스 반복자는 모두 양방향이고, 양방향 반복자는 모두 정방향이고, 정방향 반복자는 모두 입력 반복자라고 알 수 있다.

출력 반복자의 요건을 충족하는 반복자를 가변 반복자라 부르고 그렇지 않은 반복자를 상수 반복자라 부른다. 이러한 계층구조를 표현하면 아래와 같다. 여기서 계층 관계는 진짜가 아니므로 주의할 것

랜덤 액세스 -> 양방향 -> 정방향 -> 입력

알고리즘에서 사용할 반복자의 종류를 표준 방식으로 지정하려면 반복자 템플릿 타입 인수에 InputIterator, OutputIterator, ForwardIterator, BidirectionalIterator, RandomAccessIterator와 같은 이름을 지정하면 된다. 말 그대로 이름일 뿐이기 때문에 바인딩 타입 검사를 하지 않는다. 따라서 RandomAccessIterator를 인수로 받는 알고리즘에 양방향 반복자를 지정해서 호출해도 타입 검사를 거치지 않기 때문에 템플릿을 인스턴스화 할 수 있다.

하지만 랜덤 액세스 반복자의 기능을 사용하는 코드를 실행할 때 양방향 반복자를 발견하면 컴파일 에러가 발생한다. 따라서 타입 검사 기능을 제공하지 않더라도 실질적으로 타입을 엄격히 지켜야 한다. 게다가 이런 에러로 발생하는 메시지는 정확하지 않다. 

예컨대 랜덤 액세스 반복자를 지정해야 하는 sort() 알고리즘을 양방향 반복자만 제공하는 list에 적용하는 코드를 MS의 비주얼 C++ 2017에서 컴파일하면 30줄에 달하는 이상한 에러 메시지가 발생한다.

불변형 순차 알고리즘

불변형 순차 알고리즘(non-modifying sequence algorithm)이란 주어진 범위에서 원소를 검색하거나 두 범위를 서로 비교하는 함수를 말한다. 또한 개수를 세는 집계 알고리즘도 여기 속한다.

탐색 알고리즘

앞서 find()와 find_if()라는 탐색 알고리즘(검색 알고리즘)의 예를 살펴봤다. 표준 라이브러리는 순차적으로 나열된 원소를 처리하는 기본 find() 알고리즘을 다양하게 변형한 버전을 제공한다.

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

(생략)

특수 탐색 알고리즘

C++ 17부터 search() 알고리즘에 원하는 탐색 알고리즘을 지정할 수 있도록 매개변수가 추가됐다. 이러한 옵션은 크게 세 가지(default_searcher, boyer_moore_searcher, boyer_moore_horspool_searcher)가 있으며 모두 <functional>에 정의돼 있다.

두 번째와 세 번째 옵션은 각각 유명한 보이어-무어(Boyer-Moore) 탐색 알고리즘과 보이어-무어-호스풀(Boyer-Moore-Horsepool) 탐색 알고리즘을 구현한 것이다. 모두 성능이 뚜어나며 방대한 텍스트에서 서브스트링을 검색하는데 주로 사용된다. 

보이어-무어 탐색 알고리즘의 성능은 다음과 같다. 여기서 N은 탐색할 대상의 크기, M은 그 안에서 찾으려는 패턴의 크기를 의미한다.

  • 패턴을 찾지 못한 경우: 최악의 복잡도는 O(N+M)
  • 패턴을 찾은 경우: 최악의 복잡도는 O(NM)

각각에 대한 최악의 복잡도는 이론적으로 분명히 나와 있다. 실전에서 이런 특수 탐색 알고리즘을 사용해보면 O(N)보다 뛰어난 준선형(sublinear) 시간이 나온다. 다시 말해 기본 탐색 알고리즘보다 훨씬 빠르다. 이렇게 준선형 시간에 실행할 수 있는 이유는 탐색 범위에 있는 문자를 모두 검사하지 않고 중간에 건너뛸 수 있기 때문이다. 또한 탐색할 패턴이 길수록 성능이 좋아진다. 탐색 대상에서 건너뛸 문자가 많아지기 때문이다.

보이어-무어와 달리 보이어-무어-호스풀 알고리즘은 초기화와 루프를 한 바퀴 도는데 걸리는 오버헤드가 적다. 하지만 최악의 복잡도는 보이어-무어 알고리즘보다 훨씬 크다. 따라서 어떤 것을 적용할지는 주어진 작업의 성격에 맞게 판단한다.

보이어-무어 탐색 알고리즘의 사용 예는 다음과 같다.

string text = "This is the haystack to search a needle in";
string toSearchFor = "needle";

auto searcher = std::boyer_moore_searcher(cbegin(toSearchFor), cend(toSearchFor));
auto result = search(cbegin(text), cend(text), searcher);

if (result != cend(text))
{
cout << "Found the needle" << endl;
}
else
{
cout << "Needle not found" << endl;
}

비교 알고리즘

주어진 범위의 원소를 비교할 때 equal(), mismatch(), lexicographical_compare()라는 세 가지 알고리즘 중 하나를 적용할 수 있다. 이 알고리즘은 비교할 범위가 속한 컨테이너가 달라도 적용할 수 있다는 장점이 있다. 예컨대 vector에 있는 원소와 list의 원소를 비교할 수 있다.

일반적으로 비교 알고리즘은 순차 컨테이너에 적용할 때 성능이 가장 뛰어나며, 각 컬렉션에서 동일한 위치에 있는 값끼리 비교하는 방식으로 실행된다. 각 알고리즘의 작동 방식은 다음과 같다.

  • equal()
    • 주어진 원소가 모두 같으면 true를 리턴한다. 이전 버전에서 equal()은 세 가지 반복자(첫 번째 범위에 대한 시작과 끝 반복자, 두 번째 범위에 대한 시작 반복자)만 인수로 받을 수 있었다. 이 버전은 비교할 범위에 속한 원소의 개수와 일치해야 한다. 그런데 C++ 14부터 네 가지 반복자(첫 번째 범위에 대한 시작과 끝 반복자, 두 번째 범위에 대한 시작과 끝 반복자)를 받도록 오버로딩된 버전이 추가됐다. 이 버전은 서로 크기가 다른 범위를 비교할 수 있다. 네 가지 반복자를 받는 버전이 훨씬 안전하기 때문에 항상 이 버전을 사용하는 것이 좋다.
  • mismatch()
    • 주어진 범위에서 일치하지 않는 범위를 가리키는 반복자를 리턴한다. equal()과 마찬가지로 세 가지 반복자를 받는 버전과 네 가지 반복자를 받는 버전이 있다. mismatch()도 마찬가지로 네 가지 반복자를 받는 버전이 훨씬 안전하므로 이 버전을 사용하기 바란다.
  • lexicographical_compare()
    • 첫 번째로 일치하지 않는 양쪽 범위의 원소 중에서 첫 번째 범위의 원소가 두 번째 범위의 원소보다 작거나, 첫 번째 범위의 원소 수가 두 번째 범위의 원소 수보다 적으면서 첫 번째 범위의 원소가 모두 두 번째 범위의 앞부분과 일치하면 true를 리턴한다. lexicographical_compare란 이름이 붙은 이유는 스트링을 나열하는 방식이 사전과 비슷하기 때문이다. 이 알고리즘은 모든 타입의 객체를 다룰 수 있도록 규칙을 확장했다.

Note) 타입이 서로 같은 컨테이너 원소 두 개를 비교할 때는 equal()이나 lexicographical_compare() 보다는 operator==나 operator<를 사용하는게 좋다. 표준 라이브러리 알고리즘은 서로 타입이 다른 컨테이너의 부분 범위나 C 스타일 배경르 비교하는데 적합하다.

(사용 예시 생략)

집계 알고리즘

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

(사용 예시 생략)

가변형 순차 알고리즘

표준 라이브러리는 가변형 순차 알고리즘(modifying sequence algorithm)도 다양하게 제공한다. 예컨대 한 범위에 있는 원소를 다른 범위로 복제하거나 원소를 삭제하거나 주어진 범위의 원소 순서를 반대로 바꾸는 것이 있다.

가변형 알고리즘 중 일부는 원본(source)과 대상(destination) 범위를 모두 지정한다. 그래서 원본 범위에 있는 원소를 읽어서 변경한 내용을 대상 범위에 저장한다. 나머지 알고리즘은 주어진 범위에서 곧바로 수정한다. 그래서 범위를 하나만 지정해도 된다.

Caution) 가변형 알고리즘은 대상 범위에 원소를 추가하는 작업은 할 수 없다. 대상 범위에 있는 원소를 수정하거나 덮어쓸 수만 있다. 반복자 어댑터를 이용하면 대상 범위에 원소를 추가하게 만들 수는 있다.

Note) 가변형 알고리즘의 대상 범위를 map과 multimap의 범위로 지정할 수 없다. 가변형 알고리즘에 map을 적용하면 키/값 쌍으로 구성된 원소를 모두 덮어쓰기 때문이다. 그런데 map과 multimap은 키를 const로 지정하기 때문에 다른 값을 대입할 수 없다. set과 multiset도 마찬가지다. 따라서 map이나 set류의 컨테이너에 가변형 알고리즘을 적용하려면 21장에서 소개하는 추가 반복자(insert iterator)로 처리해야 한다.

transform

transform() 알고리즘의 첫 번째 버번은 주어진 범위에 있는 모든 원소마다 콜백을 적용해서 새 원소를 생성한다. 이렇게 생성된 원소는 인수로 지정한 대상 범위에 저장된다. 원본과 대상 범위를 똑같이 지정하면 그 범위 안에 담긴 원소를 그 원소에 대해 콜백을 호출할 결과로 대체할 수 있다. 이때 원본 범위의 시작과 끝 반복자, 대상 범위의 시작 반복자, 콜백을 매개변수로 지정한다. 예컨대 vector의 모든 원소에 100씩 더하려면 다음과 같이 작성한다.

vector<int> myVector;
populateContainer(myVector);

cout << "The vector contains:" << endl;
for (const auto& i : myVector) { cout << i << " "; }
cout << endl;

transform(begin(myVector), end(myVector), begin(myVector), [](int i) { return i + 100; });

cout << "The vector contains:" << endl;
for (const auto& i : myVector) { cout << i << " "; }

transform()의 또 다른 버전은 주어진 범위의 원소 쌍에 대해 이항 함수를 호출한다. 그래서 첫 번째 범위에 대한 시작과 끝 반복자, 두 번째 범위에 대한 시작 반복자, 대상 범위에 대한 시작 반복자를 인수로 지정해야 한다.

다음 예는 vector를 두 개 생성해서 transform()으로 두 vector에서 같은 위치의 원소끼리 더한 결과를 첫 번째 vector에 저장하는 방법을 보여준다.

vector<int> vec1, vec2;

cout << "Vector1:" << endl;
populateContainer(vec1);

cout << "Vector2:" << endl;
populateContainer(vec2);

if (vec2.size() < vec1.size())
{
cout << "Vector2 should be at least the same size as vector1" endl;
return 1;
}

// 컨테이너의 내용을 출력하는 람다 표현식을 만든다.
auto printContainer = [](const auto& container) {
for (auto& i : container) { cout << i << " "; }
cout << endl;
};

cout << "Vector1: ";
printContainer(vec1);

cout << "Vector2: ";
printContainer(vec2);

transform(begin(vec1), end(vec1), begin(vec2), begin(vec1), [](int a, int b){ return a + b; });

cout << "Vector1: ";
printContainer(vec1);

cout << "Vector2: ";
printContainer(vec2);

Note) transform()을 비롯한 가변형 알고리즘 중에는 대상 범위의 마지막 바로 다음 번째 항목을 가리키는 반복자를 리턴하는 것이 많다. 이 책에 나온 예제는 대부분 리턴값을 무시한다.

copy

copy() 알고리즘은 한 범위의 원소를 다른 범위로 복제한다. 이때 주어진 범위의 첫 버째 원소부터 시작해서 마지막 원소까지 순차적으로 처리한다. 원본과 대상 범위는 반드시 달라야 하지만 일정한 제약사항(예컨대 copy(b, e, d)에서 d가 b보다 앞에 나온다면) 중첩돼도 된다. 하지만 d가 [b, e) 범위 안에 있으면 어떤 결과가 나올지 알 수 없다.

다른 가변형 알고리즘과 마찬가지로 copy()도 대상 범위에 원소를 추가할 수 없다. 기존에 있던 원소를 그냥 덮어쓰기만 한다. 

여기서는 copy()를 사요하는 간단한 예제를 소개한다. 여기서 copy()는 대상 컨테이너에 공간이 충분한지 확인하는 작업을 vector의 resize() 메서드로 처리한다. 그런 다음 vec1의 원소를 모두 vec2로 복제한다.

vector<int> vec1, vec2;
populateContainer(vec1);

vec2.resize(size(vec1));
copy(cbegin(vec1), cend(vec1), begin(vec2));
for (const auto& i : vec2) { cout << i << " "; }

copy_backward()란 알고리즘도 제공한다. 이 알고리즘은 원본의 마지막 원소부터 시작 원소 순으로 복제한다. 다시 말해 원본의 마지막 원소를 복제해서 대상의 마지막 우너소에 저장하고 그다음에는 바로 전 원소를 처리하는 식으로 거슬러 올라가며 복제한다. 

copy_backward()도 원본과 대상 범위가 서로 달라야 하며, 일정한 제약 조건을 만족하면 중첩해도 된다. 앞의 예제를 copy()가 아닌 copy_backward()로 복제하도록 수정하면 다음과 같다. 여기서 세 번째 인수를 begin(vec2)가 아닌 end(vec2)로 지정한 점에 주목한다.

copy_backward(cbegin(vec1), cend(vec1), end(vec2));

copy_if() 알고리즘은 반복자 두 개로 지정한 입력 범위, 반복자 하나로 지정한 출력 대상 범위 그리고 프리디케이트를 인수로 받아 처리한다. 이 알고리즘은 지정한 프리디케이트를 만족하는 원소를 모두 대상 범위로 복제한다. 단 복제 과정에서 컨테이너를 생성하거나 확장하지는 않는다. 기존 원소를 바꾸기만 한다. 따라서 대상 범위는 복제할 원소를 모두 담을 수 있도록 충분히 커야 한다.

물론 원소를 복제한 뒤에는 마지막 원소를 복제한 지점 이후의 공간은 삭제하는 것이 좋다. 이를 위해 copy_if()는 대상 범위에 마지막으로 복제한 원소의 바로 다음 지점을 가리키는 반복자를 리턴한다. 다음 코드는 짝수만 vec2에 복제하는 예를 보여준다.

vector<int> vec1, vec2;
populateContainer(vec1);
vec2.resize(size(vex1));

auto endIterator = copy_if(cbegin(vec1), cend(vec1), begin(vec2), [](int i) { return i % 2 == 0; });
vec2.erase(endIterator, end(vec2));
for (const auto& i : vec2) { cout << i << " "; }

copy_n() 알고리즘은 원본에서 n개의 원소를 대상으로 복제한다. copy_n()의 첫 번째 매개변수는 시작 반복자, 두 번째 매개변수는 복제할 원소 수를 지정하는 정수, 세 번째 매개변수는 대상 반복자다.

copy_n() 알고리즘은 경곗값 검사를 하지 않는다. 따라서 시작 반복자부터 원소 수만큼 위칫값을 하나씩 증가하면서 복제해도 end()를 초과하지 않도록 검사하는 코드를 직접 작성해야 한다. 그렇지 않으면 예상치 못한 결과가 나올 수 있다. 예컨대 다음과 같다.

vector<int> vec1, vec2;
populateContainer(vec1);
size_t cnt = 0;
cout << "Enter number of elements you want to copy: ";
cin >> cnt;
cnt = min(cnt, size(vec1));
vec2.resize(cnt);
copy_n(cbegin(vec1), cnt, begin(vec2));
for (const auto& i : vec2) { cout << i << " "; }

move

표준 라이브러리는 move()와 move_backward()라는 두 가지 이동 알고리즘을 제공한다. 둘 다 9장에서 설명한 이동 의미론을 적용한다. 그러므로 이 알고리즘을 적용할 컨테이너의 원소 타입을 직접 정의하려면 원소 타입에 대한 클래스에 반드시 이동 대입 연산자를 구현해야 한다.

구체적인 방법은 다음 코드와 같다. 여기서 main() 함수는 먼저 MyClass 객체를 세 개 담은 vector를 생성한다. 그리고 인수를 하나만 받는 버전의 move() 함수로 좌측값(lvalue)을 우측값(rvalue)으로 변환한다. 이 함수는 <utility> 헤더 파일에 정의돼 있다. 반면 인수를 세 개 받는 표준 라이브러리의 move() 알고리즘은 컨테이너 사이에 원소를 이동시킨다. 이동 대입 연산자를 구현하고 인수를 하나만 받는 버전의 std::move() 사용법은 9장에서 설명했다.

class MyClass
{
public:
MyClass() = default;
MyClass(const MyClass& src) = default;
MyClass(string_view str) : mStr(str) {}
virtual ~MyClass() = default;

// 이동 대입 연산자
MyClass& operator=(MyClass&& rhs) noexcept
{
if (this == &rhs)
return;

mStr = std::move(rhs.mStr);
cout << "Move operator= (mStr=" << mStr << ")" << endl;
return *this;
}

void setString(string_view str) { mStr = str; }
string_view getString() const { return mStr; }

private:
string mStr;
};

int main()
{
vector<MyClass> vecSrc { MyClass("a"), MyClass("b"), MyClass("c") };
vector<MyClass> vecDst(vecSrc.size());
move(begin(vecSrc), end(vecSrc), begin(vecDst));
for (const auto& c : vecDst) { cout << c.getString() << " "; }
return 0;
}

Note) 9장에서 설명했듯이 move 연산을 수행하는 동안에는 원본 객체 중 일부는 유효한 상태에 있고 나머지는 불확실한 상태에 있게 된다. 앞의 예제에서 vecSrc에 대해 move 연산을 수행한 뒤 여기 담긴 모든 원소를 확실한 상태로 만들지 않았다면 그 원소를 사용하면 안 된다. 예컨대 아무런 사전 조건 없이 그 객체에 대해 setString()과 같은 메서드를 호출하면 안 된다.

move_backward() 알고리즘의 작동 방식도 move()와 비슷하다. 단 마지막 원소부터 첫 번째 원소 순으로 원소를 이동시킨다는 점이 다르다. move()와 move_backward()는 모두 일정 요건을 만족한다면 원본과 대상 범위가 겹쳐도 된다. 이 요건은 copy()와 copy_backward()의 조건과 같다.

replace

replace()와 replace_if() 알고리즘은 주어진 범위에서 값이나 프리디케이트로 지정한 조건에 일치하는 원소를 새 값으로 교체한다. 예컨대 replace_if()는 첫 번째와 두 번째 매개변수로 컨테이너의 원소 범위를 지정한다. 세 번째 매개변수는 true나 false를 리턴하는 함수나 람다 표현식이다. 여기서 true가 리턴되면 컨테이너의 값을 네 번째 매개변수로 지정한 값으로 교체하고, false로 리턴되면 원래대로 놔둔다.

다음과 같이 컨테이너에서 홀수 값을 가진 원소를 모두 0으로 교체하는 코드를 살펴보자.

vector<int> vec;
populateContainer(vec);
replace_if(begin(vec), end(vec), [](int i){ return i % 2 != 0; }, 0);
for (const auto& i : vec) { cout << i << " "; }

replace()와 replace_if()를 각각 변형한 replace_copy()와 replace_copy_if()도 있다. 이 알고리즘은 다른 대상 범위에 교체 결과를 복제한다. 새 원소를 충분히 담을 정도로 대상 범위가 커야 한다는 정메서 copy()와 비슷하다.

remove

 주어진 범위에서 특정한 조건을 만족하는 원소를 삭제하는 경우를 생각해 보자. 한 가지 방법은 표준 라이브러리 문서에 현재 컨테이너가 erase() 메서드를 제공한다고 나와 있다면 모든 원소에 대해 반복문을 돌면서 조건에 일치하는 원소에 대해 erase()를 호출하는 것이다. erase() 메서드를 제공하는 컨테이너의 예로 vector가 있다.

하지만 vector 컨테이너를 이렇게 처리하면 굉장히 비효율적이다. vector에서 메모리를 연속적으로 사용하기 위해 메모리 연산이 상당히 ㅁ낳이 발생하기 때문에 제곱 복잡도의 성능이 나온다. 게다가 에러가 발생하기도 쉽다.

(예시 생략)

이렇게 구현하면 성능이 상당히 떨어지기 때문에 바람직하지 않다. 이 문제는 소위 remove-erase 패턴으로 구현하는 것이 좋다. 그러면 선형 시간에 처리할 수 있다.

표준 라이브러리 알고리즘은 컨테이너를 다룰 때 반복자 인터페이스로만 접근한다. 그래서 remove() 알고리즘은 컨테이너에서 원소를 직접 삭제하지 않고, 주어진 값이나 프레디케이트를 만족하는 원소를 그렇지 않은 원소와 교체한다. 이 작업은 이동 대입 연산으로 처리한다.

그러면 주어진 범위가 두 집합으로 분할된다. 하나는 그대로 유지할 원소 집합이고, 다른 하나는 삭제할 원소 집합이다. remove()는 삭제할 범위의 첫 번째 원소를 가리키는 반복자를 리턴한다. 이 원소를 컨테이너에서 실제로 삭제하려면 먼저 remove() 알고리즘부터 적용한 뒤 리턴된 반복자를 이용하여 컨테이너에 대해 erase()를 호출해서 반복자가 가리키는 원소들을 모두 지운다. 

이것이 remove-erase 패턴이다. 예컨대 string 원소에 대한 vector에서 공백 string을 제거하는 함수를 살펴보자.

void removeEmptyStrings(vector<string>& strings)
{
auto it = remove_if(begin(strings), end(strings), [](const string& str){ return str.empty(); });

// 제거된 원소를 모두 지운다.
strings.erase(it, end(strings));
}

int main()
{
vector<string> myVector = { "", "one", "", "two", "three", "four" };

for (auto& str : myVector) { cout << "\"" << str << "\"";
cout << endl;

removeEmptyStrings(myVector);

 for (auto& str : myVector) { cout << "\"" << str << "\"";
cout << endl;

return 0;
}

Caution) remove-erase 패턴으로 구현할 때 반드시 erase()의 두 번째 인수를 지정해야 한다. 깜박잊고 erase()에 두 번째 인수를 지정하지 않으면 컨테이너에서 원소 하나만 삭젷나다. 즉, 첫 번째 인수로 전달한 반복자가 가리키는 원소만 삭제된다.

remove()와 remove_if()를 변형한 remove_copy()와 remove_copy_if()란 알고리즘도 있다. 이 알고리즘은 원본 범위를 변경하지 않는다. 대산 원소를 모두 다른 대상 범위에 복제한다. 대상 범위에 새 원소를 추가할 만큼 공간이 충분해야 한다는 점에서 copy()와 비슷하다.

Note) remove() 계열의 함수는 원소를 제거하는 과정에서 컨테이너에 남아 있는 원소의 순서를 그대로 유지한다는 점에서 안정적인 알고리즘이라 부른다.

unique

unique() 알고리즘은 remove()의 특수한 버전으로서, 같은 원소가 연달아 나오는 부분을 모두 삭제한다. list 컨테이너는 unique()라는 메서드를 통해 이 알고리즘과 똑같은 기능을 제공한다. unique()는 주로 정렬 컨테이너에 대해 사용하지만, 비정렬 컨테이너에도 적용할 수 있다.

unique()의 기본 버전은 그 자리에서 직접 원소를 제거하지만, 대상 범위에 결과를 복제하는 unique_copy()라는 버전도 있다.

sample

sample() 알고리즘은 인수로 지정한 원본 범위에서 무작위로 n개의 원소를 골라서 리턴하고 이를 대상 범위에 저장한다. 이 알고리즘은 다섯 가지 매개변수를 받는다.

  • 샘플링할 범위를 나타내는 시작과 끝 반복자
  • 무작위로 고른 원소를 저장할 대상 범위의 시작 반복자
  • 고를 원소의 수
  • 무작위수 생성 엔진
vector<int> vec { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
const size_t numberOfSamples = 5;
vector<int> samples(numberOfSamples);

random_device seeder;
const auto seed = seeder.entropy() ? seeder() : time(nullptr);
default_random_engine engine(static_cast<default_random_engine::result_type>(seed));

for (int i = 0; i < 6; i++)
{
sample(cbegin(vec), cend(vec), begin(samples), numberOfSamples, engine);

for (const auto& sample : samples) { cout << sample << " "; }
cout << endl;
}

reverse

reverse() 알고리즘은 주어진 범위에 있는 원소의 순서를 반대로 바꾼다. 범위의 첫 번째 원소를 마지막 원소와 바꾸고, 두 번째 원소를 끝에서 두 번째 원소와 바꾸는 식으로 진행한다.

reverse()의 기본 버전은 원본을 바로 수정하며 범위를 표현하는 시작 반복자와 끝 반복자를 인수로 받는다. 이와 달리 reverse_copy()는 결과를 대상 범위에 복제하며 원본 범위에 댛나 시작과 끝 반복자와 대상 범위에 대한 시작 반복자를 인수로 받는다. 여기서 대상 범위는 반드시 새 원소를 담을 만큼 공간이 넉넉해야 한다.

shuffle

shuffle() 알고리즘은 주어진 범위의 원소를 무작위 순으로 재정렬하며 성능은 선형 시간이다. 이 알고리즘은 카드를 섞는 것과 같은 작업에 유용하다. shuffle()은 재정렬할 범위를 나타내느 시작과 끝 반복자, 무작위수를 생성하는 방법을 지정하는 균등 분포 무작위수 생성기(uniform random number generator)를 인수로 받는다.

연산 알고리즘

표준 라이브러리에서 제공하는 연산 알고리즘은 for_each()와 for_each_n() 뿐이다. for_each_n()은 C++ 17부터 새로 추가됐다.

for_each() 알고리즘은 주어진 범위에 있는 원소마다 콜백을 실행시키고, for_each_n() 알고리즘은 주어진 범위에 있는 원소 중에서 첫 번째부터 n 번째 원소까지 콜백을 실행한다. 이때 컨테이너의 원소에 대해 처리할 작업은 간단한 함수 콜백이나 람다 표현식으로 정의한다. 

여기서는 단지 이런 알고리즘이 있다는 사실을 알려주기 위해 소개했다. 대부분 범위 기반 for 문을 사용하는 것이 코드를 작성하기도 쉽고 읽기도 쉽다.

for_each

다음 예제는 제네릭 람다 표현식으로 map에 있는 원소를 화면에 출력한다.

map<int, int> myMap = { { 4, 40 }, { 5, 50 }, { 6, 60 } };
for_each(cbegin(myMap), cend(myMap), [](const auto& p) { cout << p.first << "->" << p.second << endl; });

(이하 예시 생략)

for_each_n

for_each_n() 알고리즘은 주어진 범위의 시작 반복자, 반복할 원소 수, 함수 콜백을 인수로 받아서 ‘시작 지점 + n’ 위치를 가리키는 반복자를 리턴한다. 이 알고리즘도 경곗값 검사를 하지 않는다.

예컨대 map의 첫 번째와 두 번째 원소에 대해서만 반복하려면 다음과 같이 작성한다.

map<int, int> myMap = { { 4, 40 }, { 5, 50 }, { 6, 60 } };
for_each_n(cbegin(myMap), 2, [](const auto& p) { cout << p.first << "->" << p.second << endl; })

swap()과 exchange() 알고리즘

swap()

std::swap()은 두 값을 효율적으로 맞바꾼다. 이때 가능하다면 이동 의미론을 적용한다.

int a = 11;
int b = 22;
swap(a, b);

exchange()

std::exchage()는 기존 값을 새 값으로 교체한 후 기존 값을 리턴한다.

int a = 11;
int b = 22;
int returnedValue = exchange(a, b);

exchange()는 이동 대입 연산자를 구현할 때 유용하다. 이동 대입 연산자는 원본 객체에서 대상 객체로 데이터를 이동해야 한다. 이때 원본 객체에 있던 데이터를 널로 만들어야 할 때가 많은데 대부분 다음 코드에 나온 방식으로 처리한다. 여기서 Foo에 어떤 메모리에 대한 포인터를 갖는 mPtr란 데이터 멤버가 있다고 하자.

Foo& operator=(Foo&& rhs) noexcept
{
// 자신을 대입하는 것이 아닌지 검사한다.
if (this == &rhs) { return *this; }

// 예전 메모리를 해제한다.
delete mPtr;
mPtr = nullptr;

// 데이터를 이동시킨다.
mPtr = rhs.mPtr; // 데이터를 원본에서 대상으로 옮긴다.
rhs.mPtr = nullptr; // 원본에 있던 데이터를 널로 만든다.

return *this;
}

위 메서드의 마지막에서 mPtr과 rhs.mPtr에 대입하는 연산을 다음과 같이 exchange()로 구현할 수 있다.

Foo& operator=(Foo&& rhs) noexcept
{
// 자신을 대입하는 것이 아닌지 검사한다.
if (this == &rhs) { return *this; }

// 예전 메모리를 해제한다.
delete mPtr;
mPtr = nullptr;

// 데이터를 이동시킨다.
mPtr = exchange(rhs.mPtr, nullptr); // 이동 후 널로 만든다.

return *this;
}

분할 알고리즘

partition_copy()는 원본에 있는 원소를 복제해서 서로 다른 두 대상으로 분할한다. 이때 둘 중 어느 대상에 원소를 보낼지는 프레디케이트의 실행 결과가 true냐 false냐에 따라 달라진다.

partition_copy()는 반복자 쌍을 리턴한다. 그중 하나는 첫 번째 대상 범위에서 마지막으로 복제한 원소의 바로 다음 지점을 가리키는 반복자고 다른 하나는 두 번째 대상에서 마지막으로 복제한 원소의 바로 다음 지점을 가리키는 반복자다. 이렇게 리턴된 반복자를 erase()와 함께 사용해서 두 대상 범위에서 초과된 원소를 삭제하게 만들 수 있다.

구체적인 방법은 앞서 본 copy_if() 예제와 같다. 다음 코드는 사용자로부터 정수의 개수를 입력받아서 대상 범위를 짝수에 대한 vector와 호룻에 대한 vector로 분할한다.

vector<int> vec1, vecOdd, vecEven;
populateContainer(vec1);
vecOdd.resize(size(vec1));
vecEven.resize(size(vec1));

auto pairIters = partition_copy(cbegin(vec1), cend(vec1), begin(vecEven), vegin(vecOdd), [](int i){ return i % 2 == 0; });

vecEven.erase(pairIters.first, end(vecEven));
vecOdd.erase(pairIters.second, end(vecOdd));

cout << "Even numbers: ";
for (const auto& i : vecEven) { cout << i << " "; }
cout << "Odd numbers: ";
for (const auto& i : vecOdd) { cout << i << " "; }

partition() 알고리즘은 프레디케이트에서 true를 리턴하는 원소가 false를 리턴하는 원소보다 앞에 나오도록 정렬한다. 이때 두 개로 분할된 범위 내에서는 원래 순서가 유지되지 않는다. 다음 코드는 vector에 있는 원소 중 짝수를 모두 홀수 앞에 나오도록 분할하는 예를 보여준다.

vector<int> vec;
populateContainer(vec);
paritition(begin(vec), end(vec), [](int i){ return i % 2 == 0; });
cout << "Partitioned result: ";
for (const auto& i : vec) { cout << i << " "; }

정렬 알고리즘

정렬 알고리즘은 컨테이너에 담긴 원소가 특정한 조건을 기준으로 순서에 맞게 유지하도록 재배치 한다. 그래서 순차 컨테이너에만 정렬 알고리즘을 적용할 수 있다. 항상 원소를 정렬된 상태로 유지하는 정렬 연관 컨테이너에는 적용할 수 없다. 비정렬 연관 컨테이너에도 적용할 수 없다. 원래부터 정렬을 하지 않기 때문이다.

list나 forward_list와 같은 일부 컨테이너는 자체적으로 정렬 메서드를 제공한다. 그래서 제네릭 정렬 알고리즘보다 자체 메서드로 구현하는 것이 훨씬 효율적이다. 제네릭 정렬 알고리즘은 주로 vector, deque, array, C 스타일 배열에 적합하다.

sort() 알고리즘은 주어진 범위에 있는 원소를 O(N log N) 시간에 정렬한다. sort()는 기본적으로 operator<를 이용해서 주어진 범위를 오름차순으로 정렬한다. 순서를 바꾸고 싶다면 greater와 같은 다른 비교자를 지정하면 된다.

sort()를 변형한 stable_sort()란 알고리즘도 있다. 이 알고리즘은 주어진 범위에서 같은 원소에 대해서는 원본에 나온 순서를 그대로 유지한다. 그러므로 sort() 알고리즘보다 성능이 좀 떨어진다.

vector<int> vec;
populateContainer(vec);
sort(begin(vec), end(vec), greater<>());

또한 표준 라이브러리는 is_sorted(), is_sorted_until()도 제공한다. is_sorted()는 주어진 범위가 정렬된 상태면 true를 리턴하고, is_sorted_until()은 반복자를 리턴하는데, 이 반복자 앞에 나온 원소까지는 모두 정렬된 상태다.

이진 탐색 알고리즘

탐색 알고리즘 중에는 정렬된 시퀀스에 대해서만 적용하거나 검색 대상을 기준으로 분할된 시퀀스에 대해서만 적용하는 이진 탐색 알고리즘이 있다. 이러한 알고리즘에는 binary_search(), lower_bound(), upper_bound(), equal_range() 등이 있다. 

lower_bound() 알고리즘은 정렬된 범위에서 주어진 값보다 작지 않은 원소 중에서 첫 번째 원소를 찾는다. 이 알고리즘은 주로 정렬된 vector에 새 값을 추가해도 계속 정렬된 상태를 유지할 수 있는 적절한 추가 지점을 찾을 때 사용한다.

(예시 코드 생략)

binary_search() 알고리즘은 선형 시갑노다 빠른 로그 시간에 원소를 검색한다. 이 알고리즘은 탐색을 범위를 지정하는 시작과 끝 반복자, 탐색할 값 그리고 옵션으로 비교 콜백을 인수로 받는다. 주어진 범위에서 값을 찾으면 true를 리턴하고 그렇지 않으면 false를 리턴한다.

(예시 코드 생략)

집합 알고리즘

집합 알고리즘은 정렬된 범위라면 어떤 것에도 적용할 수 있다. includes() 알고리즘은 부분집합을 판별하는 표준 함수로서 인수로 주어진 두 (정렬된) 범위 중에서 한쪽의 원소가 다른 쪽 범위에 모두 포함되는지 검사한다. 포함 관계를 판단할 때는 순서를 고려하지 않는다.

set_union(), set_intersection(), set_difference(), set_symmetric_difference() 알고리즘은 각각 수학의 집합에서 합집합(union), 교집합(intersection), 차집합(difference), 대칭 차집합(symmetric difference)을 구현한 것이다.

Caution) 집합 연산을 수행할 때 연산의 결과를 담을 범위는 연산 결과로 나온 원소를 모두 담을만큼 충분히 크게 지정해야 한다. set_union()과 set_symmetric_difference()의 결과를 담으려면 적어도 입력한 두 범위의 크기를 더한 만큼의 공간을 확보해야 한다. set_intersection()의 결과를 담으려면 두 입력 범위의 크기 중 작은 것만큼 set_difference()의 결과를 담으려면 첫 번째 입력 범위의 크기만큼 확보해야 한다.

Caution) set과 같은 연관 컨테이너에서 구한 반복자 범위에는 결과를 저장할 수 없다. 연관 컨테이너는 키를 변경할 수 없기 때문이다.

(예시 코드 생략)

merge() 알고리즘을 사용하면 정렬된 두 범위를 하나로 합칠 수 있다. 이때 정렬 순서는 그대로 유지된다. 그 결과 두 범위에 있던 원소를 모두 담은 정렬된 범위가 리턴되며, 선형 시간에 처리된다. 이 알고리즘은 다음과 같은 매개변수를 받는다.

  • 첫 번째 원본 범위에 대한 시작과 끝 반복자
  • 두 번째 원본 범위에 대한 시작과 끝 반복자
  • 대상 범위에 대한 시작 반복자
  • 비교 연산을 수행하는 콜백(옵션)

두 범위를 하나로 합친 결과를 sort()로 정렬해도 merge()와 똑같은 효과를 낼 수 있지만 성능이 O(N log N)이므로 선형 복잡도를 갖는 merge()에 비해 성능이 떨어진다.

Caution) merge()의 결과를 담을 수 있도록 대상 범위의 공간을 넉넉히 확보해야 한다.

(예시 코드 생략)

최대/최소 알고리즘

min()과 max() 알고리즘은 모든 타입의 원소를 operator< 또는 사용자가 정의한 이항 프리디케이트로 비교해서 각각 최소 원소와 최대 원소에 대한 const 레퍼런스를 리턴한다. minmax() 알고리즘은 두 개 이상의 원소 중에서 최솟값과 최댓값을 쌍으로 묶어서 리턴한다. 이러면 최대/최소 알고리즘은 반복자를 매개변수로 리턴받지 않는다.

반면 min_element(), max_element(), minmax_element()는 반복자로 지정한 범위에 대해 주어진 작업을 처리한다.

Note) 떄로는 비표준 매크로로 최솟값이나 최댓값을 구하는 코드를 볼 떄가 있다. 예컨대 GNU C 라이브러리(glibc)는 MIN()과 MAX()라는 매크로를 제공하고, 윈도우에서도 Windows.h 헤더 파일에 min()과 max()란 이름의 매크로를 제공한다. 이들은 매크로이기 때문에 주어진 인수를 두 번 평가할 가능성이 있는 반면 std::min()과 std::max()는 주어진 인수를 단 한 번만 평가한다. 항상 C++ 버전의 std::min()과 std::max()를 사용하기 바란다.

std::clamp()는 <algorithm>에 정의된 간단한 헬퍼 함수로서, 주어진 값(v)이 최솟값(lo)과 최댓값(hi) 사이에 있는지 검사한다. v < lo면 lo에 대한 레퍼런스를 리턴하고, v > hi면 hi에 대한 레퍼런스를 리턴한다. 나머지 경우에는 v에 대한 레퍼런스를 리턴한다.

(예시 코드 생략)

병렬 알고리즘

C++ 17부터 성능 향상을 위한 병렬 처리 알고리즘이 표준 라이브러리에 60개 이상 추가됐다. 대표적인 예로 for_each(), all_of(), copy(), count_if(), find(), replace(), search(), sort(), transform() 등이 있다. 병렬 실행을 지원하는 알고리즘은 소위 실행 정책(execution policy)이라 부르는 옵션을 첫 번째 매개변수로 받는다.

이러한 실행 정책을 이용해서 주어진 알고리즘을 병렬로 실행할지 아니면 벡터 방식으로 순차적으로 처리할지 결정한다. 실행 정책은 크게 세 가지가 있으며, 각 타입마다 전역 인스턴스도 있다. 모두 <execution> 헤더 파일의 std::execution 네임스페이스 아래에 정의돼 있다.

실행 정책 타입 전역 인스턴스 설명
sequenced_policy seq 병렬로 실행하지 않는다.
parallel_policy par 병렬로 실행한다.
parallel_unsequenced_policy par_unseq 병렬 실행과 벡터 실행 모두 가능하다. 또한 슬드 사이에 실행을 이어서 할 수 있다.

표준 라이브러리의 구현만다 실행 정책을 얼마든지 추가할 수 있다.

여기서 parallel_unsequenced_policy로 알고리즘을 실행하는 경우에 대해 좀 더 설명할 필요가 있다. 콜백을 호출하는 함수 호출은 순차적이지 않고 서로 교차해서(interleaved) 실행될 수 있다. 다시 말해 함수 콜백에서 할 수 있는 일에 제약사항이 많다.

예컨대 메모리를 할당하거나 해제할 수 없고, 뮤텍스를 획득할 수 없고, 잠금에 재약 없는 std::atomic을 사용할 수 없다. 나머지 정책은 함수 호출을 순차적으로 실행할 수 있지만 정확한 순서는 보장할 수 없다. 이런 정책은 함수 콜백에서 할 수 있는 일에 대해 제약사항을 두지 않는다.

병렬 ㅇ라고리즘은 데이터 경쟁(data race)이나 데드락(deadlock)에 대한 대비책을 따로 제공하지 않기 때문에 알고리즘을 병렬로 실행할 때 이러한 상황에 직접 대처해야 한다. 데이터 경쟁이나 데드락을 방지한느 방법은 23장에서 자세히 설명한다.

예컨대 vector에 담긴 원소들을 병렬 정책을 지정해서 정렬하려면 다음과 같이 작성한다.

sort(std::execution::par, begin(myVector), end(myVector));

수치 처리 알고리즘

inner_product

inner_product()는 <numeric> 헤더 파일에 정의돼 있으며, 두 시퀀스(벡터)의 내적을 구한다.

(예시 코드 생략)

iota

iota() 알고리즘도 <numeric> 헤더 파일에 정의돼 있으며, 주어진 범위에서 주어진 값으로 시작해서 operator++로 값을 순차적으로 생성하는 방식으로 값에 대한 시퀀스를 만든다. 다음 코드는 이 알고리즘을 정수 타입 원소에 대한 vector에 적용하는 예를 보여준다. 참고로 정수가 아닌 다른 타입에 대해서도 operator++만 구현돼 있으면 얼마든지 적용할 수 있다.

vector<int> vec(10);
iota(begin(vec), end(vec), 5);
for (auto& i : vec) { cout << i << " "; }

// 실행 결과
// 5 6 7 8 9 10 11 12 13 14

gcd()와 lcm()

인수로 지정한 두 정수에 대해 gcd()는 최대공약수(greatest common divisor), lcm은 최소공배수(least common multiple)을 리턴한다. 둘다 <numeric>에 정의돼 있다.

(예시 코드 생략)

reduce()

std::accumulate() 알고리즘은 표준 라이브러리 알고리즘 중에서 병렬 실행을 지원하지 않는 몇 안되는 것 중 하나다. 하지만 새로 추가된 std::reduce() 알고리즘에 병렬 실행 옵션을 지정해서 주어진 값의 합으로 구할 수 있다. 예컨대 다음에 나온 두 줄 모두 벡터의 합을 구하지만, reduce()는 병렬 및 벡터 버전으로 구동하여 앞줄보다 실행 속도가 훨씬 빠르다. 성능 향상의 폭은 입력 범위가 클수록 두드러진다.

double result1 = std::accumulate(cbegin(vec), cend(vec), 0.0);
double result2 = std::reduce(std::execution::par_unseq, cbegin(vec), cend(vec));

accumulate()와 reduce()는 초깃값이 Init이고, 이항 연산자 \Theta 가 주어졌을 때 다음 수식에 따라 [x_{0}, x_{n}) 범위에 있는 원소의 합을 구한다.

Init \Theta x_{0} \Theta x_{1} ... \Theta x_{n-1}

transform_reduce()

std::inner_product() 역시 병렬 실행을 지원하지 않는다. 이 알고리즘 대신 transform_reduce()를 사용하면 옵션으로 병렬 실행을 지정해서 내적을 계산할 수 있다. 사용법은 reduce()와 거의 같다.

transform_reduce()는 초깃값이 Init이고 단항 함수 f 와 이항 연산자 \Theta 가 주어졌을 때 다음 수식에 따라 [x_{0}, x_{n}) 범위에 있는 원소의 합을 구한다.

Init \Theta f(x_{0}) \Theta f(x_{1}) ... \Theta f(x_{n-1})

스캔 알고리즘

C++ 17부터 네 가지 스캔 알고리즘(exclusive_scan(), inclusive_scan(), transform_exclusive_scan(), transform_inclusive_scan())을 제공한다.

다음 표는 [x_{0}, x_{n}) 범위에 있는 원소에 대해 초깃값으로 Init(partial_sum()에 대해서는 0)을 지정하고, 연산자로 \Theta 를 지정했을 때 [y_{0}, y_{n}) 범위에 있는 원소의 합을 exclusive_scan()으로 구하는 과정과 inclusive_scan()/partial_sum()으로 구하는 과정을 보여주고 있다.

exclusive_scan() inclusive_scan()/partial_sum()
y_{0} = Init y_{0} = Init \Theta x_{0}
y_{1} = Init \Theta x_{0} y_{1} = Init \Theta x_{0} \Theta x_{1}
y_{2} = Init \Theta x_{0} \Theta x_{1}
y_{n-1} = Init \Theta x_{0} \Theta x_{1} ... \Theta x_{n-1}
y_{n-1} = Init \Theta x_{0} \Theta x_{1} ... \Theta x_{n-2}  

transform_exclusive_scan()과 transform_inclusive_scan()은 모두 합을 구하기 전에 원소에 단항 함수를 적용한다. 이는 transform_reduce()가 리듀스 연산을 적용하기 전에 원소마다 단항 함수를 적용하는 것과 비슷하다.

여기서 스캔 함수는 모두 병렬 실행 옵션이 있다는 점에 주목한다. 각 알고리즘의 평가 순서는 정확히 알 수 없다(비결정적, non-deterministic이다). 반면 partial_sum()과 accumulate()는 왼쪽부터 오른쪽 순으로 평가된다. 바로 이런 이유 때문에 partial_sum()과 accumulate()를 병렬로 실행할 수 없다.

알고리즘 예제: 선거인 명부 검사

(생략)

[ssba]

The author

지성을 추구하는 사람/ suyeongpark@abyne.com

댓글 남기기

이 사이트는 스팸을 줄이는 아키스밋을 사용합니다. 댓글이 어떻게 처리되는지 알아보십시오.