[C++] 연관 컨테이너 맵(map)

 

 

 

서론

 

순차열 컨테이너는 데이터 관리에 유용한 도구지만, 대다수 응용프로그램에서 순차열 컨테이너가 편리한 데이터 액세스 도구는 아니다. 이름과 주소를 관리하는 경우만 생각해봐도 순차열 컨테이너는 적합하지 않을 가능성이 크다. 이름으로 주소를 찾는 간단한 작업을 생각해보자 레코드가 순차 열에 저장되어 있다면 검색부터 해야 한다. map 컨테이너는 이런 종류의 데이터를 더 효율적으로 저장하고 접근할 수 있다.

 

맵 컨테이너는 연관 컨테이너라고 한다. 연관 컨테이너는 객체를 객체와 연관된 키 값으로 위치를 정한다. 키는 기본 타입의 값이 될 수도 있고, 클래스 타입의 객체가 될 수도 있다.  또한

맵은 균형 이진트리인(레드 블랙트리)로 구성된다.

 

맵(map) 컨테이너의 종류

 

맵 컨테이너는 네 가지가 있으며 각 컨테이너는 클래스 템플릿으로 정의되어 있다. 모든 map 컨테이너는 키/값 쌍을 저장한다. T 객체와 객체와 연관된 키 K를 캡슐화한 pair <const K, T> 타입 객체를 map 원소로 저장한다. 컨테이너의 pair 원소에서 키가 const인 이유는 수정을 허용하면 컨테이너 원소의 순차 열을 망가트릴 수 있기 때문이다. 각 맵 컨테이너의 특징은 다음과 같다.

• map <K, T>: 컨테이너는 키/객체 쌍을 캡슐화한 pair <const K, T> 타입을 원소로 저장하며 키는 반드시 유일해야 하고 중복 키는 허용되지 않는다. 키 값이 다르다면 중복 객체도 저장할 수 있다. 원소들은 정렬되어 있으며 컨테이너에서 원소들의 순서는 키를 비교해서 결정된다. 키는 less <K> 객체를 사용하여 비교한다.
• multimap <K, T>: 원소가 정렬된다는 점은 map가 일치하다. 키는 반드시 비교 가능해야 하고 원소들의 순서는 키를 비교해서 결정된다. map <K, T>와 차이점은 중복 키가 허용이 된다는 점이다.
• unordered_map <K, T>: 객체를 키 값으로 정렬하지 않는 맵이다. 키 값으로 생성된 해시 값을 사용해 위치가 정해진다. 해시 값은 해싱(hashing) 과정을 통해 생성된 정수 값이다. 중복 키는 허용하지 않는다.
• unordered_multimap <K, T>: 키를 생성한 해시 값을 사용해 객체 위치를 저장한다. 중복 키를 허용한다.

map과 multimap은 map헤더에 정의되어 있고 unordered_map과 unordered_multimap은 unordered_map에 정의되어 있다.

 

map에 앞에 붙어있는 접두어를 통해 해당 컨테이너의 특징을 알 수 있다.

• multi: 키가 유일하지 않아도 된다. 즉 multi 접두어가 없으면 키가 유일해야 한다는 뜻이다.
• unordered: 원소 위치를 키 값 비교가 아니라 키에서 생성한 해시 값으로 정한다는 뜻이다.

map 컨테이너의 비교 함수를 사용 시 주의사항

map이나 multimap의 비교 함수를 바꿔야 하는 두 가지 이유가 있다.

기본 오름차순 대신 내림차순으로 원소들을 정렬하고 싶거나

보다-작은(<)이나 보다-큰(>) 연산이 아닌 비교 함수로 키를 비교해야 할 때이다.

 

키를 비교하는 함수 객체에서 매우 중요한 요구사항은 다음과 같다.

map 컨테이너의 비교 함수는 상등 관계(equality)에 대해서는 true를 반환해서는 안 된다.

다시 말해서 <= 또는 >= 비교는 절대 사용하면 안 된다. 

map과 multimap 컨테이너는 키가 같은지(equal) 판단하기 위해 동등관계(equivalence)를 사용한다. 두 키 key1과 key2가 동등관계라면 두 키를 같은 것으로 간주한다. 따라서 표현식 key1 < key2와 key2 <key1은 모두 false가 된다. 바꿔 말하자면 동등관계는!(key <key2)&&!(key2 <key1)을 true로 평가한다는 뜻이다.

직접 만든 함수 객체가 <=를 구현하면 무슨 일이 벌어지는 생각 해보자. key1이 key2와 같을 때

key1 <=key2와 key2 <=key1은 true로 평가되므로!(key <=key2)&&!(key2 <=key1)은 false로 평가된다. 이는 컨테이너 관점에서 키가 같지 않다는 뜻이 된다. 즉, 두 키가 같은 것으로 결정되는 일은 없다는 뜻이다. 이는 컨테이너가 올바르게 동작하지 않을 수 있다는 뜻이기도 하다.

 

 

 

소스코드

 

맵은 텍스트에 각 단어가 얼마나 자주 등장하는지 알아보는 데 사용할 수 있다. 

#include<iostream>
#include<string>
#include<iomanip>
#include<map>
#include<algorithm>
#include<sstream>
#include<iterator>
int main() {
    std::string word{};
    std::size_t max_len{};
    std::map<std::string, size_t>words;
    
    std::cout << " *를 누르면 종료 \n";
    std::getline(std::cin, word, '*');
    
    //비알파벳 문자는 공백으로 치환한다.
    std::replace_if(word.begin(), word.end(), [](const auto& chr) {
        return !isalpha(chr);
    },' ');
 
    //텍스트 입력 문자열 스트림으로
    std::istringstream text(word);
    std::istream_iterator<std::string> begin(text);
    std::istream_iterator<std::string> end;
 
 
    std::for_each(begin, end, [&](const std::string word) {
        words[word]++;
        max_len=std::max(max_len, word.length());
    });
    
    std::size_t per_line{ 4 },count{};
    for (auto& i : words) {
        std::cout << std::left<<std::setw(max_len+1) << i.first
            << std::right<<std::setw(3) << i.second << " ";
        if (++count % per_line == 0)std::cout << std::endl;
    }
 
}

결과

결론

• 연관 컨테이너는 특히 이름과 전화번호처럼 서로 연관된 데이터를 항목을 다루는 곳에서 사용된다. 
• 일반적으로 비순차 맵 컨테이너(unordered)가 순차 맵 컨테이너보다 객체에 더 빠르게 접근한다.
• map <K, T>은 기본으로 보다-작은(<) 연산자를 사용해 키를 결정하며 키 타입은 별도로 비교 함수를 지정하지 않는 한 <연산자를 지원해야 한다.
• 정렬된 연관 컨테이너는 두 키가 같을 때를 동등관계(equivalence)로 결정한다. 동등관계로 결정하므로 키는           보다-작은(<)이나 보다-큰(>)으로만 비교할 수 있다. 키가 같을 때 true를 반환하는 비교 함수를 사용하면 올바르게 작동하지 않을 수 있다.
• 해싱은 객체에서 해시 값이라고 하는 어느 정도 유일한 정수 값을 생성하는 과정을 말한다. 해싱은 비순차 연관 컨테이너에서 원소를 어디에 저장할지 결정하는 용도로 쓰인다. 해싱은 암호화 분야에서도 중요하게 쓰인다.
• 비순차 맵 컨테이너에서는 equal_to <K>를 사용해 상등 관계(equality)를 비교하므로 키 타입은 반드시 ==비교와 키 객체의 해싱을 지원해야 한다.

출처 및 레퍼런스

Book: C++14 STL철저 입문 아이버 호튼, 조현태

 

20.04.22
소스코드 -> color Scripter, 글자 폰트 및 색상 변경