1 | // |
2 | // HashMap.h |
3 | // |
4 | // Library: Foundation |
5 | // Package: Hashing |
6 | // Module: HashMap |
7 | // |
8 | // Definition of the HashMap class. |
9 | // |
10 | // Copyright (c) 2006, Applied Informatics Software Engineering GmbH. |
11 | // and Contributors. |
12 | // |
13 | // SPDX-License-Identifier: BSL-1.0 |
14 | // |
15 | |
16 | |
17 | #ifndef Foundation_HashMap_INCLUDED |
18 | #define Foundation_HashMap_INCLUDED |
19 | |
20 | |
21 | #include "Poco/Foundation.h" |
22 | #include "Poco/LinearHashTable.h" |
23 | #include "Poco/Exception.h" |
24 | #include <utility> |
25 | |
26 | |
27 | namespace Poco { |
28 | |
29 | |
30 | template <class Key, class Value> |
31 | struct HashMapEntry |
32 | /// This class template is used internally by HashMap. |
33 | { |
34 | Key first; |
35 | Value second; |
36 | |
37 | HashMapEntry(): |
38 | first(), |
39 | second() |
40 | { |
41 | } |
42 | |
43 | HashMapEntry(const Key& key): |
44 | first(key), |
45 | second() |
46 | { |
47 | } |
48 | |
49 | HashMapEntry(const Key& key, const Value& value): |
50 | first(key), |
51 | second(value) |
52 | { |
53 | } |
54 | |
55 | bool operator == (const HashMapEntry& entry) const |
56 | { |
57 | return first == entry.first; |
58 | } |
59 | |
60 | bool operator != (const HashMapEntry& entry) const |
61 | { |
62 | return first != entry.first; |
63 | } |
64 | }; |
65 | |
66 | |
67 | template <class HME, class KeyHashFunc> |
68 | struct HashMapEntryHash |
69 | /// This class template is used internally by HashMap. |
70 | { |
71 | std::size_t operator () (const HME& entry) const |
72 | { |
73 | return _func(entry.first); |
74 | } |
75 | |
76 | private: |
77 | KeyHashFunc _func; |
78 | }; |
79 | |
80 | |
81 | template <class Key, class Mapped, class HashFunc = Hash<Key> > |
82 | class HashMap |
83 | /// This class implements a map using a LinearHashTable. |
84 | /// |
85 | /// A HashMap can be used just like a std::map. |
86 | { |
87 | public: |
88 | typedef Key KeyType; |
89 | typedef Mapped MappedType; |
90 | typedef Mapped& Reference; |
91 | typedef const Mapped& ConstReference; |
92 | typedef Mapped* Pointer; |
93 | typedef const Mapped* ConstPointer; |
94 | |
95 | typedef HashMapEntry<Key, Mapped> ValueType; |
96 | typedef std::pair<KeyType, MappedType> PairType; |
97 | |
98 | typedef HashMapEntryHash<ValueType, HashFunc> HashType; |
99 | typedef LinearHashTable<ValueType, HashType> HashTable; |
100 | |
101 | typedef typename HashTable::Iterator Iterator; |
102 | typedef typename HashTable::ConstIterator ConstIterator; |
103 | |
104 | HashMap() |
105 | /// Creates an empty HashMap. |
106 | { |
107 | } |
108 | |
109 | HashMap(std::size_t initialReserve): |
110 | _table(initialReserve) |
111 | /// Creates the HashMap with room for initialReserve entries. |
112 | { |
113 | } |
114 | |
115 | HashMap& operator = (const HashMap& map) |
116 | /// Assigns another HashMap. |
117 | { |
118 | HashMap tmp(map); |
119 | swap(tmp); |
120 | return *this; |
121 | } |
122 | |
123 | void swap(HashMap& map) |
124 | /// Swaps the HashMap with another one. |
125 | { |
126 | _table.swap(map._table); |
127 | } |
128 | |
129 | ConstIterator begin() const |
130 | { |
131 | return _table.begin(); |
132 | } |
133 | |
134 | ConstIterator end() const |
135 | { |
136 | return _table.end(); |
137 | } |
138 | |
139 | Iterator begin() |
140 | { |
141 | return _table.begin(); |
142 | } |
143 | |
144 | Iterator end() |
145 | { |
146 | return _table.end(); |
147 | } |
148 | |
149 | ConstIterator find(const KeyType& key) const |
150 | { |
151 | ValueType value(key); |
152 | return _table.find(value); |
153 | } |
154 | |
155 | Iterator find(const KeyType& key) |
156 | { |
157 | ValueType value(key); |
158 | return _table.find(value); |
159 | } |
160 | |
161 | std::size_t count(const KeyType& key) const |
162 | { |
163 | ValueType value(key); |
164 | return _table.find(value) != _table.end() ? 1 : 0; |
165 | } |
166 | |
167 | std::pair<Iterator, bool> insert(const PairType& pair) |
168 | { |
169 | ValueType value(pair.first, pair.second); |
170 | return _table.insert(value); |
171 | } |
172 | |
173 | std::pair<Iterator, bool> insert(const ValueType& value) |
174 | { |
175 | return _table.insert(value); |
176 | } |
177 | |
178 | void erase(Iterator it) |
179 | { |
180 | _table.erase(it); |
181 | } |
182 | |
183 | void erase(const KeyType& key) |
184 | { |
185 | Iterator it = find(key); |
186 | _table.erase(it); |
187 | } |
188 | |
189 | void clear() |
190 | { |
191 | _table.clear(); |
192 | } |
193 | |
194 | std::size_t size() const |
195 | { |
196 | return _table.size(); |
197 | } |
198 | |
199 | bool empty() const |
200 | { |
201 | return _table.empty(); |
202 | } |
203 | |
204 | ConstReference operator [] (const KeyType& key) const |
205 | { |
206 | ConstIterator it = _table.find(key); |
207 | if (it != _table.end()) |
208 | return it->second; |
209 | else |
210 | throw NotFoundException(); |
211 | } |
212 | |
213 | Reference operator [] (const KeyType& key) |
214 | { |
215 | ValueType value(key); |
216 | std::pair<Iterator, bool> res = _table.insert(value); |
217 | return res.first->second; |
218 | } |
219 | |
220 | private: |
221 | HashTable _table; |
222 | }; |
223 | |
224 | |
225 | } // namespace Poco |
226 | |
227 | |
228 | #endif // Foundation_HashMap_INCLUDED |
229 | |