STL - 연관 컨테이너(associate container)

📒 STL - 연관 컨테이너(associate container)

📌 연관 컨테이너란?

• pair<key, value>처럼 관련 있는 데이터를 하나의 쌍으로 저장하는 컨테이너
• 요소들에 대한 빠른 접근을 제공한다.
• 요소가 삽입되는 위치를 지정할 수 없다.
• 균형 이진 탐색 트리(balanced binary search tree)나 해시 테이블(hash table)을 이용하여 구현한다.
• 정해진 기준으로 정렬하며 데이터를 저장한다.
• key를 기준으로 트리구조로 이루어져 있기 때문에 key는 수정할 수 없다.
• map, multimap, set, multiset이 있다.
  
  

📌 map

• key와 value 값이 한 쌍으로 구성되어 저장된다.
• key 값 중복을 허용하지 않는다.
• 요소에 대한 빠른 접근을 제공한다.

// C++

#include <iostream>
#include <map>

using std::cout;
using std::endl;
using std::map;

int main()
{
	map<int, std::string> m;
	m[1] = "a";
    
	// 없는 데이터를 조회하면 value의 default 생성자를 호출해서 값을 넣어준다.
	cout << m[2] << endl;
	cout << "m.size : " << m.size() << endl; // 값을 하나만 넣었지만 사이즈는 2.

	// [1]에 a로 덮어씌워진다.
	m[1] = "b";
	m[1] = "a";
	cout << "m[1] : " << m[1] << endl;

	// m[1]에 이미 값이 있으면 삽입하지 않는다.
	m.insert({ 1, "c" });
	cout << "m[1] : " << m[1] << endl;

	// 타입 추론으로 간결화.
	auto [iter, success] = m.insert({ 1, "10" }); // { key, value}
	cout << std::boolalpha;
	cout << "success : " << success << endl; // 삽입 결과
	cout << "key : " << iter->first << endl; // 원래 있던 데이터의 키
	cout << "value : " << iter->second << endl; // 원래 있던 데이터의 값
}

Output:

m.size : 2
m[1] : a
m[1] : a
success : false
key : 1
value : a

• 없는 데이터 조회 시, value의 default 생성자를 호출하여 값을 넣어준다.
  
  

📌 multimap

• map의 특성을 갖지만, key 값의 중복을 허용한다.
• key의 중복을 허용하기 때문에 하나의 키에 여러 값이 연결될 수 있다.
• key를 기준으로만 정렬되며 key에 있는 값들은 정렬되지 않는다.

// C++

#include <iostream>
#include <map>

using std::cout;
using std::endl;
using std::multimap;

int main()
{
	cout << std::boolalpha;
	multimap<int, std::string> mm{
		{2, "10"},
		{1, "30"},
		{1, "20"},
		{1, "30"},
	};
    
    // 해당 키의 lower_bound()와 upper_bound()를 반환한다.
	auto [lower, upper] = mm.equal_range(1);
	cout << "key가 1인 데이터의 개수 : " << std::distance(lower, upper) << endl;
}

Output:
key가 1인 데이터의 개수 : 3

 

📌 set

• 저장하는 데이터 자체를 키로 사용한다.
• 오름차순으로 정렬된 위치에 요소를 삽입하므로 검색 속도가 빠르다.
• 키의 중복을 허용하지 않는다.

// C++

#include <iostream>
#include <set>

using std::cout;
using std::endl;
using std::set;

int main()
{
	set<int> s{
		1,2,3,4
	};

	// 첨자 연산 불가.
	//s[1] = 1;

	// 데이터 삽입 성공 시 실행
	if (auto [iter, success] = s.insert(5); success)
	{
		cout << std::boolalpha;
		cout << success << endl; // 성공 여부
		cout << *iter << endl; // 삽입된 주소 역참조
	}
}

Output:
true
5

 

📌 multiset

• set의 특성을 갖지만, 키의 중복을 허용한다.

// C++

#include <iostream>
#include <set>

using std::cout;
using std::endl;
using std::set;

int main()
{
	std::multiset<int> ms
	{
		1,1,3,10,10,3
	};
	
	// 정렬되어 출력
	for (const auto& num : ms)
	{
		cout << num << endl;
	}
	cout << endl;

	std::set<int, std::less<int>> s{ 3,10,-1 }; // 오름차순
	cout << "오름차순 : " << endl;
    
	for (const auto& num : s)
	{
		cout << num << endl;
	}
	cout << endl;

	std::set<int, std::greater<int>> s1{ 3,10,-1 }; // 내림차순
	cout << "내림차순 : " << endl;
    
	for (const auto& num : s1)
	{
		cout << num << endl;
	}
}

Output:
1
1
3
3
10
10

오름차순 :
-1
3
10

내림차순 :
10
3
-1