set和multiset基本性能

set和multiset属于关联式容器，会根据特定的排序原则，将内部元素自动排序，通常以红黑树完成，（保证了到达某一元素的最长路径的深度至多是最短路径的深度的两倍）。

自动排序的优点在于其查找函数具有对数复杂度，在小数据量（元素数量<=1000）的情况下二叉树查找动作（由stl成员函数执行）平均时间仅为线性查找的1/50。

有利必有弊，因自动排序的存在，你不能直接改变容器中的元素值，提供的改变的方法是删除旧元素，插入新元素。

1.set和multiset不提供任何操作函数可以直接访问元素。

2.通过迭代器对元素进行间接访问，有一个限制：从迭代器角度看，元素是常量。

set和multiset使用须知

1.set和multiset的区别在于multiset允许元素重复而set不允许。

2.包含头文件

1 #include<set>

3.只要是可依据某排序准则被比较的任意类型T都可以成为set或multiset的元素类型。

 1 namespace std
 2 {
 3 template <typename T,
 4           typename Compare = less<T>,
 5           typename Allocator = allocator<T>>
 6           class set;
 7 
 8 template <typename T,
 9           typename Compare = less<T>,
10           typename Allocator = allocator<T>>
11           class multiset;
12 }

两个类型都被定义为命名空间std内的class template

set和multiset的操作函数

 1.创建

1     set<elem> c;           //defalut构造函数，创建一个元素类型为elem的空的set/multiset，不含任何元素
2     set<elem> c(c2);
3     set<elem> c=c2;        //copy构造函数,建立一份c2的拷贝，所有元素均被复制
4     set<elem> c(beg,end);  //以区间[beg,end)内的元素为初值，建立一个set/multiset

在这里要注意，建立的所有set的排序方式都是默认为仿函数 less<>,在此我们不对构造排序函数作过多介绍，仅提供一个反序的仿函数

1 set<elem,greater<elem>> c; //以与less<>反序的排序准则创建的一个元素类型为elem的空set/multiset

2.非更易型操作

set和multiset提供的非更易型操作用来查询大小，相互比较（比较采用的是字典序），同样的，set重载了">,<,==,!=,>=,<="一系列比较运算符

1     c.empty();      //返回是否容器为空
2     c.size();       //返回容器目前元素个数
3     c.max_size();   //返回容器元素个数之最大可能量
4     c.key_comp();   //返回比较准则
5     c.value_comp(); //返回针对value的比较准则

3.特殊的查找函数

以下函数是同名的stl算法的基于set与multiset的特殊版本，对这两个容器使用以下查找可获得对数复杂度。

1     c.count(val);       //返回“元素值为val”的元素个数
2     c.find(val);        //返回“元素值为val”的第一个元素（迭代器），找不到就返回容器的end()
3     c.lower_bound(val); //返回val的第一个可安插位置，也就是“元素值>=val”的第一个元素位置（迭代器）
4     c.upper_bound(val); //返回val的最后一个可安插位置，也就是“元素值>val”的第一个元素位置（迭代器）
5     c.equal_range(val); //返回一个pair，将lower_bound和upper_bound分别作为first和second，也就是返回一个区间

4.迭代器相关函数

1     c.begin();  //返回一个bidirectional iterator指向第一元素
2     c.end();    //返回一个bidirectional iterator指向最末元素的下一位置
3     c.rbegin(); //返回一个reverse iterator指向反向迭代的第一元素
4     c.rend();   //返回一个reverse iterator指向反向迭代的最末元素的下一位置

5.元素的安插和移除

1     c.insert(val);     //安插一个val拷贝，返回新元素位置，无论是否成功（对set而言）
2     c.insert(pos,val); //安插一个val拷贝，返回新元素位置（pos是一个提示，提示安插动作的查找起点，若提示恰当可以加快速度）
3     c.insert(beg,end); //将区间[beg,end)内所有元素的拷贝安插到c(无返回值)
4     c.erase(val);      //移除与val相等的所有元素，返回被移除的元素个数
5     c.erase(pos);      //移除iterator位置pos上的元素，无返回值
6     c.erase(beg,end);  //移除区间[beg,end)内的所有元素，无返回值
7     c.clear();         //移除所有元素，清空容器

 

特殊的是，因为set不允许重复元素的出现，所以会出现安插重复元素失败的情况，为此，标准库做出了应对，set安插操作的返回类型是以pair组织起来的两个值

1.pair结构中的first成员表示新成员（或现存的同值元素的位置）

2.pair结构中的second成员表示是否安插成功

才疏学浅，目前只能总结到这个程度，如果能有什么帮助到您，我会非常开心>-<

2019-01-30