[C++/STL Container] map, set에 대해

 

 

vector밖에 모르는 나...의 보다 쾌적한 코딩 활동을 위해 map, set에 대해서 공부해보겠습니다.

 

vector VS map VS set

---

vector

정수 인덱스 사용, 값을 저장

 

map

키 인덱스 사용, 키-값 쌍을 저장, 빠른 검색.

 

set

중복 요소 허용X, 키 저장, 빠른 검색.

 

 

 

 

ordered map VS unordered map

---

ordered map (std::map)

: 키에 따라 정렬된 상태로 데이터 유지

: 이진 검색 트리(대부분의 구현에서는 레드-블랙트리)를 사용하여 구현

: 키에 대해 순서대로 반복하거나 특정 순서를 유지해야 할 때 유용

: 주요 연산(검색, 삽입, 삭제)은 로그 시간 복잡도 '0(log n)' 

 

unordered map (std::unordered_map)

: 해시 테이블을 사용하여 내부적으로 데이터 저장

: 해시 함수를 사용하여 키를 해시 값에 매핑 -> 해시 값을 인덱스로 사용하여 데이터 저장

: 상수 시간 복잡도 '0(1)'

: 최악의 경우 '0(n)'  (모든 값들의 해시 값이 같을 경우)

 

 

 

 

set VS unordered set

---

: 중복 허용X, 단일값 저장

 

ordered set (std::set)

: 정렬된 상태로 요소 저장

: 이진 검색 트리(대부분의 구현에서는 레드-블랙트리)를 사용하여 구현

: 중복을 허용하지 않고, 요소의 정렬 상태를 유지할 때 적합

: 주요 연산(검색, 삽입, 삭제)은 로그 시간 복잡도 '0(log n)' 

 

unordered set (std::unordered_set)

: 해시 테이블을 사용하여 요소들을 저장 ( unoredered_map과 같이 상수 시간 복잡도 )

: 주로 요소의 존재 유무를 빠르게 확인해야 할 떄 사용

(ex. 중복을 허용하지 않는 유니크한 데이터의 집합 관리,, 빠른 검색)

 

 

 

 

 

 

map, set의 단점

---

- 메모리 사용

: 이진 검색 트리(부모-자식 포인터, 색상 표시 등)와 해시 테이블(해시 버킷, 충돌 해결 메커니즘) 구현에서의 추가 메모리 요구 가능성이 있기 때문에 'vector'나 'array'와 같은 연속 메모리 기반 컨테이너에 비해 메모리 사용이 더 클 수 있다.

 

- 성능상의 고려사항

: unordered_set과 unordered_map의 경우, 해시 함수의 품질과 데이터의 분포에 따라 해시 충돌이 빈번하게 발생할 수 있다. 최악의 경우 시간 복잡도가 O(n)까지 증가할 수 있음

 

- 사용의 복잡성

: 키의 유니크함, 해시 함수, 충돌 해결 메커니즘 등 추가적인 고려 사항 때문에 사용이 복잡할 수 있음

 

 

 

 

 

기본 연산

---

< map >

#include <iostream>
#include <map>

int main(){
  std::map<std::string, int> m;

  //삽입
  m.insert(std::pair<std::string, int>("a",1));
  m["b"] = 2;

  //접근
  std::cout << "a: " << m["a"] << std::endl;

  //검색
  if(m.find("b") != m.end()){
    std::cout << "key b found" << std::endl;
  }

  //삭제
  m.erase("a");

  return 0;
}

 

 

< set >

#include <iostream>
#include <set>

int main(){
  std::set<std::string> s;

  //삽입
  s.insert("a");
  s.insert("b");

  //검색
  if(s.find("b") != s.end()){
    std::cout << "b is found" << std::endl;
  }

  //삭제
  s.erase("a");

  return 0;
}

 

 

 

< unordered map >

#include <iostream>
#include <unordered_map>

int main(){
  std::unordered_map<int, std::string> um;

  //삽입
  um[3] = "three";
  um.insert(1, "one");

  //접근
  std::cout << "3: " << um[3] << std::endl;

  //검색
  if(um.find(1) != um.end()){
    std::cout << "key 1 found" << std::endl;
  }

  //삭제
  um.erase(3);

  return 0;
}

 

 

< unordered set >

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> myUnorderedSet;

    // 삽입
    myUnorderedSet.insert(2);
    myUnorderedSet.insert(4);

    // 검색
    if (myUnorderedSet.find(2) != myUnorderedSet.end()) {
        std::cout << "2 is found" << std::endl;
    }

    // 삭제
    myUnorderedSet.erase(2);

    return 0;
}

 

 

 

 

익히기

백준: 10815, 14425, 1620, 10816, 1764, 1269

https://www.acmicpc.net/problem/15563

15563번: Äventyr 1

https://www.acmicpc.net/problem/2957

2957번: 이진 탐색 트리

https://www.acmicpc.net/problem/12757

12757번: 전설의 JBNU