SET是STL中的标准容器，SET里面的元素会根据键值自动排序，它不像map那样拥有实值value和键值key的对应，set只有实值。SET的底层实现时RB-tree，当插入到RB-tree中后，其值不能再更改，因为更改就意味着可能不符合RB-tree的特性了，所以其迭代器set<T>::iterator是RB-tree的constrant iterator。由于SET底层是RB-tree，所以SET在插入等操作之后，迭代器不会失效，但删除元素的迭代器是个例外。

G++ 2.91.57，cygnus\cygwin-b20\include\g++\stl_set.h 完整列表
/*** Copyright (c) 1994* Hewlett-Packard Company** Permission to use, copy, modify, distribute and sell this software* and its documentation for any purpose is hereby granted without fee,* provided that the above copyright notice appear in all copies and* that both that copyright notice and this permission notice appear* in supporting documentation.  Hewlett-Packard Company makes no* representations about the suitability of this software for any* purpose.  It is provided "as is" without express or implied warranty.*** Copyright (c) 1996,1997* Silicon Graphics Computer Systems, Inc.** Permission to use, copy, modify, distribute and sell this software* and its documentation for any purpose is hereby granted without fee,* provided that the above copyright notice appear in all copies and* that both that copyright notice and this permission notice appear* in supporting documentation.  Silicon Graphics makes no* representations about the suitability of this software for any* purpose.  It is provided "as is" without express or implied warranty.*//* NOTE: This is an internal header file, included by other STL headers.*   You should not attempt to use it directly.*/#ifndef __SGI_STL_INTERNAL_SET_H
#define __SGI_STL_INTERNAL_SET_H__STL_BEGIN_NAMESPACE#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma set woff 1174
#endif
//less<Key>说明默认使用递增排序
#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class Key, class Compare = less<Key>, class Alloc = alloc>
#else
template <class Key, class Compare, class Alloc = alloc>
#endif
class set {
public:// typedefs://key_type和 value_type类型都是实值typedef Key key_type;typedef Key value_type;// 注意，以下 key_compare 和 value_compare 使用相同的比较函数typedef Compare key_compare;typedef Compare value_compare;
private:/* 注意，identity 定义于 <stl_function.h>，参考第7章，其定义为：template <class T>struct identity : public unary_function<T, T> {const T& operator()(const T& x) const { return x; }};*/// 以下，rb_tree<Key, Value, KeyOfValue, Compare, Alloc>typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type;rep_type t;  // 底层采用红黑树
public:typedef typename rep_type::const_pointer pointer;typedef typename rep_type::const_pointer const_pointer;typedef typename rep_type::const_reference reference;typedef typename rep_type::const_reference const_reference;//用的是RB-tree的 const_iterator。不允许修改其值，也不允许使用者在任意处插入元素typedef typename rep_type::const_iterator iterator;typedef typename rep_type::const_iterator const_iterator;typedef typename rep_type::const_reverse_iterator reverse_iterator;typedef typename rep_type::const_reverse_iterator const_reverse_iterator;typedef typename rep_type::size_type size_type;typedef typename rep_type::difference_type difference_type;// allocation/deallocation// 注意， set 一定使用 insert_unique() 而不使用 insert_equal()。// multiset 才使用 insert_equal()。set() : t(Compare()) {}explicit set(const Compare& comp) : t(comp) {}
//初始化SET
#ifdef __STL_MEMBER_TEMPLATEStemplate <class InputIterator>set(InputIterator first, InputIterator last): t(Compare()) { t.insert_unique(first, last); }template <class InputIterator>set(InputIterator first, InputIterator last, const Compare& comp): t(comp) { t.insert_unique(first, last); }
#elseset(const value_type* first, const value_type* last) : t(Compare()) { t.insert_unique(first, last); }set(const value_type* first, const value_type* last, const Compare& comp): t(comp) { t.insert_unique(first, last); }set(const_iterator first, const_iterator last): t(Compare()) { t.insert_unique(first, last); }set(const_iterator first, const_iterator last, const Compare& comp): t(comp) { t.insert_unique(first, last); }
#endif /* __STL_MEMBER_TEMPLATES */set(const set<Key, Compare, Alloc>& x) : t(x.t) {}set<Key, Compare, Alloc>& operator=(const set<Key, Compare, Alloc>& x) { t = x.t; return *this;}//一下所有的SET操作，RB-tree都已经提供，SET只是调用而已// accessors:key_compare key_comp() const { return t.key_comp(); }// 以下注意，set 的value_comp() 实际上就是RB-tree 的key_comp()。value_compare value_comp() const { return t.key_comp(); }iterator begin() const { return t.begin(); }iterator end() const { return t.end(); }reverse_iterator rbegin() const { return t.rbegin(); } reverse_iterator rend() const { return t.rend(); }bool empty() const { return t.empty(); }size_type size() const { return t.size(); }size_type max_size() const { return t.max_size(); }void swap(set<Key, Compare, Alloc>& x) { t.swap(x.t); }// insert/erasetypedef  pair<iterator, bool> pair_iterator_bool; pair<iterator,bool> insert(const value_type& x) { pair<typename rep_type::iterator, bool> p = t.insert_unique(x); return pair<iterator, bool>(p.first, p.second);}iterator insert(iterator position, const value_type& x) {typedef typename rep_type::iterator rep_iterator;return t.insert_unique((rep_iterator&)position, x);}
#ifdef __STL_MEMBER_TEMPLATEStemplate <class InputIterator>void insert(InputIterator first, InputIterator last) {t.insert_unique(first, last);}
#elsevoid insert(const_iterator first, const_iterator last) {t.insert_unique(first, last);}void insert(const value_type* first, const value_type* last) {t.insert_unique(first, last);}
#endif /* __STL_MEMBER_TEMPLATES */void erase(iterator position) { typedef typename rep_type::iterator rep_iterator;t.erase((rep_iterator&)position); }size_type erase(const key_type& x) { return t.erase(x); }void erase(iterator first, iterator last) { typedef typename rep_type::iterator rep_iterator;t.erase((rep_iterator&)first, (rep_iterator&)last); }void clear() { t.clear(); }// set operations://使用的是RB-tree的搜索函数，而不是STL的find，STL的find的只是//循序搜索，效率不如关联容器自己定义的效率高iterator find(const key_type& x) const { return t.find(x); }size_type count(const key_type& x) const { return t.count(x); }iterator lower_bound(const key_type& x) const {return t.lower_bound(x);}iterator upper_bound(const key_type& x) const {return t.upper_bound(x); }pair<iterator,iterator> equal_range(const key_type& x) const {return t.equal_range(x);}friend bool operator== __STL_NULL_TMPL_ARGS (const set&, const set&);friend bool operator< __STL_NULL_TMPL_ARGS (const set&, const set&);
};template <class Key, class Compare, class Alloc>
inline bool operator==(const set<Key, Compare, Alloc>& x, const set<Key, Compare, Alloc>& y) {return x.t == y.t;
}template <class Key, class Compare, class Alloc>
inline bool operator<(const set<Key, Compare, Alloc>& x, const set<Key, Compare, Alloc>& y) {return x.t < y.t;
}#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDERtemplate <class Key, class Compare, class Alloc>
inline void swap(set<Key, Compare, Alloc>& x, set<Key, Compare, Alloc>& y) {x.swap(y);
}#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1174
#endif__STL_END_NAMESPACE#endif /* __SGI_STL_INTERNAL_SET_H */// Local Variables:
// mode:C++
// End: