멀티맵(multimap) 은 연관 컨테이너(Associative Container) 중 하나이다.
multimap 은 노드 기반으로 이루어져 있다.
multimap 은 key 와 value 로 이루어져 있다.
key 와 value 는 pair 객체 형태로 저장되며, map 과는 달리 중복된 key 값을 허용한다.
multimap 은 원소가 삽입되면서 key 값을 기준으로 자동으로 오름차순(기본값)으로 정렬된다.
multimap 은 저장 공간의 필요에 따라 동적할당을 한다.
multimap 헤더파일#include <map>
multimap 선언std::multimap<KeyType, ValueType> MultiMapName;
multimap 생성자 (편의상 <int, int>)| std::multimap<int, int> mm; | 비어있는 멀티맵 mm을 생성 |
|---|---|
| std::multimap<int, int> mm2(mm1); | mm2는 멀티맵 mm1을 복사하여 생성 |
| std::multimap<int, int, predicate> mm; | predicate를 통해 정렬 기준을 세운 멀티맵 mm을 생성 |
std::multimap<int, int, std::greater<int>> mm; // 내림차순으로 정렬하는 멀티맵 mm을 생성
std::multimap<int, int> mm;
| mm.begin() | 첫 번째 원소를 가리키는 iterator를 반환 |
|---|---|
| mm.end() | 마지막 원소의 다음을 가리키는 iterator를 반환 |
| mm.rbegin() | 마지막 원소를 가리키는 reverse_iterator를 반환 |
| mm.rend() | 첫 번째 원소의 앞을 가리키는 reverse_iterator를 반환 |
| mm.insert(p) | pair객체 p를 삽입함. 삽입 시 자동으로 정렬됨 |
| mm.insert(iter, p) | iter가 가리키는 위치부터 pair객체 p를 삽입할 위치를 탐색해 삽입 |
| mm.erase(k) | k 값과 key 값이 일치하는 모든 원소를 제거 |
| mm.erase(iter) | iter가 가리키는 원소를 제거 |
| mm.erase(start, end) | start 반복자부터 end 반복자 전까지 [start, end) 원소를 제거 |
| mm.clear() | 멀티맵의 모든 원소를 제거 |
| mm.find(k) | k 값과 key값이 일치하는 원소를 가리키는 반복자를 반환 |
만족하는 원소가 없다면 mm.end()와 같은 반복자를 반환 |
|
| mm.count(k) | k 값과 key 값이 일치하는 원소의 개수를 반환 |
| mm.empty() | 멀티맵 mm이 비어있으면 true를 반환 |
| mm.size() | 원소의 개수를 반환 |
| m.contains(k) | 멀티맵에 k 값과 일치하는 key 값이 있으면 true 를 반환 (C++20) |
| mm2.swap(mm1) | mm1 멀티맵과 mm2 멀티맵을 서로 바꿈 |
| mm.upper_bound(k) | k 값과 key값이 일치하는 맨 마지막 원소의 다음을 가리키는 iterator를 반환. |
폐구간 ) 으로 사용 |
|
| mm.lower_bound(k) | k 값과 key값이 일치하는 맨 첫 번째 원소를 가리키는 iterator를 반환. |
개구간 [ 으로 사용 |
|
| mm.equal_range(k) | k 값과 key값이 일치하는 원소의 범위를 pair 객체로 반환 |
pair<lower_bound, upper_bound> |multimap은 map과는 다르게 연산자 [] 를 사용한 원소 추가, 수정이 불가능합니다.
insert() 를 통해 multimap 에 원소를 삽입할 수 있다.
#include <iostream>
#include <map>
int main()
{
std::multimap<int, std::string> mm;
std::multimap<int, std::string>::iterator it;
// insert() 이용
mm.insert({ 50, "A1" });
mm.insert({ 42, "B1" });
mm.insert(std::make_pair(52, "E"));
mm.insert(std::make_pair(72, "D"));
mm.insert(std::pair<int, std::string>(20, "C"));
mm.insert(std::pair<int, std::string>(42, "B2"));
mm.insert(std::pair<int, std::string>(50, "A2"));
for (it = mm.begin(); it != mm.end(); ++it)
{
std::cout << "[" << it->first << ", " << it->second << "] ";
}
return 0;
}
[20, C] [42, B1] [42, B2] [50, A1] [50, A2] [52, E] [72, D]
erase(), clear() 를 통해 multimap 의 원소를 삭제할 수 있다.
erase() : 특정 원소 삭제clear() : 전체 원소 삭제#include <iostream>
#include <map>
int main()
{
std::multimap<int, std::string> mm;
std::multimap<int, std::string>::iterator it;
// insert() 이용
mm.insert({ 50, "A1" });
mm.insert({ 42, "B1" });
mm.insert({ 52, "E1" });
mm.insert({ 72, "D1" });
mm.insert({ 20, "C1" });
mm.insert({ 52, "E2" });
mm.insert({ 50, "A2" });
for (it = mm.begin(); it != mm.end(); ++it)
std::cout << "[" << it->first << ", " << it->second << "] ";
// key 값을 기준으로 요소 삭제 (해당 하는 모든 요소가 삭제됨)
mm.erase(52);
// iterator 를 이용해 요소 삭제
mm.erase(mm.begin());
std::cout << std::endl;
for (it = mm.begin(); it != mm.end(); ++it)
std::cout << "[" << it->first << ", " << it->second << "] ";
// clear() 를 이용해 전체 원소 삭제
mm.clear();
if (mm.empty())
std::cout << "\\nmultimap이 비었습니다.";
else
std::cout << "\\nmultimap이 비어있지 않습니다.";
return 0;
}
[20, C1] [42, B1] [50, A1] [50, A2] [52, E1] [52, E2] [72, D1]
[42, B1] [50, A1] [50, A2] [72, D1]
multimap이 비었습니다.
find() 를 통해 원하는 원소를 찾을 수 있다.
#include <iostream>
#include <map>
int main()
{
std::multimap<int, std::string> mm;
std::multimap<int, std::string>::iterator it;
// insert() 이용
mm.insert({ 50, "A1" });
mm.insert({ 42, "B1" });
mm.insert({ 52, "E1" });
mm.insert({ 72, "D1" });
mm.insert({ 20, "C1" });
mm.insert({ 52, "E2" });
mm.insert({ 50, "A2" });
for (it = mm.begin(); it != mm.end(); ++it)
std::cout << "[" << it->first << ", " << it->second << "] ";
// find() 를 이용해 원하는 원소를 찾을 수 있습니다.
it = mm.find(42);
std::cout << "\\n\\n[" << it->first << ", " << it->second << "] ";
// 만약 일치하는 key 값이 없다면 end()를 가리키는 반복자를 반환합니다.
it = mm.find(40);
if (it != mm.end())
std::cout << "\\n\\n원소 발견!" << std::endl;
else
std::cout << "\\n\\n원소 미발견..." << std::endl;
return 0;
}
[20, C1] [42, B1] [50, A1] [50, A2] [52, E1] [52, E2] [72, D1]
[42, B1]
원소 미발견...
upper_bound, lower_boundupper_bound(k) : k 값과 key 값이 일치하는 맨 마지막 원소의 다음을 가리키는 반복자를 반환lower_bound(k) : k 값과 key 값이 일치하는 맨 첫 번째 원소를 가리키는 반복자를 반환#include <iostream>
#include <map>
int main()
{
std::multimap<int, std::string> mm;
std::multimap<int, std::string>::iterator it;
// insert() 이용
mm.insert({ 50, "A1" });
mm.insert({ 52, "D1" });
mm.insert({ 72, "C1" });
mm.insert({ 20, "B1" });
mm.insert({ 72, "C2" });
mm.insert({ 50, "A2" });
mm.insert({ 86, "E1" });
mm.insert({ 50, "A3" });
for (it = mm.begin(); it != mm.end(); ++it)
std::cout << "[" << it->first << ", " << it->second << "] ";
// lower_bound, upper_bound
std::multimap<int, std::string>::iterator low_it;
std::multimap<int, std::string>::iterator up_it;
low_it = mm.lower_bound(50); // 50과 일치한 key 값을 가진 맨 첫 번째 원소를 가리키는 반복자
up_it = mm.upper_bound(50); // 50과 일치한 key 값을 가진 맨 마지막 원소의 다음을 가리키는 반복자
std::cout << "\\n\\nlower_bound : [" << low_it->first << ", " << low_it->second << "]";
std::cout << "\\nupper_bound : [" << up_it->first << ", " << up_it->second << "]";
// [lower_bound, upper_bound) 출력
// 50과 일치한 key 값을 가진 모든 원소 출력
std::cout << std::endl;
for (it = mm.lower_bound(50); it != mm.upper_bound(50); ++it)
std::cout << "[" << it->first << ", " << it->second << "] ";
return 0;
}
[20, B1] [50, A1] [50, A2] [50, A3] [52, D1] [72, C1] [72, C2] [86, E1]
lower_bound : [50, A1]
upper_bound : [52, D1]
[50, A1] [50, A2] [50, A3]
equal_rangeequal_range(k) : k 값과 key 값이 일치하는 원소의 범위를 pair 객체로 반환
→ pair<lower_bound, upper_bound>
#include <iostream>
#include <map>
int main()
{
std::multimap<int, std::string> mm;
std::multimap<int, std::string>::iterator it;
// insert() 이용
mm.insert({ 50, "A1" });
mm.insert({ 52, "D1" });
mm.insert({ 72, "C1" });
mm.insert({ 20, "B1" });
mm.insert({ 72, "C2" });
mm.insert({ 50, "A2" });
mm.insert({ 86, "E1" });
mm.insert({ 50, "A3" });
for (it = mm.begin(); it != mm.end(); ++it)
std::cout << "[" << it->first << ", " << it->second << "] ";
// equal_range
std::pair<std::multimap<int, std::string>::iterator, std::multimap<int, std::string>::iterator> pair_it;
pair_it = mm.equal_range(50); // 50과 일치한 key 값을 가진 원소의 범위를 pair 객체로 반환
std::cout << "\\n\\npair_it.first : [" << (pair_it.first)->first << ", " << (pair_it.first)->second << "]";
std::cout << "\\npair_it.second : [" << (pair_it.second)->first << ", " << (pair_it.second)->second << "]";
// equal_range 출력
// 50과 일치한 key 값을 가진 모든 원소 출력
std::cout << std::endl;
for (it = mm.equal_range(50).first; it != mm.equal_range(50).second; ++it)
std::cout << "[" << it->first << ", " << it->second << "] ";
return 0;
}
[20, B1] [50, A1] [50, A2] [50, A3] [52, D1] [72, C1] [72, C2] [86, E1]
pair_it.first : [50, A1]
pair_it.second : [52, D1]
[50, A1] [50, A2] [50, A3]