[C++ 프로그래밍 / STL] Chapter5. 연관 컨테이너와 비순차 컨테이너

YH·2023년 8월 9일
Mapcppmultimapsetstlunordered_mapunordered_set비순차컨테이너연관컨테이너프로그래밍
0

CPP 프로그래밍(STL)

목록 보기
6/7

Chapter5. 연관 컨테이너와 비순차 컨테이너

1. STL 연관 컨테이너

연관 컨테이너는 Key와 Value를 연관시켜 데이터를 관리한다. 이들은 데이터의 정렬상태를 항상 유지하기 때문에 삽입/삭제/룩업 성능이 모두 동일하게 로그시간 복잡도를 갖는다. 내부적으로 균형잡힌 이진 탐색 트리를 구현하고 있으나 트리는 직접 접근할 수 없다. 표준 연관 컨테이너는 set, multiset, map, multimap 총 네 종류가 있다.
각 컨테이너의 특징은 이름을 보면 쉽게 알 수 있다. set은 Key 자체가 Value이며 중복 Key를 허용하지 않는다. multiset은 set처럼 Key가 Value인데 중복 Key를 허용한다. map은 Key와 Value가 별개이며 중복 Key를 허용하지 않는다. multimap은 Key와 Value가 별개이며 중복 Key를 허용한다.
이들 모두 템플릿 파라미터 비교 클래스가 있는데 디폴트 비교 클래스를 사용하려면 항목 타입에 operator <가 정의되어 있어야 한다.

1) set

set은 헤더에 다음과 같이 정의되어 있다.

template <
	typename _Kty,
    typename _Pr = less<_Kty>,
    typename _Alloc = allocator<_Kty>
> class set;

첫 번째 파라미터가 항목의 타입이고 두 번째 파라미터가 정렬을 위한 비교 연산 타입이다. 디폴트 값이 less 템플릿 인스턴스 이므로 오름차순으로 데이터를 정렬한다. priority_queue에서 했던 것처럼 내림차순으로 바꾸기 위해 항목을 삽입하거나 읽을 때 부호를 반전시키는 방법이 있고, 두 번째 파라미터에 greater 템플릿 인스턴스를 넘겨주는 방법이 있다.

2) insert, emplace, emplace_hint

항목 삽입을 위하 메서드들이다.
다음은 insert 메서드의 오버로딩 목록이다. C++17 이후에는 노드 타입을 지원하면서 추가된 버전이 더있지만 여기서는 다루지 않는다.

std::pair<iterator, bool> insert( const value_type& value ); //1
std::pair<iterator, bool> insert( value_type&& value ); //2
iterator insert( const_iterator hint, const value_type& value ); //3
iterator insert( const_iterator hint, value_type&& value ); //4
template< class InputIt >
void insert( InputIt first, InputIt last ); //5
void insert( std::initializer_list<value_type> ilist ); //6

1번 버전은 항목 타입의 왼값을 받고 iterator와 bool의 쌍을 반환한다. iterator는 삽입한 항목을 가리키는 반복자이며 bool은 삽입의 성공 여부이다. set은 중복 key를 허용하지 않기 때문에 이미 동일한 key가 존재하면 insert가 실패할 수 있다. 실패한 경우 함께 반환되는 반복자는 중복된 key를 가지는 기존 항목을 가리키는 반복자이다.
2번 버전은 1번과 같지만 오른값 인자를 받아 가능한 경우 이동시맨틱을 적용한다.
3번 버전은 삽입할 위치를 힌트로 알려주는 버전이다. 이 버전을 통해 삽입하면 상수 시간에 값을 삽입할 수 있다. 삽입을 위한 이분탐색과 실제 삽입의 기능을 분리하여 그 사이에 특정한 처리를 해야하는 경우 사용할 수 있다. 만약 힌트로 넘겨준 반복자가 메서드를 호출한 인스턴스의 반복자가 아니거나 정렬 상태에 맞지 않는 위치라면 힌트는 무시되어 이분 탐색 후 삽입된다. 1, 2번 버전과 달리 반환형에 bool 값이 빠져있는데 이는 다른 순차 컨테이너의 위치 삽입과 시그니처 호환을 통해 제너릭 프로그래밍에 도움이 되기 위한 목적의 설계이다. 실제 삽입의 성공여부를 확인하려면 삽입 전후로 size를 확인해야 한다.
4번 버전은 3번과 같지만 오른 값 인자를 받아 가능한 경우 이동시맨틱을 적용한다.
5번 버전은 반복자 쌍을 통해 삽입할 항목열을 받는다. 다른 컨테이너 등의 항목열을 한번에 삽입할 때 유용하다. 복수의 항목이 삽입될 수 있기 때문에, 어떤 항목들이 실제로 삽입에 성공했는지를 확인할 수 없다.
6번 버전은 initializer_list를 받는 버전으로 중괄호 초기치를 통해 일련의 항목열을 전달할 수 있게 해준다. 5번과 마찬가지로 어떤 항목들이 실제로 삽입에 성공했는지를 확인할 수 없다.
다음 코드는 각 버전의 실제 사용 예를 보여준다.

#include <set>
#include <vector>

using namespace std;

int main()
{
	vector<int> v {2,4,6};
    int set<int> s;
    s.insert({1,5,9}); //정렬되어 있지 않아도 가능
    s.insert(v.begin(), v.end()); //정렬되어 있지 않아도 가능
    s.insert(s.cend(), 10);
    s.insert(3);
}

emplace 메서드는 항목 생성을 위한 인자 목록을 받아 pair<iterator, bool>을 반환하는 한 가지 버전만 존재한다. 1번 버전의 insert와 유사하지만 이동 생성 비용만큼 비용을 줄일 수 있다.
emplace_hint는 insert_hint에 대응되는 emplace 버전이다. emplace가 가변 인자를 받기 때문에 emplace에 오버로딩을 하는 것이 불가능하여 다른 이름의 메서드로 구현되어 있다. 첫 번째 인자로 hint 반복자를 주고 이후에 항목 생성을 위한 인자 목록을 차례로 넘겨주면 된다. 이것 역시 올바른 힌트를 넘겨주면 상수 시간에 처리되고 그렇지 않으면 로그 시간에 처리된다.

3) clear, erase

clear는 다른 컨테이너들과 마찬가지로 전체 항목열을 비워내는 메서드이고 파라미터나 반환형은 없다.
erase는 크게 분류하면 값을 받아서 해당 항목을 이분 탐색으로 찾아서 삭제해주는 버전이 있고 반복자를 받아서 상수시간에 삭제해주는 버전이 있다. 반복자를 받는 버전은 반복자 하나로 특정 위치의 항목을 삭제하는 버전과 반복자 쌍으로 특정 범위 내의 항목들을 일괄적으로 삭제하는 버전으로 나뉜다. 이 반복자들은 반드시 메서드를 호출한 인스턴스의 반복자여야 한다.
반복자를 넘겨서 삭제하는 버전은 마지막으로 삭제한 항목의 다음 항목을 가리키는 반복자를 반환한다. 처음에는 반환형이 void 였다가 C++11버전부터 반환형이 추가되었는데 이러한 결정에는 반복자 무효화 현상과 관련이 있어보인다.
기존에는 set을 순회하면서 erase를 하는 경우 반복자 무효화를 피하기 위해 erase에 넘기는 반복자에 후위증가연산을 해야만 했다. 그런데 일반적으로 반복자에 대한 증가연산은 효율성을 위해 전위증가를 사용하는게 권장되기 때문에 코딩 스타일의 일관성이 깨지면서 다소 어색한 코드일 수 있어 반환형을 수정한 것으로 보인다.

#include <set>
#include <iostream>

using namespace std;

int main()
{
	set<int> c = { 1, 2, 3, 4 };
    
    auto print = [&c] {
    	cout << "c = { ";
        for(int n : c)
        	cout << n << ' ';
        cout << "}\n";
    };
    print();
    
    cout << "Erase all odd numbers:\n";
    for(auto it = c.begin(); it != c.end(); ) {
    	if(*it & 1)
        	it = c.erase(it); //또는 c.erase(it++);
        else
        	++it;
    }
    print();
    
    //값으로 삭제하는 버전은 삭제한 항목의 개수를 반환한다.
    cout << "Erase 1, erased count: " << c.erase(1) << '\n'; //return 0
    cout << "Erase 2, erased count: " << c.erase(2) << '\n'; //return 1
    cout << "Erase 2, erased count: " << c.erase(2) << '\n'; //return 0
    print();
}

4) find, count

find는 key를 가지고 항목을 찾아 반복자를 반환해준다. 만약 찾는 key와 일치하는 항목이 없으면 end 반복자를 반환한다.
count는 key를 가지고 set에서 해당 key를 갖는 항목을 카운팅하여 반환해준다. set은 중복 항목을 허용하지 않기 때문에 존재하지 않으면 0을, 존재하면 1을 반환하게 된다.
count 인터페이스가 다소 어색할 수 있지만 이렇게 설계된 이유는 다른 연관 컨테이너들과 메서드 시그니처 호환성을 갖도록 하여 제너릭 코드를 수월하게 하기 위함이다.
C++20에서는 bool 타입으로 반환해주는 contains 메서드가 추가로 제공된다.

#include <iostream>
#include <set>

using namespace std;

int main()
{
	set<int> s {1,2,3,4};
    if (s.find(5) == s.end())
    	cout << "not found 5" << endl;
    else
    	cout << "found 5" << endl;
}

5) lower_bound, upper_bound, equal_range

STL 알고리즘에 있는 함수들과 같은 기능을 한다.
lower_bound에서 찾는 key가 존재한다면 해당 항목을 가리키는 반복자를 반환할 것이고 존재하지 않는다면 key보다 작지 않은(less 연산 기준) 첫 항목을 반환한다. 즉, 해당 key를 삽입했을 때 정렬상태를 깨지 않을 위치의 반복자를 반환한다.
upper_bound는 key보다 큰(less 연산 기준) 첫 항목을 반환한다. key보다 큰 항목이 없으면 end 반복자를 반환한다. 이 메서드는 중복을 허용하지 않는 set에서는 효용이 크지 않아 잘 쓰이지 않는다.
equal_range는 위의 두 메서드의 반환값들을 pair로 묶어서 반환한다. upper_bound의 효용이 크지 않기 때문에 equal_range 역시 잘 쓰이지 않는다.

6) multiset

중복을 허용하는 set이다. set과 같이 헤더에 정의되어 있으며 템플릿 파라미터도 동일하다. set과 다른 점들을 정리해보면 다음과 같다.

  • insert 및 emplace가 항상 성공하기 때문에 bool값 없이 iterator만 반환한다.
  • find는 하나의 항목만 찾아주기 때문에 multiset에서는 효용성이 떨어진다.
  • lower_bound, upper_bound, equal_range를 통해 중복 항목들을 순회할 수 있는 반복자를 얻을 수 있으므로 find 대신에 이 룩업 함수들이 자주 쓰인다.

첫번째 차이점을 제외하고는 인터페이스 자체는 동일하기 때문에 set을 사용할 줄 안다면 multiset도 쉽게 사용할 수 있다.

7) map

map은 Key를 기준으로 정렬하여 연관된 Value들을 저장하는 컨테이너이다. 헤더에 다음과 같이 정의되어 있다.

template<
	typename _Kty, typename _Ty,
    typename _Pr = less<_Kty>,
    typename _Alloc = allocator<const _Kty, _Ty>>
> class map;

비교는 Key에 대해서만 수행하기 때문에 만약 서로 다른 두 타입을 연관시켜 저장해야 하는데 어떤 타입을 Key로 하든 상관없는 상황이라면 비교 연산의 오버헤드가 적은 타입을 Key로 하는 것이 좋다. 예를들어 int 타입과 string 타입을 연관시킨다면 int 타입을 key로 string을 value로 하는 것이 유리하다.
인터페이스는 set과 유사한데 몇 가지 다른 점이 있다.

  • insert에 값으로서 넘겨줄 인자는 Key와 Value의 pair 타입이다. 임시객체를 만들어 넘긴다면 중괄호 초기화 또는 make_pair 함수 등을 활용하면 된다.
  • operator[]를 지원한다. []안에는 Key값이 들어가며, 해당 Key가 이미 존재하면 Value의 왼값을 반환하고 존재하지 않으면 항목을 자동으로 생성한 후 Value의 왼값을 반환한다. 때문에 operator[]를 사용하기 위해서는 Value 타입이 디폴트 생성자를 가지고 있어야만 한다. 또한 항목을 자동으로 생성할 수도 있기 때문에 const로 선언되지 않았는데 이것이 제약이 되는 경우가 있을 수도 있다.
void func1(const map<int, int>& m) {
	cout << m[1] << endl; //컴파일 에러
}
void func2(const map<int, int>& m) { //오류 없는 구현
	if (m.find(1) != m.end())
    	cout << iter->second << endl;
}
  • 위의 func2 예에서 보다시피 map의 반복자는 Key, Value로 구성된 pair를 가리킨다.
  • 룩업만을 위한 at메서드를 지원한다. 이 메서드는 존재하지 않는 key인 경우 std::out_of_range 익셉션을 던진다. 존재하는 경우 Value를 왼값으로 반환한다. 다음과 같이 const 버전과 non-const 버전이 오버로딩되어 있다.
_Ty& at (const _Kty& key);
const _Ty& at (const _Kty& key) const;

8) multimap

중복 key를 허용하는 map이다. map과 마찬가지로 헤더에 정의되어 있고 템플릿 파라미터도 같다. 인터페이스 역시 map과 거의 같지만 다른 점이 몇 가지 있다.

  • 키 하나에 복수의 항목이 존재할 수 있기 때문에 operator[]와 at 메서드를 지원하지 않는다.
  • 키 중복이 허용되기 때문에 삽입 메서드는 항상 성공하고, 때문에 bool값 없이 iterator만 반환한다.
  • find 역시 하나의 항목만 찾아주고 그것이 첫 번째 항목인지 조차 보증하지 않기 때문에 효용성이 떨어지고 주로 lower_bound, upper_bound, equal_range 메서드를 통해 룩업을 수행하게 된다.

2. STL 비순차 연관 (해시 테이블) 컨테이너

C++11에서는 비순차 연관 컨테이너가 추가되었다. 해시 테이블은 기반으로 연관 데이터를 관리하기 때문에 해시 테이블 컨테이너라고 부르기도 한다. 컨테이너의 인터페이스나 기능을 보면 연관 컨테이너와 거의 유사하다. 다른 점은 해시 테이블은 데이터를 정렬하여 저장하는 방식이 아니기 때문에 이들이 제공하는 반복자는 정렬된 순서가 아닌 임의의 순서이다.
해시 충돌 대응 방법에 대해서는 표준에서 정하지 않았지만 대부분의 구현에서 리니어 체이닝 기법을 사용한다. 버킷의 크기를 키울수록 해시 충돌 가능성이 줄어들어 성능이 좋아지지만 메모리 크기가 한정적이기 때문에 무한정 늘릴 수도 없는 노릇이다. 때문에 버킷의 수를 적절하게 설정해주어 메모리 사용량과 성능의 균형을 유지하는데 이러한 작업은 자동으로 이루어지지만 버킷의 수가 바뀌게 되면 전체 항목에 대해 재해싱이 발생하면서 오버헤드가 발생하므로 가능하면 처음부터 적절한 버킷의 수를 가지도록 세팅해주는 것이 유리하다. 이것은 마치 vector를 사용할 때 reserve를 통해 항목열의 이사로 인한 오버헤드를 회피하는 것과 유사하다.
해시 테이블 특성상 반복자가 무효화되는 상황이 잦은데 clear, rehash, reserve, operator = 메서드의 호출시 모든 반복자가 무효화되고, insert, emplace, emplace_hint 등의 삽입 메서드에서도 해시 충돌이 발생한다면 해당 key의 항목을 가리키는 반복자들이 무효화된다. 따라서 비순차 연관 컨테이너의 반복자를 따로 저장해뒀다가 이후에 룩업하는 구현 등은 피하는 것이 좋다.

보충 내용 (고급)

Hash란 무한한 정의역과 유한한 치역을 갖는 함수이다. 그렇기 때문에 서로 같은 입력에서 동일한 출력이 나오는 해시 충돌이 존재하며 이는 원천적으로 완전히 회피하는 것이 불가능하다. Hash는 주로 두 분야에서 사용된다. 한 가지는 정보 보안이며 다른 한가지는 데이터 베이스이다.
정보 보안에서는 무결성을 검증하기 위한 도구로 사용되는데 이는 Hash 함수의 단방향성에 기인하여 쓰인다. 이때는 Hash 충돌 내성이 반드시 보장되어야한다. hash 충돌 내성이란 어떤 입력 X에 대해서 Hash(X)=Hash(Y)인 입력 Y를 발견하기 매우 어렵고(약한 충돌 내성), 해시 출력이 동일한 임의의 입력쌍을 발견하기 매우 어려운(강한 충돌 내성) 성질을 말한다.
데이터 베이스에서는 Hash의 치역이 유한하다는 성질에 기인하여 사용된다. 데이터 베이스에서는 자료의 목적에 맞게 다양한 구조로 데이터를 저장하는데 그 중 Hash Table이라는 자료구조는 어떤 데이터를 저장하기 위해서 데이터의 해쉬값을 데이터를 저장할 주소(인덱스 등 위치정보 = 버킷 인덱스)로 사용한다. 즉, 데이터는 버킷들의 배열에 담기는데 데이터의 해쉬값이 곧 버킷의 인덱스가 된다.
데이터의 개수와 무관하게 데이터의 해쉬값만 계산하면 위치를 알 수 있으므로 이상적으로는 삽입/삭제/룩업에 상수 시간복잡도를 갖는다. 다만 해시 충돌이 있기 때문에 동일한 버킷(보통 버킷은 연결리스트로 구현됨)에 여러 항목이 담기게 되는데 이 때문에 해시 충돌을 최소화해줘야 성능을 최대화 할 수 있다. 이것은 해쉬 충돌 내성과는 다른 개념이지만 해쉬 충돌 내성을 갖는 해쉬함수는 해쉬 값의 분포도 무작위적이기 때문에 정보 보안에서 사용되는 해쉬함수를 사용할 수도 있다. 그러나 그러한 해쉬함수는 충돌내성을 보장하기 위해 상당한 복잡한 수학적 연산을 거치기 때문에 Hash 연산의 오버헤드로 인해 실제 성능이 크게 떨어질 수 있다.

1) HashTable 관련 메서드

비순차 연관 컨테이너들은 연관 컨테이너에 대응하여 네 가지가 있는데 연관 컨테이너 버전의 인터페이스를 그대로 계승하면서 HashTable과 관련한 인터페이스들을 추가로 제공한다. 이 메서드들을 이해하기 위해서는 HashTable 구조에 대한 이해가 필요하다.

  • bucket_count
    파라미터가 없는 메서드이고 호출하면 해시테이블의 버킷 개수를 반환한다.

  • bucket
    키를 인자로 받아 해당 키의 버킷 인덱스를 반환한다. 이 메서드는 그 자체로는 어떤 의미있는 작업을 할 수 없지만 후술할 bucket_size 등을 위해 선행된다.

  • bucket_size
    버킷 인덱스를 인자로 받아 해당 버킷 안에 있는 항목의 개수를 반환한다. 여기서 1이 반환된다면 해당 버킷에는 해시 충돌이 없다는 것을 확인할 수 있다.

  • load_factor
    파라미터가 없는 메서드이고 버킷당 항목의 평균 개수를 float 타입으로 반환한다. size()를 bucket_count()로 나눈 값과 같다.

  • max_load_factor

float max_load_factor() const; //1번
void max_load_factor( float ml ); //2번

max_load_factor란 load_factor를 어디까지 허용하는지를 나타낸 것이다. load_factor가 설정된 max_load_factor를 넘어가게 되면 bucket_count를 늘려서 재해싱을 하게 된다. 재해싱이 발생하면 기존에 저장해둔 반복자나 버킷의 인덱스는 모두 무효화된다. max_load_factor를 get하는 버전(1번)과 set하는 버전(2번)이 오버로딩되어 있다.

  • rehash
    버킷의 수를 인자로 받아 bucket_count를 바꾸면서 재해싱한다. 이로인해 load_factor가 max_load_factor를 넘게되면 bucket_count는 최소 size() / max_load_factor()로 조정된다. 즉 max_load_factor가 더 우선순위가 높기 때문에 rehash보다는 max_load_factor를 관리하는 것을 권장한다.

  • reverse
    max_load_factor를 초과하지 않으면서 bucket_count를 최소화하도록 재해싱한다. 삽입 또는 삭제를 일괄적으로 수행한 후 룩업 작업만 남겨둔 상태에서는 메모리 점유율을 낮추기 위해 이 메서드를 호출하는 것을 고려할만 하다.

  • hash_function
    인자가 없는 메서드이고 사용중인 해시함수를 반환해준다.

  • key_eq
    인자가 없는 메서드이고 Key를 비교하기 위한 비교함수를 반환해준다.

2) unordered_set

set의 해시 테이블 버전이다. <unordered_set> 헤더에 다음과 같이 정의되어 있다.

template<
	typename _Kty,
    typename _Hasher = std::hash<_Kty>,
    typename _Keyeq = std::equal_to<_Kty>,
    typename _Alloc = std::allocator<_Kty>
> class unordered_set;

set의 인터페이스를 모두 포함하고 있으며 추가적으로 HashTable 관련 인터페이스들을 제공한다.

3) unordered_multiset

multiset의 해시 테이블 버전이다. <unordered_set>헤더에 정의되어 있으며 템플릿 파라미터는 unordered_set과 동일하다. multiset의 인터페이스에 더해 HashTable 관련 인터페이스들을 제공한다.

4) unordered_map

map의 해시 테이블 버전이다. <unordered_map> 헤더에 다음과 같이 정의되어 있다.

template<
	typename _Kty,
    typename _Ty,
    typename _Hasher = std::hash<_Kty>,
    typename _Keyeq = std::equal_to<_Kty>,
    typename _Alloc = std::allocator<std::pair<const _Kty, _Ty>>
> class unordered_set;

map의 인터페이스를 모두 포함하고 있으며 추가적으로 HashTable 관련 인터페이스들을 제공한다.

5) unordered_multimap

multimap의 해시 테이블 버전이다. <unordered_map> 헤더에 정의되어 있으며 템플릿 파라미터는 unordered_map과 동일하다. multimap의 인터페이스에 더해 HashTable 관련 인터페이스들을 제공한다.

profile
YH
Keep Recycling Your Dreams
이전 포스트

[C++ 프로그래밍 / STL] Chapter4. 알고리즘 Part.2

다음 포스트

[C++ 프로그래밍 / STL] Chapter6. 알고리즘 Part.3

0개의 댓글