012_멀티셋 (std::multiset)

멀티셋 (std::multiset)

멀티셋(multiset) 은 연관 컨테이너(Associative Container) 중 하나ㅏ디ㅏ.

multiset 은 노드 기반으로 이루어져 있다.

multiset 은 key 로 이루어져 있으며 set 과 달리 중복된 key 값을 허용한다.

multiset 은 원소가 삽입되면서 자동으로 오름차순(기본값)으로 정렬된다.

multiset 은 저장 공간의 필요에 따라 동적할당을 한다.

multiset 의 사용

multiset 헤더파일

#include <set>

multiset 선언

std::multiset<KeyType> MultiSetName;

multiset 생성자 (편의상 <int>)

std::multiset<int> ms;	비어있는 멀티셋 ms를 생성
std::multiset<int> ms2(ms1);	ms2는 멀티셋 ms1을 복사하여 생성
std::multiset<int, predicate> ms;	predicate를 통해 정렬 기준을 세운 멀티셋 ms를 생성

std::multiset<int, std::greater<int>> ms; // 내림차순으로 정렬하는 멀티셋 ms를 생성

multiset 의 멤버 함수

std::multiset<int> ms;

ms.begin()	첫 번째 원소를 가리키는 `iterator` 를 반환
ms.end()	마지막 원소의 다음을 가리키는 `iterator` 를 반환
ms.rbegin()	마지막 원소를 가리키는 `reverse_iterator` 를 반환
ms.rend()	첫 번째 원소의 앞을 가리키는 `reverse_iterator` 를 반환
ms.insert(k)	원소 k를 삽입함. 삽입 시 자동으로 정렬됨
ms.insert(iter, k)	iter가 가리키는 위치부터 원소 k를 삽입할 위치를 탐색해 삽입
ms.erase(k)	k 값과 `key` 값이 일치하는 원소를 제거
ms.erase(iter)	iter가 가리키는 원소를 제거
ms.erase(start, end)	start 반복자부터 end 반복자 전까지 `[start, end)` 원소를 제거
ms.clear()	멀티셋의 모든 원소를 제거
ms.find()	k 값과 `key` 값이 일치하는 원소를 가리키는 반복자를 반환
만족하는 원소가 없다면 `ms.end()` 와 같은 반복자를 반환
ms.count(k)	k 값과 `key` 값이 일치하는 원소의 개수를 반환
ms.empty()	멀티셋 ms가 비어있으면 `true` 를 반환
ms.size()	원소의 개수를 반환
ms.contains(k)	멀티셋에 k 값과 일치하는 key 값이 있으면 `true` 를 반환 (C++20)
ms2.swap(ms1)	ms2 멀티셋과 ms1 멀티셋을 서로 바꿈
ms.upper_bound(k)	k 값과 `key` 값이 일치하는 맨 마지막 원소의 다음을 가리키는 `iterator` 를 반환
폐구간 `)` 으로 사용
ms.lower_bound(k)	k 값과 `key` 값이 일치하는 맨 첫 번째 원소를 가리키는 `iterator` 를 반환
개구간 `[` 으로 사용
ms.equal_range(k)	k 값과 `key` 값이 일치하는 원소의 범위를 `pair` 객체로 반환

pair<lower_bound, upper_bound> |

multiset 의 원소 삽입

insert() 를 통해 multiset에 원소를 삽입할 수 있다.

#include <iostream>
#include <set>

int main()
{
	std::multiset<int> ms;
	std::multiset<int>::iterator it;

	// insert() 이용
	ms.insert(50);
	ms.insert(42);
	ms.insert(52);
	ms.insert(72);
	ms.insert(52);
	ms.insert(20);
	ms.insert(42);

	for (it = ms.begin(); it != ms.end(); ++it)
		std::cout << (*it) << " ";

	return 0;
}

20 42 42 50 52 52 72

multiset 의 원소 삭제

erase(), clear() 를 통해 multiset 의 원소를 삭제할 수 있다.

erase() : 특정 원소 삭제
clear() : 전체 원소 삭제

#include <iostream>
#include <set>

int main()
{
	std::multiset<int> ms;
	std::multiset<int>::iterator it;

	// insert() 이용
	ms.insert(50);
	ms.insert(42);
	ms.insert(52);
	ms.insert(72);
	ms.insert(20);
	ms.insert(52);
	ms.insert(50);

	for (it = ms.begin(); it != ms.end(); ++it)
		std::cout << (*it) << " ";

	// key 값을 기준으로 요소 삭제 (해당 하는 모든 요소가 삭제됨)
	ms.erase(52);

	// iterator 를 이용해 요소 삭제
	ms.erase(ms.begin());

	std::cout << std::endl;
	for (it = ms.begin(); it != ms.end(); ++it)
		std::cout << (*it) << " ";

	// clear()를 이용해 전체 원소 삭제
	ms.clear();

	if (ms.empty())
		std::cout << "\\nmultiset이 비었습니다.";
	else
		std::cout << "\\nmultiset이 비어있지 않습니다.";

	return 0;
}

20 42 50 50 52 52 72
42 50 50 72
multiset이 비었습니다.

multiset 의 원소 찾기

find() 를 통해 원하는 원소를 찾을 수 있다.

#include <iostream>
#include <set>

int main()
{
	std::multiset<int> ms;
	std::multiset<int>::iterator it;

	// insert() 이용
	ms.insert(50);
	ms.insert(42);
	ms.insert(52);
	ms.insert(72);
	ms.insert(20);
	ms.insert(52);
	ms.insert(50);

	for (it = ms.begin(); it != ms.end(); ++it)
		std::cout << (*it) << " ";

	// find() 를 이용해 원하는 원소를 찾을 수 있습니다.
	it = ms.find(42);
	std::cout << "\\n\\n" << (*it);

	// 만약 일치하는 key 값이 없다면 end()를 가리키는 반복자를 반환합니다.
	it = ms.find(40);
	if (it != ms.end())
		std::cout << "\\n\\n원소 발견!" << std::endl;
	else
		std::cout << "\\n\\n원소 미발견..." << std::endl;

	return 0;
}

20 42 50 50 52 52 72

42

원소 미발견...

multiset 사용 예시

`upper_bound, lower_bound`

upper_bound(k) : k 값과 key 값이 일치하는 맨 마지막 원소의 다음을 가리키는 반복자를 반환
lower_bound(k) : k 값과 key 값이 일치하는 맨 첫 번째 원소를 가리키는 반복자를 반환

#include <iostream>
#include <set>

int main()
{
	std::multiset<int> ms;
	std::multiset<int>::iterator it;

	// insert() 이용
	ms.insert(50);
	ms.insert(52);
	ms.insert(72);
	ms.insert(20);
	ms.insert(72);
	ms.insert(50);
	ms.insert(86);
	ms.insert(50);

	for (it = ms.begin(); it != ms.end(); ++it)
		std::cout << (*it) << " ";

	// lower_bound, upper_bound
	std::multiset<int>::iterator low_it;
	std::multiset<int>::iterator up_it;

	low_it = ms.lower_bound(50); // 50과 일치한 key 값을 가진 맨 첫 번째 원소를 가리키는 반복자
	up_it = ms.upper_bound(50);  // 50과 일치한 key 값을 가진 맨 마지막 원소의 다음을 가리키는 반복자

	std::cout << "\\n\\nlower_bound : " << (*low_it);
	std::cout << "\\nupper_bound : " << (*up_it);

	// [lower_bound, upper_bound) 출력
	// 50과 일치한 key 값을 가진 모든 원소 출력
	std::cout << std::endl;
	for (it = ms.lower_bound(50); it != ms.upper_bound(50); ++it)
		std::cout << (*it) << " ";

	return 0;
}

20 50 50 50 52 72 72 86

lower_bound : 50
upper_bound : 52
50 50 50

`equal_range`

equal_range(k) : k 값과 key 값이 일치하는 원소의 범위를 pair 객체로 반환 pair<lower_bound, upper_bound>

#include <iostream>
#include <set>

int main()
{
	std::multiset<int> ms;
	std::multiset<int>::iterator it;

	// insert() 이용
	ms.insert(50);
	ms.insert(52);
	ms.insert(72);
	ms.insert(20);
	ms.insert(72);
	ms.insert(50);
	ms.insert(86);
	ms.insert(50);

	for (it = ms.begin(); it != ms.end(); ++it)
		std::cout << (*it) << " ";

	// equal_range
	std::pair<std::multiset<int>::iterator, std::multiset<int>::iterator> pair_it;

	pair_it = ms.equal_range(50); // 50과 일치한 key 값을 가진 원소의 범위를 pair 객체로 반환

	std::cout << "\\n\\npair_it.first : " << (*pair_it.first);
	std::cout << "\\npair_it.second : " << (*pair_it.second);

	// equal_range 출력
	// 50과 일치한 key 값을 가진 모든 원소 출력
	std::cout << std::endl;
	for (it = ms.equal_range(50).first; it != ms.equal_range(50).second; ++it)
		std::cout << (*it) << " ";

	return 0;
}

20 50 50 50 52 72 72 86

pair_it.first : 50
pair_it.second : 52
50 50 50