전문가를 위한 C++/ 컨테이너와 반복자 살펴보기

Contents

(전체가 아니라 C#과 차이가 있는 부분을 중심으로 요약 정리)

컨테이너 개요

표준 라이브러리를 이용하면 표준 C 스타일 배열ㅇㄹ 사용하거나 연결 리스트나 스택 등을 직접 구현할 필요가 없다. 

표준 라이브러리는 16가지 컨테이너를 제공하며 크게 네 가지 범주로 나눌 수 있다.

  • 순차 컨테이너
    • vector
    • deque
    • list
    • forward_list
    • array
  • 연관 컨테이너
    • map
    • multimap
    • set
    • multiset
  • 비정렬 연관 컨테이너(해시 테이블)
    • unordered_map
    • unordered_multimap
    • unordered_set
    • unordered_multiset
  • 컨테이너 어댑터
    • queue
    • priority_queue
    • stack

원소에 대한 요구사항

표준 라이브러리 컨테이너는 원소를 값으로 처리한다. (값 전달 방식, value semantics) 다시 말해 원소의 복제본을 저장하고, 대입 연산자로 대입하고 소멸자로 원소를 샂게한다. 그래서 표준 라이브러리를 사용하는 클래스를 작성할 때는 반드시 복제할 수 있게 (copyable) 만들어야 한다. 표준 라이브러리 컨테이너에서 원소를 요청하면 저장된 복제본에 대한 레퍼런스를 리턴한다.

원소를 레퍼런스로 처리하고 싶다면(레퍼런스 전달 방식, reference semantics) 원소를 그대로 넣지 않고 원소에 대한 포인터를 저장한다. 그러면 컨테이너에서 복제하는 대상이 포인터지만 복제된 값도 결국 똑같은 원소를 가리킨다. 아니면 컨테이너에 std::reference_wrapper를 저장해도 된다. reference_wrapper는 std::ref()나 std::cref()로 생성하며 결과로 나온 레퍼런스를 복제할 수 있게 만든다.

이동 전용(move-only) 타입, 즉 복제할 수 없는 (non-copyable) 타입도 컨테이너에 저장할 수 있지만 이때 컨테이너의 연산 중 일부는 컴파일 에러를 발생시킬 수 있다. 이동 전용 타입의 대표적인 예로 std::unique_ptr이 있다.

Caution) 컨테이너에 포인터를 저장하려면 unique_ptr나 shared_ptr을 사용한다. 포인터가 가리키는 객체의 소유자가 컨테이너라면 unique_ptr을 사용하고 컨테이너가 객체의 소유권을 다른 컨테이너와 공유한다면 shared_ptr을 사용한다.

표준 라이브러리 컨테이너에 대한 템플릿 타입 매개변수 중에는 할당자(allocator)라는 것이 있다. 컨테이너는 이 할당자를 이용하여 원소에 대한 메모리를 할당하거나 해제할 수 있다. 할당자 타입 매개변수는 디폴트 값이 정해져 있어서 거의 대부분 그냥 써도 된다.

map과 같은 일부 컨테이너는 템플릿 타입 매개변수로 비교자(comparator)도 받을 수 있다. 비교자는 원소를 정렬하는데 사용된다. 비교자도 디폴트 값이 정해져 있어서 매번 값을 지정할 필요가 없다.

디폴트 할당자와 비교자를 사용하는 컨테이너의 원소가 만족해야 할 요구사항은 다음과 같다.

메서드 설명 노트
복제 생성자 기존 원소와 ‘똑같은’ 원소를 새로 생성하며, 기존 원소에 아무런 영향을 미치지 않고 안전하게 제거할 수 있다. 원소를 추가할 때마다 호출된다. 단 뒤에서 설명할 emplace 메서드를 사용할 때는 호출되지 않는다.
이동 생성자 원본 원소에 있는 내용을 모두 새 원소로 이동하는 방식으로 원소를 새로 만든다. 원본 원소가 rvalue일 때 호출되며 새 원소가 생성된 후에는 제거된다. 또한 vector의 크기가 늘어날 때도 호출된다. 이동 생성자는 반드시 noexcept로 지정해야 한다. 그렇지 않으면 호출되지 않는다.
대입 연산자 원소의 내용을 원본의 복제본으로 교체한다. 원소를 수정할 때마다 호출된다.
이동 대입 연산자 원소의 내용을 원본 원소의 모든 내용으로 교체한다. 원본 원소가 rvalue일 때 호출되며, 대입 연산자의 실행이 끝나면 제거된다. 이동 대입 연산자는 반드시 noexcept로 지정해야 한다. 그렇지 않으면 호출되지 않는다.
소멸자 원소를 삭제한다. 원소를 제거할 때마다 호출된다. 또는 vector의 크기가 증가할 때 그 안에 담긴 원소가 noexcept로 지정되지 않고 이동시킬 수 없을 때 호출된다.
디폴트 생성자 아무런 인수 없이 원소를 생성한다. 인수가 하나 뿐인 vector::resize() 나 map::operator[]와 같은 특정한 연산에서만 필요하다.
operator== 두 원소가 같은지 비교한다. 비순차(비정렬) 연관 컨테이너의 키를 비교하거나 두 컨테이너를 operator==과 같은 특정한 연ㅅ나으로 비교할 때 필요하다.
operator< 두 원소의 크기를 비교한다 순차(정렬) 연관 컨테이너의 키를 비교하거나 두 컨테이너를 operator<와 같은 특정한 연산으로 비교할 때 필요하다.

Caution) 표준 라이브러리 컨테이너는 원소의 복제 생성자와 복제 대입 연산자를 호출하는 일이 많다. 따라서 두 연산자를 최대한 효율적으로 구현해야 한다. 원소에 대해 이동 의미론을 구현하는 것도 성능을 높이는데 도움 된다.

익셉션과 에러 검사

표준 라이브러리 컨테이너는 에러 검사 기능을 제공한다. 클라이언트는 이 기능으로 컨테이너 동작의 정확성을 보장할 수 있다고 기대하겠지만, 컨테이너 메서드나 함수 중 일부는 인덱스 범위를 벗어날 떄와 같은 특정한 조건에서 익셉션을 던지기도 한다.

반복자

표준 라이브러리는 컨테이너의 원손에 접근하는 기능을 범용적으로 제공하기 위해 반복자(iterator) 패턴을 사용한다. 컨테이너마다 원소에 대해 반복문을 수행할 방법이 담긴 특수한 스마트 포인터인 반복자가 정의돼 있다. 컨테이너의 종류가 달라도 반복자의 인터페이스는 모두 C++ 표준을 따르므로 모두 같다. 그래서 구체적인 동작은 달라도 컨테이너의 원소에 대해 반복문을 비슷한 방식으로 작성할 수 있도록 인터페이스는 통일돼 있다.

반복자는 컨테이너의 특정 원소에 대한 포인터로 생각할 수 있다. 배열에서 원소를 가리키는 포인터처럼 반복자도 operator++ 연산자를 이용하여 다음 원소로 이동할 수 있다. 또한 반복자로 원소의 필드나 원소 자체에 접근할 때 operator*나 operator->를 사용할 수도 있다. 어떤 반복자는 operator=나 operator!=로 비교하거나 operator–로 이전 원소로 이동하는 기능도 제공한다.

반복자는 반드시 복제 생성자, 복제 대입 연산자, 소멸자를 제공해야 한다. 반복자의 좌측값(lvalue)는 반드시 맞교환할 수 있어야 한다. 반복자의 기능은 컨테이너마다 약간씩 다르다. 표준에서는 다음표와 같이 반복자를 다섯 가지로 분류해서 정의하고 있다.

반복자 종류 필수 연산자 설명
입력(또는 읽기) operator++
operator*
operator->
복제 생성자
operator=
operator==
operator!=
읽기 전용이며 정방향(forward)으로만 사용할 수 있다. (역방향으로 이동하는 operator–는 없다)
이 반복자를 대입하거나 복제하거나 서로 같은지 비교할 수 있다.
출력(또는 쓰기) operator++
operator*
복제생성자
operator=
쓰기 전용이며, 정방향으로만 접근할 수 있다.
이 반복자를 대입할 수는 있지만, 서로 같은지 비교할 수는 없다.
출력 반복자는 *iter = value도 할 수 있다.
operator->는 없다는 점에 주의한다.
operator++에 대한 선행(prefix, 전위) 연산자 버전과 후행(postfix, 후위) 연산자 버전을 모두 제공한다.
정방향 입력/읽기 반복자의 연산자에 디폴트 생성자가 추가됨 읽기 및 정방향 전용이다.
반복자를 대입하거나 복제하거나 서로 같은지 비교할 수 있다.
양방향 정방향 반복자의 연산자에 다음 연산자 추가 
operator–
정방향 반복자에서 제공하는 기능을 모두 제공한다.
역방향으로 이동해서 이전 원소에 접근할 수 있다.
operator–에 대한 선행 연산자 버전과 후행 연산자 버전을 모두 제공한다.
랜덤 액세스 양방향 반복자의 연산자에 다음 연산자 추가
operator+
operator-
operator+=
operator-=
operator<
operator>
operator<=
operator>=
operator[]
일반 포인터와 같다. 포인터 산술 연산, 배열 인덱스 구문 그리고 모든 종류의 비교 연산을 지원한다.

여기서 출력 반복자의 요구사항을 만족하는 반복자를 가변 반복자(mutable iterator)라 부르고, 그렇지 않은 반복자를 상수(불변) 반복자 (constant iterator)라 부른다.

std::distance()를 이용하면 컨테이너의 두 반복자 사이의 거리(항목 수)를 구할 수 있다.

반복자는 특정한 연산자만 오버로딩한다는 점에서 스마트 포인터 클래스와 구현 방식이 비슷하다.

반복자의 기본 연산은 일반 포인터와 비슷하다. 그래서 일반 포인터를 얼마든지 특정한 컨테이너에 대한 반복자로 쓸 수 있다. 실제로 vector의 반복자를 일반 포인터로 구현할 수 있다. 

Note) 반복자는 내부적으로 포인터로 구현됐을 수도 있고 그렇지 않을 수도 있다.

Note) 순차 컨테이너(sequential container), 정렬 연관 컨테이너(ordered associative container), 비정렬 연관 컨테이너(unordered associative container)만 반복자를 제공한다. 컨테이너 어댑터와 bitset 클래스는 우너소에 대한 반복자를 제공하지 않는다.

반복자를 지원하는 표준 라이브러리의 컨테이너 클래스는 모두 반복자 타입에 대해 public 타입 앨리어스인 iterator와 const_iterator를 제공한다. 예컨대 int 타입 원소에 대한 vector의 const 반복자 타입은 std::vector<int>::const_iterator다. 역방향 반복을 지원하는 컨테이너는 reverse_iterator와 const_reverse_iterator란 이름의 public 타입 앨리어스도 제공한다. 그래서 이렇나 컨테이너 반복자를 사용하는 코드는 구체적인 타입에 신경쓰지 않고 반복자를 작성할 수 있다.

Note) const_iterator와 const_reverse_iterator는 컨테이너의 원소를 읽기 전용으로 접근한다.

컨테이너는 반복자를 리턴하는 begin()과 end() 메서드를 제공한다. begin()은 첫 번째 항목을 참조한느 반복자를 리턴하고, end()는 마지막 항목의 바로 다음 원소에 해당하는 지점을 가리키는 반복자를 리턴한다. 다시 말해 end()는 마지막 우너소를 가리키는 반복자에 operator++를 적용한 결과를 리턴한다. begin()과 end()는 모두 첫 번째 원소는 포함하지만 마지막 원소는 포함하지 않은 반개방 범위(half-open range)를 지원한다. 이렇게 복잡하게 구성된 이유는 빈 구간을 지원하기 위해서다. 다시 말해 구간이 비어있을 때는 begin()과 end()의 결과가 같다. begin()과 end() 반복자로 묶인 반개방 범위를 수학 기호로 [begin, end]라고 표현하기도 한다.

Note) 반개방 범위란 개념은 insert()나 erase()와 같은 컨테이너 메서드에 전달할 반복자 구간에도 적용된다.

다음과 같은 메서드도 제공된다.

  • const 반복자를 리턴하는 cbegin()과 cend() 메서드
  • 역방향 반복자를 리턴하는 rbegin()과 rend() 메서드
  • const 역방향 반복자를 리턴하는 crbegin()과 crend() 메서드

Note) 표준 라이브러리는 비멤버 전역 함수인 std::begin(), end(), cbegin(), cend(), rbegin(), rend(), crbegin(), crend()도 제공한다. 클래스의 멤버 메서드보다는 이처럼 비멤버 전역함수를 이용하는 것이 좋다.

순차 컨테이너

vector

vector의 개요

(내용 생략)

vector의 세부 기능

(내용 생략)

vector 반복자

앞서 소개한 프로그램에서 for 문을 범위 기반 for 문이 아닌 반복자를 사용하는 버전으로 수정하면 다음과 같다.

for (vector<double>::iterator iter = begin(doubleVector); iter != end(doubleVector); ++iter)
{
*iter /= max;
cout << *iter << " ";
}

먼저 for 문의 초기화 부분을 살펴보자.

vector<double>::iterator iter = begin(doubleVector);

앞서 설명했듯이 컨테이너 타입에 대한 반복자가 iterator란 타입 이름으로 정의돼 있다. begin()은 컨테이너의 첫 번째 원소를 참조하는 반복자를 리턴한다. 그래서 앞에 나온 초기화 문장을 실행하면 doubleVector의 첫 번째 원소를 참조하는 반복자가 iter 변수에 대입된다. 다음으로 for 문의 종료 조건을 표현하는 비교문을 살펴보자.

iter != end(doubleVector);

이 문장은 반복자가 참조하는 지점이 doubleVector의 마지막 원소를 지났는지 검사한다. 그래서 마지막 원소를 지났다면 루프를 종료한다. 증가연산을 수행하는 부분(++iter)은 반복자가 vector의 다음번 원소를 참조하도록 위치를 증가시킨다.

Note) 가능하면 후행 증가(post-increment)보다는 선행 증가(pre-increment)를 지정하는 것이 좋다. 선행 증가가 대체로 성능이 좋기 때문이다. iter++는 반드시 새로운 반복자 객체를 리턴하는 반면, ++iter는 iter에 대한 레퍼런스만 리턴한다.

반복자를 이용하는 for 문에서 auto 키워드를 사용하면 한결 간결하게 표현할 수 있다.

for (auto iter = begin(doubleVector); iter != end(doubleVector); ++iter)
{
*iter /= max;
cout << *iter << " ";
}
const_iterator

일반적으로 반복자는 읽기와 쓰기를 모두 할 수 있지만 const 객체에 대해 begin()이나 end()를 호출하거나 non-const 객체에 대해 cbegin()이나 cend()를 호출하면 const_iterator가 리턴된다. const_iterator는 읽기 전용이다. 따라서 반복자가 참조하는 원소를 수정할 수 없다. iterator는 언제든 const_iterator로 변환할 수 있다. 그래서 다음과 같이 작성하는 것이 안전성 측면에서 바람직하다.

vector<type>::const_iterator it = begin(myVector);

하지만 반대로 const_iterator를 iterator로 변환할 수는 없다.

Note) vector의 원소를 수정할 필요가 없다면 const_iterator를 사용하기 바란다. 그러면 코드의 정확성을 보장하기 쉽고 컴파일러가 코드의 성능을 최적화하는데도 도움 된다.

auto 키워드를 사용할 때는 const_iterator를 다르게 작성해야 한다. 예컨대 다음 코드를 보자.

vector<string> stringVector(10, "hello");

for (auto it = begin(stringVector); it != end(stringVector); ++it)
{
cout << *it << endl;
}

여기서 auto 키워드를 사용했기 때문에 컴파일러는 it 변수의 타입을 자동으로 추론하는데, 이 과정에서 stringVector는 const가 아니기 때문에 iterator로 바뀐다. 따라서 읽기 전용 const_iterator를 auto와 함께 사용할 때는 begin(), end()대신 cbegin(), cend()를 호출해야 한다.

vector<string> stringVector(10, "hello");

for (auto it = cbegin(stringVector); it != cend(stringVector); ++it)
{
  cout << *it << endl;
}

범위 기반 for 문에서도 다음과 같이 작성하면 항상 const 반복자를 사용하게 만들 수 있다.

vector<string> stringVector(10, "hello");

for (const auto element : stringVector)
{
cout << element << endl;
}
반복자의 안전성

일반적으로 반복자의 안전성(safety)은 포인터와 같다. 한마디로 안전성이 상당히 떨어진다. 예컨대 다음 코드를 보자.

vector<int> intVector;
auto iter = end(intVector);
*iter = 10; // 버그! iter가 벡터 원소를 가리키지 않고 있다.

앞서 설명했듯이 end()가 리턴하는 반복자는 vector의 마지막 원소가 아닌 그 다음 원소를 가리킨다. 따라서 end()의 리턴값을 역참조 하면 예상과 다른 결과가 나온다. 반복자는 어떠한 검증 작업도 거치지 않는다.

반복자가 서로 일치하지 않을 때도 문제가 발생한다. 예컨대 다음 코드에 나온 for 문을 보면 vectorTwo에 대한 begin()에서 리턴한 반복자로 iter를 초기화한 다음 vectorOne에 대한 end()에서 리턴한 반복자와 비교하고 있다. 이렇게 작성하면 당연히 무한 루프에 빠지게 된다. 이렇게 엉뚱한 반복자를 역참조하면 예상할 수 없는 결과가 발생한다.

vector<int> vectorOne(10);
vector<int> vectorTwo(10);

// 벡터에 원소를 채운다.

// 버그! 무한루프에 빠질 수 있다.
for (auto iter = begin(vectorTwo); iter != end(vectorOne); ++iter)
{
// 본문
}

Note) MS의 비주얼 C++은 기본적으로 디버그 모드로 빌드할 때 위와 같은 문제를 발견하면 어서션 에러(assertion error)를 발생시킨다. 릴리스 모드로 빌드하면 아무런 검증 작업도 수행하지 않는다. 이러한 디폴트 설정은 얼마든지 변경할 수 있지만 검증 작업을 추가하면 성능이 좀 떨어진다.

반복자의 다른 연산

vector 반복자는 랜덤 액세스를 지원한다. 다시 말해 앞뒤로 이동하거나 곧바로 원하는 원소로 건너뛸 수 있다. 다음 코드는 다섯 번째(4번 인덱스) 원소의 값을 4로 바꾸는 예를 보여준다.

vector<int> intVector(10);
auto it = begin(intVector);
it += 5;
--it;
*it = 4;
반복자와 인덱싱

vector의 원소에 대해 반복하는 for문을 인덱스 변수와 size() 메서드만으로 간단히 작성할 수 있다면 굳이 반복자가 필요 없을 것이다. 하지만 다음 세 가지 경우는 반복자를 사용하는 것이 유리하다.

  • 반복자를 사용하면 원소 또는 여러 우너소를 담은 시퀀스를 컨테이너의 원하는 지점에 추가하거나 삭제하기 쉽다.
  • 반복자를 사용하면 표준 라이브러리의 알고리즘을 사용하기 좋다.
  • 컨테이너를 순차적으로 접근할 때는 인덱스로 원소를 하나씩 조회하는 것보다 반복자를 사용하는 것이 더 효율적이다. vector에 대해서는 그렇지 않을 때도 있지만 list, map, set에 대해서는 반복자를 사용하는 것이 항상 빠르다.

(이하 내용 생략)

임플레이스 연산

C++은 vector를 비롯한 대부분의 표준 라이브러리 컨테이너에 대해 임플레이스(emplace) 연산을 지원한다. 임플레이스란 ‘특정한 지점에 설치’한다는 뜻이다. 예컨대 vector에서 제공하는 emplace_back() 메서드가 있다. 이 메서는 복제나 이동 작업을 수행하지 않고, 컨테이너에 공간을 마련해서 객체를 그 자리에 바로 생성한다. 예컨대 다음과 같다.

vec.emplace_back(5, 'a');

emplace 메서드는 인수를 가변 인수 템플릿으로 받기 때문에 인수의 개수를 다양하게 지정할 수 있다. 가변 인수 템플릿은 22장에서 설명하겠지만 자세히 몰라도 emplace_back()을 사용하는데 문제없다. 이동 의미론 버전의 push_back과 emplace_back()의 성능 차이는 컴파일러의 구현 방식에 따라 다르다. 대부분 두 가지 중에서 마음에 드는 방식으로 작성하면 된다.

vec.push_back(string(5, 'a'));

// 또는

vec.emplace_back(5, 'a');

C++ 17부터 emplace_back() 메서드는 추가된 원소에 대한 레퍼런스를 리턴한다. 그 전에는 void 타입을 리턴했다.

vector는 emplace() 메서드도 제공한다. 이 메서드는 vector의 특정 지점에 객체를 바로 생성한 뒤 그 원소를 가리키는 반복자를 리턴한다.

알고리즘 복잡도와 반복자 무효화

vector에 원소를 추가하거나 삭제하면 공간을 확보하거나 채우기 위해 남은 원소를 적절히 이동시킨다. 따라서 원소의 추가와 삭제 연산의 복잡도는 선형 시간이다. 또한 추가나 삭제 지점을 참조하는 반복자는 그 연산이 끝난 뒤에는 사용할 수 없다. vector의 원소가 변경된 결과에 따라 반복자를 자동으로 조정해주지 않기 때문이다. 따라서 프로그래머가 적절히 대응해야 한다.

또한 vector의 내부에서 공간 재할당이 발생하면 추가나 삭제 대상이 되는 원소를 가리키는 반복자 뿐만 아니라 다른 지점에 대한 기존 반복자들도 모두 무효가 된다. 다음 절에서 살펴보자.

vector의 메모리 할당 방식

vector에 원소를 추가할 때는 메모리가 자동으로 할당된다. vector는 표준 C 스타일 배열처럼 원소를 연속된 메모리 공간에 저장한다. vector에 현재 할당된 메모리 공간 바로 뒤에 새 메모리를 요청할 수 없기 때문에 vector에 원소를 추가하다 공간이 모자라면 더 큰 공간을 새로 할당 받아서 기존 원소를 모두 새 공간으로 이동하거나 복제해야 한다. 이런 일이 발생하면 시간이 오래 걸리기 때문에 vector를 구현할 때 재할당 발생 가능성을 최소화하도록 실제로 필요한 양보다 더 많이 할당 받는다.

vector의 내부 메모리 할당 방식을 알아야 하는 이유는 다음 두 가지다.

  1. 효율성
    • vector의 메모리 할당 방식은 원소의 추가 연산에 대해 분할 상환 상수 시간의 복잡도를 보장한다. 다시 말해 대다수의 추가 연산은 상수 시간에 처리되지만 간혹 재할당이 발생할 때처럼 선형 시간의 복잡도를 가질 수 있다. 효율성이 중요하다면 vector의 재할당 방식을 직접 관리하면 된다.
  2. 반복자 무효화
    • 메모리 재할당이 발생하면 vector의 원소를 참조하던 기본의 반복자들이 모두 무효가 된다.
크기와 용량

vector는 size()와 capacity() 메서드를 통해 크기에 대한 정보를 두 종류로 제공한다. size() 메서드는 vector에 담긴 원소 개수(벡터 크기)를 리턴하는 반면 capacity()는 재할당 없이 담을 수 있는 원소 개수(벡터 용량)를 리턴한다. 따라서 현재 상태에서 재할당 없이 추가할 수 있는 원소 개수는 capacity() – size()다.

Note) empty() 메서드를 이용하면 현재 vector가 비어 있는지 확인할 수 있다. vector가 비어 있어도 capacity()의 리턴값은 0이 아니다.

C++ 17부터 전역 함수인 std::size()와 std::empty()가 추가됐다. 이 함수는 std::begin()과 std::end()가 반복자에 대한 전역 함수 버전인 것과 비슷하다. 전역 함수 버전의 size()와 empty()는 모든 컨테이너에 대해 호출할 수 있다. 또한 포인터로 접근하지 않는 C 스타일의 정적 할당 배열에도 적용할 수 있고, initializer_list에도 적용할 수 있다.

예비 용량

프로그램을 최대한 효율적으로 만들거나 반복자가 무효화되지 않게 만들고 싶다면 vector에서 모든 원소를 확실히 담을 수 있도록 미리 공간을 충분히 할당해야 한다. 물론 이렇게 하려면 vector에 담길 원소 수를 미리 알아야 하는데, 경우에 따라 예측하기 힘들 수 있다.

공간을 미리 확보하기 위한 한 가지 방법은 reverse()를 호출하는 것이다. 이 메서드는 지정한 수의 원소를 충분히 담을 만큼의 공간을 할당한다. 

Caution) 원소에 대한 예비 공간을 확보하면 컨테이너의 크기(size())가 아닌 용량(capacity())이 커진다. 다시 말해 실제로 원소가 추가되는 것이 아니다. vector의 크기(size())를 넘은 지점의 원소를 접근하면 안 된다.

공간을 미리 확보하는 또 다른 방법은 vector에 담길 원소 수를 vector의 생성자나 resize() 또는 assign() 메서드로 지정하는 것이다. 이렇게 하면 vector를 원하는 크기로 생성할 수 있으며 용량도 그에 맞게 적절히 설정된다.

데이터에 직접 접근하기

vector는 데이터를 연속된 메모리 공간에 저장한다. data() 메서드를 호출하면 vector에서 데이터가 있는 메모리 블록에 대한 포인터를 구할 수 있다.

C++ 17부터 std::data()라는 전역 함수가 추가됐다. 이 함수는 array나 vector 컨테이너, string, 포인터로 접근하지 않는 정적 할당 C 스타일 배열, 그리고 initialize_list에 대해 호출할 수 있다.

vector 사용 예: 라운드-로빈 클래스

전산학에서 리소스 수가 유한할 때 이에 대한 요청을 잘 분배하는 문제를 흔히 볼 수 있다. 대표적인 예로 OS의 프로세스 스케줄러가 있다. OS는 프로세스마다 작업을 수행할 수 있는 시간(타임 슬라이스(time slice, 예: 100ms))를 할당하는 방식으로 프로세스를 관리한다.

프로세스에 할당된 시간이 만료되면 OS는 그 프로세스를 잠시 중단시키고, 다음 차례의 프로세스에 타임 슬라이스를 할당해서 작업을 수행할 기회를 준다. 이러한 문제를 해결하는 알고리즘 중에 가장 간단한 것으로 라운드 로빈 스케줄링(round-robin scheduling) 알고리즘이 있다.

(이하 예시 코드 생략)

vector<bool> 특수화

C++ 표준에 따르면 bool 타입 vector를 구현할 때 공간 효율을 최적화하도록 여러 부울 값을 묶어서(패킹, packing) 처리하도록 명시하고 있다. 앞서 설명했듯이 bool 값은 true나 false 중 하나를 가질 수 있는데, 이러한 두 가지 값은 한 비트로 표현할 수 있다.

그런데 C++의 기본 타입에는 비트 하나만 표현하는 것이 없다. 그래서 어떤 컴파일러는 부울값을 char로 처리하고 어떤 컴파일러는 int로 활용한다. 따라서 vector<bool>은 한 비트짜리 bool 값들을 배열로 저장하는 방식으로 공간을 절약한다.

Note) vector<bool> 은 vector 보다는 비트 필드(bit-field)에 가깝다. 비트 필드의 구현 관점에서 볼 때 vector<bool> 보다는 bitset 컨테이너가 더 뛰어나다. 하지만 vector<bool>은 크기를 동적으로 조절할 수 있다는 장점이 있다.

완벽한 방법은 아니지만 vector<bool>을 위한 비트 필드 루틴을 구현하기 위해 flip() 메서드를 제공하고 있다. 이 메서드를 컨테이너에 대해 호출하면 그 컨테이너에 담긴 원소를 모두 반전시키고, operator[]와 같은 메서드가 리턴한 레퍼런스에 대해 호출하면 해당 원소만 반전시킨다.

그런데 bool 타입 레퍼런스에 대해 메서드를 호출할 방법이 없다. vector<bool>은 내부적으로 bool 타입(비트)을 표현하는 (bool에 대한 프록시(proxy)인) reference란 클래스를 정의하는 방식으로 구현한다. operator[], at()과 같은 메서드를 호출하면 vector<bool>은 reference 타입의 객체를 리턴하며, 실제 bool 값 대신 이 객체를 사용한다.

Caution) vector<bool>에서 리턴한 reference 객체는 사실 일종의 프록시라서 컨테이너에 담긴 원소에 대한 포인터(주소)를 구하는데 사용할 수 없다.

프로그래머 입장에서 볼 때 bool 값을 패킹함으로써 얻을 수 있는 공간 절약 효과보다 이렇게 구현하는데 드는 노력이 훨씬 크다. 게다가 vector<bool>의 원소를 조회하거나 수정하는 속도는 vector<int> 처럼 특정 타입에 대한 vector보다 훨씬 느리다.

그래서 C++ 전문가는 대부분 vector<bool> 보다는 bitset을 쓰도록 권장한다. 크기를 동적으로 조절할 수 있는 비트필드가 필요하다면 vector<std::int_fast8_t>나 vector<unsigned char>를 쓰는게 낫다. std::int_fast8_t 타입은 <cstdint> 헤더에 정의돼 있다. 부호 있는 정수 타입이므로 컴파일러에서 이를 처리할 때 최소 8비트 이상인 정수 타입 중에서 가장 빠른 것을 적용해야 한다.

deque

deque(double-ended queue, 덱)은 vector와 거의 같지만 vector보다 활용도는 낮다.

deque는 vector에 비해 거의 사용되지 않기 때문에 자세히 설명하지 않겠다.

list

list는 이중 연결 리스트(doubly-linked list)를 구현한 표준 라이브러리 클래스 템플릿이다.

리스트의 모든 지점에 원소를 추가하거나 삭제하는 속도는 상수 시간이지만 각각의 원소를 조회하는 작업은 다소 느린 선형 시간이다. 사실 list는 operator[]처럼 랜덤 액세스 연산을 제공하지 않는다. 반복자로만 개별 원소에 접근할 수 있다.

list에서 제공하는 대부분의 연산은 vector와 같기 때문에 vector와 다른 부분만 소개한다.

원소 접근 연산

list에서 원소에 접근하는 용도로 제공하는 메서드는 front()와 back() 뿐이다. 둘 다 상수 시간에 처리한다. 이 메서드는 각각 list에 담긴 첫 번째와 마지막 원소에 대한 레퍼런스를 리턴한다. 나머지 원소는 반복자로만 접근할 수 있다.

list는 첫 번째 원소를 참조하는 반복자를 리턴하는 begin() 메서드와 list의 마지막 원소 바로 다음 항목을 참조하는 반복자를 리턴하는 end() 메서드를 제공한다. 또한 vector와 마찬가지로 cbegin(), cend(), rbegin(), rend(), crbegin(), crend()도 제공한다.

반복자

list의 반복자는 양방향으로 작동한다. vector의 반복자와 달리 랜덤 액세스는 지원하지 않는다. 그래서 list는 반복자끼리 더하거나 뺄 수 없고, 반복자를 가리키는 포인터에 대해 산술 연산을 할 수 없다.

예컨대 list 반복자에 대한 포인터 p가 있을 때 ++p, –p와 같은 연산으로 list의 원소를 탐색할 수 있지만 p+n이나 p-n 같이 덧셈이나 뺄셈 연산자를 적용할 수는 없다.

원소 추가와 삭제 연산

list도 vector처럼 원소를 추가하고 삭제하는 메서드를 제공한다. 이런 메서드로 push_back(), pop_back(), emplace(), emplace_back(), 다섯 가지 버전의 insert(), 두 가지 버전의 erase(), clear() 등이 있다. deque와 마찬가지로 push_front(), emplace_front(), pop_front()도 제공한다.

clear()를 제외한 모든 메서드는 정확한 위치를 지정할 수 있다면 상수 시간에 처리된다. 따라서 list는 데이터 구조에 추가나 삭제 연산이 빈번하지만 원소를 인덱스로 빠르게 접근할 일은 없는 애플리케이션에 적합하다. 그렇다 해도 vector가 훨씬 빠르다.

list 크기에 관련된 연산

list는 deque처럼 내부 메모리 모델에 관련된 메서드가 없다. 그래서 size(), empty(), resize()는 제공하지만 reverse(), capacity()와 같은 메서드는 제공하지 않는다.

참고로 list에 대한 size() 메서드의 성능 복잡도는 상수지만 forward_list에 대한 size()는 그렇지 않다.

list의 특수 연산

list는 원소의 빠른 추가와 삭제 성능을 활용한 몇 가지 특수 연산을 제공한다.

splice()

list는 기본적으로 연결 리스트이기 때문에 한 리스트를 통째로 다른 리스트에 이어붙이기(splice, 스플라이스) 할 수 있다. 이 연산은 상수 시간에 처리된다. 이 메서드에 대한 간단한 예는 다음과 같다.

// a로 시작하는 단어를 저장한 리스트를 만든다.
list<string> dictionary{ "aardvark", "ambulance" };

// b로 시작하는 단어를 저장한 리스트를 만든다.
list<string> bWrods{ "bathos", "balderdash" };

// 첫 번째 리스트에 c로 시작하는 단어를 추가한다.
dictionary.push_back("canticle");
dictionary.push_back("consumerism");

// b로 시작하는 단어를 저장한 리스트를 첫 버째 리스트에 이어붙인다.

if (!bWords.empty())
{
// b로 시작하는 원소 중 마지막 항목을 참조하는 반복자를 구한다.
auto iterLastB = --(cend(bWords));

// b로 시작하는 단어를 넣을 위치까지 반복한다.
auto it = cbegin(dictionary);

for (; it != cend(dictionary); ++it)
{
if (*it > *iterLastB)
{
break;
}
}

// b로 시작하는 단어를 추가한다. 그러면 bWords에 있던 원소가 삭제된다.
dictionary.splice(it, bWords);
}

// 결과를 화면에 출력한다.
for (const auto& word : dictionary)
{
cout << word << endl;
}

splice()는 두 가지 버전이 더 있다. 하나는 다른 list에 있는 원소 하나를 추가하는 것이고 다른 하나는 다른 list에서 특정한 범위에 있는 원소를 통째로 추가하는 것이다. 또한 splice()의 모든 버전은 원본 list에 대한 일반 레퍼런스나 우측값(rvalue) 레퍼런스를 받을 수 있다.

Caution) 인수로 전달한 list에 splice() 연산을 적용하면 원본 list가 변경된다. 다른 list에 추가하면 원본 list에 있던 원소는 삭제되기 때문이다.

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

list는 splice() 외에도 표준 라이브러리의 제네릭 알고리즘을 list에 특화시킨 버전을 제공한다.

Note) 가능하면 표준 라이브러리에서 제공하는 제네릭 알고리즘보다 list에 특화된 메서드를 사용하는 것이 좋다. 후자가 훨씬 효율적이기 때문이다. 때로는 어쩔 수 없이 list에 특화된 메서드를 사용해야 하는 경우가 있다. 예컨대 제네릭 std::sort() 알고리즘을 사용하려면 RandomAccessIterators를 써야하는데 list에서는 이를 제공하지 않기 때문에 list에서 제공하는 sort() 메서드를 사용할 수 밖에 없다.

메서드 설명
remove()
revmoe_if()
list에서 특정한 원소를 제거한다.
unique() list에서 같은 원소가 연달아 나온 부분을 제거한다. 이때 operator==이나 사용자가 지정한 이항 프리디케이트(binary predicate, 인수 두 개를 받아서 bool 값을 리턴하는 함수 객체)를 활용한다.
merge() 두 list를 합친다. 둘 다 operator<나 사용자가 지정한 비교 연산자로 정렬된 상태여야 한다. splice()와 마찬가지로 merge()도 인수로 전달된 list를 변경한다.
sort() list을 정렬한다. 순위가 같은 원소는 그대로 둔다.
reverse() list의 순서를 반대로 바꾼다.

list 활용 예제: 입학 등록 관리 프로그램

(생략)

forward_list

forward_list는 단방향 연결 리스트란 점을 제외하면 양방향 연결 리스트인 list와 비슷하다. 이름에서 알 수 있듯 forward_list는 한 방향으로만 반복할 수 있다. 그래서 범위를 지정하는 방식도 list와 다르다. 리스트를 변경하려면 대상 원소가 처음 나오는 지점의 바로 전 원소에 접근해야 한다.

하지만 forward_list의 반복자는 역방향으로 이동할 수 없기 때문에 바로 직전 원소를 구하기 쉽지 않다. 그래서 수정할 대상을 가리키는 범위(예: erase()나 splice()에 지정할 범위)의 시작 부분은 반드시 열려있어야 한다.

앞서 살펴본 begin() 함수는 첫 번째 원소를 참조하는 반복자를 리턴하므로 시작이 닫힌 범위를 만들 때만 사용할 수 있다. 그래서 forward_list 클래스는 before_begin()이란 메서드를 제공한다. 이 메서드는 리스트의 시작 우너소의 바로 전에 있는 가상의 원소를 가리킨다. 말 그대로 가상의 데이터를 가리키기 때문에 이 반복자를 역참조 할 수는 없다. 하지만 이 반복자를 하나 증가시키면 begin()이 리턴한 반복자와 같아진다. 따라서 시작이 열린 범위를 만들 수 있다.

(이하 list와 차이점 내용 생략)

array

array는 크기가 고정된 점을 제외하면 vector와 같다. 다시 말해 크기를 늘리거나 줄일 수 없다. 크기를 고정시키는 이유는 vector처럼 항상 힙에 저장해서 접근하지 않고 원소를 스택에 할당하기 위해서다. vector와 마찬가지로 array의 반복자도 랜덤 액세스를 지원하고, 원소를 메모리에 연속적으로 저장한다.

array는 front(0, back(), at(), operator[]를 제공한다. array를 특정 원소로 채우는 fill()도 지원한다. 크기가 고정되어 있기 때문에 push_back(), pop_back(), insert(), erase(), clear(), resize(), reserve(), capacity() 등은 지원하지 않는다.

vector에 비해 아쉬운 점은 array의 swap() 메서드 성능이 선형 시간이라는 점이다. vector는 이 연산을 상수 시간에 처리한다. 또한 array는 vector와 달리 상수 시간에 이동할 수 없다. array는 size() 메서드를 제공하기 때문에 C 스타일 배열보다 훨씬 좋다.

(이하 예시 생략)

컨테이너 어댑터

표준 라이브러리는 queue, priority_queue, stack 등 세 가지 컨테이너 어댑터(container adaptor)도 제공한다. 각각 내부적으로 순차 컨테이너를 사용한다. 일종의 래퍼다. 그래서 내부 컨테이너를 교체하더라도 어댑터를 사용하는 코드에 아무런 영향을 주지 않는다. 이렇게 어댑터를 제공하는 목적은 인터페이스를 간결하게 제공할 뿐만 아니라 stack이나 queue 같은 추상 개념에 적합한 부분만 외부에 노출하기 위해서다. 그래서 여러 원소를 동시에 추가/ 삭제하는 기능이나 반복자는 제공하지 않는다.

queue

queue는 표준 FIFO(First-In First-Out, 선입선출) 방식을 구현한 것이다. queue도 클래스 템플릿으로 구현됐으며 다음과 같이 선언한다.

template<class T, class Container = deque<T>> class queue;

템플릿 매개변수 T는 queue에 저장할 타입을 지정한다. 두 번째 템플릿 매개변수는 queue의 내부에 사용할 컨테이너를 지정한다. 그런데 queue에서 push_back()과 pop_front()를 모두 지원하려면 순차 컨테이너를 지정해야 한다. 결국 기본으로 제공되는 컨테이너 중에서는 deque이나 list 중 하나만 쓸 수 있다. 대부분 디폴트값인 deque를 그대로 쓴다.

queue 연산

queue 인터페이스는 굉장히 간단하다. 메서드 8개와 생성자, 일반 비교 연산자가 전부다. push()와 emplace() 메서드는 큐의 끝에 원소를 추가하는 반면 pop()은 큐의 앞에서 원소를 제거한다. front()와 back()을 이용하면 원소를 제거하지 않고도 맨 앞과 맨 뒤의 원소에 대한 레퍼런스를 구할 수 있다.

또한 다른 메서드처럼 const 객체에 대해 호출하면 const 레퍼런스를 리턴하고, non-const 객체에 대해 호출하면 const가 아니면서 읽고 쓸 수 있는 레퍼런스를 리턴한다.

queue는 size(), empty(), swap()도 제공한다.

queue 사용 예: 네트워크 패킷 버퍼

(예시 생략)

priority_queue

priority_queue(우선순위 큐)는 원소를 정렬된 상태로 저장하는 큐다. FIFO에 따라 정렬하지 않으며, 맨 앞에 있는 원소의 우선순위가 가장 높다. 그래서 큐에 가장 오랫동안 저장된 것일 수도 있고, 가장 최근에 추가된 것일 수도 있다. 우선순위가 같은 원소 중 어느 것을 먼저 처리할지는 명확히 정해져 있지 않다.

(이하 설명 생략)

priority_queue 연산

priority_queue에서 제공하는 연산의 종류는 queue 보다 훨씬 적다. push()와 emplace() 메서드는 원소를 추가하고, pop() 메서드는 원소를 제거하고, top() 메서드는 맨 앞의 원소에 대한 const 레퍼런스를 리턴한다.

Caution) non-const 객체에 대해 top()을 호출해도 const 레퍼런스를 리턴한다. 원소를 수정하면 순서가 바뀔 수 있기 때문이다. priority_queue는 맨 끝(tail) 우너소를 구하는 메서드를 제공하지 않는다.

queue와 마찬가지로 priority_queue도 size(), empty(), swap()을 지원하지만 비교 연산자는 제공하지 않는다.

priority_queue의 사용 예: 에러 상관관계(ErrorCorrelator V1)

(예시 생략)

stack

stack은 queue와 거의 같다. FIFO가 아닌 FILO(First-In Last-Out, 선입후출) 또는 LIFO(Last-In, First-Out, 후입선출)란 점만 다르다.

stack의 내부 컨테이너로 vector, list 또는 deque를 사용할 수 있다.

stack 연산

queue와 마찬가지로 stack도 push(), emplace(), pop() 메서드를 제공한다. 하짐나 queue와 달리 push()는 최상단에 원소를 추가하고, 그 전에 있던 원소를 모두 아래로 밀어낸다. 또한 pop()은 stack에 가장 최근에 추가한 최상단 원소를 제거한다.

top() 메서드를 const 객체에 대해 호출하면 최상단 원소에 대한 const 레퍼런스를 리턴하고, non-const 객체에 대해 호출하면 non-const 레퍼런스를 리턴한다.

stack은 empty(), size(), swap()과 표준 비교 연산자도 지원한다.

stack 사용 예: 에러 상관관계(ErrorCorrelator V2)

(생략)

정렬 연관 컨테이너

정렬 연관 컨테이너는 순차 컨테이너와 달리 원소를 한 줄로 저장하지 않고 키와 값의 쌍으로 저장한다. 연관 컨테이너에서 제공하는 추가, 삭제, 조회 연산의 성능은 대체로 비슷하다.

표준 라이브러리는 map, multimap, set, multiset이라는 네 종류의 정렬 연관 컨테이너를 저장한다. 각각 원소를 트리 형태의 데이터 구조에 정렬된 상태로 저장한다.

또한 unordered_map, unordered_multimap, unordered_set, unordered_multiset이라는 비정렬 연관 컨테이너도 제공한다.

pair 유틸리티 클래스

정렬 연관 컨테이너를 보기 전에 pair 클래스부터 알아보자. pair는 두 값을 그룹으로 묶는 클래스 템플릿이다. 두 값의 타입은 서로 다르게 지정할 수 있다. pair에 담긴 두 값은 각각 first와 second라는 public 데이터 멤버로 접근한다. pair에 정의된 operator==와 operator<는 두 pair의 first와 second 원소를 모두 비교한다.

(예시 코드 생략)

표준 라이브러리는 두 값으로 pair를 만들어주는 make_pair()라는 유틸리티 함수 템플릿도 제공한다. 예컨대 다음과 같다.

pair<int, double> aPair = make_pair(5, 10.10);

물론 이렇게 하지 않고 pair 클래스에서 제공하는 인수 두 개를 받는 생성자로 만들어도 된다. 하지만 make_pair()는 함수에 pair를 전달하거나 미리 정의된 변수에 pair를 대입할 때 유용하다. 클래스 템플릿과 달리 함수 템플릿은 매개변수에 대한 타입을 추론할 수 있기 때문에 make_pair()로 pair를 생성할 때 명시적으로 타입을 지정하지 않아도 된다. 게다가 다음과 같이 make_pair()는 auto 키워드와 함께 사용할 수 있다.

auto aSecondPair = make_pair(5, 10.10);

C++ 17부터는 생성자에 대해서도 템플릿 매개변수 추론 기능이 추가됐다. 그래서 make_pair()를 쓸 필요 없이 곧바로 다음과 같이 작성해도 된다.

auto aThirdPair = pair(5, 10.10);

또한 C++ 17부터 구조적 바인딩도 추가됐다. 그래서 다음과 같이 pair에 속한 원소를 각자 다른 변수로 분리할 수 있다.

pair<string, int> myPair("hello", 5);
auto[thString, thInt] = myPair; // 구조적 바인딩으로 pair의 원소를 분리한다.
cout << "theString: " << theString << endl;
cout << "theInt: " << theInt << endl;

map

map은 단일 값이 아닌 키와 값의 쌍으로 저장한다. 추가, 조회, 삭제 연산도 모두 키를 기준으로 수행한다. 닶은 단지 키에 딸린 값을 뿐이다. map이란 용어는 이 컨테이너가 키를 값에 매핑(mapping) 한다는 개념에서 따온 것이다.

map은 원소를 키 값을 기준으로 정렬된 상태로 유지한다. 그래서 추가, 삭제, 조회 연산의 성능이 모두 로그 시간이다. 순서가 있기 때문에 원소를 나열하면 원소의 타입에 대한 operator< 연산이나 사용자가 정의한 비교자를 순서대로 나열된다.

대체로 레드-블랙 트리(red-black tree)와 같은 균형 트리(balanced tree) 형태로 구현한다. 물론 트리 구조는 클라이언트에 드러나지 않는다. ‘키’를 이용하여 원소를 저장하거나 조회하면서 일정한 순서를 유지하고 싶다면 map을 사용한다.

map 생성하기

map 클래스 템플릿은 키 타입, 값 타입, 비교 타입, 할당자 타입이라는 네 가지 타입을 매개변수로 받는다.

(이하 설명 생략)

원소 추가하기

vector나 list와 같은 순차 컨테이너에 원소를 추가하려면 항상 추가할 위치를 지정해야 한다. 하지만 map은 다른 정렬 연관 컨테이너와 마찬가지로 위치를 지정할 필요가 없다. map은 새로 추가할 원소의 위치를 내부적으로 알아서 결정하기 때문에 키와 값만 지정하면 된다.

Note) map을 비롯한 정렬 연관 컨테이너는 반복자의 위치를 인수로 받는 버전의 insert() 메서드도 제공한다. 하지만 여기서 지정하는 위치는 단지 ‘힌트’에 불과할 분 컨테이너가 반드시 그 위치에 원소를 추가한다는 보장은 없다.

원소를 추가할 때 map에 있는 키가 중복되면 안 된다. 다시 말해 map에 있는 키는 고유한 값이어야 한다. 키가 같은 원소를 여러 개 넣으려면 두 가지 방법을 사용할 수 있다. 하나는 map에서 어떤 키에 대한 값을 vector나 array 같은 다른 컨테이너를 저장하는 것이고, 다른 하나는 multimap을 사용하는 것이다.

(이하 설명 생략)

map의 반복자

map의 반복자는 순차 컨테이너의 반복자와 비슷하게 작동한다. 다른 반복자와 가장 큰 차이점은 하나의 값이 아닌 키/값으로 구성된 pair를 가리킨다는 점이다. 값에 접근하려면 반드시 pair 객체의 second 필드를 조회해야 한다. map의 반복자는 양방향으로 작동한다. 그래서 앞이나 뒤로 탐색할 수 있다. map을 반복자로 탐색하는 방법은 다음과 같다.

for (auto iter = cbegin(dataMap); iter != cend(dataMap); ++iter)
{
cout << iter->second.getValue() << endl;
}

여기서 값에 접근하는 부분을 보자.

iter->second.getValue();

iter는 키/값 pair를 가리킨다. 그래서 pair의 second 필드인 Data 객체에 접근할 때 -> 연산자를 사용했다. 그러고 나서 Data 객체의 getValue() 메서드를 호출해서 값을 구했다. 참고로 다음과 같이 ㅈ가성해도 된다.

(*iter).second.getValue()

범위 기반 for 문으로 작성하면 다음과 같이 좀 더 직관적으로 표현할 수 있다.

for (const auto& p : dataMap)
{
cout << p.second.getValue() << endl;
}

C++ 17부터 추가된 구조적 바인딩을 적용하면 훨씬 세련되게 표현할 수 있다.

for (const auto& [key, data] : dataMap)
{
cout << p.second.getValue() << endl;
}

Caution) non-const 반복자로도 원소의 값을 변경할 수 있지만 우너소의 키를 변경할 때는 컴파일 에러가 발생한다. 키가 달라지면 map에 담긴 원소의 정렬 순서가 바뀔 수 있기 때문이다.

원소 조회하기

map에서 주어진 키로 원소를 조회하는 연산의 성능은 로그 시간이다. map에서 지정한 키로 원소를 조회하는 가장 간단한 방법은 operator[]로 조회하는 것이다. 단 이 연산은 non-const map에 대해 호출하거나 map에 대한 non-const 레퍼런스에 대해 호출해야 한다.

operator[]이 좋은 점은 원소에 대한 레퍼런스를 리턴하기 때문에 pair 객체에서 값을 빼오지 않고도 그 자리에서 값을 직접 수정하거나 활용할 수 있다는 것이다.

그런데 원소기 이미 있는지 모르는 상태에서 operator[]를 호출하면 안 된다. 지정한 키에 대해 원소가 없다면 원소를 새로 만들어서 추가할 수 있기 때문이다. 이렇게 하지 않고 map에서 제공하는 find() 메서드로 원하는 키에 대한 원소를 참조하는 iterator를 리턴받거나 주어진 키에 대해 값이 없다면 end() 반복자를 활용해도 된다.

auto it = dataMap.find(1);

if (it != end(dataMap))
{
it->second.setValue(100);
}

이처럼 find() 메서드를 사용하면 코드가 약간 지저분해진다. 주어진 키에 대한 원소가 map에 존재하는지만 알고 싶다면 count() 메서드를 활용한다. 이 메서드는 지정한 키에 대해 map에 담긴 원소 수를 리턴한다. map에 대해 이 메서드를 호출하면 항상 0 아니면 1을 리턴하는데 같은 키를 가진 원소가 여러 개 있을 수 없기 때문이다.

원소 삭제하기

map은 반복자가 가리키는 특정한 지점에 있는 원소를 삭제하거나 반복자로 지정한 범위에 있는 원소를 모두 삭제하는 기능을 제공한다. 각각에 대한 성능은 분할 상환 상수 시간과 로그 시간이다. 클라이언트 입장에서 볼 때 map에서 제공하는 두 가지 버전의 erase() 메서드는 순차 컨테이너에서 제공하는 erase() 메서드와 차이가 없다. 하지만 map은 주어진 키와 일치하는 원소를 삭제하는 버전의 erase()를 제공한다는 점에서 좀 더 뛰어나다.

노드

정렬 및 비정렬 연관 컨테이너를 흔히 노드 기반(node-based) 데이터 구조라 부른다. C++ 17부터 표준 라이브러리에서 노드(node)를 노드 핸들(node handle)의 형태로 직접 접근하는 기능이 추가됐다. 정확한 타입이 정해져 있지 않지만 컨테이너마다 그 컨테이너의 노드 핸들 타입을 가리키는 node_type이란 타입 앨리어스가 있다. 노드 핸들은 이동시킬 수만 있고, 노드에 저장된 원소를 소유하고 있다. 키와 값 모두에 대해 읽기/쓰기 권한이 있다.

extract() 메서드에 반복자 위치나 키를 지정해서 호출하면 연관 컨테이너에서 노드를 노드 핸들로 가져올 수 있다. extract()로 컨테이너에서 노드를 가져오면 그 노드는 컨테이너에서 삭제된다. 리턴된 노드 핸들만 그 원소를 소유하기 때문이다.

노드 핸들을 컨테이너에 추가할 수 있도록 insert()를 오버로딩한 메서드도 새로 추가됐다.

extract()로 노드 핸들을 가져와서 insert()로 노드 핸들을 추가하면 복제나 이동 연산을 수행하지 않고도 한쪽 연관 컨테이너에 있는 데이터를 다른 쪽 연관 컨테이너로 옮기는 효과를 볼 수 있다. 심지어 map에서 multimap으로 set에서 multiset으로도 노드를 이동시킬 수 있다.

앞서 본 예제에 이어서 키가 1인 노드를 두 번째 map으로 이동시키는 부분을 추가하면 다음과 같다.

map<int, Data> dataMap2;
auto extractedNode = dataMap.extract(1);
dataMap2.insert(std::move(extractedNode));

마지막 두 문장을 다음과 같이 하나로 합칠 수 있다.

dataMap2.insert(dataMap.extract(1));

또한 merge()를 이용하면 한쪽 연관 컨테이너에 있는 노드를 모두 다른 쪽으로 이동시킬 수 있다. 대상 컨테이너의 노드와 중복되거나 다른 이유로 이동시킬 수 없는 노드는 원본 컨테이너에 남는다. 예컨대 다음과 같다.

map<int, int> src = { {1, 11}, {2, 22} };
map<int, int> dst = { {2, 22}, {3, 33}, {4, 44}, {5, 55} };
dst.merge(src);

이렇게 merge() 연산을 실행하고 나면 src에 여전히 [2, 22]란 원소가 남아 있다. 대상 컨테이너에 [2, 22]가 있어서 이동시킬 수 없기 때문이다. 이 연산을 실행한 뒤 dst는 [1, 11], [2, 22], [3, 33], [4, 44], [5, 55]란 원소를 갖게 된다.

map 사용 예제: 은행 계좌

(생략)

multimap

multimap은 한 키에 여러 개의 값을 담을 수 있는 map이다. map과 마찬가지로 multimap도 유니폼 초기화를 지원한다. multimap의 인터페이슨느 다음과 같은 점을 제외하면 map의 인터페이스와 같다.

  • multilmap은 operator[]와 at()을 제공하지 않는다. 한 키가 여러 원소를 가리키는 상황에서 두 메서드의 의미가 맞지 않기 때문이다.
  • multimap에 원소를 추가하는 연산은 항상 성공한다. 원소 하나를 추가하는 multimap::insert() 메서드는 두 값을 pair로 묶지 않고 iterator 하나만 리턴한다.
  • map에서 제공하던 insert_or_assign()과 try_emplace() 메서드를 multimap에서는 제공하지 않는다.

Note) multimap을 이용하면 키/값 쌍을 중복해서 추가할 수 있다. 중복되지 않게 하려면 원소를 추가할 때마다 중복 여부를 검사해야 한다.

multimap을 사용할 때 까다로운 부분은 원소를 조회하는 연산이다. operator[]를 제공하지 않기 때문에 이를 사용할 수 없다. find()도 지정한 키에 해당하는 모든 원소를 참조하는 iterator를 리턴하기 때문에 (그래서 주어진 키에 대해 첫 번째 원소가 아닐 수 있기 때문에) 그리 도움 되지 않는다.

하지만 multimap은 한 키에 모든 원소를 저장할 수 있고 컨테이너에서 같은 키에 속한 원소의 범위를 가리키는 iterator를 리턴하는 메서드를 제공한다. lower_bound()와 upper_bound() 메서드는 주어진 키에 일치하는 원소 중에서 각각 첫 번째와 마지막 바로 뒤에 있는 원소를 가리키는 iterator를 리턴한다. 키에 매칭되는 원소가 없다면 lower_bound()와 upper_bound()가 리턴하는 iterator가 서로 같다.

주어진 키에 대한 원소의 양쪽 경계를 가리키는 iterator를 구하고 싶다면 lower_bound()를 호출한 뒤 upper_bound()를 호출하는 것보다 equal_range()를 호출하는 것이 좀 더 효율적이다. equal_range() 메서드는 lower_bound()와 upper_bound()가 각각 리턴한느 두 가지 iterator를 pair로 묶어서 리턴한다.

Note) lower_bound(), upper_bound(), equal_range() 메서드는 map에서도 제공한다. 하지만 map은 같은 키를 가진 원소가 여러 개 있을 수 없기 때문에 이 메서드의 활용도가 떨어진다.

multimap 사용 예제: 친구 목록(BuddyList)

(생략)

set

set은 map과 상당히 비슷하다. map과 다른 점은 키/값 쌍으로 저장하지 않고 키가 곧 값이라는 점이다. set은 키를 따로 갖지 않고 정보를 중복되지 않게 정렬해서 저장하고, 추가, 조회, 삭제 연산도 빠르게 처리하고 싶을 때 적합하다.

set에서 제공하는 인터페이스는 map과 같다. 가장 큰 차이점은 set은 operator[], insert_or_assign(), try_emplace()를 제공하지 않는다는 것이다.

set에 있는 원소의 키/값은 변경할 수 없다. set의 원소를 변경하면 순서가 바뀔 수 있기 때문이다.

set 사용 예제: 접근 권한 관리(AccessList)

(생략)

multiset

multiset과 set의 관계는 multimap과 map의 관계와 같다. multiset은 set에서 제공하는 연산을 모두 제공한다. 하지만 똑같은 원소를 중복해서 가질 수 있다.

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

표준 라이브러리는 흔히 해시 테이블이라 부르는 비정렬 연관 컨테이너도 제공하며 unordered_map, unordered_multimap, unordered_set, unordered_multiset의 네 종류가 있다. 이 컨테이너들은 원소를 정렬하지 않는다.

해시 함수

비정렬 연관 컨테이너를 해시 함수(hash function)으로 구현하기 때문에 흔히 해시 테이블이라 부른다. 해시 테이블은 버킷(bucket)이라 부르는 배열 형태로 원소를 저장한다. 버킷마다 0, 1, 2 같은 숫자 인덱스가 붙어 있다. 해시 함수를 키를 해시값(hash value)으로 변환하는데, 이 값은 다시 버킷 인덱스(bucket index)로 변환된다. 그래서 이렇게 버킷 인덱스로 표현된 키에 대응되는 값을 해당 버킷에 저장한다.

해시 함수의 결과는 중복될 수 있다. 두 개 이상의 키가 같은 버킷 인덱스를 가리키는 현상을 해시 충돌(collision)이라 부른다. 충돌은 서로 다른 키의 해시값이 같거나 서로 다른 해시값이 동일한 버킷 인덱스로 변환될 때 발생한다.

이런 충돌을 해결하기 위해 이차 함수 재해싱(quadratic re-hashing), 리니어 체이닝(linear chaining)과 같은 다양한 방법이 나왔다. 표준 라이브러리는 충돌 처리 알고리즘을 특별히 정해두지 않았지만, 최근 구현된 라이브러리는 대부분 리니어 체이닝을 적용하고 있다.

리니어 체이닝은 키에 대응되는 데이터 값을 버킷에 직접 저장하지 않고, 연결 리스트에 대한 포인터를 저장한다. 이 연결 리스트에 해당 버킷에 대한 데이터 값을 모두 담고 있다. 이를 그림으로 표현하면 아래 그림과 같다.

위 그림을 보면 충돌이 두 번 발생한다. 첫 번째 충돌은 ‘Mark G’와 ‘John D’라는 키의 해시 함수 결과가 모두 버킷 인덱스 128에 대응되는 해시값으로 나와서 발생한다. 이 버킷은 ‘Mark G’와 ‘John D’라는 키와 각각에 해당하는 데이터 값을 담은 연결 리스트에 대한 포인터값을 갖고 있다. 두 번째 충돌은 ‘Scott K’와 ‘Johan G’에 대한 해시값이 모두 버킷 인덱스 129번에 대응되기 때문에 발생한다.

또한 위 그림을 보면 키로 값을 조회(룩업 lookup) 하는 과정과 이때 발생하는 복잡도도 알 수 있다. 조회 연산은 먼저 해시값을 계산하는 해시 함수를 한 번 호출해서 해시값을 구한뒤 이를 버킷 인덱스로 변환한다. 버킷 인덱스를 구했다면 한 개 이상의 등호(equality) 연산을 이용해서 연결 리스트에서 적합한 키를 찾는다. 그래서 기존 map에 비해 해시 테이블에 대한 조회 연산이 굉장히 빠르다. 하지만 충돌 발생 횟수에 따라 성능이 달라질 수 있다.

어떤 해시 함수를 사용하느냐도 중요하다. 충돌이 전혀 없는 해시 함수를 ‘완전 해시(perfect hash)’라 부른다. 완전 해시의 조회 시간은 상수다. 일반 해시의 조회 시간은 원소 수에 관계 없이 평균적으로 1에 가깝다. 충돌 횟수가 많아질수록 조회 시간은 늘어나서 성능이 떨어진다. 기본 해시 테이블의 크기를 늘리면 충돌을 줄일 수 있지만 캐시 크기도 함께 고려해서 결정해야 한다.

C++ 표준에서는 포인터 타입이나 bool, char, int, float, double 등과 같은 기본 타입에 대해 해시 함수를 제공한다. 또한 error_code, error_condition, optional, variant, bitset, unique_ptr, shared_ptr, type_index, string, string_view, vector<bool>, thread::id에 대해서도 해시 함수를 제공한다.

원하는 키 타입을 제공하는 해시 함수가 표준에 없다면 직접 구현해야 한다. 완전 해시를 만들기란 쉽지 않다. 키의 개수와 종류가 정해져 있더라도 그렇다. 수학적으로 깊이 있게 분석해야 하기 때문이다. 그런데 완전 해시가 아니더라도 충분한 성능을 내는 해시를 만드는 것도 쉽지 않다. 

다음 코드는 해시 함수를 직접 만드는 방법을 보여준다. 여기서는 요청된 사항을 표준 해시 함수 중 하나로 전달하기만 한다. 여기서 정의한 IntWrapper 클래스는 정숫값 하나를 감싸기만 한다. 비정렬 연관 컨테이너에서는 키에 대한 operator== 연산을 반드시 제공해야 한다.

class IntWrapper
{
public:
IntWrapper(int i) : mWrappedInt(i) { }
int getValue() const { return mWrappedInt; }

private:
int mWrappedInt;
};

bool operator==(const IntWrapper& lhs, const IntWrapper& rhs)
{
return lhs.getValue() == rhs.getValue();
}

IntWrapper에 대한 해시 함수는 std::hash 템플릿을 IntWrapper에 대해 특수화는 방식으로 구현한다. std::hash 템플릿은 <functional> 헤더 파일에 정의돼 있다. 이렇게 특수화 하려면 주어진 IntWrapper 인스턴스에 대한 해시를 계산해서 리턴하는 함수 호출 연산자를 구현 해야 한다. 예제에서는 정수 타입에 대한 표준 해시 함수로 전달하는 방식으로 처리한다.

namespace std
{
template<> struct hash<IntWrapper>
{
using argument_type = IntWrapper;
using result_type = size_t;

result_type operator()(const argument_type& f) const
{
return std::hash<int>()(f.getValue());
}
}
}

일반적으로 std 네임스페이스에 새로운 것을 추가하면 안 된다. 하지만 std 클래스 템플릿을 특수화 할 때는 예외적으로 이를 허용한다. hash 클래스 템플릿을 특수화하려면 두 가지 타입을 정의해야 한다. 함수 호출 연산자는 단 한 줄로 구현했는데, 정수에 대한 표준 해시 함수인 std::hash<int>()의 인스턴스를 생성한 뒤 이 인스턴스의 함수 호출 연산자에 f.getValue()를 인수로 지정해서 호출한다. 

여기서는 IntWrapper에 정수에 대한 데이터 멤버가 하나만 있기 때문에 이런 식으로 요청을 전달할 수 있다. 하지만 클래스에 데이터 멤버가 여러 개면 해시값을 계산할 때 여기 나온 데이터 멤버를 모두 반영해야 한다.

unordered_map

(설명 생략)

map과 마찬가지로 unordered_map도 키가 중복될 수 없다.

unordered_map은 한 버킷에 담긴 원소에 대해 루프를 돌도록 local_iterator와 const_local_iterator도 제공한다. 이 반복자는 다른 버킷에 대해서는 적용할 수 없다.

bucket(key) 메서드는 인수로 지정한 키의 버킷 인덱스를 리턴한다. begin(n))은 인덱스가 n인 버킷에 있는 첫 번째 원소를 가리키는 local_iterator를 리턴하고, end(n)은 인덱스가 n인 버킷에 있는 마지막 바로 다음번 원소를 가리키는 local_iterator를 리턴한다.

unordered_map 사용 예제: 전화번호부(phoneBook)

(예시 생략)

unordered_multimap

unordered_multimap은 같은 키로 여러 우너소를 대응시킬 수 있는 unordered_map이다. 다음과 같은 차이를 제외하면 인터페이스는 똑같다.

  • unordered_multimap은 operator와 at()을 제공하지 않는다. 한 키가 여러 원소를 가리키는 상황에서 두 메서드의 의미가 맞지 않기 때문이다.
  • unordered_multimap에 대한 추가 연산은 항상 성공한다. 그래서 원소 하나를 추가하는 unordered_multimap::insert() 메서드는 두 값을 pair로 묶지 않고 iterator 하나만 리턴한다.
  • unordered_map에서 제공하던 insert_or_assign()과 try_emplace() 메서드를 unordered_multimap에서는 제공하지 않는다.

unordered_multimap은 원소를 operator[]로 조회할 수 없다. 이 연산을 제공하지 않기 때문이다. find()로 조회해도 되지만 지정한 키에 대응되는 원소 중에서 첫 번째가 아닌 다른 원소를 가리키는 반복자를 리턴할 수 있다. 따라서 주어진 키에 대응되는 첫 번째 원소와 마지막 바로 다음번 원소를 가리키는 원소를 가리키는 반복자를 pair로 묶어서 리턴하는 equal_range() 메서드로 조회하는 것이 좋다. equal_range() 메서드의 사용법은 multimap과 같다.

unordered_set과 unordered_multiset

각각 키를 정렬하지 않고 해시 함수를 사용한다는 점만 빼면 set, multiset과 상당히 유사하다. unordered_set과 unordered_map의 차이점은 앞서 설명한 set과 map의 차이점과 같다.

기타 컨테이너

C++ 은 표준 라이브러리와 함께 사용할 수 있는 컨테이너를 다양하게 제공한다. 대표적인 예로 표준 C 스타일 배열, string, 스트림, bitset 등이 있다.

표준 C 스타일 배열

앞서 일반 포인터도 일종의 반복자라고 설명한 적 있는데, 반복자와 관련된 연산을 제공하기 때문이다. 이 점을 가볍게 볼 수 없는 이유는 원소에 대한 포인터를 반복자로 사용하면 표준 C 스타일 배열을 표준 라이브러리 컨테이너처럼 사용할 수 있기 때문이다.

표준 C 스타일 배열은 당연히 size(), empty(), insert(), erase()와 같은 메서드를 제공하지 않기 때문에 정식 표준 라이브러리 컨테이너는 아니다. 하지만 포인터를 이용한 반복자를 제공하기 때문에 18장에서 소개하는 표준 라이브러리의 알고리즘과 이 장에서 소개하는 몇 가지 메서드에 적용할 수 있다.

예컨대 모든 컨테이너의 반복자 범위를 인수로 받는 vector의 insert() 메서드로 표준 C 스타일 배열에 담긴 원소를 모두 vector로 복제할 수 있다. 이 버전의 insert() 메서드의 프로토타입은 다음과 같다.

template <class InputIterator> iterator insert(const_iterator position, InputIterator first, InputIterator last);

원본이 int 타입에 대한 표준 C 스타일 배열일 때 InputIterator를 템플릿화한 타입은 int*가 된다. 예컨대 다음과 같다.

const size_t count = 10;
int arr[count]; // 표준 C 스타일 배열

// 배열의 원소를 모두 인덱스 값으로 초기화한다.
for (int i = 0; i < count; i++)
{
arr[i] = i;
}

// 배열에 담긴 내용을 vector 뒤에 추가한다.
vector<int> vec;
vec.insert(end(vec), arr, arr + count);

// vector의 내용을 화면에 출력한다.
for (const auto& i : vec)
{
cout << i << " ";
}

여기서 배열의 첫 번째 원소를 가리키는 반복자는 첫 번째 원소(arr)의 주소다. 그러므로 배열의 이름은 첫 번째 원소에 대한 주소처럼 쓸 수 있다. 마지막 원소를 가리키는 반복자는 반드시 마지막 바로 다음 번째 원소를 가리켜야 한다. 그러므로 첫 번째 원소의 주소에 count를 더한 arr+count의 주소가 된다.

std::begin()이나 std::cbegin()을 이용하면 포인터로 접근하지 않는 정적 할당 C 스타일 배열의 첫 번째 원소에 대한 반복자를 쉽게 구할 수 있다. 또한 std::end()나 std::cend()를 사용하면 이 배열의 마지막 바로 다음 번째 원소에 대한 반복자를 얻을 수 있다. 예컨대 앞서 나온 코드에서 insert()를 호출하는 부분을 다음과 같이 표현할 수 있다.

vec.insert(end(vec), cbegin(arr), cend(arr));

Caution) std::begin()과 std::end() 같은 함수는 포인터로 접근하지 않는 정적 할당 C 스타일 배열에 대해서만 사용할 수 있다. 포인터를 사용하거나 동적으로 할당된 C 스타일 배열에는 적용할 수 없다.

string

string을 문자에 대한 순차 컨테이너로 볼 수 있다. 실제로 C++의 string은 정식 순차 컨테이너다. 반복자를 리턴하는 begin(), end() 메서드와 insert(), push_back, erase(), size(), empty()를 비롯한 순차 컨테이너에서 기본적으로 제공하는 메서드를 모두 갖추고 있다. reserve()와 capacity() 같은 메서드도 제공해서 vector와도 상당히 비슷하다.

(예시 코드 생략)

string은 표준 라이브러리의 순차 컨테이너에서 제공하는 메서드 뿐만 아니라 여러 유틸리티 메서드와 friend 함수도 제공한다. string의 인터페이스는 좀 지저분한데, 6장에서 설명한 잘못된 디자인의 대표적 예다.

스트림

전통적인 분류에 따르면 입력과 출력 스트림은 컨테이너가 아니다. 원소를 저장하지 않기 때문이다. 하지만 원소를 순차적으로 다룬다는 점에서 표준 라이브러리의 컨테이너와 공통점이 많다.

C++ 스트림은 표준 라이브러리 관련 메서드를 하나도 제공하지 않지만 표준 라이브러리에서 istream_iterator와 ostream_iterator라는 특수 반복자를 제공한다. 그래서 입력과 출력 스트림에 대해 반복할 수 있다.

bitset

bitset은 고정된 크기의 비트열을 추상화한 것이다. 한 비트는 0과 1이라는 두 가지 값만 가질 수 있으며, 흔히 참/거짓, 켜기/끄기와 같은 속성을 표현한다. bitset은 셋(set)과 언셋(unset)이란 용어를 사용한다. 값을 반전(토글(toggle)또는 플립(flip)) 시킬 수도 있다.

bitset은 정식 표준라이브러리 컨테이너가 아니다. 크기가 고정됐고, 원소 타입에 대해 템플릿화 할 수 없고, 반복자를 제공하지 않기 때문이다. 하지만 컨테이너와 함께 사용하는 일이 많을 정도로 유용하기 때문에 살펴보겠다.

bitset의 기본 기능

bitset은 저장할 비트 수에 대해 템플릿화할 수 있다. 디폴트 생성자는 bitset의 모든 필드를 0으로 초기화한다. 0과 1이란 문자로 구성된 string을 bitset으로 만드는 생성자도 있다.

각각의 비트값은 set(), unset(), flip() 메서드로 설정할 수 있고, bitset에 대해 오버로딩된 operator[] 연산으로 각 필드값을 조회하거나 설정할 수도 있다. 참고로 non-const 객체에 대해 operator[] 연산을 수행하면 flip()을 호출하거나 operator~ 연산으로 부울값을 할당할 수 있는 프록시 객체를 리턴한다. 또한 test() 메서드로 개별 필드에 접근할 수도 있다.

그리고 추가 및 추출 연산으로 bitset을 스트림으로 처리할 수도 있다. bitset을 스트림으로 처리하면 0과 1이란 문자로 구성된 string으로 표현된다.

bitset<10> myBitset;

myBitSet.set(3);
myBitSet.set(6);
myBitSet[8] = true;
myBitSet[9] = myBitSet[3];

if (myBitSet.test(3))
{
cout << "Bit 3 is Set!" << endl;
}

cout << myBitSet << endl;

// 코드 실행 결과
// Bit 3 is Set!
// 1101001000

string의 출력 결과를 보면 가장 왼쪽에 나온 문자가 최상위 비트다. 우리가 흔히 이진수를 표현할 때 가장 낮은 자리 비트인 20 = 1을 가장 오른쪽에 표현하는 방식과 일치한다.

비트 연산

bitset은 기본적인 비트 조작 메서드뿐만 아니라 &, |, ^, ~, <<, >>, &=, |=, ^=, <<=, >>=와 같은 비트 연산자도 제공한다. 이 연산은 실제 비트열에 적용할 때와 똑같이 작용한다. 예컨대 다음과 같다.

auto str1 = "0011001100";
auto str2 = "0000111100";
bitset<10> bitsOne(str1);
bitset<10> bitsTwo(str2);

auto bitTHree = bitsOne & bitsTwo;
cout << bitsThree << endl;

bitsThree <<= 4;
cout << bitsThree << endl;

// 실행 결과
// 0000001100
// 0011000000

bitset 사용 예제: 케이블 채널 관리(CableCompany)

(생략)

[ssba]

The author

지성을 추구하는 사람/ suyeongpark@abyne.com

댓글 남기기

이 사이트는 스팸을 줄이는 아키스밋을 사용합니다. 댓글이 어떻게 처리되는지 알아보십시오.