C++ STL 정리 - 개요

간단하게 C++ STL 의 종류와 특성에 대해서 훑어보는 포스팅이다.

 

STL 은 Standard Template Library 의 약자로 C++ 언어를 위한 4가지 구성요소를 제공하는 라이브러리다.

 

4가지 구성요소는 

Algorithm, Container, Iterator, Functors가 해당한다.

 

 

* Algorithm

Algorithm 은 Algorithm 이라는 헤더 파일에 정의되어 있으며, 

Container 를 다루기 위한 여러 수단을 제공한다.

 

예를 들면,

Container 를 정렬 하기 위해 쓰는 sort() 함수나,

이진 탐색을 위해서 쓰이는 binary_search() 함수나,

Container 내부의 값을 찾는 find() 함수 등 다양하게 존재한다

자세한 함수 종류는 Reference 첫번째 문서를 참조 바란다.

 

 

* Container

Container 는 4가지 종류로 나뉠 수 있는데,

 

 

- 1) Sequence Container (순차 컨테이너)

 

Sequence Container 는 선형 방식으로 동일한 타입의 데이터를 저장하기에 알맞은 자료구조가 해당한다.

이에 해당하는 타입은 아래와 같이 5개가 있다.

 

-array 

-vector

-forwarded_list (singly-linked list)

-list (doubly-linked list)

-deque (double-ended queue)

 

 

 

- 2) Associative Container (연관 컨테이너)

 

Associative Container 는 정렬된 데이터 구조를 제공하며, 빠른 탐색이 가능한게 특징인 자료구조이다.

이에 해당하는 타입은 아래와 같이 4가지가 존재한다.

 

- Key 가 unique 한 경우

: set, map

 

- Key 가 하나이지만 중복된 value 가 허용되는 경우

: multiset, multimap

 

Associative Container 의 경우 컨테이너를 정의할 때, 별도의 정렬 방식을 정의해 줄 수 있다.

예를 들면, 아래의 코드는 class set 에 대한 기본정의 인데,

template<class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key>> class set;

 

비교 값은 Key 로 비교를 하고, 비교/정렬에 대한 방법은 std::less 를 사용하며, 할당을 key 값으로 정의하는 것을 알 수 있다.

 

(std::less, std::greater 는 #include <functional> 에 정의된 함수로, less(a,b) 하면 a 가 b 보다 작을 때, true 를 리턴, greater(a,b) 하면 a 가 b 보다 클때, true 를 리턴한다.

그래서 less 를 사용해서 컨테이너를 정의하면 오름 차순 컨테이너 생성이 가능하고,

greater 를 사용해서 컨테이너를 정의하면 내림 차순 컨테이너 생성이 가능하다.)

 

 

 

- 3) Unordered Associative Container (비정렬 연관 컨테이너)

 

Unordered Associative Container 이 컨테이너들은 해시화가 된 key 를 기반으로 자료에 접근하는 것이 특징이다.

이 경우도 Associative Container 와 유사하게 두 종류로 나뉜다

 

- Key 가 unique 한 경우

: unordered_set, unordered_map

 

- Key 가 하나이지만 중복된 value 가 허용되는 경우

: unordered_multiset, unordered_multimap

 

* 위에서 언급한 "Key 가 하나이지만 중복된 value 가 허용되는 경우" 란 컨테이너의 이름을 보면 추측이 가능하지만, 동일한 키에 여러개의 값이 들어 갈 수 있다는 의미이다. 예를들면 DB 에서 주민등록번호는 Unique Key, Primary Key 로 칠 수 있지만, 이름은 그렇지 않다. 이름이 바로 value 가 중복되어 허용되는 경우라 볼 수 있다.

 

 

- 4) Container Adapters

이 컨테이너들은 그 자체적으로 완전한 컨테이너 클래스는 아니고 다른 컨테이너를 겸용해서 정의된 경우이다.

이 말이 무슨 말인고 하면, stack 에 대한 정의를 보면 

template<class T, class Container = std::deque<T>> class stack;

 

으로 정의가 되어 있는데, 다른 컨테이너 정의에 비해서 deque 라는 다른 요소를 끼고 정의 되었음을 의미한다.

물론 이 deque  대신에 다른 것을 override 하여 바꿀 수 있다고 한다.

(단 두가지 조건이 따르는데, 1. Sequence Container 의 형태여야 하며, 2. back(), push_back(), pop_back() 인터페이스를 제공해야만 한다)

 

여기에 해당하는 컨테이너들은

stack, queue, priority_queue 가 해당한다.

 

 

* Iterator

Iterator (반복자) 의 경우 주로, 컨테이너를 탐색, 순회 할 때 자주 사용되는 인터페이스다.

다음과 같은 종류의 Iterator 가 존재한다.

 

- Input Iterator

-> 현재 위치의 원소를 단 한번만 읽을 수 있는 반복자 (istream)

 

- Output Iterator

-> 현재 위치의 원소를 단 한번만 쓸 수 있는 반복자 (ostream)

 

- Forward Iterator

-> 입력, 출력 반복자 기능에 순방향으로 이동(++)이 가능한 재할당될 수 있는 반복자

 

- Bidirectional Iterator

->순방향 반복자 기능에 역방향으로 이동(--)이 가능한 반복자  (list, set, mulitset, map, multimap)

 

- Random Access Iterator

-> 양방향 반복자 기능에 +, -, += , -=, [] 연산이 가능한 반복자
 (vector, deque)

 

Iterator 에 대한 더 자세한 사항은 Reference 의 세번째 문서를 참조 바란다.

 

 

* Functors

Functor 란 객체를 마치 함수처럼 쓰게 만드는 것으로,

Function Object 라고도 불린다.

이에 대한 더 자세한 설명은 Reference 의 4,5 번째 문서를 참조 바란다.

 

 

- Reference

1. http://www.cplusplus.com/reference/algorithm/

2. https://embeddedartistry.com/blog/2017/08/02/an-overview-of-c-stl-containers/

3. https://en.cppreference.com/w/cpp/iterator

4. https://haedallog.tistory.com/85

5. https://en.cppreference.com/w/cpp/utility/functional