C++ STL sequence container

1. Standard Template Library 

- C++ internal library이다.

- template으로 구현되어 있다.

- container class (vector, list, stack, queue) 등이 구현되어있다.

- algorithms (sort, search, merge, swap) 등이 구현되어있다.

2. container class

- data type에서 자유로운 object들을 저장하는 collection이다.

- 포인터와 비슷한 iterator를 통해 element들에 접근한다.

- 뿐만아니라 container class에는 sort, search등의 다양한 operation들이 구현되어 있다. 

 

3. sequence container

- 순서대로 data가 저장되는 유형의 container이다. order가 존재하고 순서에 따라 접근하게 된다.

- vector, list, deque

- 위와 같은 member function들로 container에 access, add, remove를 수행한다.

- 그 밖에도 다양한 기능의 member function등이 존재한다.

4. Vector

- vector는 array와 유사하지만 더 편리하고 안전한 관리가 가능하다.

- 가변길이 container이다. 자동으로 연속된 storage를 늘려준다.

- element가 늘어나면 혹은 줄어들면 자동으로 resize를 한다.

- 연속된 공간의 메모리가 잡히기 때문에 index만 알면 access가 O(1)안에 끝난다. (random access O(1))

- size는 벡터에 들어있는 멤버의 수 이다.

- capacity는 할당된 메모리 공간의 크기이다. (allocation)

- capacity가 가득차면 vector가 알아서 다시 capacity를 늘린다. max_size는 최대로 늘어날 수 있는 capactiy의 크기이다.

- 인자로 vector를 넘겨줄때는 &를 사용해서 참조자로 넘겨줘서 불필요한 복사가 일어나지 않도록 하자.

5. Stack  

6. List

- stl에서 제공하는 list는 doubly-linked list로 구현되어있다.

- front, back은 바로 찾지만 중간의 노드들은 traverse를 해야 한다.

- 위치와 관계없이 삽입, 삭제가 매우 빠르다.

- iterator를 사용해 traverse하는 코드이다.

- iterator를 사용한 insert의 예시이다.

- 삽입은 it가 가리키는 노드 "앞에" 수행된다. 삽입이 끝나면 it는 여전히 아까 가리키던 노드를 가리킨다.

7. STL Sequence Container Time Complexity