C++之set

2020-12-23

Set和MultiSet会按照特定的排序规则，自动将元素排序。两者的不同是在于mutilset允许有重复元素在容器内，而set则不允许有重复元素。set和multiset位于头文件中。

对于set和multiset而言,只要是comparable（可依据某排序准则比较）的任意类型T都可以成为set或multiset的元素类型，如果没有自定义排序准则，那么set和multiset就会使用默认的仿函数less用来作为排序的准则,以operator<对元素进行比较。所谓的排序准则需要遵循以下原则：

必须是非对称的：若x op y为true，则 y op x 为 false
必须是可传递的：如 x op y为 true且 y op z 为true,则 x op z 为 true
必须是非自反的: x op x为 false
必须有等效传递性：如果 a = b且 b=c 那么 a = c

multiset的等效元素是随机且稳定的。set和multiset通常以平衡二叉树实现。自动排序的主要优点在于令二叉树于查找元素时拥有良好的效能。其查找函数具有对数复杂度。但是不能直接改变元素值，要想改变元素值，需要删除旧的元素再插入新元素。set和multiset不提供任何操作函数可以直接访问元素，通过迭代器进行元素间接访问，元素值是常量。

操作函数：

构造函数，拷贝构造，拷贝赋值，析构函数

操作	功能
set/multiset c	创建一个空的set/multiset对象c
set/multiset c(op)	建立一个空的set/multiset对象，以op为排序准则
set/multiset c(c1)	copy constructor
set/multiset c = c1	copy constructor
set/multiset c(rv)	move constructor.rv的所有资源被释放
set/multiset c = rv	move constructor.rv的所有资源被释放
set/multiset c(beg,end)	以区间[beg,end)内的元素为c的初值
set/multiset c(beg,end,op)	以区间[beg,end)内的元素为c的初值，以op为排序准则
set/multiset c(initlist)	列表初始化
set/multiset c=initlist	列表初始化
c.~~set/c.~~multiset()	析构函数

其中 set代表 set,multiset 代表 multiset

非更改操作：

操作	功能
c.key_comp()	返回 op
c.value_comp()	返回 op
c.empty()	容器是否为空
c.size()	目前的元素个数
c.max_size()	元素个数的最大可能量
c1 == c2	c1是否等于c2(每个元素调用 == )
c1 != c2	c1 是否不等于 c2
c1 < c2	c1 是否小于 c2
c1 > c2	c1 是否大于 c2
c1 <= c2	c1 是否小于等于c2
c1 >= c2	c1 是否大于等于 c2

查找函数：

操作	功能
c.ount(val)	返回容器中val的个数
c.find(val)	返回容器中第一个元素为val的元素，没有返回end()
c.lower_bound(val)	返回val第一个可以插入的位置，也就是元素值>=val的第一个位置
c.upper_bound(val)	返回val最后一个可以插入的位置，也就是元素值>val的第一个位置
c.equal_range(val)	返回val可被插入的第一个位置和最后一个位置即元素值==val的元素区间

赋值操作：

操作	效果
c = c1	copy assignment，将c2元素赋值给c
c = rv	move assignment,
c = initilist	将初值列的元素赋值给c
c1.swap(c2)	交换c1和c2的元素
swap(c1,c2)	交换c1和c2的元素

迭代器：

操作	效果
c.begin()	返回一个 bidirectional iterator指向第一元素
c.end()	返回一个 bidirectional iterator指向末尾元素的下一位置
c.cbegin()	返回一个 const bidirectional iterator指向第一元素
c.cend()	返回一个 const bidirectional iterator指向末尾元素的下一位置
c.rbegin()	返回一个 reverse iterator指向反向迭代的第一元素
c.rend()	返回一个 reverse iterator指向反向迭代的末尾元素的下一位置
c.crbegin()	返回一个 const reverse iterator指向反向迭代的第一元素
c.crend()	返回一个const reverse iterator指向反向迭代的末尾元素的下一位置

元素操作：

操作	效果
c.insert(val)	插入val,并返回新元素的位置
c.insert(pos,val)	以pos为起点在[pos,end)中插入val，返回新元素的位置
c.insert(beg,end)	将区间[beg,end)内的元素插入到c中
c.insert(initlist)	将初值列的元素插入到c中
c.emplace(args…)	插入一个args元素的值，并返回新元素的位置
c.emplace_hint(pos,args…)	以pos为起点在[pos,end)中插入args，返回新元素的位置
c.erase(val)	移除与 val相等的所有元素，返回被移除的个数
c.erase(pos)	移除iterator位置pos上的元素，无返回值
c.erase(beg,end)	移除区间[beg,end)内的元素，无返回值
c.clear()	将容器清空

代码示例如下：

 #include <set>
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
int main(int argc,char * argv[])
{
    set<int,greater<int>> coll1;
    coll1.insert({1,12,30,45,15,6});
    coll1.insert(8);

    for (auto const& elem : coll1) {
        cout << elem << '\t';
    }
    cout << endl;

    copy(coll1.rbegin(),coll1.rend(),ostream_iterator<int>(cout,"\t"));
    cout<< endl;

    auto pos = coll1.insert(21);
    if (pos.second){
        cout << "21 insert as element " << distance(coll1.begin(),pos.first) + 1 << endl;
    }else{
        cout << "21 is exists" << endl;
    }

    set<int> coll2(coll1.begin(),coll1.end());
    copy(coll2.begin(),coll2.end(),ostream_iterator<int>(cout,"\t"));
    cout<< endl;

    coll2.erase(coll2.begin(),coll2.find(21));
    int num = coll2.erase(45);
    cout << num << " elements is removed " << endl;
    copy(coll2.begin(),coll2.end(),ostream_iterator<int>(cout,"\t"));
    cout<< endl;
    return 0;
}