[c++] std container2. 연관 컨테이너(Associative Container)

* 잘못된 내용에 대한 피드백은 언제나 환영입니다. *

 

멍하

멍정이에요.

오늘은 STL컨테이너 두번째 시간!

연관 컨테이너(Associative Container)에 대해 알아보아요!

 

연관 컨테이너에서 요소는 미리 정의된 순서(예: 오름차순 정렬)로 삽입됩니다. 순서가 지정되지 않은 연관 컨테이너도 사용할 수 있습니다. 연관 컨테이너를 맵 및 집합의 두 하위 집합으로 그룹화할 수 있습니다.
Microsoft Learn - STL 컨테이너 문서

 

말 그대로 컨테이너에 값을 넣을 때 정의된 순서를 따라서 삽입한다고 할 수 있습니다.

하나하나 천천히 살펴보아요.

 

map container

각 요소가 정렬 키와 데이터 값을 갖고 있는 쌍으로 삽입됩니다.

키 값은 고유하며(이미 값이 있는 경우에는 다시 삽입 불가) 키 값을 기준으로 데이터가 자동으로 정렬되어 삽입됩니다.

키 값은 변경할 수 없지만 데이터 값은 변경할 수 있습니다. 

-> 이진탐색트리 사용

자주 쓰는 map 멤버 함수

insert({key, val})	key와 val 쌍 삽입 (중복 X)	m.insert({"apple", 1});
[] (operator[])	key에 접근 및 할당 (없으면 생성됨)	m["banana"] = 2;
at(key)	key에 접근 (범위 검사 O)	m.at("apple");
find(key)	key의 반복자 반환 (없으면 end())	if (m.find("apple") != m.end())
erase(key)	key에 해당하는 요소 제거	m.erase("apple");
clear()	모든 요소 제거	m.clear();
size()	요소 개수	m.size();
empty()	비어있는지 확인	if (m.empty())
count(key)	key가 존재하면 1, 없으면 0	if (m.count("apple"))
begin()	첫 요소 반복자	auto it = m.begin();
end()	마지막 다음 반복자	auto it = m.end();
rbegin()	역방향 첫 반복자 (가장 큰 key부터)	auto it = m.rbegin();
rend()	역방향 마지막 다음 반복자	auto it = m.rend();
swap(m2)	다른 map과 내용 교환	m.swap(m2);

사용 예시

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

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

    m.insert({"apple", 3});
    m["banana"] = 5;

    if (m.count("apple")) {
        cout << "apple 있음, 개수: " << m["apple"] << '\n';
    }

    m.erase("apple");

    for (const auto& pair : m) {
        cout << pair.first << " : " << pair.second << '\n';
    }

    m.clear();
    if (m.empty()) cout << "map이 비었습니다\n";

    return 0;
}

---

 

unordered_map container

map과 동일하게 (key, value) 쌍의 형태로 값을 저장하지만, 해시 함수로 약하게 정렬됩니다.

같은 해시값을 갖는 key들은 버킷(bucket)에 정렬된 집합으로 분할됩니다.

-> key에 맞춰서 버킷이라는 배열을 생성한 느낌?

=> 해시 테이블이라는 특징 덕분에 탐색/삽입/삭제가 매우 빠르다. O(1)

-> 하지만 모든 값이 동일한 해시를 갖으면 O(n)의 속도가 된다.

 

-> 해시 테이블에 대한 공부가 더 필료하다,,,,

 

자주 쓰는 unordered_map 멤버 함수

insert({key, val})	key와 val 삽입 (중복 무시)	um.insert({"apple", 1});
um[key] = val	key에 val 할당 (없으면 생성)	um["banana"] = 2;
at(key)	key 접근 (없으면 예외)	int x = um.at("apple");
find(key)	key 반복자 반환 (end()와 비교)	if (um.find("apple") != um.end())
erase(key)	해당 key 삭제	um.erase("apple");
count(key)	존재하면 1, 없으면 0	if (um.count("apple"))
size()	요소 개수 반환	cout << um.size();
empty()	비어 있는지 확인	if (um.empty())
clear()	모든 요소 삭제	um.clear();
begin() / end()	순회용 반복자 (순서 보장 X)	for (auto it = um.begin(); it != um.end(); ++it)
swap(um2)	다른 unordered_map과 내용 교환	um.swap(um2);

 

사용 예시

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

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

    um["apple"] = 3;
    um["banana"] = 5;

    if (um.count("apple")) {
        cout << "apple 있음, 개수: " << um["apple"] << '\n';
    }

    um.erase("banana");

    for (const auto& pair : um) {
        cout << pair.first << " : " << pair.second << '\n';
    }

    return 0;
}

---

set container

중복 없이 값을 삽입하고(중복 시 삽입 x), 자동으로 정렬되어 저장한다.

 

자주 쓰는 set 멤버 함수

insert(val)	값 삽입 (중복은 무시됨)	s.insert("apple");
erase(val)	특정 값 제거	s.erase("apple");
find(val)	값의 반복자 반환 (없으면 end())	if (s.find("apple") != s.end())
count(val)	존재하면 1, 없으면 0 반환	if (s.count("apple")) cout << "있음";
size()	요소 개수 반환	cout << s.size();
empty()	비어있는지 여부 확인	if (s.empty())
clear()	모든 요소 삭제	s.clear();
begin()	첫 요소 반복자	auto it = s.begin();
end()	마지막 다음 반복자	auto it = s.end();
rbegin()	역방향 첫 반복자 (가장 큰 값)	auto it = s.rbegin();
rend()	역방향 마지막 다음 반복자	auto it = s.rend();
swap(s2)	다른 set과 내용 교환	s.swap(s2);

 

사용 예시

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

int main() {
    set<string> s;

    s.insert("apple");
    s.insert("banana");
    s.insert("apple"); // 중복 삽입 무시됨

    if (s.count("banana")) {
        cout << "banana 있음\n";
    }

    s.erase("banana");

    for (const auto& str : s) {
        cout << str << '\n';
    }

    s.clear();
    if (s.empty()) cout << "set이 비었습니다\n";

    return 0;
}

 

---

unordered_set container

정렬되지 않은 set으로 삽입/탐색/삭제 시 set보다 빠르고 효율적이다.

 

자주 쓰는 set 멤버 함수

insert(val)	요소 삽입 (중복 무시)	us.insert("apple");
erase(val)	특정 요소 제거	us.erase("apple");
find(val)	반복자 반환 (end()와 비교)	if (us.find("apple") != us.end())
count(val)	요소 존재 여부 (0 또는 1)	if (us.count("apple"))
size()	요소 개수 반환	cout << us.size();
empty()	비어 있는지 확인	if (us.empty())
clear()	모든 요소 삭제	us.clear();
begin() / end()	순회용 반복자	for (auto it = us.begin(); it != us.end(); ++it)
swap(us2)	다른 unordered_set과 내용 교환	us.swap(us2);

 

사용 예시

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

int main() {
    unordered_set<string> us;

    us.insert("apple");
    us.insert("banana");
    us.insert("apple"); // 중복 무시됨

    if (us.count("banana")) {
        cout << "banana 있음\n";
    }

    us.erase("banana");

    for (const auto& item : us) {
        cout << item << '\n'; // 순서는 랜덤
    }

    us.clear();
    if (us.empty()) cout << "set이 비었습니다\n";

    return 0;
}

---

map, unordered_map, set, unordered_set 비교

항목	map	unordered_map	set	unordered_set
🔧 내부 구조	이진 탐색 트리 (Red-Black Tree)	해시 테이블	이진 탐색 트리	해시 테이블
📚 헤더 파일	<map>	<unordered_map>	<set>	<unordered_set>
🕒 시간 복잡도 (탐색/삽입/삭제)	O(log n)	평균 O(1) 최악 O(n)	O(log n)	평균 O(1) 최악 O(n)
🔢 정렬 여부	✅ 자동 정렬 (key 기준 오름차순)	❌ 정렬되지 않음	✅ 자동 정렬	❌ 정렬되지 않음
🔁 순회 순서	오름차순	랜덤	오름차순	랜덤
📎 중복 허용	❌ key 중복 불가	❌ key 중복 불가	❌ 값 중복 불가	❌ 값 중복 불가
🎯 Key-Value 저장	✅ (pair<const Key, T>)	✅ (pair<const Key, T>)	❌ (key만 저장)	❌ (key만 저장)
🧪 [] 연산자 지원	✅ (m[key])	✅ (um[key])	❌	❌
🔄 반복자(Iterator) 안정성	삽입: 유지 삭제: 해당 요소만 무효	삽입: 유지 삭제: 해당 요소만 무효	삽입: 유지 삭제: 해당 요소만 무효	삽입: 유지 삭제: 해당 요소만 무효
🧰 커스텀 비교/해시	Compare 함수로 key 정렬 기준 설정 가능	hash 함수 오버라이딩 필요	Compare 함수로 정렬 기준 설정 가능	hash 함수 오버라이딩 필요
🧭 사용 목적	정렬된 key-value 저장	빠른 key-value 접근	정렬된 집합	빠른 집합 관리 (존재 여부 등)

지피티의 추천 가이드...

목적	추천 컨테이너
정렬된 key-value 저장	map
빠른 key-value 조회	unordered_map
정렬된 값의 집합	set
빠른 값 존재 여부 확인	unordered_set