[C/C++] STL

Standard Template Library

C++의 Template 기반 container(컨테이너), algorithm(알고리즘), iterator(반복자)를 담고 있는 라이브러리이다.

container

데이터를 담는 객체로 여러 자료구조 형태로 구성되어있다.

컨테이너를 사용하기 위해서는 각 컨테이너에 해당하는 헤더파일을 include 해야한다.

• array
• vector (array의 단점을 개선한 동적 배열 ,배열의 크기가 동적이다)
• deque
  vector의 경우에는 데이터를 추가할 때마다 기존의 데이터를 복사한 이후 다른 메모리 공간에 추가한 데이터와 함께 붙여넣는 방식으로 동작하기 때문에 overhead가 많다. 이런 vector의 단점을 개선하고자 잘게 쪼개진 메모리 블록을 이용한 deque가 등장하였다.
  
• list
• queue
• priority queue (heap을 이용한 우선순위 큐)
• stack
• map
• set
• hash_map
• hash_set

algorithm

정렬, 삭제, 검색 등 STL에서 제공하는 기본적인 알고리즘이다.
(swap은 원래 algorithm헤더에 존재했지만 C++11부터 기본 제공)

컨테이너와 달리 algorythm 헤더에 모두 포함되어 있다.

sort

template <typename T>
void sort(T start, T end, Compare comp);

comp 함수는 greater() (내림차순), less() (오름차순)와 같은 객체를 사용해도 되고, bool 자료형으로 함수를 직접 만들어서 사용해도 된다. Compare 함수를 사용하지 않는 기본값은 오름차순이다.

find

template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& val);

first부터 last까지 중 val 값과 동일한 데이터를 찾아 그 데이터의 Iterator를 return해준다. 만약, 찾지 못한다면 last를 return한다.

iterator

컨테이너마다 데이터에 접근하는 방식이 제각각이다.
iterator는 이런 데이터 접근에 통일성을 주고자 만들어진 컨테이너 데이터 접근 객체이다.

즉, iterator는 통일된 포인터이다.

iterator 생성

vector<>::iterator itr;

iterator 관련 함수

vector<> arr;
arr.begin() : arr의 시작점을 가리키는 iterator 리턴.
arr.end() : arr의 (끝점 + 1)을 가리키는 iterator 리턴.

iterator를 활용한 데이터 접근

vector<> arr;
vector<>::iterator itr;

for (auto itr = arr.begin(); itr < arr.end(); itr ++) {
	...
}