117.STL中的multiset

1.multiset的介绍

1.multiset是按照特定顺序存储元素的容器，其中元素是可以重复的
2.在multiset在，元素的value也会识别它组成的键值对，multiset元素的值不能在容器中进行修改，但可以插入和删除
3.在内部，multiset按照特定的严格弱排序准则进行排序
4.multiset容器通过key访问单个元素比unordered_multiset容器慢，但当使用迭代器遍历的时候，会得到一个有序序列
5.multiset的底层是二叉搜索树（红黑树）

注：
1.multiset的底层存储的是<value, value>的键值对
2.multiset的插入接口中只需要插入即可
3.multiset与set的区别是multiset中的元素可以重复
4.使用迭代器遍历，可以得到有序的multiset
5.multiset中的元素不可修改
6.multiset的查找的时间复杂度是Olog₂N
7.multiset的作用，可以对元素进行排序

2.multiset的构造

const allocator_type& alloc = allocator_type()

这段代码是C++中的语法，它定义了一个名为 alloc 的对象，该对象是 allocator_type 类型的，并通过调用默认构造函数 allocator_type() 进行初始化。allocator_type 是某个容器类（例如 std::set 或 std::multiset）的成员类型，用于管理容器的内存分配和释放。

在这里，const allocator_type& alloc = allocator_type() 的作用是创建一个引用，该引用指向一个 allocator_type 类型的对象，并将其初始化为默认构造的 allocator_type 对象。通过引用 alloc，可以在容器类中使用该引用来分配和释放内存。

这种语法形式通常用于容器类的成员函数中，以提供对容器内部使用的内存分配器的访问。具体来说，通过引用 alloc，可以在容器类中调用 allocate、deallocate 等函数来管理容器的内存分配和释放。

例1：

// constructing multisets
#include <iostream>
#include <set>
using namespace std;

bool fncomp(int lhs, int rhs) { return lhs < rhs; }

struct classcomp
{
	bool operator() (const int& lhs, const int& rhs) const
	{
		return lhs < rhs;
	}
};

int main()
{
	multiset<int> first;                          //基本定义

	int myints[] = { 10,20,30,20,20 };
	multiset<int> second(myints, myints + 5);       // pointers used as iterators

	for (multiset<int>::iterator it = second.begin(); it != second.end(); ++it)
		cout << ' ' << *it;
	cout << endl;

	multiset<int> third(second);                 // 复制
	for (multiset<int>::iterator it = second.begin(); it != second.end(); ++it)
		cout << ' ' << *it;
	cout << endl;

	multiset<int> fourth(second.begin(), second.end());  // iterator ctor.
	for (multiset<int>::iterator it = second.begin(); it != second.end(); ++it)
		cout << ' ' << *it;
	cout << endl;

	multiset<int, classcomp> fifth;                // class as Compare

	bool(*fn_pt)(int, int) = fncomp;
	multiset<int, bool(*)(int, int)> sixth(fn_pt); // function pointer as Compare

	return 0;
}

输出：

 10 20 20 20 30
 10 20 20 20 30
 10 20 20 20 30

容器间赋值：

//assignment operator with multisets
#include <iostream>
#include <set>
using namespace std;

int main()
{
	int myints[] = { 19,81,36,36,19 };
	multiset<int> first(myints, myints + 5);   // multiset with 5 ints

	cout << "first为:" << endl;
	for (auto it : first)
	{
		cout << it << " ";
	}
	cout << endl;

	multiset<int> second;                    // empty multiset

	second = first;                          // now second contains the 5 ints
	cout << "second为:" << endl;
	for (auto it : second)
	{
		cout << it << " ";
	}
	cout << endl;

	first = multiset<int>();                 // 清空first

	cout << "Size of first: " << first.size() << '\n';
	cout << "Size of second: " << second.size() << '\n';

	return 0;	
}

输出：

first为:
19 19 36 36 81
second为:
19 19 36 36 81
Size of first: 0
Size of second: 5

3.multiset的迭代器

4.遍历容器

for (auto it : first)
{
    cout << it << " ";
}

//assignment operator with multisets
#include <iostream>
#include <set>
using namespace std;

int main()
{
    int myints[] = { 42,71,71,71,12 };
    multiset<int> mymultiset(myints, myints + 5);

    multiset<int>::iterator it;//定义一个在multiset上的iterator

    cout << "mymultiset contains:";
    for (multiset<int>::iterator it = mymultiset.begin(); it != mymultiset.end(); ++it)
        cout << ' ' << *it;

    cout << '\n';

    return 0;
}

输出：

mymultiset contains: 12 42 71 71 71

4.multiset的容量操作

5.multiset的修改

插入数据：

//assignment operator with multisets
#include <iostream>
#include <set>
using namespace std;

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

    // set some initial values:
    for (int i = 1; i <= 5; i++) 
        mymultiset.insert(i * 10);  // 10 20 30 40 50

    it = mymultiset.insert(25);

    it = mymultiset.insert(it, 27);    // max efficiency inserting
    it = mymultiset.insert(it, 29);    // max efficiency inserting
    it = mymultiset.insert(it, 24);    // no max efficiency inserting (24<29)

    int myints[] = { 5,10,15 };
    mymultiset.insert(myints, myints + 3);

    cout << "mymultiset contains:";
    for (it = mymultiset.begin(); it != mymultiset.end(); ++it)
        cout << ' ' << *it;
    cout << '\n';

    return 0;
}

输出：

mymultiset contains: 5 10 10 15 20 24 25 27 29 30 40 50

删除某个特定元素：

//assignment operator with multisets
#include <iostream>
#include <set>
using namespace std;

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

	// insert some values:
	mymultiset.insert(40);                            // 40
	for (int i = 1; i < 7; i++)
		mymultiset.insert(i * 10);   // 10 20 30 40 40 50 60

	cout << "删除数据前：" << endl;
	for (multiset<int>::iterator it = mymultiset.begin(); it != mymultiset.end(); ++it)
		cout << ' ' << *it;

	it = mymultiset.begin();
	it++;                                              //    ^
	cout  << endl;

	mymultiset.erase(it);                             // 10 30 40 40 50 60
	cout << "删除数据第一次后：" << endl;
	for (multiset<int>::iterator it = mymultiset.begin(); it != mymultiset.end(); ++it)
		cout << ' ' << *it;
	cout  << endl;

	mymultiset.erase(40);                             // 10 30 50 60
	cout << "删除数据第二次后：" << endl;
	for (multiset<int>::iterator it = mymultiset.begin(); it != mymultiset.end(); ++it)
		cout << ' ' << *it;
	cout  << endl;

	it = mymultiset.find(50);

	mymultiset.erase(it, mymultiset.end());         // 10 30
	cout << "删除数据第三次后：" << endl;
	for (multiset<int>::iterator it = mymultiset.begin(); it != mymultiset.end(); ++it)
		cout << ' ' << *it;
	cout  << endl;

	cout << "mymultiset contains:";
	for (it = mymultiset.begin(); it != mymultiset.end(); ++it)
		cout << ' ' << *it;
	cout << '\n';

	return 0;
}

输出：

删除数据前：
 10 20 30 40 40 50 60
删除数据第一次后：
 10 30 40 40 50 60
删除数据第二次后：
 10 30 50 60
删除数据第三次后：
 10 30
mymultiset contains: 10 30

参考：

multiset的介绍及使用

【原创】C++STL multiset - Where_Free - 博客园 (cnblogs.com)