C++ 기초 개념 10-1 : 벡터(vector), 리스트(list), 덱(deque)

모두의 코드를 참고하여 핵심 내용을 간추리고 있습니다. 자세한 내용은 모두의 코드의 씹어먹는 C++ 강좌를 참고해 주세요!

---

C++ 표준 템플릿 라이브러리 (STL : Standard Template Library)

STL 은 다음과 같은 세 개의 라이브러리들을 의미한다.

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

 

 

Container

컨테이너에는 배열처럼 객체들을 순차적으로 보관하는 시퀀스 컨테이너(sequence container) 와 키를 바탕으로 대응되는 값을 찾아주는 연관 컨테이너(associative container) 가 있다.

먼저 시퀀스 컨테이너의 경우 vector, list, deque 이렇게 3 개가 있다. 각각의 시간 복잡도와 특징을 살펴보자.

 

 

벡터 (vector)

벡터는 메모리가 연속된 공간에 저장된다. push_back 연산이 계속 들어와 Capacity (할당된 공간) 보다 더 많은 길이가 되면, 기본 메모리를 파괴하고 capacity 를 늘려 영역을 할당한다. 따라서 이 경우, 배열을 새로 구성하기 때문에 실제 시간은 O(n) 이지만 매번 재할당을 하지 않아 맨 끝에 요소를 삽입하는 경우의 시간 복잡도는 amortized O(1) 이라고 부른다. ( 평균적으로 O(1) 이지만 최악의 경우 O(n) )

 

임의의 위치 원소 접근([ ], at)의 경우 O(1), 맨 뒤에 원소 추가 및 제거(push_back, pop_back)는 amortized O(1), 임의의 원소 추가 및 제거(insert, erase) 는 O(n) 이 든다. capacity 를 조절할 때는 resize 를 사용한다.

 

 

반복자 (iterator)

반복자는 컨테이너에 iterator 멤버 타입으로 정의되어 있다.

반복자를 이용한 벡터 요소 출력은 다음과 같이 실행한다.

// 전체 벡터를 출력하기
for (std::vector<int>::iterator itr = vec.begin(); itr != vec.end(); ++itr) {
  std::cout << *itr << std::endl;
}

// 템플릿 버전의 경우, typename 을 붙여 주어야 한다!
// 이는 의존타입 문제를 해결하기 위해서이다
for (typename std::vector<T>::iterator itr = vec.begin(); itr != vec.end();
     ++itr) {
     // ...

 

만약 반복자를 이용해 erase 나 insert 를 수행한다면 어떨까?

  std::vector<int>::iterator itr = vec.begin();
  std::vector<int>::iterator end_itr = vec.end();

  for (; itr != end_itr; ++itr) {
    if (*itr == 20) {
      vec.erase(itr);
    }
  }

다음의 코드는 에러를 발생시킨다. 컨테이너에 원소를 추가하거나 제거하면 기존에 사용하였던 모든 반복자를 사용할 수 없기 때문이다. 따라서 코드를 다음과 같이 고쳐야 한다.

 

for (std::vector<int>::size_type i = 0; i != vec.size(); i++) {
  if (vec[i] == 20) {
    vec.erase(vec.begin() + i);
    i--;
  }
}

하지만 이는 정수형 변수 i 를 이용하므로 반복자를 사용하는 규칙을 깨 버렸다. 추후 remove 를 이용해서 삭제를 깔끔하게 처리하는 방법에 대해 적어 놓도록 하겠다.

 

벡터의 반복자에는 추가적으로 const_interator 와 reverse_iterator 가 있는데,  const_iterator 는 이름에서 유추할 수 있듯 상수 반복자로, iterator 가 가리키는 값을 바꿀 수 없는 속성을 가진다. reverse_iterator 는 다음과 같이 역으로 벡터를 순회할 수 있는 반복자이다.

상수 반복자가 있는 것처럼, const_reverse_iterator 라는, 상수 역반복자도 존재한다!

  std::vector<int>::reverse_iterator r_iter = vec.rbegin();
  for (; r_iter != vec.rend(); r_iter++) {
    std::cout << *r_iter << std::endl;
  }

 

사실 반복자에는 여러 종류가 있고, 각각의 컨테이너는 이에 맞는 반복자를 상속받아 사용한다. 상속관계는 다음과 같다.

벡터의 경우 Random Access Iterator를, 리스트의 경우 Bidirectional Iterator를, 덱의 경우 Random Access Iterator 를 사용한다고 이해하면 된다.

 

범위 기반 for 문 (ranged based for loop)

범위 기반 for 문을 이용하면 간단하고 빠르게 컨테이너의 원소를 순회할 수 있다.

  // range-based for 문
  for (int elem : vec) {
    std::cout << "원소 : " << elem << std::endl;
  }

범위 기반 for 문은 벡터 뿐만이 아니라, 순방향 반복자(forward Iterator)를 지원하는 다른 컨테이너에서도 마찬가지로 사용 가능하다.

 

 

리스트 (list)

리스트는 양방향 연결 구조를 가진 자료형이다.

Random Access Iterator 가 아닌, Bidirectional Iterator 를 사용하므로 임의의 위치의 원소에 접근을 할 수는 없지만, 대신 임의의 위치에 원소를 추가하거나 제거하는 작업은 O(1) 로 매우 빠르다! 이는 해당 위치 앞뒤의 링크값만 바꾸어 주면 되기 때문이다.

 

 

덱 (deque - double ended queue)

덱은 Random Access Iterator 를 사용하여 임의의 위치의 원소에 접근할 수 있으며, 맨뒤/맨앞의 원소를 추가/제거하는 작업도 O(1) 으로 수행이 가능하다. 임의의 위치에 원소를 제거/추가하는 작업은 O(n) 으로 수행 가능하다. 덱의 메모리 구조는 다음과 같다.

 

덱은 벡터와 달리 원소들이 메모리상에서 연속적으로 존재하지 않는다. 대신 블록별로 메모리가 저장되고, 이를 위해 추가적인 메모리를 필요로 한다. 그렇다면 덱은 어째서 맨 뒤에 요소를 추가하는 작업이 O(1) 밖에 들지 않을까? 다음과 같은 경우를 보자.

 

삽입 전

삽입 후

삽입 전과 삽입 후를 보면, 벡터처럼 기존 영역을 재할당하지 않고, 그냥 블록을 하나 더 추가하는 방식으로 메모리 부족 문제를 해결했다! 따라서 평균적으로 덱이 벡터보다 더 빠르게 작동하게 된다. 특히 맨 처음과 끝에 원소를 추가하는 작업을 많이 할 경우, 덱을 사용하면 유리하다.

 

물론 대부분의 상황에서는 벡터를 사용하는 것이 좋다! 벡터가 최적화가 잘 되어 있다고 한다.

 

참고 : 시퀀스 컨테이너들의 모든 함수들 링크