[Basic C++] #38_map, 연관 컨테이너

 

#1. 개념

 

1. map

• [정의] : C++의 STL에서 제공하는 map 컨테이너는 지정된 형식의 키와 데이터 값을 한 쌍으로 레드-블랙 트리 자료구조에 저장하는 연관 컨테이너입니다.
• [특징] : map 컨테이너는 오직 키를 통해 접근 가능합니다. 더불어, map 컨테이너는 내부적으로 정렬 작업을 수행하며, 기준은 오름차순입니다.
• [성능] : map 컨테이너의 탐색/삽입/삭제 작업은 모두 O(log n)의 시간 복잡도를 가집니다.

 

[Basic C++] #1 Map, Unordered_map, 해쉬 테이블

 

---

 

#2. 선언 및 초기화

 

1. 초기화 리스트

#include <map>
#include <string>

int main()
{

    map<int, string> m = 
    {
        { 1, "One" },
        { 2, "Two" }
    };

}

 

2. make_pair

#include <map>
#include <string>

int main()
{

    map<int, string> m = 
    {
        make_pair(1,"One"),
        make_pair(2,"Two")
    };

}

 

---

 

#3. 탐색 및 접근

 

1. 탐색

map<int, string> myMap;

for (auto it = myMap.begin(); it != myMap.end(); ++it)
{
    cout << it->second << endl;
}

or

for (const auto& data : myMap)
{
    cout << data.second << endl;
}

 

Details

 

map의 반복자는 순차 컨테이너의 것들과 비슷하게 동작합니다. 다만, map의 반복자는 값에 접근하는 것이 아니라 pair 객체에 접근합니다. 따라서, map을 순회하는 반복자는 최종적으로 pair 객체의 first 그리고 second 멤버에 접근합니다.* 이때, 특정 항목의 키 값을 변경하려고 시도하면 컴파일러가 에러를 발생시킵니다.

 

2. 접근

// 1. 찾고자 하는 항목의 키 값을 알고 잇는 경우

map< int, string > myMap = {	// 유니폼 초기화
	{1, "One"},
        {2, "Two"},
	{3, "Three"}
    };
    
cout << myMap[1] << endl;	// "One" 출력

// 2. 찾고자 하는 항목의 키 값을 모르는 경우

auto it = myMap.find(1);	// const_iterator find(Key): Key에 해당하는 항목을 가리키는 반복자를 반환합니다.
if(it != end(myMap))
	cout << it->second << endl;
    
// 3. 단순히 항목이 존재하는지 여부를 확인하고 싶은 경우

if(myMap.count(1) == 0)
	cout << "No Data Here!" << endl;
else
	cout << "Data is Here! << endl;

 

Details

 

1. operator[] : operator[]는 key를 통해 value에 접근합니다. 다만, 의도치 않은 새로운 항목이 생성될 수 있습니다.
2. find() : find()는 반복자를 반환하며, 의도치 않은 새로운 항목 생성 및 삽입을 방지합니다.

 

---

 

#3. 삽입/제거

 

1. insert()

/*
	pair<const_iterator, bool> insert({key, value} or pair<key, value> _inPair): 
    	key와 value를 삽입합니다.
        이때, 반환 값은 반복자와 bool형을 멤버로 갖는 pair 타입입니다.
*/

map<int, string> myMap;

// 1. initializer_list를 통한 항목 생성
auto ret = myMap.insert({5, "Five"});

if(ret.second == true)
	cout << "insertion was successful!" << "\n";
else
	cout << "insertion failed" << "\n";

// 2. make_pair를 통한 항목 생성
auto ret2 = myMap.insert(make_pair(6, "Six"));

if(ret2.second == true)
	cout << "insertion was successful!" << "\n";
else
	cout << "insertion failed" << "\n";

 

Details

 

map의 "insert()" 메서드는 다소 번거로운 삽입 방법입니다. 다만, "insert()" 메서드를 통해 우리는 중복된 키를 갖고 있는 항목을 찾을 수 있습니다. 특이한 점은 반환 값이 반복자와 bool 형의 pair라는 점입니다. 이때, 반복자는 삽입 성공 여부에 따라 달라집니다. 먼저, 삽입이 성공적으로 이루어졌다면, 새로 삽입한 항목을 가리키며 그렇지 않을 경우, 해당 키를 갖는 기존의 항목을 가리킵니다.bool 형의 경우 간단하게 삽입의 성공 여부를 나타냅니다.

 

2. operator []

map<int, String> myMap;

myMap[1] = "One";	// Key = 1, Data = "One"
myMap[1] = "Two";	// Key = 1, Date = "One" -> "Two" 로 변경

 

Details

 

두 번째 삽입 방법으로 "operator[]"가 있습니다."operator[]"를 사용할 경우, [] 사이에 키 값이 들어가고, 항목 값은 대입문의 우항에 위치합니다.물론, 이 삽입 방법은 실패가 없습니다. 왜냐하면, 이미 존재하는 키에 대해 값을 대입하면 새로운 항목으로 교체되기 때문입니다.

 

void func(const map<int, int>& m)
{
	cout << m[3] << endl;	// 에러 발생!!
}

 

Details

 

"operator[]"의 경우 "insert()"를 사용하는 것보다 비교적 비효율적입니다."operator[]"는 항상 새로운 값 객체가 생성되며, 위 코드와 같이 새로운 키로 접근하게 될 경우 "const"로 선언된 map 컨테이너는 오류를 발생시킬 수 있습니다!

 

3. erase()

map <int, string> myMap;

myMap[1] = "One";

myMap.erase(1);	// erase(Key): Key값에 해당하는 항목을 삭제합니다.

 

Details

 

map의 "erase()"는 인자로 받은 key 값에 해당하는 항목을 삭제합니다. 순차 컨테이너의 것과 같지만, map은 특별히 키에 기반해서 항목을 삭제할 수 있어 더욱 편리합니다.

 

---