map

map은 연관 컨테이너로, 노드 기반 컨테이너다.
map은 key-value 쌍을 원소로 저장한다.

인터페이스

map은 set이 제공하는 인터페이스를 동일하게 제공한다.
템플릿 형식과 멤버 함수의 형식 차이만이 조금 있다.

특히, [] 연산자를 이용하여 key에 해당하는 원소를 쉽게 접근하고 갱신할 수 있다.

원소의 삽입

map의 원소 삽입 연산은 기본적으로 set과 동일하게 작동한다.
하지만 map은 key-value 쌍을 원소로 가지기 때문에 pair를 사용해야 한다.

#include <iostream>
#include <map>

using namespace std;

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

    // pair 임시 객체를 이용하여 삽입할 수 있다.
    m.insert(pair<int, int>(1, 10));
    m.insert(pair<int, int>(2, 20));
    m.insert(pair<int, int>(3, 30));

    // pair 객체를 이용하여 삽입할 수 있다.
    pair<int, int> four(4, 40);
    pair<int, int> five(5, 50);
    m.insert(four);
    m.insert(five);

    for(map<int, int>::iterator iter = m.begin(); iter != m.end(); iter++)
        cout << "[ " << (*iter).first << ", " << (*iter).second << " ]" << ' ';
    cout << endl;
    
    // 반복자는 -> 연산자를 오버로딩하기 때문에
    // 포인터와 비슷하게 ->를 이용하여 원소를 역참조할 수 있다.
    for(map<int, int>::iterator iter = m_begin(); iter != m.end(); iter++)
        cout << "[ " << iter->first << ", " << iter->second << " ]" << ' ';
    cout << endl;
}

map의 insert()는 set과 똑같이 삽입한 원소를 가리키는 반복자와 성공 여부를 쌍으로 반환한다.
즉, insert()의 반환형은 pair<map::iterator, bool>이다.

#include <iostream>
#include <map>

using namespace std;

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

    m.insert(pair<int, int>(1, 10));
    m.insert(pair<int, int>(2, 20));
    m.insert(pair<int, int>(3, 30));
    m.insert(pair<int, int>(4, 40));
    m.insert(pair<int, int>(5, 50));

    // key가 6인 원소는 map 내부에 존재하지 않으므로 삽입에 성공한다.
    pair<map<int, int>::iterator, bool> pr = m.insert(pair<int, int>(6, 60));

    if(pr.second)
        cout << "60을 저장하는 데 성공했습니다:)" << endl;
    else
        cout << "60을 저장하는 데 실패했습니다:(" << endl;

    // 앞서 key가 6인 원소를 map 내부에 삽입했으므로 삽입에 실패한다.
    pair<map<int, int>::iterator, bool> pr = m.insert(pair<int, int>(6, 60));

    if(pr.second)
        cout << "60을 저장하는 데 성공했습니다:)" << endl;
    else
        cout << "60을 저장하는 데 실패했습니다:(" << endl;
}

[] 연산자

map은 임의 접근 반복자에서 사용하는 []과 의미가 다른 연산자 오버로딩을 가지고 있다.
[]을 이용하여 map에 새로운 key-value 쌍을 추가하거나 해당 key에 해당하는 value에 접근할 수 있다.

map은 해시 함수 기반이 아닌 균형 이진 트리 기반이므로 탐색에 O(log n)의 시간 복잡도를 보인다.

#include <iostream>
#include <map>

using namespace std;

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

    // [] 연산자를 이용하여 key-value 쌍을 map에 저장한다.
    m[1] = 10;
    m[2] = 20;
    m[3] = 30;
    m[4] = 40;
    m[5] = 50;

    for(map<int, int>::iterator iter = m_begin(); iter != m.end(); iter++)
        cout << "[ " << iter->first << ", " << iter->second << " ]" << ' ';
    cout << endl;

    // [] 연산자를 이용하여 원소를 갱신한다.
    m[5] = 500;

    for(map<int, int>::iterator iter = m_begin(); iter != m.end(); iter++)
        cout << "[ " << iter->first << ", " << iter->second << " ]" << ' ';
    cout << endl;
}

조건자 지정

map의 조건자를 명시적으로 지정하면 원소가 저장되는 정렬 순서를 변경할 수 있다.

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

using namespace std;

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

    m[1] = "one";
    m[2] = "two";
    m[3] = "three";
    m[4] = "four";
    m[5] = "fix";

    for(map<int, int>::iterator iter = m_begin(); iter != m.end(); iter++)
        cout << "[ " << iter->first << ", " << iter->second << " ]" << ' ';
    cout << endl;
}

정리

• map은 연관 컨테이너이자 노드 기반 컨테이너다.
• map은 key와 value를 묶은 pair를 원소로 가진다.
• map은 원소의 중복을 허용하지 않는다.
• map은 [] 연산자를 이용하여 key에 해당하는 원소에 접근할 수 있다.