Algorithm&DataStructure - Map, Set

1. (Ordered) Map

- key와 value 쌍으로 이루어진 트리구조이다. 항상 정렬된 상태를 유지한다.

- 따라서 탐색, 삽입, 삭제시 O(logn)의 복잡도를 갖는다.

- key의 중복을 허용하지 않는다.

- 따라서 동일한 키의 쌍의 삽입은 무시된다.

- 중복된 원소를 갖고 싶다면 multi map을 사용한다.

#include <map> 

map<string, int> ma;
 
ma.insert(make_pair("hi", 3));  

ma["hi"] = 10;

cout << ma.find("hi")->second << endl;

ma.erase("hi");
 
for (auto iter = ma.begin(); iter != ma.end(); ++iter) {
    cout << "key : " << iter->first << " value : " << iter->second << '\n';
}

2. Unordered Map

- (ordered) map과는 다르게 key-value쌍이 정렬된 트리구조가 아니라 해쉬 테이블로 구현되어있다.

- 따라서 탐색, 삽입, 삭제시 O(1)의 복잡도를 갖는다.

- 마찬가지로 key의 중복을 허용하지 않는다.

#include <unordered_map> 

unordered_map<string, int> ma;
 
ma.insert(make_pair("hi", 3));  

ma["hi"] = 10;

cout << ma.find("hi")->second << endl;

ma.erase("hi");
 
for (auto iter = ma.begin(); iter != ma.end(); ++iter) {
    cout << "key : " << iter->first << " value : " << iter->second << '\n';
}

if(s.find(30) != s.end()){
    cout << *iter << " : 존재 " << endl; 
}else{
    cout << "존재하지 않음 " << endl; 
}

3. Set

- key값을 가지는 노드들이 트리구조로 저장된다.

- 따라서 삽입, 탐색, 삭제 시 O(logn)의 복잡도를 갖는다.

- set은 중복된 key의 삽입을 허용하지 않는다.

- 중복된 값을 갖고 싶다면 multi set을 사용한다.

#include<set>
 
set<int> s;
 
s.insert(40);    
s.insert(10);
s.insert(80);
s.insert(30);
 
set.erase(30);

set<int>::iterator iter;
for(iter = s.begin(); iter != s.end(); iter++){
    cout << *iter << " " ;
}


iter = s.find(30);
if(iter != s.end()){
    cout << *iter << " : 존재 " << endl; 
}else{
    cout << "존재하지 않음 " << endl; 
}