Go to the documentation of this file.00001
00002
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 };
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 };
00233
00234 }
00235 }
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