[Rank 4] CPP 08

CPP 08

Templated containers, iterators, algorithms

템플릿 컨테이너, 반복자, 알고리즘

stl

Standard Template Library

표준 템플릿 라이브러리라는 이름에서 알 수 있듯 세 개의 구성 요소로 이루어진 템플릿들을 제공한다

그것은 반복자 (iterator), 컨테이너 (container), 알고리즘 (algorithm)

스택, 큐, 덱, 맵, 벡터, 리스트 등 한번쯤 들어봤을 법한 자료구조들과 적합한 알고리즘들이 내장되어 있으며, 필요한 자료구조를 꺼내서 사용하면 된다

container

http://www.tcpschool.com/cpp/cpp_container_adapter

http://www.tcpschool.com/cpp/cpp_container_associate

특수한 자료구조로 특정 타입의 데이터를 담을 수 있는 공간을 컨테이너라고 한다

 

순차 컨테이너 (sequence container)

• 원소들을 선형적인 순차열로 저장한다 (내부에서 정렬하지 않고, 들어온 순서대로 저장됨)
• array (C++11), vector, deque, forward_list (C++11), list가 여기에 해당된다
• 이 중에서 벡터는 요소가 삽입 또는 삭제될 때마다 크기가 자동으로 조정된다

 

컨테이너 어댑터 (container adapter)

• 기존 컨테이너의 인터페이스를 제한하여 만든 컨테이너
• 기초가 되는 클래스가 존재하고, 기능이 제한되거나 변형되어 있으며 특정 형태의 동작만 수행토록 한다
• 예를 들어 스택 같은 경우 맨 끝점에서만 데이터를 넣었다 뺐다 할 수 있다
• stack, queue, priority_queue가 여기에 해당된다

 

연관 컨테이너 (associative container)

• 키 - 값 등 관련있는 데이터를 한 쌍으로 저장하는 컨테이너
• 키와 값을 이용하기 때문에 요소에 접근이 빠르다
• 대개 균형잡힌 이진탐색 트리로 구현한다 (ft_containers가 그것을 알아볼 수 있는 과제)
• set, multiset, map, multimap 등이 포함된다
• unordered_set, unordered_multiset, unordered_map, unordered_multimap이 C++11에서 포함되었다

iterator

std::컨테이너<자료형>::iterator it;

반복자

컨테이너를 순회할 때 필요한 값으로, 컨테이너의 특정 위치를 나타낸다

어떤 자료구조를 사용하는지에 따라 반복자의 증감 형태도 다르므로 이를 하드코딩하기보단 라이브러리에서 반복자를 꺼내 사용한다

C++은 반복자도 포인터로 값을 다루기 때문에 값을 읽어오기 위해선 *를 앞에 붙여주면 된다

std::find

std::컨테이너<자료형>::iterator 반복자명 = std::find(탐색할시작점, 탐색할끝점, 찾고싶은값);

컨테이너에서 값을 찾을 때 사용한다

탐색할 시작점과 끝점은 컨테이너의 반복자 (iterator) 형식으로, 반환값도 반복자로 주어진다

탐색에 실패하면 컨테이너의 끝점이 반환되며, 마지막 반복자까지 탐색해도 값을 찾을 수 없음을 의미한다

컨테이너 관련 메서드

std::vector<int> v;

v.begin(); // 컨테이너의 시작점
v.end(); // 컨테이너의 끝점
v.front(); // 컨테이너의 첫 번째 요소 참조
v.back(); // 컨테이너의 마지막 요소 참조

• begin, end는 각각 첫 값의 주소와 마지막 값보다 한 칸 뒤의 주소를 반환한다
• front, back은 각각 첫 값과 마지막 값의 참조를 반환한다

 

v.push_back(); // 벡터 컨테이너 맨 뒤에 값 추가
v.pop_back(); // 벡터 컨테이너 맨 뒤 값 삭제

• push_back과 pop_back은 스택의 push, pop처럼 맨 뒤 값을 추가하거나 삭제한다

 

v.size(); // 벡터 컨테이너의 크기
v.at(5); // 인자로 주어진 인덱스에 있는 값 반환

• size는 벡터의 크기 (전체 길이) 를 반환한다
• at은 인자로 들어온 인덱스에 존재하는 값을 반환한다
  • 보통은 [] 연산자를 오버로딩하여 사용한다 (v[5] 이런 식으로)

 

v.clear(); // 벡터 비우기

• clear는 벡터의 모든 내용물을 지우고 길이를 0으로 초기화한다

 

std::max_element(v.begin(), v.end()); // 두 반복자 사이의 모든 값 중 최대값의 이터레이터 반환
std::min_element(v.begin(), v.end()); // 두 반복자 사이의 모든 값 중 최소값의 이터레이터 반환

• max_element와 min_element는 벡터의 메서드가 아니라 algorithm 라이브러리에 있는 메서드이다
• 반복자 두 개를 인자로 받으며, 두 반복자 사이의 값들 중 가장 작은 값 (min_element) 또는 가장 큰 값 (max_element) 을 반환한다

stack은 기존 컨테이너를 상속받는 컨테이너 어댑터이다

스택의 내부 구조를 보면 deque 부분이 주석처리되어 있는데, 템플릿 내에서 컨테이너 클래스를 받는 것으로 보아 컨테이너를 지정해줄 수 있음을 알 수 있다

 

C++ reference는 다음과 같이 설명하고 있다 :

The underlying container may be any of the standard container class templates or some other specifically designed container class. The container shall support the following operations:

임의의 표준 컨테이너 클래스 템플릿이나 별도로 작성된 컨테이너 클래스 어떤 것이든 (스택의) 기본이 되는 컨테이너가 될 수 있습니다. 다만 다음의 기능들을 포함하고 있어야 합니다:

• empty
• size
• back
• push_back
• pop_back

The standard container classes vector, deque and list fulfill these requirements. By default, if no container class is specified for a particular stack class instantiation, the standard container deque is used.

표준 컨테이너 클래스인 벡터, 덱과 리스트는 위의 조건을 만족합니다.

만약 스택 클래스 초기화 시에 어떠한 컨테이너 클래스도 명시하지 않았다면, 기본값으로 덱이 사용됩니다.

이 말인 즉슨 스택은 덱 컨테이너를 기반으로 만들어졌으며, 다르게 말하면 스택 컨테이너가 덱 컨테이너의 내용을 상속받아 만들어져 있으므로 추가적인 기능을 꺼내올 수도 있다는 것이다

 

스택에서 덱 컨테이너의 요소를 꺼내오기 위해 container_type 자료형의 c를 사용한다

container_type이 위에 설명한 기반 컨테이너의 자료형이므로, 덱을 기반으로 한 스택은 c의 자료형이 덱일 것이고 리스트를 기반으로 한 스택은 c의 자료형이 리스트일 것이다

이 c와 Stack 클래스 상속을 이용해서 스택 클래스에 추가적인 기능을 붙인 새로운 클래스 템플릿을 만들 수 있다

reverse iterator

컨테이너에는 두 종류의 반복자가 있는데, iterator 와 reverse_iterator이다

iterator는 컨테이너의 첫 번째 요소의 주소를 시작점 (begin) 으로 잡고, 마지막 요소의 다음 주소를 끝점 (end) 로 잡는다

따라서 컨테이너 전체를 순회하려면 begin부터 시작하여 end - 1까지 돌면 된다

++ 연산자는 begin 에서 end를 향해 움직이므로 메모리상에서 1칸씩 증가한다

 

reverse_iterator는 컨테이너의 마지막 요소의 주소를 시작점 (rbegin) 으로 잡고, 첫 번째 요소의 이전 주소를 끝점 (rend) 로 잡는다

마찬가지로 rbegin부터 rend + 1까지 순회하면 모든 요소를 탐색할 수 있으나, 일반 iterator와 달리 역순으로 탐색한다

++ 연산자는 rbegin에서 rend를 향해 움직이므로 메모리상에서 1칸씩 감소한다

 

iterator와 reverse_iterator의 상수 버전인 const_iterator와 const_reverse_iterator도 있는데 하는 행동은 완전히 같은 대신 상수값이다