[전문가를 위한 C++] 17장. 컨테이너와 반복자 살펴보기

Chapter 17. 컨테이너와 반복자 살펴보기

컨테이너 개요

• 다양한 데이터를 묶음 단위로 저장하는 제네릭 데이터 구조다.
• 표준 라이브러리의 컨테이너는 모두 클래스 템플릿으로 구현되어 있어 기본 조건만 만족한다면(원소에 대한 요구사항) 거의 모든 타입에 대해 인스턴스화 하여 사용할 수 있다.
• array와 bitset을 제외한 표준 라이브러리 컨테이너는 모두 크기를 조절할 수 있고 추가 삭제에 따라 크기가 자동으로 결정된다.
  • vector (동적 배열)
  • deque
  • list
  • forward_list
  • array
  • map
  • multimap
  • set
  • multiset
  • unordered_map
  • unordered_multimap
  • unordered_list
  • unordered_multilist
  • queue
  • priority_queue
  • stack
  • 순차 컨테이너
  • 연관 컨테이너
  • 비정렬 연관 컨테이너 (해시 테이블)
  • 컨테이너 어댑터
• 표준 라이브러리에 있는 것들은 모두 std 네임스페이스에 속한다.
  • using namespace std; (이 문장을 절대로! 헤더 파일에 넣으면 안 된다.)

원소에 대한 요구사항

• 표준 라이브러리 컨테이너는 원소를 값으로 처리한다. (value semantics)
  • 원소의 복제본을 작성하고, 대입 연산자로 대입하고, 소멸자로 원소를 삭제한다. 그래서 표준 라이브러리를 사용하는 클래스를 작성할 때는 반드시 복제할 수 있도록 만들어야 한다.
• 표준 라이브러리 컨테이너에서 원소를 요청하면 저장된 복제본에 대한 레퍼런스를 리턴한다.
• 원소를 레퍼런스로 처리하고 싶다면,
  • 원소를 그대로 넣지 말고 원소에 대한 포인터를 저장한다.
  • 혹은 컨테이너에 std::reference_wrapper을 저장한다. 이것은 std::ref(), std::cref()로 생성되며, <functional> 헤더 파일에 정의 되어 있다.
• 표준 라이브러리 컨테이너에 대한 템플릿 타입 매개변수 중에는 할당자(allocator)라는 것이 있다.
  • 원소에 대한 메모리를 할당하거나 해제할 수 있다.
• map과 같은 일부 컨테이너는 템플릿 타입 매개변수로 비교자도 받을 수 있다.
  • 원소를 정렬하는 데 사용.
• 요구사항은 다음과 같다.
  • 복제 생성자
  • 이동 생성자
  • 대입 연산자
  • 이동 대입 연산자
  • 소멸자
  • 디폴트 생성자
  • operator==
  • operator<

익셉션과 에러 검사

• 표준 라이브러리 컨테이너는 에러 검사 기능을 제공한다.

반복자

• 입력
• 출력
• 정방향
• 양방향
• 랜덤 액세스 (임의 접근)

순차 컨테이너

• vector
  • 원소를 연속된 메모리 공간에 한 자리 씩 차지하게 저장한다.
  • vector 개요

    • <vector> 헤더 파일에 정의된 클래스 템플릿으로, 저장할 원소의 타입과 할당자 타입을 매개변수로 담는다.

      template<class T, class Allocator = allocator<T> >> class vector;
      

    • Allocator 매개변수는 클라이언트가 메모리 할당 방식을 커스터마이즈하는 데 사용된다. 디폴트로 정해져 있다.

  • 동적 크기 vector
    • push_back() 메서드로 vector에 추가한다. 새로 추가한 원소에 대한 메모리는 vector가 알아서 할당한다.
  • vector 세부 기능

    • 생성자와 소멸자

        // 원소 수와 각각의 초깃값을 지정할 수 있다.
        vector<int> intvector(10, 100);  // 초깃값이 100인 int 원소 10개를 담은 vector 생성
      
        // vector를 생성할 때 초기 원소를 이니셜라이저리스트(initializer_list)로 지정해도 된다.
        vector<int> intvector({1, 2, 3, 4, 5});
      
        // 유니폼 초기화 사용 가능 
        vector<int> intvector1 = {1, 2, 3, 4, 5};
        vector<int> intvector2{1, 2, 3, 4, 5};
      
        // Heap에 할당 가능 
        auto Elementvector = make_unique<vector<Element>>;
      

  • vector 복제와 대입
    • vector는 객체의 복사본을 저장한다.
    • vector의 소멸자는 원소 객체의 소멸자를 호출하도록 되어 있다.
    • vector 클래스의 복제 생성자와 대입 연산자는 vector 원소를 복제할 때 깊은 복제를 수행한다.
      • 성능을 높이려면 메서드에 vector 전달 시 레퍼런스나 const 레퍼런스로 전달하는 것이 좋다.

    • assign() 메서드로 vector를 재사용할 수 있다. (이니셜라이저리스트 사용 가능)

      vector<int> vectorOne(10);
      vector<int> vectorTwo(5, 100);
      vectorOne.swap(vectorTwo);
      

    • swap() 메서드로 두 vector를 상수 시간에 맞 바꾼다.

      vector<int> vectorOne(10);
      vector<int> vectorTwo(5, 100);
      vectorOne.swap(vectorTwo);
      

  • vector 비교
    • 표준 라이브러리에서 제공하는 vector는 비교 연산자를 오버로딩한 버전을 제공한다.
    • 커스텀 클래스에서 객체를 저장한 vector를 비교하려면 반드시 커스텀 클래스에 비교 연산자가 오버로딩 구현 되어 있어야 한다.
    • vector 반복자

      • begin()은 컨테이너의 첫번째 원소를 참조하는 반복자를 리턴한다.

        for (vector<double>::iterator it = begin(douvlevector); it != end(doublevector); ++it) {...}
        

      • end()는 vector의 마지막 원소의 다음 원소를 가리키는 반복자를 리턴한다.

  • vector에 레퍼런스 저장하기

    • vector와 같은 컨테이너에 레퍼런스를 저장할 수 있다.

      string str1 = "Hello";
      string str2 = "World";
      
      vector<reference_wrapper<string>> vec{ref(str1)};
      vec.push_back(ref(str2));
            
      vec[1].get() += "!";  // 앞에서 만든 vector의 두 번째 원소(레퍼런스)가 참조하는 스트링 값을 변경한다.
      

  • 원소 추가와 삭제
    • insert() 메서드를 이용하면 원하는 지점에 원소를 추가할 수 있다.
      • 원소 하나만 추가
      • 원소 하나에 대한 n개의 복제본 추가
      • 반복자 범위로 지정된 원소들을 추가
      • 지정한 원소를 이동 의미론을 적용해서 vector에 이동시켜 추가
      • 원소 리스트를 initializer_list에 지정해서 vector에 추가
    • push_back(), insert()는 rvalue, lvalue를 매개변수로 받는 버전도 있다.
    • erase() 메서드를 이용하면 vector에 담긴 원소 중 원하는 것을 제거할 수 있다.
      • 반복자 하나를 인수로 받아 원소 하나만 삭제
      • 삭제할 원소 범위를 지정하여 두 개의 반복자를 인수로 받는다.
    • 원소를 모두 삭제하려면 clear()를 사용한다.
    • 이동 의미론
      • 표준 라이브러리에서 제공하는 컨테이너는 모두 이동 의미론을 구현하도록 이동 생성자와 이동 대입 연산자가 제공된다.
      • 따라서 표준 라이브러리 컨테이너를 함수에서 값으로 리턴해도 성능 오버헤드를 최소화 할 수 있다.

      • push 연산도 특정한 상황에서 이동 의미론을 적용해 성능을 높일 수 있다.

         vector<string> vec;
         string myElement(5, 'a');
        
         vec.push_back(myElement);  // myElement는 임시객체가 아니기 때문에 복제본을 만들어 vector에 추가한다.
         vec.push_back(move(myElement));  // push_back(const T& val)의 이동 의미 버전인 push_back(T&& val)도 지원하므로 이렇게 호출하면 복제 연산이 발생하지 않는다.
        
         // 다음과 같이 push_back을 호출하면 이동 의미론 버전이 호출된다. 여기서 호출한 string 생성자는 임시 객체를 생성하기 때문이다. 
         // push_back 메서드는 이렇게 생성된 임시 string 객체를 vector로 복제하지 않고 이동시킨다.
         vec.push_back(string(5, 'a'));
        

  • 임플레이스 연산

    • 특정한 지점에 설치한다. 복제나 이동 작업을 수행하지 않고, 컨테이너에 공간을 마련해서 객체를 그 자리에서 바로 생성한다.

      vec.emplace_back(5, 'a');
      

  • 추가된 원소에 대한 레퍼런스를 리턴한다. (C++17)
  • 알고리즘 복잡도와 반복자 무효화
  • vector의 메모리 할당 방식
    • vector는 기본적으로 연속된 메모리 공간에 원소를 저장하며 원소 추가 시 메모리가 자동으로 할당된다.
    • 원소를 추가하다가 공간이 모자라면 더 큰 공간을 새로 할당 받아 기존 원소들을 모두 새 공간으로 이동하고 복제해야 한다.
    • 따라서 재 할당 발생 가능성을 최소화 하기 위해 실제로 필요한 양보다 더 많이 할당 받는다.
    • 재 할당이 발생하면 원소 추가 시 선형 시간의 복잡도를 가지게 된다. 그리고 기본 반복자들이 무효가 된다.
    • 따라서 vector는 vector의 재할당 상태를 조회하거나 직접 제어하는 인터페이스도 제공한다.
• vector<bool> 특수화
  • 음… bitset쓰라고 권장함.
• deque
  • <deque> 헤더 파일에 정의 되어 있다.
  • vector에 비해 안 쓰인다고 자세한 설명 안 한다고 함.
• list
  • <list> 헤더 파일에 정의 되어 있는 이중 연결 리스트를 구현한 표준 라이브러리 클래스 템플릿.
  • 리스트의 모든 지점에서 원소를 추가하거나 삭제하는 속도는 상수 시간이지만, 각각의 원소를 조회하는 작업은 다소 느린 선형 시간에 처리한다.
  • operator[]처럼 랜덤 액세스 연산을 지원하지 않고, 반복자로만 개별 원소에 접근할 수 있다.
  • 생성자, 소멸자, 복제 연산자, 대입 연산자, 비교연산자 등 대부분은 vector와 같지만 다른 연산은 아래와 같다.
  • 원소 접근 연산
    • front(), back() : 리스트에 담긴 첫 번째와 마지막 원소에 대한 레퍼런스를 리턴한다. 나머지는 반복자로만 접근할 수 있다.
    • begin(), end()
    • cbegin(), cend(), rbegin(), rend(), crbegin(), crend()
  • 반복자
    • list는 랜덤 액세스를 지원하지 않기 때문에, list반복자끼리 더하거나 뺄 수 없고, 반복자를 가리키는 포인터에 대해 산술 연산을 할 수 없다.
    • list반복자에 대한 포인터 p가 있을 때, ++p, –p와 같은 연산으로 list 원소를 탐색할 수 있지만 p+n, p-n과 같이 덧셈이나 뺄셈 연산자를 적용할 수는 없다.
  • 원소 추가와 삭제 연산
    • push_back(), pop_back(), emplace(), emplace_back(), 다섯 가지 버전의 insert(), 두 가지 버전의 erase(), clear() 등.
  • list 크기와 관련된 연산
    • list는 vector와 다르게 내부 메모리 모델에 관련된 메서드가 없다.
    • size(), empty(), resize()는 제공하지만 reserve(), capacity()와 같은 메서드를 제공하지 않는다는 뜻이다.
  • list의 특수 연산

    • splace() : 이어붙이기

      auto iterLastB = --(cend(bWords));
      auto it = cbegin(dictionary);
      for (; it != cend(dictionary); ++i) {
          if (*it > *iterLastB) break;
      }
      dictionary.splice(it, bWords);  // bWords에 있던 원소가 삭제된다.
      for (const auto& word: dictionary) {
          cout << word << endl;
      }
      // splice()에는 두 가지 버전이 더 있다. 다른 리스트에 있는 원소 하나를 추가하는 버전, 다른 리스트 일부 원소들을 추가하는 버전.
      

    • 좀 더 효율적인 버전의 알고리즘

      • remove(), remove_if() : list에서 특정 원소를 제거한다.
      • unique() : list에서 같은 원소가 연달아 나오는 부분을 제거한다.
      • merge() : 두 리스트를 합친다. 둘 다 정렬된 상태여야 한다. 원본을 변경한다.
      • sort() : 리스트를 정렬한다.
      • reverse() : 리스트의 순서를 반대로 바꾼다.
• forward_list
  • <forward_list>
• array
  • 크기가 고정된 점을 제외하면 vector와 같다. 고정 시킨 이유는 원소를 스택에 할당하기 위해서다.
  • fill() 메서드로 array를 특정 원소로 채울 수 있다.
  • swap() 메서드 성능이 선형 시간이다. (벡터는 상수)

  • std::get() 함수 템플릿으로 std::array의 N인덱스에 있는 원소를 가져올 수 있다. 인덱스는 반드시 상수여야 한다.

    array<int, 3> myArray(11, 12, 13);
    cout << std::get<1>(myArray) << endl;
    cout << std::get<10>(myArray) << endl;  // compile error.
    

컨테이너 어댑터

• 일종의 wrapper다. 내부적으로 순차 컨테이너를 사용한다.
• queue
  • <queue>
  • queue 연산
  • push(), emplace() 메서드로 큐의 끝에 원소를 추가할 수 있다.
  • pop()은 큐의 앞에서 원소를 제거한다.
  • front(), back()을 이용하면 원소를 제거하지 않고도 맨 앞과 맨 뒤의 원소에 대한 레퍼런스를 구할 수 있다.
• priority_queue
  • <queue>
  • 맨 앞(헤더)에 있는 원소의 우선순위가 가장 높다. 디폴트 설정에 따르면 이 순서는 operator< 연산에 따라 낮은 쪽이 낮은 우선순위를 갖도록 정한다.
  • priority_queue 연산
    • push(), emplace() 원소 추가,
    • pop() 원소 제거,
    • top() 맨 앞의 원소에 대한 const 레퍼런스 리턴
    • size(), empty(), swap()을 지원한다. 비교 연산자는 지원하지 않는다.
• stack

정렬 연관 컨테이너

• pair 유틸리티 클래스
• map
• multimap
• set
• multiset

비정렬 연관 컨테이너 (해시 테이블)

• 해시 함수
• unordered_map
• unordered_multimap
• unordered_set과 unordered_multimap

기타 컨테이너

• 표준 C 스타일 배열
• string
• 스트림
• bitset