20. Containers and Iterators

20.1. Storing and Processing Data

데이터를 온라인으로 수집해 처리하는 예를 보자.

20.1.1. Working with data

배열을 순회하면서 최대 원소를 가져오려고 할 때 포인터를 쓰는 C 식의 해결법은 매우 번거롭다.

20.1.2. Generalizing code

C 식 배열과 C++ 식 std::vector를 전부 순회할 수 있는 일반적인 메커니즘은 없을까?

20.2. STL Ideals

STL에서는 일반적인 자료형과 컨테이너에 대응하기 위한 일반화된 메커니즘을 통해 다음 기능들을 제공한다.

  • 데이터에 대한 일관적인 접근
  • 데이터가 저장된 방식에 대해 독립적인 인터페이스
  • 데이터의 자료형에 대해 독립적인 인터페이스
  • 데이터에 대한 타입 안전한 접근
  • 데이터에 대한 간편한 순회
  • 데이터에 대한 컴팩트한 저장
  • 빠른 속도
  • 데이터에 대한 참조
  • 데이터 추가
  • 데이터 삭제
  • 표준화된 범용 알고리즘

20.3. Sequences and Iterators

STL에서는 컨테이너를 순회할 수 있는 반복자를 제공한다. 반복자는 포인터로 구현될 때도 있지만 포인터여야 하는 것은 아니다. 포인터가 아닌, 구간 범위를 체크하는 반복자도 만들 수 있다.

20.3.1. Back to the example

구간을 순회하며 최대값을 찾는 알고리즘은 다음과 같이 구현한다.

template<typename Iterator>
Iterator high(Iterator first, Iterator last)
          // return an iterator to the element in [first:last) that has the highest value
{
          Iterator high = first;
          for (Iterator p = first; p!=last; ++p)
                    if (*high<*p) high = p;
          return high;
}

20.4. Linked Lists

std::vector 외에 중요한 자료구조는 std::list이다. 대개 이중 연결 리스트로 구현된다.

20.4.1. List operations

std::list는 시작/끝 반복자, 원소 삽입/삭제 등의 연산을 제공해야 한다. 연속된 배열이 아니므로 operator[] 는 제공하지 않는다. O(1) 시간에 할 수 없기 때문이다. 즉, 무작위 접근 반복자가 아닌 양방향 반복자이다.

20.4.2. Iteration

반복자는 *, ++, ==, != 연산을 제공해야 한다. 양방향 반복자는 –, 무작위 접근 반복자는 거기에 추가로 operator[]도 제공한다.

20.5. Generalizing std::vector Yet Again

using iterator, using size_type, using const_iterator 등을 통해 컨테이너의 내부 구현과 순회 인터페이스를 분리할 수 있다.

20.5.1. Container traversal

range-for 순회를 통해 무작위가 아닌 반복자를 제공하는 컨테이너도 제네릭하게 순회할 수 있다.

20.5.2. auto

반복자 타입을 일일히 치기는 번거로우니 auto로 치자. 문자열 리터럴은 auto로 받을 경우 std::string이 아니라 const char*임에 주의하자.

20.6. An Example : A Simple Text Editor

라인 단위로 처리를 하는 텍스트 에디터는 std::list가 std::vector보다 더 적합한 몇 안되는 예 중 하나이다.

20.6.1. Lines

라인에 대한 인터페이스를 정의해 입력을 받는다.

20.6.2. Iteration

STL 알고리즘 중 반복자를 리턴하는 경우를 잘 이용하자.

20.7. std::vector, std::list and std::string

std::vector, std::list, std::string의 장단점을 잘 비교해 보자. 다만, C 스타일 배열은 장점이 거의 없다.

20.7.1. insert and erase

std::vector에서 반복자가 가리키는 원소를 이동시킨 경우 그 반복자는 무효화된다. 무효화된 반복자를 사용하는 것은 정의되지 않은 행동이므로 극히 주의해야 한다. std::list는 삽입/삭제 시 반복자가 무효화되지 않는다는 장점이 있다. 대신 std::list는 메모리를 많이 먹는다.

20.8. Adapting our vector to the STL

insert()와 erase()를 직접 구현해 보자.

20.9. Adapting built-in arrays to the STL

C 스타일 배열에 대한 가벼운 래퍼로 std::array이 존재한다. 이는 항목에 대한 초기화를 해주지 않는다.

20.10. Container Overview

  • std::vector : 연속적으로 할당된 배열. 기본 컨테이너 선택.
  • std::list : 이중 연결 리스트. 존재하는 원소를 이동시키지 않고 삽입/삭제를 빈번하게 하고 싶을 때
  • std::deque : std::vector와 std::list의 중간 격. 초보자용이 아님.
  • std::map : 균형 이진 탐색 트리. 순서를 정렬된 채 유지하면서 값으로 항목을 접근하고 싶을 때.
  • std::multimap : std::map에서 키의 중복을 허용.
  • std::unordered_map : 해시 테이블. 값으로 항목을 접근하고 싶을 때.
  • std::unordered_multimap : std::unordered_map에서 키의 중복을 허용.
  • std::set, std::multiset, std::unordered_set, std::unordered_multiset : 위의 4가지 버전에서 키-값 쌍이 아닌 키만 저장하는 버전.
  • std::array : C 스타일 배열의 래퍼.

컨테이너가 아닌 것들:

  • 기본 배열.
  • std::string.
  • std::valarray.

20.10.1. Iterator categories

반복자의 범위는 입력/출력 반복자 ⊆ 전방 반복자 ⊆ 양방향 반복자 ⊆ 무작위 접근 반복자이다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중