C++ young 程序库——y_hash_function.hpp、y_hash_table_base.hpp 和 y_hash_table.hpp

文件位置：young/hash/y_hash_function.hpp

这个文件的内容是照抄SGI STL的。

The young Library

Permission to use, copy, modify, distribute and sell this software 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.

The author make no representations about the suitability of this software

for any purpose. It is provided "as is" without express or implied warranty.

//-----------------------------------------------------------------------------

#ifndef __MACRO_CPLUSPLUS_YOUNG_LIBRARY_HASH_FUNCTION_HEADER_FILE__

#define __MACRO_CPLUSPLUS_YOUNG_LIBRARY_HASH_FUNCTION_HEADER_FILE__

//-----------------------------------------------------------------------------

#include "../y_define.hpp"

//-----------------------------------------------------------------------------

__MACRO_CPLUSPLUS_YOUNG_LIBRARY_BEGIN_NAMESPACE__

//-----------------------------------------------------------------------------

template< typename Key >

struct hash {};

inline def_size_t hash_string( const char* s )

{

unsigned long h = 0;

for ( ; *s; ++s )

h = 5 * h + *s;

return def_size_t(h);

}

template<>

struct hash<char*>

{

def_size_t operator()( const char* s ) const

{ return hash_string(s); }

};

template<>

struct hash<const char*>

{

def_size_t operator()( const char* s ) const

{ return hash_string(s); }

};

template<>

struct hash<char>

{

def_size_t operator()( char x ) const

{ return x; }

};

template<>

struct hash<unsigned char>

{

def_size_t operator()( unsigned char x ) const

{ return x; }

};

template<>

struct hash<signed char>

{

def_size_t operator()( unsigned char x ) const

{ return x; }

};

template<>

struct hash<short>

{

def_size_t operator()(short x) const

{ return x; }

};

template<>

struct hash<unsigned short>

{

def_size_t operator()( unsigned short x ) const

{ return x; }

};

template<>

struct hash<int>

{

def_size_t operator()( int x ) const

{ return x; }

};

template<>

struct hash<unsigned int>

{

def_size_t operator()( unsigned int x ) const

{ return x; }

};

template<>

struct hash<long>

{

def_size_t operator()( long x ) const

{ return x; }

};

template<>

struct hash<unsigned long>

{

def_size_t operator()( unsigned long x ) const

{ return x; }

};

template<>

struct hash<long long>

{

def_size_t operator()( long long x ) const

{ return x; }

};

template<>

struct hash<unsigned long long>

{

def_size_t operator()( unsigned long long x ) const

{ return x; }

};

//-----------------------------------------------------------------------------

__MACRO_CPLUSPLUS_YOUNG_LIBRARY_END_NAMESPACE__

#endif

//-----------------------------------------------------------------------------

文件位置：young/hash/y_hash_table_base.hpp

The young Library

Permission to use, copy, modify, distribute and sell this software 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.

The author make no representations about the suitability of this software

for any purpose. It is provided "as is" without express or implied warranty.

//-----------------------------------------------------------------------------

#ifndef __MACRO_CPLUSPLUS_YOUNG_LIBRARY_HASH_TABLE_BASE_HEADER_FILE__

#define __MACRO_CPLUSPLUS_YOUNG_LIBRARY_HASH_TABLE_BASE_HEADER_FILE__

//-----------------------------------------------------------------------------

#include "../algorithm/y_algorithm_lower_bound.hpp"

//-----------------------------------------------------------------------------

__MACRO_CPLUSPLUS_YOUNG_LIBRARY_BEGIN_NAMESPACE__

//-----------------------------------------------------------------------------

static const int hash_table_num_primes = 28;

static const unsigned long hash_table_prime_list[ hash_table_num_primes ] =

{

53, 97, 193, 389, 769,

1543, 3079, 6151, 12289, 24593,

49157, 98317, 196613, 393241, 786433,

1572869, 3145739, 6291469, 12582917, 25165843,

50331653, 100663319, 201326611, 402653189, 805306457,

1610612741, 3221225473ul, 4294967291ul

};

inline unsigned long hash_table_next_prime( unsigned long n )

{

const unsigned long* first = hash_table_prime_list;

const unsigned long* last = hash_table_prime_list + hash_table_num_primes;

const unsigned long* pos = lower_bound( first, last, n );

return ( pos == last ? *(last - 1) : *pos );

}

//-----------------------------------------------------------------------------

__MACRO_CPLUSPLUS_YOUNG_LIBRARY_END_NAMESPACE__

#endif

//-----------------------------------------------------------------------------

文件位置：young/hash/y_hash_table.hpp

The young Library

Permission to use, copy, modify, distribute and sell this software 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.

The author make no representations about the suitability of this software

for any purpose. It is provided "as is" without express or implied warranty.

//-----------------------------------------------------------------------------

#ifndef __MACRO_CPLUSPLUS_YOUNG_LIBRARY_HASH_TABLE_HEADER_FILE__

#define __MACRO_CPLUSPLUS_YOUNG_LIBRARY_HASH_TABLE_HEADER_FILE__

//-----------------------------------------------------------------------------

#include "y_hash_table_base.hpp"

#include "../y_pair.hpp"

#include "../y_vector.hpp"

//-----------------------------------------------------------------------------

__MACRO_CPLUSPLUS_YOUNG_LIBRARY_BEGIN_NAMESPACE__

//-----------------------------------------------------------------------------

template< typename Value >

struct hash_table_node

{

hash_table_node* next; //当节点为链表的尾节点时，该值为空

Value data;

};

//-----------------------------------------------------------------------------

template< typename T, typename Ref, typename Ptr, typename Key,

typename HashFun, typename ExtractKey, typename EqualKey,

typename Alloc >

class hash_table_iterator;

template< typename Key, typename Value, typename HashFun,

typename ExtractKey, typename EqualKey, typename Allocator >

class hash_table;

template< typename T, typename Ref, typename Ptr, typename Key,

typename HashFun, typename ExtractKey, typename EqualKey,

typename Alloc >

class hash_table_iterator

{

public:

typedef forward_iterator_tag iterator_category;

typedef def_size_t size_type;

typedef def_ptrdiff_t difference_type;

typedef T value_type;

typedef Ref reference;

typedef Ptr pointer;

typedef hash_table_iterator<T, Ref, Ptr, Key, HashFun, ExtractKey,

EqualKey, Alloc> self;

typedef hash_table_iterator<T, T&, T*, Key, HashFun, ExtractKey,

EqualKey, Alloc> iterator;

typedef hash_table_iterator<T, const T&, const T*, Key, HashFun,

ExtractKey, EqualKey, Alloc> const_iterator;

private:

typedef hash_table<Key, T, HashFun, ExtractKey, EqualKey, Alloc>

hashtable;

typedef hash_table_node<value_type> node;

typedef typename primal_type<Ref>::contrary_const_ref Ref_t;

typedef typename primal_type<Ptr>::contrary_const_ptr Ptr_t;

friend class hashtable;

friend class hash_table_iterator<T, Ref_t, Ptr_t, Key, HashFun,

ExtractKey, EqualKey, Alloc>;

friend iterator const_iter_cast <> ( const const_iterator& );

node* current;

hashtable* table;

public:

hash_table_iterator() : current(NULL_POINTER), table(NULL_POINTER) {}

hash_table_iterator( node* n_ptr, hashtable* ht_ptr )

: current(n_ptr), table(ht_ptr) {}

hash_table_iterator( const iterator& x )

: current(x.current), table(x.table) {}

self& operator=( def_nullptr_t n )

{

if( n == NULL_POINTER )

{

current = NULL_POINTER;

table = NULL_POINTER;

}

return *this;

}

bool operator!() const { return ( !current && !table ); }

bool operator==( const self& rhs ) const { return current == rhs.current; }

bool operator!=( const self& rhs ) const { return current != rhs.current; }

reference operator*() const { return current->data; }

pointer operator->() const { return &( operator*() ); }

self& operator++();

self operator++(int)

{

self old = *this;

++(*this);

return old;

}

}; //end iterator

template< typename T, typename Ref, typename Ptr, typename Key,

typename HashFun, typename ExtractKey, typename EqualKey,

typename Alloc >

hash_table_iterator<T, Ref, Ptr, Key, HashFun, ExtractKey, EqualKey, Alloc>&

hash_table_iterator<T, Ref, Ptr, Key, HashFun, ExtractKey, EqualKey, Alloc>::

operator++()

{

const node* old = current;

current = current->next;

if( !current )

{

size_type bucket = table->bucket_pos_value( old->data );

size_type bkt_size = table->m_buckets.size();

while( !current && ++bucket < bkt_size )

current = table->m_buckets[bucket];

}

return *this;

}

template< typename T, typename Key, typename HashFun, typename ExtractKey,

typename EqualKey, typename Alloc >

inline

hash_table_iterator<T, T&, T*, Key, HashFun, ExtractKey, EqualKey, Alloc>

const_iter_cast( const hash_table_iterator<T, const T&, const T*, Key,

HashFun, ExtractKey, EqualKey, Alloc>& citer )

{

return hash_table_iterator<T, T&, T*, Key, HashFun, ExtractKey,

EqualKey, Alloc>( citer.current, citer.table );

}

//-----------------------------------------------------------------------------

template< typename Key, typename Value,

typename HashFun, typename ExtractKey, typename EqualKey,

typename Allocator = allocator< hash_table_node<Value> > >

class hash_table

{

public:

typedef hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>

self;

typedef Key key_type;

typedef HashFun hasher;

typedef ExtractKey extract_key;

typedef EqualKey key_equal;

typedef Allocator allocator_type;

typedef Value value_type;

typedef value_type& reference;

typedef const value_type& const_reference;

typedef value_type* pointer;

typedef const value_type* const_pointer;

typedef def_size_t size_type;

typedef def_ptrdiff_t difference_type;

typedef hash_table_iterator

<Value, Value&, Value*, Key, HashFun, ExtractKey, EqualKey,

Allocator> iterator;

typedef hash_table_iterator

<Value, const Value&, const Value*, Key, HashFun, ExtractKey,

EqualKey, Allocator> const_iterator;

typedef pair<iterator, iterator> pair_iterator;

typedef pair<const_iterator, const_iterator> pair_const_iterator;

typedef pair<iterator, bool> pair_iterator_bool;

friend class hash_table_iterator<Value, Value&, Value*, Key, HashFun,

ExtractKey, EqualKey, Allocator>;

friend class hash_table_iterator<Value, const Value&, const Value*, Key,

HashFun, ExtractKey, EqualKey, Allocator>;

protected:

typedef hash_table_node<value_type> node;

typedef typename Allocator::rebind<node*>::other ptr_allocator;

// typedef allocator<node*> ptr_allocator;

hasher m_hash;

key_equal m_eq_key;

extract_key m_get_key;

size_type m_node_count;

double m_hash_factor;

allocator_type m_alloc;

vector<node*, ptr_allocator> m_buckets;

public:

explicit hash_table( size_type size,

const hasher& hf = hasher(),

const key_equal& eq = key_equal(),

const extract_key& et = extract_key() )

: m_hash(hf), m_eq_key(eq), m_get_key(et), m_node_count(0),

m_hash_factor(0.75)

{

init_buckets( size );

}

hash_table( const self& rhs )

: m_hash(rhs.m_hash), m_eq_key(rhs.m_eq_key), m_get_key(rhs.m_get_key),

m_node_count(0), m_hash_factor(0.75)

{

copy( rhs );

}

self& operator=( const self& rhs )

{

if( this != &rhs )

{

clear();

m_hash = rhs.m_hash;

m_eq_key = rhs.m_eq_key;

m_get_key = rhs.m_get_key;

copy( rhs );

}

return *this;

}

~hash_table() { clear(); }

hasher hash_fun() const { return m_hash; }

key_equal key_eq() const { return m_eq_key; }

double get_hash_factor() const { return m_hash_factor; }

void set_hash_factor( double factor )

{

if( factor > 0 )

m_hash_factor = factor;

}

void clear();

void resize( size_type new_elements );

size_type count( const key_type& k ) const;

size_type size() const { return m_node_count; }

size_type max_size() const { return size_t_max; }

bool empty() const { return ( m_node_count == 0 ); }

size_type bucket_count() const { return m_buckets.size(); }

size_type max_bucket_count() const

{

return hash_table_prime_list[ hash_table_num_primes - 1 ];

}

size_type elements_in_bucket( size_type bucket ) const

{

size_type result = 0;

node* current = m_buckets[bucket];

while( current )

{

result += 1;

current = current->next;

}

return result;

}

iterator begin()

{ return iterator( begin_node(), this ); }

iterator end()

{ return iterator( (node*)NULL_POINTER, this ); }

const_iterator begin() const

{ return const_iterator( begin_node(), const_cast<self*>(this) ); }

const_iterator end() const

{ return const_iterator( (node*)NULL_POINTER, const_cast<self*>(this) ); }

void modify_key_equal( const key_type& k, const key_type& new_key );

void modify_key_equal( iterator position, const key_type& new_key )

{

if( position != end() )

modify_key_aux( position, new_key );

}

iterator modify_key_unique( const key_type& k, const key_type& new_key )

{

iterator result = find( k );

if( result != end() && find(new_key) == end() )

modify_key_aux( result, new_key );

return result;

}

bool modify_key_unique( iterator position, const key_type& new_key )

{

if( position == end() || find(new_key) != end() )

return false;

modify_key_aux( position, new_key );

return true;

}

void swap( self& rhs )

{

if( this != &rhs )

{

data_swap( m_hash, rhs.m_hash );

data_swap( m_eq_key, rhs.m_eq_key );

data_swap( m_get_key, rhs.m_get_key );

data_swap( m_node_count, rhs.m_node_count );

data_swap( m_hash_factor, rhs.m_hash_factor );

data_swap( m_alloc, rhs.m_alloc );

m_buckets.swap( rhs.m_buckets );

}

iterator find( const key_type& k )

{ return iterator( find_node(k), this ); }

const_iterator find( const key_type& k ) const

{ return const_iterator( find_node(k), const_cast<self*>(this) ); }

pair_iterator equal_range( const key_type& k )

{

pair_node_ptr pptr = equal_range_node( k );

return pair_iterator( iterator(pptr->first, this),

iterator(pptr->second, this) );

}

pair_const_iterator equal_range( const key_type& k ) const

{

pair_node_ptr pptr = equal_range_node( k );

return pair_const_iterator( const_iterator(pptr->first,

const_cast<self*>(this)),

const_iterator(pptr->second,

const_cast<self*>(this)) );

}

void erase( iterator first, iterator last );

size_type erase( const key_type& k );

void erase( iterator position )

{

erase_adjust( position.current );

destroy_node( position.current );

--m_node_count;

}

pair_iterator_bool insert_unique( const value_type& v )

{

resize( m_node_count + 1 );

return insert_unique_noresize( v );

}

template< typename InputIterator >

void insert_unique( InputIterator first, InputIterator last,

size_type extra_size = 0 )

{

if( first != last )

range_insert_unique( first, last,

range_length(first, last, extra_size) );

}

iterator insert_equal( const value_type& v )

{

resize( m_node_count + 1 );

return insert_equal_noresize( v );

}

template< typename InputIterator >

void insert_equal( InputIterator first, InputIterator last,

size_type extra_size = 0 )

{

if( first != last )

range_insert_equal( first, last,

range_length(first, last, extra_size) );

}

protected:

//初始化辅助函数

void copy( const self& rhs );

node* create_node( const_reference x )

{

node* ptr = m_alloc.allocate( 1 );

try

{

construct( &(ptr->data), x );

}

catch(...)

{

m_alloc.deallocate( ptr, 1 );

throw;

}

ptr->next = NULL_POINTER;

return ptr;

}

void destroy_node( node* ptr )

{

destroy( &(ptr->data) );

m_alloc.deallocate( ptr, 1 );

}

void init_buckets( size_type n )

{

const size_type bkt_size = hash_table_next_prime( n );

m_buckets.assign( bkt_size, (node*)NULL_POINTER );

m_node_count = 0;

}

//获得节点在散列表中位置的辅助函数

size_type bucket_pos_key( const key_type& k, size_type n ) const

{ return ( m_hash(k) % n ); }

size_type bucket_pos_key( const key_type& k ) const

{ return bucket_pos_key( k, m_buckets.size() ); }

size_type bucket_pos_value( const value_type& v, size_type n ) const

{ return bucket_pos_key( m_get_key(v), n ); }

size_type bucket_pos_value( const value_type& v ) const

{ return bucket_pos_key( m_get_key(v) ); }

//insert、erase辅助函数

pair_iterator_bool insert_unique_noresize( const value_type& v );

iterator insert_equal_noresize( const value_type& v );

template< typename InputIterator >

void range_insert_unique( InputIterator first, InputIterator last,

size_type extra_size )

{

resize( m_node_count + extra_size );

for( ; first != last; ++first )

insert_unique_noresize( *first );

}

template< typename InputIterator >

void range_insert_equal( InputIterator first, InputIterator last,

size_type extra_size )

{

resize( m_node_count + extra_size );

for( ; first != last; ++first )

insert_equal_noresize( *first );

}

void erase_bucket( const size_type bkt_num, node* first, node* last );

void erase_bucket( const size_type bkt_num, node* last );

//负责查找的辅助函数

typedef pair<node*, node*> pair_node_ptr;

node* find_node( const key_type& k ) const;

pair_node_ptr equal_range_node( const key_type& k ) const;

node* begin_node() const;

void erase_adjust( node* position );

void modify_key_aux( iterator position, const key_type& new_key );

}; //end class

//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,

typename EqualKey, typename Allocator >

void hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::

copy( const self& rhs )

{

m_buckets.assign( rhs.m_buckets.size(), (node*)NULL_POINTER );

try

{

size_type bkt_size = rhs.m_buckets.size();

for( size_type i = 0; i < bkt_size; ++i )

{

node* source = rhs.m_buckets[i];

if( source )

{

m_buckets[i] = create_node( source->data );

node* current = m_buckets[i];

source = source->next;

while( source )

{

current->next = create_node( source->data );

source = source->next;

current = current->next;

} //end while

} //end if

} //end for

} //end try

catch(...)

{

clear();

throw;

}

m_node_count = rhs.m_node_count;

}

//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,

typename EqualKey, typename Allocator >

typename hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::node*

hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::

begin_node() const

{

size_type bkt_size = m_buckets.size();

for( size_type i = 0; i < bkt_size; ++i )

{

if( m_buckets[i] )

return m_buckets[i];

}

return ( (node*)NULL_POINTER );

}

//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,

typename EqualKey, typename Allocator >

void hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::clear()

{

size_type bkt_size = m_buckets.size();

for( size_type i = 0; i < bkt_size; ++i )

{

node* current = m_buckets[i];

node* temp;

while( current )

{

temp = current;

current = current->next;

destroy_node( temp );

}

m_buckets[i] = NULL_POINTER;

}

m_node_count = 0;

}

//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,

typename EqualKey, typename Allocator >

void hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::

resize( size_type new_elements )

{

const size_type old_bkt_size = m_buckets.size();

//当新节点个数与buckets个数的比值大于散列系数时，就重构表

if( (new_elements / old_bkt_size) > m_hash_factor )

{

const size_type new_bkt_size = hash_table_next_prime( new_elements );

if( new_bkt_size > old_bkt_size ) //当质数为最大值时会相等

{

vector<node*> new_buckets( new_bkt_size, (node*)NULL_POINTER );

try

{

for( size_type i = 0; i < old_bkt_size; ++i )

{

node* current = m_buckets[i];

while( current )

{

//寻找在新表中的新位置

const size_type new_pos =

bucket_pos_value( current->data, new_bkt_size );

m_buckets[i] = current->next;

current->next = new_buckets[new_pos];

new_buckets[new_pos] = current;

current = m_buckets[i];

} //end while

} //end for

m_buckets.swap( new_buckets );

} //end try

catch(...)

{

for( size_type j = 0; j < new_buckets.size(); ++j )

{

node* next;

while( new_buckets[j] )

{

next = new_buckets[j]->next;

destroy_node( new_buckets[j] );

new_buckets[j] = next;

}

throw;

} //end for

} //end catch

} //end if

}

//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,

typename EqualKey, typename Allocator >

typename hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::

pair_iterator_bool

hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::

insert_unique_noresize( const value_type& v )

{

const size_type n = bucket_pos_value( v ); //找到新节点应插入的位置

node* first = m_buckets[n];

node* current = first;

while( current )

{

if( m_eq_key( m_get_key(current->data), m_get_key(v) ) ) //有等价值则不插入

return pair_iterator_bool( iterator(current, this), false );

current = current->next;

}

node* new_node = create_node( v );

new_node->next = first;

m_buckets[n] = new_node;

++m_node_count;

return pair_iterator_bool( iterator(new_node, this), true );

}

//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,

typename EqualKey, typename Allocator >

typename

hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::iterator

hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::

insert_equal_noresize( const value_type& v )

{

const size_type n = bucket_pos_value( v );

node* first = m_buckets[n];

node* current = first;

while( current )

{

if( m_eq_key( m_get_key(current->data), m_get_key(v) ) )

{

node* new_node = create_node( v );

new_node->next = current->next;

current->next = new_node;

++m_node_count;

return iterator( new_node, this );

}

current = current->next;

}

node* new_node = create_node( v );

new_node->next = first;

m_buckets[n] = new_node;

++m_node_count;

return iterator( new_node, this );

}

//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,

typename EqualKey, typename Allocator >

void hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::

erase_adjust( node* erase_node )

{

if( erase_node )

{

const size_type n = bucket_pos_value( erase_node->data );

node* current = m_buckets[n]; //节点所在的bucket

if( erase_node == current ) //删除节点是该bucket的第一个节点

m_buckets[n] = current->next;

else

{

node* next = current->next;

while( next )

{

if( next == erase_node ) //找到要删除的节点

{

current->next = next->next;

return;

}

else

{

current = next;

next = current->next;

}

} //end while

} //end else

}

//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,

typename EqualKey, typename Allocator >

void hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::

erase( iterator first, iterator last )

{

if( first != last )

{

size_type first_bkt = first.current ? bucket_pos_value( first.current->data )

: m_buckets.size();

size_type last_bkt = last.current ? bucket_pos_value( last.current->data )

: m_buckets.size();

if( first_bkt == last_bkt )

erase_bucket( first_bkt, first.current, last.current );

else

{

for( size_type i = first_bkt; i < last_bkt; ++i )

erase_bucket( i, 0 );

if( last_bkt != m_buckets.size() )

erase_bucket( last_bkt, last.current );

}

//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,

typename EqualKey, typename Allocator >

typename

hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::size_type

hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::

erase( const key_type& k )

{

size_type erase_count = 0;

const size_type n = bucket_pos_key( k );

node* first = m_buckets[n];

if( first )

{

node* current = first;

node* next = current->next;

while( next ) //先删除first后面的等价节点

{

if( m_eq_key( m_get_key(next->data), k ) )

{

current->next = next->next;

destroy_node( next );

next = current->next;

--m_node_count;

++erase_count;

}

else

{

current = next;

next = current->next;

}

if( m_eq_key( m_get_key(first->data), k ) ) //确定是否删除第一个节点

{

m_buckets[n] = first->next;

destroy_node( first );

--m_node_count;

++erase_count;

}

return erase_count;

}

//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,

typename EqualKey, typename Allocator >

void hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::

erase_bucket( const size_type bkt_num, node* first, node* last )

{

node* current = m_buckets[bkt_num];

if( current == first )

erase_bucket( bkt_num, last );

else

{

node* next = current->next;

while( next != first ) //找到first在链表中的位置

{

current = next;

next = current->next;

} //current将指向first之前的那个节点

while( next != last )

{

current->next = next->next;

destroy_node( next );

next = current->next;

--m_node_count;

}

//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,

typename EqualKey, typename Allocator >

void hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::

erase_bucket( const size_type bkt_num, node* last )

{

node* current = m_buckets[bkt_num];

node* next;

while( current != last )

{

next = current->next;

destroy_node( current );

current = next;

--m_node_count;

}

m_buckets[bkt_num] = current;

}

//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,

typename EqualKey, typename Allocator >

typename

hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::size_type

hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::

count( const key_type& k ) const

{

const size_type n = bucket_pos_key( k );

size_type result = 0;

for( node* current = m_buckets[n]; current; current = current->next )

{

if( m_eq_key( m_get_key(current->data), k ) )

++result;

}

return result;

}

//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,

typename EqualKey, typename Allocator >

typename hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::node*

hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::

find_node( const key_type& k ) const

{

const size_type n = bucket_pos_key( k );

node* current = m_buckets[n];

while( current )

{

if( m_eq_key( m_get_key(current->data), k ) )

break;

else

current = current->next;

}

return current;

}

//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,

typename EqualKey, typename Allocator >

typename

hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::pair_node_ptr

hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::

equal_range_node( const key_type& k ) const

{

const size_type i = bucket_pos_key( k );

for( node* first = m_buckets[i]; first; first = first->next )

{

if( m_eq_key( m_get_key(first->data), k ) )

{

for( node* last = first->next; last; last = last->next )

{

if( !m_eq_key( m_get_key(first->data), k ) )

return pair_node_ptr( first, last );

}

for( size_type j = i + 1; j < m_buckets.size(); ++j )

{

if( m_buckets[j] )

return pair_node_ptr( first, m_buckets[j] );

}

} //end if

} //end for

return pair_node_ptr( (node*)NULL_POINTER, (node*)NULL_POINTER );

}

//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,

typename EqualKey, typename Allocator >

void hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::

modify_key_aux( iterator position, const key_type& new_key )

{

node* modify_node = position.current;

erase_adjust( position.current );

try

{

m_get_key( modify_node->data ) = new_key;

}

catch(...)

{

destroy_node( modify_node );

--m_node_count;

throw;

}

//为节点寻找新插入的位置

const size_type n = bucket_pos_key( new_key );

node* first = m_buckets[n];

node* current = first;

while( current )

{

if( m_eq_key( m_get_key(current->data),

m_get_key(position.current->data) ) )

{

modify_node->next = current->next;

current->next = modify_node;

return;

}

current = current->next;

}

modify_node->next = first;

m_buckets[n] = modify_node;

}

//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,

typename EqualKey, typename Allocator >

void hash_table<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>::

modify_key_equal( const key_type& k, const key_type& new_key )

{

//寻找新的插入位置

const size_type n = bucket_pos_key( new_key );

node* new_first = m_buckets[n];

node* new_prev_first = NULL_POINTER;

while( new_first ) //寻找新链表中是否有键值相等的点

{

if( m_eq_key( m_get_key(new_first->data), new_key ) )

break;

new_prev_first = new_first;

new_first = new_first->next;

}

//修改所有键值相等的节点并插入新的位置

const size_type i = bucket_pos_key( k );

node* old_first = m_buckets[i];

node* old_prev_first = old_first;

node* adjust_node;

while( old_first )

{

if( m_eq_key( m_get_key(old_first->data), k ) )

{

//已找到键值相等的节点

while( old_first )

{

//调整原节点所在的链表

adjust_node = old_first;

old_first = old_first->next;

old_prev_first->next = old_first;

if( m_buckets[i] == adjust_node )

m_buckets[i] = old_first;

//修改新找到节点的键值

try

{

m_get_key( adjust_node->data ) = new_key;

}

catch(...)

{

destroy_node( adjust_node );

--m_node_count;

throw;

}

if( new_prev_first ) //新插入的bucket中有其他节点

{

adjust_node->next = new_first;

new_prev_first->next = adjust_node;

}

else //新插入的bucket没有其他节点或者第一个节点即为键值相等的节点

{

m_buckets[n] = adjust_node;

adjust_node->next = new_first;

}

new_first = adjust_node;

//判断下一个节点是否为空或者键值是否相等

if( !old_first || !m_eq_key( m_get_key(old_first->data), k ) )

return;

} //end while

} //end if

//未找到键值相等的节点则继续往下查找

old_prev_first = old_first;

old_first = old_first->next;

} //end while

}

//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename HashFun, typename ExtractKey,

typename EqualKey, typename Allocator >

inline void swap( hash_table

<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>& lhs,

hash_table

<Key, Value, HashFun, ExtractKey, EqualKey, Allocator>& rhs )

{

lhs.swap( rhs );

}

//-----------------------------------------------------------------------------

__MACRO_CPLUSPLUS_YOUNG_LIBRARY_END_NAMESPACE__

#endif

//-----------------------------------------------------------------------------