1. Standard Template Library

• 임의 타입의 객체를 보관할 수 있는 컨테이너
• 컨테이너에 보관된 원소에 접근할 수 있는 반복자
• 반복자들을 가지고 일련의 작업을 수행하는 알고리즘

2. 컨테이너-벡터(std::vector)

C++STL에서 컨테이너는 크게 시퀀스 컨테이너와 연관 컨테이너로 나뉜다.

시퀀스는 vector, list, deque가 정의되어있다.

vector는 가변 길이 배열이라 보면 된다.

• 메모리 상에 실제로 순차적으로 저장되어 있음
• 임의의 위치에 있는 원소를 접근하는 것을 매우 빠르게(O(1)) 수행할 수 있음

2.1. push_back

벡터에서 맨 뒤에 원소를 추가하는 작업은 엄밀히 말하자면 amortized O(1)이다.

• vector는 현재 가지고 있는 원소의 개수 보다 더 많은 공간을 할당
  • 따라서 원소 추가 시 O(1)
• 할당된 공간을 다 채웠을 경우
  • 새로운 큰 공간을 다시 할당하고, 기존의 원소들을 복사해야 함
    • 원소를 모두 복사해야 하기 때문에 O(n)으로 수행됨
    • 하지만 이는 매우 드문 경우

2.2. 시간복잡도 정리

• 임의의 위치 원소 접근: O(1)
• 맨 뒤에 원소 추가 및 제거: amortized O(1)
• 임의의 위치 원소 추가 및 제거: O(n)

3. 반복자(iterator)

컨테이너 원소에 접근할 수 있는 포인터와 같은 객체이다.

• 컨테이너에 iterator멤버 타입으로 정의되어 있음

• vector의 반복자를 반환하는 함수: begin(), end()
  

• end()가 vector의 마지막 원소 한칸 뒤를 가리키는 이유

  • begin() == end()를 통해 비어있는 벡터를 표현하기 위해(물론 다양한 이유가 더 많겠지만)

• 주의할 점: iterator를 통해 순회하는 중 원소를 지우거나 추가하게되면 순회를 위해 사용중인 반복자는 유효한 반복자가 아니게 됨

  • 지우거나 추가하는 행위를 한 뒤에는 반복자를 다시 설정해주자

• const_iterator: 상수반복자로, iterator가 가리키는 값을 바꿀 수 없는 속성을 가짐

• reverse_iterator: 역으로 벡터를 순회 가능한 반복자

• const_reverse_iterator: 상수 역반복자

• 반복자의 상속 구조

  • 반복자는 여러 종류가 있고, 각각 컨테이너는 이에 맞는 반복자를 상속받아 사용
  • vector: Random Access Iterator
  • list: Bidirectional Iterator(한칸씩밖에 이동 불가)
  • deque: Random Access Iterator
    

4. 리스트(list)

양방향 연결 구조를 가진 자료형

• vector와 달리 임의의 위치에 있는 원소에 접근 불가
  • 시작 원소와 마지막 원소의 위치만 기억
• 임의의 위치에 원소를 추가하거나 제거하는 작업의 시간복잡도가 O(1)

5. 덱(deque-double ended queue)

원소들이 실제로 메모리 상에서 연속적으로 존재하지는 않지만 원소들이 어디에 저장되어 있는지에 대한 정보를 보관하기 위해 추가적인 메모리를 더 사용하는 실행속도를 얻고 메모리를 버리를 컨테이너

• 원소들이 메모리에 연속되어 존재하는 것이 아니라 일정 크기로 잘려서 각각의 블록속에 존재함
  • 이 블록들이 메모리 상에 어느곳에 위치하여 있는지 저장하기 위해 각각의 블록들의 주소를 저장하는 벡터가 필요함

• 임의의 위치의 원소에 접근하는 시간복잡도: O(1)
• 맨뒤, 앞에 원소를 추가/제거하는 작업의 시간복잡도: O(1)
  • 공간이 부족하더라도 새로운 블록을 만들면 되니 vector보다 빠름
• 임의의 위치에 원소를 추가/제거하는 작업의 시간복잡도: O(n)