STL - Map, MultiMap 컨테이너

map과 multimap은 '연관 컨테이너'입니다. 모든 연관 컨테이너(set, multiset, map, multimap)는 '노드 기반 컨테이너'입니다. 또 모든 연관 컨테이너는 균형 2진 트리로 구현됩니다. 균형 2진 트리는 보통 레드-블랙 트리를 사용합니다. map은 key와 value의 쌍으로 구성된 데이터 셋의 집합입니다. 여기서 key는 유니크합니다. multiset도 map과 같이 key와 value의 쌍으로 구성된 데이터 셋의 집합입니다. 단, multiset은 map과 달리 중복된 key가 존재할 수 있습니다.

 

map의 주요 개념을 그림으로 표현하면

 

 

set과 map은 데이터의 key가 유니크합니다.

 

multiset의 주요 개념을 그림으로 표현하면

 

 

multiset과 multimap은 같은 key값의 데이터를 컨테이너에 저장할 수 있습니다.

 

map, multimap의 주요 특징과 함수

 map도 set처럼 데이터를 추가하는 push_? 류의 함수를 가지고 있지 않습니다. 삽입(insert)한다는 의미에서 insert() 함수를 가지고 있습니다.

map의 특징은 key와 value의 쌍으로 데이터를 저장합니다. 그리고 key값을 이용하여 빠르게 value값을 찾을 수 있습니다. 연관 컨테이너에서 유일하게 [] 연산자 중복을 제공합니다.

 

기본적인 map 예제

#include <iostream>
#include <map>
using namespace std;
void main( )
{
    map<int , int > m;

    m[5] = 100;
    m[3] = 50;
    m[7] = 80;
    m[2] = 100;
    m[4] = 100;

    cout << m[5] << endl;
    cout << m[3] << endl;
    cout << m[7] << endl;
    cout << m[2] << endl;
    cout << m[4] << endl;
}


1. 100
   50
   80
   100
   100

map은 key와 value의 쌍으로 구성된 데이터들의 집합입니다. []연산자의 인덱스는 key이며 인덱스가 가리키는 메모리 값이 value입니다.

주의할 점은 m[5] = 100 연산에서 5라는 key가 없으면 노드 '추가'가되며 5라는 key가 있으면 '갱신'이 됩니다. 아래에서 공부합니다.

그림으로 설명하면..

 

 

map의 트리 그림입니다.

 

 

map의 key값 5로 value를 접근하는 그림입니다.

 

 

 

 map은 key와 value의 쌍을 pair 객체로 저장합니다. STL의 쌍을 이루는 모든 요소는 pair 객체를 사용합니다.

위 예제는 insert()함수를 사용하여 아래 예제로 바꿀 수 있습니다.

#include <iostream>
#include <map>
using namespace std;
void main( )
{
    map<int , int > m;

    m.insert( pair<int,int>( 5, 100) );
    m.insert( pair<int,int>( 3, 50) );
    m.insert( pair<int,int>( 7, 80) );
    m.insert( pair<int,int>( 2, 100) );
    pair<int,int> pr( 4, 100);
    m.insert( pr );

    cout << m[5] << endl;
    cout << m[3] << endl;
    cout << m[7] << endl;
    cout << m[2] << endl;
    cout << m[4] << endl;
}



1. 100
   50
   80
   100
   100

 map은 key, value를 pair 객체로 각각 first와 second에 저장합니다.

그림으로 표현하면

 

 

 

 

반복자를 사용한 모든 key, value 출력 예제

#include <iostream>
#include <map>
using namespace std;

void main( )
{
    map<int , int > m;

    m[5] = 100;
    m[3] = 50;
    m[7] = 80;
    m[2] = 100;
    m[4] = 100;

    map<int, int>::iterator iter;
    for( iter = m.begin(); iter != m.end() ; iter++)
        cout << "m["<<(*iter).first <<"]: " << (*iter).second << endl;

    cout << "==============" << endl;
    for( iter = m.begin(); iter != m.end() ; iter++)
        cout << "m["<<iter->first <<"]: " << iter->second << endl;
}


1. m[2]: 100
   m[3]: 50
   m[4]: 100
   m[5]: 100
   m[7]: 80
   ==============
   m[2]: 100
   m[3]: 50
   m[4]: 100
   m[5]: 100
   m[7]: 80

 map도 양방향 반복자를 제공합니다.

그림으로 간단하게..

 

 

 

 

연관 컨테이너는 모두 동일한 함수군을 가지며 동작 방식도 같습니다.

map의 검색 함수들입니다.

#include <iostream>
#include <map>
using namespace std;

void main( )
{
    map<int , int > m;

    m[5] = 100;
    m[3] = 50;
    m[7] = 80;
    m[2] = 100;
    m[4] = 100;

    map<int, int >::iterator iter;

    iter = m.find( 5 );
    if( iter == m.end() )
        cout << "없음!" << endl;
    else
        cout << "m["<<iter->first <<"]: " << iter->second << endl;

    iter = m.lower_bound( 5 );
    if( iter == m.end() )
        cout << "없음!" << endl;
    else
        cout << "m["<<iter->first <<"]: " << iter->second << endl;

    iter = m.upper_bound( 5 );
    if( iter == m.end() )
        cout << "없음!" << endl;
    else
        cout << "m["<<iter->first <<"]: " << iter->second << endl;

    pair< map<int, int>::iterator, map<int, int>::iterator> iter_pair;
    iter_pair = m.equal_range(5);

    if( (iter_pair.first) == m.end() && (iter_pair.second == m.end()) )
        cout << "없음!" << endl;
    else
    {
        cout << "m["<< iter_pair.first->first <<"]: " << iter_pair.first->second <<" ~ ";
        cout << "m["<< iter_pair.second->first <<"]: " << iter_pair.second->second <<endl;
    }
}


1. m[5]: 100
   m[5]: 100
   m[7]: 80
   m[5]: 100 ~ m[7]: 80

 동작은 set에서 설명했으므로 패스~!

그림으로 설명하면...

 

 

 

 

 

마지막으로 multimap 예제입니다.

map과 다른 점은 [] 연산자가 없으며 key 값이 중복될 수 있습니다.

#include <iostream>
#include <map>
using namespace std;

void main( )
{
    multimap<int , int > m;

    m.insert( pair<int,int>( 5, 100) );
    m.insert( pair<int,int>( 3, 50) );
    m.insert( pair<int,int>( 7, 80) );
    m.insert( pair<int,int>( 2, 100) );
    m.insert( pair<int,int>( 4, 100) );
    m.insert( pair<int,int>( 7, 200) );
    m.insert( pair<int,int>( 7, 300) );

    pair<multimap<int,int>::iterator, multimap<int, int>::iterator > iter_pair;
    iter_pair = m.equal_range( 7 );
    multimap<int,int>::iterator iter;
    for( iter = iter_pair.first ; iter != iter_pair.second ; iter++)
        cout << "m["<< iter->first <<"]: " << iter->second <<' ';
    cout << endl;

}


1. m[7]: 80 m[7]: 200 m[7]: 300

 설명은 multiset과 같습니다.

아래는 위 예제의 그림입니다.

 

출처 : http://blog.daum.net/coolprogramming/76