Set和Map类似，也是一组key的集合，但不存储value。由于key不能重复，所以，在Set中，没有重复的key。

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

greater和less

greater和less是头文件<xfunctional>中定义的两个结构。下面看它们 的定义，greater和less都重载了操作符()。

在sort()函数中使用greater<int>()和less<int>(),

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1.关于set

C++ STL 之所以得到广泛的赞誉，也被很多人使用，不只是提供了像vector, string, list等方便的容器，更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组，list封装了链表，map和set封装了二叉树等，在封装这些数据结构的时候，STL按照程序员的使用习惯，以成员函数方式提供的常用操作，如：插入、排序、删除、查找等。让用户在STL使用过程中，并不会感到陌生。

关于set，必须说明的是set关联式容器。set作为一个容器也是用来存储同一数据类型的数据类型，并且能从一个数据集合中取出数据，在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序。应该注意的是set中数元素的值不能直接被改变。C++ STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树：红黑树，也成为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树，所以被STL选择作为了关联容器的内部结构。

 关于set有下面几个问题：

（1）为何map和set的插入删除效率比用其他序列容器高？

大部分人说，很简单，因为对于关联容器来说，不需要做内存拷贝和内存移动。说对了，确实如此。set容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点。结构图可能如下：

　　A
　  / \
　 B C
　/ \ / \
  D E F G

因此插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点也OK了。这里的一切操作就是指针换来换去，和内存移动没有关系。

（2）为何每次insert之后，以前保存的iterator不会失效？

iterator这里就相当于指向节点的指针，内存没有变，指向内存的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。相对于vector来说，每一次删除和插入，指针都有可能失效，调用push_back在尾部插入也是如此。因为为了保证内部数据的连续存放，iterator指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时push_back的时候，容器内部空间可能不够，需要一块新的更大的内存，只有把以前的内存释放，申请新的更大的内存，复制已有的数据元素到新的内存，最后把需要插入的元素放到最后，那么以前的内存指针自然就不可用了。特别时在和find等算法在一起使用的时候，牢记这个原则：不要使用过期的iterator。

（3）当数据元素增多时，set的插入和搜索速度变化如何？

如果你知道log2的关系你应该就彻底了解这个答案。在set中查找是使用二分查找，也就是说，如果有16个元素，最多需要比较4次就能找到结果，有32个元素，最多比较5次。那么有10000个呢？最多比较的次数为log10000，最多为14次，如果是20000个元素呢？最多不过15次。看见了吧，当数据量增大一倍的时候，搜索次数只不过多了1次，多了1/14的搜索时间而已。你明白这个道理后，就可以安心往里面放入元素了。

2.set中常用的方法

begin()     　　 ,返回set容器的第一个元素

end() 　　　　 ,返回set容器的最后一个元素

clear()   　　     ,删除set容器中的所有的元素

empty() 　　　,判断set容器是否为空

max_size() 　 ,返回set容器可能包含的元素最大个数

size() 　　　　 ,返回当前set容器中的元素个数

rbegin　　　　 ,返回的值和end()相同

rend()　　　　 ,返回的值和rbegin()相同

写一个程序练一练这几个简单操作吧： 

 1 #include <iostream>
 2 #include <set>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     set<int> s;
 9     s.insert(1);
10     s.insert(2);
11     s.insert(3);
12     s.insert(1);
13     cout<<"set 的 size 值为 ："<<s.size()<<endl;
14     cout<<"set 的 maxsize的值为 ："<<s.max_size()<<endl;
15     cout<<"set 中的第一个元素是 ："<<*s.begin()<<endl;
16     cout<<"set 中的最后一个元素是:"<<*s.end()<<endl;
17     s.clear();
18     if(s.empty())
19     {
20         cout<<"set 为空 ！！！"<<endl;
21     }
22     cout<<"set 的 size 值为 ："<<s.size()<<endl;
23     cout<<"set 的 maxsize的值为 ："<<s.max_size()<<endl;
24     return 0;
25 }

运行结果：

小结：插入3之后虽然插入了一个1，但是我们发现set中最后一个值仍然是3哈，这就是set 。还要注意begin() 和 end()函数是不检查set是否为空的，使用前最好使用empty()检验一下set是否为空.

count() 用来查找set中某个某个键值出现的次数。这个函数在set并不是很实用，因为一个键值在set只可能出现0或1次，这样就变成了判断某一键值是否在set出现过了。

示例代码：

 1 #include <iostream>
 2 #include <set>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     set<int> s;
 9     s.insert(1);
10     s.insert(2);
11     s.insert(3);
12     s.insert(1);
13     cout<<"set 中 1 出现的次数是 ："<<s.count(1)<<endl;
14     cout<<"set 中 4 出现的次数是 ："<<s.count(4)<<endl;
15     return 0;
16 }

运行结果：

equal_range() ，返回一对定位器，分别表示第一个大于或等于给定关键值的元素和 第一个大于给定关键值的元素，这个返回值是一个pair类型，如果这一对定位器中哪个返回失败，就会等于end()的值。具体这个有什么用途我还没遇到过~~~

示例代码：

 1 #include <iostream>
 2 #include <set>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     set<int> s;
 9     set<int>::iterator iter;
10     for(int i = 1 ; i <= 5; ++i)
11     {
12         s.insert(i);
13     }
14     for(iter = s.begin() ; iter != s.end() ; ++iter)
15     {
16         cout<<*iter<<" ";
17     }
18     cout<<endl;
19     pair<set<int>::const_iterator,set<int>::const_iterator> pr;
20     pr = s.equal_range(3);
21     cout<<"第一个大于等于 3 的数是 ："<<*pr.first<<endl;
22     cout<<"第一个大于 3的数是 ： "<<*pr.second<<endl;
23     return 0;
24 }

运行结果：

erase(iterator)  ,删除定位器iterator指向的值

erase(first,second),删除定位器first和second之间的值

erase(key_value),删除键值key_value的值

看看程序吧：

 1 #include <iostream>
 2 #include <set>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     set<int> s;
 9     set<int>::const_iterator iter;
10     set<int>::iterator first;
11     set<int>::iterator second;
12     for(int i = 1 ; i <= 10 ; ++i)
13     {
14         s.insert(i);
15     }
16     //第一种删除
17     s.erase(s.begin());
18     //第二种删除
19     first = s.begin();
20     second = s.begin();
21     second++;
22     second++;
23     s.erase(first,second);
24     //第三种删除
25     s.erase(8);
26     cout<<"删除后 set 中元素是 ：";
27     for(iter = s.begin() ; iter != s.end() ; ++iter)
28     {
29         cout<<*iter<<" ";
30     }
31     cout<<endl;
32     return 0;
33 }

运行结果：

小结：set中的删除操作是不进行任何的错误检查的，比如定位器的是否合法等等，所以用的时候自己一定要注意。

find()  ，返回给定值值得定位器，如果没找到则返回end()。

示例代码：

 1 #include <iostream>
 2 #include <set>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int a[] = {1,2,3};
 9     set<int> s(a,a+3);
10     set<int>::iterator iter;
11     if((iter = s.find(2)) != s.end())
12     {
13         cout<<*iter<<endl;
14     }
15     return 0;
16 }

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.

示例代码：

 1 #include <iostream>
 2 #include <set>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int a[] = {1,2,3};
 9     set<int> s;
10     set<int>::iterator iter;
11     s.insert(a,a+3);
12     for(iter = s.begin() ; iter != s.end() ; ++iter)
13     {
14         cout<<*iter<<" ";
15     }
16     cout<<endl;
17     pair<set<int>::iterator,bool> pr;
18     pr = s.insert(5);
19     if(pr.second)
20     {
21         cout<<*pr.first<<endl;
22     }
23     return 0;
24 }

运行结果：

lower_bound(key_value) ，返回第一个大于等于key_value的定位器

upper_bound(key_value)，返回最后一个大于等于key_value的定位器

示例代码：

 1 #include <iostream>
 2 #include <set>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     set<int> s;
 9     s.insert(1);
10     s.insert(3);
11     s.insert(4);
12     cout<<*s.lower_bound(2)<<endl;
13     cout<<*s.lower_bound(3)<<endl;
14     cout<<*s.upper_bound(3)<<endl;
15     return 0;
16 }

运行结果：

++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++

自定义比较函数

         使用insert将元素插入到集合中去的时候，集合会根据设定的比较函数奖该元素放到该放的节点上去。在定义集合的时候，如果没有指定比较函数，那么采用默认的比较函数，即按键值从小到大的顺序插入元素。但在很多情况下，需要自己编写比较函数。

编写比较函数有两种方法。

(1)如果元素不是结构体，那么可以编写比较函数。下面的程序比较规则为按键值从大到小的顺序插入到集合中。

+++++++++++++++++++++++++++++++++++++++++++++++++++++++

【C++ STL】Set和Multiset

1、结构

　　set和multiset会根据特定的排序原则将元素排序。两者不同之处在于，multisets允许元素重复，而set不允许重复。

　　只要是assignable、copyable、comparable（根据某个排序准则）的型别T，都可以成为set或者multisets的元素。如果没有特别的排序原则，采用默认的less，已operator < 对元素进行比较，以便完成排序。

排序准则必须遵守以下原则：

•  必须是“反对称的”，对operator <而言，如果x < y为真，y<x为假。

•  必须是“可传递的”，对operator <而言，如果x<y为真，y<z为真，那么x<z也为真。

•  必须是“非自反的”，对operator<而言，x<x永远为假。

2、能力

　　和所有的标准关联容器类似，sets和multisets通常以平衡二叉树完成。

　　自动排序的主要优点在于使二叉树搜寻元素具有良好的性能，在其搜索函数算法具有对数复杂度。但是自动排序也造成了一个限制，不能直接改变元素值，因为这样会打乱原有的顺序，要改变元素的值，必须先删除旧元素，再插入新元素。所以sets和multisets具有以下特点：

• 不提供直接用来存取元素的任何操作元素
• 通过迭代器进行元素的存取。

3、操作函数

3.1 构造、拷贝、析构

3.2 非变动性操作

3.3 特殊的搜寻函数

　　sets和multisets在元素快速搜寻方面做了优化设计，提供了特殊的搜寻函数，所以应优先使用这些搜寻函数，可获得对数复杂度，而非STL的线性复杂度。比如在1000个元素搜寻，对数复杂度平均十次，而线性复杂度平均需要500次。

3.4 赋值

3.5 迭代器相关函数

　　sets和multisets的迭代器是双向迭代器，对迭代器操作而言，所有的元素都被视为常数，可以确保你不会人为改变元素值，从而打乱既定顺序，所以无法调用变动性算法，如remove()。

3.6 安插和删除元素

　　必须保证参数有效,迭代器必须指向有效位置，序列起点不能位于终点之后，不能从空容器删除元素。

4、示例代码

4.1 set

// cont/set1.cpp

    #include <iostream>
    #include <set>
    using namespace std;

    int main()
    {

       /*type of the collection:
        *-no duplicates
        *-elements are integral values
        *-descending order
        */
       typedef set<int,greater<int> > IntSet;

       IntSet coll1;         // empty set container

       //insert elements in random order
       coll1.insert(4);
       coll1.insert(3);
       coll1.insert(5);
       coll1.insert(1);
       coll1.insert(6);
       coll1.insert(2);
       coll1.insert(5);

       //iterate over all elements and print them
       IntSet::iterator pos;
       for (pos = coll1.begin(); pos != coll1.end(); ++pos) {
           cout << *pos << ' ';
       }
       cout << endl;

       //insert 4 again and process return value
       pair<IntSet::iterator,bool> status = coll1.insert(4);
       if (status.second) {
           cout << "4 inserted as element "
                << distance (coll1.begin(),status. first) + 1
                << endl;
       }
       else {
           cout << "4 already exists" << endl;
       }

       //assign elements to another set with ascending order
       set<int> coll2(coll1.begin(),
                      coll1.end());

       //print all elements of the copy
       copy (coll2.begin(), coll2.end(),
             ostream_iterator<int>(cout," "));
       cout << endl;

       //remove all elements up to element with value 3
       coll2.erase (coll2.begin(), coll2.find(3));

       //remove all elements with value 5
       int num;
       num = coll2.erase (5);
       cout << num << " element(s) removed" << endl;

       //print all elements
       copy (coll2.begin(), coll2.end(),
             ostream_iterator<int>(cout," "));
       cout << endl;
    }

输出：

   6 5 4 3 2 1
   4 already exists
   1 2 3 4 5 6
   1 element(s) removed
   3 4 6

4.2 multiset

 // cont/mset1.cpp

   #include <iostream>
   #include <set>
   using namespace std;

   int main()
   {

       /*type of the collection:
        *-duplicates allowed
        *-elements are integral values
        *-descending order
        */
       typedef multiset<int,greater<int> > IntSet;

       IntSet coll1,        // empty multiset container

       //insert elements in random order
       coll1.insert(4);
       coll1.insert(3);
       coll1.insert(5);
       coll1.insert(l);
       coll1.insert(6);
       coll1.insert(2);
       coll1.insert(5);

       //iterate over all elements and print them
       IntSet::iterator pos;
       for (pos = coll1.begin(); pos != coll1.end(); ++pos) {
           cout << *pos << ' ';
       }
       cout << endl;

       //insert 4 again and process return value
       IntSet::iterator ipos = coll1.insert(4);
       cout << "4 inserted as element "
            << distance (coll1.begin(),ipos) + 1
            << endl;

       //assign elements to another multiset with ascending order
       multiset<int> coll2(coll1.begin(),
                              coll1.end());

       //print all elements of the copy
       copy (coll2.begin(), coll2.end(),
             ostream_iterator<int>(cout," "));
       cout << endl;

       //remove all elements up to element with value 3
       coll2.erase (coll2.begin(), coll2.find(3));

       //remove all elements with value 5
       int num;
       num = coll2.erase (5);
       cout << num << " element(s) removed" << endl;

       //print all elements
       copy (coll2.begin(), coll2.end(),
             ostream_iterator<int>(cout," "));
       cout << endl;
   }

输出：

6 5 5 4 3 2 1
4 inserted as element 5
1 2 3 4 4 5 5 6
2 element(s) removed
3 4 4 6