[자료구조] C++ Container Library : Associative Containers - multiset & multimap

---

C++ 표준 라이브러리(STL)의 일부인 컨테이너 라이브러리 중 연관 컨테이너(Associative Containers) 자료구조 중 std::multiset과 std::multimap에 대해 정리한 글입니다.

(std::set과 std::map에 대해 알고 있다고 가정하고 정리하였습니다.)

[자료구조] C++ Container Library : Associative Containers - set & map

[자료구조] C++ Container Library : Associative Containers - set & map

---

📚 std::multiset

출처: Different Approaches to Initialize a Multiset in C++ ❘ by Pawara Gunawardena ❘ Medium

📖 std::multiset

👉 중복된 키(key)를 허용하면서 자동 정렬되는 컨테이너

• 내부 구조는 std::set과 동일하게 자가 균형 이진 탐색 트리(Self-Balancing Binary Search Tree, 일반적으로 Red-Black Tree로 구현)로 구성
• std::set과 달리 중복된 값(키, key)의 삽입을 허용
• 기본적으로 오름차순으로 정렬

📌 std::multiset 사용 예시 코드

#include <iostream>
#include <set>

using namespace std;

int main() {
  multiset<int> ms;

  ms.insert(3);
  ms.insert(1);
  ms.insert(3);
  ms.insert(2);

  for (int x : ms) cout << x << " "; // 출력 예시 : 1 2 3 3
  
  return 0;
}

---

📖 std::multiset의 주요 특징

• key의 중복을 허용
• 새로운 key가 삽입되면, 자동 정렬 (기본: 오름차순 정렬)
• 탐색, 삽입, 삭제 시 시간 복잡도 : $ O(\log N) $
• 임의 접근(random access) 불가능 ➡️ iterator를 이용한 탐색 및 접근

---

📖 std::multiset의 주요 함수

• insert(val) : 값(val) 삽입 (중복 허용)
• erase(val) : 해당하는 값(val) 모두 삭제
  • erase(iterator) : 특정 위치(iterator)의 값 하나 삭제
• count(val) : 해당 값(val)의 개수 반환
• find(val) : 해당 값(val) 중 첫 번째 위치 반환 (iterator)
• equal_range(val) : 동일한 값의 범위(iterator 쌍) 반환

📌 count() 함수 예제

#include <iostream>
#include <set>

using namespace std;

int main() {
  multiset<int> ms = {1, 3, 3, 5};

  cout << ms.count(3);  // 출력: 2

  return 0;
}

• std::set에서 count(val) 함수는 해당 값(val)의 존재 여부(0 또는 1)를 알려줬지만, std::multiset에서는 중복된 값의 개수를 반환

📌 equal_range() 함수 예제

#include <iostream>
#include <set>

using namespace std;

int main() {
  multiset<int> ms = {1, 3, 3, 5};

  auto range = ms.equal_range(3);

  for (auto it = range.first; it != range.second; ++it) {
    cout << *it << " ";  // 출력 : 3 3
  }

  return 0;
}

• equal_range()는 같은 값을 가지는 구간의 [start, end) iterator 쌍을 반환
• 중복된 원소를 모두 순회할 수 있는 방법

📌 erase() 함수 사용 시 주의사항

#include <iostream>
#include <set>

using namespace std;

int main() {
  multiset<int> ms = {1, 3, 3, 5};

  ms.erase(3);  // 3이라는 값을 가진 모든 원소 삭제

  // 하나만 삭제하고 싶다면?
  auto it = ms.find(3);
  if (it != ms.end()) ms.erase(it);  // 3 하나만 삭제

  return 0;
}

• erase(val)는 해당하는 모든 값(val) 삭제
• erase(it)는 해당 위치(it)의 값 하나 삭제

---

📖 std::multiset의 정렬 기준

📌 기본 정렬

👉 std::multiset은 기본적으로 오름차순 정렬을 수행 (std::less<T>를 기준으로 정렬)

#include <iostream>
#include <set>

using namespace std;

int main() {
  multiset<int> ms;
  ms.insert(5);
  ms.insert(1);
  ms.insert(3);
  ms.insert(3);
  ms.insert(2);

  for (int x : ms) cout << x << " ";  // 출력: 1 2 3 3 5

  return 0;
}

📌 내림차순 정렬

👉 std::greater<T>를 비교 객체로 넘기면 내림차순 정렬 가능

#include <functional>
#include <iostream>
#include <set>

using namespace std;

int main() {
  multiset<int, greater<int>> ms;
  ms.insert(4);
  ms.insert(7);
  ms.insert(4);
  ms.insert(1);

  for (int x : ms) cout << x << " ";  // 출력: 7 4 4 1

  return 0;
}

📌 사용자 정의 정렬

👉 복잡한 기준으로 정렬하려면 비교 함수 객체를 사용하거나, 사용자 정의 타입에 비교 연산자를 정의할 수 있음

✅ 비교 함수 객체(구조체)를 이용한 정렬 기준

• 비교 함수를 별도의 구조체로 정의하여 정렬 기준을 지정
• 클래스나 구조체의 특정 멤버를 기준으로 정렬할 때 유용

#include <iostream>
#include <set>

using namespace std;

struct Person {
  string name;
  int age;
  Person(string n, int a) : name(n), age(a) {}
};

struct Compare {
  bool operator()(const Person& a, const Person& b) const {
    return a.age < b.age;  // 나이 오름차순 정렬
  }
};

int main() {
  multiset<Person, Compare> ms;
  ms.emplace("Alice", 25);
  ms.emplace("Bob", 30);
  ms.emplace("Charlie", 25);

  for (const auto& p : ms) {
    cout << p.name << " " << p.age << endl;  // 출력: Alice 25, Charlie 25, Bob 30
  }

  return 0;
}

✅ 사용자 정의 타입 기준

• 사용자 정의 타입 내부에 operator<를 정의하여 비교 기준을 지정
• 비교 로직을 구조체 내부에 캡슐화하고 싶을 때 유용

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

struct Person {
  string name;
  int age;
  Person(string n, int a) : name(n), age(a) {}
  bool operator<(const Person& other) const {
    return age < other.age;  // 나이 오름차순 정렬
  }
};

int main() {
  multiset<Person> ms;

  ms.emplace("Alice", 25);
  ms.emplace("Bob", 30);
  ms.emplace("Charlie", 25);

  for (const auto& p : ms) {
    cout << p.name << " " << p.age << endl;  // 출력: Alice 25, Charlie 25, Bob 30
  }

  return 0;
}

 

---

📖 multiset의 사용 예시

• 중복 원소를 정렬 상태로 관리하고 싶을 때
• 우선순위, 빈도, 출현 순서 등을 고려해서 정렬 저장할 때
• top-N, 순위 추적, 정렬된 기록 수집 등

➡️ ex. 시험 점수 저장 (동일 점수 가능) | 빈도수 기반 기록 저장 | 자동 정렬되지만 중복을 허용해야 할 때

---

📚 std::multimap

출처: Different Approaches to Initialize a Multimap ❘ by Pawara Gunawardena ❘ Medium

📖 std::multimap

👉 key-value 쌍을 저장하면서, 동일한 key가 여러 개 존재할 수 있는 컨테이너

• 내부 구조는 std::map과 동일하게 자가 균형 이진 탐색 트리(Self-Balancing Binary Search Tree, 일반적으로 Red-Black Tree로 구현)로 구성
• std::map과 달리 같은 key로 여러 값을 저장할 수 있음 (중복 허용)
• key는 자동으로 정렬(기본: 오름차순)되지만, value는 정렬되지 않음

📌 std::multimap 사용 예시 코드

#include <iostream>
#include <map>

using namespace std;

int main() {
  multimap<string, int> scores;

  scores.insert({"Alice", 90});
  scores.insert({"Bob", 85});
  scores.insert({"Alice", 95});  // 중복 key 허용!

  for (auto& [name, score] : scores) {
    cout << name << " : " << score << endl;
  }
}

• std::map에서는 두번째 insert({"Alice", 95})가 무시되지만, std::multimap에서는 저장

---

📖 std::multimap의 주요 특징

• key-value 쌍으로 저장하며, key의 중복을 허용
• key를 기준으로 자동으로 정렬되며, 기본은 오름차순 정렬
• 탐색, 삽입, 삭제 시 시간복잡도 : $ O(\log N) $
• 임의 접근(random access)은 불가능 ➡️ iterator만 가능

---

📖 std::multimap의 주요 함수

• insert({key, val}) : key-value 쌍으로 저장되며, 중복된 key로 추가 가능
• find(key) : 첫 번째 key가 위치하는 iterator 반환
• count(key) : key의 개수 반환
• equal_range(key) : 같은 key들의 구간 반환 ➡️ pair<begin_iterator, end_iterator> 형태로 반환
• erase(key) : 해당 key 전체 제거 (모든 동일 key-value 쌍 제거)
  • erase(iterator) : 해당 위치(iterator)에 있는 key-value 쌍 제거

📌 equal_range() 함수 사용 예제

#include <iostream>
#include <map>

using namespace std;

int main() {
  multimap<string, int> scores;

  scores.insert({"Alice", 90});
  scores.insert({"Bob", 85});
  scores.insert({"Alice", 95});  // 중복 key 허용!

  auto range = scores.equal_range("Alice");

  for (auto it = range.first; it != range.second; ++it) {
    cout << it->first << " : " << it->second << endl;
  }

  return 0;
}

• 같은 key를 모두 순회하려면 equal_range()를 사용
  • range.first ➡️ key의 첫 번쨰 요소의 iterator
  • range.second ➡️ key의 마지막 요소의 다음 iterator

---

📖 사용자 정의 정렬

📌 기본 정렬

👉 std::multimap은 기본적으로 오름차순 정렬을 수행 (std::less<T>를 기준으로 정렬)

#include <iostream>
#include <map>

using namespace std;

int main() {
  multimap<int, string> mm;

  mm.insert({3, "C"});
  mm.insert({1, "A"});
  mm.insert({2, "B"});
  mm.insert({3, "D"});  // 중복 key

  for (auto& [k, v] : mm) cout << k << " : " << v << endl;
  
  return 0;
}

 

📌 내림차순 정렬

👉 std::greater<T>를 비교 객체로 넘기면 내림차순 정렬 가능

#include <functional>  // for greater
#include <iostream>
#include <map>

using namespace std;

int main() {
  multimap<int, string, greater<int>> mm;

  mm.insert({3, "C"});
  mm.insert({1, "A"});
  mm.insert({2, "B"});
  mm.insert({3, "D"});

  for (auto& [k, v] : mm) cout << k << " : " << v << endl;

  return 0;
}

📌 사용자 정의 정렬

✅ 구조체를 이용한 정렬 기준

• 비교 함수 객체를 사용하여 key의 특정 멤버를 기준으로 정렬

#include <iostream>
#include <map>
#include <string>

using namespace std;

struct Person {
  string name;
  int age;
  Person(string n, int a) : name(n), age(a) {}
};

struct PersonCompare {
  bool operator()(const Person& a, const Person& b) const {
    return a.age < b.age;  // 나이 기준 오름차순 정렬
  }
};

int main() {
  multimap<Person, string, PersonCompare> mm;

  mm.emplace(Person("Alice", 25), "엔지니어");
  mm.emplace(Person("Bob", 30), "매니저");
  mm.emplace(Person("Charlie", 25), "디자이너");

  for (const auto& pair : mm) {
    cout << pair.first.name << " (나이 " << pair.first.age << "): " << pair.second << endl;
    // 출력: Alice (나이 25): 엔지니어
    //       Charlie (나이 25): 디자이너
    //       Bob (나이 30): 매니저
  }

  return 0;
}

✅ 사용자 정의 타입 기준

• key 타입 내에 operator<를 정의하여 정렬 기준으로 지정

#include <iostream>
#include <map>
#include <string>

using namespace std;

struct Person {
  string name;
  int age;
  Person(string n, int a) : name(n), age(a) {}
  bool operator<(const Person& other) const {
    return age < other.age;  // 나이 기준 오름차순 정렬
  }
};

int main() {
  multimap<Person, string> mm;

  mm.emplace(Person("Alice", 25), "엔지니어");
  mm.emplace(Person("Bob", 30), "매니저");
  mm.emplace(Person("Charlie", 25), "디자이너");

  for (const auto& pair : mm) {
    cout << pair.first.name << " (나이 " << pair.first.age << "): " << pair.second << endl;
    // 출력: Alice (나이 25): 엔지니어
    //       Charlie (나이 25): 디자이너
    //       Bob (나이 30): 매니저
  }

  return 0;
}

---

📖 multimap의 사용 예시

• 하나의 키에 여러 값을 연결해야 할 때

➡️ ex. 하나의 학생 이름에 여러 시험 점수 저장 | 단어(키)에 여러 문맥(뜻) 저장 | 에러 코드 - 로그 메시지 여러 개 저장

---