C++ Set

定义

set不同于vector,strin,list这种存储容器，set是一种关联式容器，底层是搜二叉；

功能

set可以确定唯一的值，可以排序+去重。

接口

insert()

#include <iostream>
#include<set>
using namespace std;int main(int argc, char** argv) {set<int>s;s.insert(10);s.insert(2);s.insert(4);s.insert(1);set<int> ::iterator it=s.begin();for(;it<=s.end();it++){cout<<*it<<" ";}cout<<endl;return 0;
}

 警告：

 原因：

在C++中，std::set是一个有序的容器，它使用红黑树实现。s.end()返回的是指向最后一个元素之后的位置的迭代器，而不是指向最后一个元素本身的迭代器。因此，将it与s.end()进行比较时，应该使用不等于操作符!=而不是小于等于操作符<=。如果你使用it <= s.end()作为循环条件，当it指向最后一个元素之后的位置时，循环将继续执行，这将导致访问超出s的边界，引发未定义的行为。为了避免这种情况，应该使用it != s.end()作为循环条件，确保只在it指向有效元素时循环执行。

 修改：

set<int> ::iterator it=s.begin();for(;it!=s.end();it++){cout<<*it<<" ";}cout<<endl;

 

	s.insert(10);s.insert(2);s.insert(4);s.insert(1);

第二个1没有插入进去。

之前讲过set底层是一棵搜二叉，搜二叉特点cur比root大往右插，比root小往左插。

找到为空的地方插入节点，如果发现cur与root的value相同，那就返回false；

怎么接收返回值的？

inset（）的类型是pair，pair的第一个参数叫 first ，返回类型是 iterator;

第二个参数叫second，返回类型是 bool

自己写一个看看：

erase()

erase有三种删除方式：迭代器删除，直接删除值，区间删除

 ps:

我们可以先用find找到要删除的数，再用erase（）把这个数删除。

find（）是如果找到这个数就把这个数返回，否则就返回最后一个数，即end；

it=s.find(4);if(it!=s.end()){s.erase(it);}	for(auto ch:s){cout<<ch<<" ";}

 如果要删除的这个数不存在或已经被删除如果迭代器所指向的元素被删除，则该迭代器失效。

此刻find return end，erase(end)会中断。

	s.erase(2);	it=s.find(2);s.erase(it);

 怎么知道是否删除成功呢？

erase()有一个返回值size_type:

size_type是无符号整型，也就是如果删除成功返回1，否则返回0：

lower_bound   upper_bound

	set<int> myset;set<int>::iterator itlow,itup;for (int i=1; i<10; i++)  // 10 20 30 40 50 60 70 80 90myset.insert(i*10);itlow=myset.lower_bound (30);                //       ^itup=myset.upper_bound (60);                 //                   ^myset.erase(itlow,itup);    // 10 20 70 80 90cout << "myset contains:";for (set<int>::iterator it=myset.begin(); it!=myset.end(); ++it)cout << ' ' << *it;cout << '\n';

可以看见是

lower_bound,upper_bound是[ )的状态，左开右闭。

lower_bound返回的肯定是30，upper_bound返回的肯定是70。

所以就会把[30,70)的值全部删除了。

如果这样呢？

  itlow=myset.lower_bound (25);        itup=myset.upper_bound (65);  

还是一样，删除[25,65)之间的数。

equal_range

set<int> myset;for (int i=1; i<=5; i++) myset.insert(i*10);   // myset: 10 20 30 40 50pair<std::set<int>::const_iterator,std::set<int>::const_iterator> ret;ret = myset.equal_range(30);cout << "the first bound points to: " << *ret.first << '\n';cout << "the second bound points to: " << *ret.second << '\n';

equal_range有两个参数，第一个参数lower返回一个>=value的数，第二个参数upper返回一个>value的数。

如果value=35,第一个返回值是>=35的值，因为数组里面没有35，所以返回40，第二个返回值是>35的值，所以返回40：

  ret = myset.equal_range(35);

count

count返回一个size_t，就是如果有valuer返回1，否则返回0：

 可以用来判断某个值是否存在：

	if(s.count(3)) cout<<"3在"<<endl;else cout<<"3不在"<<endl;

set不支持修改，因为被修改了就不是搜索树了：

multiset

set不可以插入重复的值，因为其底层是一个搜二叉，而multiset可以插入重复的值，可以理解为是一个变异的搜二叉：

	multiset<int>s;s.insert(10);s.insert(2);	s.insert(4);s.insert(1);s.insert(1);multiset<int> ::iterator it=s.begin();for(;it!=s.end();it++){cout<<*it<<" ";}cout<<endl;

插入重复的值，放在右边还是左边都可以，假如我们放右边，现在又要插入1个5，这个5放哪里：

虽然是变异的搜二叉，但仍然保持了有序这个特点，因此我们再插入1个5，它肯定和第一个5是挨着的，第一个5又是跟节点，搜二叉按中序走。

跟节点走完之后就是右子树，右子树又按 左->跟->右走，因此，我们想让第二个5和根节点挨着只需要把第二个5放到右子树的最左节点即可，如下图：-+

中序：2 5 5 8 8  8

erase()

直接使用erase也是把所有重复的值删掉：

s.erase(4);

如果用迭代器去查找删除，会删除中序的第一个重复值：

	it=s.find(4);if(it!=s.end()){s.erase(it);}

count

统计1的个数：

数组：111144int ret=myset.count(1);cout<<ret<<endl;输出：4