map & set

vector,list,deque 컨테이너는 시퀀스 컨테이너라 하며 순서가 있는 것을 의미하낟.
map/set 검색과 중복 방지에 특화된 연관 컨테이너로 노드기반, 균형 이진 트리를 사용한다.
레드-블랙 트리로 구현되어 있다.

 

레드-블랙 트리 (Red-Black Tree)

 

map : key와 value 쌍을 저장하고 키를 통해 → 값을 빠르게 탐색 할 수 있는 자료 구조

set : 키만 저장하고 중복은 허용하지 않는 구조

map

• 키와 값을 한쌍으로 묶어서 관리
• 키는 유일해야 하고, 검색, 삽입, 삭제 가 평균 O(log N)
• 내부적으로 이진 탐색 트리(레드-블랙 트리)를 사용한다.
• ex) 전화번호부 , 이름 ,전화번호

set

• 키만 저장, 즉 value 가 따로 필요 없을때 사용
• 중복이 불가능, 이미 원소가 있다면 들어가지 않음
• O(log N) 내부구조는 map 과 동일, 단 키가 존재한다는 차이가 있음
• ex ) 콘서트 티켓명단, 이미 등록된 사람은 중복 불가, 누가 출입했는지 확인빠름

 

map 예제 코드

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> score;

    // 삽입
    score["rtan"] = 95;
    score["goong"] = 88;
    score.insert({"yeorerbun", 100}); 

    // 검색
    cout << "rtan 점수: " << score["rtan"] << endl; // 95
    cout << "goong 점수: " << score.at("goong") << endl; // 88

    // 원소 확인
    if (score.find("tom") == score.end()) {
        cout << "tom 기록 없음!" << endl;
    }

    // 수정
    score["goong"] = 90; // 값 변경 (기존 key가 존재하면 수정)

    // 전체 순회 (맵의 각 요소는 first, second로 접근 가능!)
    for (auto &kv : score) {
        cout << kv.first << "의 점수: " << kv.second << endl;
    }
}

set 예제 코드

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

int main() {
    set<int> s;

    // 삽입
    s.insert(5);
    s.insert(2);
    s.insert(9);
    s.insert(5); // 이미 5가 있으니 무시됨!

    // 원소 확인
    if (s.find(2) != s.end()) {
        cout << "2가 존재합니다!" << endl;
    }

    // 전체 순회
    for (auto &elem : s) {
        cout << elem << " "; // 2 5 9
    }
    cout << endl;

    // 삭제
    s.erase(5); // 5가 제거됨

    auto lb = s.lower_bound(2);//지정된 값 이상의 첫 번째 요소를 반환
    if (lb != s.end()) cout << "lower_bound(2) : " << *lb << endl; // 2
    
    auto ub = s.upper_bound(2);//지정된 값보다 큰 첫 번째 요소를 반환
    if (ub != s.end()) cout << "upper_bound(2) : " << *ub << endl; // 9
}