뇌를 자극하는 C++ STL

Chapter 01 연산자 오버로딩

01-1 연산자 오버로딩이란

• 연산자 오버로딩은 C++에서 제공하는 기본 타입이 아닌 클래스 타입, 즉 사용자 정의 타입에도 연산자를 사용할 수 있게 하는 문법이다

01-2 연산자 오버로딩 정의 및 사용하기

• 연산자 오버로딩의 핵심은 클래스 타입(사용자 정의 타입)의 객체에 연산자를 사용하면 컴파일러는 정의된 함수를 호출하는 데 있다

01-3 단항 연산자 오버로딩

• ++ 연산자를 구분하기 위해 후위 ++ 연산자는 operator++() 멤버 함수 호출 시 의미 없는(dummy) 정수형 인자 0을 전달합니다

01-4 이항 연산자 오버로딩

• 오버로딩이 가능한 이항연산자로는 +, -, *, /, ==, !=, <, <= 등이 있다

01-5 전역 함수를 이용한 연산자 오버로딩

• 연산자 오버로딩에는 다음 두 가지가 있다 첫째, 멤버 함수를 이용한 연산자 오버로딩, 둘째 전역 함수를 이용한 연산자 오버로딩
• 이항 연산자의 왼쪽 항이 연산자 오버로딩 객체가 아니면 멤버 함수를 이용한 연산자 오버로딩을 이용할 수 없다 대신 전역 함수 연산자 오버로딩을 사용해야 한다
• 전역 함수를 이용하면 Point클래스의 private 멤버인 x,y에 접근할 수 없으므로 getter를 이용하거나 프렌드 함수를 사용한다

01-6 STL에 필요한 주요 연산자 오버로딩

• 함수 호출 연산자 오버로딩은 객체를 함수처럼 동작하게 하는 연산자 입니다 C++에서 Print(10)이라는 함수 호출 문장은 아래 세가지로 해석할 수 있습니다
• 첫째, 함수 호출 : Print가 함수 이름 입니다
• 둘째, 함수 포인터 : Print가 함수 포인터 입니다
• 셋째, 함수 객체 : Print가 함수 객체 입니다
• [] 연산자 오버로딩은 일반적으로 많은 객체를 저장하고 관리하는 객체에 사용됩니다
• [] 연산자 오버로딩은 일반적으로 컨테이너 객체에 사용됩니다 컨테이너 객체가 관리하는 내부 원소에 접근할 때 사용됩니다
• [] 연산자 오버로딩은 arr[i] = 10과 같은 쓰기 연산도 가능해야 하므로 operator[]() 함수는 const 함수와 비 const 함수 모두를 제공해야 합니다
• *, -> 연산자는 스마트 포인터나 반복자(iterator) 등의 특수한 객체에 사용된다
• 반복자가 STL의 핵심 구성 요소이므로 *, -> 연산자 오버로딩이 아주 중요하다
• 스마트 포인터는 일반 포인터의 기능에 몇 가지 유용한 기능을 추가한 포인터처럼 동작하는 객체이다
• 사용 중에 함수가 종료하거나 예외 등이 발생하면 동적으로 할당한 메모리를 해제하지 못하는 문제가 발생한다 이런 문제들은 스마트 포인터를 사용하여 쉽게 해결할 수 있다

01-7 타입 변환 연산자 오버로딩

• 사용자가 직접 정의해서 사용할 수 있는 타입 변환은 아래의 두가지가 있다
• 첫째, 생성자를 이용한 타입 변환
• 둘째, 타입 변환 연산자 오버로딩을 이용한 타입 변환
• 생성자를 이용한 형변환을 의도하지 않는다면 생성자는 명시적 호출만 가능하도록 explicit 키워드를 지정한다
• 타입 변환 연사자 오버로딩을 사용하면 자신의 타입을 다른 타입으로 변환할 수 있다
• 타입 변환 연산자는 생성자나 소멸자처럼 반환 타입을 지정하지 않는다

Chapter 02 함수 포인터

02-1 함수 포인터란

• 함수의 이름은 함수가 시작하는 시작 주소이며, 함수 포인터는 이 함수의 주소를 저장하는 포인터이다
• 함수 포인터는 메모리 접근 연산자 *를 붙여도 함수의 주소이다

02-2 함수 포인터의 종류

• C++에서 함수는 정적 함수와 멤버 함수로 나눌 수 있다
• 함수 호출은 아래와 같이 세 가지가 있다
• 첫째, 정적 함수 호출 ( 정적 함수 )
• 둘째, 객체로 멤버 함수 호출 ( 멤버 함수 )
• 셋째, 객체의 주소로 멤버 함수 호출 ( 멤버 함수 )
• 함수 호출 규약, 함수 호출 시 전달되는 인자의 순서나 함수가 종료될 때 함수의 스택을 정리하는 시점등을 약속한 것이다 대표적인 함수 호출 규약은 stdcall, cdecl, thiscall, fastcall 등이 있다
• 함수 호출은 멤버 함수 호출 방법에 따라 다르다

02-3 클라이언트 코드와 서버 코드

• 어떤 기능이나 서비스를 제공하는 코드 측을 서버 코드(서버)라 한다 그 기능을 제공받는 코드 측을 클라이언트 코드(클라이언트)라 한다
• 클라이언트가 서버를 호출하면 콜(call)이라 하고 서버가 클라이언트를 호출 하면 콜백(callback)이라 한다
• 윈도의 모든 프로시저(procdeure)는 시스템이 호출하는 콜백 함수이다
• 서버는 여러 클라이언트에 의해 호출되며 클라이언트의 존재를 알지 못한다

Chapter 03 함수 객체

03-1 함수 객체란

• 함수 객체(Function Object)는 함수처럼 동작하는 객체이다 다시 말해 ()연산자를 오버로딩한 객체이다
• 함수 객체는 함수자(Functor)라 불리기도 한다
• P.79 함수 객체의 장점 읽어보자
• for_each() 알고리즘은 사용자 정의 타입까지도 전달받을 수 있다는 사실을 기억하자

03-2 함수 객체 구현

• STL에는 유용하게 사용할 수 있는 함수 객체가 내장돼 있다 그중 대표적인 함수 객체가 less와 greater 이다
• less는 < 연산자의 함수 객체이며, greater는 > 연산자의 함수 객체이다
• 사용자 Less, Greater와 STL less, greater의 결과는 같다 단, STL less, greater는 템플릿 클래스이므로 임시 객체를 less<int>(), greater<int>()와 같이 생성한다 여기서 int는 비교할 값의 타입이다

Chapter 04 템플릿

04-1 함수 템플릿

• 템플릿은 함수 템플릿과 클래스 템플릿이 있다
• 함수 오버로딩은 클라이언트가 매개변수 타입을 미리 알고 있다는 전제로 만들어진다
• 만일 클라이언트에서 사용자 정의 타입 등 타입을 결정해야 한다면 함수 오버로딩을 사용할 수 없다
• 템플릿 함수를 사용하면 컴파일러는 클라이언트(호출 측)의 함수 호출 인자 타입을 보고 템플릿 함수의 매개변수 타입을 결정하여 실제 함수인 템플릿 인스턴스 함수를 만들어 낸다 이는 대단한 확장성을 갖는다
• 템플릿에 의해 컴파일 시점에 생성된 함수를 해당 템플릿의 인스턴스라 한다
• 컴파일이 완료되면 함수 템플릿은 존재하지 않으며 인스턴스화된 세 함수가 있을 뿐이다
• 템플릿도 함수처럼 여러 매개변수를 가질 수 있다
• 템플릿의 매개변수 타입 객체에는 템플릿 함수 정의의 연산이 가능한 객체, 즉 인터페이스를 지원하는 객체라면 모두 올 수 있다
• 함수 템플릿 특수화는 특수화된 버전의 함수 템플릿을 더 제공하는 것이다

04-2 클래스 템플릿

• 클래스 템플릿은 클래스를 만들어내는 틀(메타 코드)이다
• 템플릿은 클래스의 메타 코드일 뿐이며 컴파일러는 클래스 템플릿(클래스 메타 코드)을 이용해 실제 클래스(클래스 정의 코드)를 생성한다
• 템플릿의 매개변수도 함수의 매개변수처럼 디폴트 매개변수 값을 지정할 수 있다
• 클래스 템플릿도 특수화가 가능하다

04-3 STL을 위한 템플릿 예제

• For_each()는 배열의 원소를 출력하는 함수이다, 이 함수는 배열의 시작 주소와 끝 주소를 인자로 받아 모든 원소에 대해 클라이언트 함수를 호출한다
• For_each() 함수가 원소의 타입에 상관없이 사용할 수 있는 일반적인 함수라면 클라이언트의 활용도를 높이고 유지 보수를 좋게 할 수 있다
• 출력 함수의 템플릿 매개변수를 컴파일러가 유추할 수 없으므로 명시적으로 매개변수 인자를 지정하자
• 템플릿의 매개변수와 함수 객체를 결합하면 반환 타입과 함수 매개변수 타입을 클라이언트가 결정하는 아주 유연한 함수 객체를 만들 수 있다
• pair 클래스는 두 객체를 하나의 객체로 취급할 수 있게 두 객체를 묶어준다
• pair 클래스의 주요 멤버는 객체 쌍을 저장하는 first와 second 이다

Chapter 05 STL 소개

05-1 STL이란

• STL은 모든 구성 요소의 특징을 어느정도 이해하고 있어야만 효율적으로 사용할 수 있다
• STL이란 프로그램에 필요한 자료구조와 알고리즘을 템플릿으로 제공하는 라이브러리이다
• 컨테이너는 객체를 저장하는 객체이다
• STL의 세 가지 특징은 효율성, 일반화 프로그램(재사용성), 확장성이다

05-2 STL을 한눈에

• 컨테이너는 삽입순서에 기반해 두 가지로 나눈다(표준 시퀀스 컨테이너, 표준 연관 컨테이너)
• 컨테이너는 메모리에 기반해 두 가지로 나눈다(배열 기반 컨테이너, 노드 기반 컨테이너)
• 반복자는 컨테이너에 저장된 원소를 순회하고 접근하는 일반화된 방법을 제공한다
• 반복자는 컨테이너와 알고리즘이 하나로 동작하게 묶어주는 인터페이스 역할을 한다
• STL의 모든 컨테이너는 자신만의 반복자를 제공한다 여기서 주의할 점은 순차열의 시작과 끝에서 끝은 실제 원소가 아닌 끝을 표시하는 원소이다
• 반복자는 다음과 같이 다섯 범주로 나뉜다 ( 입력 반복자, 출력 반복자, 순방향 반복자, 양방향 반복자, 임의 접근 반복자 )
• 모든 컨테이너는 양방향 반복자 이상을 제공한다
• 배열 기반 컨테이너인 vector와 deque는 임의 접근 반복자를 제공한다
• STL은 순차열의 원소를 조사, 변경, 관리, 처리할 목적으로 알고리즘이라는 구성 요소를 제공한다
• STL 알고리즘은 아주 일반적이다 일반적이라는 의미는 특정 컨테이너나 원소 타입에 종속적이지 않다는 뜻이다
• 연관 컨테이너는 컨테이너만의 정렬 기준을 가지고 있기 때문에 sort 알고리즘 적용 자체가 말이 안된다
• STL에서 함수 객체는 클라이언트가 정의한 동작을 다른 구성 요소에 반영하려 할 때 사용된다
• 어댑터는 구성 요소의 인터페이스를 변경한다
• STL의 어댑터로는 컨테이너 어댑터, 반복자 어댑터, 함수 어댑터가 있다
• 대표적인 컨테이너 어댑터는 stack 이다
• 대표적인 반복자 어댑터는 reverse_iterator 이다
• 대표적인 함수 어댑터는 부정사 not2 이다
• stack<int, vector<int>> st 는 vector 컨테이너를 적용한 정수를 저장하는 stack 컨테이너를 생성한다
• 정방향 반복자는 반복자가 가리키는 원소와 값이 모두 같지만, 역방향 반복자가 가리키는 원소의 실제 값은 가리키는 원소의 다음(++) 원소가 된다
• 역방향 반복자를 이렇게 설계한 이유는 순차열의 구간(반복의 쌍)이 반개 구간으로 알고리즘 수행 시 정방향 반복자와 호환되도록 하기 위해서이다
• not2는 조건자 함수 객체를 반대 의미의 조건자 함수 객체로 변경하는 어댑터이다
• 할당기는 컨테이너의 메모리 할당 정보와 정책(메모리 할당 모델)을 캡슐화한 STL 구성 요소이다
• 할당기는 템플릿 클래스이며 모든 컨테이너는 기본 할당기를 사용한다
• STL의 할당기도 사용자 직접 할당기를 정의하고 사용할 수 있다
• 사용자 정의 할당기는 사용자가 직접 메모리 할당 방식을 제어할 수 있게 한다
• 모든 컨테이너는 템플릿 매개변수에 할당기를 인자로 받는다 기본 할당기는 allocator<T>이며 컨테이너는 템플릿 매개변수에 디폴트 매개변수 값으로 기본 할당기를 지정한다

Chapter 06 시퀀스 컨테이너

06-1 vector 컨테이너

• 시퀀스 컨테이너는 저장 원소가 삽입 순서에 따라 상대적인 위치(순서)를 갖는 컨테이너이며, 연관 컨테이너는 특정 정렬 규칙에 따라 저장 원소가 정렬되는 컨테이더이다

for(int i=0; i< v.size(); ++i) // 이 코드는 경고를 발생시킨다
	cout<< v[i] << endl;
for(vector<int>::size_type i = 0; i< v.size(); ++i) // 위의 코드로 인한 경고는 이와같이 수정해야 제거된다
	cout<< v[i] << endl;

• vector는 앞쪽에 원소를 추가,제거할 수 없다
• vector의 size_type은 원소의 개수나 [] 연산자 등의 index로 사용하는 형식의 typedef된 멤버 형식이다
• vector의 멤버함수 max_size()는 컨테이너가 담을 수 있는 최대 원소의 개수를 가르키며 유일하게 vector만 가지는 멤버함수 이다
• vector의 멤버함수 중 reverse()를 사용하면 미리 메모리를 할당해 capacity를 결정하고 vector에 원소가 추가되더라도 메모리를 재할당하지 않는다
• resize() 멤버 함수를 사용하면 컨테이너의 size를 변경할 수 있다 주의할 점은 size를 키울 때 capacity도 늘어나지만, size를 줄일 때는 capacity가 줄지 않는다
• capacity를 0으로 만드는 함수는 존재하지 않지만 C++에서 권장하는 swap 방법이 있다 임시로 생성한(기본 생성자에 의해 size, capacity가 0인) 컨테이너 객체와 capacity를 0으로 만들고자 하는 컨테이너 객체를 서로 swap하는 방법이다
• swap() 멤버 함수는 모든 컨테이너가 제공하며 두 컨테이너의 원소를 교환할 때 사용한다
• []연산자와 at() 멤버 함수의 차이점은 범위 점검을 하느냐 하지 않느냐 이다
• vector와 deque는 임의 접근 반복자를 제공하며 노드 기반 컨테이너인 list, set, multiset, map, multimap은 양방향 반복자를 제공한다 또한 컨테이너는 동작방식이 조금씩 다른 iterator, const_iterator, reverse_iterator, const_reverse_iterator 등 네 개의 반복자를 내장하고 있다
• vector<int>::iterator: 는 반복자 클래스이며 vector 내에 내장되어 있다
• 원소의 값을 변경하지 않는다면 상수 반복자를 사용하는 것이 좋다

vector<int>::iterator			// 다음 원소로 이동 가능하고 원소의 변경이 가능한 반복자이다
vector<int>::const_iterator		// 다음 원소로 이동 가능하고 원소의 변경이 불가능한 반복자이다
const vector<int>::iterator		// 다음 원소로 이동이 불가능하고 원소의 변경이 가능한 반복자이다
const vector<int>const_iterator	// 다음 원소로 이동이 불가능하며 원소의 변경이 불가능한 반복자이다

• reverse_iterator 은 역방향 반복자 이다
• vector는 여러 개의 원소를 한 번에 삽입하는 버전의 insert() 멤버 함수와 반복자 쌍(구간)을 사용하여 원소를 삽입할 수 있는 버전의 insert() 멤버 함수를 제공한다
• v2.insert(iter, v.begin(), v.end()): 는 iter가 가리키는 위치의 v2 컨테이너에 구간 v.begin(), v.end() 의 원소를 삽입한다
• 컨테이너 연산자는 vector 뿐만 아니라 다른 컨테이너 모두 제공하는 연산자이다 ==, !=, <, <=, >, >= 가 있다

06-2 deque 컨테이너

• deque는 vector의 단점을 해결하기 위해 여러 개의 메모리 블록을 할당하고 사용자에게는 하나의 블록처럼 보이게 하는 정책을 사용한다 원소의 추가 시 메모리가 부족할때마다 일정한 크기의 새로운 메모리 블록을 할당하여 이전 메모리를 제거하거나 이전 원소를 복사하는 등의 연산을 수행하지 않는다
• deque는 앞쪽에 원소를 추가/제거 할 수 있으므로 push_front() 멤버 함수와 push_back() 멤버 함수를 제공한다
• STL 컨테이너 중 deque와 vector는 배열 기반 컨테이너로서 임의 접근 반복자를 지원한다 노드 기반 컨테이너인 나머지 컨테이너 list, set, multiset, map, multimap은 양방향 반복자를 지원한다
• deque는 멤버함수 push_front(), pop_front()를 제공한다

06-3 list 컨테이너

• list는 노드 기반 컨테이너로 at()과 []연산자가 없으며 임의 접근 반복자가 아닌 양방향 반복자를 제공한다
• 노드 기반 컨테이너의 삽입과 제거 동작은 반복자를 무효화시키지 않는다
• 삽입하는 원소의 위치는 반복자가 가리키는 원소의 앞쪽이다
• liter = v.insert(liter, 600)의 실행결과 liter가 가리키는 위치에 600을 삽입하고 삽입한 원소의 반복자를 liter에 대입한다
• list는 원소의 값으로 원소를 제거하는 remove() 멤버 함수를 가지고 있다
• list의 remove()는 erase()처럼 해당 값의 노드만을 제거하므로 속도가 빠르며 유일하게 list 만이 remove() 멤버 함수를 가지므로 반복자가 아닌 원소의 값으로 컨테이너의 원소를 제거해야 한다면 list 컨테이너를 선택하는 것이 좋다
• 조건자를 이용해 원소를 제거해야 한다면 remove_if() 버전의 멤버 함수를 사용하자

bool Predicate(int n)
{
	return 10 <= n && n <= 30;
}
lt.remove_if(Predicate); // 이와 같이 조건자가 참인 모든 원소를 제거할 수 있다

• list는 splice()라는 함수를 활용해 상수 시간에 순차열을 잘라붙일 수 있다
• reverse()는 이중 연결 리스트의 탐색 경로를 서로 바꿈으로써 순차열을 리버스 시킨다
• unique() 멤버 함수는 인접한 원소를 하나만 남기므로 연속하지 않는 원소는 중복될 수 있다
• unique() 멤버 함수로 모든 원소를 유일하게 만들고자 한다면 원소를 정렬한 후 unique()를 수행하면 된다
• list는 자체 정렬 멤버 함수 sort()를 제공한다
• sort()의 조건자 버전을 사용하면 정렬 기준을 바꿀 수 있다
• 합병할 두 list는 정렬되어 있어야 한다
• 합병된 원소는 합병되어 사라진다
• list가 다른 정렬 기준을 사용하고 있다면 조건자 버전 merge() 멤버 함수를 사용하여 합병해야 한다
• 합병 정렬할 때 정렬 기준을 같게 지정하지 않으면 오류가 발생한다
• list는 다른 list와 결합할 때 좋은 컨테이너이다

Chapter 07 연관 컨테이너

07-1 set 컨테이너

• 연관 컨테이너가 시퀀스 컨테이너와 다른 점은 연관 컨테이너는 특정 정렬 규칙에 따라 저장 원소가 컨테이너에 정렬된다 ( 균형 이진 트리로 구현된다 )
• set 컨테이너는 연관 컨테이너 중 단순한 컨테이너로 key라 불리는 원소(value)의 집합으로 이뤄진 컨테이너이다
• set은 원소들이 유일하다 따라서 원소의 중복을 허용해야 한다면 multiset을 사용해야 한다
• 연관 컨테이너는 특정 정렬 기준(조건자)에 따라 원소를 자동 정렬하는 컨테이너 이다 이때 정렬 기준은 템플릿 매개 변수에 지정할 수 있으며, 기본 정렬 기준은 less 조건자이다
• 연관 컨테이너는 시퀀스 컨테이너가 제공하는 순서와 관련된 함수를 제공하지 않는다( push_back() 등등 )
• set은 같은 원소를 중복 저장할 수 없으므로 insert() 멤버 함수 호출 시 반환값으로 실패를 확인할 수 있다
• set은 저장 원소인 값(value)이 곧 비교로 사용되는 키(key)가 되며 그래서 set은 value와 key 타입이 같다
• 연관 컨테이너의 찾기 관련 멤버 함수는 key(원소)를 찾을 때 == 연산을 사용하지 않는다
• 연관 컨테이너는 정렬 기준에 의해 key(원소)가 정렬되어 있으므로 컨테이너의 정렬 기준 조건자를 이용해 찾기 연산을 수행한다
• set의 멤버함수 lower_bound()는 찾은 원소의 시작 반복자를 반환한다
• set의 멤버함수 upper_bound()는 찾은 원소의 다음 원소를 가리키는 반복자를 반환한다
• set뿐만 아니라 모든 연관 컨테이너의 key는 변경할 수 없다

07-2 multiset 컨테이너

• multiset 컨테이너는 중복 원소를 컨테이너에 저장할 수 있다는 것 외에는 set과 다른 것이 없다
• multiset은 set처럼 저장 위치와 삽입 성공 여부의 bool 값을 반환하는 pair 객체가 아닌 저장된 위치만을 가리키는 반복자를 반환한다

07-3 map 컨테이너

• map 컨테이너는 원소를 key와 value의 쌍으로 저장한다
• map 컨테이너는 set처럼 원소의 key는 컨테이너에 중복 저장될 수 없으며 중복 key를 저장해야 한다면 multimap을 사용해야 한다
• map의 insert() 멤버 함수는 set처럼 저장한 원소의 위치를 가리키는 반복자와 삽입 성공 여부를 나타내는 bool 값을 pair 객체로 반환한다
• map은 [] 연산자를 사용하여 쉽게 원소(key, value)를 추가하거나 value 값을 갱신할 수 있다
• map 컨테이너의 기본 정렬 기준은 less 이다, 정렬 기준을 바꾸려면 템플릿 형식의 세 번째 인자를 이용한다
• map은 연관 컨테이너이자 노드 기반 컨테이너이다 또한 삽입, 제거, 찾기 관련 함수를 모두 로그 시간에 수행한다

07-4 multimap 컨테이너

• multimap은 여러 key를 중복해서 저장할 수 있다
• multimap은 [] 연산자를 제공하지 않는다

Chapter 08 알고리즘

08-1 원소를 수정하지 않는 알고리즘

• adjacent_find()는 현재 원소와 다음 원소가 같아지는 첫 원소의 반복자를 반환한다
• adjacent_find()를 활용하여 순차열에서 인접한 원소가 특정 조건에 따라 인접한지 찾고자 한다면 조건자를 활용하면 된다
• 순차열에서 원소의 개수를 구하려면 간단하게 count() 알고리즘을 활용하자, 조건자 버전은 count_if() 이다
• equal() 알고리즘을 사용하여 두 순차열의 원소가 모두 같은지(==) 판단할 수 있다, 조건자를 줄 수 있다
• find()는 특정 원소를 찾는 알고리즘이며, find_if()는 조건에 따라 원소를 찾는 알고리즘이다
• 순차열 하나에 포함하는 다른 순차열이 있는지 찾아야 한다면 find_end()와 search() 알고리즘을 사용한다
• 조건자 버전의 find_end() 알고리즘을 사용하면 원소의 비교를 사용자가 결정할 수 있다
• find_first_of() 알고리즘은 두 순차열을 비교하여 모든 원소 중 같은 원소가 하나라도 발견되면 발견된 첫 원소의 반복자를 반환한다
• 순차열의 모든 원소에 사용자 동작을 적용하려면 일반적으로 for_each() 알고리즘을 사용한다
• 사용자 정책을 반영하려고 for_each() 알고리즘의 함수류를 함수가 아닌 함수자로 변경하면 다양한 출력 패턴을 구현할 수 있다
• 문자열 비교처럼 순차열의 사전순 비교가 필요하다면 lexicographical_compare() 알고리즘을 사용한다
• 순차열을 비교할 때 사용자가 직접 비교 기준을 설정하려면 조건자 버전의 lexicographical_compare() 알고리즘을 사용한다
• max(a,b), max(a,b,f), min(a,b), min(a,b,f)를 사용하면 간단하게 값을 비교하여 크거나 작은 값을 찾을 수 있다
• max_element(a,b) 알고리즘은 특정 구간에서 가장 큰 원소의 반복자를 반환한다
• min_element(a,b) 알고리즘은 특정 구간에서 가장 작은 원소의 반복자를 반환한다
• 정렬 기준을 설정하여 Point 객체의 x 값을 먼저 비교하고 x 값이 같으면 y 값을 비교하여 가장 큰 point 객체를 찾아 출력하게 할 수 있다
• 두 순차열을 비교하여 원소의 값이 서로 다른 위치를 찾고자 한다면 mismatch() 알고리즘을 사용한다
• search() 알고리즘이 find_end()와 다른 점은 일치하는 순차열이 여러 개라면 find_end()는 마지막 순차열의 반복자를 반환하지만, search()는 첫 번째 순차열의 반복자를 반환한다
• search_n() 알고리즘은 원소 x가 n번 연속한 첫 원소의 반복자를 반환한다

08-2 원소를 수정하는 알고리즘

• 원소를 수정하는 알고리즘은 원소의 값을 변경하거나 목적지 순차열로 원소를 복사하는 알고리즘이다
• 순차열에서 다른 순차열로 원소를 복사해야 한다면 copy() 알고리즘을 사용한다, 여기서 주목할 점은 목적지 순차열로 복사 동작을 수행할 때 두 가지 모드의 복사 동작이 있다 하나는 덮어쓰기 모드이고 하나는 삽입 모드 이다
• 원소의 복사를 순차열의 마지막 원소부터 복사하고자 한다면 copy_backward() 알고리즘을 사용한다
• 순차열을 특정 값으로 채우고자 한다면 fill(), fill_n() 알고리즘을 사용한다
• void Func(int &r)의 매개변수는 출력 매개변수로 사용되어야 하므로 꼭 레퍼런스 &를 사용해야 한다
• for_each() 알고리즘의 사용자 함수류를 함수자(함수 객체)로 구현하면 객체는 상태 변수를 가질 수 있으므로 함수를 사용하는 것보다 더 다양한 작업을 순차열에 적용할 수 있다
• 순차열의 모든 원소를 단순한 동작의 값으로 수정하고자 한다면 generatre() 알고리즘을 사용한다
• gernerate() 알고리즘과 for_each(), transform() 알고리즘의 큰 차이점은 함수자의 매개변수로 순차열의 원소를 전달받지 않기 때문에 원소가 가지고 있는 원값을 활용할 수 없고, 단순히 일정한 값으로 채울 뿐이다
• 정렬된 두 순차열을 하나의 정렬된 순차열로 합병하려면 merge() 알고리즘을 사용한다
• 만약 합병하려는 두 순차열이 특정 정렬 기준에 의해 정렬된 상태라면 일반 버전의 merge() 알고리즘을 사용할 수 없다
• 순차열의 특정 원소를 다른 값으로 수정하고자 한다면 replace() 알고리즘을 사용한다
• 사용자의 조건에 맞는 원소를 수정하여 목적지 순차열로 복사하려면 replace_copy()와 replace_copy_if() 알고리즘을 사용한다
• 순차열과 순차열의 모든 원소를 교환하려면 swap_ranges() 알고리즘을 사용한다
• 순차열의 모든 원소에 사용자의 정책을 반영하려면 일반적으로 for_each(), transform() 알고리즘을 사용한다
• transform() 알고리즘이 for_each() 알고리즘과 다른 것은 원본의 순차열의 변화 없이 목적지의 순차열로 저장한다는 점이다 물론 덮어쓰기 모드로 동작한다
• transform() 알고리즘의 사용자 정책 함수는 반환값을 사용하므로 for_each() 알고리즘과 다르게 반환 타입을 가진다
• 사용자 연산(함수류 적용)을 두 순차열의 원소에 적용하고자 한다면 transform() 알고리즘 버전을 사용하자
• 위의 알고리즘 모두가 덮어쓰기 모드로 동작한다 따라서 목적지 순차열은 원본 이상의 원소를 가지고 있어야 한다

08-3 제거 알고리즘

• 제거 알고리즘은 원소를 실제로 제거하지 않고 논리적으로 제거(다음 원소로 덮어쓰기)하기 때문에 순차열의 size를 실제로는 변경하지 않는다
• 실제 size를 변경하려면 컨테이너의 erase() 함수를 이용하자
• remove() 알고리즘은 순차열의 원소를 논리적으로 제거할 뿐 실제 제거하지 않는다 만약 실제 컨테이너의 size까지 변경하려면 erase() 멤버 함수를 함께 사용해야 한다
• 순차열의 원본을 변경하지 않고 특정 원소를 제거하여 목적지 순차열로 복사하고자 한다면 remove_copy() 알고리즘을 사용한다
• 순차열의 인접 원소를 유일하게 만들고자 한다면 unique() 알고리즘을 사용한다
• unique() 알고리즘에서 주의할 점은 인접한 중복 원소를 제거하기 때문에 결과에서 인접하지 않는 중복 원소는 남게된다 이와 같은 중복 원소도 제거하려면 정렬 후 unique() 알고리즘을 수행하면 된다

08-4 변경 알고리즘

• 변경 알고리즘은 순차열의 원소를 서로 교환하거나 이동하여 순차열 원소의 순서를 변경하는 알고리즘이다
• 원소의 순서를 순열처럼 변경할 때 next_permutation()과 prev_permutation() 알고리즘을 사용한다
• 순차열의 원소를 특정 조건에 따라 분류하고자 한다면 partition() 알고리즘을 사용한다
• 순차열의 원소를 특정 기준으로 분류하되 원소의 상대적인 순서는 변경하지 않게 하려면 stable_partition() 알고리즘을 사용한다
• 순차열의 원소의 순서를 랜덤으로 뒤섞고자 한다면 random_shuffle() 알고리즘을 사용한다 이때 출력 결과를 바꾸고 싶다면 srand()를 사용해야 한다
• reverse() 알고리즘은 순차열을 뒤집을 수 있다
• 뒤집힌 순차열을 목적지 순차열로 복사하고자 한다면 reverse_copy() 알고리즘을 사용한다
• 순차열을 회전시키려면 rotate() 알고리즘을 사용한다
• 순차열을 회전하여 목적지 순차열에 복사하려면 rotate_copy() 알고리즘을 사용한다

08-5 정렬 알고리즘

• 특정 정렬 기준으로 원소의 순서를 변경하여 정렬한다
• 힙은 트리 내의 모든 원소가 부모 노드보다 큰 값(혹은 작은 값)을 갖는 완전 이진 트리라 정의된다 그러므로 힙에서 루트 노드는 항상 가장 작은 값(혹은 가장 큰 값)을 갖는다
• 항상 루트 노드가 가장 작은 값(혹은 가장 큰 값)이기 때문에 힙은 우선순위 큐나 정렬 등의 알고리즘에 유용하게 사용되는 자료구조이다
• make_head() 알고리즘은 순차열을 힙으로 만든다
• pop_heap() 알고리즘은 힙에서 루트(가장 큰 원소) 노드를 제거한다
• 힙을 정렬시키려면 sort_heap() 알고리즘을 사용한다
• 순차열의 원소 중 n개의 원소를 선별하고자 한다면 nth_element() 알고리즘을 사용한다
• sort() 알고리즘은 퀵정렬을 기반으로 한다, stable_sort() 알고리즘은 머지정렬을 기반으로 한다, partial_sort() 알고리즘은 힙정렬을 기반으로 한다
• 순차열을 정렬할 때 같은 원소의 상대적인 순서를 유지해야 한다면 stable_sort() 알고리즘을 사용해야 한다
• 순차열의 상위 구간만을 정렬하거나 힙정렬의 특징이 필요하다면 partial_sort() 알고리즘을 사용한다

08-6 정렬된 범위 알고리즘

• 정렬된 범위 알고리즘은 정렬된 구간에서만 동작하는 알고리즘이다
• 한 순차열이 다른 순차열의 부분 집합인지 판단하려면 includes() 알고리즘을 사용한다
• 순차열에서 같은 원소를 찾기 위해 연관 컨테이너의 lower_bound(), upper_bound() 멤버 함수와 비슷한 알고리즘이 필요하다면 lower_bound(), upper_bound() 알고리즘을 사용한다
• 순차열에서 찾는 원소의 반복자 쌍(구간)을 얻고자 한다면 equal_range() 알고리즘을 사용한다
• 정렬된 두 순차열을 하나의 목적지 순차열로 합병하려면 merge() 알고리즘을 사용한다
• 하나의 순차열이 두 구간으로 정렬돼 있다면 inplace_merge() 알고리즘을 사용하여 하나의 구간으로 정렬할 수 있다
• 정렬된 두 순차열의 합집합을 구하려면 set_union()을 사용한다
• 정렬된 두 순차열의 교집합을 구하려면 set_intersection()을 사용한다
• 정렬된 두 순차열의 차집합을 구하려면 set_difference()을 사용한다

08-7 수치 알고리즘

• 순차열의 모든 원소를 누적하려면 for_each()나 transform() 알고리즘을 사용할 수 있지만 누적값(상태값)을 기억하기 위해 함수자(functor)을 사용해야 하므로 조금 복잡하다 순차열의 모든 원소에 대해 누적을 구하거나 순서대로 원소에 연산을 적용해야 한다면 수치 알고리즘을 사용하여 좀 더 간단하게 처리할 수 있다
• 순차열 모든 원소의 합또는 곱을 구하려면 accumulate() 알고리즘을 사용한다
• 두 순차열의 내적(모든 원소의 곱의 합)을 구하려면 inner_product() 알고리즘을 사용한다
• 함수류 버전의 inner_product() 알고리즘을 사용하면 다양한 원소 간의 연산과 누적 연산을 수행할 수 있다
• 순차열에서 원소 간의 차를 구하려면 adjacent_difference() 알고리즘을 사용한다
• 순차열에서 인접 원소와의 사용자 정의 연산을 수행하려면 함수류 버전 adjacent_difference() 알고리즘을 사용한다
• 순차열에서 현재 원소까지의 합을 구하고자 한다면 partial_sum() 알고리즘을 사용한다
• 순차열에서 현재 원소까지의 합(누적)뿐만 아니라 사용자 연산을 수행하려면 함수류 버전의 partial_sum() 알고리즘을 사용한다

Chapter 09 STL 함수 객체

09-1 함수 객체의 종류

• 함수 객체(function object)는 함수자(functor)라는 애칭으로 더 많이 사용되며, operator() 연산자를 오버로딩한 클래스 객체이다
• STL 함수 객체는 일반 함수 객체와 함수 어댑터로 분류할 수 있다
• 조건자는 bool 형식을 반환하는 함수류(함수 객체, 함수, 함수 포인터)이다
• STL에서 제공하는 조건자는 모두 함수 객체 조건자이다 bool 형식을 반환하는 함구 객체라고 해서 모두 함수 객체 조건자(function object predicate)는 아니며 조건자는 객체의 상태값을 변경할 수 없다는 요구조건을 만족해야 한다 그래서 함수 객체 조건자의 operator() 연산자 오버로딩 함수는 모두 const 함수이다

09-2 산술 연산 함수 객체

• STL은 다음 여섯 가지 산술 연산 함수 객체(함수자)를 제공한다
• plus<T> : 이항 연산 함수자로 + 연산
• minus<T> : 이항 연산 함수자로 - 연산
• muliplies<T> : 이항 연산 함수자로 * 연산
• divides<T> : 이항 연산 함수자로 / 연산
• modulus<T> : 이항 연산 함수자로 % 연산
• negate<T> : 단항 연산 함수자로 - 연산

09-3 비교 연산 조건자

• 조건자(predicate)는 조건을 판단해야 하는 대부분의 알고리즘에 사용된다
• 특정 정렬 기준으로 정렬되어야 하는 컨테이너인 연관 컨테이너 set, map, multiset, multimap에도 사용된다
• 조건자는 상태가 변경될 수 없으므로 bool 형식을 반환하는 operator() 연산자 함수를 꼭 const 함수로 구현해야 한다

09-4 논리 연산 조건자

• STL은 다음 세 가지 논리 연산 함수 객체 조건자를 제공한다
• logical_and<T> : 이항 조건자로 && 연산
• logical_or<T> : 이항 조건자로 || 연산
• logical_not<T> : 단항 조건자로 ! 연산

09-5 바인더

• 바인더는 이항 함수자를 단항 함수자로 변환한다

09-6 부정자

• 부정자는 조건자를 반대의 조건자로 변환한다

09-7 함수 포인터 어댑터

• 함수 포인터 어댑터는 일반 함수를 어댑터 적용이 가능한 함수 객체로 변환한다

09-8 멤버 함수 포인터 어댑터

• 멤버 함수 포인터 어댑터는 멤버 함수를 함수 객체로 변환하여 알고리즘이 객체 원소의 멤버 함수를 호출할 수 있게 한다

Chapter 10 반복자

10-1 반복자의 종류

• 컨테이너와 알고리즘은 반복자를 통해 서로 통신(인터페이스) 한다
• 반복자는 포인터를 추상화한 클래스 객체이다
• 순차열은 순서 있는 원소의 집합이다
• 순차열은 하나의 시작과 끝을 나타내는 반복자의 쌍으로 표현되며 이를 구간(range)이라 한다

10-2 iterator와 const_iterator

• iterator : 반복자가 가리키는 원소의 읽기, 쓰기 가능
• const_iterator : 반복자가 가리키는 원소의 읽기 가능

10-3 reverse_iterator와 const_reverse_iterator

• reverse_iterator : 역방향 반복자의 내장 형식, 반복자가 가리키는 원소 읽기, 쓰기 가능
• const_reverse_iterator : 역방향 반복자의 내장 형식, 반복자가 가리키는 원소의 읽기 가능

10-4 삽입 반복자

• 삽입 반복자는 순차열에 원소를 삽입할 수 있게 반복자를 변환하는 반복자 어댑터이다

10-5 입/출력 스트림 반복자

• 입/출력 스트림 반복자는 스트림과 연결된 반복자로 알고리즘이 스트림에 읽고 쓸 수 있게 하는 반복자 어댑터이다

10-6 반복자 특성과 보조 함수

• 반복자는 반복자의 효율적인 사용을 위해 다섯 가지 반복자(입력, 출력, 순방향, 양방향, 임의 접근 반복자)로 분류한다, 이때 각 반복자는 자신만의 특징을 가지며 이 특징을 저장하는 템플릿 클래스를 가리켜 반복자 특성이라고 한다

Chapter 11 컨테이너 어뎁터

11-1 stack 컨테이너

• stack 컨테이너는 LIFO 방식의 컨테이너를 구현한 템플릿 클래스이다
• stack 컨테이너는 vector, deque, list를 사용할 수 있으며, 이 인터페이스들을 지원한다면 사용자 컨테이너를 사용할 수 있다

11-2 queue 컨테이너

• queue 컨테이너는 FIFO 방식의 컨테이너를 구현한 템플릿 클래스이다
• queue 컨테이너는 vector를 사용할 수 없으며, deque, list와 이 인터페이스를 지원하는 사용자 컨테이너를 사용할 수 있다

11-3 priority_queue 컨테이너

• priority_queue 컨테이너는 우선순위 queue를 구현한 템플릿 클래스이다

Chapter 12 string 컨테이너

12-1 string의 주요 인터페이스와 특징

• string은 vector 컨테이너와 비슷한 컨테이너이다, 시퀀스 컨테이너이며 배열 기반 컨테이너의 범주에 속한다

12-2 string의 주요 멤버 함수 정리

• reserve()를 사용하면 메모리 재할당으로 발생하는 비효율성을 줄일 수 있다

맨 위로 이동하기