map

map 은 기본적으로 레드블랙 트리(Red-Black Tree 이하 RB Tree) 기반으로 되어있습니다.

때문에 모든 데이터는 정렬되어 저장됩니다.

 

RB Tree는 검색속도가 빠른 Binary Search Tree(BST)에 Self-Balancing 기능을 추가한 것으로 AVL Tree만큼 엄격하진 않지만

O(logN)을 보장하는 수준으로 Balancing 되어지는 특징을 갖고 있습니다. 

 

이러한 특성 때문에 입력되는 키 값의 분포가 고르지 못할 경우 balancing(node rotation)에 대한 비용이 들기 때문에

Insert / Delete 성능이 저하될 수 있습니다. (물론 최악의 경우에도 O(logN)의 성능은 보장됩니다)

 

unordered_map

unordered_map은 hash_table 기반의 hash container입니다. 

 

hash_table을 통해 참조를 하기 때문에 각 node들을 정렬할 필요가 없습니다. 

따라서 충분한 hash_table의 크기만 주어진다면 데이터 양이 많아지더라도

Search / Insert / Delete 의 O(1) 성능을 꾸준하게 보장할 수 있습니다. 

 

 

 

 



출처: https://gracefulprograming.tistory.com/3 [Peter의 우아한 프로그래밍]

저작자표시

'STL > map' 카테고리의 다른 글

map 자주 쓰는 멤버함수 정리  (0) 2019.09.28

#include <map>

1. 기본형

  • map<key,value> : key와 value를 pair 형태로 선언, 각 key와 value에 사용할 type 선언

2. 반복자(iterator)

  • begin() : beginning iterator를 반환
  • end() : end iterator를 반환

3. 추가 / 삭제

  • insert(make_pair(key,value)) : 맵에 원소를 pair 형태로 추가
  • erase(key) : 맵에서 key(키값)에 해당하는 원소 삭제
  • clear() : 맵의 원소들 모두 삭제

4. 조회

  • find(key) : key(키값)에 해당하는 iterator 반환, iterator의 first, second 통해 key, value에 접근 -> 없으면 end() 반환
  • count(key) : key(키값)에 해당하는 원소들(value들)의 개수를 반환

5. 기타

  • empty() : 맵이 비어있으면 true 아니면 false를 반환
  • size() : 맵 원소들의 수를 반환

 

#include <iostream>
#include <map>
#include <string>
using namespace std;
 
int main()
{
    // 기본형 선언 
    map<string, int> m;
    
    // iterator 선언 
    map<string, int>::iterator it;
 
 
 
    // insert(key,value)
    m.insert(make_pair("a", 1));
    m.insert(make_pair("b", 2));
    m.insert(make_pair("c", 3));
    m.insert({"d", 4});
    m.insert({"e", 5});
 
    // 주로 사용하는 형태
    m["f"] = 6;
 
 
 
    // erase(key)
    m.erase("d");
    m.erase("e");
    m.erase(m.find("f")); 
 
 
 
    // empty(), size()
    if(!m.empty()) cout << "m size : " << m.size() << "\n";
 
 
 
    // find(key)
    cout << "a : " << m.find("a")->second << "\n";
    cout << "b : " << m.find("b")->second << "\n";
    // it = m.find("a");
    // cout << "a : " << (*it).second << "\n";
    // if(m.find("a") != m.end())을 통해 키값 유무 확인
 
 
    // count(key)
    cout << "a count : " << m.count("a") << "\n";
    cout << "b count : " << m.count("b") << "\n";
    // if(m.count("a") != 0)을 통해 키값 유무 확인
 
 
 
    // begin(), end()
    cout << "traverse" << "\n";
    
    // for(auto it = m.begin(); it != m.end(); it++)
    for(it = m.begin(); it != m.end(); it++)
    {
        cout << "key : " << it->first << " " << "value : " << it->second << "\n";
    }
 
    return 0;
}
   cs

 

출처 :

https://twpower.github.io/91-how-to-use-map-in-cpp

 

저작자표시

'STL > map' 카테고리의 다른 글

<map> vs <unordered_map> 차이  (0) 2020.03.31

+ Recent posts

티스토리툴바