- 关与set的认识，由于最近写了一道题，问了好多人，大部分都说用set或hash ，，（哈哈…….）.这东西在我脑子里一片空白。搜索了部分博友的博客。顺便尝试了一下，感觉挺好用的，总结一下他们的博文。
set有几个常见的问题：
- 为何map和set的插入删除效率比用其他序列容器高？
大部分人说很贱，因为对于关联容器来说，不许做内存拷贝和内存移动。确实如此。set容器内所有元素都是一节点的方式来存储的，器节点结构和链表差不多，指向父节点和子节点。结构图如下：
为何每次insert之后，以前保存的iterator不会失效？
iterator这里就相当于指向节点的指针，内存没有变，指向指向内存的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。相对于vector来说，每一次删除和插入，指针都有可能失效，调用push_back在尾部插入也是如此。因为为了保证内部数据的连续存放，iterator指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时push_back的时候，容器内部空间可能不够，需要一块新的更大的内存，只有把以前的内存释放，申请新的更大的内存，复制已有的数据元素到新的内存，最后把需要插入的元素放到最后，那么以前的内存指针自然就不可用了。特别时在和find等算法在一起使用的时候，牢记这个原则：不要使用过期的iterator。
当数据元素增多时，set的插入和搜索速度变化如何？
如果你知道log2的关系你应该就彻底了解这个答案。在set中查找是使用二分查找，也就是说，如果有16个元素，最多需要比较4次就能找到结果，有32个元素，最多比较5次。那么有10000个呢？最多比较的次数为log10000，最多为14次，如果是20000个元素呢？最多不过15次。看见了吧，当数据量增大一倍的时候，搜索次数只不过多了1次，多了1/14的搜索时间而已。你明白这个道理后，就可以安心往里面放入元素了。
- set中的常用操作
- begin（） //返回set容器的第一个元素
- end（） //返回set容器的最后一个元素
- clear（） //删除set容器的最后一个元素
- empty() //判断set容器是否为空
- max_size（） // 返回set容器可能包含的元素的最大个数
- size（） //返回当前set容器中的元素个数
- rbegin（） //返回的值和end（）相同
- rend（） //返回的值和rbegin（）相同
- 程序练习：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
int main(){
set<int>s;
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(1);
cout<<"set 的 size值为："<<s.size()<<endl;
cout<<"set 的 maxsize的值为："<<s.max_size()<<endl;
cout<<"set 的第一个元素是："<<*s.begin()<<endl;
cout<<"set 的最后的元素是："<<*s.end()<<endl;
cout<<"set 中的1出现的次数"<<s.count(1)<<endl;
cout<<"set 中的4出现的次数"<<s.count(4)<<endl;
s.clear();
if(s.empty()){
cout<<"set 为空"<<endl;
}
cout<<"set 的size值为："<<s.size()<<endl;
cout<<"set 的 maxsize的值为："<<s.max_size()<<endl;
return 0;
}
- 结论：插入3之后插入了1 ，但我们发现set中最后一个值仍然是3哈，这就是set。还要注意begin()和end（）函数是检查set是否为空的，使用前最好empty()检验一下set是否为空。cout()是用来查找set中某个键值出现的次数。这个函数在set并不是很实用，因为一个键值在set只可能出现0或1此，这样就变成了判断某一个键值是否在set出现了。
- equal_range() ，返回一对定位器，分别表示第一个大于或等于给定关键值的元素和 第一个大于给定关键值的元素，这个返回值是一个pair类型，如果这一对定位器中哪个返回失败，就会等于end()的值。具体这个有什么用途我还没遇到过~~~
程序如下：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
int main(){
set<int>s;
set<int>::iterator iter;
for(int i=1;i<=5;++i){
s.insert(i);
}
for(iter =s.begin();iter!=s.end();++iter){
cout<<*iter<<" ";
}
cout<<endl;
pair<set<int>::const_iterator,set<int>::const_iterator>pr;
pr=s.equal_range(3);
cout<<"第一个大于等于3的数是："<<*pr.first<<endl;
cout<<"第一个大于3的数是："<<*pr.second<<endl;
return 0;
}
删除操作
erase(iterator) ,删除定位器iterator指向的值
erase(first,second),删除定位器first和second之间的值
erase(key_value),删除键值key_value的值
程序 ：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
int main(){
set<int>s;
set<int>::const_iterator iter;
set<int>::iterator first;
set<int>::iterator second;
for(int i=1;i<=10;++i){
s.insert(i);
}
s.erase(s.begin());
first=s.begin();
second=s.begin();
second++;
second++;
s.erase(first,second);
s.erase(8);
cout<<"删除后set中的元素是：";
for(iter =s.begin();iter!=s.end();++iter){
cout<<*iter<<" ";
}
cout<<endl;
return 0;
}
注意：set中的删除操作是不进行任何的错误检查的，比如定位器的是否合法等等，所以用的时候自己一定要注意。
- find() ，返回给定值值得定位器，如果没找到则返回end()。
程序如下：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
int main(){
int a[]={1,2,3};
set<int>s(a,a+3);
set<int>::iterator iter;
if((iter = s.find(8))!=s.end()){
cout<<*iter<<endl;
}
return 0;
}
- insert(key_value); 将key_value插入到set中 ，返回值是pair<set<int>::iterator,bool>，bool标志着插入是否成功，而iterator代表插入的位置，若key_value已经在set中，则iterator表示的key_value在set中的位置。
- inset(first,second);将定位器first到second之间的元素插入到set中，返回值是void.
程序代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
int main(){
int a[]={1,2,3};
set<int>s;
set<int<::iterator iter;
s.insert(a,a+3);
for(iter=s.begin();iter!=s.end();++iter){
cout<<*iter<<" ";
}
cout<<endl;
pair<set<int>::iterator,bool>pr;
pr=s.insert(5);
if(pr.second){
cout<<*pr.first<<endl;
}
return 0;
}
- upper_bound（i） 返回的是键值为i的元素可以插入的最后一个位置（上界）
- lowe_bound（i） 返回的是键值为i的元素可以插入的位置的第一个位置（下界）。
实例代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
int main(){
set<int>s;
s.insert(1);
s.insert(3);
s.insert(4);
cout<<*s.lower_bound(2)<<endl;
cout<<*s.lower_bound(3)<<endl;
cout<<*s.upper_bound(1)<<endl;
return 0;
}
- 怎么理解呢，举例：
在升序的set里面
set里没有元素i的时候，两个元素的返回值是一样的。 1 2 4 5 这个序列，upp（3）和low（3）都返回位置2（下标）
如果只有一个元素i，low返回那个元素的位置，而upp返回那个元素的位置的后一个位置。
1 2 4 5 这个序列upp（2）返回下标2而low（2）返回下标1多个元素i，low返回那个元素的位置，upp返回那多个元素中的最后一个的后一个位置。
1 2 2 4 5 这个序列 upp（2）返回下标3的位置，low（2）返回下标1的位置。特别注意：举例在一个升序的容器里，如果所有元素都大于i则，upp和low都返回begin。都小于i则返回end（越界了）。
terator lower_bound( const key_type &key ): 返回一个迭代器，指向键值>= key的第一个元素。
- iterator upper_bound( const key_type &key ):返回一个迭代器，指向键值<=key的最后一个元素的后一个元素。
- 降序排列的容器：
iterator lower_bound( const key_type &key ): 返回一个迭代器，指向键值<= key的第一个元素。
iterator upper_bound( const key_type &key ):返回一个迭代器，指向键值>=key的最后一个元素的后一个元素。 - STL源码学习—-lower_bound和upper_bound算法 这个解释的较为详细。
- 结构体类型（struct ）的set 。
程序介绍：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
struct Info
{
string name;
double score;
bool operator < (const Info &a) const // 重载“<”操作符，自定义排序规则
{
//按score由大到小排序。如果要由小到大排序，使用“>”即可。
return a.score < score;
}
};
int main()
{
set<Info> s;
Info info;
//插入三个元素
info.name = "Jack";
info.score = 80;
s.insert(info);
info.name = "Tom";
info.score = 99;
s.insert(info);
info.name = "Steaven";
info.score = 60;
s.insert(info);
set::iterator it;
for(it = s.begin(); it != s.end(); it++)
cout << (*it).name << " : " << (*it).score << endl;
return 0;
}
