벡터/리스트/데크

• [C++] 벡터/리스트/데크

  STL 시퀀스 컨테이너(sequence container)

  시퀀스 컨테이너 (Sequence Container) : 인덱스에 따라 원소를 순서대로 보관하는 컨테이너로써 vector, list, deque 등이 있다. 차례대로 원소를 추가/제거 하는 push, pop과 첫/마지막 원소를 참조하는 front,back 함수, 지정한 위치(반복자를 통해)에 원소를 삽입하는 insert 함수를 가진다.

  vector

  가변 배열과 같다고 생각하면 된다.

  • 시간복잡도

    • 임의의 위치 원소 접근 O(1)

    • 맨 뒤에 원소 추가 및 제거 amortized O(1) (평균적으로 O(1) 이지만, 메모리 재할당을 할경우 O(n))

    • 임의의 위치 원소 추가 및 제거 O(n)

  list

  노드기반 컨테이너, 이중 연결 리스트로 구현되어 있으며, 반복자를 사용할 때 1칸씩 밖에 이동하지 못한다.

  • 시간복잡도

    • 임의의 위치 원소 접근 O(n)

    • 임의의 위치 원소 추가 및 제거 O(1) (단, 반복자가 해당 위치에 접근해 있어야 한다)

  deque

  vector와 같은 기능에 맨 앞의 원소를 추가/제거 가능하며, 임의의 위치의 원소 추가/제거가 벡터보다

  약간 더 빠르지만, 원소들이 실제로 연속적으로 존재하지 않으며, 메모리가 추가적으로 필요하다.

  • 시간복잡도

    • 임의의 위치 원소 접근 O(1)

    • 맨 ‘앞 또는 맨 뒤에 원소 추가 및 제거O(1)

    • 임의의 위치 원소 추가 및 제거 O(n)