set, multimap, multiset

전체 코드

---

📌 1. set, multimap, multiset 개요

C++의 set, multimap, multiset은 연관 컨테이너(Associative Containers) 중 하나로, 데이터를 자동 정렬하고 빠른 검색을 제공합니다.

✅ 1) set

• 데이터를 자동 정렬하며 중복을 허용하지 않는 컨테이너
• 내부적으로 이진 탐색 트리(Red-Black Tree) 구조 사용
• 탐색, 삽입, 삭제 모두 O(log n)의 시간 복잡도
• Key = Value (값 자체가 키 역할을 함)

✅ 2) multimap

• 중복 키를 허용하는 map 컨테이너
• 내부적으로 이진 탐색 트리(Red-Black Tree) 구조 사용
• 탐색, 삽입, 삭제 모두 O(log n)의 시간 복잡도
• 중복된 키를 저장할 수 있음 (반복자가 필요)

✅ 3) multiset

• 중복 값을 허용하는 set
• 내부적으로 이진 탐색 트리(Red-Black Tree) 구조 사용
• 탐색, 삽입, 삭제 모두 O(log n)의 시간 복잡도
• 동일한 값을 여러 개 저장할 수 있음

---

📂 2. 코드 분석 (set, multimap, multiset)

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

• #include <map> → std::map, std::multimap 사용
• #include <set> → std::set, std::multiset 사용

---

✅ 1) set 사용법

set<int> s;

• int 값을 저장하는 자동 정렬되는 set 생성

데이터 추가

s.insert(10);
s.insert(30);
s.insert(20);
s.insert(50);
s.insert(40);
s.insert(70);
s.insert(90);
s.insert(80);
s.insert(100);
s.insert(60);
s.insert(60); // 중복 허용 안됨

• set은 중복 데이터를 허용하지 않음
• insert(60)을 두 번 호출했지만 한 번만 저장됨

데이터 삭제

s.erase(40);

• 값이 40인 요소를 삭제
• 삭제 연산도 O(log n) (이진 탐색 트리에서 삭제)

데이터 검색

set<int>::iterator findIt = s.find(50);
if (findIt == s.end()) cout << "못 찾음" << endl;
else cout << "찾음" << endl;

• find(50)을 사용하여 특정 값을 찾음
• 없으면 end() 반환 → "못 찾음" 출력

전체 데이터 순회

for (set<int>::iterator it = s.begin(); it != s.end(); ++it)
    cout << (*it) << endl;

• begin()부터 end()까지 반복하여 모든 요소 출력
• 자동 정렬된 상태로 데이터가 출력됨

📢 주의! s[10] = 10; 같은 문법은 set에서 지원되지 않음

• set은 키를 기준으로 값이 저장되는 구조가 아님
• map과 달리 [] 연산자를 지원하지 않음

---

✅ 2) multimap 사용법

multimap<int, int> mm;

• 중복 키를 허용하는 multimap 선언
• Key와 Value를 저장하는 pair<int, int> 형태로 데이터를 저장

데이터 추가

mm.insert(make_pair(1, 100));
mm.insert(make_pair(1, 200));
mm.insert(make_pair(1, 300));
mm.insert(make_pair(2, 400));
mm.insert(make_pair(2, 500));

• Key 값이 1인 요소가 3개, Key 값이 2인 요소가 2개 추가됨
• 중복된 Key 값을 가질 수 있음 (기존 map과 차이점)

📢 주의! mm[1] = 500; 은 multimap에서 지원되지 않음

• operator[]는 map에서만 사용 가능
• multimap에서는 중복 키를 저장하기 위해 insert() 사용 필요

데이터 삭제

unsigned int count = mm.erase(1);

• Key 값이 1인 모든 요소 삭제
• 반환값: 삭제된 요소 개수

데이터 검색

multimap<int, int>::iterator findIt2 = mm.find(2);
if (findIt2 != mm.end()) cout << "찾음 " << findIt2->first << " " << findIt2->second << endl;
else cout << "못 찾음" << endl;

• Key 값이 2인 요소를 찾음
• 값이 있으면 Key-Value 출력

특정 Key 값의 모든 요소 검색 (equal_range())

pair<multimap<int, int>::iterator, multimap<int, int>::iterator> itPair;
itPair = mm.equal_range(2);

for (multimap<int, int>::iterator it = itPair.first; it != itPair.second; ++it)
    cout << it->first << " " << it->second << endl;

• equal_range(2) → Key 값 2에 해당하는 모든 요소의 범위 반환
• lower_bound(1), upper_bound(1) → 1의 첫 번째 요소, 마지막 요소의 다음 위치

---

✅ 3) multiset 사용법

multiset<int> ms;

• 중복 값 저장이 가능한 multiset 선언

데이터 추가

ms.insert(100);
ms.insert(100);
ms.insert(100);
ms.insert(200);
ms.insert(200);

• 100이 3개, 200이 2개 저장됨
• 중복 저장이 가능한 점이 set과 다름

데이터 삭제

ms.erase(200);

• 값이 200인 모든 요소 삭제
• erase()는 해당 값과 일치하는 모든 요소를 삭제함

데이터 검색

multiset<int>::iterator findIt3 = ms.find(100);

• 특정 값이 존재하는지 검색

특정 값의 모든 요소 검색 (equal_range())

pair<multiset<int>::iterator, multiset<int>::iterator> itPair2;
itPair2 = ms.equal_range(100);

for (multiset<int>::iterator it = itPair2.first; it != itPair2.second; ++it)
    cout << (*it) << endl;

• equal_range(100) → 100인 모든 요소의 범위 반환

---