C++ STL(Map)

Map이란

Key값과 Value값을가지고있는 Red-Black Tree의 자료구조이다.

 

Map의 특징

1. Map은 가지고 있는 값을 정렬한다.
2. 중첩된 key 값을 가질 수 없다.
3. 저장할 자료가 적을 때는 메모리 낭비와 오버헤드가 일어난다.

 

Map의 정의 및 삽입

void main()
{
    map<string, int> m;
 
    pair<string, int> p("A", 10);
    m.insert(p);
    m.insert(pair<string, int>("B", 20));
    cout <<  m.find("A")->second << endl;
    cout << m.find("B")->second << endl;
}

3행 : map의 정의 <key, value>로 저장된다 string의 key 값을 가지고 int의 value를 가진다.
5~6행 : map의 값 삽입 map은 pair를 객체로 저장한다.

pair은 구조체이다. 해당 구조체 안에는 first와 second가 존재하고 first에는 key값을 second에는 value값을 저장한다.
7행 : 임시 객체 활용

 

Map의 삽입

void main()
{
    map<string, int> m;
 
    m.insert(make_pair("A", 10));
 
    m.insert(map<string, int>::value_type("B", 20));
 
    m["C"] = 30;
 
    m.emplace("D", 40);
 
    m.insert({ "E", 50 });
}

3, 5, 7 행은 가장 기본적인 map의 삽입이다.

9행은 값은 삽입이 되나 만약 m["A"] = 30;을 해버리면 A의 값이 바뀌는 문제가 있어 잘 사용하지 않는다.

(프로그래머의 실수를 유발한다.)
또한 해당 값을 넣기 위해서는 항상 모든 값을 전부다 탐색하기 때문에 느리다.
모든 값을 탐색하고 해당 값이 없으면 그때야 객체를 생성한다.
11, 13행은 c++ 11에서 새롭게 추가된 문법이다.
11행 같은 경우에는 list와 vector에도 존재한다.

 

Map의 반복자

    map<string, int> m;
 
    m.emplace("C", 30);
    m.emplace("A", 10);
    m.emplace("B", 20);
    m.emplace("D", 40);
 
 
    for (auto iter = m.begin(); iter != m.end(); ++iter)
    {
        cout << iter->first << iter->second << endl;
    }

9행 : 반복자를 이용한 map의 순회이다.

10행 : 출력결과는 30, 10, 20, 40이 아닌 정렬하여 10, 20, 30 ,40으로 출력된다.

 

Map의 탐색

    map<string, int> m;
 
    m.emplace("C", 30);
    m.emplace("A", 10);
    m.emplace("B", 20);
    m.emplace("D", 40);
 
    auto iter = m.find("B");
    for (; iter != m.end(); ++iter)
    {
        cout << iter->second << endl;
    }

8행 : find(key)를 이용해서 B의 key값을 찾는다. key를 찾으면 해당 반복자를 반환하게된다.

만약 해당 key를 찾지못하면 end()를 반환하게 된다.

11행 : B부터 시작해서 20, 30, 40 이출력된다.

 

find의 문제점

find는 단순 비교이다. 그렇기 때문에 문자열을 비교할 때 해당 문자를 비교하는 게 아닌 단순 주소를 비교한다.

    map<const char*, int> m;
 
    m.emplace("B", 20);
 
    char str[16] = "B";
    auto iter = m.find(str);
    if (iter == m.end())
    {
        cout << "탐색불가" << endl;
    }

해당 예제를 실행시키면 탐색 불가 출력될 것이다. 분명 str은 B이고 key 값 또한 B인데 말이다.
이유는 단순 비교인데 key의 저장 공간은 Data 영역 str의 문자열은 stack 영역이라 비교하게 되면
전혀 다른 값이기 때문이다.

 

이럴때는 알고리즘 함수인 find_if를 사용하여 해결할수있다.

class stringCMP
{
private:
    const char* m_pString;
public:
    stringCMP(char* _str) : m_pString(_str) {    }
 
public:
    template <typename T>
    bool operator()(T& _Dst)
    {
        return !strcmp(m_pString, _Dst.first);
    }
};
 
void main()
{
    map<const char*, int> m;
 
    m.emplace("B", 20);
 
    char str[16] = "B";
    auto iter = m.find(str);
 
    auto iter = find_if(m.begin(), m.end(), stringCMP(str));
 
    if (iter != m.end())
        cout << iter->first << ", " << iter->second << endl;
    else
        cout << "탐색 불가" << endl;
}

find_if는 무조건 단항 연산자 이어야 한다.

그렇기 때문에 해당 예제에서 2개의 문자를 비교해야 하는 예제의 경우에는 위의 방식으로 만들어야

여러 가지의 문자를 비교할 수 있다.

해당 코드를 실행하면 stringCMP에 str 값이 저장되고 해당 연산자 오버 로딩이 호출된다.

find_if의 시작과 끝 지점까지 해당 함수가 실행되면 처음부터 문자열 끝까지 보고 해당하는 반복자를

반환해 주게 된다.