_C++_연관 컨테이너_비순차 연관 컨테이너

STL 연관 컨테이너

연관 컨테이너는 Key와 Value를 연관시켜 데이터를 관리한다.

데이터의 정렬상태를 항상 유지함. (삽입, 삭제, 룩업 성능이 모두 동일하게 로그 시간복잡도를 가짐.)

내부적으로 균형잡힌 이진 탐색 트리를 구현하고 있으나 트리는 직접 접근 불가.

표준 연관 컨테이너는 다음과 같이 네 종류가 있다.

• 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;

첫 번째 파라미터: 항목의 타입

두 번째 파라미터: 정렬을 위한 비교 연산 타입. default value는 less템플릿(오름차순)

priority_queue에서 했던 것 처럼 내림차순으로 바꾸기 위해 항목을 삽입하거나 부호를 반전시키는 방법이 있음. 또는 greater<>을 넘겨주면 된다.

 

insert, emplace, emplace_hint

항목 삽입을 위한 매서드이다.

다음과 같이 사용한다.

insert 메서드의 오버로딩 목록이다.

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를 받는 버전으로 중괄호 초기치를 통해 일련의 항목열을 전달할 수 있게 해준다.

복수의 항목이 삽입될 수 있기 때문에, 어떤 항목들이 성공했는지 확인할 수 없다.

//실제 사용 예시
#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 반복자를 주고 이후에 항목 생성을 위한 인자 목록을 차례로 넘겨주면 된다.

올바른 힌트를 넘겨주면 상수시간에 처리되고, 그렇지 않으면 로그 시간에 처리된다.

 

clear, erase

clear은 전체 항목열을 비워내는 메서드이고 파라미터, 반환형은 없다.

erase

1. 값을 받아서 해당 항목을 이분 탐색으로 찾아서 삭제해주는 버전
2. 반복자를 받아서 상수 시간에 삭제해주는 버전
   • 반복자 하나로 특정 위치의 항목을 삭제하는 버전
   • 반복자 쌍으로 특정 범위 내의 항목들을 일괄적으로 삭제하는 버전

반복자들은 반드시 메서드를 호출한 인스턴스의 반복자로 사용해야 한다.

반복자를 넘겨서 삭제하는 버전은 마지막으로 삭제한 항목의 다음 항목을 가리키는 반복자를 반환한다.

처음에는 반환형이 void였다가 C++11버전부터 반환형이 추가 되었다.

#include <set>
#include <iostream>
using namespace std;
int main()
{
    set<int> c = { 1, 2, 3, 4 };
 
    auto print = [&c] {
        for(int n : c)
            cout << n << " ";
        cout << "\n";
    };
    print();
 	
    //홀수 제거
    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();
}

 

find, count

find는 key를 가지고 항목을 찾아서 반환해준다. 만약 찾는 key와 일치하는 항목이 없으면 end 반복자를 반환한다.

count는 key를 가지고 set에서 해당 key를 갖는 항목을 카운팅하여 반환해준다.

C++20에서는 bool타입으로 반환해주는 contains메서드가 추가로 제공된다.

#include <iostream>
#include <set>
using namespace std;
int main()
{
	set<int> s {1,2,3,4};

    // 5를 찾지 못했으므로 not found 5를 출력.
	if (s.find(5) == s.end())
		cout << "not found 5" << endl;
	else
		cout << "found 5" << endl;
    
    cout << s.count(4); // 1
}

 

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의 효용이 크지 않기 때문에 잘 쓰이지 않는다.

 

2. multiset

중복을 허용하는 set으로 set과 같은 헤더에 정의되어잇으며, 동일한 템플릿 파라미터를 갖는다.

set을 사용할 줄 안다면, multiset도 쉽게 사용할 수 있다.

- 다른점

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

 

3. map

map은 Key를 기준으로 정렬하여 연관된 Value들을 저장하는 컨테이너이다.

헤더의 정의는 다음과 같다.

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

비교는 Key에 대해서만 수행한다. 만약 서로 다른 두 타입을 저장하는데 어떤 타입을 Key로 하든지 상관이 없다면 비교 연산의 오버헤드가 적은 타입을 Key로 하는게 좋다.

인터페이스가 set과 유사하지만, 몇 가지 다른점이 있다.

• insert 값으로 넘겨줄 인자는 Key, Value의 pair 타입이다. 임시객체를 만들어 넘긴다면 중괄호 초기화 또는 make_pair 함수 등을 활용
• operator[]를 지원한다. []안에는 Key값이 들어가며, 해당 Key가 존재한다면 Value의 왼값을 반환하고 존재하지 않으면 자동으로 생성한 후 Value의 왼값을 반환한다. operator[]를 사용하기 위해서는 Value 타입이 디폴트 생성자를 가지고 있어야한다.또한, 항목을 자동으로 생성할 수도 있어서 const로 선언되지 않았는데 이것이 제약이 될 수 있다.

#include <iostream>
#include <map>
using namespace std;

int main()
{
    map<int, int> m;
    m[1] = 101;
    m[2] = 102;

    cout << m[1] << "\n"; //101
    cout << m[2] << "\n"; //102
    cout << m[3] << "\n"; //0

    return 0;
}

룩업만을 위한 at 메서드를 지원한다.

const 버전과 non-const 버전이 오버로딩 되어있다.

_Ty& at (const _Kty& key);
const _Ty& at (const _Kty& key) const;

- 사용법 정리

C++_map

 

 

4. multimap

중복 Key를 허용하는 map이다. map과 함께 헤더에 정의되어 있고 템플릿 파라미터도 같다.

몇 가지 다른점을 제외하고 인터페이스가 map과 같다.

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

 

---

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

비순차 연관 컨테이너는 C++11에서 추가되었다.

해시 테이블을 기반으로 연관 데이터를 관리하기 때문에 해시 테이블 컨테이너라고 부른다.

인터페이스나 기능은 연관 켄테이너와 거의 유사하지만, 해시 테이블은 데이터를 정렬하여 저장하는 방식이 아님 때문에 이들이 제공하는 반복자는 정렬된 순서가 아닌 임의의 순서이다.

해시 충돌 대응 방법에 대해서는 표준에서 정하지 않았지만 대부분의 구현에서 리니어 체이닝 기법을 사용한다. 버킷의 크기를 키울 수록 해시 충돌 가능성이 줄어들어 성능이 좋아지지만 메모리 크기가 한정적이기 때문에 무한정 늘릴 수도 없다.

버킷의 수를 적절하게 설정해주어 메모리 사용량과 성능의 균형을 유지해야한다.

이러한 작업은 자동으로 이루어지지만 버킷의 수가 바뀌게 되면 전체 항목에 대해 재해싱이 발생하면서 오버헤드가 발생하므로 가능하면 처음부터 적절한 버킷의 수를 가지도록 세팅해주는 것이 유리하다.
해시 테이블 특성상 반복자가 무효화되는 상황이 잦은데 clear, rehash, reserve, operator= 메서드의 호출시 모든 반복자가 무효화되고, insert, emplace, emplace_hint 등의 삽입 메서드에서도 해시 충돌이 발생한다면 해당 key의 항목을 가리키는 반복자들이 무효화된다.

따라서 비순차 연관 컨테이너의 반복자를 따로 저장해뒀다가 이후에 룩업하는 구현 등은 피하는 것이 좋다.

 

HashTable 관련 메소드

비순차 연관 컨테이너들은 연관 컨테이너에 대응하여 네 가지가 있다.

연관 컨테이너 버전의 인터페이스를 그대로 계승하며 HashTable과 관련한 인터페이스들을 추가로 제공한다.

 

bucket_count

파라미터가 없는 메소드. 호출하면 해시테이블의 버킷 개수를 반환.

 

bucket

키를 인자로 받아 해당 키의 버킷 인덱스를 반환.

메소드 그 자체로는 의미있는 작업을 할 수 없지만, bucket_size등을 위해 선행된다.

 

bucket_size

버킷 인덱스를 인자로 받아 해당 버킷 안에 있는 항목의 개수를 반환.

1이 반환되면 해당 버킷에는 해시 충돌이 없다는 것을 확인할 수 있음.

 

load_factor

파라미터가 없는 매서드이고 버킷당 항목의 평균 개수를 float type으로 반환.

size()를 bucket_count()로 나눈 값과 같다.

 

max_load_factor

max_load_factor는 load_factor를 어디까지 허용하는지를 나타낸 것이다.

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

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

 

rehash

버킷의 수를 인자로 받아 bucket_count를 바꾸면서 재해싱한다.

이로인해 load_factor가 max_load_factor를 넘게되면 bucket_count는 최소 size() / max_load_factor()로 조정된다.

즉, max_load_factor가 더 우선순위가 높기 때문에 rehash보다는 max_load_factor를 관리하는 것을 권장합니다.

 

reserve

max_load_factor를 초과하지 않으면서 bucket_count를 최소화하도록 재해싱한다.

삽입 또는 삭제를 일괄적으로 수행한 후 룩업 작업만 남겨둔 상태에서는 메모리 점유율을 낮추기 위해 이 메서드를 호출하는 것을 고려할만 하다.

 

hash_function

인자가 없는 메소드. 사용중인 해시함수를 반환.

 

key_eq

인자가 없는 메소드. Key를 비교하기 위한 비교함수를 반환.

 

해시 테이블

unordered_set

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 관련 인터페이스들을 제공.

unordered_multiset

multiset의 해시 테이블 버전. <unordered_set>헤더에 정의되어 있으며 템플릿 파라미터는 <unordered_set>과 동일하다.

multiset의 인터페이스 + HashTable 관련 인터페이스들을 제공.

 

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관련 인터페이스 제공.

unordered_multimap

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