template<
    class Key,
    class Ty,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, Ty>>
> class map;

   map은 key와 value 쌍을 하나의 요소로 저장하는 자료구조를 구현한 컨테이너이다. <map> 헤더에 구현되어 있다. key를 통해서 컨테이너 내부를 탐색해 value를 얻을 수 있다. set 과 유사하게 key에 대해 이진탐색트리로 구현되어 있다. 대부분의 연산은 O(lgN)으로 이루어진다.


 

1. 사용

   보통 map은 특정한 데이터(value)를 key에 따라 보관하고 key를 이용해서 꺼내 쓰고 싶을 때 사용한다. 예를 들면, id가 있고 id 마다 어떤 유저 정보가 있을 때 id : info 쌍으로 map을 생성할 수 있다. 기본적으로 균형 이진 탐색 트리를 사용하기 때문에, key에 따른 정렬된 순서를 유지한다.


생성

다양한 방법을 이용해 생성 가능하다. 빈 컨테이너를 생성하거나, 미리 요소가 추가된 컨테이너를 생성할 수 있다. 각 생성자들은 Allocator를 추가적으로 받을 수 있다. 모든 삽입 연산은 O(lgN)이기 때문에 N개의 요소를 동시에 생성하는 생성자는 O(NlgN)의 실행시간을 갖는다.

  1. 기본 생성자
  2. initializer_list를 전달하는 생성자
  3. 시작과 끝의 이터레이터를 전달하는 생성자
  4. 복사 생성자
  5. 이동 생성자
// 1.	기본 생성자
//		아무것도 할당되지 않은 상태로 초기화.
map<string, int> m1;

// 2.	initializer_list
map<string, int> m2 = {			// 용직 - 준혁 - 효빈
	{"효빈", 4},
	{"준혁", 10},
	{"용직", 1}
};		
map<string, string> m2_2{		// bdd - chovy - faker
	{"faker", "이상혁"},
	{"chovy", "정지훈"},
	{"bdd", "곽보성"}
};
map<int, int> m2_3({
	{1,1}, {2,20}, {3, 111}		// 1 - 2 - 3
});

// 3.	iterator
map<string, int> m3(m2.begin(), m2.end());	// 용직 - 준혁 - 효빈

// 4.	copy
map<string, int> m4(m3);					// 용직 - 준혁 - 효빈

// 5. move
map<string, int> m5(move(m4));				// 용직 - 준혁 - 효빈

   추가적으로 compare 함수를 전달할 수 있다. compare는 컨테이너가 내부에서 요소간 비교를 수행할 때, 그 연산을 수행하는 함수이다. 이는 삽입, 검색 등 다양한 곳에 이용된다. comp를 전달하지 않은 set은 기본적으로 오름차순 관계를 갖는다. std에서는 기본적인 compare 함수를 제공하는데, 오름차순으로 정렬되는 std::less<Ty>()와 내림차순으로 정렬되는 std::greater<Ty>()가 있다. compare를 전달하지 않으면 기본적으로 std::less<>가 전달된다.

// 6.	comp 전달
//		내림차순으로 정렬됨.
map<string, int> m6(greater<string>());
map<string, int, greater<string>> m6_2;

// 7.	comp with initializer_limt
map<string, int, greater<string>> m7({							// 효빈 - 준혁 - 용직
	{"효빈", 4},
	{"준혁", 10},
	{"용직", 1} }
);

// 8.	iterator
map<string, int, greater<string>> m8(m7.begin(), m7.end());		// 효빈 - 준혁 - 용직

// 9.	copy
map<string, int, greater<string>> m9(m7);						// 효빈 - 준혁 - 용직

// 10. move
map<string, int, greater<string>> m10(move(m9));				// 효빈 - 준혁 - 용직

greater와 less는 괄호 연산자가 로버로딩된 구조체이다. 필요에 따라서 직접 정의할 수도 있다.

template <class _Ty = void>
struct Greater {
	bool operator()(_Ty& _Left, _Ty& _Right) {
		return _Left > _Right;
	}
};

template <class _Ty = void>
struct Less {
	bool operator()(_Ty& _Left, _Ty& _Right) {
		return _Left < _Right;
	}
};

이를 구조체가 아닌 일반 함수로 만들어 사용할 수도 있다.

template<typename Ty>
bool greaterFunc(Ty& left, Ty& right) {
	return left > right;
}

// 템플릿을 사용하지 않는 경우
bool lessIntFunc(int& left, int& right) {
	return left < right;
}

접근

   []연산자와 at()을 통해서 접근이 가능하다. 단, 이 연산자에 입력 값은 인덱스가 아니라, key 값이다. map은 요소를 key 통해서 접근한다. 트리에서 key값을 탐색해야하기 때문에 O(lgN) 의 실행시간이 필요하다. 그 외의 접근 방법은 이터레이터나 조회(Lookup) 메서드를 사용하는 것 뿐이다.

map<string, string> m{
		{"faker", "이상혁"},
		{"chovy", "정지훈"},
		{"bdd", "곽보성"}
};

cout << m["faker"] << endl;		// 이상혁
cout << m["chovy"] << endl;		// 정지훈
cout << m.at("bdd") << endl;	// 곽보성

   접근 메서드를 활용하면, 컨테이너에 존재하지 않은 key로 접근하는 경우, 해당 키로 새로운 요소를 생성해 저장한다. key에 대응하는 value는 타입의 zero 값으로 생성된다.

cout << m["showmaker"] << endl;		// 빈 문자열이 생성됨!

m["scout"] = "이예찬";			//   bdd   -   chovy  -  faker  -  scout   - showmaker
								// "곽보성" - "정지훈" - "이상혁" - "이예찬" - ""

이터레이터

   --와 ++ 연산자를 지원한다. 역참조는 pair<key, value>를 반환한다. key는 const로 수정할 수 없다.

map<string, string> m{
{"faker", "이상혁"},
{"chovy", "정지훈"},
{"bdd", "곽보성"}
};
auto iter = m.begin();
cout << iter->first << ", " << iter->second << endl;	// "bdd", "곽보성"
// iter->first = "ddb"		// error
iter->second = "비디디";		// "bdd", "비디디"

용량

  • size() 저장된 요소의 개수를 반환
  • empty() 컨테이너가 비어있으면 true
  • max_size() 저장 가능한 컨테이너 수 반환

수정

insert()와 emplace()로 삽입할 수 있다. erase()로 요소를 삭제한다. key의 대소 관계에 따라서 위치가 정해지기 때문에 직접 위치를 지정할 수는 없다. 이미 존재하는 key의 value를 수정하고 싶다면 삽입 대신 insert_assign()을 사용한다.

map<int, int> m{
	{1,1}, {2,2}
};

m.insert({ 3,3 });			// {1,1}, {2,2}, {3,3}
m.emplace(4,4);				// {1,1}, {2,2}, {3,3}, {4,4}

// 수정 실패
m.insert({ 3,4 });			// {1,1}, {2,2}, {3,3}, {4,4}

// 지우고 다시 삽입하는 방식으로 수정
m.erase(3);					// {1,1}, {2,2}, {4,4}
m.insert({ 3,4 });			// {1,1}, {2,2}, {3,4}, {4,4}

// 삽입 혹은 수정
m.insert_or_assign(3, 3);	// {1,1}, {2,2}, {3,3}, {4,4}
m.insert_or_assign(5, 5);	// {1,1}, {2,2}, {3,3}, {4,4}, {5,5}

   merge()를 이용해서 <key, value> 타입이 같은 두 map을 하나로 합칠 수 있다. 매개변수로 들어오는 set은 복사가 아니라 이동된다. clear()함수로 컨테이너를 비울 수 있다.

map<int, int> m1{ {1,1}, {3,3} };
map<int, int> m2{ {2,2}, {4,4} };
m1.merge(m2);	// {1,1} {2,2} {3,3} {4,4}
m1.clear();		// empty

   extract는 set에서 요소를 제거하면서 제거된 요소의 tree_node를 반환한다. 반환된 node에는 요소의 값은 물론 기존 연결되어 있었던 부모, 자식에게도 접근할 수 있다.

//        4
//     2     5
//   1  3
map<int, int> m{ {1,1},{2,2},{3,3},{4,4},{5,5} };
auto node = m.extract(1);
auto v = node._Getptr()->_Parent;

cout << node.mapped() << endl;				// 1
cout << v->_Myval.second << endl;			// 2
cout << v->_Left->_Myval.second << endl;	// 스레기 값(1 이 tree에서 삭제됨.)
cout << v->_Right->_Myval.second << endl;	// 3

조회

   map의 핵심 기능은 트리에서 key를 찾는 것이다. 이와 관련된 다양한 연산이 존재한다.

  • count(key) - 보관된 key의 개수를 반환한다.
  • find(key) - key가 존재하면 key의 이터레이터를, 아니면 past-the-end 이터레이터를 반환한다.
  • contains(key) - key가 존재하면 true를 반환한다.
  • equal_range(key) - key값이 존재하는 범위에 대한 시작, 끝 이터레이터를 반환한다.
  • lower_bound(key) - key 값이나 없다면 key에 가장 가까운 오른쪽 값을 반환한다.
  • upper_bound(key) - key과 가장 가까운 오른쪽 값을 반환한다.

   lower_bound()와 upper_bound()는 past-the-end를 반환할 수 있다는 점에서 항상 주의해야 한다. 오름차순을 기준으로 lower_bound는 v가 존재하면 v를 아니면 v보다 큰 수 중 가장 작은 수를 반환한다. upper_bound는 항상 v보다 크면서 가장 작은 수를 반환한다.

map<int, int> m{ {1,1},{1,2},{2,3},{2,4},{2,5},{3,6} };
				// {1,1} {2,3} {3,6}; (중복키 제거됨)

m.count(1);		// 1

auto iter = m.find(6);		// past-the-end
if (iter == m.end()) {
	cout << "end 이터레이터" << endl;
}

if (m.contains(3)) {
	cout << "키가 3인 원소가 존재함" << endl;
}

cout << "i\tlower\tupper" << endl;
for (int i = 0; i < 5; i++) {
	cout << i << '\t';
	auto lower = m.lower_bound(i);
	if (lower == m.end()) {
		cout << "end\t";
	}
	else {
		cout << lower->first << "," << lower->second << '\t';
	}

	auto upper = m.upper_bound(i);
	if (upper == m.end()) {
		cout << "end" << endl;
	}
	else {
		cout << upper->first << "," << upper->second << endl;
	}
}

end 이터레이터
키가 3인 원소가 존재함
i       lower   upper
0       1,1     1,1
1       1,1     2,3
2       2,3     3,6
3       3,6     end
4       end     end


 

2. multimap

   multimap은 중복을 허용하는 map이다. 중복된 키가 동시에 컨테이너에 존재할 수 있다. 중복 허용은 많은 메서드의 결과를 달라지게 만든다. multiset은 <set> 헤더에 구현되어 있다.

   우선 count()를 더 의미있게 사용할 수 있다. map에서는 0아니면 1이었기 때문에 find나 contains를 사용하는 것과 다를게 없었지만, multiset에서는 같은 요소가 여러 번 저장될 수 있기 때문에 보관된 요소의 수를 출력한다.
  equal_range()역시 map에 비해서 의미있게 사용할 수 있다. 해당 메서드를 사용해서 중복되는 모든 요소의 이터레이터를 얻을 수 있다.

multimap<int, char> mm{ {1,'A'},{2,'B'},{2,'C'}, {2,'D'}, {3,'E'} };

cout << mm.count(2) << endl;	// 2

auto [begin, end] = mm.equal_range(2);
for (auto iter = begin; iter != end; iter++) {
	cout << iter->first << ", " << iter->second << endl;
}

3
2, B
2, C
2, D

   find()의 경우에는 가장 왼쪽에 있는 요소의 이터레이터를 반환한다. lower_bound와 upper_bound 역시 연산을 만족하는 가장 왼편의 값을 반환한다.

for (auto iter = mm.find(2); iter != mm.end(); iter++) {
	cout << iter->first << ", " << iter->second << endl;

}
cout << endl;

// 가장 왼편의 2를 선택함
for (auto iter = mm.lower_bound(2); iter != mm.end(); iter++) {
	cout << iter->first << ", " << iter->second << endl;

}
cout << endl;

// 가장 왼편의 3을 선택함.
for (auto iter = mm.upper_bound(2); iter != mm.end(); iter++) {
	cout << iter->first << ", " << iter->second << endl;
}

2, B
2, C
2, D
3, E

2, B
2, C
2, D
3, E

3, E