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_TEMPLATES

  template <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); }

#else

  set(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/erase

  typedef  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_TEMPLATES

  template <class InputIterator>

  void insert(InputIterator first, InputIterator last) {

    t.insert_unique(first, last);

  }

#else

  void 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_ORDER

template <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: