11:59 by youxin, ... 阅读,
这是微软帮助文档中对集合（set）的解释： &描述了一个控制变长元素序列的对象（注：set中的key和value是Key类型的，而map中的key和value是一个pair结构中的两个分 量）的模板类，每一个元素包含了一个排序键（sort key）和一个值(value)。对这个序列可以进行查找、插入、删除序列中的任意一个元素，而完成这些操作的时间同这个序列中元素个数的对数成比例关 系，并且当游标指向一个已删除的元素时，删除操作无效。&而一个经过更正的和更加实际的定义应该是：一个集合（set）是一个容器，它其中所包含的元素的值是唯一的。这在收集一个数据的具体值的时候是有用的。集 合中的元素按一定的顺序排列，并被作为集合中的实例。如果你需要一个键/值对（pair）来存储数据，map是一个更好的选择。一个集合通过一个链表来组 织，在插入操作和删除操作上比向量（vector）快，但查找或添加末尾的元素时会有些慢。
#include&iostream&
#include&string&
#include&set&
using namespace
int main()
set&string&
set&string&::
strset.insert("apple");
strset.insert("orange");
strset.insert("grapes");
strset.insert("grapes");
for(iter=strset.begin();iter!=strset.end();iter++)
cout&&*iter&&
applegrapesorange
//注意：输出的集合中的元素是按字母大小顺序排列的，而且每个值都不重复。&如果你感兴趣的话，你可以将输出循环用下面的代码替换：copy(strset.begin(), strset.end(), ostream_iterator＜string＞(cout, " "));&
另一个例子：
#include&iostream&
#include&set&
using namespace
struct stu{
char a[10];
class stu1:greater&stu&
operator () (stu b1,stu b2) const{
return b1.s&b2.s;
set&stu,stu1 &
for(int i=0;i&3;i++){
cin&&d.a&&d.s;
a.insert(d);
set&stu,stu1 &::
for(l=a.begin();l!=a.end();l++){
cout&&l-&a&&" "&&l-&s&&
注意:set第二个参数为仿函数，不能写成函数。
我在类中写成员函数operator()报错，不知为什么。
set/multiset会根据待定的排序准则，自动将元素排序。两者不同在于前者不允许元素重复，而后者允许。
1) 不能直接改变元素值，因为那样会打乱原本正确的顺序，要改变元素值必须先删除旧元素，则插入新元素
2) 不提供直接存取元素的任何操作函数，只能通过迭代器进行间接存取，而且从迭代器角度来看，元素值是常数
3) 元素比较动作只能用于型别相同的容器(即元素和排序准则必须相同)
set模板原型：//Key为元素(键值)类型
template &class Key, class Compare=less&Key&, class Alloc=STL_DEFAULT_ALLOCATOR(Key) &
从原型可以看出，可以看出比较函数对象及内存分配器采用的是默认参数，因此如果未指定，它们将采用系统默认方式，
另外，利用原型，可以有效地辅助分析创建对象的几种方式
#include &iostream&
#include &string&
#include &set&
using namespace
struct strLess
bool operator() (const char *s1, const char *s2) const
return strcmp(s1, s2) & 0;
void printSet(set&int& s)
copy(s.begin(), s.end(), ostream_iterator&int&(cout, ", ") );
// set&int&::
// for (iter = s.begin(); iter != s.end(); iter++)
//cout&&"set["&&iter-s.begin()&&"]="&&*iter&&", "; //Error
cout&&*iter&&", ";
void main()
//创建set对象，共5种方式，提示如果比较函数对象及内存分配器未出现，即表示采用的是系统默认方式
//创建空的set对象，元素类型为int，
set&int& s1;
//创建空的set对象，元素类型char*，比较函数对象(即排序准则)为自定义strLess
set&const char*, strLess& s2( strLess);
//利用set对象s1,拷贝生成set对象s2
set&int& s3(s1);
//用迭代区间[&first, &last)所指的元素，创建一个set对象
int iArray[] = {13, 32, 19};
set&int& s4(iArray, iArray + 3);
//用迭代区间[&first, &last)所指的元素，及比较函数对象strLess，创建一个set对象
const char* szArray[] = {"hello", "dog", "bird" };
set&const char*, strLess& s5(szArray, szArray + 3, strLess() );
//元素插入：
//1,插入value，返回pair配对对象，可以根据.second判断是否插入成功。(提示:value不能与set容器内元素重复)
//pair&iterator, bool& insert(value)
//2,在pos位置之前插入value，返回新元素位置，但不一定能插入成功
//iterator insert(&pos, value)
//3,将迭代区间[&first, &last)内所有的元素，插入到set容器
//void insert[&first, &last)
cout&&"s1.insert() : "&&
for (int i = 0; i &5 ; i++)
s1.insert(i*10);
printSet(s1);
cout&&"s1.insert(20).second = "&&;
if (s1.insert(20).second)
cout&&"Insert OK!"&&
cout&&"Insert Failed!"&&
cout&&"s1.insert(50).second = "&&
if (s1.insert(50).second)
{cout&&"Insert OK!"&& printSet(s1);}
cout&&"Insert Failed!"&&
cout&&"pair&set&int&::iterator::iterator, bool&\np = s1.insert(60);\nif (p.second):"&&
pair&set&int&::iterator::iterator, bool&
p = s1.insert(60);
if (p.second)
{cout&&"Insert OK!"&& printSet(s1);}
cout&&"Insert Failed!"&&
//元素删除
//1,size_type erase(value) 移除set容器内元素值为value的所有元素，返回移除的元素个数
//2,void erase(&pos) 移除pos位置上的元素，无返回值
//3,void erase(&first, &last) 移除迭代区间[&first, &last)内的元素，无返回值
//4,void clear()， 移除set容器内所有元素
cout&&"\ns1.erase(70) = "&&
s1.erase(70);
printSet(s1);
cout&&"s1.erase(60) = "&&
s1.erase(60);
printSet(s1);
cout&&"set&int&::iterator iter = s1.begin();\ns1.erase(iter) = "&&
set&int&::iterator iter = s1.begin();
s1.erase(iter);
printSet(s1);
//元素查找
//count(value)返回set对象内元素值为value的元素个数
//iterator find(value)返回value所在位置，找不到value将返回end()
//lower_bound(value),upper_bound(value), equal_range(value) 略
cout&&"\ns1.count(10) = "&&s1.count(10)&&", s1.count(80) = "&&s1.count(80)&&
cout&&"s1.find(10) : ";
if (s1.find(10) != s1.end())
cout&&"OK!"&&
cout&&"not found!"&&
cout&&"s1.find(80) : ";
if (s1.find(80) != s1.end())
cout&&"OK!"&&
cout&&"not found!"&&
//其它常用函数
cout&&"\ns1.empty()="&&s1.empty()&&", s1.size()="&&s1.size()&&
set&int& s9;
s9.insert(100);
cout&&"s1.swap(s9) :"&&
s1.swap(s9);
cout&&"s1: "&&
printSet(s1);
cout&&"s9: "&&
printSet(s9);
//lower_bound,upper_bound,equal_range(略)
///////////////i测试结果/////////////////////////
s1.insert() :
0, 10, 20, 30, 40,
s1.insert(20).second =
Insert Failed!
s1.insert(50).second =
Insert OK!
0, 10, 20, 30, 40, 50,
pair&set&int&::iterator::iterator, bool&
p = s1.insert(60);
if (p.second):
Insert OK!
0, 10, 20, 30, 40, 50, 60,
s1.erase(70) =
0, 10, 20, 30, 40, 50, 60,
s1.erase(60) =
0, 10, 20, 30, 40, 50,
set&int&::iterator iter = s1.begin();
s1.erase(iter) =
10, 20, 30, 40, 50,
s1.count(10) = 1, s1.count(80) = 0
s1.find(10) : OK!
s1.find(80) : not found!
s1.empty()=0, s1.size()=5
s1.swap(s9) :
所有的STL容器容器（Container）的概念的出现早于模板（template），它原本是一个计算机科学领域中的一个重要概念，但在这里，它的概念和STL混合在一起了。下面是在STL中出现的7种容器：vector（向量）&&STL中标准而安全的数组。只能在vector 的&前面&增加数据。deque（双端队列double-ended queue）&&在功能上和vector相似，但是可以在前后两端向其中添加数据。&list（列表）&&游标一次只可以移动一步。如果你对链表已经很熟悉，那么STL中的list则是一个双向链表（每个节点有指向前驱和指向后继的两个指针）。set（集合）&&包含了经过排序了的数据，这些数据的值(value)必须是唯一的。map（映射）&&经过排序了的二元组的集合，map中的每个元素都是由两个值组成，其中的key（键值，一个map中的键值必须是唯一的）是在排序 或搜索时使用，它的值可以在容器中重新获取；而另一个值是该元素关联的数值。比如，除了可以ar[43] = "overripe"这样找到一个数据，map还可以通过ar["banana"] = "overripe"这样的方法找到一个数据。如果你想获得其中的元素信息，通过输入元素的全名就可以轻松实现。multiset（多重集）&&和集合（set）相似，然而其中的值不要求必须是唯一的（即可以有重复）。multimap（多重映射）&&和映射（map）相似，然而其中的键值不要求必须是唯一的（即可以有重复）。注意：如果你阅读微软的帮助文档，你会遇到对每种容器的效率的陈述。比如：log(n*n)的插入时间。除非你要处理大量的数据，否则这些时间的影响是可 以忽略的。如果你发现你的程序有明显的滞后感或者需要处理时间攸关（time critical）的事情，你可以去了解更多有关各种容器运行效率的话题。怎样在一个map中使用类？Map是一个通过key（键）来获得value(值)的模板类。另一个问题是你希望在map中使用自己的类而不是已有的数据类型，比如现在已经用过的int。建立一个&为模板准备的（template-ready）&类，你必须确保在该类中包含一些成员函数和重载操作符。下面的一些成员是必须的：缺省的构造函数（通常为空）拷贝构造函数重载的&=&运算符你应该重载尽可能多的运算符来满足特定模板的需要，比如，如果你想定义一个类作为 map中的键（key），你必须重载相关的运算符。但在这里不对重载运算符做过多讨论了。//程序：映射自定义的类。//目的：说明在map中怎样使用自定义的类。#include ＜string＞#include ＜iostream＞#include ＜vector＞#include ＜map＞class CStudent{public :int nStudentID;int nApublic ://缺省构造函数&&通常为空CStudent() { }// 完整的构造函数CStudent(int nSID, int nA) { nStudentID=nSID; nAge=nA; }//拷贝构造函数CStudent(const CStudent& ob)&{&nStudentID=ob.nStudentID; nAge=ob.nA }// 重载&=&void operator = (const CStudent& ob)&{nStudentID=ob.nStudentID; nAge=ob.nA&}};int main(int argc, char* argv[]){map ＜string, CStudent＞ mapSmapStudent["Joe Lennon"] = CStudent();mapStudent["Phil McCartney"] = CStudent();mapStudent["Raoul Starr"] = CStudent();mapStudent["Gordon Hamilton"] = CStudent();// 通过姓名来访问Cstudent类中的成员cout ＜＜ "The Student number for Joe Lennon is " ＜＜&(mapStudent["Joe Lennon"].nStudentID) ＜＜return 0;}&TYPEDEF如果你喜欢使用typedef关键字，下面是个例子：typedef set ＜int＞ SET_INT;typedef SET_INT::iterator SET_INT_ITER&编写代码的一个习惯就是使用大写字母和下划线来命名数据类型。ANSI / ISO字符串ANSI/ISO字符串在STL容器中使用得很普遍。这是标准的字符串类，并得到了广泛地提倡，然而在缺乏格式声明的情况下就会出问题。你必须使用&＜＜&和输入输出流（iostream）代码（如dec, width等）将字符串串联起来。
参考了：可在必要的时候使用c_str()来重新获得字符指针。
set是关联容器。其键值就是实值，实值就是键值，不可以有重复，所以我们不能通过set的迭代器来改变set的元素的值，set拥有和list相同的特
性：当对他进行插入和删除操作的时候，操作之前的迭代器依然有效。当然删除了的那个就没效了。set的底层结构是RB-tree，所以是有序的。
&& stl中特别提供了一种针对set的操作的算法：交集set_intersection，并集set_union，差集set_difference。对称差集set_symeetric_difference，这
些算法稍后会讲到。
一：set模板类的声明。
template &&& class Key,&&& class Traits=less&Key&,&&& class Allocator=allocator&Key&&&class set。
其中个参数的意义如下：
key：要放入set里的数据类型，可以是任何类型的数据。
Traits：这是一个仿函数（关于仿函数是什么，我后面的文章会讲到）。提供了具有比较功能的仿函数，来觉得元素在set里的排列的顺序，这是
一个可选的参数，默认的是std::less&key&，如果要自己提供这个参数，那么必须要遵循此规则：具有两个参数，返回类型为bool。
Allocator:空间配置器，这个参数是可选的，默认的是std::allocator&key&.
二：set里的基本操作
我们可以通过下面的方法来实例化一个set对象
std::set&int&那个s这个对象里面存贮的元素是从小到大排序的，(因为用std::less作为比较工具。)
如果要想在s里面插入数据，可以用inset函数（set没用重载[]操作，因为set本生的值和索引是相同的)
s.insert(3);s.insert(5).....
因为set是集合，那么集合本身就要求是唯一性，所以如果要像set里面插入数据和以前的数据有重合，那么插入不成功。
可以通过下面的方法来遍历set里面的元素
std::set&int&::iterator it = s.begin();while(it!=s.end()){&& cout&&*it++&&//迭代器依次后移，直到末尾。}
如果要查找一个元素用find函数，it = s.find(3);这样it是指向3的那个元素的。可以通过rbegin，rend来逆向遍历
std::set&int&::reverse_iterator it = s.rbegin();
while(it!=s.rend())
{cout&&*it++&&}
还有其他的一些操作在这就不一一列出了。
三：与set相关的一组算法
set_intersection() :这个函数是求两个集合的交集。下面是stl里的源代码
template&class _InIt1,class _InIt2,class _OutIt& inline_OutIt set_intersection(_InIt1 _First1, _InIt1 _Last1,&& _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest){ // AND sets [_First1, _Last1) and [_First2, _Last2), using operator&for (; _First1 != _Last1 && _First2 != _Last2; )&& if (*_First1 & *_First2)&&& ++_First1;&& else if (*_First2 & *_First1)&&& ++_First2;&& else&&& *_Dest++ = *_First1++, ++_First2;return (_Dest);}
这是个模板函数，从上面的算法可以看出，传进去的两个容器必须是有序的。_Dest指向输出的容器，这个容器必须是预先分配好空间的，否则
会出错的,返回值指向保存结果的容器的尾端的下一个位置。eg.
set_union() :求两个集合的并集，参数要求同上。
std::set_difference（）：差集
set_symmetric_difference（）：得到的结果是第一个迭代器相对于第二个的差集并上第二个相当于第一个的差集。代码：
struct compare{bool operator ()(string s1,string s2){&& return s1&s2;}///自定义一个仿函数};int main(){typedef std::set&string,compare& _SET;_SETs.insert(string("sfdsfd"));s.insert(string("apple"));s.insert(string("english"));s.insert(string("dstd"));cout&&"s1:"&&std::set&string,compare&::iterator it = s.begin();while(it!=s.end())&& cout&&*it++&&"&& ";cout&&endl&&"s2:"&&_SET s2;s2.insert(string("abc"));s2.insert(string("apple"));s2.insert(string("english"));it = s2.begin();while(it!=s2.end())&& cout&&*it++&&"&& ";cout&&endl&&
string str[10];string *end = set_intersection(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//求交集，返回值指向str最后一个元素的尾端cout&&"result of set_intersection s1,s2:"&&&& string *first =&& while(first&end)&&& cout &&*first++&&" ";&& cout&&endl&&endl&&"result of set_union of s1,s2"&&&& end = std::set_union(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//并集&& first =&& while(first&end)&&& cout &&*first++&&" ";&& cout&&endl&&endl&&"result of set_difference of s2 relative to s1"&&&&& first =&& end = std::set_difference(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//s2相对于s1的差集&& while(first&end)&&& cout &&*first++&&" ";&& cout&&endl&&endl&&"result of set_difference of s1 relative to s2"&&&&& first =&& end = std::set_difference(s2.begin(),s2.end(),s.begin(),s.end(),str,compare());//s1相对于s2的差集
&& while(first&end)&&& cout &&*first++&&" ";&& cout&&endl&&&& first =end = std::set_symmetric_difference(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//上面两个差集的并集&& while(first&end)&&& cout &&*first++&&" ";&& cout&&&}
set&int&&& s3&& ;&&&set&int&::iterator&& iter&& =&& s3.begin()&& ;&&&set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(),inserter(s3,iter));&&&copy(s3.begin(),s3.end(),&& ostream_iterator&int&(cout,"&& "));一、set和multiset基础
set集合容器：实现了红黑树的平衡二叉检索树的数据结构，插入元素时，它会自动调整二叉树的排列，把元素放到适当的位置，以保证每个子树根节点键值大于左子树所有节点的键值，小于右子树所有节点的键值；另外，还得保证根节点左子树的高度与右子树高度相等。
平衡二叉检索树使用中序遍历算法，检索效率高于vector、deque和list等容器，另外使用中序遍历可将键值按照从小到大遍历出来。
构造set集合主要目的是为了快速检索，不可直接去修改键值。
set和multiset会根据特定的排序准则，自动将元素进行排序。不同的是后者允许元素重复而前者不允许。
需要包含头文件：
#include &set&
set和multiset都是定义在std空间里的类模板：
只要是可复赋值、可拷贝、可以根据某个排序准则进行比较的型别都可以成为它们的元素。第二个参数用来定义排序准则。缺省准则less是一个仿函数，以operator&对元素进行比较。
所谓排序准则，必须定义strict weak ordering，其意义如下：
1、必须使反对称的。
对operator&而言，如果x&y为真，则y&x为假。
2、必须使可传递的。
对operator&而言，如果x&y为真，且y&z为真，则x&z为真。
3、必须是非自反的。
对operator&而言，x&x永远为假。
因为上面的这些特性，排序准则可以用于相等性检验，就是说，如果两个元素都不小于对方，则它们相等。
二、set和multiset的功能
和所有关联式容器类似，通常使用平衡二叉树完成。事实上，set和multiset通常以红黑树实作而成。
自动排序的优点是使得搜寻元素时具有良好的性能，具有对数时间复杂度。但是造成的一个缺点就是：
不能直接改变元素值。因为这样会打乱原有的顺序。
改变元素值的方法是：先删除旧元素，再插入新元素。
存取元素只能通过迭代器，从迭代器的角度看，元素值是常数。
三、操作函数
构造函数和析构函数
set的形式可以是：
有两种方式可以定义排序准则：
1、以template参数定义：
此时，排序准则就是型别的一部分。型别系统确保只有排序准则相同的容器才能被合并。
程序实例：
程序运行会报错。但是如果把s1的排序准则也指定为greater&int&便运行成功。
2、以构造函数参数定义。
这种情况下，同一个型别可以运用不同的排序准则，而排序准则的初始值或状态也可以不同。如果执行期才获得排序准则，而且需要用到不同的排序准则，这种方式可以派上用场。
程序实例：
运行结果：
虽然set1和set2的而比较准则本身不同，但是型别相同，所以可以进行赋值操作。
非变动性操作
注意：元素比较操作只能用于型别相同的容器。
特殊的搜寻函数
赋值
赋值操作两端的容器必须具有相同的型别，但是比较准则本身可以不同，但是其型别必须相同。如果比较准则的不同，准则本身也会被赋值或交换。
迭代器相关函数
元素的插入和删除
注意：插入函数的返回值不完全相同。
set提供的插入函数：
multiset提供的插入函数：
返回值型别不同的原因是set不允许元素重复，而multiset允许。当插入的元素在set中已经包含有同样值的元素时，插入就会失败。所以set的返回值型别是由pair组织起来的两个值：
第一个元素返回新元素的位置，或返回现存的同值元素的位置。第二个元素表示插入是否成功。
set的第二个insert函数，如果插入失败，就只返回重复元素的位置！
但是，所有拥有位置提示参数的插入函数的返回值型别是相同的。这样就确保了至少有了一个通用型的插入函数，在各种容器中有共通接口。
注意：还有一个返回值不同的情况是：作用于序列式容器和关联式容器的erase()函数：
序列式容器的erase()函数：
关联式容器的erase()函数：
这完全是为了性能的考虑。因为关联式容器都是由二叉树实现，搜寻某元素并返回后继元素可能很费时。
五、set应用示例：
上述程序最后新产生一个set：s2，默认排序准则是less。以s1的元素作为初值。
注意：s1和s2有不同的排序准则，所以他们的型别不同，不能直接进行相互赋值或比较。
运行结果：
本文已收录于以下专栏：
相关文章推荐
set和Multiset:
STL之Set和multiset容器STL之Set和multiset容器
setmultiset的简介
对象的默认构造
插入与迭代器
函数对象functor的用法
set对象的拷贝构造与赋值...
原文地址：
http://blog.csdn.net/xiajun/article/details/7459206
一、set和multiset基础
STL中的关联容器set/multiset、map/multimap
（1）：set的含义是集合，它是一个有序的容器，里面的元素都是排序好的，支持插入，删除，查找等操作，就 像一个集合一样。所有的操作的都是严格在logn时间之内完成，效率非常高，具体实现采用了...
STL只规定接口和复杂度，对于具体实现不作要求。set大多以红黑树实现，但STL在标准规格之外提供了一个所谓的hash_set，以hash table实现。hash_set的接口，hash_table...
标准的STL关联式容器分为set（集合）和
使用set或multiset之前，必须加入头文件
Set、multiset都是集合类，差别在与set中不允许有重复元素，multiset中允许有重复元素。
sets和multiset内部以平衡二叉树实...
1.vector,头文件#include
(1) 声明方法：vector 变量；
int main()
    vector IntArray(3);
IntArray[0]...
这四种关联式容器可以分成两组：set和map。
set是一种集合，其中可包含0个或多个不重复的和不排序的元素，然后默认从小到大排序输出。
（若要从大到小排：创建实例set&）
他的最新文章
讲师：王哲涵
讲师：韦玮
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)set/multiset是一个集合容器，我们可以对这个容器进行插入，删除，查找等工作。set的元素内容只有一个键值（key，key和value为同一个值），不允许重复冗余，当对它插入一个已经存在的元素时，它会自动忽略。set/multiset的底层是用红黑树（RBTree）实现，拥有平衡二叉搜索树的结构，所以在进行检索时，效率会很高。而正因为它是一颗红黑树结构，当我们顺序遍历它时，序列是有序的。我们就不能通过迭代器取修改相应的元素的key值。我们可以借源码看到，set的迭代器是红黑树const迭代器的typedef。
multiset大部分功能与set相同，不同之处在于multiset允许出现相同的key值，也就是说允许出现重复的元素。所以再insert，erase的实现上会有所不同。其它都一样。我会再讲到insert，erase时剖析一下不同点，下面以set开讲。
构造/析构函数/赋值运算符重载
它的构造函数实现有三种。
explicit set ( const Compare& comp = Compare(), const Allocator& = Allocator() );`
explicit关键字用来修饰类的构造函数，防止发生隐式的类型转换。也可以理解为防止构造函数被隐式调用。
它有两个参数，Compare是一个类型，Compare()是这个类型的匿名对象。这是一个比较函数，内部是以仿函数的形式来使用它，来实现排序时比较等功能。Allocator是一个空间配置器，它是c++标准库中最神秘的存在。以我现在的水平，还分析不出它。但是对我们理解set也不会有影响。
template &class InputIterator&
set ( InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() );
这个构造函数是以模板形式定义。模板参数InputIterator是一个类型的迭代器。
它有四个参数，前两个参数都是迭代器，（first，last）所表示的是一个左闭右开的区间。可想而知，这个构造函数是以其他容器的一段数据进行构造。后两个参数与上相同。
最后一个，拷贝构造函数，不再多说。
set ( const set&Key,Compare,Allocator&& x );
赋值运算符重载
set&Key,Compare,Allocator&& operator= ( const set&Key,Compare,Allocator&& x );
返回值为一个set的引用，参数为另一个set的引用。
迭代器Iterators:
iterator begin ();
const_iterator begin () const;
正向迭代器，返回第一个元素的位置。
iterator end ();
const_iterator end () const;
正向迭代器，返回最后一个元素的下一个位置。
reverse_iterator rbegin();.
const_reverse_iterator rbegin()
反向迭代器，返回最后一个元素的位置。
reverse_iterator rend();
const_reverse_iterator rend()
反向迭代器，返回第一个元素的前一个位置。
注意：有人可能以为，我调用rbegin()得到的迭代器是最后一个元素的位置，那对这个迭代器进行–(减减)操作就可以从后向前遍历这个set？不是，还是++(加加)。看一个例子：
#include&iostream&
#include&set&
using namespace std;
void TestSet()
for (int i = 0; i & 10; ++i)
s.insert(i);
set&int&::reverse_iterator it = s.rbegin();
while (it != s.rend())
cout && *it && " ";
int main()
TestSet();
system("pause");
输出结果：
bool empty ( ) const;
判空，当为空时返回true，不空时返回false。加const修饰是防止这个函数对类的成员做出修改。
size_type size()
返回set内元素的数量。 const作用同上。
size_type size()
返回能插入元素的最大值，这个数输出来应该是。为什么是这个数，由于系统和库的限制。
调节器Modifiers
set的insert有3种实现
pair&iterator,bool& insert ( const value_type& x );
返回值为一个pair，pair是一个模板类型，有两个模板参数，第一个叫first，第二个叫second。（想深入了解的自己查一下）
这里的first是一个迭代器，第二个参数是一个bool值。
当插入一个新元素时，返回值的first是新插入元素位置的迭代器，second是true。
当插入一个已有的元素时，不插入，返回值得first是已有元素位置的迭代器，second是false。
iterator insert ( iterator position, const value_type& x );
第二种实现的返回值是一个迭代器，第一个参数是一个迭代器位置，第二个参数是要插入的元素。意思是在postion位置插入x。
当插入一个新元素，返回新元素的迭代器。
当插入一个已存在元素，不插入，返回已存在元素的迭代器。
template &class InputIterator&
void insert ( InputIterator first, InputIterator last );
第3种实现，返回值为空，参数是两个模板类型的迭代器，（first，last）是一个左闭右开的区间，意思是将这个区间的元素插入set。可以理解为批量插入。
multiset的insert
multiset的insert定义，返回值，参数与set全部相同，不同之处在于它们耳朵内部实现。我们在开头说过set/multiset的底层实现是红黑树，所以它们大部分的功能函数都是调用的红黑树的函数。我们来看一下insert源码的定义：（参照《STL源码剖析》）
（ps：t是一个红黑树的对象）
我们可以从图中看到，set的insert的三种实现都调用了一个叫insert_unipue()的函数，我们不需要看它的实现了，从字面就可以看出，unique独一无二，这种插入方法不允许出现重复数据。
multiset源码
（ps：注意红色箭头指向的内容，意思是其他函数的实现，multise与set相同）
可以看出不同了吧，multiset底层调用的insert_equal()这个函数。equal什么意思呢？英语不好的就去查吧！^v^!
set的erase三种实现。
void erase ( iterator position );
指定位置擦除，参数为一个迭代器，意思是擦拭position位置的数据。
size_type erase ( const key_type& x );
指定元素擦除，参数为一个数据，意思是擦除键值（key）为x的数据。
void erase ( iterator first, iterator last );
指定区间擦除，擦除左闭右开区间（first，last）的元素。
multiset的erase
我们已经知道了，multiset允许插入相同的元素，删除呢？
void erase ( iterator position );
指定位置删除，与set相同
void erase ( iterator first, iterator last );
删除区间 [first，last）,与set相同。
不同的来了！
size_type erase ( const key_type& x );
指定元素删除，删除参数x。删除key等于x的所有元素。返回删除元素的个数。
void clear ( );
清空所有元素，它内部调用的红黑树的clear。
void swap ( set&Key,Compare,Allocator&& st );
交换两个set的值，返回值为空，参数是另一个set的引用。
key_compare key_comp ( ) const;
这个方法的功能是返回set排序所调用的比较函数。返回值是key_compare，什么是key_compare呢？
查看key_compare的定义，发现它是_Pr的一个typedef
再查看_Pr的定义，
到这里我们就能看到，_Pr是一个名为less的类型。再查看less的定义。
一目了然了吧，less就是一个结构体，它内部实现了对()的重载，功能是比较两个值得大小,left小于right的时候返回true。当把这个结构体类型传入当模版参数时，在类内部就可以以仿函数的形式调用它。
再回来说到，key_compare就是一个类型，key_comp的返回值就是set的比较函数，也可以说是底层红黑树的比较函数。当然我们还可以调用这个比较函数。我们来测一下：
set&int&::key_compare ret2 = s.key_comp();
cout && "less:1&2?" &&
cout && ret2(1, 2) &&
cout && "less:1&2?" &&
cout && ret2(2, 1) &&
value_comp
set的key和value都是同一个值，都是键值（key），所以这个函数与key_comp的功能一样，返回值也相同。
Operations
iterator find ( const key_type& x ) const;
查找一个值x的位置，返回值为迭代器。const保证这个函数内部不对类的成员做出修改。
当这个值x存在时，返回这个值的迭代器。
当这个值x不存在时，返回end（最后一个元素的下一个位置），end是一个不可访问的位置。
set/multiset的find的find函数功能都相同，返回的都是指向第一个匹配元素位置的迭代器。
size_type count ( const key_type& x )
查找一个元素是否存在。返回值类型为size_type（我们理解为size_t）
如果元素存在，返回元素的个数。
如果元素不存在，返回0。
思考：既然set里面不允许出现相同的元素，次数只能是0或1，为什么它要用一个size_type来接收返回值？为什么不用bool？
因为multiset与set的count函数相同，底层都是调用的红黑树的count函数，multiset允许重复数据出现，那就有大于1的次数。所以用size_type。
lower_bound
iterator lower_bound ( const key_type& x ) const;
返回值是一个迭代器，返回指向set中第一个大于等于x的值的迭代器。当没有比x大的元素的时候，返回end。
看一个例子：
我插入的原始数据为 1， 3， 5， 7 ，9
for (int i = 1; i & 10; i+=2)
s.insert(i);
set&int&::iterator it = s.begin();
while (it != s.end())
cout && *it && " ";
cout && "lower_bound: 大于等于0的第一个元素" &&
cout && *(s.lower_bound(0)) &&
cout && "lower_bound: 大于等于1的第一个元素" &&
cout && *(s.lower_bound(1)) &&
cout && "lower_bound: 大于等于2的第一个元素" &&
cout && *(s.lower_bound(2)) &&
cout && "lower_bound: 大于等于3的第一个元素" &&
cout && *(s.lower_bound(4)) &&
cout && "lower_bound: 大于等于4的第一个元素" &&
cout && *(s.lower_bound(6)) &&
upper_bound
iterator upper_bound ( const key_type& x ) const;
返回指向第一个大于x的值的迭代器，例子不再给出，测试方法与上相同。
equal_range
pair&iterator,iterator& equal_range ( const key_type& x ) const;
返回值为一个pair，pair的两个值都是迭代器，这个函数的功能是上面两个函数的结合体。找到指向第一个大于等于x的值的迭代器，存到pair的first里面去。找到指向第一个大于x的值的迭代器，存到pair的second里面去。
看一个例子，插入数据1，3，5，7，9
for (int i = 1; i & 10; i += 2)
s.insert(i);
set&int&::iterator it = s.begin();
while (it != s.end())
cout && *it && " ";
pair&set&int&::iterator, set&int&::iterator& ret = s.equal_range(3);
cout && "pair.first:lower_bound:" && *ret.first &&
cout && "pair.second:upper_bound:" && *ret.second &&
空间配置器等我搞明白了再写出来。。。。。
本文已收录于以下专栏：
相关文章推荐
面试题：实现KNN，给定各个点之间的距离，返回某个点的k个neighbor。
思路： 考虑到A家喜欢问海量数据，所以用heap，复杂度O(nlogk)。 当时是自己实现的heap。后来发现可...
一、set和multiset基础
set和multiset会根据特定的排序准则，自动将元素进行排序。不同的是后者允许元素重复而前者不允许。
需要包含头文件：
set的特性是所有元素都会根据键值自动排序，set的元素不像map那样同时拥有实值（value）和键值（key），set元素的键值就是实值，实值就是键值。Set不允许两个元素拥有相同的键值。不能通过迭...
set和Multiset:
STL之Set和multiset容器STL之Set和multiset容器
setmultiset的简介
对象的默认构造
插入与迭代器
函数对象functor的用法
set对象的拷贝构造与赋值...
原文地址：
http://blog.csdn.net/xiajun/article/details/7459206
一、set和multiset基础
STL中的关联容器set/multiset、map/multimap
（1）：set的含义是集合，它是一个有序的容器，里面的元素都是排序好的，支持插入，删除，查找等操作，就 像一个集合一样。所有的操作的都是严格在logn时间之内完成，效率非常高，具体实现采用了...
STL只规定接口和复杂度，对于具体实现不作要求。set大多以红黑树实现，但STL在标准规格之外提供了一个所谓的hash_set，以hash table实现。hash_set的接口，hash_table...
标准的STL关联式容器分为set（集合）和
他的最新文章
讲师：王哲涵
讲师：韦玮
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)