[C++] STL 및 Container

STL - Standard Template Library 

직역하면 표준 템플릿 라이브러리
c++ 프로그래밍에 필요한 자료구조와 알고리즘 템플릿을 제공하는 라이브러리로써 
사용자가 자료구조나 알고리즘을 알지 못하여도 사용할 수 있는 라이브러리입니다.
( 편하게 사용가능 한 도구라고 생각하자.)

# STL 구성요소 

1. Container ( + Container Adaptor ) 
2. Iterator
3. Algorithm
4. Function Object

---

1. Container 

데이터를 저장하는 객체들로써 연속 컨테이너들과 연관 컨테이너들을 포함합니다. 

- 표준 연속(Sequence) 컨테이너 ( Vector, deque, list )

- 표준 연관(Associative)  컨테이너
  ( set, multiset, map, multimap, hash_set, hash_map, hash_multiset, hash_multimap ) 
  키(Key) 와 값 ( value ) 구조( 키를 넣으면 대응되는 값을 돌려주는 구조 )를 가지는 컨테이너 

* container adaptors ( queue, priority_queue, stack ) - 구성 요소의 인터페이스를 변경해 새로운 인터페이스를 갖는 구성요소로 변경 

---

# vector 

: 길이가 변하는 가변 길이를 가진 배열로써 벡터 컨테이너는 동적 배열로 구현. 
보통 배열과 다르게 벡터 컨테이너는 스스로 공간을 할당하고 크기를 확장가능함. 

장점

• 각각의 원소의 인덱스 값으로 바로 참조 가능

• 원소들을 임의의 순서로 접근 가능 

• 벡터 끝에 새로운 원소 추가 및 제거 가능  

단점

• 많은 장점을 위해서 보통의 배열보다 더 많은 메모리 공간을 필요로 함. 

 

# deque ( double-ended queue ) 

: 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 형태 
두개의 포인터를 사용해 양쪽에서 삭자와 삽입 발생 가능 ( 큐와 스택을 합친 형태라고 생각 가능 )

장점

• 각각의 원소들이 가진 인덱스 값을 통해 접근 가능

• 원소를 모든 방향으로 반복/참조 가능하다.

• 데크 끝과 시작 부분에 원소 추가 및 삭제 가능 

 

# list 

: 메모리 상에 선형으로 배열되며 이중 연결 리스트로 구현된다. 

template <class T, class Allocator = allocator<T> > class list;

장점

• 컨테이너 임의의 위치에 원소의 삽입과 삭제가 가능 ( 상수 시간 필요 )

• 다른 컨테이너 사이 또는 내부에서 원소들 간의 이동이 매우 효율적

• 원소들을 앞에서 뒤로 혹은 뒤에서 앞으로 참조 가능  

 단점

• 원소들을 인덱스로 직접 참조하는 것이 비효율적 

 

---

# set 

: 단순 컨테이너로써 원소는 key 값이며 삽입되는 key들은 자동으로 오름차순 정렬된다.
set의 원소들은 모두 유일하도록 저장되며 중복 저장을 필요로 할시에 multiset을 사용

시퀀스 컨테이너와 다르게 각각의 원소를 각각의 박스에 담은 게 아니라 한 개의 큰 박스에 모두 넣은 것으로써 상자 안에 원소의 유무만을 따지는 컨테이너 

 

# multiset

: set과 동일하며 중복 요소들을 허용함

 

 

# map 

: set과 매우 유사한 구조로써 map은 키에 대응되는 값 ( value )까지 같이 보관하게 됨. ( 중복된 키값은 허용 x )

 정렬 방식 

• map <int, string, string.less<int>> map의 오름차순 

• map <int, string, string.greator<int>> map의 내림차순

 추가 방식 

• map<int, string> strMap;

• strMap.insert( make_pair( 5, "Choi"));

• strMap.insert( make_pair <int, string> (, "Choi"));

 

# multimap

: map과 다르게 중복된 키값을 허용하는 구조.
find로 검색 시 먼저 들어온 데이터를 우선.
erase로 삭제 시 해당 키값에 해당하는 pair를 모두 삭제 

 

# hash

: 임의의 크기의 데이터를 고정된 크기의 데이터로 대응시켜주는 역할 수행.  

 

참고 링크 : 

표준 템플릿 라이브러리 - 위키백과, 우리 모두의 백과사전

 

씹어먹는 C++ - <10 - 2. C++ STL - 셋(set), 맵(map), unordered_set, unordered_map>