STL#3 연관 컨테이너 - map, unordered_map, set, multimap, multiset

이젠 시퀀셜 컨테이너 아닌 다른 방법을 알아보자.

노드기반으로 만들어지는 연관컨테이너.

벡터로 플레이어 정보를 만들어 id로 플레이어정보를 조회하고자 할때

벡터를 모두 순회하면서 찾는 id의 플레이어가 어떤것인지 대조해봐야한다.

따라서 O(n)의 시간이 걸린다.

map

map은 균형이진트리(AVL)로 만든다.

역시나 노드기반.

 부모 노드보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 배치하게 한다.

비슷한 원리로 맵을 만든다. 왼쪽 노드의 수와 오른쪽 노드의 수의 균형을 맞추기 위해 다양한 방법이 이용된다. (예를 들어 중앙값을 찾아서 맨 위로 끌어 올리는..?)

노드를 만든다면 아래와 같이 만든다.

class Node{

public: 

Node* _left;

Node* _right;

pair<int, Player*> _data;

}

데이터가 연속해서 붙어있는게 아니라 iterator로 순회해야한다. 탐색 시간 복잡도는 이진탐색을 하기 때문에 O(log n)이 걸린다. 삽입, 삭제시간도 똑같이 O(log n)이 걸린다. 정렬되어 있는 값에서 찾을때 유리하다.

#include <map>

static std::map<size_t, std::unique_ptr<WebPanel>> g_webPanels;

XEXPORT(BOOL) SetBBS(const TCHAR* szURL, INT id, INT startX, INT startY, INT width, INT height)
{
	USES_CONVERSION;

	if (!g_hWV2Ldr)
	{
		g_bCanBeDeleted = TRUE;
		return FALSE;
	}

	BOOL shouldBeActive = FALSE;
	std::unique_ptr<WebPanel> newTab = WebPanel::CreateNewWebPanel(g_hDlg, g_webViewEnvironment.get(), id, szURL, startX, startY, width, height);

	std::map<size_t, std::unique_ptr<WebPanel>>::iterator it = g_webPanels.find(id);
	if (it == g_webPanels.end())
	{
		g_webPanels.insert(std::pair<size_t, std::unique_ptr<WebPanel>>(id, std::move(newTab)));
	}
	else
	{
		g_webPanels.at(id)->m_contentController->Close();
		it->second = std::move(newTab);
	}

	return TRUE;
}

 

 

unordered_map

hash table 용도로 map을 쓰기도 하지만 unordered_map을 많이 쓰기도 한다.

이름에서도 볼 수 있듯이 map은 정렬되어있는 반면 unordered_map은 정렬되어 있지 않아 해쉬테이블로 이루어져있다. 그래서 map 보다 더 빠른 탐색을 위해 쓰인다.  map은 BST로 탐색 시간 복잡도는 O(log n)인 반면 unordered_map은 O(1)이다.

unordered_map을 사용하기 위해서는 #include< unordered_map > 을 선언해야 합니다.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main(){
    
    unordered_map<string,int> um;
    
    um["apple"] = 1;
    um["banana"] = 2;
    um["apple"]++;

    um.insert({ "melon", 4 });
    um.erase("apple"); // 키로 삭제 외에도 iterator로도 가능, 범위로도.

    // 마찬가지로 iterator로도 가능. 
    for (auto& element : um)
    {
        cout << element.first << ' ' << element.second;
    }
    
}

unordered_map은 중복된 데이터를 허용하지 않고 map에 비해 데이터가 많을 시 월등히 좋은 성능을 보이지만, key가 유사한 데이터가 많을 시 해시 충돌로 인해 성능이 떨어질 수도 있다. 즉, 알고리즘 문제에서는 괜찮지만 실무 혹은 개발 프로젝트에서 hash table 활용 시, hash bucket collison 이슈가 발생하지 않도록 하는 것에 주의를 기울여야 한다.

https://preamtree.tistory.com/20

[IT 기술면접 준비자료] 해시(Hash)와 해시충돌(Hash Collision)

 

그리고 자료의 수가 적을때 해쉬테이블을 사용하면 메모리 낭비와 검색시 오버헤드가 생기므로 많은 자료를 저장해야 할때,  검색 속도는 빨라야 할때 그리고 너무 빈번하게 자료를 삽입, 삭제하지 않을 때 적합하다.

또한 참고로 문자열 키를 사용하는 경우는 map이 unordered_map보다 탐색 성능의 우위를 점한다.

map은 Red-Black로 구현이 되어있어서 문자열 비교에 적은 비교 횟수를 필요로 하기 때문이다.

즉, 문자열의 길이가 길고 데이터의 크기가 크지 않은 경우는 map이 unordered_map보다 탐색에 유리하다.

 

set

map과 마찬가지로 이진트리로 만들어져 정렬되어 있다. 

map과의 차이는 map은 key,value를 갖는다면 그냥 데이터를 키로 사용하고자 할때는 set를 사용한다.

#include <set>

int main()
{
    // 사용법
    set<int> s;
    
    // 1. 삽입
    s.insert(10);
    s.insert(60);
    s.insert(30);
    s.insert(20);
    s.insert(90);
    s.insert(70);
    
    // 2. 삭제
    s.erase(90); 
    
    // 3. 조회
    set<int>::iterator findit = s.find(50);
    if(findit == s.end()) cout<<"실패"<<endl;
    else cout<<"성공";
    
    // 4. 순회
     for(set<int>::iterator iter=s.begin();iter!=s.end();iter++)
       cout<<*iter<<'\n'; 
       
    return 0;
}

 

mulitmap

#include <map>

int main()
{
    multimap<int,int> mm;
    
    // 삽입
    mm.insert(make_pair(1,100));
    mm.insert(make_pair(1,200));
    mm.insert(make_pair(1,300)); // 같은 키에 다른 값을 넣기가 가능하다.
    mm.insert(make_pair(2,400));
    
    //mm[1] = 500; // map과 다르게 임의 접근이 불가능하다.
    
    // 삭제
    unsigned int count = mm.erase(1); // 키를 1로 갖는 모든 데이터를 지워준다.
    
    // 찾기
    // 키로 찾은 첫번째 값만 지운다.
    /*{
    multimap<int,int>::iterator itFind = mm.find(1);
    if(itFind != mm.end())
        mm.erase(itFind);
    }*/    
    
    {
    pair<multimap<int,int>::iterator, multimap<int,int>::iterator> itPair;    
    itPair = mm.equal_range(1); // 키가 1인 데이터들의 시작부분과 마지막 다음을 순서대로 가지고있다.
    // multimap<int,int>::iterator itBegin = mm.lower_bound(1); // 위와 같은 의미이나 다른 방식.
    // multimap<int,int>::iterator itEnd = mm.upper_bound(1);
    
    for(multimap<int,int>::iterator it = itPair.first; it != itPair.second; ++i)
    //for(multimap<int,int>::iterator it = itBegin; it != itEnd; ++i) 
    {
        cout<< it->first << " " << it->second<< endl;
    }
    // 1 100
    // 1 200
    // 1 300
    // equal_range로 한번에 추출할수도 있지만 lower_bound,upper_bound를 사용할수도 있다.
    // mm.lower_bound(1)로 1이 키인 데이터의 첫번째 영역의 반복자를 얻고
    // mm.upper_bound(1)로 그 다음 키의 첫번째 데이터의 반복자를 얻어서 그 사이를 순회할 수 있다.
    }
    
    return 0;
}

map과 다르게 multimap은 같은 키에 대해 여러 값을 가질수 있는 특징이 있어 같은 키를 가진 여러 데이터를 다루는 문법이 함께한다. 그런데 자료구조가 저장되는 방식 등은 매우 비슷하다.

multiset

set이랑 같은데 같은 키 값이 여러개 들어갈 수 있는 자료구조.