【 C++ 】set、multiset的介绍和使用

目录

1、关联式容器

2、键值对

3、树形结构的关联式容器

4、set

        set的介绍

        set的定义

        set的使用

5、multiset

        multiset的介绍

        multiset的使用

---

1、关联式容器

先前我们已经接触过STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的键值对，在数据检索时比序列式容器效率更高。

---

2、键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。

SGI-STL中关于键值对的定义：

template <class T1, class T2>
struct pair
{
	typedef T1 first_type;
	typedef T2 second_type;
	T1 first;
	T2 second;
	pair() : first(T1()), second(T2())
	{}
	pair(const T1& a, const T2& b) : first(a), second(b)
	{}
};

---

3、树形结构的关联式容器

根据应用场景的不同，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一个容器。

---

4、set

set的介绍

• 1、set是按照一定次序存储元素的容器
• 2、在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
• 3、在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
• 4、set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
• 5、set在底层是用二叉搜索树(红黑树)实现的。

注意：

• 1、与map/multimap不同，map/multimap中存储的是真正的键值对，set中只放value，但在底层实际存放的是由构成的键值对。
• 2、set中插入元素时，只需要插入value即可，不需要构造键值对。
• 3、set中的元素不可以重复(因此可以使用set进行去重)。
• 4、使用set的迭代器遍历set中的元素，可以得到有序序列
• 5、set中的元素默认按照小于来比较
• 6、set中查找某个元素，时间复杂度为：logN
• 7、set中的元素不允许修改，因为set在底层是用二叉搜索树来实现的，若是对二叉搜索树当中某个结点的值进行了修改，那么这棵树将不再是二叉搜索树。
• 8、set中的底层使用二叉搜索树(红黑树)来实现。

set的定义

• 1、构造空的set

set<int> s1;

• 2、set的拷贝构造

set<int> s2(s1);

• 3、用[first, last)迭代器区间中的元素构造set

string s("hello world");
set<char> s3(s.begin(), s.end());

• 4、构造一个指定为大于的比较方式

set<int, greater<int>> s4;

set的使用

• 1、set的模板参数列表

T: set中存放元素的类型，实际在底层存储的键值对

Compare：set中元素默认按照小于来比较

Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

• 2、set的迭代器

函数声明	功能介绍
begin	返回set中起始位置元素的迭代器
end	返回set中最后一个元素后面的迭代器
cbegin	返回set中起始位置元素的const迭代器
cend	返回set中最后一个元素后面的const迭代器
rbegin	返回set第一个元素的反向迭代器，即end
rend	返回set最后一个元素下一个位置的反向迭代器，即begin
crbegin	返回set第一个元素的反向const迭代器，即cend
crend	返回set最后一个元素下一个位置的反向const迭代器，即cbegin

• 3、set的容量

函数声明	功能介绍
bool empty ( ) const	检测set是否为空，空返回true，否则返回true
size_type size() const	返回set中有效元素的个数

• 4、set的修改操作

函数声明	功能介绍
insert	在set中插入元素x，实际插入的是构成的键值对，如果插入成功，返回<该元素在set中的位置，true>,如果插入失败，说明x在set中已经存在，返回
void erase ( iterator position )	删除set中position位置上的元素
size_type erase ( const key_type& x )	删除set中值为x的元素，返回删除的元素的个数
void erase ( iterator first, iterator last )	删除set中[first, last)区间中的元素
swap	交换set中的元素
clear	将set中的元素清空
find	返回set中值为val的元素的位置
count	值为val的元素存在则返回1，不存在则返回0
lower_bound	返回 >= val 的迭代器位置
upper_bound	返回 > val 的迭代器位置

• 示例如下：

迭代器 + insert 

void test_set1()
{
	set<int> s;
	s.insert(4);
	s.insert(5);
	s.insert(2);
	s.insert(1);
	s.insert(1);
	s.insert(3);
	s.insert(3);
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		//有序+去重
		//*it = 10; err不允许修改
		cout << *it << " ";//1 2 3 4 5
		it++;
	}
	cout << endl;
	//范围for
	for (auto e : s)
	{
		cout << e << " ";
	}
}

find + erase + count

void test_set2()
{
	set<int> s;
	s.insert(4);
	s.insert(5);
	s.insert(2);
	s.insert(1);
	s.insert(3);
	cout << s.erase(3) << endl;//1
	cout << s.erase(30) << endl;//0
	for (auto e : s)
	{
		cout << e << " "; //1 2 4 5
	}
	cout << endl;
	set<int>::iterator pos = s.find(3);
	if (pos != s.end())
		s.erase(pos);
	for (auto e : s)
	{
		cout << e << " "; //1 2 4 5
	}
	if (s.find(5) != s.end())
	{
		cout << "5在" << endl;//5在
	}
	if (s.count(5))//相较于find更加方便
	{
		cout << "5在" << endl;//5在
	}
}

lower_bound

void test_set3()
{
	set<int> s;
	s.insert(4);
	s.insert(5);
	s.insert(2);
	s.insert(1);
	s.insert(3);
	s.insert(7);
	s.insert(9);
	for (auto e : s)
		cout << e << " ";//1 2 3 4 5 7 9
	cout << endl;
	//lower_bound返回 >= val的位置迭代器
	set<int>::iterator lowIt = s.lower_bound(3);
	cout << *lowIt << endl;//3
	lowIt = s.lower_bound(6);
	cout << *lowIt << endl;//7
 
	//要求删除 >= x 的所有值
	int x;
	cin >> x;//6
	lowIt = s.lower_bound(x);
	s.erase(lowIt, s.end());
	for (auto e : s)
		cout << e << " ";//1 2 3 4 5
}

upper_bound

void test_set4()
{
	set<int> s;
	s.insert(4);
	s.insert(5);
	s.insert(2);
	s.insert(1);
	s.insert(3);
	s.insert(7);
	s.insert(9);
	for (auto e : s)
		cout << e << " ";//1 2 3 4 5 7 9
	cout << endl;
	//upper_bound返回 > val的位置迭代器
	set<int>::iterator upIt = s.upper_bound(5);//存在
	cout << *upIt << endl;//7
	upIt = s.upper_bound(6);//不存在
	cout << *upIt << endl;//7
	//删除 x <= [] <= y的区间
	int x, y;
	cin >> x >> y;//x = 3, y = 7
	auto leftIt = s.lower_bound(x);
	auto rightIt = s.upper_bound(y);
	s.erase(leftIt, rightIt);
	for (auto e : s)
		cout << e << " ";//1 2 9
	cout << endl;
}

---

5、multiset

multiset的介绍

• 1、multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。
• 2、在multiset中，元素的value也会识别它(因为multiset中本身存储的就是组成的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除。
• 3、在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。
• 4、multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。
• 5、multiset底层结构为二叉搜索树(红黑树)。

注意：

• 1、multiset中再底层中存储的是的键值对
• 2、mtltiset的插入接口中只需要插入即可
• 3、与set的区别是，multiset中的元素可以重复，set是中value是唯一的
• 4、使用迭代器对multiset中的元素进行遍历，可以得到有序的序列
• 5、multiset中的元素不能修改
• 6、在multiset中找某个元素，时间复杂度为O(logN)
• 7、multiset的作用：可以对元素进行排序

multiset的使用

multiset和set的接口近乎一致，唯一不同于set的在于multiset允许键值冗余：

void test_set1()
{
	multiset<int> s;
	s.insert(4);
	s.insert(5);
	s.insert(2);
	s.insert(1);
	s.insert(1);
	s.insert(3);
	s.insert(3);
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		//排序
		cout << *it << " ";//1 1 2 3 3 4 5
		it++;
	}
}

正是multiset允许了键值冗余，所以multiset的两个函数接口find和count与set的也是有区别的：

成员函数count	功能说明
set对象	值为val的元素存在则返回1，不存在则返回0
multiset对象	返回set中值为x的元素的个数

成员函数find	功能说明
set对象	返回值为val的元素的迭代器位置
multiset对象	返回底层搜索树中序的第一个值为val的元素的迭代器

示例：

void test_set2()
{
	multiset<int> multiset;
	multiset.insert(4);
	multiset.insert(5);
	multiset.insert(2);
	multiset.insert(1);
	multiset.insert(1);
	multiset.insert(3);
	multiset.insert(3);
	multiset.insert(3);
	//1 1 2 3 3 3 4 5
	set<int> set(multiset.begin(), multiset.end());
	cout << multiset.count(1) << endl;//2 返回1的个数
	cout << set.count(1) << endl;//1 返回一个bool值，存在返回1
	cout << multiset.erase(1) << endl;//2 返回删除的1的个数
	cout << set.erase(1) << endl;//1 返回一个bool值，存在删除的值返回1
	auto pos1 = multiset.find(3); //返回中序的第一个3的迭代器
	while (pos1 != multiset.end())
	{
		cout << *pos1 << " ";//3 3 3 4 5
		pos1++;
	}
}