C++ STL ordered associative container(set, map)

intro

associative란, "연관 있는" 이런 의미이다.

그렇다면, ordered하고 associative 한 객체들은 어떻게 관리할 수 있을까?

이는 linear한 구조보다는 binary tree 구조로 관리하는 게, 삽입, 삭제, 검색의 시간복잡도면에서 유리하다.

binary tree는 linear한 구조와 어떻게 다르길래?

 

binary tree

binary tree는 최대 2개 이하의 자식 노드를 가지는 tree를 말한다.

parent node와 child node 간의 연관관계를 가지고 tree를 구성하면, 삽입, 삭제, 검색을 logN의 시간복잡도로 해결할 수 있다. (N은 node의 개수를 의미한다)

 

binary_tree.jpg (600×351) (tutorialspoint.com)

 

그러나, binary tree가 항상 위의 그림과 같이, 좌-우 balance가 맞는 tree가 생성되지는 않는다.

그렇다면, 항상 balance 맞는 tree를 구현할 수 없을까? 그래서 등장한 것이 red-black tree이다.

이번 posting에서 다루고자 하는, set, map 또한 red-black tree 구조이다.

 

set

set은 key값을 가지는 node로 이루어진 red-black tree이다. node 간의 sort는 key값의 비교함수로 결정된다. (디폴트는 Key값에 대한 오름차순 정렬이다.)

set template을 보면 다음과 같다.

template <class _Kty, class _Pr = less<_Kty>, class _Alloc = allocator<_Kty>>
class set : public _Tree<_Tset_traits<_Kty, _Pr, _Alloc, false>> {
    // ordered red-black tree of key values, unique keys
    ...
}

• class _Pr이 key값의 비교함수이다.
• key를 새로운 struct로 정의하는 경우, 비교함수도 재정의가 필요하다.

삽입, 삭제, 검색의 시간복잡도는 다음과 같다.

	시간복잡도
insert	O (logN)
erase	O (logN)
find	O (logN)

예제 코드

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

int main()
{
	set<int> s;
	s.insert(5);
	s.insert(3);
	s.insert(4);
	s.insert(2);
	s.insert(1);
	s.erase(1);
	s.erase(7);          // set에 없는 key값을 erase하는 경우, 0을 리턴한다.
	auto it = s.find(2); // set에 없는 key값을 find하는 경우, s.end()를 리턴한다.
	s.erase(it);
	return 0;
}

 

 

key가 2개 이상일 때는 어떻게 Set을 사용할 수 있을까?

key struct를 정의하고, struct 내부에서 < 연산자 오버로딩을 한다.

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

#define MAX_ID (10)

struct Key
{
	int id;
	int priority;
    
	// 우선순위가 클수록, 우선순위가 같다면 id가 작을수록
	bool operator<(const Key& r) const
	{
		if (priority != r.priority) return priority > r.priority;
		return id < r.id;
	}
};

int main()
{
	set<Key> s;
	s.insert({5,0});
	s.insert({3,0});

    // id 5의 우선순위가 10으로 업데이트
	s.erase({ 5,0 });
	s.insert({ 5,10 });

	return 0;
}

 

 

key는 하나인데, 비교를 key값뿐만 아니라 key와 관련된 data들과 같이 비교하려면 어떻게 해야 할까?

() 연산자 오버로딩을 한다.

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

#define MAX_ID (10)

int priorityTb[MAX_ID];

struct Comp
{
	// 우선순위가 클수록, 우선순위가 같다면 id가 작을수록
	bool operator()(const int& l, const int& r) const
	{
		if (priorityTb[l] != priorityTb[r]) return priorityTb[l] > priorityTb[r];
		return l < r;
	}
};

set<int, Comp> s;
set<int, Comp>::iterator sit[MAX_ID];

void insert(int id, int val)
{
	priorityTb[id] = val;
	sit[id] = s.insert(id).first;
}

void update(int id, int val)
{
	s.erase(sit[id]); // iterator로 지우는 경우, O(1)이다. 그러나 key로 지우는 경우, O(N*logN)이다.
	priorityTb[id] = val;
	s.insert(id);
}

int main()
{
	int id = 0;
	insert(id++, 5);
	insert(id++, 3);
	update(1, 10);   // id 1의 priority를 10으로 업데이트
	update(0, 10);   // id 0의 priority를 10으로 업데이트
	return 0;
}

 

map

set과 거의 동일하다. 다른 점은 node에 key값과 value값이 pair로 존재한다.

 

reference

Data Structure and Algorithms - Tree (tutorialspoint.com)