[C++] Map Container

1. map (#include <map>)

map의 특징

• 노드는 pair<key, value> 형태를 가진다. 
• 중복 제거
• 노드 기반으로 index 접근 불가
• Red-Black 트리 기반의 균형 이진 트리

 

Search: O(log n)

Insert: O(log n)

Delete: O(log n)

 

 

장점

• 삽입, 삭제, 검색과 같은 기본 작업 속도가 빠르다.
• 균형 이진 트리를 유지하는 방식이 Red-Black 트리 기반이기 때문에 오버헤드가 크진 않다.

 

단점

• Red-Black 트리의 노드 색상을 저장하기 위해 각 노드마다 1 bit의 추가 저장 공간이 요구된다.

 

multimap은 중복 허용인 map이라고 생각하면 된다.

unordered_map은 정렬이 아닌 map이라고 생각하면 된다.

unordered_multimap은 정렬이 아닌 multimap이라고 생각하면 된다.

 

※ unordered를 사용하기 위해선 #include <unordered_map> 추가

※ unordered_map은 hash table에 가깝다.

 

 

 

 

 

2. map 초기화 & 값 할당 및 참조

#include <iostream>
#include <map>

using namespace std;

int main(void)
{
    map<string, int> m;

    m.insert(make_pair("Alice", 100));
    m.insert(make_pair("Bim", 200));
    m.insert(make_pair("Coma", 300));
    m["Dalin"] = 500;

    map<string, int> m1(m.begin(), m.end());
    map<string, int> m2(m);
    map<string, int> m3 = m;

    for (auto iter = m.begin(); iter != m.end(); iter++)
        cout << iter->first << " | " << iter->second << '\n';
    for (auto item : m)
        cout << item.first << " | " << item.second << '\n';

    return 0;
}

map 초기화는 다른 container와 동일하게 iterator로 초기화할 수 있다.

여기서 알아야 할 점은 <key, value> 구조를 가지는 hash map이기 때문에

map["Dalin"] = 500 처럼 indexing을 통한 값 참조 및 할당이 가능하다!

 

 

 

 

3. map 정렬 기준 설정

struct cmp
{
    bool operator()(const int& a, const int& b) const
    {
        return a > b;
    }
};

int main(void)
{
    map<int, int> basic;

    basic.insert(make_pair(1, 200));
    basic.insert(make_pair(2, 400));
    basic.insert(make_pair(3, 300));
    basic[4] = 100;

    cout << "==========< basic >==========" << '\n\n';
    for (auto item : basic)
        cout << item.first << " | " << item.second << endl;

    map<int, int, greater<int>> greater_map(basic.begin(), basic.end());

    cout << "==========< greater_map >==========" << '\n\n';
    for (auto item : greater_map)
        cout << item.first << " | " << item.second << endl;

    map<int, int, cmp> custom_map(basic.begin(), basic.end());

    cout << "==========< custom_map >==========" << '\n\n';
    for (auto item : custom_map)
        cout << item.first << " | " << item.second << endl;
}

상황에 따라선 map의 정렬 기준을 변경할 수 있다.

가장 기본이 되는 방식은 first의 오름차순이다.

 

greater와 같은 정의된 정렬 방식은 항상 key에 대해서만 작동한다.

(추가 질문) 그렇다면 value에 대해서 어떻게 정렬할 수 있을까?!

 

A. vector<pair<key, value>>를 선언하여 custom sort를 진행한다.

 

bool pair_cmp(pair<int, int> a, pair<int, int> b)
{
    return a.second < b.second;
}

int main(void)
{
    map<int, int> basic;

    basic.insert(make_pair(1, 200));
    basic.insert(make_pair(2, 400));
    basic.insert(make_pair(3, 300));
    basic[4] = 100;

    vector<pair<int, int>> vec(basic.begin(), basic.end());
    sort(vec.begin(), vec.end(), pair_cmp);

    cout << "==========< value_sort_map >==========" << "\n\n";
    for (auto item : vec)
        cout << item.first << " | " << item.second << endl;

    return 0;
}

 

Map 정렬 기준을 Custom하기 위해선 Compare을 위한 구조체가 필요하다.

구조체 내부에 Key에 대한 Const Operator를 정의하면 된다.

 

위 코드의 결과는 다음과 같다.

 

 

 

 

 

4. map 관련 함수

begin(): 시작 iterator 반환

end(): 끝 iterator 반환

rbegin(): 끝 iterator를 시작점으로 지정

rend(): 시작 iterator를 끝 부분으로 지정

empty(): 현재 빈 상태인가에 대한 여부를 bool 형태로 반환

size(): 현재 저장되어 있는 요소 개수 반환

insert(): 값 삽입

erase(key or iterator): 값 삭제

find(key): key 탐색 (찾지 못하면 end iterator 반환)