📌 연관 컨테이너
-
정렬 규칙에 따라 원소가 컨테이너에 정렬되어 저장된다.
-
연관 컨테이너는 모두 노드 기반으로 작용
-
모든 연관 컨테이너들은 같은 인터페이스를 제공한다. (생성자, 멤버 함수, 연산자)
✅ 연관 컨테이너 정리
| 분류 | 컨테이너 종류 | 내부 구조 | 정렬 여부 | 시간복잡도 (탐색/삽입/삭제) |
|---|---|---|---|---|
| 트리 기반 | set, map, multiset, multimap | 🔺 균형 이진 탐색 트리 (Red-Black Tree) | ✅ 자동 정렬 | O(log N) |
| 해시 기반 | unordered_set, unordered_map, unordered_multiset, unordered_multimap | 📦 해시 테이블 | ❌ 정렬되지 않음 | 평균 O(1), 최악 O(N) |
✅ 연관 컨테이너들 특징
| 컨테이너 | 특징 |
|---|---|
set | 중복된 값을 저장할 수 없음 ➡ key만 저장 |
map | 중복된 값을 저장할 수 없음 ➡ key, value로 저장 |
multiset | 중복된 값 저장 가능 ➡ key만 저장 |
multimap | 중복된 값 저장 가능 ➡ key, value로 저장 |
📌 연관 컨테이너 주요 인터페이스
| 범주 | 함수 이름 | 설명 |
|---|---|---|
| 삽입 | insert(val) | 원소를 삽입 (set, map: 중복 불가 / multi*: 중복 허용) |
insert(pos, val) | 힌트를 사용한 삽입 (성능 최적화 가능) | |
insert(first, last) | 반복자 구간 삽입 | |
| 삭제 | erase(key) | 해당 key를 삭제 |
erase(iterator pos) | 반복자 위치 삭제 | |
erase(first, last) | 반복자 구간 삭제 | |
clear() | 전체 요소 삭제 | |
| 탐색 | find(key) | key를 가진 요소를 찾음 (iterator 반환) |
count(key) | 해당 key의 개수 반환 (set은 0 or 1, multi*는 ≥0) | |
contains(key) (C++20) | key 존재 여부를 bool로 반환 | |
| 범위 조회 | lower_bound(key) | key 이상인 첫 번째 위치 |
upper_bound(key) | key 초과인 첫 번째 위치 | |
equal_range(key) | lower_bound와 upper_bound를 pair로 반환 | |
| 기타 | size() | 요소 개수 반환 |
empty() | 컨테이너가 비었는지 확인 | |
begin(), end() | 반복자 시작/끝 반환 | |
rbegin(), rend() | 역방향 반복자 반환 | |
swap(other) | 다른 컨테이너와 내용 교환 |
📌 set
컨테이너에 중복없이 원소(Key)를 삽입하는 컨테이너
✅ 원소 삽입 insert()
-
insert()에 의해 삽입된 원소는 자동 정렬된다.
-
중복된 값을 허용하지 않기 때문에 중복된 값을 insert()하게 될 경우 삽입에 실패
-
set :: insert()는 실제로 삽입된 위치(반복자) & 삽입 성공 여부(bool)을 반환함.
-
다른 종류의 자료구조 모두 삽입이 가능하다. 반복자 타입을 넣으면 된다.
➡ 단, 리스트의 splice는 불가능
❓ 왜 리스트의 splice는 불가능할까?
➡ 리스트의 splice는 노드 자체를 포인터로 잘라서 붙이는 것. set는 본인만의 정렬 규칙이 존재하기 때문에 (균형 이진 트리) 잘라와서 붙일 수 없고, 무조건 insert()로 정렬 삽입 해야한다.
|--- pair를 통해서 확인해보기 ---|
❓ pair란?
두 개의 값을 하나의 객체로 묶는 자료형
- insert()는 아래의 코드 처럼 삽입 할 요소만 넣을 수도 있고, 원하는 위치를 찾아서 그 위치부터 탐색을 시작하고 삽입 할 수도 있다.
- 반복자 범위를 넣어서 요소를 삽입 할 수도 있다.
➡ 이 경우엔, 리스트의 splice는 불가능
✅ 정렬 기준 조건자
템플릿에 정의된 정렬 기준 조건자 (함수 객체)를 반환하는 key.comp() / value.comp()
➡ set은 key, value의 타입이 동일하다. key가 곧 value
✅ 원소 검색 find()
원소(key)를 검색하여 key를 가리키는 반복자를 반환
find()의 내부 구조에서는 찾는 값이 이 원소가 맞는지를 연산할 때, == 을 사용하지 않는다
➡ 정렬 기준에 의해 원소가 정렬되어 있으니까, 정렬 기준 조건자를 이용해 찾기 연산을 수행
➡ == 연산자를 사용하지 않기 때문에 정렬 기준 조건자를 사용 시, a가 b보다 앞서 있지 않고, b도 a보다 앞서 있지 않다면 a와b는 같다고 판단.
✅ 순차열 구간 (반복자 쌍) 반환
lower_bound() / upper_bound()
➡ find()로 찾은 원소의 반복자 구간으로 반환하는 멤버 함수
➡ 중복 원소를 허용하지 않는 set에서는 큰 의미가 있진 않으니 간단하게 보고 가자
✅ equal_range(찾고자 하는 값)
반복자 쌍을 한꺼번에 반환하는 멤버 함수
➡ lower_bound() & upper_bound();
❓ auto란?
타입 자동 추론 키워드
➡ C#의 var와 유사함
🏆 Set 특징 총정리
-
노드 기반의 연관 컨테이너 . 특정 정렬 기준에 의해 자동정렬
-
균형 이진 트리 기반으로 원소 찾기의 시간복잡도 logN
-
push , pop 인터페이스 제공x / 삽입은 무조건 insert()로 정렬 삽입
-
양방향 반복자를 지원하며 멤버 함수 begin(), end(), rbegin(), rend()는 지원하지만, 첫 원소와 마지막 원소의 참조를 반환하는 front()와 back() 멤버 함수는 제공하지 않음
📌 multiset
중복 원소를 허용한다는 점을 제외하고는 set과 동일하다.
아래는 multiset의 몇가지 멤버 함수
예시) insert(), count(), find()
📌 map
연관 컨테이너 중 자주 사용하는 컨테이너. 원소를 key와 value의 쌍으로 저장함.
set처럼 원소의 key는 컨테이너에 중복으로 저장될 수 없다.
연관컨테이너 이므로 key값을 기준으로 자동 정렬
✅ 템플릿 형식
ex) map<key, value, Compare> maps;
template <
class Key, // 키 값
class T, // 벨류 값
class Compare = std::less<Key>, // 정렬 기준 조건자
class Allocator = std::allocator<std::pair<const Key, T>>
> class map;✅ insert()
✅ insert()로 값 삽입
map의 반복자 iterator가 operator -> 를 오버로딩 한 상태이기에 사용 가능
✅ insert()로 삽입 성공 여부 확인
✅ [ ] 를 사용하여 값 추가
🏆 Map 특징 총정리
- set의 특징과 같다
📒 추가적인 특징
-
원소가 key와 value의 쌍으로 이루어져있다.
-
[ ]연산자를 이용해 원소를 추가하거나 참조를 반환할 수 있다.
📌 multimap
중복 원소를 허용한다는 점을 제외하고는 map과 동일하다.
아래는 multimap의 중복 키를 검색하는 예시)
#include <iostream>
#include <map>
using namespace std;
int main()
{
multimap<int, int> mm;
mm.insert(pair<int, int>(5, 100));
mm.insert(pair<int, int>(3, 100));
mm.insert(pair<int, int>(3, 100));
mm.insert(pair<int, int>(8, 30));
mm.insert(pair<int, int>(5, 100));
// 반복자를 담을 변수
multimap<int, int>::iterator lower_iter;
multimap<int, int>::iterator upper_iter;
lower_iter = mm.lower_bound(3); // 시작 반복자
upper_iter = mm.upper_bound(3); // 끝 반복자
pair<multimap<int, int>::iterator, multimap<int,int>::iterator> iter_pair;
iter_pair = mm.equal_range(3); // 반복자 쌍을 반환함
cout << iter_pair.first->first << endl; // 반복자가 가리키는 key
cout << iter_pair.first->second << endl;// 반복자가 가리키는 value
}
