Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

hashtable Class Template Reference

#include <stl_hashtable.h>

Inheritance diagram for hashtable:

Inheritance graph
[legend]
Collaboration diagram for hashtable:

Collaboration graph
[legend]
List of all members.

Public Types

typedef Key key_type
typedef Value value_type
typedef HashFcn hasher
typedef EqualKey key_equal
typedef size_t size_type
typedef ptrdiff_t difference_type
typedef value_type * pointer
typedef const value_type * const_pointer
typedef value_type & reference
typedef const value_type & const_reference
typedef __hashtable_iterator<
Value, Key, HashFcn, ExtractKey,
EqualKey, Alloc > 		iterator
typedef __hashtable_const_iterator<
Value, Key, HashFcn, ExtractKey,
EqualKey, Alloc > 		const_iterator

Public Methods

hasher hash_funct () const
key_equal key_eq () const
 hashtable (size_type n, const HashFcn &hf, const EqualKey &eql, const ExtractKey &ext)
 hashtable (size_type n, const HashFcn &hf, const EqualKey &eql)
 hashtable (const hashtable &ht)
hashtable & operator= (const hashtable &ht)
 ~hashtable ()
size_type size () const
size_type max_size () const
bool empty () const
void swap (hashtable &ht)
iterator begin ()
iterator end ()
const_iterator begin () const
const_iterator end () const
size_type bucket_count () const
size_type max_bucket_count () const
size_type elems_in_bucket (size_type bucket) const
pair< iterator, bool > insert_unique (const value_type &obj)
iterator insert_equal (const value_type &obj)
pair< iterator, bool > insert_unique_noresize (const value_type &obj)
iterator insert_equal_noresize (const value_type &obj)
void insert_unique (const value_type *f, const value_type *l)
void insert_equal (const value_type *f, const value_type *l)
void insert_unique (const_iterator f, const_iterator l)
void insert_equal (const_iterator f, const_iterator l)
reference find_or_insert (const value_type &obj)
iterator find (const key_type &key)
const_iterator find (const key_type &key) const
size_type count (const key_type &key) const
pair< iterator, iterator > equal_range (const key_type &key)
pair< const_iterator, const_iterator > equal_range (const key_type &key) const
size_type erase (const key_type &key)
void erase (const iterator &it)
void erase (iterator first, iterator last)
void erase (const const_iterator &it)
void erase (const_iterator first, const_iterator last)
void resize (size_type num_elements_hint)
void clear ()

Private Types

typedef __hashtable_node<
Value > 		node
typedef simple_alloc< node,
Alloc > 		node_allocator

Private Methods

size_type next_size (size_type n) const
void initialize_buckets (size_type n)
size_type bkt_num_key (const key_type &key) const
size_type bkt_num (const value_type &obj) const
size_type bkt_num_key (const key_type &key, size_t n) const
size_type bkt_num (const value_type &obj, size_t n) const
node * new_node (const value_type &obj)
void delete_node (node *n)
void erase_bucket (const size_type n, node *first, node *last)
void erase_bucket (const size_type n, node *last)
void copy_from (const hashtable &ht)

Private Attributes

hasher hash
key_equal equals
ExtractKey get_key
vector< node *, Alloc > buckets
size_type num_elements

Friends

struct __hashtable_iterator< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >
struct __hashtable_const_iterator< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >
bool operator==__STL_NULL_TMPL_ARGS (const hashtable &, const hashtable &)

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
class hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >

Member Typedef Documentation

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
typedef __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> hashtable::const_iterator
 

Definition at line 200 of file stl_hashtable.h.

Referenced by hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::begin, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::end, equal_range, and hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::find.

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
typedef const value_type* hashtable::const_pointer
 

Definition at line 175 of file stl_hashtable.h.

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
typedef const value_type& hashtable::const_reference
 

Definition at line 177 of file stl_hashtable.h.

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
typedef ptrdiff_t hashtable::difference_type
 

Definition at line 173 of file stl_hashtable.h.

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
typedef HashFcn hashtable::hasher
 

Definition at line 169 of file stl_hashtable.h.

Referenced by hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::hash_funct.

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> hashtable::iterator
 

Definition at line 196 of file stl_hashtable.h.

Referenced by hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::begin, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::end, equal_range, erase, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::find, insert_equal_noresize, and insert_unique_noresize.

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
typedef EqualKey hashtable::key_equal
 

Definition at line 170 of file stl_hashtable.h.

Referenced by hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::key_eq.

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
typedef Key hashtable::key_type
 

Definition at line 167 of file stl_hashtable.h.

Referenced by hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::bkt_num_key, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::count, and hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::find.

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
typedef __hashtable_node<Value> hashtable::node [private]
 

Definition at line 187 of file stl_hashtable.h.

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
typedef simple_alloc<node, Alloc> hashtable::node_allocator [private]
 

Definition at line 188 of file stl_hashtable.h.

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
typedef value_type* hashtable::pointer
 

Definition at line 174 of file stl_hashtable.h.

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
typedef value_type& hashtable::reference
 

Definition at line 176 of file stl_hashtable.h.

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
typedef size_t hashtable::size_type
 

Definition at line 172 of file stl_hashtable.h.

Referenced by hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::begin, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::bkt_num, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::bkt_num_key, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::bucket_count, clear, copy_from, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::count, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::elems_in_bucket, equal_range, erase, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::find, find_or_insert, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::hashtable, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::initialize_buckets, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::insert_equal, insert_equal_noresize, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::insert_unique, insert_unique_noresize, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::max_bucket_count, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::max_size, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::next_size, resize, and hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::size.

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
typedef Value hashtable::value_type
 

Definition at line 168 of file stl_hashtable.h.

Referenced by hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::bkt_num, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::insert_equal, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::insert_unique, and hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::new_node.

Constructor & Destructor Documentation

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::hashtable (  size_type    n,
const HashFcn &    hf,
const EqualKey &    eql,
const ExtractKey &    ext
)  [inline]
 

Definition at line 208 of file stl_hashtable.h. 

00212     : hash(hf), equals(eql), get_key(ext), num_elements(0)
00213   {
00214     initialize_buckets(n);
00215   }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::hashtable (  size_type    n,
const HashFcn &    hf,
const EqualKey &    eql
)  [inline]
 

Definition at line 217 of file stl_hashtable.h. 

00220     : hash(hf), equals(eql), get_key(ExtractKey()), num_elements(0)
00221   {
00222     initialize_buckets(n);
00223   }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::hashtable (  const hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc > &    ht )  [inline]
 

Definition at line 225 of file stl_hashtable.h. 

00226     : hash(ht.hash), equals(ht.equals), get_key(ht.get_key), num_elements(0)
00227   {
00228     copy_from(ht);
00229   }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::~hashtable (    )  [inline]
 

Definition at line 243 of file stl_hashtable.h. 

00243 { clear(); }

Member Function Documentation

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
const_iterator hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::begin (    )  const [inline]
 

Definition at line 268 of file stl_hashtable.h. 

00269   {
00270     for (size_type n = 0; n < buckets.size(); ++n)
00271       if (buckets[n])
00272         return const_iterator(buckets[n], this);
00273     return end();
00274   }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
iterator hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::begin (    )  [inline]
 

Definition at line 258 of file stl_hashtable.h. 

00259   { 
00260     for (size_type n = 0; n < buckets.size(); ++n)
00261       if (buckets[n])
00262         return iterator(buckets[n], this);
00263     return end();
00264   }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
size_type hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::bkt_num (  const value_type &    obj,
size_t    n
)  const [inline, private]
 

Definition at line 472 of file stl_hashtable.h. 

00473   {
00474     return bkt_num_key(get_key(obj), n);
00475   }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
size_type hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::bkt_num (  const value_type &    obj )  const [inline, private]
 

Definition at line 462 of file stl_hashtable.h.

Referenced by erase, find_or_insert, insert_equal_noresize, insert_unique_noresize, __hashtable_const_iterator::operator++, __hashtable_iterator::operator++, and resize. 

00463   {
00464     return bkt_num_key(get_key(obj));
00465   }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
size_type hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::bkt_num_key (  const key_type &    key,
size_t    n
)  const [inline, private]
 

Definition at line 467 of file stl_hashtable.h. 

00468   {
00469     return hash(key) % n;
00470   }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
size_type hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::bkt_num_key (  const key_type &    key )  const [inline, private]
 

Definition at line 457 of file stl_hashtable.h.

Referenced by hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::bkt_num, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::bkt_num_key, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::count, equal_range, erase, and hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::find. 

00458   {
00459     return bkt_num_key(key, buckets.size());
00460   }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
size_type hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::bucket_count (    )  const [inline]
 

Definition at line 283 of file stl_hashtable.h. 

00283 { return buckets.size(); }

template<class V, class K, class HF, class Ex, class Eq, class A>
void hashtable< V, K, HF, Ex, Eq, A >::clear (    ) 
 

Definition at line 904 of file stl_hashtable.h.

References delete_node, __hashtable_node::next, num_elements, vector::size, and size_type.

Referenced by copy_from, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::operator=, and hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::~hashtable. 

00905 {
00906   for (size_type i = 0; i < buckets.size(); ++i) {
00907     node* cur = buckets[i];
00908     while (cur != 0) {
00909       node* next = cur->next;
00910       delete_node(cur);
00911       cur = next;
00912     }
00913     buckets[i] = 0;
00914   }
00915   num_elements = 0;
00916 }

template<class V, class K, class HF, class Ex, class Eq, class A>
void hashtable< V, K, HF, Ex, Eq, A >::copy_from (  const hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc > &    ht )  [private]
 

Definition at line 920 of file stl_hashtable.h.

References __STL_TRY, __STL_UNWIND, buckets, clear, vector::clear, vector::end, vector::insert, new_node, __hashtable_node::next, num_elements, vector::reserve, vector< node *, Alloc >::size, size_type, and __hashtable_node::val.

Referenced by hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::hashtable, and hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::operator=. 

00921 {
00922   buckets.clear();
00923   buckets.reserve(ht.buckets.size());
00924   buckets.insert(buckets.end(), ht.buckets.size(), (node*) 0);
00925   __STL_TRY {
00926     for (size_type i = 0; i < ht.buckets.size(); ++i) {
00927       if (const node* cur = ht.buckets[i]) {
00928         node* copy = new_node(cur->val);
00929         buckets[i] = copy;
00930 
00931         for (node* next = cur->next; next; cur = next, next = cur->next) {
00932           copy->next = new_node(next->val);
00933           copy = copy->next;
00934         }
00935       }
00936     }
00937     num_elements = ht.num_elements;
00938   }
00939   __STL_UNWIND(clear());
00940 }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
size_type hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::count (  const key_type &    key )  const [inline]
 

Definition at line 422 of file stl_hashtable.h. 

00423   {
00424     const size_type n = bkt_num_key(key);
00425     size_type result = 0;
00426 
00427     for (const node* cur = buckets[n]; cur; cur = cur->next)
00428       if (equals(get_key(cur->val), key))
00429         ++result;
00430     return result;
00431   }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
void hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::delete_node (  node *    n )  [inline, private]
 

Definition at line 488 of file stl_hashtable.h.

Referenced by clear, erase, erase_bucket, and resize. 

00489   {
00490     destroy(&n->val);
00491     node_allocator::deallocate(n);
00492   }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
size_type hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::elems_in_bucket (  size_type    bucket )  const [inline]
 

Definition at line 288 of file stl_hashtable.h. 

00289   {
00290     size_type result = 0;
00291     for (node* cur = buckets[bucket]; cur; cur = cur->next)
00292       result += 1;
00293     return result;
00294   }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
bool hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::empty (    )  const [inline]
 

Definition at line 247 of file stl_hashtable.h. 

00247 { return size() == 0; }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
const_iterator hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::end (    )  const [inline]
 

Definition at line 276 of file stl_hashtable.h. 

00276 { return const_iterator(0, this); }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
iterator hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::end (    )  [inline]
 

Definition at line 266 of file stl_hashtable.h.

Referenced by hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::begin, and equal_range. 

00266 { return iterator(0, this); }

template<class V, class K, class HF, class Ex, class Eq, class A>
pair< typename hashtable< V, K, HF, Ex, Eq, A >::const_iterator, typename hashtable< V, K, HF, Ex, Eq, A >::const_iterator > hashtable< V, K, HF, Ex, Eq, A >::equal_range (  const key_type &    key )  const
 

Definition at line 709 of file stl_hashtable.h.

References bkt_num_key, const_iterator, end, equals, get_key, __hashtable_node::next, size_type, and __hashtable_node::val. 

00710 {
00711   typedef pair<const_iterator, const_iterator> pii;
00712   const size_type n = bkt_num_key(key);
00713 
00714   for (const node* first = buckets[n] ; first; first = first->next) {
00715     if (equals(get_key(first->val), key)) {
00716       for (const node* cur = first->next; cur; cur = cur->next)
00717         if (!equals(get_key(cur->val), key))
00718           return pii(const_iterator(first, this),
00719                      const_iterator(cur, this));
00720       for (size_type m = n + 1; m < buckets.size(); ++m)
00721         if (buckets[m])
00722           return pii(const_iterator(first, this),
00723                      const_iterator(buckets[m], this));
00724       return pii(const_iterator(first, this), end());
00725     }
00726   }
00727   return pii(end(), end());
00728 }

template<class V, class K, class HF, class Ex, class Eq, class A>
pair< typename hashtable< V, K, HF, Ex, Eq, A >::iterator, typename hashtable< V, K, HF, Ex, Eq, A >::iterator > hashtable< V, K, HF, Ex, Eq, A >::equal_range (  const key_type &    key ) 
 

Definition at line 686 of file stl_hashtable.h.

References bkt_num_key, end, equals, get_key, iterator, __hashtable_node::next, size_type, and __hashtable_node::val. 

00687 {
00688   typedef pair<iterator, iterator> pii;
00689   const size_type n = bkt_num_key(key);
00690 
00691   for (node* first = buckets[n]; first; first = first->next) {
00692     if (equals(get_key(first->val), key)) {
00693       for (node* cur = first->next; cur; cur = cur->next)
00694         if (!equals(get_key(cur->val), key))
00695           return pii(iterator(first, this), iterator(cur, this));
00696       for (size_type m = n + 1; m < buckets.size(); ++m)
00697         if (buckets[m])
00698           return pii(iterator(first, this),
00699                      iterator(buckets[m], this));
00700       return pii(iterator(first, this), end());
00701     }
00702   }
00703   return pii(end(), end());
00704 }

template<class V, class K, class HF, class Ex, class Eq, class A>
void hashtable< V, K, HF, Ex, Eq, A >::erase (  const_iterator    first,
const_iterator    last
)  [inline]
 

Definition at line 815 of file stl_hashtable.h.

References __hashtable_const_iterator::cur, erase, __hashtable_const_iterator::ht, and iterator. 

00817 {
00818   erase(iterator(const_cast<node*>(first.cur),
00819                  const_cast<hashtable*>(first.ht)),
00820         iterator(const_cast<node*>(last.cur),
00821                  const_cast<hashtable*>(last.ht)));
00822 }

template<class V, class K, class HF, class Ex, class Eq, class A>
void hashtable< V, K, HF, Ex, Eq, A >::erase (  const const_iterator &    it )  [inline]
 

Definition at line 826 of file stl_hashtable.h.

References __hashtable_const_iterator::cur, erase, __hashtable_const_iterator::ht, and iterator. 

00827 {
00828   erase(iterator(const_cast<node*>(it.cur),
00829                  const_cast<hashtable*>(it.ht)));
00830 }

template<class V, class K, class HF, class Ex, class Eq, class A>
void hashtable< V, K, HF, Ex, Eq, A >::erase (  iterator    first,
iterator    last
) 
 

Definition at line 795 of file stl_hashtable.h.

References bkt_num, __hashtable_iterator::cur, erase_bucket, vector::size, size_type, and __hashtable_node::val. 

00796 {
00797   size_type f_bucket = first.cur ? bkt_num(first.cur->val) : buckets.size();
00798   size_type l_bucket = last.cur ? bkt_num(last.cur->val) : buckets.size();
00799 
00800   if (first.cur == last.cur)
00801     return;
00802   else if (f_bucket == l_bucket)
00803     erase_bucket(f_bucket, first.cur, last.cur);
00804   else {
00805     erase_bucket(f_bucket, first.cur, 0);
00806     for (size_type n = f_bucket + 1; n < l_bucket; ++n)
00807       erase_bucket(n, 0);
00808     if (l_bucket != buckets.size())
00809       erase_bucket(l_bucket, last.cur);
00810   }
00811 }

template<class V, class K, class HF, class Ex, class Eq, class A>
void hashtable< V, K, HF, Ex, Eq, A >::erase (  const iterator &    it ) 
 

Definition at line 765 of file stl_hashtable.h.

References bkt_num, __hashtable_iterator::cur, delete_node, __hashtable_node::next, num_elements, size_type, and __hashtable_node::val. 

00766 {
00767   if (node* const p = it.cur) {
00768     const size_type n = bkt_num(p->val);
00769     node* cur = buckets[n];
00770 
00771     if (cur == p) {
00772       buckets[n] = cur->next;
00773       delete_node(cur);
00774       --num_elements;
00775     }
00776     else {
00777       node* next = cur->next;
00778       while (next) {
00779         if (next == p) {
00780           cur->next = next->next;
00781           delete_node(next);
00782           --num_elements;
00783           break;
00784         }
00785         else {
00786           cur = next;
00787           next = cur->next;
00788         }
00789       }
00790     }
00791   }
00792 }

template<class V, class K, class HF, class Ex, class Eq, class A>
hashtable< V, K, HF, Ex, Eq, A >::size_type hashtable< V, K, HF, Ex, Eq, A >::erase (  const key_type &    key ) 
 

Definition at line 732 of file stl_hashtable.h.

References bkt_num_key, delete_node, equals, get_key, __hashtable_node::next, num_elements, size_type, and __hashtable_node::val.

Referenced by erase. 

00733 {
00734   const size_type n = bkt_num_key(key);
00735   node* first = buckets[n];
00736   size_type erased = 0;
00737 
00738   if (first) {
00739     node* cur = first;
00740     node* next = cur->next;
00741     while (next) {
00742       if (equals(get_key(next->val), key)) {
00743         cur->next = next->next;
00744         delete_node(next);
00745         next = cur->next;
00746         ++erased;
00747         --num_elements;
00748       }
00749       else {
00750         cur = next;
00751         next = cur->next;
00752       }
00753     }
00754     if (equals(get_key(first->val), key)) {
00755       buckets[n] = first->next;
00756       delete_node(first);
00757       ++erased;
00758       --num_elements;
00759     }
00760   }
00761   return erased;
00762 }

template<class V, class K, class HF, class Ex, class Eq, class A>
void hashtable< V, K, HF, Ex, Eq, A >::erase_bucket (  const size_type    n,
node *    last
)  [private]
 

Definition at line 891 of file stl_hashtable.h.

References delete_node, __hashtable_node::next, and num_elements. 

00892 {
00893   node* cur = buckets[n];
00894   while (cur != last) {
00895     node* next = cur->next;
00896     delete_node(cur);
00897     cur = next;
00898     buckets[n] = cur;
00899     --num_elements;
00900   }
00901 }

template<class V, class K, class HF, class Ex, class Eq, class A>
void hashtable< V, K, HF, Ex, Eq, A >::erase_bucket (  const size_type    n,
node *    first,
node *    last
)  [private]
 

Definition at line 870 of file stl_hashtable.h.

References delete_node, __hashtable_node::next, and num_elements.

Referenced by erase. 

00872 {
00873   node* cur = buckets[n];
00874   if (cur == first)
00875     erase_bucket(n, last);
00876   else {
00877     node* next;
00878     for (next = cur->next; next != first; cur = next, next = cur->next)
00879       ;
00880     while (next) {
00881       cur->next = next->next;
00882       delete_node(next);
00883       next = cur->next;
00884       --num_elements;
00885     }
00886   }
00887 }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
const_iterator hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::find (  const key_type &    key )  const [inline]
 

Definition at line 411 of file stl_hashtable.h. 

00412   {
00413     size_type n = bkt_num_key(key);
00414     const node* first;
00415     for ( first = buckets[n];
00416           first && !equals(get_key(first->val), key);
00417           first = first->next)
00418       {}
00419     return const_iterator(first, this);
00420   }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
iterator hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::find (  const key_type &    key )  [inline]
 

Definition at line 400 of file stl_hashtable.h. 

00401   {
00402     size_type n = bkt_num_key(key);
00403     node* first;
00404     for ( first = buckets[n];
00405           first && !equals(get_key(first->val), key);
00406           first = first->next)
00407       {}
00408     return iterator(first, this);
00409   }

template<class V, class K, class HF, class Ex, class Eq, class A>
hashtable< V, K, HF, Ex, Eq, A >::reference hashtable< V, K, HF, Ex, Eq, A >::find_or_insert (  const value_type &    obj ) 
 

Definition at line 665 of file stl_hashtable.h.

References bkt_num, equals, get_key, new_node, __hashtable_node::next, num_elements, resize, size_type, __hashtable_node::val, and value_type. 

00666 {
00667   resize(num_elements + 1);
00668 
00669   size_type n = bkt_num(obj);
00670   node* first = buckets[n];
00671 
00672   for (node* cur = first; cur; cur = cur->next)
00673     if (equals(get_key(cur->val), get_key(obj)))
00674       return cur->val;
00675 
00676   node* tmp = new_node(obj);
00677   tmp->next = first;
00678   buckets[n] = tmp;
00679   ++num_elements;
00680   return tmp->val;
00681 }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
hasher hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::hash_funct (    )  const [inline]
 

Definition at line 179 of file stl_hashtable.h. 

00179 { return hash; }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
void hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::initialize_buckets (  size_type    n )  [inline, private]
 

Definition at line 449 of file stl_hashtable.h.

Referenced by hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::hashtable. 

00450   {
00451     const size_type n_buckets = next_size(n);
00452     buckets.reserve(n_buckets);
00453     buckets.insert(buckets.end(), n_buckets, (node*) 0);
00454     num_elements = 0;
00455   }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
void hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::insert_equal (  const_iterator    f,
const_iterator    l
)  [inline]
 

Definition at line 388 of file stl_hashtable.h. 

00389   {
00390     size_type n = 0;
00391     distance(f, l, n);
00392     resize(num_elements + n);
00393     for ( ; n > 0; --n, ++f)
00394       insert_equal_noresize(*f);
00395   }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
void hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::insert_equal (  const value_type *    f,
const value_type *    l
)  [inline]
 

Definition at line 371 of file stl_hashtable.h. 

00372   {
00373     size_type n = l - f;
00374     resize(num_elements + n);
00375     for ( ; n > 0; --n, ++f)
00376       insert_equal_noresize(*f);
00377   }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
iterator hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::insert_equal (  const value_type &    obj )  [inline]
 

Definition at line 302 of file stl_hashtable.h. 

00303   {
00304     resize(num_elements + 1);
00305     return insert_equal_noresize(obj);
00306   }

template<class V, class K, class HF, class Ex, class Eq, class A>
hashtable< V, K, HF, Ex, Eq, A >::iterator hashtable< V, K, HF, Ex, Eq, A >::insert_equal_noresize (  const value_type &    obj ) 
 

Definition at line 642 of file stl_hashtable.h.

References bkt_num, equals, get_key, iterator, new_node, __hashtable_node::next, num_elements, size_type, __hashtable_node::val, and value_type.

Referenced by hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::insert_equal. 

00643 {
00644   const size_type n = bkt_num(obj);
00645   node* first = buckets[n];
00646 
00647   for (node* cur = first; cur; cur = cur->next) 
00648     if (equals(get_key(cur->val), get_key(obj))) {
00649       node* tmp = new_node(obj);
00650       tmp->next = cur->next;
00651       cur->next = tmp;
00652       ++num_elements;
00653       return iterator(tmp, this);
00654     }
00655 
00656   node* tmp = new_node(obj);
00657   tmp->next = first;
00658   buckets[n] = tmp;
00659   ++num_elements;
00660   return iterator(tmp, this);
00661 }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
void hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::insert_unique (  const_iterator    f,
const_iterator    l
)  [inline]
 

Definition at line 379 of file stl_hashtable.h. 

00380   {
00381     size_type n = 0;
00382     distance(f, l, n);
00383     resize(num_elements + n);
00384     for ( ; n > 0; --n, ++f)
00385       insert_unique_noresize(*f);
00386   }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
void hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::insert_unique (  const value_type *    f,
const value_type *    l
)  [inline]
 

Definition at line 363 of file stl_hashtable.h. 

00364   {
00365     size_type n = l - f;
00366     resize(num_elements + n);
00367     for ( ; n > 0; --n, ++f)
00368       insert_unique_noresize(*f);
00369   }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
pair<iterator, bool> hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::insert_unique (  const value_type &    obj )  [inline]
 

Definition at line 296 of file stl_hashtable.h. 

00297   {
00298     resize(num_elements + 1);
00299     return insert_unique_noresize(obj);
00300   }

template<class V, class K, class HF, class Ex, class Eq, class A>
pair< typename hashtable< V, K, HF, Ex, Eq, A >::iterator, bool > hashtable< V, K, HF, Ex, Eq, A >::insert_unique_noresize (  const value_type &    obj ) 
 

Definition at line 624 of file stl_hashtable.h.

References bkt_num, equals, get_key, iterator, new_node, __hashtable_node::next, num_elements, size_type, __hashtable_node::val, and value_type.

Referenced by hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::insert_unique. 

00625 {
00626   const size_type n = bkt_num(obj);
00627   node* first = buckets[n];
00628 
00629   for (node* cur = first; cur; cur = cur->next) 
00630     if (equals(get_key(cur->val), get_key(obj)))
00631       return pair<iterator, bool>(iterator(cur, this), false);
00632 
00633   node* tmp = new_node(obj);
00634   tmp->next = first;
00635   buckets[n] = tmp;
00636   ++num_elements;
00637   return pair<iterator, bool>(iterator(tmp, this), true);
00638 }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
key_equal hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::key_eq (    )  const [inline]
 

Definition at line 180 of file stl_hashtable.h. 

00180 { return equals; }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
size_type hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::max_bucket_count (    )  const [inline]
 

Definition at line 285 of file stl_hashtable.h. 

00286     { return __stl_prime_list[__stl_num_primes - 1]; }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
size_type hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::max_size (    )  const [inline]
 

Definition at line 246 of file stl_hashtable.h. 

00246 { return size_type(-1); }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
node* hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::new_node (  const value_type &    obj )  [inline, private]
 

Definition at line 477 of file stl_hashtable.h.

Referenced by copy_from, find_or_insert, insert_equal_noresize, and insert_unique_noresize. 

00478   {
00479     node* n = node_allocator::allocate();
00480     n->next = 0;
00481     __STL_TRY {
00482       construct(&n->val, obj);
00483       return n;
00484     }
00485     __STL_UNWIND(node_allocator::deallocate(n));
00486   }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
size_type hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::next_size (  size_type    n )  const [inline, private]
 

Definition at line 447 of file stl_hashtable.h.

Referenced by hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::initialize_buckets, and resize. 

00447 { return __stl_next_prime(n); }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
hashtable& hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::operator= (  const hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc > &    ht )  [inline]
 

Definition at line 231 of file stl_hashtable.h. 

00232   {
00233     if (&ht != this) {
00234       clear();
00235       hash = ht.hash;
00236       equals = ht.equals;
00237       get_key = ht.get_key;
00238       copy_from(ht);
00239     }
00240     return *this;
00241   }

template<class V, class K, class HF, class Ex, class Eq, class A>
void hashtable< V, K, HF, Ex, Eq, A >::resize (  size_type    num_elements_hint ) 
 

Definition at line 833 of file stl_hashtable.h.

References __STL_TRY, bkt_num, delete_node, __hashtable_node::next, next_size, vector::size, size_type, vector::swap, and __hashtable_node::val.

Referenced by find_or_insert, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::insert_equal, and hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::insert_unique. 

00834 {
00835   const size_type old_n = buckets.size();
00836   if (num_elements_hint > old_n) {
00837     const size_type n = next_size(num_elements_hint);
00838     if (n > old_n) {
00839       vector<node*, A> tmp(n, (node*) 0);
00840       __STL_TRY {
00841         for (size_type bucket = 0; bucket < old_n; ++bucket) {
00842           node* first = buckets[bucket];
00843           while (first) {
00844             size_type new_bucket = bkt_num(first->val, n);
00845             buckets[bucket] = first->next;
00846             first->next = tmp[new_bucket];
00847             tmp[new_bucket] = first;
00848             first = buckets[bucket];          
00849           }
00850         }
00851         buckets.swap(tmp);
00852       }
00853 #         ifdef __STL_USE_EXCEPTIONS
00854       catch(...) {
00855         for (size_type bucket = 0; bucket < tmp.size(); ++bucket) {
00856           while (tmp[bucket]) {
00857             node* next = tmp[bucket]->next;
00858             delete_node(tmp[bucket]);
00859             tmp[bucket] = next;
00860           }
00861         }
00862         throw;
00863       }
00864 #         endif /* __STL_USE_EXCEPTIONS */
00865     }
00866   }
00867 }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
size_type hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::size (    )  const [inline]
 

Definition at line 245 of file stl_hashtable.h.

Referenced by hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::empty. 

00245 { return num_elements; }

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
void hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >::swap (  hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc > &    ht )  [inline]
 

Definition at line 249 of file stl_hashtable.h. 

00250   {
00251     __STD::swap(hash, ht.hash);
00252     __STD::swap(equals, ht.equals);
00253     __STD::swap(get_key, ht.get_key);
00254     buckets.swap(ht.buckets);
00255     __STD::swap(num_elements, ht.num_elements);
00256   }

Friends And Related Function Documentation

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
friend struct __hashtable_const_iterator< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc > [friend]
 

Definition at line 204 of file stl_hashtable.h.

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
friend struct __hashtable_iterator< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc > [friend]
 

Definition at line 202 of file stl_hashtable.h.

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
bool operator==__STL_NULL_TMPL_ARGS (  const hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc > &   ,
const hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc > &   
)  [friend]
 

Member Data Documentation

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
vector<node*,Alloc> hashtable::buckets [private]
 

Definition at line 190 of file stl_hashtable.h.

Referenced by copy_from, __hashtable_const_iterator::operator++, __hashtable_iterator::operator++, operator==, and hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::swap.

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
key_equal hashtable::equals [private]
 

Definition at line 184 of file stl_hashtable.h.

Referenced by hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::count, equal_range, erase, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::find, find_or_insert, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::hashtable, insert_equal_noresize, insert_unique_noresize, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::key_eq, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::operator=, and hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::swap.

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
ExtractKey hashtable::get_key [private]
 

Definition at line 185 of file stl_hashtable.h.

Referenced by hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::bkt_num, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::count, equal_range, erase, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::find, find_or_insert, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::hashtable, insert_equal_noresize, insert_unique_noresize, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::operator=, and hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::swap.

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
hasher hashtable::hash [private]
 

Definition at line 183 of file stl_hashtable.h.

Referenced by hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::bkt_num_key, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::operator=, and hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::swap.

template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
size_type hashtable::num_elements [private]
 

Definition at line 191 of file stl_hashtable.h.

Referenced by clear, copy_from, erase, erase_bucket, find_or_insert, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::hashtable, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::initialize_buckets, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::insert_equal, insert_equal_noresize, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::insert_unique, insert_unique_noresize, hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::size, and hashtable< Value, Value, HashFcn, identity< Value >, EqualKey, Alloc >::swap.

The documentation for this class was generated from the following file:
logo OpenMask

Documentation generated on Thu May 2 15:03:31 2002

Generated with doxygen 1.2.12 by Dimitri van Heesch ,   1997-2001