STL 맵, map 사용법 [C++]

 

맵이 뭔가 싶지만

C++의 dictionary를 맵이라 부른다.

즉, key ,value 짝의 자료구조를 맵이라 부른다.

 

그래서 선언할 때도 key자료형, value자료형 같이 선언한다.

 

map<key,value>: key와 value를 pair 형태로 선언한다.

 

 

**unordered_map은 체이닝을 사용하는 해시 테이블로 구현되어 있다.

부하율이 1이 되면 해시 테이블의 크기를 키우고 재해싱을 하게 된다.

 

 

 

---

 

 

우선 Map이란

Maps are associative containers that store elements formed by a combination of a key value and a mapped value, following a specific order.

 

일반적으로 맵에서 key를 찾아서 value를 반환하는 형식이다.

In a map, the key values are generally used to sort and uniquely identify the elements, while the mapped values store the content associated to this key.

 

그리고 일반적으로

map containers are generally slower than unordered_map containers to access individual elements by their key, but they allow the direct iteration on subsets based on their order.

물론 키로 접근하는 방식이 unodered map보단 느리지만

직접 접근이 가능해서 쓰나보다.

 

이 map의 property는

 

Associative

Elements in associative containers are referenced by their key and not by their absolute position in the container.

원소가 다른 컨테이너와 달리 index같은 절대적 위치보다는 key로 참조하는 것이다.

 

Ordered

The elements in the container follow a strict order at all times. All inserted elements are given a position in this order.

정렬되어있지만 key로 정렬되어 있다.

 

Map

Each element associates a key to a mapped value: Keys are meant to identify the elements whose main content is the mapped value.

 

key는 구분해주는 것이고 우리가 쓰고자하는 것은 value다.

 

Unique keys

No two elements in the container can have equivalent keys.

 

중복을 허용하지 않는다.

즉, 같은 key를 가지는 것을 허용하지 않는다.

 

-> 키값을 중복하고 싶다면 multimap이라는 것이 있다.

 

Allocator-aware

The container uses an allocator object to dynamically handle its storage needs.

 

동적으로 메모리를 확보한다.

 

---

 

기본적인 함수는

 

iterator(반복자)

• begin(): beginning iterator를 반환
• end(): end iterator를 반환

 

Insert& Update & Delete

• insert( make_pair(key,value) ): 맵에 원소를 pair 형태로 추가
• erase(key): 맵에서 key(키값)에 해당하는 원소 삭제
• clear(): 맵의 원소들 모두 삭제

 

사실 맵에선 삽입과 삭제가 중요한 것 같다.

그래서 조금 더 자세히 보려고 한다.

삽입 4가지

(1)번이 가장 흔하게 사용하는 예이다.

 

예시

// map::insert (C++98)
#include <iostream>
#include <map>

int main ()
{
  std::map<char,int> mymap;

  // first insert function version (single parameter):
  mymap.insert ( std::pair<char,int>('a',100) );
  mymap.insert ( std::pair<char,int>('z',200) );

  std::pair<std::map<char,int>::iterator,bool> ret;
  ret = mymap.insert ( std::pair<char,int>('z',500) );
  if (ret.second==false) {
    std::cout << "element 'z' already existed";
    std::cout << " with a value of " << ret.first->second << '\n';
  }

  // second insert function version (with hint position):
  std::map<char,int>::iterator it = mymap.begin();
  mymap.insert (it, std::pair<char,int>('b',300));  // max efficiency inserting
  mymap.insert (it, std::pair<char,int>('c',400));  // no max efficiency inserting

  // third insert function version (range insertion):
  std::map<char,int> anothermap;
  anothermap.insert(mymap.begin(),mymap.find('c'));

  // showing contents:
  std::cout << "mymap contains:\n";
  for (it=mymap.begin(); it!=mymap.end(); ++it)
    std::cout << it->first << " => " << it->second << '\n';

  std::cout << "anothermap contains:\n";
  for (it=anothermap.begin(); it!=anothermap.end(); ++it)
    std::cout << it->first << " => " << it->second << '\n';

  return 0;
}

////////////////////////////////////////////////

element 'z' already existed with a value of 200
mymap contains:
a => 100
b => 300
c => 400
z => 200
anothermap contains:
a => 100
b => 300

 

 

 

삭제 3가지

 

예시

// erasing from map
#include <iostream>
#include <map>

int main ()
{
  std::map<char,int> mymap;
  std::map<char,int>::iterator it;

  // insert some values:
  mymap['a']=10;
  mymap['b']=20;
  mymap['c']=30;
  mymap['d']=40;
  mymap['e']=50;
  mymap['f']=60;

  it=mymap.find('b');
  mymap.erase (it);                   // erasing by iterator

  mymap.erase ('c');                  // erasing by key

  it=mymap.find ('e');
  mymap.erase ( it, mymap.end() );    // erasing by range

  // show content:
  for (it=mymap.begin(); it!=mymap.end(); ++it)
    std::cout << it->first << " => " << it->second << '\n';

  return 0;
}
///////////////////////////////////////////
a => 10
d => 40

 

 

Read

• find(key): key(키값)에 해당하는 iterator를 반환
• count(key): key(키값)에 해당하는 원소들(value들)의 개수를 반환

 

나머지

• empty(): 맵이 비어있으면 true 아니면 false를 반환
• size(): 맵 원소들의 수를 반환

 

 

key,value가 쌍으로 붙어다니기 때문에

make_pair() 함수를 많이 쓴다.

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main(){

	// map
	// <string, int> => <key, value>
	map< string, int > m;


	// insert(key,value)
	m.insert(make_pair("a", 1));
	m.insert(make_pair("b", 2));
	m.insert(make_pair("c", 3));
	m.insert(make_pair("d", 4));
	m.insert(make_pair("e", 5));
	m["f"] = 6; // also possible


	// erase(key)
	m.erase("d");
	m.erase("e");
	m.erase(m.find("f")); // also possible


	// empty(), size()
	if(!m.empty()) cout << "m size: " << m.size() << '\n';


	// find(key)
	cout << "a: " << m.find("a")->second << '\n';
	cout << "b: " << m.find("b")->second << '\n';


	// count(key)
	cout << "a count: " << m.count("a") << '\n';
	cout << "b count: " << m.count("b") << '\n';


	// begin(), end()
	cout << "traverse" << '\n';
    // map< string, int >::iterator it; also possible
	for(auto it = m.begin(); it != m.end(); it++){
		cout << "key: " << it->first << " " << "value: " << it->second << '\n';
	}

	return 0;

}

 

 

음.. 그렇다면

왜 굳이 map을 쓰느냐??

 

associative container라서

맵은 많은 자료를 가지고 있어도 이진탐색트리 기반이어서 검색속도가 빠르다.

빈번하게 삽입, 삭제하지 않는다면 유리하다.

또한 key로 자동정렬되어 유용하다.

다만 이 맵의 장점이 부각되려면 자료가 아주 많아졌을 때 빛을 발한다.

 

 

 

http://www.cplusplus.com/reference/map/map/