C++] map 사용법과 원리
map이란?
배열을과 비슷하게 생겼습니다.
배열은 index값을 통해 값을 찾죠.
ex) a[3] = { 10. 20. 30 };
a[0] = 10, a[1] = 20, a[2] = 30.
이런식으로 a라는 배열에서 원하는 값을 얻기 위해 0 ~ 2까지의 번호를 입력해 얻어옵니다.
map은 순차적으로 증가하는 배열의 index와는 다르게 key와 value로 구성되어 있습니다.
key는 사용자가 직접 정의해줘야 합니다.
key는 int가 될 수있고 string이 될 수 있고 그밖의 자료형도 가능합니다.
map은 다음과 같은 형태로 저장됩니다.
map은 red-black tree로 구성되어 key별로 오름차순 혹은 내림차순이 가능합니다.
아무것도 지정안하고
map<int, string>만 하면 오름차순으로 정렬이 되면서 삽입이 되고,
map<int, string, greater<int>> 로 하게되면 내림차순으로 정렬이 되면서 삽입이 됩니다.
(key값 기준으로 정렬)
또한 map의 특징은 key의 중복을 허용하지 않습니다.
이것이 가장 큰 특징이죠.
map 초기화
| map<자료형, 자료형> 변수 | 기본적인 선언방법 |
| map<자료형, 자료형> 변수(같은 자료형의 변수) | map 복사 |
| 변수[Key] = 변수 | = 대입 연산 |
#include <iostream>
#include <map>
using namespace std;
int main() {
map<char, int> m;
m['c'] = 1;
map<char, int> m2(m), m3;
m3 = m;
cout << m['c'] << " " << m2['c'] << endl;
//output : 1 1
return 0;
}
map 반복자(iterator)
| s.begin() | map의 시작이 되는 주소 값 반환 |
| s.end() | map의 마지막 부분에 대한 주소 값 반환(정확히는 마지막 뒤 공백구간) |
| s.rbegin() | map의 마지막 부분을 시작점으로 지정 |
| s.rend() | map의 첫번 째 부분을 마지막점으로 지정 |
| s.cbegin() | begin()과 동일하지만 const로 설정. |
| s.cend() | end()와 동일하지만 const로 설정 |
| s.crbegin() | rbegin()과 동일하지만 const로 설정 |
| s.crend() | rend()와 동일하지만 const로 설정 |
출처 : https://en.cppreference.com/w/cpp/container/vector/rend
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
int main() {
map<char, int> m;
m['c'] = 1;
m['a'] = 10;
m['z'] = 99;
m['h'] = 77;
for_each(m.begin(), m.end(), [&](pair<char, int> itr) {
cout << itr.first << " " << itr.second << endl;
});
map<char, int>::reverse_iterator itr = m.rbegin();
for (; itr != m.rend(); itr++) {
cout << itr->first << " " << itr->second << endl;
}
return 0;
}
map의 용량(Capacity)
| empty() | 비어있다면 true, 아니면 false |
| size() | 저장되어 있는 크기 |
| max_size() | 가질 수 있는 최대 크기 |
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
int main() {
map<char, int> m;
m['c'] = 1;
m['a'] = 10;
m['z'] = 99;
m['h'] = 77;
cout << m.empty() << endl; //output : false
cout << m.size() << endl; //output : 4
cout << m.max_size() << endl; //output : 178956970
return 0;
}
map의 요소 접근(Access)
| m[key 값] | key 값에 대한 요소 접근(범위 검사 x) |
| m.at(key 값) | key 값에 대한 요소 접근(범위 검사 o) |
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
int main() {
map<char, int> m;
m['c'] = 1;
m['a'] = 10;
m['z'] = 99;
m['h'] = 77;
cout << m['c'] << endl; //output : 1
cout << m.at('z') << endl; //output : 99
return 0;
}
at과 []의 차이점은 범위검사를 통한 예외처리입니다. 백터와 같은데 at은 범위검사를 하고 해당 범위 이외의 값이 들어오면
std::out_of_range를 발생시킵니다.
반면 []는 범위검사를 하지 않으며, 예외처리가 아닌 VC++ or g++의 디버깅이 일어나게 됩니다.
map의 삽입, 삭제(Modifiers)
| m.insert() | m에 값 삽입 |
| m.erase() | m에 저장된 요소 삭제 |
| m1.swap() | m1과 m2를 서로 교환 |
| m.clear() | m의 요소들 전부 삭제 |
| m.emplace() | move()를 사용해 객체를 저장 |
| m.emplace_hint() | 삽입될 위치에 대한 힌트를 토대로 삽입 |
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
int main() {
/****** insert() ******/
map<char, int> m1;
m1.insert(pair<char, int>('a', 10));
m1.insert(pair<char, int>('f', 20));
m1.insert(pair<char, int>('c', 30));
//output : m1['a'] = 10, m1['f'] = 20, m1['c'] = 30.
/****** emplace(), emplace_hint() ******/
map<char, int> m2;
m2.emplace('z', 100);
m2.emplace('d', 200);
m2.emplace('q', 300);
///// output : m2['z'] = 100, m2['d'] = 200, m2['q'] = 300.
map<char, int>::iterator itr = m2.find('q');
m2.emplace_hint(itr, 'r', 111);
m2.emplace_hint(itr, 'x', 222);
///// output : m2['z'] = 100, m2['d'] = 200, m2['q'] = 300,
// m2['r'] = 111, m2['x'] = 222.
/****** erase() ******/
map<char, int> m3;
m3['a'] = 1;
m3['b'] = 2;
m3['c'] = 3;
m3['d'] = 4;
m3['e'] = 5;
m3['f'] = 6;
m3['g'] = 7;
m3.erase('c'); //output : m['c']에 대한 데이터 삭제
m3.erase(m3.find('d'), m3.end()); //output : m['d'] ~ m['g'] 까지 데이터 모두 삭제
/****** swap() ******/
m1.swap(m3);
// m1과 m3의 요속소값을 바꿔준다.
/****** clear() ******/
m1.clear(); //map<char, int>().swap(m1)을 추천.
// m1의 데이터 전부 삭제
return 0;
}
emplace_hnt()는 map변수에서 요소 값 하나를 지정 후 해당 위치에서 데이터를 삽입하는 것입니다.
기본적으로 map은 tree로 구성되어 있기 때문에 삽입을 하더라도 처음 위치에서 부터 순차적으로 삽입할 위치를 찾습니다.
이런 수고를 덜어주는 거시 emplace_hint()입니다. 하지만 tree 특성상 O(n long(n))이기 때문에 시간 차이는 별로 나지 않을 것입니다.
clear()같은 경우 해당 map에 대한 데이터를 전부 지워주지만 capacity()는 그대로 남아 있습니다. 때문에 clear()를 반복적으로 사용한다면
heap메모리엔 잉여 데이터 공간이 많이 생기게 됩니다. C++은 garbage collection 기능이 없기 때문에 프로그래머가 직접 관리해 줘야 합니다.
여기서 map<char, int>().swap(m1)을 사용하게 되면 m1에 대한 capacity()는 0이 되기 때문에 데이터를 완전히 지울 땐 해당 방법을 추천하는 것입니다.
emplace와 insert의 차이점은 emplace는 내부에서 생산자를 호출해 데이터를 직접 삽입하게 됩니다.
때문에 pair<> 없이 직접삽입이 가능합니다. 이에 대해선 https://hwan-shell.tistory.com/119에 설명을 자세히 해 놨으니 참고하시기 바랍니다.
map의 기능(Operations)
| find() | key값에 위치를 찾은 후 반환 |
| count() | 해당 key값에 있는 변수 갯수를 반환 (있다면 무조건 1 반환) |
| lower_bound() | map의 원하는 key값의 iterator를 반환 |
| upper_bound() | map의 원하는 key값의 iterator를 반환 |
| equal_range() | pair형태로 반환되며 지정한곳을 기준으로 다음 값 까지 기억 가능 |
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
int main() {
map<char, int> m;
m['a'] = 1;
m['b'] = 2;
m['c'] = 3;
m['d'] = 4;
m['e'] = 5;
m['f'] = 6;
//****** find(), count() ******//
if (m.find('a') != m.end())
cout << "find : a" << endl;
else
cout << "not find" << endl;
//output : find : a
if(m.find('z') != m.end())
cout << "find : z" << endl;
else
cout << "not find" << endl;
//output : not find
cout << m.count('a') << endl; //output : 1
cout << m.count('c') << endl; //output : 1
cout << m.count('z') << endl; //output : 0
//******* lower_bound(), upper_bound() ******//
m.erase(m.lower_bound('c'), m.upper_bound('e'));
for (auto itr = m.begin(); itr != m.end(); itr++)
cout << itr->first << " " << itr->second << endl;
//output : a 1, b 2, f 6
pair <map<char, int>::iterator, map<char, int>::iterator> itr;
itr = m.equal_range('a');
cout << itr.first->first << " " << itr.first->second << endl;
cout << itr.second->first << " " << itr.second->second << endl;
//output : a 1, b 2
return 0;
}
find()의 반환 값은 iterator이며 찾는 값이 없을 땐 end()를 return하게 됩니다.
기본적을 erase를 사용할 때 m.erase(m.begin(), m.find('e') 까지하게되면 a ~ d 까지 삭제됩니다. e는 남아 있죠.
하지만 lower_bound(), upper_bound()를 사용하면 a ~ e까지 삭제를 하게 됩니다.