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

 

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

map_개념.png 

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

 

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

multimap_개념.png 

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_간단_코드.png

map의 트리 그림입니다.

map_데이터_추가.png 

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

map_데이터_접근.png 

 

 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에 저장합니다.

그림으로 표현하면

map_pair_객체.png 

 

 

반복자를 사용한 모든 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_반복자.png

 

 

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

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에서 설명했으므로 패스~!

그림으로 설명하면...

map_검색_함수.png 

 

 

 

마지막으로 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과 같습니다.

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

multimap_equal_range(1).png  

 

 

 

여기까지 STL의 컨테이너를 마무리합니다.

C++ 표준에 추가된 해쉬 컨테이너는 다음에 공부합니다. 

출처 : http://coolprogramming.springnote.com/pages/4826369

 

최근엔 hesh_map 등이 더 인기가 있는거 같은..

쓰기에는 map 과 같은 인터페이스에 using namespase std 가 아닌 stdext 를 쓴다

자세한 레퍼렌스는 http://msdn.microsoft.com/query/dev10.query?appId=Dev10IDEF1&l=EN-US&k=k(HASH_MAP);k(DevLang-%22C%2B%2B%22);k(TargetOS-WINDOWS)&rd=true 를 참고하자

+ Recent posts