아이버 호튼 지음 / 조현태 옮김
길벗
2016
Using the C++ Standard Template Libraries
Ivor Horton
Apress
2015
1장. 표준 템플릿 라이브러리
1장에서는 표준 템플릿 라이브러리에 내재된 기본 개념부터 설명하겠다.
- STL에는 무엇이 있는가?
- 템플릿을 정의하고 사용하는 법
- 컨테이너는 무엇인가?
- 반복자는 무엇이고 어떻게 사용하는가?
- 스마트 포인터의 중요성과 컨테이너를 사용하는 법
- 알고리즘은 무엇이고 응용하는 방법
- 수치 라이브러리가 제공하는 기능
- 함수 객체는 무엇인가?
- 람다 표현식을 정의하고 사용하는 방법
이 장에서는 STL을 지탱하는 기본 아이디어도 소개하지만, 이어지는 장에서 자주 사용하기 때문에 익숙해져야 할 C++ 언어의 기능도 소개할 것이다. 여러분이 이런 주제에 익숙하다면 건너뛰어도 좋다.
1.1 기본 아이디어
STL은 데이터를 구성하고 처리하는 강력한 도구다. STL은 모두 템플릿으로 정의되어 있어서 최소 요구 조건만 맞으면 어떤 타입의 데이터에도 쓸 수 있다. STL은 개념적으로는 크게 네 가지 라이브러리로 나눌 수 있다.
- 컨테이너 라이브러리에는 데이터를 저장하고 관리하는 데 쓸 수 있는 컨테이너가 정의되어 있다.
- 반복자 라이브러리에는 반복자(iterator)가 정의되어 있으며 반복자는 포인터처럼 동작하는 객체로 컨테이너에 있는 객체의 순차열을 참조할 때 사용된다.
- 알고리즘 라이브러리에는 컨테이너에 저장된 원소에 적용할 수 있는 알고리즘이 폭넓게 정의되어 있다.
- 수치 라이브러리에는 숫자와 관련된 기능이 폭넓게 정의되어 있으며 여기에는 컨테이너에 있는 원소에 수치 처리를 할 수 있는 기능이 포함되어 있다.
복잡하고 어려운 작업도 STL을 사용하면 코드 몇 줄로 정말 쉽게 처리할 수 있다. 다음 코드는 부동소수점 값들을 표준 입력으로 읽고 평균을 계산해서 출력한다.
std::vector<double> values;
std::cout << "값은 공백으로 구분해서 입력하세요. 종료하려면 Ctrl+Z를 입력하세요.\n";
values.insert(std::begin(values), std::istream_iterator<double>(std::cin), std::istream_iterator<double>());
std::cout << "평균값: " << (std::accumulate(std::begin(values), std::end(values), 0.0) / values.size()) << std::endl;
1.2 템플릿
템플릿은 함수나 클래스를 매개변수로 작성한 명세라 할 수 있다. 컴파일러는 템플릿을 사용해서 필요할 때 함수나 클래스 정의를 생성한다.
1.3 컨테이너
컨테이너는 객체를 일정한 방식으로 저장하고 조직화하는 객체를 말한다. 컨테이너를 사용한다는 건 데이터에 접근하기 위해 반드시 반복자를 사용한다는 것이므로 반복자도 이해해야 한다는 뜻이다. STL에서 제공하는 컨테이너는 다음과 같이 나눌 수 있다.
- 순차 컨테이너는 객체들을 선형으로 저장한다. 선형은 배열과 비슷하지만, 반드시 연속 메모리로 저장될 필요는 없다는 뜻이다. 멤버 함수를 호출하거나 반복자를 사용해서 객체들을 차례로 접근할수 있다.
- 연관 컨테이너는 객체들을 연관된 키와 함께 저장한다. 키를 이용해서 연관 컨테이너에서 객체를 가져온다.
- 컨테이너 어댑터는 순차 컨테이너나 연관 컨테이너에 저장된 데이터에 접근하는 다른 방법을 제공하는 어댑터 클래스 템플릿을 말한다.
객체들이 이동 시맨틱을 갖는 타입(주로 임시 객체)의 우측값이 아니면 모든 STL 컨테이너는 객체를 컨테이너에 저장할 때 복사본을 저장한다. STL에서는 이동 생성자와 이동 할당 연산자가 반드시 noexcept로 지정되어야 한다.
1.4 반복자
반복자는 포인터와 비슷하게 동작하는 클래스 템플릿 타입의 객체를 말한다. 반복자 iter가 유효 객체를 가리킨다면 *iter라고 쓰기만 해도 반복자 iter를 역참조해서 객체에 대한 참조를 얻을 수 있다. iter가 클래스 객체를 가리킨다면 객체의 멤버 member는 iter->member로 접근할 수 있다. 따라서 반복자는 포인터처럼 쓰면 된다.
반복자는 데이터에서 알고리즘을 분리해준다. 다시 말해 알고리즘은 컨테이너 내부에 데이터가 어떤 방식으로 구성되어 있는지 전혀 몰라도 된다. 반복자는 iterator 헤더에 정의된 템플릿 타입의 인스턴스지만, 컨테이너에 대해서도 알아야 하므로 컨테이너를 정의한 헤더들이 모두 포함되어 있다.
1.4.1 반복자 얻기
컨테이너의 반복자는 컨테이너 객체에서 begin()과 end() 멤버함수를 호출해서 얻을수 있다. 전역함수 begin()과 end()는 일반 배열이나 문자열 객체를 인수로 받아도 동작하며 반복자를 얻는 단일 방법을 제공한다.
배열, 컨테이너 또는 문자열 객체의 const 반복자를 반환하는 전역 함수 cbegin()과 cend()도 있다. 기억하라. const 반복자는 변경되지 말아야 할 것을 가리키지만, 반복자 자체는 바꿀 수 있다.
1.4.2 반복자 카테고리
모든 반복자 타입은 복사 생성자, 복사 할당 연산자, 소멸자를 가져야 한다. 반복자가 가리키는 객체들은 교환(swap)할 수 있어야 하며, 이에 대한 더 깊은 설명은 2장에서 할 것이다. 반복자는 기능 수준에 따라 5가지 카테고리로 나뉜다. 카테고리는 새로운 반복자 템플릿이 아니다. 반복자 타입이 지원하는 카테고리는 iterator 템플릿의 타입 매개변수에 쓰인 인수 값으로 식별할 수 있다.
컨테이너를 위해 얻을 수 있는 카테고리는 컨테이너의 종류에 따라 정해진다. 커테고리는 알고리즘이 반복자의 기능을 결정하게 도와준다. 알고리즘은 반복자 인수의 카테고리를 두가지 방식으로 이용할 수 있다. 첫번째는 연산에 필요한 최소 기능 요구 조건을 만족시켰는지 확인하는 방식이며 두번째는 반복자가 최소 요구 조건 이상을 충족한다면 알고리즘은 연산을 더 효율적으로 수행하기 위해 확장 기능을 사용하는 방식이다.
반복자 카테고리는 다음과 같이 5가지가 있다.
1. 입력 반복자(input iterator)는 객체에 대한 읽기 권한을 갖는다. iter가 입력 반복자라면 iter가 가리키는 값에 대한 참조를 얻는 *iter를 반드시 지원해야 한다. 입력 반복자는 한번만 읽을 수 있다. 즉, 한번 반복자를 증가시키면 반복자가 가리켰던 이전 원소에 접근할 수 없으며 이전 원소에 접근하려면 새 반복자를 써야 한다.
2. 출력 반복자(output iterator)는 객체에 대한 쓰기 권한을 갖는다. iter가 출력 반복자라면 새로운 값을 할당할 수 있으므로 *iter = new_value라고 쓸수 있다. 출력 반복자는 한번만 쓸 수 있다.
3. 순방향 반복자(forward iterator)는 입력 반복자와 출력 반복자의 기능에 몇 번이고 쓸 수 있는 기능을 더한 것이다. 따라서 원소를 읽거나 쓰는 작업에 슨방향 반복자를 몇 번이고 원하는 만큼 재사용할 수 있다.
4. 양방향 반복자(bidirectional iterator)는 순방향 반복자와 같은 기능에 역방향으로 이동할 수 있다.
5. 랜덤 액세스 반복자(random access iterator)는 양방향 반복자와 같은 기능에 원소들에 마음대로 접근할 수 있는 기능을 더한 것이다.
1.4.3 스트림 반복자
스트림 객체에서 지정된 타입의 데이터로 동작하는 스트림 반복자 객체를 생성할 수 있다. 즉, 데이터 타입이 반복자 템플릿 타입 매개변수가 되고, 스트림 객체는 생성자 인수가 된다. istream_iterator<T>는 istream에서 타입 T의 객체들을 읽을 수 있는 입력 반복자이며, istream은 파일 스트림이나 표준 입력 스트림 cin이 될 수 있다. 객체는 >> 연산자로 읽게 되며, 읽게 되는 객체의 타입은 반드시 >> 연산자를 지원해야 한다.
ostream_iterator는 istream_iterator와 보완 관계이며 ostream에 객체를 위한 한번 출력 기능을 제공하는 출력 반복자이다. 객체는 << 연산자로 쓴다.
1.4.4 반복자 어댑터
반복자 어댑터는 표준 반복자에 특별한 동작을 제공하는 클래스 템플릿이므로 반복자 템플릿에서 파생되었다. 어댑터 클래스 템플릿에서 정의하는 반복자는 reverse_iterator, insert_iterator, move_iterator 3가지다.
1.5 반복자에 쓰이는 연산
iterator 헤더에는 반복자에 쓰이는 연산을 정의한 4가지 함수 템플릿이 정의되어 있다.
- advance()는 첫번째 인수로 받은 반복자를 두번째 인수로 지정한 숫자만큼 증가시킨다.
- distance()는 두 반복자가 지정한 범위에 있는 원소들의 개수를 반환한다.
- next()는 첫번째 인수로 받은 반복자를 두번째 인수로 지정한 숫자만큼 증가시킨 반복자를 반환한다.
- prev()는 첫번째 인수로 받은 반복자를 두번째 인수로 지정한 숫자만큼 감소시킨 반복자를 반환한다.
1.6 스마트 포인터
1.6.1 unique_ptr<T> 포인터 사용하기
unique_ptr<T> 객체는 주소 하나를 유일하게 저장할 수 있다. 따라서 주소가 가리키는 객체를 unique_ptr<T> 객체가 독점적으로 소유한다. unique_ptr<T> 객체가 소멸될 때 해당 객체도 같이 소멸된다.
std::unique_ptr<std::string> pname {new std::string {"Algernon"}};
auto pname2 = std::make_unique<std::string>("Algernon");
1.6.2 shared_ptr<T> 객체 사용하기
shared_ptr<T> 객체는 다음과 같이 정의할 수 있다.
std::shared_ptr<double> pdata {new double{999.0}};
auto pdata = std::make_shared<double>(999.0);
std::shared_ptr<double> pData2 {pdata};
1.6.3 weak_ptr<T> 포인터
weak_ptr<T> 객체는 shared_ptr<T> 객체로만 생성할 수 있다. weak_ptr<T> 포인터는 자유 공간에 생성된 객체들의 인스턴스 주소를 클래스 멤버로 저장할 때 주로 사용된다.
auto pData = std::make_shared<X>();
std::weak_ptr<X> pwData {pData};
std::weak_ptr<X> pwData2 {pwData};
약한 포인터로는 할 수 있는게 많지 않다. 즉, 약한 포인터가 가리키는 객체는 역참조해서 접근할 수 없다.
- 약한 포인터가 가리키는 객체의 유무만 테스트할 수 있다. 즉, 약한 포인터가 가리키는 shared_ptr<T>가 여전히 거기에 있는지만 확인할 수 있다.
- weak_ptr<T> 객체에서 shared_ptr<T> 객체를 생성할 수 있다.
1.7 알고리즘
알고리즘은 반복자 쌍으로 지정한 객체의 범위에 적용할 수 있는 계산 함수와 알고리즘 함수로 되어 있다. 알고리즘은 데이터 원소들을 반복자로 접근하기 때문에 알고리즘은 데이터가 저장되는 위치에 관여하지 않는다.
알고리즘은 크게 나누면 다음과 같이 분류할 수 있다.
1. 변경 불가 순차열 연산(non-mutating sequence operation)은 대상 순차열의 내용을 변경하지 못한다.
2. 변경 가능 순차열 연산(mutation sequence operation)은 순차열의 내용을 변경한다.
3. 정렬, 병합, 이와 관련된 알고리즘은 순차열의 순서를 변경한다.
1.8 함수를 인수로 전달하기
다른 함수에 함수를 인수로 넘기는 방법은 3가지가 있다.
- 함수 포인터를 사용한다.
- 함수 객체를 인수로 전달한다.
- 람다 표현식을 인수로 전달한다.
1.8.1 함수 객체
함수 객체(종종 functor라 한다)는 함수 호출 연산자 operator()()를 오버로딩한 클래스의 객체를 말한다. 함수 객체는 원시 함수 포인터를 사용하는 것보다 더 효율적으로 함수를 다른 함수에 인수로 전달하는 방법을 제공한다.
1.8.2 람다 표현식
람다 표현식은 익명 함수를 정의한다. 람다 표현식으로 정의한 함수는 람다 표현식 바깥 범위에 있는 변수들을 캡처하고 접근할 수 있다는 점에서 일반 함수와 다르다.
1.9 요약
2장. 순차 컨테이너
2장에서는 일상적으로 사용하는 컨테이너 중에 가장 자주 사용하게 될 순차 컨테이너를 소개한다.
2.1 순차 컨테이너
순차 컨테이너는 원소들을 선형적인 순차열(linear sequence)로 저장한다. 선형적이라는 건 원소들을 정렬하지 않는다는 뜻이다. 원소들은 저장한 순소대로 배열된다. 5가지 표준 순차 컨테이너가 있고, 각각은 조금씩 다른 특성을 갖는다.
- array<T, N> 컨테이너는 타입 T 객체, 고정 길이 N으로 된 순차열을 정의한다. 원소들을 추가하거나 삭제할 수 없다.
- vector<T> 컨테이너는 타입 T 객체, 가변 길이 순차열을 정의하며 필요할 때 자동으로 길이가 늘어난다. 순차열의 끝에서만 원소를 추가하거나 삭제할 수 있다.
- deque<T> 컨테이너는 자동으로 길이가 늘어나는 가변 길이 순차열을 정의한다. 순차열의 양쪽 끝에서 원소를 추가하거나 삭제할 수 있다.
- list<T> 컨테이너는 이중 연결 리스트로 된 타입 T 객체의 가변 길이 순차열을 정의한다. 순차열의 모든 위치에서 원소를 추가하거나 삭제할 수 있다.
- forward_list<T>는 단일 연결 리스트로 된 타입 T 객체의 가변 길이 순차열을 정의한다. 순방향 리스트 컨테이너는 리스트 컨테이너보다 빠르고 더 적은 메모리를 사용하지만, 순차열에 있는 원소에 접근할 때 첫번째 원소에서만 접근을 시작해야 한다.
2.1.1 컨테이너의 공통 함수 멤버
2.2 array<T, N> 컨테이너 사용하기
array<T, N> 템플릿은 표준 배열에 해당하는 컨테이너 타입을 정의한 것이다. 타입 T, 원소의 개수가 N개인 순차열이므로 원소의 타입과 개수를 지정하는 점을 제외하면 일반 배열과 같다. 원소를 추가하거나 삭제할 수 없다. 템플릿 인스턴스의 원소들은 내부에서 표준 배열로 저장된다. array 컨테이너는 표준 배열과 비교해도 오버페드가 매우 작지만, 두가지 장점이 있다. 하나는 at()을 사용해 원소에 접근하면 범위를 벗어난 인덱스에 접근하는지 탐지할 수 있다는 것이다. 다른 하나는 컨테이너에 몇개의 원소가 있는지 알고 있으므로 함수에 원소의 개수를 별도로 지정하지 않아도 array 컨테이너를 인수로 전달할 수 있다는 것이다.
2.2.1 원소에 접근하기
표준 배열처럼 [과 ]사이에 인덱스를 넣은 표현식으로 array 컨테이너의 원소를 접ㅈ근하고 사용할 수 있다.
std::array<double, 100> values {0.5, 1.0, 1.5, 2.0};
values[4] = values[3] + 2.0 * values[1]; // 인덱스 경계 검사 안함.
values.at(4) = values.at{=(3}=) + 2.0 * values.at(1); // 인덱스 경계 검사 함.array 컨테이너에서 n번째 원소에 접근하난 get<n>() 헬퍼 함수를 위한 함수 템플릿도 정의되어 있다. 템플릿 매개변수의 인수는 컴파일 타임에 평가될 수 있는 상수 표현식이어야 하므로 루프 변수로는 쓸 수 없다. get<n>() 템플릿은 런타임 검사 없이 인덱스 값으로 원소에 접근할 수 있다. 런타임 검사가 없으므로 인덱스 값이 범위를 벗어나서는 안된다.
2.2.2 array 컨테이너에서 반복자 사용하기
array 템플릿에는 begin(), end() 멤버가 정의되어 있다. begin(), end()는 예상대로 첫번째 원소와 마지막 원소에서 하나 더 뒤를 가리키는 랜덤 액세스 반복자를 각각 반환한다.
2.2.3 array 컨테이너의 비교
두 array<T, N> 컨테이너의 크기가 같고, 원소들이 같은 타입이고, 이 타입이 비교 연산을 지원한다면 비교 연산자를 사용해 두 컨테이너 전체를 비교할 수 있다.
2.3 vector<T> 컨테이너 사용하기
vector<T>는 타입 T를 원소로 갖는 순차 컨테이너이다. array<T, N> 컨테이너와 같지만, 더 많은 원소를 수용할 수 있도록 크기가 자동으로 커진다는 차이점이 있다. vector에 현재 할당된 용량(capacity)을초기하는 즉시 더 많은 원소를 저장할 수 있는 추가 공간이 자동으로 할당된다. 컨테이너의 끝에서 원소를 추가하거나 삭제할 때만 효율적이다.
2.3.1 vector<T> 컨테이너 생성하기
std::vector<double values;
values.reserve(20);컨테이너 객체의 reserve()를 호출해서 용량을 늘릴 수 있다. reserve() 호출은 컨테이너에 이미 있는 원소에는 어떤 영향도 주지 않는다. 그러나 reserve() 호출로 할당된 메모리가 증가했다면 시작 반복자나 끝 반복자처럼 이미 생성한 반복자들은 무효화되므로 이들 반복자는 반드시 다시 생생해야 한다. 이는 컨테이너의 크기를 늘리는 과정에서 기존 원소들이 새로운 메모리 위치로 복사되거나 이동될 수 있기 때문이다.
2.3.2 백터의 용량과 크기
벡터의 용량(capacity)은 메모리를 추가 할당하지 않아도 저장할 수 있는 원소들의 개수를 말한다. 즉, 이 원소들은 있을 수도 있고, 없을 수도 있다. 벡터의 크기(size)는 실제로 갖고 있는 원소들의 개수를 말한다.
resize() 멤버 함수를 호출하면 벡터의 크기를 변경할 수 있고, 용량을 늘리는 데도 쓸 수 있다.
std::vector<int>
values{1, 2, 3}; // 1 2 3 : 크기는 3
values.resize(5); // 1 2 3 0 0 : 크기는 5
values.resize(7, 99); // 1 2 3 0 0 99 99 : 크기는 7
values.resize(6); // 1 2 3 0 0 99 : 크기는 6
2.3.3 원소에 접근하기
[index]로 기존 원소의 값을 설정하거나 표현식에서 현재 값을 사용할 수 있다.
새 원소를 추가할 때는 반드시 push_back(), insert(), emplace(), emplace_back()을 사용해야 한다.
vector의 front()와 back() 멤버 함수는 순차열의 첫번째 원소와 마지막 원소에 대한 참조를 반환한다.
data() 멤버 함수는 vector 내부에서 원소를 저장하는 배열에 대한 포인터를 반환한다.
2.3.4 vector 컨테이너에서 반복자 사용하기
vector에는 push_back() 함수가 있으므로 새원소를 뒤에 추가할 때 back_insert_iterator를 사용할 수 있다. back_inserter() 전역 함수를 호출해도 back_insert_iterator를 얻을 수 있다. front_insert_iterator는 vector 컨테이너에 쓸 수 없다.
std::vector<double> data{32.5, 30.1, 36.3, 40.0, 39.2};
std::copy(std::istream_iterator<double>(std::cin), std::istream_iterator<double>(), std::back_inserter(data));
2.3.5 벡터 컨테이너에 새 원소 추가히기
컨테이너에 원소를 추가하는 방법은 멤버함수 호출이 유일하다는 것을 잊지 마라. 컨테이너의 멤버 함수를 호출하지 않고 비멤버 함수를 호출해서 원소를 추가하거나 삭제할 수 없다.
2.3.5.1 원소를 추가하기
컨테이너 객체의 push_back() 함수로 순차열의 끝에 원소를 추가한다. push_back()의 두번째 버전은 우축값 참조 매개변수를 사용한다. 이 버전은 원소 추가에 이동 연산을 한다
std::vector<std::string> words;
words.push_back(string("adiabatic"));
새 원소를 추가하는 더 나은 방법도 있다. emplace_back() 멤버는 push_back()보다 이를 더 효율적으로 처리한다.
std::vector<std::string> words;
words.push_back(std::string("facetious")); // string 생성자 호출 & 문자열 객체 이동
words.emplace_back("abstemious"); // 내부에서 string 생성자를 호출해 원소를 생성
emplace_back() 함수의 인수는 컨테이너에 추가될 객체의 생성자에 넘길 인수들이다. emplace_back() 멤버는 전달된 인수들을 사용해 객체 타입의 생성자를 호출해 컨테이너 내부에서 객체를 생성하므로 push_back()을 실행했을 때 발생하는 객체의 이동 연산을 제거할 수 있다.
2.3.5.2 원소를 삽입하기
emplace() 멤버 함수를 사용해 vector 순차열의 내부에 새 원소를 추가할 수 있다.
2.3.6 원소를 삭제하기
clear() 멤버를 호출해서 vector 객체에서 원소들을 모두 제거할 수도 있다. pop_back() 함수를 호출해서 vector 객체의 마지막 원소를 삭제할 수 있다.
원소들의 순서에 신경쓰지 않아도 된다면 원소들을 모두 이동하지 않아도 마지막 원소를 삭제하는 방법으로 원하는 원소를 제거할 수 있다.
std::swap(std::begin(data) + 1, std::end(data) - 1);
data.pop_back();컨테이너에 할당된 용량이 그렇게 클 필요가 없다면, 즉 원소를 추가하지 않을 것이라면 shrink_to_fit() 멤버를 호출해서 용량을 줄일 수 있다.
하나 또는 여러 원소를 삭제할 때는 vector의 erase() 멤버 함수를 호출하면 된다.
algorithm 헤더에 정의된 템플릿에 있는 remove() 알고리즘은 범위에서 지정한 값과 일치하는 원소들을 제거한다. remove()는 전역 함수이므로 컨테이너의 원소들을 삭제할 수 없다. remove()가 원소들을 제거하는 방법은 문자열에서 공백을 제거하는 절차와 비슷하다. 세번째 인수와 일치하는 원소들을 벡터 컨테이너 앞으로(오른쪽에서 왼쪽으로) 덮어쓰면서 복제하는 것이다.
std::vector<std::string>
words {"one", "none", "some", "all", "none", "most", "many"};
auto iter = std::remove(std::begin(words), std::end(words), "none");remove() 연산 이후에 words의 원소들을 출력해보면 처음 5개의 원소만 표시될 것이다. 그러나 벡터의 size()를 호출해서 반환된 값은 여전히 7이다. 즉, 마지막 2 원소가 여전히 거기에 있으며 빈 string 객체로 치환되어 있을 뿐이다. 이러한 잉여 원소들을 제거하려면 벡터의 erase() 멤버를 호출해야 한다.
words.erase(iter, std::end(words)); // erase-remove idiom
2.3.7 vector<bool> 컨테이너
vector<bool>은 vector<T> 템플릿의 특수화로 bool 타입 원소들에 대해 메모리 사용이 더 최적화되어 있다. vector<bool>의 구현은 bool 원소를 1비트로 저장한다.
2.4 deque<T> 컨테이너 사용하기
deque<T>는 타입 T의 원소들을 deque(double-ended queue)로 저장하는 컨테이너를 생성한다. 순차열의 시작이나 끝에 객체들을 효율적으로 추가하거나 삭제할 수 있다는 점에서 벡터보다 낫다.
2.4.1 deque 컨테이너 생성하기
2.4.2 원소에 접근하기
2.4.3 원소를 추가하고 제거하기
2.4.4 deque 컨테이너의 내용을 대체하기
2.5 list<T> 컨테이너 사용하기
list<T> 컨테이너 템플릿은 타입 T 객체의 이중 연결 리스트를 구현한 것이다. lsit는 vector나 deque 컨테이너와 비교하면 순차열의 어느 위치라도 상수 시간에 원소 삽입과 삭제를 할 수 있다는 장점이 있다. 하지만 순차열에서 특정 위치에 있는 원소에 바로 접근할 수 없다는 단점도 있다. 즉, 원소들에 인덱스를 사용할 수 없다. list 내부에 있는 원소에 접근하려면 한 원소에서 옆 원소로 하나씩 이동하며, 즉 처음부터 마지막 원소까지 원소들을 순회해야 한다.
2.5.1 list 컨테이너 생성하기
2.5.2 원소 추가하기
2.5.3 원소를 제거하기
2.5.4 원소를 정렬하고 병합하기
2.5.5 원소에 접근하기
2.6 forward_list<T> 컨테이너 사용하기
forward_list 컨테이너는 단일 연결 리스트로 객체를 저장한다. forward_list와 list 컨테이너의 주된 차이점은 원소들을 역방향으로 순회할 수 없다는 것이다. forward_list의 단일 연결로 정해지는 특성들이 있다. 첫째, 역방향 반복자는 이용할 수 없다. 오직 증가 연산만 사용할 수 있다. 둘째, 마지막 원소에 대한 참조를 반환하는 back() 멤버가 없다. 오직 front() 멤버만 있다. 셋째, 순차열의 끝에 도달하는 유일한 방법이 이전 원소를 가리키는 반복자에 증가 연산을 하는 것 뿐이므로 push_back(), pop_back(), emplace_back() 연산은 이용할 수 없다.
2.7 반복자를 직접 정의하기
2.7.1 STL 반복자 요구사항
STL에서 클래스 타입에 반복자를 정의하려면 특정 요구사항을 만족해야 한다. 그래야 반복자를 사용하는 알고리즘이 예상대로 동작하는 것을 보장할 수 있다.
알고리즘을 정의하는 템플릿은 필요한 반복자 카테고리를 결정해야 알고리즘에 전달된 반복자가 알고리즘에 필요한 반복자 기능을 충족하는지 검증할 수 있다. 알고리즘에 인수로 전달된 반복자 카테고리를 아는 것은 동작을 더 효율적으로 할 수 있는 최소 요구사항을 아는 것뿐 아니라 알고리즘이 반복자의 기능을 최대한 이용할 가능성도 제공하는 것이다. 이를 실현하기 위해 반복자 기능을 표준화된 방법으로 식별할 수 있어야 한다. 다양한 반복자 카테고리는 반복자 클래스가 정의해야 하는 다양한 멤버 함수가 있다.
2.7.1.1 STL 반복자 사용의 문제
정의하려는 함수 템플릿의 매개변수가 반복자일 때 발생하는 문제는 템플릿 정의에서 사용해야 하는 모든 타입을 항상 알 수 있는게 아니라는 것이다.
template<typename Iter>
void my_swap(Iter a, Iter b) {
tmp = *a; // tmp 변수는 선언되지 않았다.
*a = *b;
*b = tmp;
}반복자 인수가 가리키는 값의 타입을 결정할 수 있는 추가 메커니즘도 있다. 예를 들어 my_swap()에서 이용하는 모든 반복자 타입은 반복자가 가리키는 객체의 타입으로 value_type을 포함해야 한다고 하는 것이다.
template<typename Iter>
void my_swap(Iter a, Iter b) {
typename Iter::value_type tmp = *a;
*a = *b;
*b = tmp;
}이 방식은 value_type 별칭을 정의한 클래스 타입의 반복자에서는 잘 동작할 것이다. 그러나 STL 알고리즘은 반복자뿐 아니라 포인터와도 잘 동작한다. 하지만 Iter가 int* 같은 일반 포인터 타입이라면 이런 방식의 코드는 동작하지 않는다. 왜냐하면 포인터 타입은 타입 별칭을 포함할 수 있는 클래스가 아니기 때문이다.
2.7.2 STL 접근 방식
iterator_traits 템플릿 타입은 반복자 타입의 특징을 정의한 타입 별칭을 정의한다. iterator_traits 템플릿 정의는 다음과 같다.
template<class Iterator>
struct iterator_traits {
typedef typename Iterator::difference_type difference_type;
typedef typename Iterator::value_type value_type;
typedef typename Iterator::pointer pointer;
typedef typename Iterator::reference reference;
typedef typename Iterator::iterator_category iterator_category;
};
iterator_traits 템플릿 타입 별칭을 my_swap() 템플릿에 적용해서 tmp의 타입을 다음과 같이 지정하는 것도 가능하다.
template<typename Iter>
void my_swap(Iter a, Iter b) {
typename std::iterator_traits<Iter>::value_type tmp = *a;
*a = *b;
*b = tmp;
}
iterator_traits 템플릿에는 T*과 const T* 타입에 대한 특수화가 정의되어 있다.
template<class T>
struct iterator_traits<T*>
{
typedef ptrdiff_t difference_type;
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef random_access_iterator_tag iterator_category;
};
2.7.2.1 반복자 템플릿 사용하기
STL에는 직접 반복자 클래스를 만들 때 필요한 타입 별칭을 쉽게 넣을 수 있는 iterator 템플릿이 정의되어 있다. iterator는 iterator_traits 템플릿의 5가지 타입 별칭을 정의한 struct 템플릿이다.
template<class Category, class T, class Difference = ptrdiff_t, class Pointer = T*, class Reference = T&>
struct iterator {
typedef T value_type;
typedef Difference difference_type;
typedef Pointer pointer;
typedef Reference reference;
typedef Category iterator_category;
};
2.7.2.2 STL 반복자 멤버 함수 요구사항
STL은 반복자 카테고리에 따라 반복자 타입이 반드시 지원해야 하는 멤버 함수들을 정해놓았다. 이 함수들을 그룹으로 모아 놓으면 이해하기 쉬울 것이다. 첫번째 그룹은 모든 반복자가 갖춰야 하는 것이다. 모든 반복자 클래스가 갖고 있어야 하는 함수에는 기본 생성자, 복사 생성자, 할당 연산자가 있다. 이들 함수를 작성해야 한다면 명시적으로 소멸자도 작성하게 되는게 보통이다.
STL에 따르면 랜덤 액세스 반복자 클래스는 상등관계(equality) 연산자와 관계 연산자를 모두 정의해야 한다.
반복자 클래스가 반드시 정의해야 하는 나머지 연산들은 반복자 카테고리에 따라 정해진다. 이들 연산은 카테고리에 따라 누적되는 형태이므로 가장 상위 카테고리인 랜덤 엑세스 반복자는 전체 연산을 지원해야 한다.
2.8 요약
3장. 컨테이너 어댑터
3장에서는 2장에서 살펴본 STL 컨테이너를 변형하는 방법을 설명한다. 이들 변형은 특정 상황에 사용할 수 있는 더 간단한 인터페이스를 순차열 컨테이너에 정의해준다.
3.1 컨테이너 어댑터는 무엇인가
컨테이너 어댑터는 순차열 컨테이너를다른 기능을 제공하는 순차열 컨테이너로 정의하기 위해 래핑하는 클래스 템플릿을 말한다. 다른 기능을 제공하기 위해 컨테이너의 기존 인터페이스를 확장하기 때문에 이런 클래스 템플릿을 어댑터 클래스라 부른다.
3.2 stack<T> 컨테이너 어댑터 생성과 사용하기
stack<T> 컨테이너 어댑터의 데이터는 LIFO로 저장된다. 오직 최상위에 있는 원소만 접근할 수 있다. 스택에서 바로 아래 있는 원소는 위에 있는 원소를 제거한 후에 접근할 수 있다.
stack 컨테이너 어댑터 템플릿은 매개변수 2개를 사용한다. 첫번째는 저장할 객체의 타입이고, 두번째는 기반 컨테이너의 타입이다. stack<T>의 기반 순차열 컨테이너는 deque<T> 컨테이너가 기본이며, 따라서 실제 템플릿 타입은 stack<typename T, typename Container = deque<T>>가 된다.
back(), push_back(), pop_back(), empty(), size() 연산만 지원한다면 어떤 컨테이너도 두번째 템플릿 타입 인수에 기반 컨테이너로 지정할 수 있다.
3.2.1 스택 연산
3.3 queue<T> 컨테이너 어댑터 생성과 사용하기
queue<T> 컨테이너에서는 첫번째와 마지막 원소만 접근할 수 있다. 새 원소는 큐의 뒤에서만 추가할 수 있고, 원소 제거는 앞에서만 할 수 있다.
기반 컨테이너 타입은 front(), back(), push_back(), pop_front(), empty(), size()를 반드시 제공해야 한다.
3.3.1 큐 연산
3.3.2 queue 컨테이너의 실제 사용
3.4 priority_queue<T> 컨테이너 어댑터 사용하기
priority_queue 컨테이너 어댑터는 원소들을 정렬된 순서로 담아두는 큐를 정의한다. 즉, 우선 순위가 가장 높은 원소가 큐의 앞에 온다. 이것도 큐이므로 첫번째 원소만 접근할 수 있다. 따라서 우선순위가 가장 높은 원소가 항상 먼저 처리된다.
priority_queue 템플릿은 3가지 매개변수가 있고, 그중에 두가지는 기본 인수다. 첫번째는 저장할 객체의 타입, 두번째는 원소를 저장할 때 사용할 기반 컨테이너, 세번째는 원소의 순서를 결정하는 조건자를 정의한 함수 객체 타입이다.
3.4.1 우선순위 큐를 생성하기
우선순위 큐는 front(), push_back(), pop_back(), size(), empty() 멤버 함수를 지원하는 컨테이너를 사용할 수 있다.
3.4.2 우선순위 큐를 위한 연산
3.5 힙
힙(heap)은 컨테이너가 아니라 데이터를 구성하는 방식을 말한다. 힙이 무엇인지 이해하려면 우선 트리가 무엇인지 알아야 한다.
부모 노드가 자식 노드를 2개까지 가질 수 있는 트리를 이진 트리(binary tree)라고 한다. 모든 부모 노드가 자식 노드를 2개씩 갖고 있으면 완전 이진 트리(complete binary tree)라고 한다. 트리에서 부모 노드와 자식 노드를 연결하려면 포인터가 필요하다. 완전 이진 트리는 각 레벨에 필요한 노드 개수가 정해져 있으므로 자식 노드를 연결하는 포인터를 사용하지 않아도 배열이나 vector같은 순차열에 저장할 수 있다. 트리의 각 레벨을 n이라고 한다면 루트 노드는 레벨 0으로 시작하고, 각 레벨에는 2^n개의 노드가 필요하다. 배열에서 인덱스 n에 저장된 노드의 부모 인덱스는 항상 (n-1)/2 를 계산한 정숫값이 된다.
힙은 완전 이진 트리이고, 각 노드는 자식 노드에 따라 정렬된다. 부모 노드가 항상 자식 노드보다 크거나 같아야 하는 최대 힙(max heap)이 있고, 부모 노드가 항상 자식 노드보다 작거나 같아야 하는 최소 힙(min heap)이 있다. 부모 노드의 자식 노드까리는 반드시 정렬되지 않아도 된다.
3.5.1 힙 생성하기
힙을 다루는 함수는 algorithm 헤더에 템플릿으로 정의되어 있다. make_heap() 함수는 랜덤 엑세스 반복자로 정의한 원소들을 재배치해서 힙을 만든다. make_heap() 함수는 힙을 만들기 위해 < 연산자를 사용하므로 최대 힙을 만들게 된다.
std::vector<double>
numbers {2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
std::make_heap(std::begin(numbers), std::end(numbers));
priority_queue가 바로 힙이다! priority_queue의 인스턴스는 내부에서 힙을 생성한다. 그렇다면 왜 STL에는 이미 힙인 priority_queue와 힙을 생성할 수 있는 두가지 기능이 있을까? 힙을 우선순위 큐로 사용하면 되지 않을까?
사실, priority_queue는 힙보다 장점이 있다. 원소 순서가 자동으로 관리된다. 우선순위 큐는 첫번째 원소만 접근할 수 있고 다른 원소에는 접근할 수 없으므로 priority_queue의 정렬된 상태를 망가뜨릴 수 없다. 반면에 make_heap()으로 힙을 생성하면 priority_queue에 없는 몇가지 장점이 있다.
- 힙에서는 가장 큰 원소뿐 아니라 어떤 원소에도 접근할 수 있다. 이는 직접 생성한 벡터 같은 컨테이너에 원소들을 저장하기 때문에 가능하다.
- 랜덤 엑세스 반복자를 지원하는 어떤 시퀀스 컨테이너로도 힙을 생성할 수 있다. 일반 배열, string 객체, 직접 정의한 컨테이너가 여기에 해당한다.
- 힙 순서를 유지하는 힙 함수를 사용한다면 힙을 우선순위 큐로 쓸 수 있다.
3.5.2 힙 연산
힙을 생성한 후에는 원소들을 추가하고 싶을 것이다. algorithm 헤더의 push_heap() 템플릿 함수가 원소를 추가하지만, push_heap() 함수가 동작하는 방식을 처음보면 약간 이상하게 보일지도 모른다. 힙에 원소를 추가하려면 순차열에서 동작하는 메소드를 이용해 원소를 순차열의 뒤에 추가해야 한다. 그 다음에 추가한 마지막 원소를 처리하기 위해 push_heap() 함수를 호출한다. push_heap() 함수는 힙 배치를 유지하기 위해 순차열의 적절한 위치에 원소를 삽입한다.
std::vector<double> numbers {2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
std::make_heap(std::begin(numbers), std::end(numbers)); // 12 10 3.5 6.5 8 2.5 1.5 6
numbers.push_back(11); // 12 10 3.5 6.5 8 2.5 1.5 6 11
std::push_heap(std::begin(numbers), std::end(numbers)); // 12 11 3.5 10 8 2.5 1.5 6 6.5
가장 큰 원소를 제거하는 과정은 힙에 원소를 추가하는 과정과 비슷하지만, 방식은 정반대다. 먼저 pop_heap()을 호출하고, 그 다음에 컨테이너에서 가장 큰 원소를 제거한다.
3.6 포인터를 컨테이너에 저장하기
보통은 컨테이너에 객체보단 포인터를 저장하는 것이 더 좋고, 원시 포인터보단 스마트 포인터가 대부분은 더 좋다. 포인터를 컨테이너에 저장하는 이유는 다음과 같다.
- 컨테이너에 포인터를 저장한다는 것은 포인터가 가리키는 객체가 아니라 포인터가 복사된다는 뜻이다. 포인터 복사가 객체 복사보다 보통은 훨씬 더 빠르다.
- 컨테이너에 포인터를 저장하면 다형성을 얻을 수 있다. 기반 타입의 원소를 가리키는 포인터를 저장할 수 있게 컨테이너를 정의하면 파생 타입 객체의 포인터도 저장할 수 있다.
- 포인터를 저장한 컨테이너의 내용을 정렬하는 것이 객체를 정렬하는 것보다 빠르다. 객체가 아니라 포인터만 이동하면 되기 때문이다.
- 스마트 포인터를 저장하는 것이 원시 포인터를 저장하는 것보다 안전하다. 이는 스마트 포인터를 더는 참조하지 않을 때 자유 공간에 있는 객체가 자동으로 삭제되기 때문이다.
3.6.1 순차열 컨테이너에 포인터 저장하기
3.6.2 우선순위 큐에 포인터 저장하기
3.6.3 포인터 힙
3.6.4 기반 클래스 포인터를 담은 컨테이너
3.6.5 알고리즘을 포인터 범위에 적용하기
3.7 요약
4장. map 컨테이너
4.1 맵 컨테이너 소개
맵 컨테이너는 4가지가 있으며 각 컨테이너는 클래스 템플릿으로 정의되어 있다. 모든 map 컨테이너는 키/값 쌍을 저장한다. T 객체와 객체와 연관된 키 K를 캡슐화한 pair<const K, T> 타입 객체를 map에 원소로 저장한다. 컨테이너의 pair 원소에서 키가 const인 이유는 키 수정을 허용하면 컨테이너 원소의 순차열을 망가뜨릴 수 있기 때문이다.
4.2 map 컨테이너 사용하기
map<K, T>는 타입 T 객체를 저장하고 각 객체는 연관 키 타입 K를 갖는 맵을 정의한다. 컨테이너에서 객체의 위치는 키를 비교해서 결정된다.
4.2.1 map 컨테이너 생성하기
4.2.2 맵에 원소 삽입하기
4.2.3 map 원소를 내부에서 생성하기
4.2.4 map의 원소들에 접근하기
4.2.5 원소 삭제하기
4.3 pair<>와 tuple<> 객체 사용하기
일반적으로 pair로 캡슐화하는 객체는 어떤 타입이라도 될 수 있으므로 원하는 용도에 따라 pair<T1, T2> 객체를 생성할 수 있다.
tuple<> 템플릿은 pair 템플릿을 일반화한 것으로 타입이 다른 객체를 몇 개라도 캡슐화한 tuple 템플릿 인스턴스를 정의할 수 있다. 따라서 tuple인스턴스의 템플릿 타입 인수는 필요한 만큼 가질 수 있다.
4.3.1 pair 연산
4.3.2 tuple 연산
4.3.3 tuple과 pair를 함께 사용
4.4 multimap 컨테이너 사용하기
4.5 비교 함수를 바꾸기
4.5.1 greater<T> 객체 사용하기
4.5.2 원소를 비교하는 함수 객체 정의하기
4.6 해싱
해싱은 기본 타입의 데이터 항목이나 문자열 같은 객체에서 원하는 정숫값을 생성하는 과정을 말한다. 해싱한 결과로 얻은 값을 해시값 또는 해시 코드라고 하며, 컨테이너는 보통 이런 값을 사용해서 테이블 안에 객체의 위치를 정한다. 해싱을 사용해 원소 위치를 정하는 컨테이너는 키 값은 다르지만 해시값은 중복되는 경우를 다룰 수 있는 여유 공간이 있어야 한다.
해싱 알고리즘은 많지만, 공통으로 적용할 수 있는 방법은 없다. 해싱은 종종 나눗셈 이후에 나머지를 구하는 게 필요하다. 만약 가장 간단한 해싱 알고리즘으로 키를 다룬다고 하자. 수치값 k가 있고, 숫자 m으로 나눈 나머지를 계산하고, 이 나머지를 해시 값으로 사용하면 된다. 따라서 해시값은 k % m를 계산한 결과가 된다. m값을 잘 선택하면 생성되는 해시값의 중복 가능성을 최소화할 수 있고, 해시값이 균등하게 분포될 수 있으므로 m값의 선택이 중요하다. m값을 2의 거듭제곱, 즉 2^n으로 선택하면 해시값은 k의 최하위 n 비트가 되어버린다. 이렇게 되면 k의 최상위 비트는 해시값과 무관해지므로 좋은 결과라고 할 수 없다. 이상적이라면 키의 모든 비트가 해상의 결과에 영향을 줘야 한다. 따라서 m값으로 보통은 소수를 선택하는데, 이는 해시값이 범위 전반에 걸쳐 균등하게 분포될 가능성이 더 크기 때문이다.
4.6.1 해시 값을 생성하는 함수
functional 헤더에는 비순차 연관 컨테이너에서 사용하는 hash<K> 템플릿의 특수화가 정의되어 있다. hash<K> 템플릿에 정의된 함수 객체 타입은 타입 K 객체의 해시값을 생성한다. 기본 타입과 포인터 타입에 대해서는 hash<K> 템플릿의 특수화가 모두 제공된다.
4.7 unordered_map 컨테이너 사용하기
4.7.1 unordered_map 컨테이너 생성과 관리하기
4.7.2 버킷 개수 조정하기
4.7.3 원소 삽입하기
4.7.4 원소에 접근하기
4.7.5 원소 제거하기
4.7.6 버킷에 접근하기
4.8 unordered_multimap 컨테이너 사용하기
4.9 요약
5장. set으로 작업하기
5.1 set 컨테이너 이해하기
5.2 set<T> 컨테이너 사용하기
5.2.1 원소 추가와 제거
5.2.2 원소에 접근하기
5.2.3 set으로 작업하기
5.2.4 set 반복자
5.2.5 set 컨테이너에 포인터 저장하기
5.3 multiset<T> 컨테이너 사용하기
5.3.1 포인터를 파생 클래스 객체에 저장하기
5.4 unordered_set<T> 컨테이너 사용하기
5.4.1 원소 추가하기
5.4.2 원소 가져오기
5.4.3 원소 삭제하기
5.4.4 버킷 리스트를 보여주기
5.5 unordered_multiset<T> 컨테이너 사용하기
5.6 set 연산
5.6.1 set_union() 알고리즘
5.6.2 set_intersection() 알고리즘
5.6.3 set_difference() 알고리즘
5.6.4 set_symmetric_difference() 알고리즘
5.6.5 includes() 알고리즘
5.6.6 집합 연산 실습
5.7 요약
6. 정렬, 병합, 검색, 분리
6장에서는 범위를 정렬, 병합하고, 이와 관련된 알고리즘을 설명한다. 이들 알고리즘의 두 그룹은 정렬과 병합에 특화되어 있다. 다른 그룹은 주어진 원소 값에 따라 밤위를 분리하는 메커니즘을 제공한다. 두 그룹은 범위에서 하나 이상의 원소를 찾는 방법을 제공한다.
6.1 범위를 정렬하기
정렬은 많은 애플리케이션에서 필수이며, STL 알고리즘의 상당수는 범위로 지정된 객체들이 정렬되어 있을 때만 동작한다. algorithm 헤더에 정의된 sort<Iter>() 함수 템플릿은 범위로 지정된 원소들을 오름차순으로 정렬한다. 즉, 정렬하려는 객체의 타입에서 < 연산자르 지원한다고 가정하는 것이다. 객체들은 반드시 교환 가능(swappable)해야 하며, 이는 utility 헤더에 정의된 swap() 함수 템플릿을사용해 두 객체를 서로 교환할 수 있어야 한다는 뜻이다. 이것은 더 나아가서 졍렬하려는 객체의 타입은 이동 생성자와 이동 할당 연산자를 반드시 구현해야 한다는 것을 의미한다. sort 함수 템플릿 타입 매개변수 Iter는 정렬 범위에 속한 반복자의 타입이어야 하며, 반드시 랜덤 엑세스 반복자이여야 한다. 즉 랜덤 액세스 반복자를 제공하는 컨테이너의 원소들만 sort() 알고리즘으로 정렬할 수 있다는 뜻이다.
6.1.1 같은 원소의 정렬과 순서
stable_sort() 알고리즘은 범위에 있는 원소들을 정렬하고, 같은 원소들이 원본 순차열과 같은 순서로 남는 것을 보장한다.
sort() 알고리즘은 같은 원소들의 순서를 보장하지 않는다. 같은 원소들의 순서가 그대로 유지되어야 한다면 stable_sort()를 사용해야 한다.
6.1.2 부분 정렬
부분 정렬은 범위에서 최하위 n개만 정렬한다. 이런 용도를 위한 특별한 알고리즘 partial_sort() 알고리즘이 있다.
partial_sort_copy() 알고리즘은 정렬한 원소들을 다른 범위, 즉 다른 컨테이너에 복제한다는 점만 빼면 partial_sort()와 같다.
nth_element() 알고리즘의 적용 범위는 첫번째와 세번째 인수로 지정하고, 두번째 인수는 n번째 원소를 가리키는 반복자다. nth_element()를 실행하면 원소 범위 전체를 정렬했을 때 n번째가 되는 원소를 가리키게 된다. 범위에서 n번째 원소 앞에 오는 모든 원소는 n번째 원소보다 작고, 이후에 오는 모든 원소들은 n번째 원소보다 큰 값이 될 것이다.
n번째 원소 앞에 있는 원소들은 n번째 원소보다 작지만 반드시 정렬되어 있지는 않다. 마찬가지로 n번째 원소 뒤에 오는 원소들은 n번째 원소보다 크지만 반드시 정렬되어 있지는 않다.
6.1.3 정렬된 범위의 테스트
is_sort() 함수 템플릿은 두 반복자 인수로 지정한 범위에 있는 원소들이 오름차순이면 true를 반환한다. 인수로 지정하는 반복자는 원소들을 순차적으로 처리할 수 있어야 하므로 최소 순방향 반복자는 되어야 한다.
is_sorted_until() 함수 템플릿을 사용해 범위에 지정된 원소들이 정렬되어 있는지 판단할 수도 있다.
6.2 범위를 병합하기
병합 연산은 같은 방식으로 정렬된 두 범위의 원소들을 결합한다. 같은 방식이란 두 범위 모두 오름차순이거나 내림차순이어야 한다는 뜻이다. 병합 연산의 결과는 두 입력 범위의 원소들의 복제본을 담은 범위가 되며 원본 범위와 같은 방식으로 정렬되어 있다.
merge() 알고리즘은 두 범위를 병합해서 세번째 범위에 결과를 저장한다.
inplace_merge() 알고리즘은 정렬된 두 인접 순차열을 내부에서 병합한다. 세가지 매개변수 first, second, last를 사용하며, 이들은 모두 양방향 반복자다. 첫번째 입력 순차열의 범위는 [first, second)이며, 두번째 입력 순차열의 범위는 [second, last) 이므로 second가 가리키는 원소는 두번째 입력 범위에 속한다.
6.3 범위를 검색하기
STL은 객체들의 범위를 다양한 방법으로 검색할 수 있는 알고리즘을 제공한다. 이들 알고리즘은 대부분 비순차 시퀀스에서 동작한다. 하지만, 나중에 살펴보겠지만 정렬된 시퀀스가 필요한 알고리즘도 있다.
6.3.1 범위에서 원소 찾기
두 반복자로 정의한 범위에서 객체 하나를 찾는 알고리즘은 3가지가 있다.
- find() 알고리즘은 처음 두 인수로 지정한 범위에서 세번째 인수로 지정한 것과 같은 첫번째 객체를 찾는다.
- find_if() 알고리즘은 처음 두 인수로 지정한 범위에서 세번째 인수로 지정한 조건자가 true를 반환하는 첫번째 객체를 찾는다.
- find_not_if() 알고리즘은 처음 두 인수로 지정한 범위에서 세번째 인수로 지정한 조건자가 false를 반환하는 첫번째 객체를 찾는다.
6.3.2 범위에서 원소 범위 중에 하나를 찾기
find_first_of() 알고리즘은 두번째 범위의 원소들 중에 처음 일치하는 것을 범위에서 검색한다. 검색할 범위는 입력 반복자로 지정할 수 있지만, 찾아야 할 원소 범위는 순방향 반복자 이상이어야 한다.
6.3.3 범위에서 여러 원소를 찾기
adjacent_find() 알고리즘은 범위에서 연속으로 일치하는 두 원소를 검색한다. 연속적인 원소쌍은 == 연산자를사용해서 비교하고, 처음 같은 두 원소의 첫번째를 가리키는 반복자가 반환된다.
6.3.3.1 find_end() 알고리즘
find_end() 알고리즘은 범위에서 두번째 범위로 주어진 원소들과 일치하는 마지막 위치를 찾는다.
6.3.3.2 search() 알고리즘
search() 알고리즘은 시퀀스에서 서브시퀀스를 찾는다는 점에서 find_end()와 비슷하지만, 마지막 위치가 아니라 처음 위치를 찾는다는 점이 다르다.
6.3.3.3 search_n() 알고리즘
search_n() 알고리즘은 지정된 숫자만큼 연속으로 일치되는 원소를 범위에서 검색한다.
6.4 범위를 분리하기
어떤 범위에 있는 원소들을 분리하는 것은 주어진 조건자가 true를 반환하는 원소들을 앞쪽으로, 조건자가 false를 반환하는 원소들을 뒤쪽으로 재배열하는 것을 말한다. partition() 알고리즘이 이런 작업을 한다.
6.4.1 partition_copy() 알고리즘
6.4.2 partition_point() 알고리즘
6.5 이진 탐색 알고리즘
6장에서 지금까지 살펴본 탐색 알고리즘은 범위를 순차적으로 탐색할 뿐이었으며 원소들이 사전에 정렬될 필요도 없었다. 이진 탐색 알고리즘은 순차 검색보다 빠르지만, 범위에 지정된 원소들은 정렬되어 있어야 한다.
6.5.1 binary_search() 알고리즘
6.5.2 lower_bound() 알고리즘
6.5.3 equal_range() 알고리즘
6.6 요약
1. 사전 설정
7.1 원소 속성을 테스트하기
7.2 범위를 비교하기
7.2.1 범위에서 일치하지 않는 위치를 찾기
7.2.2 사전 순서로 범위 비교하기
7.2.3 범위의 순열
7.3 범위를 복제하기
7.3.1 n개의 원소들을 복제하기
7.3.2 조건에 따라 복제하기
7.3.3 역순으로 복제하기
7.4 원소 순서를 뒤집어서 복제하기
7.5 인접한 중복 원소를 제거하고 범위를 복제하기
7.6 범위에서 인접한 중복을 제거하기
7.7 범위를 회전하기
7.8 범위를 이동하기
7.9 범위에서 원소들을 제거하기
7.10 범위에서 원소를 설정하고 수정하기
7.10.1 원소 값을 함수로 생성하기
7.10.2 범위를 변경하기
7.10.3 범위의 원소를 치환하기
7.11 알고리즘을 적용하기
7.12 요약
[출처] C++14 STL 철저 입문|작성자 비블레리