STL容器之＜multiset＞

测试环境

系统：ubuntu 22.04.2 LTS 64位
gcc版本：11.3.0
编辑器：vsCode 1.76.2

multiset介绍

1. 关联式容器。
2. 元素是唯一的，即是值又是键。
3. 元素不能直接修改，需要先删除在插入。
4. 支持双向迭代器。
5. 在插入、删除和搜索时间复杂度为log(n)。

头文件

#include <set>

模块类定义

template <typename _Key, typename _Compare = std::less<_Key>, typename _Alloc = std::allocator<_Key> >class multiset{};

_Key：表示存储的键(值)数据类型
_Compare：表示按照键的排序方式。
_Alloc：表示所存储分配器的类型，负责元素内存的分配和释放。可选参数，一般不使用。

对象构造

/*默认构造函数*关联容器和容器适配器。*/
std::multiset<int> multiSet1;
/*构造一个set指定排序方式*/
std::multiset<int> multiSet2(std::less<int>());
/*拷贝构造函数*/
std::multiset<int> multiSet3(multiSet1);
/*移动构造函数*/
std::multiset<int> multiSet4(std::move(multiSet1));
/*初始化列表*/
std::multiset<int> multiSet5({5,4,3,2,1});
/*初始化列表+排序方式*/
std::multiset<int> multiSet6({5,4,3,2,1}, std::less<int>());
/*迭代器指定范围构造*/
std::multiset<int> multiSet7(multiSet6.begin(),multiSet6.end());
/*迭代器指定范围+排序方式*/
std::multiset<int> multiSet8(multiSet7.begin(), multiSet7.end(), std::less<int>());

初始化

/*初始化列表初始化元素*/
multiSet1 = {1,3,5,4,2};

元素访问

不支持at()函数和下标运算符访问元素

元素插入和删除

函数	返回值	功能
clear()	无	清空所有元素
erase()	迭代器或删除元素数量	清除指定位置的一个元素、通过迭代器指定范围内的元素或通过键删除值
emplace()	迭代器	直接构造一个元素并插入集合中。
emplace_hint()	迭代器	在指定的位置插入元素。
insert()	键值对、迭代器、无	1）直接插入一个元素。2）在指定位置插入1个元素。3）复制通过迭代器指定范围的元素。4）通过初始化列表插入元素。

multiSet1 = {2,2,3,1,1,5,6,6,2};
/*直接构造并插入元素*/
std::multiset<int>::iterator itr1 = multiSet1.emplace(10);
std::cout << "itr1 value is "<<*itr1<<std::endl;
/*直接构造元素并插入指定位置*/
std::multiset<int>::iterator itr2 = multiSet1.emplace_hint(++multiSet1.begin(),8);
std::cout << "itr2 value is "<<*(itr2)<<std::endl;
/*使用移动语句在指定位置插入元素*/
int iValue = 10;
std::multiset<int>::iterator itr3 = multiSet1.emplace_hint(++multiSet1.begin(),iValue);
std::cout << "itr3 value is "<<*(itr3)<<std::endl;
/*插入元素*/
std::multiset<int>::iterator itr4 = multiSet1.insert(8);
std::cout << "itr4 value is "<<*(itr4)<<std::endl;
/*使用移动函数插入元素,使用移动语句后iValue1不要再使用*/
int iValue1 = 7;
std::multiset<int>::iterator itr5 = multiSet1.insert(std::move(iValue1));
std::cout << "itr5 value is "<<*(itr5)<<std::endl;
/*指定位置插入元素*/
std::multiset<int>::iterator itr6 = multiSet1.insert(++multiSet1.begin(), 12);
std::cout << "itr6 value is "<<*(itr6)<<std::endl;
/*使用移动函数在指定位置插入元素*/
int iValue2 = 13;
std::multiset<int>::iterator itr7 = multiSet1.insert(--multiSet1.end(), std::move(iValue2));
std::cout << "itr7 value is "<<*(itr7)<<std::endl;
/*使用迭代器插入元素*/
multiSet1.insert(++multiSet5.begin(), --multiSet5.end());
/*使用初始化列表插入元素*/
multiSet1.insert({1,2,5,4,8,3});
/*按值删除元素*/
int iDelCnt = multiSet1.erase(2);
std::cout << "delete value count " << iDelCnt << std::endl;
/*删除指定位置的元素*/
std::multiset<int>::iterator itr8 = multiSet1.erase(++multiSet1.begin());
std::cout << "itr8 value is "<<*(itr8)<<std::endl;
/*删除指定范围的元素*/
std::multiset<int>::iterator itr9 = multiSet1.erase(++multiSet1.begin(), --multiSet1.end());
std::cout << "itr9 value is " << *(itr9) << std::endl;
/*清空元素*/
multiSet1.clear();

元素查找

函数	返回值	功能
count()	std::size_t	返回给定键对应元素的数量
find()	迭代器	查找指定键对应元素的位置,未找到则返回end()
lower_bound()	迭代器	查找第一个大于或等于给定键的元素的位置,未找到则返回end()
upper_bound()	迭代器	查找第一个大于给定键的元素的位置，未找到返回end()
equal_range()	键值对	获取给定键的lower_bound和upper_bound，键值对的第一个元素表示lower_bound,第二个元素表示upper_bound

multiSet1 = {1,1,2,2,3,4,5,6,6,8};
/*查找指定值的数量*/
std::cout << "count:" << multiSet1.count(2) << std::endl;
/*查找指定值的位置*/
std::multiset<int>::iterator itr10 = multiSet1.find(6);
std::cout << "itr10 value is " << *(itr10) << std::endl;
/*查找第一个大于等于给定键的元素的位置*/
std::multiset<int>::iterator itr11 = multiSet1.lower_bound(3);
std::cout << "itr11 value is "<<*(itr11)<<std::endl;
/*查找第一个大于给定键的元素的位置*/
std::multiset<int>::iterator itr12 = multiSet1.upper_bound(6);
std::cout << "itr12 value is "<<*(itr12)<<std::endl;
/*分别返回lower_bound和upper_bound*/
std::pair<std::multiset<int>::iterator, std::multiset<int>::iterator> pair = multiSet1.equal_range(1);
std::cout << "lower_bound value:"<<*(pair.first)<<std::endl;
std::cout << "upper_bound value:"<<*(pair.second)<<std::endl;

容器大小

函数	返回值	功能
size()	std::size_t	获取当前容器中的元素数量
empty()	bool	判断当前容器是否为空，为空返回true，否则返回false
max_size()	std::size_t	返回容器的最大容量

/*判断元素的数量*/
std::cout<<"multiSet1 size is "<<multiSet1.size()<<std::endl;
/*判断容器最大能容纳的元素的数量*/
std::cout<< "multiSet1 max size is :" <<multiSet1.max_size()<<std::endl;
/*判断容器是否为空*/
std::cout<< "multiSet1 is empty ? " <<std::boolalpha<<multiSet1.empty()<<std::endl;

迭代器

类型	功能
iterator	正向访问迭代器。从前向后访问元素，可以读取也可以修改
const_iterator	常量正向访问迭代器。从前向后访问元素，只能读取不能修改
reverse_iterator	逆向访问迭代器。从后向前访问元素，可以读取也可以修改
const_reverse_iterator	常量逆向访问迭代器。从后向前访问元素，只能读取不能修改

函数	返回值	功能
begin()	正向访问迭代器	返回指向set对象首元素所在位置的迭代器
end()	正向访问迭代器	返回指向set对象末尾元素的下一个位置的迭代器
cbegin()	常量正向访问迭代器	返回指向set对象首元素所在位置的常量迭代器
cend()	常量正向访问迭代器	返回指向set对象末尾元素的下一个位置的迭代器
rbegin()	逆向访问迭代器	返回指向set对象末尾元素位置的迭代器
rend()	逆向访问迭代器	返回指向set对象首元素的前一个位置的迭代器
crbegin()	常量逆向访问迭代器	返回指向set对象末尾元素位置的常量迭代器
crend()	常量逆向访问迭代器	返回指向set对象首元素的前一个位置的常量迭代器

std::multiset<int> multisetTest({1,8,2,6,4,5,8,10,2,7});
/*正向随机访问迭代器，并打印输出（1 2 2 4 5 6 7 8 8 10）*/
std::set<int>::iterator itr;
for (itr = multisetTest.begin(); itr != multisetTest.end(); itr++)
{/* 不允许修改元素值 *///*itr += 10; /* 访问元素 */std::cout<<*(itr)<<" ";
}
std::cout<<std::endl;
/*常量正向随机访问迭代器，并打印输出（1 2 2 4 5 6 7 8 8 10）*/
std::set<int>::const_iterator cItr;
for (cItr = multisetTest.cbegin(); cItr != multisetTest.cend(); cItr++)
{/* 不允许修改值，编译报错 *///*cItr += 10; /* 访问元素 */std::cout <<*(cItr)<<" ";
}
std::cout<<std::endl;
/*逆向随机访问迭代器，并打印输出（10 8 8 7 6 5 4 2 2 1）*/
std::set<int>::reverse_iterator rItr;
for (rItr= multisetTest.rbegin(); rItr!= multisetTest.rend(); rItr++)
{/* 不允许修改元素值 *///*rItr += 100; /* 访问元素 */std::cout <<" " << *(rItr);
}
std::cout<<std::endl;/*常量逆向随机访问迭代器，并打印输出（10 8 8 7 6 5 4 2 2 1）*/
std::set<int>::const_reverse_iterator crItr;
for (crItr= multisetTest.crbegin(); crItr!= multisetTest.crend(); crItr++)
{/* 不允许修改元素值， 编译报错 *///*crItr += 100; /* 访问元素 */std::cout <<" "<<*crItr;
}
std::cout << std::endl;

其他函数

函数名	返回值	功能
swap()	无	交换两个容器的元素

/*交互两个容器元素的值,无返回值*/
std::multiset<int> multisetSwap1 = {1,2,3,4,3};
std::multiset<int> multisetSwap2 = {6,7,8,6,10};
/*方式1， multisetSwap1={6,6,7,8,10}, multisetSwap2={1,2,3,3,4}*/
multisetSwap1.swap(multisetSwap2);
std::cout << "multisetSwap1: " << std::endl;
for (auto & item : multisetSwap1)
{std::cout << " "<<item;
}
std::cout <<std::endl<< "multisetSwap2: " << std::endl;
for (auto & item : multisetSwap2)
{std::cout << " "<<item;
}
/*multisetSwap1={1,2,3,3,4}, multisetSwap2={6,6,7,8,10}*/
std::swap(multisetSwap1,multisetSwap2);
std::cout << std::endl <<"multisetSwap1: " << std::endl;
for (auto & item : multisetSwap1)
{std::cout << " "<<item;
}
std::cout << std::endl << "multisetSwap2: " << std::endl;
for (auto & item : multisetSwap2)
{std::cout << " "<<item;
}