Certi Pro 취득을 위해 꼭 알아야 할 STL Container : Associative

저번 포스팅에서는 STL에 정의된 자료구조 중 Sequence Contatiner에 대해 알아보았다.

Sequence Container : Certi Pro 취득을 위해 꼭 알아야 할 STL Container : Sequence

 

이번 포스팅에서는 Associative Container에 대해 알아보자.

 

① set

set은 Red-Black Tree(Self Balancing Binary Search Tree)로 구현된, 우선순위가 존재하는 자료구조이다.

프로 시험에서는 priority_queue와 비교하여 자주 사용되는데, 우선순위가 존재하는 자료구조를 저장하되 특정 위치의 자료구조의 값을 수정해야 할 때 주로 set을 사용했다. priority_queue처럼 우선순위에 따라 정렬이 되면서, 특정 위치의 원소를 삭제할 수 있는 erase 메서드가 제공되기 때문이다.

set 자료구조는 key type 하나를 가지며 모든 검색은 key를 활용하여 진행된다. 등록된 element의 key값은 변경이 불가능하기 때문에, 필요하다면 erase 후 다시 insert 하며, 이것이 위에서 언급한 "특정 위치의 자료구조의 값을 수정할 때" 사용되는 이유이자 수정하는 방법이다.

 

set의 자료구조

set은 이진 탐색 트리의 구조이기 때문에 자료의 탐색, 삽입, 삭제 모두 O(logn)에 가능하다.

 

	Average	Worst Case
space	O(n)	O(n)
search	O(logn)	O(logn)
insert	O(logn)	O(logn)
delete	O(logn)	O(logn)

 

[Set 주요 문법]

set<T> s
set<T, compare> s // compare에 사용자 정의 정렬 함수를 넣어서 사용한다.

iterator s.begin(), s.end()
reverse_iterator s.rbegin(), s.rend()

bool s.empty()
void s.clear()

size_t s.size()
size_t s.count(x) // x의 개수 반환 (1 or 0)

iterator s.find(x)
iterator s.lower_bound(x) // x보다 크거나 같은 가장 작은 값

pair<iterator, bool> s.insert(x) // 등록된 iterator, 성공 여부 반환
void s.insert(first, last)

iterator s.erase(pos)
iterator s.erase(first, last) // 마지막 지워진 element의 다음 iterator 반환
bool s.erase(x) // 성공 여부 반환

set의 메서드 중에 lower_bound는 특정 값보다 크거나 같은 가장 작은 값을 반환하는 메서드로, 시험에 대비하여 알아두면 좋고, insert 메서드에서 <iterator, 성공 여부>를 pair로 반환한다는 사실을 기억 두어야 한다. 또한 erase의 경우 지워진 element의 다음 iterator를 반환한다.

시험에서 set을 사용할 때 가장 주의해야 할 점이, 데이터를 직접 수정하면 정렬 구조가 깨지기 때문에 반드시 삭제후 삽입해야 한다는 점이다.

 

[Set 사용 예제]

Compare 기준 : default = less<int>, 오름차순

set<int> s;
for (int i = 5; i > 0; i--) s.insert(i);

for (auto x : s) cout << x << ' '; // 1 2 3 4 5
for (auto it = s.begin(); it != s.end(); ++it) cout << *it << ' '; // 1 2 3 4 5
for (auto it = s.rbegin(); it != s.rend(); ++it) cout << *it << ' '; // 5 4 3 2 1

s.empty(); // 0
s.size(); // 5
s.count(1); // 1
s.count(0); // 0

auto ret = s.find(1); // 1 검색, ret = 값 1의 iterator
auto ret = s.insert(6);
// 6 등록, ret.first = 등록된 iterator, ret.second = 1 (등록 여부)
auto ret = s.insert(1).first; // 1 등록, ret = 등록된 iterator
auto ret = s.insert(1).second; // 1 등록, ret = 0 (등록 여부)

auto ret = s.erase(2); // 2 삭제, ret = 1 (삭제 여부)
auto ret = s.erase(2); // 2 삭제, ret = 0 (삭제 여부)

auto ret = s.erase(s.begin());
// 맨 앞 element 삭제, ret = 삭제된 element의 다음 iterator
auto ret = s.erase(--s.end());
// 맨 뒤 element 삭제, ret = 삭제된 element의 다음 iterator

 

※ Compare 설정

이전 포스팅에서도 여러 번 언급한 적이 있는데, 사용자가 지정한 Compare함수를 설정할 때 가장 기본적인 형태가 function object 형태이다. set에서도 <T, compare>의 형식으로 직접 정의한 방식으로 정렬을 수행할 수 있다.

 

1) pre-defined function object : less<T>, greater<T>
    ex) greater<T>, 내림차순

set<int, greater<int>> s {1, 2, 3, 4, 5};
for (auto x : s) cout << x << ' '; // 5 4 3 2 1

 

2) user-defined function object

    ex) 절댓값 오름차순

struct AbsComp{
	bool operator()(const int &a, const int &b) const {
    	return abs(a) < abs(b);
    }
};

set<int, AbsComp> s{ -5, -3, 1, 4, 6 }
for (auto x : s) cout << x << ' '; // 1 -3 4 -5 6

 

[custom type의 compare 설정]

• 기본 type과 동일하지만 <, > operator를 사용하려면 해당 operator의 정의가 필요하다. ☞ operator overloading

1) Operator overloading : default가 less<Data>이므로 operator < overloading 필요

struct Data {
    int a, b, c;
    bool operator<(const Data& r) const {
    	return a < r.a;
    }
};

set<Data> s; // == set<Data, less<Data>> s;

 

2) function object

struct Data { int a, b, c };
struct Comp {
	bool operator()(const Data&l, const Data&r) const {
    	return a < r.a;
    }
};

set<Data, Comp> s;

 

 

② map

map 역시 set과 마찬가지로 Red-Black Tree(Self Balancing Binary Search Tree)로 구현된, 우선순위가 존재하는 자료구조이다. set과 다른 점은 key type에 대한 value type이 존재한다는 것이다. set과 마찬가지로 모든 검색을 key를 활용해서만 진행되며 등록된 element의 key값은 변경이 불가능하므로 필요할 경우 erase 후 재 insert를 해야 하지만, map의 value는 변경이 가능하다.

map의 자료구조

map 역시 key값 insert, erase, search에 대해 set과 같은 시간복잡도를 가진다.

 

[Map 주요 문법]

map<T, U> m
map<T, U, Compare<T>> m

U m[T x] // x가 등록되지 않은 상황이면 default 값 0으로 등록

iterator m.begin(), m.end()
iterator m.rbegin(), m.rend()

bool m.empty()
size_t m.size() // size_t : unsigned long long
void m.clear()
size_t m.count(T x)

iterator m.find(T x)
iterator m.lower_bound(T x)

pair<iterator, bool> m.insert({ T x, U y })
// first (등록된 iterator), second (성공 여부 반환)
void m.insert(iterator first, iterator last)

iterator m.erase(iterator pos)
iterator m.erase(iterator first, iterator last)
// 마지막 지워진 element 바로 다음 iterator 반환
bool m.erase(T x) // 성공 여부 반환

key값에 대한 value가 추가된 것 외에는 set과 동일하며 compare 기준은 무조건 key 값이다.

 

[map 사용 예제]

map<int, int> m;

for (int i = 5; i > 0; i--) m.insert({ i, 0 });

for (auto x : m) cout << x.first << ',' << x.second;
// (1, 0), (2, 0), (3, 0), (4, 0), (5, 0)
for (auto it = m.begin(); it != m.end(); ++it) {
	cout << it->first << ',' << it->second;
} // (1, 0), (2, 0), (3, 0), (4, 0), (5, 0)

for (auto it = m.rbegin(); it != m.rend(); ++it) {
	cout << it->first << ',' << it->second;
} // (5, 0), (4, 0), (3, 0), (2, 0), (1, 0)

m[1] = 3; // (1, 3), (2, 0), (3, 0), (4, 0), (5, 0)
m[6]; // index 접근 시, 등록되어 있지 않은 key 값이면 default 값 0으로 insert : (6, 0)
m[7]++; // key 값 7이 등록되어 있지 않으므로 value 0으로 insert 후 value 1 증가 : (7, 1)
// m = (1, 3), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0), (7, 1)

 

 

다음 포스팅에서 Unordered Associative Container를 다룰 때 나오겠지만, (set, map) vs (unordered_set, unordered_map)과 (set, unordered_set) vs (map, unordered_map)을 잘 알아두어야 한다.

 

다음 글 : Certi Pro 취득을 위해 꼭 알아야 할 STL Container : Unordered Associative