[Effective STL] 1. 컨테이너(Container)

항목 1. 적재적소에 알맞은 컨테이너를 사용하자

 

 

 

컨테이너의 종류

• 표준 STL 시퀀스(sequence) 컨테이너
  • vector, string, deque, list
• 표준 STL 연관(associative) 컨테이너
  • set, multiset, map, multimap
• 비표준 시퀀스 컨테이너 (항목 50 참조)
  • slist(단일 연결 리스트), rope(대용량 string)
• 비표준 연관 컨테이너 (항목 25 참조)
  • hash_set, hash_multiset, hash_map
  • 다만 모던 C++에서는 unordered_set, unordered_map 등을 표준으로 지원함.
• string 대신 사용되는 vector<char> (항목 13 참조)
  • 간혹 이렇게 쓰면 괜찮을 때가 있다.
• 표준 연관 컨테이너 대신 사용되는 vector (항목 23 참조)
  • vector가 수행 속도나 크기 면에서 표준 연관 컨테이너보다 더 나은 경우가 있다.
• STL에 속하지 않는 표준 컨테이너 (항목 16 참조)
  • C++ 배열, bitset, valarray, stack, queue, priority_queue
  • 하지만 이제 C++ 배열을 제외하고는 모두 STL에 포함된다.

 

 

 

STL 컨테이너의 분류

• 연속 메모리(contiquous-memory) 컨테이너
  • 동적 할당된 하나 이상(대개 하나)의 메모리 단위(chunk)에다가 데이터 요소를 저장해 두는 컨테이너.
  • 각 청크는 하나 이상의 요소를 담고 있다.
  • 삽입, 삭제 시, 같은 청크의 요소들은 앞, 뒤로 밀려나며 새 요소가 삽입될 공간을 만들던가, 지워진 공간을메운다.
• 노드 기반(node-based) 컨테이너
  • 동적 할당된 하나의 청크에다가 하나의 요소만을 저장한다.
  • 삽입, 삭제 시, 노드의 포인터만이 영향을 받고 노드의 내용은 그대로이다.

 

 

 

어떤 상황에 어떤 컨테이너를 쓰면 가장 좋을까?

• 컨테이너의 아무 위치에 요소를 삽입할 수 있어야 하나?
  • 시퀀스 컨테이너를 사용한다.
• 컨테이너 내의 요소들의 순서 결정에 직접 관여해야 하나?
  • 해쉬 컨테이너는 사용할 수 없다.
• 표준 C++에 포함된 컨테이너를 사용해야 하나?
  • slist, rope는 사용할 수 없다.
• 임의 접근 반복자가 필요한가?
  • vector, deque, string, rope(항목 50 참조) 를 사용한다.
• 양방향 반복자가 필요한가?
  • slist와 해쉬 컨테이너는 사용할 수 없다.
• 요소 삽입이나 삭제 시 다른 컨테이너 요소들이 밀려나는 일이 없어야 하나?
  • 연속 메모리 컨테이너는 사용할 수 없다.
• 컨테이너 내의 데이터가 C의 데이터 타입과 메모리 배열 구조적으로 호환되어야 하나?
  • vector만을 사용할 수 있다.
• 탐색 속도가 중요한가?
  • 해쉬 컨테이너(항목 25 참조), 정렬된 vector(항목 23 참조), 표준 연관 컨테이너 순으로 고려해본다.
• 컨테이너의 참조 카운팅을 사용하고 싶지 않은가?
  • string은 고려하지 않는다.
    • 많은 string 코드가 참조 카운팅이 되도록 구현되어 있다.(항목 13 참조)
  • rope는 확실히 참조 카운팅 기반으로 구현되어 있다.(항목 50 참조)
  • 대신 vector<char>를 사용한다.
• 삽입과 삭제 동작이 트랜잭션적인 의미를 가지길 바라는가?
  • 즉, 삽입과 삭제 동작을 안정적으로 롤백할 수 있어야 하는가? (항목 17 참조)
    • 예외 안전성(exception safety)에 중요한 특징이다.
  • 노드 기반 컨테이너를 사용한다.
• 반복자, 포인터 참조자가 무효화(invalidation, 포인터가 가리키고 있던 메모리의 실제 내용이 없어짐)되는 일을 최소화해야 하는가? 
  • 노드 기반 컨테이너를 사용한다.
  • 연속 메모리 컨테이너는 전체적인 메모리 재할당이 빈번하므로 무효화되기 쉽다.

    • std::vector<int> vec = {1, 2, 3};
      int* ptr = &vec[0];
      vec.push_back(4); // 벡터 확장으로 인해 기존 요소의 위치가 변경될 수 있음
      // ptr은 이제 유효하지 않음 (invalidated)

• 임의 접근 반복자를 지원하는 시퀀스 컨테이너가 필요한데, 요소 삭제가 일어나지 않고 요소 삽입이 컨테이너의 끝에서만 일어나는 한, 포인터와 참조자가 무효화되지 않는 작업이 필요한가?
  • deque를 사용한다.
    • 요소 삽입이 끝에서 일어날 때, 반복자만 무효화된다.
    • 즉, 포인터와 참조자는 무효화되지 않는다.
    • STL 컨테이너 중 포인터와 참조자는 보장되고, 반복자만 무효화되는 것은 deque가 유일하다.
• 각 컨테이너 타입에서 사용하는 메모리 할당 전략에 따른 고려(항목 10, 항목 14 참조)