set源代碼



G++ 2.91.57，cygnus\cygwin-b20\include\g++\stl_set.h

完整清單

/*

 *

 * Copyright (c) 1994

 * Hewlett-Packard Company

 * Permission to use, copy, modify, distributeand sell this software

 * and its documentation for any purpose ishereby granted without fee,

 * provided that the above copyright noticeappear in all copies and

 * that both that copyright notice and thispermission notice appear

 * in supporting documentation. 

Hewlett-Packard Company makes no

 * representations about the suitability ofthis software for any

 * purpose. It

is provided "as is" without express or implied warranty.

 * Copyright (c) 1996,1997

 * Silicon Graphics Computer Systems, Inc.

Silicon Graphics makes no

 */

/* NOTE: This isan internal header file, included by other STL headers.

 *  

Youshould 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 woff1174

#endif

#ifndef__STL_LIMITED_DEFAULT_TEMPLATES

template <classKey,

class Compare

= less<Key>, class

Alloc = alloc>

#else

template <classKey, class Compare, class Alloc = alloc>

class

set {

public:

// typedefs:

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; 

採用紅黑樹（RB-tree）來表現

set

typedef typename rep_type::const_pointer

pointer;

const_pointer;

typedef typename rep_type::const_reference

reference;

const_reference;

typedef typename rep_type::const_iterator

iterator;

注意上一行，iterator

定義為 RB-tree

的

const_iterator，這表示

// 疊代器無法執行寫入動作。這是因為

的元素有一定次序安排，

// 不允許使用者在任意處做寫入動作。

const_iterator;

typedef typename rep_type::const_reverse_iteratorreverse_iterator;

typedef typenamerep_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) {}

#ifdef__STL_MEMBER_TEMPLATES

template <class InputIterator>

set(InputIterator first, InputIterator last)

: t(Compare()) { t.insert_unique(first, last); }

set(InputIterator first, InputIterator last, const Compare& comp)

: t(comp) { t.insert_unique(first, last); }

set(const value_type* first, const value_type* last)

set(const value_type* first, const value_type* last, const Compare&comp)

set(const_iterator first, const_iterator last)

set(const_iterator first, const_iterator last, const Compare& comp)

#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

都已提供，是以

隻要轉呼叫即可。

// accessors:

key_compare key_comp() const { return

t.key_comp(); }

以下注意，set

的value_comp()

事實上為RB-tree

的key_comp()。

value_compare value_comp() const { return

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::iteratorrep_iterator;

return t.insert_unique((rep_iterator&)position, x);

void insert(InputIterator first, InputIterator last) {

t.insert_unique(first, last);

void insert(const_iterator first, const_iterator last) {

void insert(const value_type* first, const value_type* last) {

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) {

t.erase((rep_iterator&)first, (rep_iterator&)last);

void clear() {

t.clear(); }

// set operations:

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 <classKey, class Compare, class Alloc>

inline bool

operator==(const set<Key, Compare, Alloc>& x,

const set<Key, Compare,Alloc>& y) {

return x.t == y.t;

operator<(const set<Key, Compare, Alloc>& x,

const set<Key,Compare, Alloc>& y) {

return x.t < y.t;

#ifdef__STL_FUNCTION_TMPL_PARTIAL_ORDER

inline void

swap(set<Key, Compare, Alloc>& x,

set<Key, Compare,Alloc>& y) {

x.swap(y);

#endif /*__STL_FUNCTION_TMPL_PARTIAL_ORDER */

#pragma reset woff1174

__STL_END_NAMESPACE

#endif /*__SGI_STL_INTERNAL_SET_H */

// LocalVariables:

// mode:C++

// End: