[c++]Associate container

학부생이 공부 기록 차원에서 작성한 글입니다. 언제나 지적은 환영입니다.

 

Associate container

key - value 를 통해서 서로 관계있는 값을 묶어 저장하는 컨테이너를 말한다. key 값을 통해서 각각의 record 에 빠르게 접근이 가능하지만 specific 한 rule 에 의해 sorting 되기 때문에 insert 할 key 값의 위치를 지정할 수 없다. balanced binary search tree 나 hash function 을 사용하여 구현된다고 한다.

 

std::set

balanced binary tree 로 구현되어 있는 정렬된 집합을 포함하는 associate container 이다. 

중복되는 요소를 허용하지 않는다. 오름차순으로 정렬된 위치에 원소를 삽입하기 때문에 search 속도가 매우 빨라서

데이터의 존재 유무를 파악하는 데에 효율적인 컨테이너이다. 

void main()
{
	set<int> s;
	s.insert(5);
	s.insert(4);
	s.insert(3);
	s.insert(2);
	s.insert(1); // insert 를 통해서 자동적으로 정렬된다.

	cout << "s 의 size = " << s.size() << '\n';
	
	// set s 의 모든 원소를 출력하기
	for (set<int>::iterator iter = s.begin(); iter != s.end(); iter++)
		cout << *iter << ' ';
	cout << '\n';

	// set 에서 특정 원소를 찾기
	std::set<int>::iterator iter = s.find(3);
	if (iter != s.end())
		cout << "found \n";
	else
		cout << "something wrong \n";

	// 특정 원소를 삭제하기
	s.erase(3);
	for (set<int>::iterator iter = s.begin(); iter != s.end(); iter++)
		cout << *iter << ' ';
	cout << '\n';

	
}

std::multiset

multiset 은 set 과는 달리 key 를 중복되게 컨테이너에 저장할 수 있다. 외에는 set 과 동일하다. 그러므로 set 을 사용하고자 하는데 key 의 중복이 필요한 상황이라면 multiset 을 활용할 수 있다. multiset 은 키의 중복이 허용되기 때문에 같은 값을 여러개 저장할 수 있다.

 

void main()
{
	multiset<int> s;
	s.insert(5);
	s.insert(4);
	s.insert(3);
	s.insert(2);
	s.insert(1); // insert 를 통해서 자동적으로 정렬된다.

	s.insert(4); // 중복된 요소 삽입

	cout << "s 의 size = " << s.size() << '\n';
	
	// set s 의 모든 원소를 출력하기
	for (set<int>::iterator iter = s.begin(); iter != s.end(); iter++)
		cout << *iter << ' ';
	cout << '\n';

	// set 에서 특정 원소를 찾기
	std::set<int>::iterator iter = s.find(3);
	if (iter != s.end())
		cout << "found \n";
	else
		cout << "something wrong \n";

	// 특정 원소를 삭제하기
	s.erase(3);
	for (set<int>::iterator iter = s.begin(); iter != s.end(); iter++)
		cout << *iter << ' ';
	cout << '\n';
}

std::map & std::multimap

map 은 key - value 를 pair 로 가지는 associate container 이다. set 은 원소의 값으로 key 하나만을 저장할 수 있지만, map 은 <key , value> 와 같이 pair 로 저장하며 중복으로 저장되지 않는다. 그러므로 하나의 key 에는 하나의 value 만 짝지어 있다. 

void main()
{
	map<string, int> m;

	m.insert(make_pair("first", 1));
	m.insert(pair<string, int>("second", 2));
	m["three"] = 3;

	
	for (map<string, int>::iterator iter = m.begin(); iter != m.end(); iter++)
		cout << iter->first << ' ' << iter->second << '\n';
}

std::multimap 의 경우도 key 의 중복을 허용한다는 점 외에는 map 과 동일하다.

 

unordered associate container

unordered associated conatiner 은 정렬되지 않고 랜덤하게 저장되며, hash function 기반으로 동작한다는 것이 차이점이다. 이에따라 원소의 추가, 삭제, 검색 속도가 O(1) 으로 동작하기 때문에 굉장히 빠르다고 할 수 있다. 

 

---

References

1. https://blog.itsforme.dev/stl/

2. https://ya-ya.tistory.com/91#:~:text=1.%20pair%20%ED%81%B4%EB%9E%98%EC%8A%A4,%EB%95%8C%20%EC%82%AC%EC%9A%A9%ED%95%98%EB%A9%B4%20%ED%8E%B8%EB%A6%AC%ED%95%A9%EB%8B%88%EB%8B%A4.

3. https://blankspace-dev.tistory.com/347

4. https://min-zero.tistory.com/79