map

key의 중복없이 정렬된 상태로 key-value 쌍을 저장하고, 랜덤한 인덱스의 데이터에 접근 불가

검색, 삽입, 삭제 - 시간 복잡도: O(logN)

선언

map은 key를 기준으로 오름차순 정렬

map<key_type, value_type> m;

• 내림차순으로 정렬하고 싶을 때 greater<key_type> 추가

map<key_type, value_type, greater<key_type>> m;

초기화

map<key_type, value_type> m = { {key1, val1}, {key2, val2}, ... };

삽입

// 방법 1
m.insert(pair<type1, type2>(key1, val1));

// 방법2
m.insert(make_pair(key1, val1));

// 방법3
m.insert({key1, key2});

원소 접근

// 방법 1
// C++17 이상에서만 사용 가능
for (const auto& [key, value] : cnt) {
    cout << key << " " << value << "\n";
}


// 방법 2
for (const auto& p : cnt) {
    cout << p.first << " " << p.second << "\n";
}

// 방법 3
for (auto it = cnt.begin(); it != cnt.end(); ++it) {
    cout << it->first << " " << it->second << "\n";
}

// 방법 4
cout << cnt["mike"]; // 없는 key면 자동으로 { "mike": 0 } 생성됨
// 조회 시 find문 추가하는 것이 안전
if (cnt.find("mike") != cnt.end()) {
    cout << cnt["mike"] << "\n";
}

// 방법 5
auto it = cnt.find("mike");
if (it != cnt.end()) {
    cout << it->first << " " << it->second << "\n";
}

// 방법 6
cout << cnt.at("mike");

unordered map

이진 탐색으로 자동 정렬되는 map과 달리 정렬을 적용하지 않음
map은 O(logN), unordered_map은 O(1)

map을 쓰면 좋은 경우

• 키를 정렬된 순서로 순회해야 할 때
• lower_bound, upper_bound 같은 정렬 기반 탐색이 필요할 때
• 메모리를 조금 더 아껴야 할 때

unordered_map을 쓰면 좋은 경우

• 정렬 필요 없고 빠르게 탐색해야 할 때

---

set

key를 중복없이 정렬된 상태로 저장하고, 랜덤한 인덱스의 데이터에 접근 불가

검색, 삽입, 삭제 - 시간 복잡도: O(logN)

삽입

set<int> s;
s.insert(x);

삭제

set<int> s;
s.erase(x);

검색

s.find() : 찾는 값이 있으면 해당 위치의 iterator 반환, 아니면 s.end()반환

set 순회

#include <iostream>
#include <set>
...
set<int> s;

//방법1
for(auto iter = s.begin(); iter != s.end(); iter++) {
	cout << *iter << " ";
}

for(auto iter : s) {
	cout << iter << " ";
}

count()

set에서 찾고자 하는 요소가 있으면 1, 없으면 0 반환

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {1, 2, 3, 4, 5};

    if (s.count(3)) cout << "3이 존재합니다!\n";
    if (!s.count(6)) cout << "6은 없습니다!\n";

    return 0;
}