-
Notifications
You must be signed in to change notification settings - Fork 0
/
23_HashTable.cpp
42 lines (39 loc) · 1.37 KB
/
23_HashTable.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstring>
#include <vector>
using namespace std;
template <class Value>
struct __hashtable_node {
__hashtable_node* next;
Value val;
};
template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
struct __hashtable_iterator {
typedef __hashtable_node<Value> node;
typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> hashtable;
node* cur;
hashtable* ht; // back to buckets vector to next bucket
};
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey, class Alloc>
class hashtable {
public:
typedef HashFcn hasher;
typedef EqualKey key_equal;
typedef size_t size_type;
typedef Key key_type;
typedef Value value_type;
private:
hasher hash;
key_equal equals;
ExtractKey get_key;
typedef __hashtable_node<Value> node;
vector<node*, Alloc> buckets;
size_type num_elements;
protected:
size_type bkt_num(const value_type& obj, size_type n) const { return bkt_num_key(get_key(obj), n); }
size_type bkt_num(const value_type& obj) const { return bkt_num_key(get_key(obj)); }
size_type bkt_num_key(const key_type& key, size_type n) const { return hash(key) % n;}
size_type bkt_num_key(const key_type& key) const { return bkt_num_key(key, buckets.size()); }
public:
size_type bucket_count() const { return buckets.size(); }
};