Map

각 노드가 key와 value의 쌍으로 이루어진 트리구조이며 중복을 허용하지 않는다.
#inlude <map> 필요
std::map<<keytype>, <valuetype>> m

호출

map[key]의 형태로 value를 호출할 수 있지만
const로 선언된 map의 경우 호출이 불가하다.

map<int, string> m0;
m0[1] = "10"
const map<int, string> m1;
// m1[1] = "10" error

선언

std::map<int, string> m{
	{2, "1"},
    std::pair<int, string>(3, "2"),
    std::make_pair(1, "3")
};

Pair

2개의 객체를 하나의 객체로 취급할 수 있게 묶어주는 클래스
std::pair<first_type, second_type> p

실사용할 때에는 한가지 방법만 사용하여 일관되게 선언하는것이 좋다.

예제

std::map<int, string> m{
	{2, "1"},
    std::pair<int, string>(3, "2"),
    std::make_pair(1, "3")
};
for (const std::pair<int, string>& pair : m1)
	cout << pair.first << " : " << pair.second << endl;

for (auto& pair : m1)
	pair.second = "aaa";

for (auto& pair : m1)
	cout << pair.first << " : " << pair.second << endl;
    
for (map<int, string>::iterator iter = m1.begin(); iter != m1.end(); iter++)
	iter->second = "bbb";

for (auto iter = m1.begin(); iter != m1.end(); iter++)
	cout << iter->first << " : " << iter->second << endl;

실행 결과

1 : 3
2 : 1
3 : 2
1 : aaa
2 : aaa
3 : aaa
1 : bbb
2 : bbb
3 : bbb

실행결과를 보아 알 수 있듯이 map은 key값이 오름차순으로 정렬되고 pair를 이용해 참조할 수 있음.
또한 출력시에는 const를 붙여주어야 하기 때문에 auto를 통한 type추론을 사용하는것이 좋다.

삽입

앞서 보인 예제에서 사용했듯이
pair와 iterator를 이용한 삽입도 가능하지만
const map이 아닌 경우에 map[0] = "10"과 같은 형태의 첨자연산을 통한 삽입이 가능하다.

insert

map.insert({key, value})
원하는 key에 value를 삽입할 수 있다.
하지만 map은 key의 중복이 허용되지 않기에 이미 key가 할당되어 있다면 삽입이 일어나지 않는다.

erase

map.erase(key)
말 그대로 key를 지운다.

예제

cout << boolalpha;

map<int, string> m{ {1,"1"}, {2, "2"} };
m[3] = "10";
cout << m[3] << endl;

pair<map<int, string>::iterator, bool> result = m1.insert({ 3, "50" });
cout << result.second << endl;
cout << result.first->first << " : " << result.first->second << endl;

m.erase(3);

auto [iter, success] = m.insert({3, "20"});
cout << success << endl;
cout << iter->first << " : " << iter->second << endl;

실행 결과

10
false
3 : 10
true
4 : 20

첨자연산을 통해 key:3에 10의 value를 넣었고
이미 key:3에는 value가 할당되어 있기 때문에 삽입이 실패하여 false가 출력되고
기존의 key:3의 value인 10이 출력된다.

key:3이 지워졌기 때문에 삽입이 성공하여 true가 출력되며 3의 value인 20이 출력된다.

auto [변수1, 변수2]

C++ 17이상 부터 사용가능하며 type추론을 통해 변수1에 iterator클래스, 변수2를 bool type을 선언한다.

for (auto& [key, value] : m1)
	value = "dfdfdf";

for (auto [key, value] : m1)
	cout << key << " : " << value << endl;

와 같은 형태로 사용가능

탐색

map.count(key)
key의 수를 센다.
map에서는 중복이 허용되지 않기때문에 유무를 판단
map.find(key)
key값을 찾아 호출한다.

예제

map<int, string> m{ {1, "1"}, {2, "2"}, {3, "3"} };
cout << m.count(1) << endl;
cout << m.count(10) << endl;

map<int, string>::iterator iter0 = m.find(3);
if (iter0 != m.end())
	cout << iter0->first << " : " << iter0->second << endl;
else
	cout << "nothing" << endl;
    
if (auto iter = m.find(10); iter != m.end())
	cout << iter->second << endl;
else
	cout << "nothing" << endl;

실행 결과

1
0
3 : 3
nothing

key:10은 없기 때문에 count는 0을 반환한다.

Multimap

#include <multimap>
std::multimap<keytype, valuetype> mm

멀티 맵은 key의 중복을 허용한다.
key와 value가 1대1 대응이 안되기 때문에 mm[0]와 같은 첨자연산을 허용하지 않는다.

그 외에는 map과 동일한 구조를 가진다.

std::multimap<int, string> mm{
	{2, "10"},
	{1, "30"},
	{1, "10"},
	{1, "30"},
};

cout << mm.count(1) << endl;

for (auto [key, value] : mm)
	cout << key << " : " << value << endl;

// mm[1] 1 : 1 대응이 안되기 때문에 첨자연산이 안된다.

auto result = mm.insert({ 1, "100" });
cout << result->first << " : " << result->second << endl;

실행 결과

3
1 : 30
1 : 10
1 : 30
2 : 10
1 : 100

탐색

mm.find(key)를 사용하여 특정 key의 value를 탐색할 수 있다.
하지만 key의 값이 여러개라면 가장 먼저 찾은 key 하나만 반환하기 때문에 여러개의 value를 가진 key는 전부 탐색하지 못한다.

upper_bound, lower_bound

mm.lower_boud(<key>)
key가 이루는 pair의 첫번째를 가리킨다.
mm.upper_boud(<key>)
key가 이루는 pair의 마지막의 다음을 가리킨다.

예제

if (auto iter = mm.find(1); iter != mm.end())
	cout << iter->second << endl;
// 처음 찾은 한가지 값만 나온다

auto lower = mm.lower_bound(1);
auto upper = mm.upper_bound(1);

for (auto iter = lower; iter != upper; iter++)
	cout << iter->second << endl;

cout << upper->first << endl;

실행 결과

30
30
10
30
100
2

upper는 마지막의 다음을 가리킨다.
즉, 마지막의 upper->first가 2인것을 보면 알 수 있듯이
여기서 upper는 {2, "10"}을 가리키고 있다.