【C++】set和multiset的常用接口详解

 

        前⾯我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，本篇文章将介绍一下set和multiset的使用。  

1. 序列式容器和关联式容器

        在介绍set之前我们先简单介绍一下什么是序列式容器和关联式容器。

前⾯我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间⼀般没有紧密的关联关系，⽐如交换⼀下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

关联式容器也是⽤来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是 ⾮线性结构，两个位置有紧密的关联关系，交换⼀下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列unordered_map/unordered_set系列。

set是key搜索场景的结构。 

 

2. set系列的使⽤

2.1 set和multiset参考⽂档

参考文档： - C++ Reference"> - C++ Reference

先来总体看一下set的相关接口。

 总的来说还是之前我们在vector，string接触过的那些东西。虽然看起来接口很多，但常用的以及会学习到的就那些。

 

2.2 set类的介绍

set的声明如下。

• 参数1：T就是set底层关键字的类型。这个T就是key，名字不同。
• 参数2：set默认要求T⽀持⼩于⽐较，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现仿函数传给第⼆个模版参数。
• 参数3：set底层存储数据的内存是从空间配置器申请的（空间配置器），如果需要可以⾃⼰实现内存池，传给第三个参数。

  ⼀般情况下，我们都不需要传后两个模版参数。

  set底层是⽤红⿊树（以后会介绍）实现，增删查效率是O（ ） ，迭代器遍历是⾛的搜索树的 中序，所以是有序的。    

  2.3 set的构造和迭代器

  先看它的构造函数。

  

   再来看看他的迭代器。

  

  • 从文档介绍可以看出这是一个双向迭代器，⽀持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是⼆叉搜索树，迭代器遍历⾛的中序。
  • ⽀持迭代器就意味着⽀持范围for，set的iterator和const_iterator都不⽀持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。

    

     

    2.4 set的增删查（不支持改）

    2.4.1 insert

    

     

    先看insert，增。

    增这里首先支持增加一个value_type类型的东西，value_type什么？

    

     从这里可以看到，其实就是我们传的那个关键字Key，并且上面那个key_type也是key。所以就是插入一个key。这里的返回值类型后面会说，暂时不关注。

     用set的时候要包含头文件#include

    #include 
    #include 
    using namespace std;
    int main()
    {
    	set s;
    	s.insert(2);
    	s.insert(1);
    	s.insert(4); //重复
    	s.insert(3);
    	s.insert(4); //重复
    	return 0;
    }

    第二个参数不传的话，默认排升序。

    

    用迭代器遍历一下。

    int main()
    {
    	set s;
    	s.insert(2);
    	s.insert(1);
    	s.insert(4);
    	s.insert(3);
    	s.insert(4);
    	auto it = s.begin();
    	while (it != s.end())
    	{
    		cout