C++ STL 정리 - Map

# Definition

: map 컨테이너는 연관 컨테이너의 한 종류로, 아래와 같이 정의되어 있다

template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T> >
> class map;

 

map 컨테이너는 key-value 형식의 데이터를 가지며, 

정렬의 기준이 되는 함수는 Compare 이며, 정렬의 기준 값은 value 가 아니라 Key 이다.

map 컨테이너도 set 과 마찬가지로 red-black tree 를 기반으로 하고 있다.

 

 

# Header

#include <map>

 

 

# Iterator

set 컨테이너와 마찬가지로 8가지가 존재한다

begin(), cbegin(), end(), cend(), rbegin(), crbegin(), rend(), crend()

#include <iostream>
#include <map>
#include <utility>
 
using namespace std;
 
int main() {
    map<int, string> m;
 
    map<int, string>::iterator iter;
 
    m.insert(make_pair(8, "apple"));
    m.insert(make_pair(4, "banana"));
    m.insert(make_pair(6, "mango"));
    m.insert(make_pair(2, "lemon"));
    // 키 값 기준으로 정렬되기 때문에 
    // m = ({2, "lemon"}, {4, "banana"}, {6, "mango"}, {8, "apple"}) 이 된다.
 
 
    cout << " ---- iterator ---- " << '\n';
    for (iter = m.begin(); iter != m.end(); iter++) {
        cout << iter->first << " " << iter->second << '\n';
    }
    // 출력결과 : 2 lemon, 4 banana, 6 mango, 8 apple
 
 
    map<int, string>::const_iterator citer;
 
    cout << " ---- const iterator ---- " << '\n';
    for (citer = m.cbegin(); citer != m.cend(); citer++) {
        cout << citer->first << " " << citer->second << '\n';
    }
    // 출력결과 : 2 lemon, 4 banana, 6 mango, 8 apple
 
 
    map<int, string>::reverse_iterator riter;
 
    cout << " ---- reverse iterator ---- " << '\n';
    for (riter = m.rbegin(); riter != m.rend(); riter++) {
        cout << riter->first << " " << riter->second << '\n';
    }
    // 출력결과 : 8 apple, 6 mango, 4 banana, 2 lemon
 
 
    map<int, string>::const_reverse_iterator criter;
 
    cout << " ---- const reverse iterator ---- " << '\n';
    for (criter = m.crbegin(); criter != m.crend(); criter++) {
        cout << criter->first << " " << criter->second << '\n';
    }
    // 출력결과 : 8 apple, 6 mango, 4 banana, 2 lemon
 
    return 0;
}

 

 

set 컨테이너와 마찬가지로 c 가 붙고 안붙고의 차이는 

const_iterator 를 반환하느냐 iterator 를 반환하느냐의 차이이다.

r 은 역으로 하느냐 아니냐의 차이.

 

출처 : https://en.cppreference.com/w/cpp/container/map/rbegin

 

 

# Capacity

#include <iostream>
#include <map>
#include <utility>
 
using namespace std;
 
int main() {
    map<int, string> m;
    
    cout << " map empty ? : " << m.empty() << '\n'; // 결과 : 1 (true)
    
    m.insert(make_pair(1, "good"));
    
    cout << " map empty ? : " << m.empty() << '\n'; // 결과 : 0 (false)
    
    int size = m.size();
    
    cout << " map size ? : " << size << '\n'; // 결과 : 1
    
    cout << " map max size ? : " << m.max_size() << '\n'; // 결과 : 3843.....
    
    return 0;
}

empty() 는 빈 컨테이너인지 확인하고,

size() 는 컨테이너 내부의 원소 갯수를 리턴하며,

max_size() 는 컨테이너가 가질 수 있는 최대의 원소 갯수를 리턴한다.

 

 

# Modifier

-1) insert, emplace

#include <iostream>
#include <map>
#include <utility>
 
using namespace std;
 
void print_map(auto s) {
    for (auto iter = s.begin(); iter != s.end(); iter++) {
        cout << iter->first << " " << iter->second << '\n';
    }
}
 
int main() {
    map<int, string> m2;
 
    m2.emplace(make_pair(99, "java"));
    m2.emplace(make_pair(22, "cobol"));
    // m2 = ({99, "java"}, {22, "cobol"})
 
    pair<map<int, string>::iterator, bool> Pair;
 
    Pair = m2.emplace(make_pair(33, "c"));
    cout << " ---- emplace result ---- " << '\n';
    cout << Pair.first->first << " " << Pair.first->second << " " << Pair.second << '\n'; // 출력 : 33 c 1(=true)
    cout << " ---- print_map(m2) ---- " << '\n';
    print_map(m2);
    
    cout << '\n';
    
    Pair = m2.emplace(make_pair(33, "c"));
    cout << " ---- emplace result ---- " << '\n';
    cout << Pair.first->first << " " << Pair.first->second << " " << Pair.second << '\n'; // 출력 : 33 c 0(=false)
    cout << " ----- print_map(m2) ---- " << '\n';
    print_map(m2);
    
    cout << '\n';
    m2.insert({55, "ruby"});
    m2.insert({23, "kotlin"});
    m2.insert(make_pair(43, "rust"));
    print_map(m2);
    
    return 0;
}

 

 

set 컨테이너와 마찬가지로 insert, emplace 둘다 값을 넣는 용도 이나,

 

emplace 의 리턴타입이 pair<iterator, bool> 이란점이 다르다.

iterator 는 emplace 를 해서 들어간 값의 위치정보를 담는 iterator 값이 들어있고,

bool 은 emplace 를 시도할때 중복된 값이 있었는지 없었는지에 따라 바뀌는 값이다.

 

 

-2) erase

#include <map>
#include <iostream>
int main()
{
    std::map<int, std::string> c = {{1, "one"}, {2, "two"}, {3, "three"},
                                    {4, "four"}, {5, "five"}, {6, "six"}};
 
    // erase all odd numbers from c
    for(auto it = c.begin(); it != c.end(); ) {
        if(it->first % 2 == 1)
            it = c.erase(it);
        else
            ++it;
    }
 
    for(auto& p : c) {
        std::cout << p.second << ' '; // 출력 : two four six
    }
}

 

cppreference 에서 그대로 가져온 코드로 (en.cppreference.com/w/cpp/container/map/erase) 

키 값이 2의 배수인 값만 살리고 나머지는 없애는 코드이다.

 

 

-3) clear, swap

#include <iostream>
#include <map>
#include <utility>
 
using namespace std;
 
void print_map(auto s) {
    if (s.empty()){
        cout << "empty" << '\n';
        return;
    } else {
        for (auto iter = s.begin(); iter != s.end(); iter++) {
            cout << iter->first << " " << iter->second << '\n';
        }
        cout << '\n';
    }
}
 
int main() {
    map<int, string> m2;
    
    m2.insert(make_pair(2, "graphql"));
    m2.insert(make_pair(1, "docker"));
    m2.insert(make_pair(6, "openAI"));
    m2.insert(make_pair(3, "openCV"));
    
    print_map(m2); // 출력 : 1 docker, 2 graphql, 3 openCV, 6 openAI
    
    m2.clear();
    
    print_map(m2); // 출력 : empty
    cout << '\n';
    
    map<int, string> m3 = { {44, "JQuery"}, {55, "Spring Boot"}, {66, "Kotlin"} };
    map<int, string> m4 = { {6, "kubernetes"}, {7, "Circle CI"} };
    
    cout << " ---- before swap ---- " << '\n';
    print_map(m3); // 출력 : 44 JQuery, 55 Spring Boot, 66 Kotlin
    print_map(m4); // 출력 : 6 kubernetes, 7 Circle CI
    
    
    m3.swap(m4);
    
    cout << " ---- after swap ---- " << '\n';
    print_map(m3); // 출력 : 6 kubernetes, 7 Circle CI
    print_map(m4); // 출력 : 44 JQuery, 55 Spring Boot, 66 Kotlin
    
    return 0;
}

 

 

 

 

-4) extract

#include <algorithm>
#include <iostream>
#include <map>
 
using namespace std;
 
int main()
{
    map<int, char> cont{{1, 'a'}, {2, 'b'}, {3, 'c'}};
 
    auto print = [](pair<const int, char>& n) { 
        cout << " " << n.first << '(' << n.second << ')'; 
    };
 
    cout << "Start:";
    for_each(cont.begin(), cont.end(), print);
    cout << '\n';
 
    // Extract node handle and change key
    auto nh = cont.extract(1);
    nh.key() = 4; 
 
    cout << "After extract and before insert:";
    for_each(cont.begin(), cont.end(), print);
    cout << '\n';
 
    // Insert node handle back
    cont.insert(move(nh));
 
    cout << "End:";
    for_each(cont.begin(), cont.end(), print);
    cout << '\n';
}

 

 

코드 출처 : en.cppreference.com/w/cpp/container/map/extract

 

set 컨테이너와 마찬가지로 특정 노드를 하나빼와서 키값을 바꾼뒤 다시 뒤에 넣어주는 코드이다.

(C++ 17 부터 가능하다)

 

 

-5) merge

#include <map>
#include <iostream>
#include <string>
 
using namespace std;
 
int main()
{
  map<int, string> ma {{1, "apple"}, {5, "pear"}, {10, "banana"}};
  map<int, string> mb {{2, "zorro"}, {4, "batman"}, {5, "X"}, {8, "alpaca"}};
  map<int, string> u;
  u.merge(ma);
  cout << "ma.size(): " << ma.size() << '\n';
  u.merge(mb);
  cout << "mb.size(): " << mb.size() << '\n';
  cout << "mb.at(5): " << mb.at(5) << '\n';
  for(auto const &kv: u)
    cout << kv.first << ", " << kv.second << '\n';
    
  // 출력 결과
  // ma.size(): 0
  // mb.size(): 1
  // mb.at(5): X
  // 1, apple
  // 2, zorro
  // 4, batman
  // 5, pear
  // 8, alpaca
  // 10, banana
}

코드 출처 : en.cppreference.com/w/cpp/container/map/merge

 

set 컨테이너와 마찬가지로 x.merge(y) 하면, x 에 x 와 y 간 합집합이 들어가고, y 에 교집합이 들어간다

그래서 위 코드에서 u.merge(ma) 를 하면 u 는 (1, apple), (5, pear), (10, banana) 가 들어가며, ma 는 없는 상태가 된다.

extract 와 마찬가지로 C++ 17 에서 부터 가능하다.

 

 

# LookUp

 

#include <iostream>
#include <map>
 
using namespace std;
 
void print_map(auto m) {
    for (auto iter : m) {
        cout << iter.first << " " << iter.second << '\n';
    }
}
 
int main()
{
    
    map<int, string> m;
    
    m.insert({1, "java"});
    m.insert({1, "c"});
    m.insert({1, "javascript"});
    
    m.insert({2, "gcp"});
    
    // count
    cout << m.count(1) << '\n'; // 출력 : 1
    
    
    // find
    map<int, string>::iterator it = m.find(2);
    cout << it->first << " " << it->second << '\n';  // 출력 : 2 gcp
    cout << '\n';
    
    m.insert({3, "azure"});
    m.insert({4, "AWS"});
    
    
    // lower_bound, upper_bound
    map<int, string>::iterator low = m.lower_bound(2);
    map<int, string>::iterator up = m.upper_bound(2);
    
    cout << low->first << " " << low->second << '\n'; // 출력 : 2 gcp
    cout << up->first << " " << up->second << '\n';   // 출력 : 3 azure
    cout << '\n';
    
    
    // equal_range
    pair<map<int, string>::iterator, map<int, string>::iterator> Pair = m.equal_range(3);
    
    for (auto& q = Pair.first; q != Pair.second; ++q) {
        cout << q->first << " " << q->second << '\n'; // 출력 : 3 azure
    }
    cout << '\n';
    
    
    // check begin
    pair<map<int, string>::iterator, map<int, string>::iterator> PPair = m.equal_range(-1);
    
    if (PPair.first == m.begin()) {
        cout << "PPair.first is iterator to first not-less than -1" << '\n'; // 출력
    } else {
        cout << "Unexpected PPair.first" << '\n';
    }
    cout << '\n';
    
    if (PPair.second == m.begin()) {
        cout << "PPair.second is iterator to first element greater than -1" << '\n'; // 출력
    } else {
        cout << "Unexpected PPair.second" << '\n';
    }
    cout << '\n';
    
    
    // check end
    pair<map<int, string>::iterator, map<int, string>::iterator> PPPair = m.equal_range(5);
    
    if (PPPair.first == m.end()) {
        cout << "PPPair.first is iterator to first not-less than 5" << '\n'; // 출력
    } else {
        cout << "Unexpected PPPair.first" << '\n';
    }
    cout << '\n';
    
    if (PPPair.second == m.end()) {
        cout << "PPPair.second is iterator to first element greater than 5" << '\n'; // 출력
    } else {
        cout << "Unexpected PPPair.second" << '\n';
    }
    
    return 0;
}
 

 

count(key) 는 키갑과 일치하는 원소의 갯수를 리턴하고,

find(key) 는 해당 key 값과 일치하는 iterator 를 리턴한다.

 

lower_bound(key) 는 키 값 보다 크거나 같은 값을 갖는 최초의 원소 부분에 대한 iterator 를 찾아서 리턴한다.

upper_bound(key) 는 키 값 보다 큰 값이 최초로 나오는 지점에 대한 iterator 를 리턴한다

 

equal_range(key) 는 리턴 형태가 pair<iterator, iterator> 인데, 

첫번째 iterator 는 lower_bound, 두번째 iterator 는 upper_bound 이다.

 

 

- Reference

1. en.cppreference.com/w/cpp/container/map