[STL] map

연관 컨테이너(Associative Containers)

연관 컨테이너(Associative Containers)는

데이터를 저장할 때 각 요소의 키(key)와 값(value)을 쌍(pair)으로 저장한다

이러한 키와 값의 쌍은 서로 연관되어 있으며, 키를 사용하여 값을 빠르게 검색할 수 있다

대표적으로는 map, set 등이 있다

 

Sequence Contaioners vs. Associative Containers

시퀀스 컨테이너는 특정한 데이터를 찾고 탐색하는 경우에

모든 데이터를 순회해야 하기 때문에 시간이 오래 걸린다는 단점이 있다

 

반면에, 연관 컨테이너는 데이터의 삽입과 삭제를 하는 과정에서

정렬을 해야해서 조금 효율이 안 좋더라도

데이터를 찾는, 탐색하는 과정이 매우 빠르다는 장점이 있다


map이란?

map은 균형이진트리(AVL)이다
이진트리 중에서도 좌우의 균형을 맞춰주는 형태를 맞춰주기에

균형이진트리라고 한다

map에서 노드는 아래와 같은 간단한 형태로 구성되어 있다

Class Node
{
public:
    Node* left;
    Node* right;
        
    pair<int, Player*> data;// key와 value의 pair
}

map 간단한 사용법

1) erase()

다양한 종류의 오버로딩 있지만

key값을 인자로 받으면,

key값을 탐색 후 해당 데이터를 삭제한다

 

반환하는 값으로는 size_t로 뱉어준다

size_t는 unsigned int형태이다
map에 해당하는 key값이 있어서 지웠다면, 1

map에 해당하는 key값이 없어서 지울 필요도 없었다면, 0

을 반환한다

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

void main(void)
{
	map<int, int> m;
	
	for (int i = 0; i < 100; i++)
	{
		// pair의 자료형을 직접 적는 방식
		m.insert(pair<int, int>(i, i * 1000));
		
		// pair의 자료형을 생략한 방식
		//m.insert(make_pair(i, i * 1000);
	}

	size_t erase_true = m.erase(1);// 1이 반환
	size_t erase_false = m.erase(1);// 이미 지워졌기에 0이 반환
}

2) find()
해당하는 key값을 찾고

찾았다면, 해당하는 key의 주소를 반환하고

없다면, m.end()를 반환한다

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

void main(void)
{
	map<int, int> m;
	
	for (int i = 0; i < 100; i++)
	{
		// pair의 자료형을 직접 적는 방식
		m.insert(pair<int, int>(i, i * 1000));
		
		// pair의 자료형을 생략한 방식
		//m.insert(make_pair(i, i * 1000);
	}

	map<int, int>::iterator findIt = m.find(50);
	if (findIt != m.end())
		cout << "찾음" << endl;

	else
		cout << "못찾음" << endl;

}

 

3) insert()
key는 중복이 되지 않는다

따라서 key가 있는 경우에 value를 또 insert 하면

해당 부분은 무시가 된다 (덮어쓰기가 되지 않는다)

 

반환하는 값으로는

pair<map<int, int>::iterator, bool> 형태로

iterator와 bool을 한 쌍으로 묶은 형태이다
first는

데이터의 iterator

second는

정상적으로 처리되면, 1

중복 키를 입력받아 비정상적으로 처리되면, 0

을 반환한다

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

void main(void)
{
	map<int, int> m;
	
	for (int i = 0; i < 100; i++)
	{
		// pair의 자료형을 직접 적는 방식
		m.insert(pair<int, int>(i, i * 1000));
		
		// pair의 자료형을 생략한 방식
		//m.insert(make_pair(i, i * 1000);
	}

	pair<map<int, int>::iterator, bool> insert_true = m.insert(make_pair(1, 100));
	pair<map<int, int>::iterator, bool> insert_false = m.insert(make_pair(1, 200));

}

4) map 순회

일반적인 컨테이너들처럼

순회를 하면서 접근이 가능하고

iterator의 first와 second를 통해서 key와 value값에 접근할 수 있다

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

void main(void)
{
	map<int, int> m;
	
	for (int i = 0; i < 100; i++)
	{
		// pair의 자료형을 직접 적는 방식
		m.insert(pair<int, int>(i, i * 1000));
		
		// pair의 자료형을 생략한 방식
		//m.insert(make_pair(i, i * 1000);
	}

	for (map<int,int>::iterator it = m.begin(); it != m.end(); ++it)
	{
		pair<const int, int>& p = (*it);
		int key = it->first;
		int value = it->second;
	}

}

5) 없으면 추가, 있으면 수정 ( [] 문법 )

직접 상황에 맞게 구현한 수동버전과

"[]" 문법을 이용하는 버전이 있다

 

[] 문법을 사용할 때는 주의점이 있다

"없으면 추가, 있으면 수정"이라는 용도로

사용되는 문법이기 때문에

[]를 사용한다면, 굳이 해당 문법과 대입 연산자를 같이 사용하지 않더라도

단독적으로 Key/Value 형태의 데이터가 추가된다는 것이다

Value는 기본적으로 0이 들어가게 된다

 

이처럼 찾기 위한 용도로 사용하면 생각과는 다른 결과가 나올 수 있다

예를 들어,
아래의 코드에서

i라는 key값이 m에 있는지 찾으려고 작성한 해당 부분이
for문을 돌면서 해당 key의 value가 0으로 된 데이터가 추가된다는 것이다

따라서, 

단순히 있는지 없는지는 find를 활용하고
기본값(0)으로 데이터가 추가되는 것이 상관없는 경우에는 [] 문법 버전을 써도 된다

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

void main(void)
{
	map<int, int> m;
	
	for (int i = 0; i < 100; i++)
	{
		// pair의 자료형을 직접 적는 방식
		m.insert(pair<int, int>(i, i * 1000));
		
		// pair의 자료형을 생략한 방식
		//m.insert(make_pair(i, i * 1000);
	}

	// 수동 버전
	map<int, int>::iterator insertOrModifyIt = m.find(10);
	if (insertOrModifyIt != m.end())
		insertOrModifyIt->second = 200;
	else
		m.insert(10, 200);

	// [] 문법 버전
	m[10] = 200;
	
   
	m.clear();// m을 지워서 뒤에서 데이터가 추가되는지 확인하기 위한 코드
    
	for (int i = 0; i < 10; i++)
	{
		cout << m[i] << endl;
	}

}

 

 

사용법 총정리

넣고 insert, []
빼고 erase
찾고 find, []
반복자는 pair형태로 뱉어준다는 것을 명심하다