map?
1. 연관 컨테이너이며 노드 기반 컨테이너
2. 특정 정렬 기준으로 원소(Key)가 자동으로 정렬된다.
3. 균형 이진트리의 장점을 가지고 있어 찾기, 삭제, 삽입의 성능 O(lgN)을 보장한다.
자주 사용하는 멤버 함수
기본적으로 연관 컨테이너 set과 똑같지만 차이점을 주자면
[] 연산자를 제공한다.
[] 연산자를 이용해서 원소(key, value)를 삽입하거나, key에 매핑된 value를 갱신할 수 있다.
아래에는 자주 사용하는 부분들을 정리했다.
| insert(pair<int,int>(key,value)) |
map에 pair 객체로 key와 value를 저장한다. |
| map[key] = value |
map에 key에 해당하는 원소가 없다면 (key, value) 저장하고
key에 해당하는 원소가 있다면 value를 갱신한다. |
| erase() |
삭제 |
| find() |
찾기 |
| lower_bound() |
key를 처음 찾는 곳의 반복자를 리턴 |
| upper_bound() |
key 다음 원소의 반복자를 리턴 |
| equal_range() |
[lower_bound(), upper_bound()) 를 pair 쌍으로 반복자를 리턴 |
연습해보기
삽입은 insert() 혹은 [] 연산자를 이용해서 삽입한다.
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<int, int> m; // (key, value) less <
// 임시 pair 객체 생성 후 저장
m.insert(pair<int, int>(5, 100));
m.insert(pair<int, int>(3, 100));
m.insert(pair<int, int>(8, 30));
m.insert(pair<int, int>(4, 40));
m.insert(pair<int, int>(1, 70));
m.insert(pair<int, int>(7, 100));
pair<int, int> pr(9, 50);
m.insert(pr);
for (auto iter = m.begin(); iter != m.end(); iter++)
cout << "(" << (*iter).first << ',' << (*iter).second << ") ";
cout << '\n';
// iterator는 -> 연산자 오버로딩되어 있으므로
// 포인터처럼 멤버를 -> 연산자로 접근이 가능
for (auto iter = m.begin(); iter != m.end(); iter++)
cout << "(" << iter->first << ',' << iter->second << ") ";
cout << '\n';
pair<map<int, int>::iterator, bool> ret;
ret = m.insert(pair<int, int>(9, 50));
if (true == ret.second)
cout << "key: " << ret.first->first << ", value: " << ret.first->second << " success\n";
else
cout << "key: " << ret.first->first << ", value: " << ret.first->second << " failure\n";
return 0;
}
(1, 70) (3, 100) (4, 40) (5, 100) (7, 100) (8, 30) (9, 50)
(1, 70) (3, 100) (4, 40) (5, 100) (7, 100) (8, 30) (9, 50)
key: 9, value : 50 failure
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<int, int> m;
m[5] = 100; // key 5, value 100 insert
m[3] = 100;
m[8] = 30;
m[4] = 40;
m[1] = 70;
m[7] = 100;
m[9] = 50;
for (auto iter = m.begin(); iter != m.end(); iter++)
cout << "(" << iter->first << "," << iter->second << ") ";
cout << '\n';
m[5] = 200; // update;
for (auto iter = m.begin(); iter != m.end(); iter++)
cout << "(" << iter->first << "," << iter->second << ") ";
cout << '\n';
return 0;
}
(1, 70) (3, 100) (4, 40) (5, 100) (7, 100) (8, 30) (9, 50)
(1, 70) (3, 100) (4, 40) (5, 200) (7, 100) (8, 30) (9, 50)
검색은 find() 연산을 이용한다.
key에 해당하는 원소가 존재한다면 그 위치의 반복자를 리턴하고 아니라면 end() 반복자를 리턴한다.
lower_bound()는 key를 처음으로 찾은 지점의 반복자를 리턴
upper_bound()는 key를 찾은 다음 원소의 반복자를 리턴
equal_range()는 [lower_bound(), upper_bound()) 를 반복자를 쌍으로 리턴한다.
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<int, int> m;
m[5] = 100;
m[3] = 100;
m[8] = 30;
m[4] = 40;
m[1] = 70;
m[7] = 100;
m[9] = 50;
for (auto iter = m.begin(); iter != m.end(); iter++)
cout << "(" << iter->first << ',' << iter->second << ") ";
cout << '\n';
// key를 기준으로 찾는다.
auto iter = m.find(5);
if (iter != m.end())
cout << "key 5에 매핑된 value: " << iter->second << '\n';
else
cout << "key 5가 없습니다.\n";
map<int, int>::iterator lower_iter = m.lower_bound(5);
map<int, int>::iterator upper_iter = m.upper_bound(5);
cout << "[lower_iter, upper_iter): ";
for (auto iter = lower_iter; iter != upper_iter; iter++)
cout << "(" << iter->first << "," << iter->second << ") ";
cout << '\n';
auto iter2 = m.equal_range(5);
cout << "[iter2.first, iter.second): ";
for (auto iter = iter2.first; iter != iter2.second; iter++)
cout << "(" << iter->first << "," << iter->second << ") ";
cout << '\n';
return 0;
}
(1, 70) (3, 100) (4, 40) (5, 100) (7, 100) (8, 30) (9, 50)
key 5에 매핑된 value : 100
[lower_iter, upper_iter): (5, 100)
[iter2.first, iter.second): (5, 100)
정렬 기준을 변경해보자.
map도 기본적인 정렬 기준은 less이지만
key를 내림차순으로 정렬하고 싶다면 greater로 변경해서 사용하면 된다.
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
// greater >
map<int, string, greater<int>> m;
// [] operator
m[2] = "two";
m[5] = "five";
m[3] = "three";
m[8] = "eight";
m[4] = "four";
m[6] = "six";
m[1] = "one";
m[7] = "seven";
m[9] = "nine";
for (auto iter = m.begin(); iter != m.end(); iter++)
cout << "(" << iter->first << "," << iter->second << ") ";
cout << '\n';
for (int i = 0; i < m.size(); i++)
cout << m[i] << ' ';
cout << '\n';
return 0;
}
(9, nine) (8, eight) (7, seven) (6, six) (5, five) (4, four) (3, three) (2, two) (1, one)
one two three four five six seven eight nine