Chocobubble

Game programmer

17 minute read

‘전문가를 위한 C++ - Marc Gregoire 지음, 남기혁 옮김’ 책을 참고하여 작성한 포스트입니다.

컨테이너 개요

  • 표준 라이브러리에서 제공하는 컨테이너는 클래스 템플릿으로 구현되어 있으므로 기본 조건만 만족한다면 거의 모든 타입에 대해 인스턴스화해 사용 가능하다.
  • 컨테이너의 종류
    • 순차 컨테이너
      • vector(동적 배열)
      • deque
      • list
      • forward_list
      • array
    • 연관 컨테이너
      • map
      • multimap
      • set
      • multiset
    • 비정렬 연관 컨테이너(해시 테이블)
      • unordered_map
      • unordered_multimap
      • unordered_set
      • unordered_multiset
    • 컨테이너 어댑터
      • queue
      • priority_queue
      • stack

원소에 대한 요구사항

  • 표준라이브러리 컨테이너는 원소를 값으로 처리한다. (값 의미론, value semantics)
    • 원소의 복제본을 저장하고 대입 연산자로 대입하고 소멸자로 원소를 삭제한다.
    • 그래서 복제할 수 있게 만들어 주어야 하고,
    • 컨테이너에서 원소를 요청하면 저장된 복제본에 대한 레퍼런스를 반환한다.
  • 원소를 레퍼런스로 처리하고 싶다면(레퍼런스 의미론, reference semantics)
    • 원소를 그대로 넣지 않고 원소에 대한 포인터를 저장한다.
    • 포인터가 복제되지만 결국엔 같은 원소를 가리킨다.
  • 이동 전용 타입과 복제 불가능한 타입도 컨테이너에 저장할 수 있지만 이들의 연산 중 일부는 컴파일 에러를 발생시킬 수 있다.
  • 컨테이너에 포인터를 저장하려면 unique_ptr, shared_ptr 을 사용한다.
  • 할당자(allocator)
    • 컨테이너는 할당자를 이용해 원소에 대한 메로리를 할당하거나 해제한다.
    • 타입 매개변수는 디폴트값이 정해져 있어 거의 대부분 그냥 써도 된다.
    • template <class T, class Allocator = std::allocator<T>> class vector;
  • 비교자(comparator)
    • 템플릿 타입 매개변수로 받아 원소를 정렬하는데 사용된다.
    • 이 역시 디폴트 값이 정해져 있다.
    • ```template <class key, class T, class Compare = std::less, ...>
  • 표준라이브러리 컨테이너는 원소를 복제하거나 이동시킬 일이 많으므로 컨테이너에 저장하는 객체 타입이 이동 의미론이 지원돼야 좋다.



순차 컨테이너(sequential container)

vector

  • 원소 하나에 한 칸씩, 연속된 메모리에 저장된다.
  • 인덱스로 접근 가능하고, 원소를 끝이나 원하는 지점에 추가 가능하다.
  • 기본적으로 추가 삭제는 선형 시간이 걸리나, 끝에서 처리할 때는 분할 상환 상수 시간(amortized constant time)이 걸린다.

vector 개요

  • <vector>에 클래스 템플릿으로 정의되어 있다.
  • 저장할 원소의 타입과 할당자(allocator) 타입을 매개변수로 받는다.
template <class T, class Allocator = std::allocator<T>> class vector;
  • 할당자를 통해 메모리 할당 방식을 커스터마이징 할 수 있다.(25장)
  • c++20 부터 std::string 처럼 constexpr 이다.
    • 즉, 컴파일 시간에 연산 수행 가능하고, constexpr 함수와 클래스 구현 가능하다.

고정 크기 vector

  • operator[] 연산자가 오버로딩 되어있어 원소에 쉽게 가능하다.
  • 기본 배열과 마찬가지로 경계 검사를 하지 않는다.
  • at() 메서드는 경계 검사(bound checking)를 수행해서, 인덱스가 범위를 벗어나면 out_of_range 익셉션을 던진다.
  • front() 와 back() 은 각각 첫, 마지막 원소에 대한 레퍼런스를 리턴한다.
    • 둘 다 공백 컨테이너에 대해 호출할 때의 동작은 명확히 정의되어 있지 않다.
  • vector 내의 원소에 접근하는 연산의 복잡도는 모두 상수 시간이다.
  • operator[]는 원소에 대한 레퍼런스를 반환하기 때문에 이 값을 대입문의 좌측에서 사용 가능하다.
    • const vector의 경우에는 const 원소에 대한 레퍼런스를 반환하므로 대입문 좌측에서 사용 불가

vector 의 세부 기능

생성자와 초기자

  • 디폴트 생성자는 빈 vector를 생성하고, 모두 0으로 초기화된다.
  • 사용자 정의 타입 원소에 대한 vector 생성도 가능하다.
  • 초기자 리스트도 적용 가능하다.
vector<int> IntVector( {1, 2, 3} );
// 균일 초기화
vector<int> IntVector2 { 1, 2, 3 };
// CTAD(클래스 템플릿 인수 추론)
vector IntVector3 { 1, 2, 3 };
// 프리 스토어 할당
auto VectorPtr = make_unique<vector<Element>> (10);

복제와 대입

  • vector는 원소 객체의 복제본을 저장한다.
  • vector의 소멸자는 각 원소 객체의 소멸자를 호출한다.
  • 복제 생성자와 대입 연산자는 깊은 복사를 수행한다.
  • 따라서 함수나 메서드에 vector 전달할 때 값보다는 비 const 레퍼런스나 const 레퍼런스로 전달하는 것이 좋다.
  • assign()
    • 현재 저장된 원소 모두 삭제하고 원하는 수만큼 추가
    • 초기자 리스트 사용 가능
  • swap()
    • 두 vector의 내용을 상수 시간에 맞바꿈
vector<int> IntVector(10);
IntVector.assign(5, 100);
IntVector.assign({1, 2, 3});
vector<int> IntVector2(10);
IntVector.swap(IntVector2);

vector 비교

  • 두 vector가 같기 위해서는 원소 개수 및 각각의 원소도 같아야 함.
  • 디폴트는 사전순으로 비교?
  • operator== 와 operator!= 로 비교하려면 operator== 가 오버로딩 되어 있어야 하고,
  • 나머지 네 비교자를 사용하려면 operator< 오버로딩해야 한다.

vector 반복자

  • begin(vector), end(vector) 는 각각 첫 원소, 마지막 원소 바로 다음 지점을 참조하는 반복자를 리턴
for(vector<int>::iterator iter = begin(IntVector);
	iter != end(IntVector); ++iter) 
{
	// iter 가 가리키는 원소 수정
	*iter += 1;
}
  • iterator 타입이 복잡하다면 auto 쓰면 됨.
  • (c)begin(), (c)end(), (c)rbegin(), (c)rend() 는 각각 (const) 반복자를 리턴한다.
  • const iterator 는 참조하는 원소를 수정할 수 없다.
    • vector<type>::const_iterator iter ....
  • auto 로 반복자를 사용하는 경우, const iterator로 사용하고 싶다면, cbegin(), cend()를 사용해주면 된다.
for(auto iter = cbegin(IntVector); iter != cend(IntVector); ...)
  • 반복자의 안전성은 포인터 수준이므로 주의해서 사용해야 한다.
  • 반복자는 랜덤 액세스를 지원한다.
auto iter = begin(IntVector);
iter += 5;
*iter = 4;
  • 반복자의 필요성
    • 컨테이너의 원하는 지점에 원소 추가 삭제가 간편하다.
    • 표준 라이브러리 알고리즘 사용하기 좋다(20장)
    • list, map, set의 경우 반복자 사용하는 것이 하나씩 조회해보는 것보다 훨씬 빠르다.

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

vector에 레퍼런스 저장하기

  • std::reference_wrapper로 감싸서 저장할 수 있다.
int Value1 = 10;
int Value2 = 20;
vector<reference_wrapper<int>> RefVector = ref(Value1);
RefVector.push_back(ref(Value2));

원소의 추가와 삭제

  • push_back은 추가, pop_back()은 삭제, 둘 다 리턴하는 값이 없다.
  • insert를 통해 원하는 지점에 원소 추가가 가능하고, 추가된 지점에서 뒤에있는 원소들은 모두 뒤로 한칸씩 밀리며, 새로운 공간이 확보된다.
  • insert의 다섯 가지 오버로딩
    • 원소 하나를 추가
    • 원소 하나에 대한 복제본 n개 추가
    • 반복자의 범위로 지정된 원소들 추가 (끝 반복자가 참조하는 원소는 제외)
    • 지정한 원소를 이동 의미론에 따라 추가
    • 원소 리스트를 initializer_list로 추가
  • push_back과 insert 둘 다 좌측값이나 우측값을 매개변수로 받는 버전도 있다.
    • 좌측값 버전은 지정한 원소의 복제본을 저장하고, 우측값 버전은 이동 의미론을 적용해 소유권을 vector로 넘긴다.
  • erase()를 이용해 원소를 삭제한다.
    • 반복자 하나를 받아 원소 하나 삭제
    • 범위를 지정하는 반복자 둘을 받아 범위 내 원소 삭제
  • clear()는 원소 모두 삭제
vector<int> Vector1 {1, 2, 4};
vector<int> Vector2;

// 빠진 위치에 3 삽입
Vector1.insert(cbegin(Vector1) + 2, 3);
for(int i=5; i<=10; ++i)
{
	Vector2.push_back(i);
}
// vector1 뒤에 Vector2 삽입
Vector1.insert(cend(Vector1), cbegin(Vector2), cend(Vector2));
Vector1.erase(cbegin(Vector1) + 1, cbegin(Vector1) + 5);
Vector2.clear();
// 100에 대한 복제본 10개를 추가
Vector2.insert(cbegin(Vector2), 10, 100);
Vector2.pop_back();
  • c++20에서는 std::erase(), std::erase_if() 라는 비 멤버 함수를 이용 가능하다.
의미 이동론
  • 표준 라이브러리에서 제공하는 컨테이너는 모두 이동 의미론(move semantics)을 적용하여 특ㄱ정한 상황에서 성능을 높일 수 있다.
vector<string> vec;
string MyElement(5, 'a') // "aaaaa"
vec.push_back(MyElement);
  • MyElement는 임시 객체가 아니기 때문에 MyElement의 복제본을 만들어 vec에 추가하게 된다.
  • vector는 push_back(T&&)도 지원하므로, vec.push_back(move(MyElement))를 하면 복제 연산이 일어나지 않는다.
  • 물론 위처럼 호출하고나면 MyElement는 상태를 다시 명확히 설정해주기 전까지 사용하면 안되겠죠
  • vec.push_back(string(5, ‘a’)) 도 이동 의미론 버전이 호출된다.
임플레이스 연산(emplace operation)
  • emplace란 특정한 지점에 설치 한다는 뜻이다.
  • vector에서의 emplace_back()은 복제나 이동 작업을 수행하지 않고, 컨테이너에 공간을 마련하여 객체를 그 자리에 바로 생성한다.
  • emplace 메서드는 인수를 가변 인수 템플릿(variadic template)으로 받기 때문에 인수의 개수를 다양하게 지정 가능하다.(26장)
  • push_back과 성능 차이는 컴파일러의 구현 방식에 따라 달라 맘에 드는 방식으로 하면 됨
  • c++17부터 emplace_back은 추가된 원소에 대한 레퍼런스를 리턴함. 그전은 void 리턴했음
  • emplace()는 특정 지점에 객체를 바로 생성한 뒤 그 원소를 가리키는 바복자를 리턴함
알고리즘 복잡도와 반복자 무효화
  • vector 내부에서 공간 재할당이 발생하면 추가나 삭제 대상 원소를 가리키는 반복자뿐만 아니라 다른 지점에 대한 기존 반복자들도 모두 무효화된다.

vector의 메모리 할당 방식

  • vector는 원소를 연속된 메모리 공간에 저장한다.
  • 할당된 메모리 공간 바로 뒤에 새 메모리 요청이 불가능해, 원소를 추가할 공간이 모자라면 더 큰 공간을 새로 할당받고 기존 원소를 모두 새 공간으로 이동하거나 복제해야 한다.
  • 이동이나 복제의 시간 복잡도는 선형 시간이 걸리므로 미리 공간을 적절히 할당해 재할당을 방지하면 좋다.
  • 그리고 재할당이 일어나면 반복자도 모두 무효가 되어버린다.
크기와 용량
  • vector에 size()는 현재 담긴 원소의 개수, capacity()는 재할당 없이 담을 수 있는 원소의 개수를 리턴한다
  • 글로벌 함수로 std::size(), std::empty()가 있는데, 모든 컨테이너에 대해 호출 가능하다.
  • c++20 부터 글로벌 비 멤버 헬퍼 함수인 std::ssize()가 추가 되었다. 크기를 부호 있는 정수 타입으로 리턴한다.
vector vec { 1, 2, 3 };
cout<< size(vec) << " " << empty(vec) << endl;
예비 용량
  • vector의 공간을 미리 확보하기 위해 reserve() 호출하는 방법이 있다.
  • vector의 생성자를 이용하는 방법, resize(), assign() 메서드도 있다.
메모리 회수
  • 벡터의 메모리는 전체가 해제되기 전까지 해제되지 않는다.
  • 벡터의 메모리를 회수하는 방법 중 하나는 벡터의 메모리 전체를 빈 것으로 교체하는 것이다.
vector<int> values;
vector<int>().swap(values);
데이터 직접 접근하기
  • data() 메서드를 통해 vector에서 데이터가 있는 메모리 블록에 대한 포인터를 구할 수 있다.
  • 비 멤버 글로벌 함수인 std::data()도 있다. array, vector, string, 정적 할당 스타일 c 스타일 배열, initializer_list에 대해 호출 가능하다.
vector vec { 1, 2, 3 };
int* data1 { vec.data() };
int* data2 { data(vec)};

// 예전 방법. 빈 vector에 대해 안전하지 않다.
int* data3 { &vec[0] };

이동 의미론

  • 모든 표준 라이브러리 컨테이너는 이동 생성자와 이동 대입 연산자를 제공해 이동 의미론을 지원한다.
  • 이동 의미론을 적용하면 표준 라이브러리 컨테이너를 함수에서 값으로 리턴해도 성능 오버헤드를 최소화 할 수 있다.
vector<int> CreateVector(size_t size)
{
	vector<int> vec(size, 1);
	return vec;
}

vector<int> MyVector;
MyVector = CreateVector(5);
  • 이동 의미론이 지원되지 않았다면 위에서 CreateVector()의 결과가 MyVector에 대입될 때 복제 대입 연산자가 호출되었을 것이다. 하지만 표준 라이브러리 컨테이너는 이동 의미론을 지원하므로 복제 연산이 발생하지 않고, 이동 대입 연산자를 호출하게 된다.
  • 이동 의미론이 제대로 작동하려면 컨테이너에 저장된 타입에 대한 이동 생성자와 이동 대입연산자를 반드시 noexcept로 지정해 주어야 한다.
  • 메모리 재할당이 일어나는 도중에 예외를 던지게 되면 문제가 될 것이다.
  • noexcept가 지정되지 않았다면 익셉션 안전성을 보장하기 위해 복제 메서드를 대신 사용한다.

vector 사용 예제 (라운드 로빈) (나중에 추가)

vector 특수화

  • C++ 기본 타입에는 비트 하나만 표현하는 것이 없다.
  • 표준은 여러 부울 타입 값을 묶어 (packing) 처리하도록 하고 있다.
  • 컴파일러마다 구현방법이 다르다.
  • bitset 컨테이너를 활용하는 것이 좋다.
  • 나중에 내용 추가

deque (double-ended queue)

  • <deque>에 정의
  • vector와의 차이점은 다음과 같다
    • 원소를 메모리에 연속으로 저장하지 않음
    • 양쪽끝에 원소 추가 삭제를 상수 시간에 처리함. 재할당 없음
    • push_front, pop_front(), emplace_front()를 제공함
    • 앞뒤에 원소 추가해도 반복자 무효화되지 않음
    • 메모리 관리 기능 메서드가 없음

list

  • 이중 연결 리스트를 구현한 클래스 템플릿이다.
  • <list>에 정의
  • 리스트의 모든 지점에 원소 추가 삭제가 상수 시간이지만 원소 조회 시간은 선형 시간에 처리한다.
  • 랜덤 액세스 연산을 제공하지 않아 반복자로만 개별 원소에 접근 가능하다.

원소 접근 연산

  • 원소 접근 메서드는 front(), back() 뿐이다.
  • 랜덤 액세스는 지원하지 않는다.
  • begin(), end(), cbegin(), cend(), rbegin(), rend(), crbegin(), crend() 지원한다.

반복자

  • 양방향으로 작동한다.
  • 반복자에 대해 산술연산은 불가능하다.

원소 추가와 삭제

  • clear()를 제외한 모든 메서드는 정확한 위치를 지정할 수 있다면 상수 시간에 처리 가능하다.
  • 즉, 데이터 추가나 삭제가 빈번하지만 원소를 인덱스로 빠르게 조회할 필요가 없는 애플리케이션에 적합하다.
  • 그래도 vector가 훨씬 빠르다.

list의 크기 연산

  • 내부 메모리 관련 메서드가 없다.
  • size(), empty(), resize()는 제공한다. reserve() 등은 x

list의 특수 연산

splice()

  • 한 리스트를 통째로 다른 리스트에 이어 붙이기(splice) 할 수 있다.
  • 상수 시간에 처리된다.

    list에 특화시킨 알고리즘

  • remove(), remove_if()
    • 특정한 조건을 만족하는 원소를 리스트에서 제거한다
  • unique()
    • 같은 원소가 연달아 나온 부분을 제거한다.
    • operator== 나 binary predicate(인수 두개를 받아 bool 값을 리턴하는 함수 객체)를 활용한다.
  • merge()
    • 두 list를 합친다.
    • operator<나 사용자가 지정한 비교 연산자로 정렬된 상태여야 한다.
  • sort()
    • stable sort
  • reverse()
    • 순서를 반대로 바꾼다.

forward_list

  • 단방향 연결 리스트이다.
  • <forward_list> 에 정의
  • 역방향으로 반복자가 이동할 수 없다.
  • before_begin() 메서드가 리스트의 시작 원소의 바로 전에 있는 가상의 원소를 가리킨다.
  • 이 반복자를 하나 증가시키면 begin()이 리턴한 반복자와 같아진다.
  • 시작이 열린 범위로 만들어 주는 역할을 한다.
  • 표준은 forward_list는 반드시 공간을 최소화 해야 하므로,
  • size() 메서드가 없다.(리스트 크기 저장하는 공간도 절약하려고)

array

  • <array>에 정의
  • 크기가 고정된 점을 제외하면 vector와 같다.
  • 고정시킨 이유는 원소를 스택에 할당하기 위해서다. vector 같은 경우는 항상 프리스토어에 저장됨
  • 생성시 초기화하지 않으면 원소들이 초기화되지 않은 상태로 남아 있다. 즉, 쓰레깃값이 들어 있음
  • vector나 list 같은 컨테이너는 항상 초기화됨.
  • 크기가 고정되어 있어 push_back 등은 지원하지 않음
  • swap 성능이 선형시간임. vector는 상수 시간
  • array 선언할 때는 매개변수 하나는 원소의 타입, 다른 하나는 원소의 개수를 지정해 주어야 한다.
  • std::get() 함수 템플릿을 이용해 array의 n번 인덱스에 있는 원소를 가져올 수 있다. 이때 인덱스는 상수 표현식으로 지정해야 한다. 컴파일 시간에 검사한다.
  • c++20 부터 std::to_array() 비 멤버 함수를 사용해 c 스타일 배열을 std::array로 변환하고, 원소에 대해 복제 초기화를 적용한다. 1차원 배열에만 적용 가능하다.

span(c++20)

  • span을 이용해 vector, c 스타일 배열, std::array 등을 다루는 함수 하나를 만들 수 있다.
  • string_view와 마찬가지로 span도 복제를 효율적으로 처리한다.
  • 실제로 첫 번째 원소에 대한 포인터와 원소 개수만 담고 있다.
  • 데이터를 전혀 복사하지 않고 그래서 값 전달 방식을 사용한다.
  • span은 string_view와 달리 원소 쓰기도 가능하므로 원소 변경되는 것이 싫다면 span 등으로 해주어야 한다.
  • 나중에 내용 추가



컨테이너 어댑터

  • container adaptor에 queue, priority_queue, stack 등이 있다.
  • 순차 컨테이너를 감싼 래퍼이므로 내부 컨테이너를 교체하더라도 어댑터를 사용하는 코드에 아무런 영향을 주지 않는다.

queue

  • <queue> 에 정의
  • FIFO 방식
template <class T, class Container = deque<T>> class queue;
  • deque이 디폴트이다. list를 써도 됨

queue 연산

  • push, emplace
    • 큐의 끝(tail)에 원소 추가
  • pop
    • 큐의 맨 앞(head)에서 원소 제거
  • front, back
    • 큐의 앞, 뒤 원소 제거하지 않고 레퍼런스 반환
    • 다른 메서드처럼 const 객체에 대해 호출하면 const 레퍼런스를 리턴하고, 비 const 객체에 대해 호출하면 읽기/쓰기가 가능하고, 비 const 레퍼런스를 리턴한다.
  • size, empty, swap

queue 사용 예제 : 네트워크 패킷 버퍼 (나중에 추가)

priority_queue(우선순위 큐)

  • 원소를 정렬된 상태로 저장하는 큐
  • <queue>에 정의
template <class T, class Container = vector<T>m class Compare = less<T>>;
  • 랜덤 액세스를 지원하기 때문에 deque을 사용해도 되지만, list는 안된다.
  • 디폴트는 operator<에 의해 작은 쪽이 낮은 우선순위를 갖는다.

priority_queue 연산

  • push, emplace
    • 원소 추가
  • pop
    • 원소 제거
  • top
    • 맨 앞 원소에 대한 const 레퍼런스 리턴
    • 원소를 수정하면 순서가 바뀔수 있어서 비 const 객체도 const 레퍼런스를 리턴한다.
  • swap, size, empty
  • 비교 연산자는 x

priority_queue 사용 예제: 에러 상관관계 첫 번째 버전(나중에 추가)

stack

  • queue와 거의 같다.
  • LIFO
  • stack 에 정의
  • vector, list, deque 가능
template <class T, class Container = deque<T>> class stack;

stack 연산

  • push, emplace
    • 최상단(top)에 원소 추가
  • pop
    • 최상단 원소 제거
  • top
  • empty, size, swap



정렬 연관 컨테이너(ordered associative container)

  • 순차 컨테이너와 달리 원소를 한 줄로 저장하지 않고 키와 값의 쌍으로 정렬된 상태로 저장한다.
  • map, set, multiset, multimap

pair 유틸리티 클래스

  • <utility>에 정의
  • 두 값을 그룹으로 묶는 클래스 템플릿. 서로 타입이 달라도 됨.
  • first, second로 각 데이터 멤버 접근
  • 모든 종류의 비교 연산자로 두 멤버 비교 가능
  • c++17부터 CTAD로 템플릿 타입 인수 생략 가능. make_pair도 안써도 됨
pair<int, double> pair1 = make_pair(5, 1.1);
auto pair2 = make_pair(5, 1.2);
pair pair3 = {5, 1.1}; // CTAD

map

  • <map>에 정의
  • 단일 값 대신 키와 값의 쌍으로 저장.
  • 추가, 조회, 삭제 모두 키를 기준으로 수행. 성능이 모두 로그 시간
  • 키 값을 기준으로 정렬된 상태 유지.
  • 레드-블랙 트리와 같은 균형 트리 형태로 구현.
  • operator<나 사용자가 정의한 비교자를 적용한 순서대로 정렬

map 생성

  • 매개변수로 1. 키타입, 2. 값 타입, 3. 비교 타입, 4. 할당자 타입 을 받는다.
  • map은 내부적으로 pair 인스턴스로 저장함

원소 추가하기

  • 정렬 연관 컨테이너는 위치를 지정할 필요가 없다.
  • 내부적으로 알아서 결정
  • 반복자를 받는 insert 메서드가 있긴 하지만 여기서 지정하는 위치는 ‘힌트’일 뿐 반드시 그 위치에 추가한다는 보장은 없음
  • 키가 중복되면 안된다.
  • 중복된 값을 넣고 싶다면 배열 등 활용하거나 multimap

insert()

  • 키가 이미 존재하는지 검사할 수 있는 장점이 있음
  • 키/값을 pair 객체나 initializer_list로 지정해야 함
  • iterator와 bool에 대한 pair를 리턴함
  • 덮어쓰지 않게 해줌

insert_or_assign() 메서드

  • 리턴 타입은 insert와 비슷
  • 지정한 키의 원소가 이미 존재하면 덮어 씀
  • 키와 값에 대한 매개변수를 따로 받음. pair같은 객체가 아님

operator[]

  • 이 연산으로 추가하면 항상 성공함. 덮어씀
  • 값에 대한 객체를 항상 새로 만든다. 그래서 값(원소)에 대해 디폴트 생성자가 반드시 있어야 함. 그래서 insert() 보다 효율이 떨어진다.
  • 객체를 새로 만든다는 것은 operator[]를 const로 선언하지 않았다는 의미이다.
  • 그래서 변수가 map에 대한 const 레퍼런스라면 operator[]를 사용할 때 에러가 발생한다.

emplace()

  • 원소를 그자리에 곧바로 생성하도록 함
  • emplace, emplace_hint()
  • try_emplace()
    • 키가 없으면 원소를 새로 만들어 추가. 있으면 아무 일도 일어나지 않음

map의 반복자

  • 순차 컨테이너의 반복자와 비슷하게 작동한다.
  • 반복자는 pair를 가리킨다.
  • 즉, 값에 접근하려면 second로 접근해야 한다.
  • 양방향으로 작동한다.
  • 구조적 바인딩 활용 예시 
    for (const auto& [key, data] : dataMap) {
  cout << data.getValue() << endl;
}
  • 비 const 반복자로 원소 값 변경이 가능하지만, 원소의 키를 변경하면 컴파일 에러가 발생한다. 원소의 정렬 순서가 바뀔 수 있기 때문

원소 조회하기

  • operator[] 는 원소에 대한 레퍼런스를 리턴하므로 pair에서 값을 빼오지 않고도 그 자리에서 값을 읽고 쓰기가 가능하다.
  • 하지만 비 const 일때만 사용 가능하다
  • 그리고 원소가 이미 있는지 모른상태에서 사용하면 새로운 원소가 생성 되버릴 수 있으므로 유의해야 한다.
  • find() 메서드를 이용해 찾는 방법이 있다.
  • 주어진 키가 존재하는 지만 알고 싶다면 count() 메서드를 활용한다.
  • 중복 키가 없으니 0이나 1을 반환한다.
  • c++20 부터는 모든 연관 컨테이너가 contains()를 제공한다

원소 삭제하기

  • 반복자가 가리키는 특정한 지점에 있는 원소를 삭제하거나 반복자로 지정한 범위에 있는 원소 모두 삭제 기능이 있다.
  • 그리고 주어진 키와 일치하는 원소를 삭제하는 버전의 erase()를 제공한다.

노드(나중에 추가)

  • 정렬 및 비정렬 연관 컨테이너를 흔히 노드 기반(node-based) 데이터 구조라 부른다.
  • c++17 부터 표준 라이브러리에서 노드를 노드 핸들(node handle)의 형태로 직접 접근하는 기능이 추가됨

multimap

  • 한 키에 여러 값을 담을 수 있는 map.
  • multimap도 균일초기화를 지원한다.
  • 대부분 비슷하지만 다음은 map과 다르다
    • operator[]와 at()을 제공하지 않는다.
    • 원소 추가하는 연산이 항상 성공. 즉 insert()는 pair가 아닌 iterator만 반환
    • insert_or_assign, try_emplace는 지원하지 않음
  • find()가 지정한 키에 해당하는 모든 원소를 참조하는 iterator를 리턴하므로(주어진 키에 대해 첫 번째 원소가 아닐 수 있음) 별 도움이 안된다.
  • 같은 키에 속한 원소의 범위를 가리키는 iterator를 리턴하는 메서드를 다음과 같이 제공함
    • lower_bound()
    • upper_bound()
    • equal_range()
auto begin = MyMultimap.lower_bound(Key);

set

  • <set> 에 정의
  • 키가 곧 값이다.
  • map과 거의 비슷하나 값이 없어 operator[], insert_or_assign, try_emplace를 제공하지 않음
  • set 원소 수정도 되지 않음. 순서가 바뀔수 있어서

multiset



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

  • 흔히 hash table이라 불리는 unordered associative container에 unordered_map, unordered_multimap, unordered_set, unordered_multiset 이 있다.
  • 원소를 정렬하지 않음

해시 함수(hash function)

  • 비정렬 컨테이너는 해시 함수로 구현하기 때문에 해시 테이블이라 부른다.
  • 해시 테이블은 버킷(bucket)이라 부르는 배열 형태로 원소를 저장한다.
  • 버킷들에는 숫자 인덱스가 붙어 있고,
  • 해시 함수는 키를 해시 값(hash value)으로 변환한 뒤, 다시 버킷 인덱스(bucket index)로 변환하고 값을 해당 버킷에 저장한다.
  • 같은 버킷 인덱스를 가리키는 키가 두 개 이상인 상황을 해시 충돌이라고 부른다.
  • 서로 다른 키의 해시 값이 같거나, 다른 해시 값이 동일한 버킷 인덱스로 변환되는 경우가 있다.
  • 해시 충돌을 해결하기 위한 방법으로, 1. 이차 함수 재해싱(quadratic re-hashing), 2. 리니어 체이닝(linear chaining) 이 있다.
  • 대부분은 리니어 체이닝을 사용한다.
    • 키에 대응 되는 데이터 값을 버킷에 직접 저장하지 않고, 연결 리스트에 대한 포인터를 저장한다.
    • 이 연결 리스트에 해당 버킷에 대한 값들이 들어 있다.
    • 해시 값에 따라 버킷 인덱스를 구하는 과정은 복잡도가 상수 시간이지만 연결 리스트를 따라 값을 찾는 과정은 복잡도가 선형 시간이다.
  • 충돌이 전혀 없는 해시 함수 인 완전 해시(perfect hash)는 조회의 시간 복잡도가 상수 시간이다.
  • c++ 표준에서는 기본 타입, 포인터 타입, error_code, error_condition, optional, variant, bitset, unique_ptr, shared_ptr, type_index, string, string_view, vector, thread::id 에 대해서 해시 함수 제공한다.
  • 원하는 키 타입을 제공하지 않는다면 직접 구현해야 한다.

unordered_map

  • 다음과 같이 정의되어 있다. 
    template<class Key,
       class T,
       class Hash = hash<Key>,
       class Pred = std::equal_to<Key>,
       class Alloc = std::allocator<std::pair<const Key, T>>>
class unoredered_map;
  • 순서대로 키, 값, 해시, 등호 비교, 할당자 타입 이다.
  • 마지막 세 매개변수는 대부분 default 값을 사용한다.
  • map 처럼 균일 초기화 적용 가능하다.
    ```cpp unoredered_map<int, string> m { {1, “one”}, {2, “two”} };

for (const auto& [key, value] : m) { cout « format(“{} = {}”, key, value) « endl; }

for (const auto& p : m ) { cout « format(“{} = {}”, p.first, p.second) « endl; }

### 주요 메서드
- load_factor()
	- 버킷당 평균 원소 수
- bucket_count()
	- 컨테이너에 있는 버킷 수 리턴
- bucket(key)
	- 키의 버킷 인덱스 리턴
- begin(n)
	- 인덱스가 n인 버킷에 있는 첫 번째 원소를 가리키는 local_iterator 리턴
- end(n)
	- 인덱스가 n인 버킷에 있는 마지막 바로 다음 원소를 가리키는 local_iterator 리턴

### 예시 코드

```cpp
#include <iostream>
#include <map>

using namespace std;
void PrintMap (const unordered_map<string, string> m)
{
	for (auto& [key, value] : m)
	{
		cout << key << " (Print: "<< value << ")" << endl;
	}
	cout << "------"<< endl;
}

int main()
{
	unordered_map<string, string> PhoneBook {
		{"Kim", "12345"},
		{"Son", "67890"}
	};
	PrintMap(PhoneBook);

	// 전화번호 추가 / 삭제
	PhoneBook.insert(make_pair("Lee", "34567"));
	PhoneBook["Moon"] = "23456";
	PhoneBook["Choi"] = "78904";
	PhoneBook.erase("Choi");
	PrintMap(PhoneBook);

	// 주어진 키의 버킷 인덱스 검색
	const size_t bucket = PhoneBook.bucket("Moon");
	cout << "bucket index of Moon is " << bucket << endl;
	cout << "the bucket of Moon contains " << PhoneBook.bucket_size(bucket) << endl;

	// 여기서 auto는 unordered_map<string, string>::const_local_iterator 로 추론한다.
	auto LocalBegin = PhoneBook.cbegin(bucket);
	auto LocalEnd = PhoneBook.cend(bucket);
	for (auto iter = LocalBegin; iter != LocalEnd; ++iter) {
		cout << iter->first << "'s Phone number : " << iter->second << endl;
	}
	cout << "------" << endl;
	cout << "There are " << PhoneBook.bucket_count() << "buckets in the PhoneBook" << endl;
	cout << "Average number of elements in a bucket is " << PhoneBook.load_factor() << endl;
}

/* 출력결과
Kim (Print: 12345)
Son (Print: 67890)
------
Kim (Print: 12345)
Moon (Print: 23456)
Son (Print: 67890)
Lee (Print: 34567)
------
bucket index of Moon is 3
the bucket of Moon contains 2
Moon's Phone number : 23456
Kim's Phone number : 12345
------
There are 5buckets in the PhoneBook
Average number of elements in a bucket is 0.8
*/

unordered_multimap

  • 같은 키로 여러 원소를 대응시킬 수 있는 unordered_map 이다.

    차이점

  • 한 키가 여러 원소를 가리키기 때문에 operator[] 와 at() 을 제공하지 않는다.
  • 추가 연산이 항상 성공한다. 키가 중복된다고 실패하지 않음
  • 그래서 insert_or_assign()과 try_emplace()를 제공하지 않음
  • find()로 조회하더라도 지정한 키에 대응되는 원소 중 첫번째가 아닌 다른 원소를 가리키는 반복자를 리턴할 수도 있다.
  • equal_range로 조회하는 것이 좋다

unordered_set, unordered_multiset

  • map의 경우와 비슷



기타 컨테이너

표준 라이브러리와 함께 사용할 수 있는 여러 컨테이너가 있다.
c 스타일 배열, string, 스트림, bitset 등이 있다

표준 C 스타일 배열

  • 정식 표준 라이브러리 컨테이너는 아니지만 원소에 대한 포인터를 반복자로 사용하면 표준 라이브러리 컨테이너처럼 사용 가능하다.
  • 정적 할당 c 스타일 배열의 경우,
    • std::begin, std::cbegin, std::end std::cend 로 원소에 대한 반복자를 쉽게 구할 수 있다.
    • 배열의 이름은 첫 번째 원소에 대한 주소처럼 쓸 수 있다.
    • 배열의 이름 + 배열의 사이즈 = 마지막에서 바로 다음번 째 원소를 가리키는 반복자

string

  • 표준라이브러리의 vector 처럼 쓸 수 있다.

스트림 (17장)

bitset

  • 고정된 크기의 비트열을 추상화한 것.
  • 크기가 조정되었고, 원소 타입에 대해 템플릿화할 수 없으며, 반복자를 제공하지 않는다.
  • <bitset>에 정의되어 있으며 저장할 비트 수에 대해 템플릿화 할 수 있다.
  • 디폴트 생성자는 모든 필드를 0으로 초기화한다.
  • 0과 1 문자로 구성된 string을 bitset으로 만드는 생성자도 있다.
  • 각 비트 값은 set(), unset(), flip() 메서드로 설정 가능하고, 오버로딩된 operator[] 연산으로 각 필드값을 조회하거나 설정도 가능하다.
  • 비 const 객체에 대해 operator[] 연산을 수행하면 flip()을 호출하거나 operator~ 연산으로 부울값을 할당할 수 있는 프록시 객체를 리턴한다.
  • test() 메서드로 개별 필드에 접근도 가능함
  • 추가 및 추출 연산으로 bitset을 스트림으로 처리할 수도 있음. 그럼 0과 1 문자로 표현된 string으로 처리됨
  • 비트 연산자 모두 제공한다.

예시 코드

#include <iostream>
#include <bitset>
#include <string>

using namespace std;

int main()
{
	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;

	string str1 = "0011001100";
	auto str2 = "0000111100";
	bitset<10> BitsOne(str1);
	bitset<10> BitsTwo{str2};
	auto BitsThree = BitsOne & BitsTwo;

	cout << BitsThree << endl;
	BitsThree <<= 4;
	cout << BitsThree << endl;
}

/*
 Bit 3 is set 
1101001000
0000001100
0011000000
*/

사용 예 ( 책 참고 )

Leave a comment

You may also enjoy