C++ STL

STL(Standard Template Library)

* 표준 C++ 라이브러리

* 구성요소 : Container, Iterator, Function Object, Algorithm 등

 

컨테이너 : 객체를 저장하는 객체, 자료구조

- 순차 컨테이너(sequence container) : array, vector, list, deque 등

   * 자료를 입력한 순서대로 저장하기 때문에 저장, 검색 알고리즘에 불리

   -> 많지 않은 양의 자료, 검색속도 중요하지 않은 경우 사용

 

- 연관 컨테이너(associative container) : set, multiset, map, multimap 등

   * 이진탐색트리 기반

   * 일정규칙에 따라 자료를 조직화하여 저장

   * 자료를 정렬하여 저장하기 때문에 검색 유리 -> 많은 양의 자료, 빠른검색에 사용

 

- 정렬되지않은 연관 컨테이너(unordered associative container) : unordered_set, unordered_map 등

   * 해시테이블 기반

   * 요소의 추가 삭제가 연관 컨테이너보다 빠르다. 단, 연관 컨테이너는 양방향 iterator를 지원하지만

      unordered 컨테이너는 순방향 iterator만 지원한다.

 

- 어댑터 컨테이너 : sequence 컨테이너를 변형시켜 다른 형태로 저장

                         (ex : stack, queue, priority_queue 등)

 

 * 모든 컨테이너는 기본적으로 포인터와 다르게 레퍼런스가 아닌 값을 제공한다(call by value)

   따라서 함수에 인자로 넘길 때는 자동으로 복사본을 생성하기에, 값을 변경시키고 싶다면 &연산자를 사용하여야 함!

 * 컨테이너 별 시간복잡도 : https://blog.naver.com/yoochansong/221739086178

C++ STL container 시간복잡도 및 특징 비교.

 

Iterator : 컨테이너의 원소를 가리키고, 가리키는 원소에 접근하여 다음 원소를 가리키는 기능

             포인터와 비슷

 

 

Function Object : 함수처럼 동작하는 객체로 operator() 연산자를 오버로딩한 객체

 

 

Algorithm : 다양한 알고리즘 처리를 위한 일반함수 제공

                      (ex : sort, lower_bound, binary_search 등)

 

Allocator