table.hh
Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  * $Id: table.hh 957 2005-03-07 16:01:20Z sjoyeux $
00003  */
00004 #ifndef UTILMM_UTILS_HASH_TABLE_HEADER
00005 # define UTILMM_UTILS_HASH_TABLE_HEADER
00006 
00007 # include <utility> 
00008 # include <vector>
00009 
00010 #include "utilmm/functional/arg_traits.hh"
00011 
00012 #include "utilmm/hash/hash_fwd.hh"
00013 #include "utilmm/hash/bits/iter.hh"
00014 
00015 namespace utilmm {
00016   namespace hash_toolbox {
00017 
00018     template<typename Value>
00019     struct node {
00020       explicit node(Value const &v, node *n=0);
00021 
00022       Value val;
00023       node *next;
00024     }; // struct utilmm::hash_toolbox::node<>
00025     
00044     template<typename Key, typename Value, 
00045              class Extract, class Hash, class Equal>
00046     class table {
00047     public:
00049       typedef Value  value_type;
00051       typedef Key    key_type;
00053       typedef size_t size_type;
00054       
00055       typedef typename arg_traits<value_type>::type value_arg;
00056       typedef typename arg_traits<key_type>::type key_arg;
00057 
00058     private:
00059       typedef node<value_type> node_type;
00060       typedef std::vector<node_type *> bucket_type;
00061 
00062     public:
00067       typedef iter<Key, Value, Extract, Hash, Equal>       iterator;
00073       typedef const_iter<Key, Value, Extract, Hash, Equal> const_iterator;
00074       
00079       table();
00081       table(table const &);
00082       
00084       ~table();
00085 
00093       void swap(table &other);
00095       table &operator= (table const &other);
00096       
00102       size_type size() const;
00107       size_type max_size() const;
00108 
00116       bool empty() const;
00117 
00125       iterator begin();
00133       iterator end();
00134 
00142       const_iterator begin() const;
00150       const_iterator end() const;
00151 
00162       std::pair<iterator, iterator> equal_range(key_arg key);
00167       std::pair< const_iterator,
00168                  const_iterator > equal_range(key_arg key) const;
00169 
00177       void erase(iterator const &first, iterator const &last);
00178 
00190       std::pair<iterator, bool> insert_unique(value_arg v);
00200       iterator insert_multiple(value_arg v);
00201 
00206       void clear();
00207 
00208     private:
00209       bucket_type bucket;
00210       size_type   node_count, avg_bucket_count;
00211       
00212       void resize(size_type size);
00213       
00214       node_type *insert(node_type **helper, value_arg v);
00215       
00216       static size_t hash_key(key_arg k, size_type mod);
00217       static size_t hash_node(value_arg v, size_type mod);
00218       static key_type const &get_key(value_arg v);
00219 
00220       static bucket_type copy_bucket(bucket_type const &other);
00221 
00222       size_t hash_node(value_arg v);
00223       
00224       node_type **find_node(key_arg k);
00225       node_type *find_node(key_arg k) const;
00226 
00227       template<typename K, typename V, class Ex, class H, class Eq>
00228       friend class iter;
00229       
00230       template<typename K, typename V, class Ex, class H, class Eq>
00231       friend class const_iter;
00232     }; // class utilmm::hash_toolbox::table<>
00233 
00234   } // namespace utilmm::hash_toolbox
00235 } // namespace utilmm
00236 
00237 # define IN_UTILMM_UTILS_HASH_TABLE_HEADER
00238 #include "utilmm/hash/bits/table.tcc"
00239 # undef IN_UTILMM_UTILS_HASH_TABLE_HEADER
00240 #endif // UTILMM_UTILS_HASH_TABLE_HEADER
00241 


utilmm
Author(s): Sylvain Joyeux/sylvain.joyeux@m4x.org
autogenerated on Wed Sep 16 2015 07:05:43