[C++] multiset

특징

set의 경우 key 값이 중복되지 않지만,

multiset의 경우 key 값이 중복될 수 있다.

대부분의 특징들은 set과 동일하므로 바로 예제를 통해서 하나씩 배워보자.

삽입

set과 마찬가지로 insert(key); 를 이용해서 삽입할 수 있다.

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

int main()
{
	multiset<int> ms;
	// less <
	// left node < parent node <= right node
	ms.insert(50);
	ms.insert(30);
	ms.insert(80);
	ms.insert(80);
	ms.insert(30);
	ms.insert(70);
	auto iter = ms.insert(10); // 저장된 위치만 가리키는 반복자 리턴

	cout << "*iter : " << *iter << '\n';

	for (iter = ms.begin(); iter != ms.end(); iter++)
		cout << *iter << ' ';
	cout << '\n';

	// greater >
	// left node >= parent node > right node
	multiset<int, greater<int>> ms2;
	for (iter = ms.begin(); iter != ms.end(); iter++)
		ms2.insert(*iter);

	for (iter = ms2.begin(); iter != ms2.end(); iter++)
		cout << *iter << ' ';
	cout << '\n';

	return 0;
}

*iter : 10
10 30 30 50 70 80 80
80 80 70 50 30 30 10

다양한 검색 연산들

count(key) : key가 몇 개 있는지 리턴

find(key) : key의 반복자를 리턴, 없다면 end() 리턴

lower_bound(key) : 찾는 key의 시작 반복자 리턴

upper_bound(key) : 찾는 key의 다음 반복자 리턴

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

int main()
{
	multiset<int> ms;
	ms.insert(50);
	ms.insert(30);
	ms.insert(80);
	ms.insert(80);
	ms.insert(30);
	ms.insert(70);
	ms.insert(10);

	for (auto iter = ms.begin(); iter != ms.end(); iter++)
		cout << *iter << ' ';
	cout << '\n';

	cout << "ms.count(30) : " << ms.count(30) << '\n';
	cout << "ms.count(100) : " << ms.count(100) << '\n';

	auto iter = ms.find(30);
	if (iter != ms.end())
		cout << "30 exist\n";
	else
		cout << "30 not exist\n";

	iter = ms.find(100);
	if (iter != ms.end())
		cout << "100 exist\n";
	else
		cout << "100 not exist\n";

	multiset<int>::iterator lower_iter;
	multiset<int>::iterator upper_iter;

	lower_iter = ms.lower_bound(30);
	upper_iter = ms.upper_bound(30);
	cout << "lower_iter : " << *lower_iter << '\n';
	cout << "upper_iter : " << *upper_iter << '\n';

	cout << "[lower_iter, upper_iter) -> ";
	for (iter = lower_iter; iter != upper_iter; iter++)
		cout << *iter << ' ';
	cout << '\n';
	return 0;
}

10 30 30 50 70 80 80
ms.count(30) : 2
ms.count(100) : 0
30 exist
100 not exist
lower_iter : 30
upper_iter : 50
[lower_iter, upper_iter) -> 30 30

equal_range()

lower_bound와 upper_bound를 따로 찾을 필요 없이 한 쌍으로 리턴해준다.

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

int main()
{
	multiset<int> ms;
	ms.insert(50);
	ms.insert(30);
	ms.insert(80);
	ms.insert(80);
	ms.insert(30);
	ms.insert(70);
	ms.insert(10);

	for (auto iter = ms.begin(); iter != ms.end(); iter++)
		cout << *iter << ' ';
	cout << '\n';

	auto iter = ms.equal_range(30);
	for (auto p = iter.first; p != iter.second; p++)
		cout << *p << ' ';
	cout << '\n';
	return 0;
}

10 30 30 50 70 80 80
30 30

다양하게 연습해보기

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

int main()
{
	multiset<int, greater<int> > mset;
	multiset<int, greater<int> > ::iterator itr;

	mset.insert(40);
	mset.insert(40);
	mset.insert(40);
	mset.insert(30);
	mset.insert(60);
	mset.insert(20);
	mset.insert(50);
	mset.insert(50);
	mset.insert(10);

	cout << "mset : ";
	for (itr = mset.begin(); itr != mset.end(); ++itr)
		cout << *itr << ' ';
	cout << endl;

	cout << "Size : " << mset.size() << endl;

	cout << "[mset.begin(), mset.find(40)) erase\n";
	mset.erase(mset.begin(), mset.find(40));

	cout << "mset : ";
	for (itr = mset.begin(); itr != mset.end(); ++itr)
		cout << *itr << ' ';
	cout << endl;

	cout << "40 counts : " << mset.count(40) << endl;

	cout << "Max-Size : " << mset.max_size() << endl;

	cout << "erase 40\n";
	mset.erase(40);
	cout << "mset : ";
	for (itr = mset.begin(); itr != mset.end(); ++itr)
		cout << *itr << ' ';
	cout << endl;

	mset.clear();

	mset = { 1,2,3,4,5,5,5,3,3,9,10 };
	cout << "mset : ";
	for (itr = mset.begin(); itr != mset.end(); ++itr)
		cout << *itr << ' ';
	cout << endl;

	cout << "lower_bound(5) : " << *mset.lower_bound(5) << endl;
	cout << "upper_bound(5) : " << *mset.upper_bound(5) << endl;
	for (auto i = mset.lower_bound(5); i != mset.upper_bound(5); ++i)
		cout << *i << ' ';
	cout << endl;

	auto p = mset.equal_range(5);
	for (auto i = p.first; i != p.second; ++i)
		cout << *i << ' ';
	cout << endl;
	return 0;
}

 

mset : 60 50 50 40 40 40 30 20 10
Size : 9
[mset.begin(), mset.find(40)) erase
mset : 40 40 40 30 20 10
40 counts : 3
Max-Size : 214748364
erase 40
mset : 30 20 10
mset : 10 9 5 5 5 4 3 3 3 2 1
lower_bound(5) : 5
upper_bound(5) : 4
5 5 5
5 5 5