C++中的set

set集合容器——STL Introduction

set集合容器使用红黑树（Red-Black Tree）来组织泛化的元素数据。每个节点包含一个取值红色或黑色的颜色域，以便利于进行树的平衡处理。作为节点键值元素的插入，必须确保每个子树根节点的键值大于左子树所有节点的键值，而小于右子树所有节点的键值。重复的键值不能插入容器，键值插入也无需指定具体的插入位置，而是按照元素在树中的关联关系，进行位置的插入，检索和删除。

元素数据的检索，使用的是二叉检索树的中序遍历算法，检索的效率高于vector、deque和list等容器。由于采用中序遍历算法可将二叉检索树的键值由小到大遍历排列出来，因此set容器元含了元素间的有序性。
set容器的标准头文件是set，需要先用宏语句“#include <set>”包含进来方可使用。 SGI C++ STL的set头文件代码实现红黑树所需的pair结构体，用到的相关算法和内存分配器的定义，则有stl_tree.h文件包含进来，导入了stl_algorithm.h、st_alloc.h、stl_construct.h和stl_function.h等文件。
为了访问set容器中红黑树的节点元素，在set中定义了对应于中序遍历和逆中序遍历的前向/后向迭代器类型iterator、const_iterator、reverse_iterator和const_reverse_iterator，可用这些类型声明响应的迭代器变量，操作set容器的元素数据。这些迭代器类型可用set<T>::iterator等方式给出（其中T是容器元素的一个具体类型，即键值的类型)。

创建set对象
为了管理set的二叉树链表数据，先用set容器的构造函数，创建一个set对象
(1) set()
用默认的less<T>函数对象和内存分配器，创建一个没有任何数据元素的set对象。
set<int> s;  //创建了空的set对象s，元素类型为整型int;
(2) set(const key_compare& comp)
指定一个比较函数对象 comp 来创建set对象，内存分配器为默认值。
//定义字符串比较函数对象 strLess
struct strLess {
    bool operatro() (const char *s1, const char *s2) const
    {
         return strcmp(s1,  s2)  < 0;
     }
};
//创建set容器对象s
set<const char*, strLess> s(strLess());
(3)set(const set&)
set拷贝构造函数，通过红黑树的拷贝构造函数，实现两个set容器的元素、头结点和节点个数的拷贝。
//set<int> s1;
set<int> s2 (s1);
(4)set(InputIterator first, InputIterator last)
用区间迭代器[first, last)所指的元素，创建一个set对象。
int iArray = { 13, 32,19 };
set<int> s(iArray, iArray+3);
(5)set(InputIterator first, InputIterator last, const key_compare& comp)
用区间迭代器[first, last)所指的元素和comp函数对象，创建一个set对象。
const char* szArray = {"hello", "dog", "bird" };
set<const char* , strLess> s(szArray, szArray+3, strLess() );

元素的插入
set没有尾部插入函数push_back()，元素的插入一般使用insert进行动态检索插入。
(1)pair<iterator, bool> insert(const value_type& v)
将元素v插入set容器，要求v值不与set容器的任何元素重复，否则插入失败。返回一个pair配对对象，提供所插入元素的迭代器位置和true/false插入成功标志。
(2)iterator insert(iterator position, const value_type& v)
将元素v插入set容器，参数position提示可在position位置之前插入v，所返回的插入位置视实际情况而定，不一定能在position位置之前插入。
(3)void insert(inputIterator fist, InputIterator last)
将某迭代器区间[first, last)所指的数据作为元素，插入到set容器。

元素的删除
与插入一样，set容器也具有高效的红黑树元素的删除处理， 并自动重新调整内部的红黑树平衡。
(1) void erase(iterator position)
删除position所指的元素
(2)size_type erase(const key_type& k)
删除等于键值k的那个元素，对于set容器来说，此函数总是返回值1， 因为set容器不会出现重复的元素值（键值）。
(3)void erase(iterator first, iterator last)
删除set迭代器区间[first, last)上的所有元素。
(4)void clear()
删除所有元素，但不会删除内部红黑树的头节点。

元素的遍历访问
set容器的迭代器提供了访问内部红黑树中元素的操作，通常先用begin和end函数找出遍历开始的首元素和结束元素，然后通过迭代器的“++”操作，有小到到大取出元素值。
iterator begin();
iterator  end();

元素的反向遍历
利用set容器定义的方向迭代器reverse_iterator和const_reverse_iterator，可实现红黑树的逆中序遍历，从而将元素从大到小遍历出来。
reverse_iterator rbegin();
reverse_iterator rend();

元素的搜索
set容器提供了一个应用红黑树进行搜索的函数find，返回的迭代器值为搜索到的元素位置，如果元素不存在，则返回end结束元素位置
iterator find(const key_type& k) const