728x90
728x90
map(맵)
특징
- 연관 컨테이너(Associative Container) 중 하나이다.
- 연관 컨테이너에는 set, multiset, map, multimap 이 있다.
- string : int 형태로 값을 할당해야 할 때 맵을 사용한다.
- 키(Key)와 값(Value) 형태로 이루어져 있고, 레드-블랙 트리(Red-Black Tree)라는 구조를 내장하고 있다.
- 노드 기반으로 이루어져 있고, 균형 이진 트리 구조이다.
- pair 객체 형태로 키(Key)와 값(Value)이 저장된다.
- Key는 고유한 값이므로 중복이 불가능하다.
- 중복 Key를 사용하려면 multimap을 사용하면 된다.
- 삽입, 삭제, 탐색에 대해서 $O(logN)$ 정도의 시간 복잡도를 가진다.
- 집합(Set)과 마찬가지로 삽입이 되면서 자동으로 정렬이 된다.
- 데이터를 삽입할 때 정렬된 위치에 삽입되게 된다.
- 검색 속도가 빠르다는 장점이 있다.
- 정렬 대상은 키(Key)를 기준으로 오름차순 정렬한다.
- 정렬의 기본값은 오름차순(less)이다.
- 데이터를 삽입할 때 정렬된 위치에 삽입되게 된다.
- 저장 공간의 필요에 따라 allocator 객체를 사용한다. (동적 할당을 수행한다.)
- map의 종류에는 unordered_map과 map 2가지가 있으며, map은 정렬을 보장한다.
- unordered_map에 대해 알아보기 : https://dev-astra.tistory.com/245
헤더 파일
- 맵(Map)을 사용하려면 다음의 헤더 파일을 불러와야 한다.
#include <map>
멤버 함수
사용 방법
객체 생성
일반적인 방법
map<[data_type_1], [data_type_2]> [name]
사용 예
map<int, int> m1;
map<string, int> m2;
정렬 방법을 지정하는 방법
- 요소가 삽입될 때, 정렬되는 기준(pred)을 지정한다.
- pred는 map의 정렬 기준인 조건자이다.
map<int> m(pred); // pred를 통해 정렬 기준(오름차순, 내림차순)을 정한다.
다른 맵의 요소를 복사하여 생성하는 방법
map<int> m2(m1); // m1을 복사한 m2를 생성
관련 연산자
- ==, !=, <, >, <=, >= 연산자를 사용할 수 있다.
- [] 연산자를 이용하여 요소를 다룰 수 있다.
- m[key] = Value; 을 통해서 원소 (Key, Value)를 추가 또는 수정이 가능하다.
선언과 동시에 초기화하기
- 다양한 방법으로 객체를 선언과 동시에 초기화할 수 있다.
map<int, string> m0 {
{1, "1"}, // way 1
pair<int, string>(2, "1"), // way 2, C++17 이상부터 pair(1, "1") 과 같이 사용 가능 (자동 추론)
make_pair(3, "1") // way 3
};
- 다음과 같이 일관성 있게 선언하는 것이 좋다.
map<int, string> m1 {
{1, "1"},
{2, "2"},
{3, "3"}
};
요소 삽입
- 다양한 방법으로 맵에 요소를 넣을 수 있다.
- 이미 값이 있는 키(Key)에는 값(Value)을 삽입할 수 없다.
- 5번 방법이 권장된다.
// 1. insert() 함수에 pair 객체로 묶은 요소를 인자로 하여 요소 넣기
m1.insert(pair<int, int>(10, 20));
m2.insert(pair<string, int>("Kim", 27));
// 2. insert() 함수에 중괄호({})에 넣은 요소를 인자로 하여 요소 넣기
m1.insert({ 10, 20 });
m2.insert({ "Kim", 27 });
// 3. insert() 함수에 make_pair() 함수를 이용하여 묶은 요소를 인자로 하여 요소 넣기
m1.insert(make_pair(10, 20));
m2.insert(make_pair("Kim", 27));
// 4. emplace() 함수를 이용하여 요소 넣기
m1.emplace(10, 20);
m2.emplace("Kim", 27);
// 5. [] 연산자를 이용하여 넣기 (변경 및 추가 가능)
m1[10] = 20;
m2["Kim"] = 27;
요소 수정
- 다음과 같은 방법으로 요소의 값(Value)을 수정할 수 있다.
m1[10] = 77; // 방법 1-1 : 키(Key)가 10인 값(Value)을 77로 변경
m2["Kim"]++; // 방법 1-2 : 키(Key)가 "Kim"인 값(Value)을 1 증가시킴.
- for 문을 이용하여 다양하게 값(Value)을 한번에 수정할 수 있다.
// 방법 2
for (auto i = m1.begin(); i != m1.end(); i++) {
i->second = 7; // m1 맵의 요소들의 값(Value)을 모두 7로 변경함.
(*i).second = 8; // m1 맵의 요소들의 값(Value)을 모두 8로 변경함.
}
// 방법 3
for (auto i : m1) {
i.second = 9; // m1 맵의 요소들의 값(Value)을 모두 9로 변경함.
}
// 방법 4 : C++17부터 사용 가능 (분기)
for (auto [key, value] : m1) {
value = 10; // m1 맵의 요소들의 값(Value)을 모두 10으로 변경함.
}
// 방법 5 : C++17부터 사용 가능 (분기)
for (auto i : m1.cbegin(); i != m1.cend(); i++) {
auto [key, value] = *i;
value = 11; // m1 맵의 요소들의 값(Value)을 모두 11로 변경함.
}
- 다음과 같은 분기 기능은 C++17 부터 사용 가능하다.
map<int, string> m {
{1, "1"},
{2, "2"},
{3, "3"}
};
if (auto [iter, success] = m.insert({1, "7"}), success) {
cout << success << endl;
cout << iter->first << endl;
cout << iter->second << endl;
}
요소 접근(순회)
- 다음과 같은 방법으로 요소에 접근(순회)할 수 있다.
- Key 값은 first, Value 값은 second로 탐색이 가능하다.
// 방법 1 : for
for (auto i = m1.begin(); i != m1.end(); i++) {
cout << "(" << i->first << ", " << (*i).second << ")" << '\n'; // 2가지 방법으로 요소에 접근 가능
}
// 방법 2 : range for
for (auto i : m1) {
cout << "(" << i.first << ", " << i.second << ")" << '\n';
}
- 다음과 같이 다양하게 요소에 접근(순회) 할 수 있다.
- const_iterator를 사용할 경우, cbegin(), cend() 메소드를 이용한다.
- iterator를 사용할 경우, begin(), end() 메소드를 이용한다.
// 방법 3
for (const pair<const int, string>& pair : m1) {
cout << "(" << pair.first << ", " << pair.second << ")" << '\n';
}
// 방법 4
for (auto& pair : m2) {
cout << "(" << pair.first << ", " << pair.second << ")" << '\n';
}
// 방법 5
for (map<int, string>::const_iterator i = m1.cbegin(); i != m1.cend(); i++) {
cout << "(" << i->first << ", " << (*i).second << ")" << '\n';
}
// 방법 6
for (auto i = m2.cbegin(); i != m2.cend(); i++) {
cout << "(" << i->first << ", " << (*i).second << ")" << '\n';
}
// 방법 7
for (const auto& [key, value] : m1) {
cout << "(" << key << ", " << value << ")" << '\n';
}
// 방법 8
for (auto i = m2.cbegin(); i != m2.cend(); i++) {
auto& [key, value] = *i;
cout << "(" << i->first << ", " << (*i).second << ")" << '\n';
}
요소 찾기
- find() 메소드를 이용하여 요소를 찾을 수 있다.
map.find([Key]);
- find() 메소드는 요소를 찾지 못하면 end() 이터레이터(Iterator)를 반환한다.
auto search = m1.find(40);
if (search != m1.end()) {
cout << "Key : " << search->first << ", Value : " << (*search).second << '\n'; // 발견되면 키와 값을 출력
}
else {
cout << "Not Found." << '\n'; // 발견되지 않으면 발견되지 않았다는 문장 출력
}
- C++17부터 다음과 같이 요소를 찾을 수 있다.
if (auto i = m1.find(10); i != m1.end()) {
cout << i->first << " : "; // Key 출력
cout << i->second << endl; // Value 출력
}
해당 키(Key)가 맵에 있는지 확인하기
- count() 메소드를 이용하여 해당 키(Key)가 맵에 있는지 확인할 수 있다.
map.count([Key]);
#include <iostream>
#include <map>
using namespace std;
map<int, string> m {
{1, "1"},
{2, "2"},
{3, "3"}
};
int main() {
cout << m.count(3) << " " << m.count(10) << '\n'; // 해당 키가 있으면 1, 없으면 0 출력
return 0;
}
1 0
맵 객체의 크기 출력하기
- size() 메소드를 이용하여 맵 객체의 크기를 출력할 수 있다.
cout << m1.size() << '\n';
맵 객체의 요소 지우기
- erase() 메소드를 이용하여 맵 객체의 특정 요소를 지울 수 있다.
- 키(Key)와 값(Value) 모두 지워진다.
map.erase([Key]);
m1.erase(10); // 키 값이 10인 요소 제거
- 또는 다음과 같이 find() 메소드를 활용하여 요소를 지울 수 있다.
auto search = m1.find(10);
if (search != m1.end()) {
m1.erase(search);
}
맵에 있는 모든 요소 지우기
- clear() 메소드를 이용하여 맵에 있는 모든 요소를 지울 수 있다.
m1.clear() // 맵에 있는 모든 요소 제거
사용 시 주의사항
맵과 참조
- 맵을 사용할 때, 해당 인덱스에 참조만 해도 값(Value)이 생긴다. (맵의 요소가 생긴다.)
- int 형의 경우 0이 값(Value)으로 들어간다.
- string 형의 경우 빈 문자열이 값(Value)으로 들어간다.
#include <iostream>
#include <map>
using namespace std;
map<int, int> mp1;
map<string, string> mp2;
int main() {
// 인덱스에 참조만 하기
cout << mp1[1] << '\n';
cout << mp2["aaa"] << '\n';
// 확인하기
for (auto i : mp1) {
cout << i.first << " " << i.second << '\n';
}
for (auto i : mp2) {
cout << i.first << " " << i.second << '\n';
}
return 0;
}
0
1 0
aaa
- 따라서 맵에 요소가 있는지 없는지를 확인하고 맵에 데이터를 할당하는 부분의 로직을 다음과 같이 구축할 수 있다.
- 다만, 이 방법은 해당 키의 값(Value)에 0이 아닌 값이 들어갈 때만 활용이 가능하다.
- 문제에서 키에 0이 들어가는 경우 활용이 불가능하다.
#include <iostream>
#include <map>
using namespace std;
map<int, int> mp;
int main() {
if (mp[1] == 0) { // mp1의 첫 번째 인덱스에 접근하자마자 0이 값(Value)으로 생성된다.
mp[1] = 2; // 값(Value)을 2로 변경해준다.
}
for (auto i : mp) {
cout << "Key : " << i.first << ", Value : " << i.second << '\n';
}
return 0;
}
Key : 1, Value : 2
- 만약 문제에서 키의 값(Value)에 0이 들어가는 경우에는 다음과 같이 사용하는 것이 좋다.
#include <iostream>
#include <map>
using namespace std;
map<int, int> mp;
int main() {
if (mp.find(1) == mp.end()) { // find() 메소드는 요소를 찾지 못하면 end() 이터레이터를 반환한다.
mp[1] = 2;
}
for (auto i : mp) {
cout << "Key : " << i.first << ", Value : " << i.second << '\n';
}
return 0;
}
Key : 1, Value : 2
map vs. unordered_map
- map과 unordered_map을 모두 사용할 수 있는 경우, unordered_map을 사용하는 것이 시간 복잡도 측면에서 더 효율적이다. (관련 문제 : https://dev-astra.tistory.com/252)
- map
- 탐색, 삽입, 삭제 : $O(\log n)$
- unordered_map
- 탐색, 삽입, 삭제 : $O(1)$
- 최악의 경우 : $O(N)$
- map
- 참고로, map은 다른 연관 컨테이너(multimap, set, multiset 등)에 비해 비교적 빠른 속도를 보인다.
사용 예
#include <iostream>
#include <map>
using namespace std;
// [1] 객체 생성 및 초기화
//// 객체만 생성
map<int, string> m1;
//// 객체 생성과 동시에 초기화
map<int, string> m2 {
{ 1, "Lim" }, // 방법 1
pair<int, string>(2, "Kuk"), // 방법 2
make_pair(3, "Yun") // 방법 3
};
int main() {
// [2] 요소 삽입
m1.insert(pair<int, string>(40, "Me")); // 방법 1
m1.insert({ 20, "Lee" }); // 방법 2
m1.insert(make_pair(10, "Choi")); // 방법 3
m1.emplace(35, "Park"); // 방법 4
m1[65] = "Kim"; // 방법 5
// [3] 요소 접근
//// 방법 1
for (auto i = m1.begin(); i != m1.end(); i++) {
cout << "(" << i->first << ", " << (*i).second << ")" << '\n'; // 2가지 방법으로 요소에 접근 가능
}
cout << endl;
//// 방법 2
for (auto i : m2) {
cout << "(" << i.first << ", " << i.second << ")" << '\n';
}
cout << endl;
// [4] 요소 찾기
auto search1 = m1.find(70); // 찾기 실패
auto search2 = m1.find(20); // 찾기 성공
if (search1 != m1.end()) {
cout << "Key : " << search1->first << ", Value : " << (*search1).second << '\n';
}
else {
cout << "Not Found." << '\n';
}
if (search2 != m1.end()) {
cout << "Key : " << search2->first << ", Value : " << (*search2).second << '\n';
}
else {
cout << "Not Found." << '\n';
}
//// 해당 키가 맵에 있는지 확인하기
cout << m1.count(22) << " " << m2.count(20) << '\n';
// [5] 요소 수정
map<string, int> m3 {
{ "Queen", 2 },
{ "Prince", 3 },
{ "Princess", 4 }
};
m3["Pince"] = 0; // 방법 1-1
m3["Queen"]++; // 방법 1-2 : 값(Value)을 1 증가 시킴.
// 방법 2
for (auto i = m3.begin(); i != m3.end(); i++) {
i->second = 7; // m3 맵의 요소들의 값(Value)을 모두 7로 변경함.
(*i).second = 8; // m3 맵의 요소들의 값(Value)을 모두 8로 변경함.
}
// 방법 3
for (auto i : m3) {
i.second = 9; // m3 맵의 요소들의 값(Value)을 모두 9로 변경함.
}
// 방법 4
for (auto [key, value] : m3) {
value = 10; // m3 맵의 요소들의 값(Value)을 모두 10으로 변경함.
}
// 방법 5
for (auto i = m3.cbegin(); i != m3.cend(); i++) {
auto [key, value] = *i;
value = 11; // m3 맵의 요소들의 값(Value)을 모두 11로 변경함.
}
cout << endl;
// [6] 맵 객체의 크기 출력하기
cout << m1.size() << '\n';
cout << m2.size() << '\n';
cout << m3.size() << '\n';
cout << endl;
// [7] 맵 객체의 요소 지우기
//// 방법 1
m1.erase(10);
//// 방법 2
auto search = m1.find(10);
if (search != m1.end()) {
m1.erase(search);
}
cout << endl;
// [8] 맵에 있는 모든 요소 지우기
m1.clear();
m2.clear();
m3.clear();
cout << endl;
// [*] 맵에 요소가 있는지 없는지를 확인하고 맵에 데이터를 할당하기
//// 방법 1
if (m1[90] == "") {
m1[90] = "Koo";
}
//// 방법 2
if (m1.find(50) == m1.end()) {
m1[50] = "Jung";
}
// 결과 출력
for (auto i : m1) {
cout << "(" << i.first << ", " << i.second << ")" << '\n';
}
for (auto i : m2) {
cout << "(" << i.first << ", " << i.second << ")" << '\n';
}
for (auto i : m3) {
cout << "(" << i.first << ", " << i.second << ")" << '\n';
}
return 0;
}
(10, Choi)
(20, Lee)
(35, Park)
(40, Me)
(65, Kim)
(1, Lim)
(2, Kuk)
(3, Yun)
Not Found.
Key : 20, Value : Lee
0 0
5
3
4
(50, Jung)
(90, Koo)
728x90
728x90
'Programming > C++' 카테고리의 다른 글
[C++] multiset(중복 집합) (0) | 2022.11.09 |
---|---|
[C++] set(집합) (0) | 2022.11.08 |
[C++] multimap(멀티 맵) (0) | 2022.11.08 |
[C++] unordered_map (0) | 2022.11.08 |
[C++] pair(페어)와 tuple(튜플) (0) | 2022.11.03 |
[C++] lower_bound(), upper_bound() ; 이진 탐색(Binary Search) (0) | 2022.11.01 |
[C++] sort 함수를 이용하여 오름차순/내림차순 정렬하는 방법 (0) | 2022.10.27 |
[C/C++] 현재 날짜/시간 원하는 형태로 출력하기 (0) | 2022.10.20 |