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
27namespace Poco {
28
29
30template <class Key, class Value>
31struct 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
67template <class HME, class KeyHashFunc>
68struct 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
76private:
77 KeyHashFunc _func;
78};
79
80
81template <class Key, class Mapped, class HashFunc = Hash<Key> >
82class HashMap
83 /// This class implements a map using a LinearHashTable.
84 ///
85 /// A HashMap can be used just like a std::map.
86{
87public:
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
220private:
221 HashTable _table;
222};
223
224
225} // namespace Poco
226
227
228#endif // Foundation_HashMap_INCLUDED
229