STL之set

2019-11-08 19:26:08

字体：大中小

来源：转载

供稿：网友

首先要知道set是STL中的一种标准关联容器（例如set，map，multiset，multimap都是标准关联容器，而像vector,list,string,deque这些都是序列容器），那什么是关联式容器，什么又是序列容器呢？关联容器与序列容器的区别在于：关联容器是通过键存储和读取元素的，而序列容器则是通过元素在容器中的位置顺序存储和访问元素的。 set特性： set的底层其实就是使用平衡搜索树——红黑树(RB-tree)实现的,所以他的插入和删除操作只需要用迭代器操作节点即可完成（但不能通过迭代器改变它的元素值，因为它的键值就是元素值，改变会影响它的排列规则，当然STL也不会给你改变键值的接口），不需要内存移动和拷贝，所以效率函数比较高的。另外set里所有元素都会根据键值自动被排列（并且默认进行升序排列），跟map不同的是，map同时拥有实值和键值，而set只有键值，或者说它的实值就是键值，键值就是实值，同时set不允许两个元素有相同的键值。 set的标准形式是

template < class T, // set::key_type/value_type class Compare = less<T>, // set::key_compare/value_compare class Alloc = allocator<T> // set::allocator_type > class set;

这里写图片描述

我们来看看set的接口：由于set底层是由RB-tree实现的，所以set的大部分接口红黑树都提供了，几乎都在转调用RB-tree的操作。

insert接口中原型是这样的：

这里写图片描述

pair类型： pair模板类用来绑定两个对象为一个新的对象，该类型在头文件中定义。pair类型提供的操作如下表： pair

template<typename K, typename V>struct pair{ K first; V value;}

现在因为它的value是不存在的，前面说过它只有键值，value存的是bool类型,如果插入成功返回true，失败返回false。这里insert有两种情况，一种是已存在的，一种不存在的，不存在的返回的pair是返回插入的迭代器，bool返回的是ture，对于已经存在的，返回的是已经存在的迭代器，第二个参数bool返回false。下面可以验证一下。

std::set<int> s; s.insert(3); pair<set<int>::iterator, int > ret1 = s.insert(4); s.insert(ret1.first, 12); cout << ret1.second << endl; pair<set<int>::iterator, int >ret = s.insert(3); cout<<ret.second<<endl; system("pause"); return 0;

输出的是1 0也就是对应的true false。最后验证一下它不允许两个相同键值存储：

int main(){ set<int> s; s.insert(5); s.insert(2); s.insert(3); s.insert(1); s.insert(3); set<int>::iterator it = s.begin(); while (it != s.end()) { cout << *it << " "; it++; } cout << endl; system("pause"); return 0;}

这里写图片描述发现set已经按照默认升序排列完成，并且没有将重复出现的3插入。