[C++] multimap container 정리 및 사용법

• 안녕하세요, BlockDMask 입니다.

• 오늘은 연관 컨테이너(Associative container) 중 multimap 에 대해서 알아보도록 하겠습니다.

• multimap은 map과 거의 동일하지만 딱 한부분 만 다릅니다.

• key값이 중복 가능하다.

• map에 대한 자세한 정보는 [바로가기] 에 있습니다.

1) multimap container

• Associative : 노드 기반으로 구현된 Associative Container 에 속합니다.
  
  
• Ordered : Key, Value 값이 삽입될때 정렬이 되면서 삽입됩니다. (항상 정렬되어있는 상태 입니다)
  
  
• Map : 각각의 Key는 하나의 Value 에 mapping 됩니다. (pair 객체를 이용하여 key, value를 묶습니다.)
  
  
• Multiple equivalent keys : multimap은 중복 key를 허용합니다.
  
  
• Allocator-aware : multimap container는 인자들이 들어올때마다 allocator 객체를 사용하여 메모리를 동적할당 합니다.
  
  
• 그림으로 살펴보겠습니다.
  

2) multimap 사용법

• <map> 헤더 파일에 존재합니다.
  
  
• using namespace std; 네임공간을 사용하면 편리합니다.
  
  
• 기본 선언 방법은 : multimap< [Data Type1 = Key], [Data Type2 = Value] > [변수이름] 입니다.
  ex) multimap<string, int> mm1;
  ex) multimap<int, int> mm2;
  
  > insert 시에는 pair 객체를 통해서 insert를 합니다.
  
  ex) mm1.insert(pair<string, int>("BlockDMask", 27));
  ex) mm2.insert(pair<int, int>(2017, 0729));
  

3) multimap 생성자와 연산자

• multimap<int, int> mm;
  - 기본 선언 방법입니다.
  - 첫번째 인자가 key 이고, 두번째 인자가 value 가 됩니다.
  
  
• multimap<int, int> mm(pred);
  - pred를 통해서 오름차순인지 내림차순인지 (less or greater) 정렬의 기준을 정합니다.
  
  
  
• multimap<int, int> mm2(mm1);
  - mm1을 복사한 multimap mm2를 생성합니다.
  
  
• ==, !=, <, >, <=, >= 연산자 사용 가능합니다.
  
  
• map 과는 다르게
  operator [] 를 사용해서 원소 (pair<key, value>)를 추가 또는 수정이 불가능 합니다.

4) multimap 의 멤버 함수

-> map, set과 동일한 멤버 함수로 구성되어있습니다. [바로가기]

-> 멤버 변수 종류만 나열하고, 이번 예시에서 사용하는 함수만 설명하겠습니다.

• mm.begin();
• mm.end();
• mm.rbegin();
• mm.rend();
• mm.clear();
• mm.count(key);
• mm.empty();
• mm.insert(pair < >);     // pair 객체입니다.
• mm.erase(start, end);
• mm.find(key);
• mm2.swap(mm1);
• mm.value_comp();
• mm.key_comp();
• mm.max_size();
• mm.size();

• mm.upper_bound(key);
  - key 값에 해당되는 맨 마지막 원소의 "다음" 을 가리키는 반복자를 반환합니다.
  - 폐구간 " ) " 으로 사용됩니다.
  
  

• mm.lower_bound(key);
  - key 값에 해당하는 맨 첫번째 원소를 가리키는 반복자를 반환합니다.
  - 개구간 " [ " 으로 사용됩니다.
  
  

• mm.equal_range(key);
  - key 값에 해당하는 원소의 "범위" 를 pair 객체로 반환합니다.
  
  - pair 객체의 first 는 key 값에 해당하는 원소의 첫번째 반복자를 반환. (lower_bound)
  - pair 객체의 second 는 key 값에 해당하는 원소의 마지막 원소의 "다음" 반복자를 반환. (upper_bound)
  
  - [ first, second ) 
  
  

이 세 함수를 그림으로 표현해 보았습니다. 

- multimap<int, int> mm;

- pair< multimap<int, int>::iterator, multimap<int, int>::iterator > pair_iter = mm.equal_range(6);

- upper_bound, pair_iter.second 가 둘다 key : 8 을 가리킨다 하더라도. 개구간 " ) " 이기 때문에.
- iterator 를 통해 순회를 하더라도, [6,60] [6,61] [6,62] 까지 나오게됩니다.

5) multimap 예제

<Test 1> insert, count

#include<iostream>
#include<map>
 
using namespace std;
 
int main(void){
    multimap<int, int> mm;
 
    mm.insert(pair<int, int>(60, 6));
    mm.insert(pair<int, int>(30, 3));
    mm.insert(pair<int, int>(70, 7));
    mm.insert(pair<int, int>(90, 9));
    mm.insert(pair<int, int>(40, 4));        
    mm.insert(pair<int, int>(20, 2));
    mm.insert(pair<int, int>(50, 5));
    mm.insert(pair<int, int>(80, 8));
        
        
    multimap<int, int>::iterator iter;
 
    cout << "mm.size() : " << mm.size() << endl;
    cout << "mm.count(40) : " << mm.count(40) << endl;
    
 
    for(iter = mm.begin(); iter != mm.end(); iter++){
        cout << "[" << iter->first << ", " << iter->second << "] " ;
    }
 
    cout << endl << endl;
 
    //인자 2개 추가
    mm.insert(pair<int, int>(40, 44));        
    mm.insert(pair<int, int>(40, 3));        
 
    
    cout << "mm.size() : " << mm.size() << endl;
    cout << "mm.count(40) : " << mm.count(40) << endl;
 
 
    for(iter = mm.begin(); iter != mm.end(); iter++){
        cout << "[" << iter->first << ", " << iter->second << "] ";
    }
        
    
    return 0;    
}

• Test 1 결과
  

<Test 2> upper_bound, lower_bound

#include<iostream>
#include<map>
 
using namespace std;
 
int main(void){
    multimap<int, string> mm;
 
    mm.insert(pair<int, string>(60, "C"));
    mm.insert(pair<int, string>(30, "C++"));
        mm.insert(pair<int, string>(40, "Linux"));        
    mm.insert(pair<int, string>(70, "JAVA"));
        mm.insert(pair<int, string>(40, "Ubuntu"));        
    mm.insert(pair<int, string>(90, "Unix"));
        mm.insert(pair<int, string>(40, "CentOS"));        
 
        
    multimap<int, string>::iterator iter;
 
    for(iter = mm.begin(); iter != mm.end(); iter++){
        cout << "[" << iter->first << ", " << iter->second << "] " ;
    }
    cout << endl << endl;
 
 
 
    //중복 키 값이 존재하는 40 의 인자 출력.    
    for(iter = mm.lower_bound(40); iter != mm.upper_bound(40); iter++){
        cout << "[" << iter->first << ", " << iter->second << "] " ;
    }
    cout << endl;
 
 
    
    // 인자 >= lower_bound
    // 인자 < upper_bound
    // [ lower_iter, upper_bound )  개폐구간. 
    multimap<int, string>::iterator lower_iter = mm.lower_bound(40);
    multimap<int, string>::iterator upper_iter = mm.upper_bound(40);
 
    cout << "lower_iter : " << lower_iter->first << ", " << lower_iter->second << endl;        
    cout << "upper_iter : " << upper_iter->first << ", " << upper_iter->second << endl;
 
    
    return 0;    
}

• Test 2 결과
  
• 키 값이 같더라도, 나중에 삽입되는 값이 뒤쪽에 삽입이 됩니다. (inorder상 뒤쪽)

<Test 3> equal_range

#include<iostream>
#include<map>
 
using namespace std;
 
int main(void){
    multimap<int, string> mm;
 
    mm.insert(pair<int, string>(60, "C"));
    mm.insert(pair<int, string>(30, "C++"));
        mm.insert(pair<int, string>(40, "Linux"));        
    mm.insert(pair<int, string>(70, "JAVA"));
        mm.insert(pair<int, string>(40, "Ubuntu"));        
    mm.insert(pair<int, string>(90, "Unix"));
        mm.insert(pair<int, string>(40, "CentOS"));        
 
        
    multimap<int, string>::iterator iter;
 
    for(iter = mm.begin(); iter != mm.end(); iter++){
        cout << "[" << iter->first << ", " << iter->second << "] " ;
    }
    cout << endl << endl;
 
 
 
    //중복 키 값이 존재하는 40 의 인자 출력.    
    for(iter = mm.equal_range(40).first; iter != mm.equal_range(40).second; iter++){
        cout << "[" << iter->first << ", " << iter->second << "] " ;
    }
    cout << endl;
 
 
    
    // 인자 >= equal_range.first
    // 인자 < equal_range.second
    // [ first, second )  개폐구간. 
    pair<multimap<int, string>::iterator, 
          multimap<int,string>::iterator> pair_iter = mm.equal_range(40);
 
 
    cout << "pair_iter.first : " 
        << (pair_iter.first)->first << ", " << (pair_iter.first)->second << endl;        
    cout << "pair_iter.second: " 
        << (pair_iter.second)->first << ", " << (pair_iter.second)->second << endl;
 
    //여기서 pair_iter.first 는 이전 Test2 에서 lower_bound 를 가리키는 iterator와 동일합니다. 
    //여기서 pair_iter.second 는 이전 Test2 에서 upper_bound 를 가리키는 iterator와 동일합니다.
    
    return 0;    
}

• Test 3 결과
  

참고 : http://www.cplusplus.com/reference/map/multimap/