map과 multimap은 '연관 컨테이너'입니다. 모든 연관 컨테이너(set, multiset, map, multimap)는 '노드 기반 컨테이너'입니다. 또 모든 연관 컨테이너는 균형 2진 트리로 구현됩니다. 균형 2진 트리는 보통 레드-블랙 트리를 사용합니다. map은 key와 value의 쌍으로 구성된 데이터 셋의 집합입니다. 여기서 key는 유니크합니다. multiset도 map과 같이 key와 value의 쌍으로 구성된 데이터 셋의 집합입니다. 단, multiset은 map과 달리 중복된 key가 존재할 수 있습니다.
set과 map은 데이터의 key가 유니크합니다.
multiset과 multimap은 같은 key값의 데이터를 컨테이너에 저장할 수 있습니다.
map, multimap의 주요 특징과 함수
map도 set처럼 데이터를 추가하는 push_? 류의 함수를 가지고 있지 않습니다. 삽입(insert)한다는 의미에서 insert() 함수를 가지고 있습니다.
map의 특징은 key와 value의 쌍으로 데이터를 저장합니다. 그리고 key값을 이용하여 빠르게 value값을 찾을 수 있습니다. 연관 컨테이너에서 유일하게 [] 연산자 중복을 제공합니다.
기본적인 map 예제
#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;
}
- 100
50
80
100
100
map은 key와 value의 쌍으로 구성된 데이터들의 집합입니다. []연산자의 인덱스는 key이며 인덱스가 가리키는 메모리 값이 value입니다.
주의할 점은 m[5] = 100 연산에서 5라는 key가 없으면 노드 '추가'가되며 5라는 key가 있으면 '갱신'이 됩니다. 아래에서 공부합니다.
map의 key값 5로 value를 접근
map은 key와 value의 쌍을 pair 객체로 저장합니다. STL의 쌍을 이루는 모든 요소는 pair 객체를 사용합니다.
위 예제는 insert()함수를 사용하여 아래 예제로 바꿀 수 있습니다.
#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;
}
- 100
50
80
100
100
map은 key, value를 pair 객체로 각각 first와 second에 저장합니다.
반복자를 사용한 모든 key, value 출력 예제
#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;
}
- 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;
}
}
- m[5]: 100
m[5]: 100
m[7]: 80
m[5]: 100 ~ m[7]: 80
동작은 set에서 설명했으므로 패스~!
마지막으로 multimap 예제입니다.
map과 다른 점은 [] 연산자가 없으며 key 값이 중복될 수 있습니다.
#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;
}
- m[7]: 80 m[7]: 200 m[7]: 300
설명은 multiset과 같습니다.
'Programing > 자료구조' 카테고리의 다른 글
| STL find함수 사용 (0) | 2016.12.01 |
|---|---|
| 이중연결리스트 노드 cpp (0) | 2016.12.01 |
| 이중연결리스트 노드클래스 (0) | 2016.12.01 |
| 이중연결리스트.cpp (0) | 2016.12.01 |
| 단일연결리스트.cpp (0) | 2016.11.30 |