CppCommon 1.0.5.0
C++ Common Library
Loading...
Searching...
No Matches
hashmap.inl
Go to the documentation of this file.
1
9namespace CppCommon {
10
11template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
12inline HashMap<TKey, TValue, THash, TEqual, TAllocator>::HashMap(size_t capacity, const TKey& blank, const THash& hash, const TEqual& equal, const TAllocator& allocator)
13 : _hash(hash), _equal(equal), _blank(blank), _size(0), _buckets(allocator)
14{
15 size_t reserve = 1;
16 while (reserve < capacity)
17 reserve <<= 1;
18 _buckets.resize(reserve, std::make_pair(_blank, TValue()));
19}
20
21template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
22template <class InputIterator>
23inline HashMap<TKey, TValue, THash, TEqual, TAllocator>::HashMap(InputIterator first, InputIterator last, bool unused, size_t capacity, const TKey& blank, const THash& hash, const TEqual& equal, const TAllocator& allocator)
24 : HashMap(capacity, blank, hash, equal, allocator)
25{
26 for (auto it = first; it != last; ++it)
27 insert(*it);
28}
29
30template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
32 : HashMap(hashmap.bucket_count(), hashmap._blank, hashmap._hash, hashmap._equal, hashmap._buckets.get_allocator())
33{
34 for (const auto& item : hashmap)
35 insert(item);
36}
37
38template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
40 : HashMap(capacity, hashmap._blank, hashmap._hash, hashmap._equal, hashmap._buckets.get_allocator())
41{
42 for (const auto& item : hashmap)
43 insert(item);
44}
45
46template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
48{
49 clear();
50 reserve(hashmap.size());
51 for (const auto& item : hashmap)
52 insert(item);
53 return *this;
54}
55
56template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
61
62template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
67
68template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
73
74template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
79
80template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
85
86template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
91
92template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
97
98template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
103
104template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
109
110template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
115
116template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
121
122template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
127
128template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
130{
131 assert(!key_equal(key, _blank) && "Cannot find a blank key!");
132
133 for (size_t index = key_to_index(key);; index = next_index(index))
134 {
135 if (key_equal(_buckets[index].first, key))
136 return iterator(this, index);
137 if (key_equal(_buckets[index].first, _blank))
138 return end();
139 }
140}
141
142template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
144{
145 assert(!key_equal(key, _blank) && "Cannot find a blank key!");
146
147 for (size_t index = key_to_index(key);; index = next_index(index))
148 {
149 if (key_equal(_buckets[index].first, key))
150 return const_iterator(this, index);
151 if (key_equal(_buckets[index].first, _blank))
152 return end();
153 }
154}
155
156template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
157inline std::pair<typename HashMap<TKey, TValue, THash, TEqual, TAllocator>::iterator, typename HashMap<TKey, TValue, THash, TEqual, TAllocator>::iterator> HashMap<TKey, TValue, THash, TEqual, TAllocator>::equal_range(const TKey& key) noexcept
158{
159 return std::make_pair(find(key), end());
160}
161
162template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
163inline std::pair<typename HashMap<TKey, TValue, THash, TEqual, TAllocator>::const_iterator, typename HashMap<TKey, TValue, THash, TEqual, TAllocator>::const_iterator> HashMap<TKey, TValue, THash, TEqual, TAllocator>::equal_range(const TKey& key) const noexcept
164{
165 return std::make_pair(find(key), end());
166}
167
168template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
170{
171 auto it = find(key);
172 if (it == end())
173 throw std::out_of_range("Item with the given key was not found in the hash map!");
174
175 return it->second;
176}
177
178template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
180{
181 auto it = find(key);
182 if (it == end())
183 throw std::out_of_range("Item with the given key was not found in the hash map!");
184
185 return it->second;
186}
187
188template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
189inline std::pair<typename HashMap<TKey, TValue, THash, TEqual, TAllocator>::iterator, bool> HashMap<TKey, TValue, THash, TEqual, TAllocator>::insert(const value_type& item)
190{
191 return emplace_internal(item.first, item.second);
192}
193
194template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
195inline std::pair<typename HashMap<TKey, TValue, THash, TEqual, TAllocator>::iterator, bool> HashMap<TKey, TValue, THash, TEqual, TAllocator>::insert(value_type&& item)
196{
197 return emplace_internal(item.first, std::move(item.second));
198}
199
200template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
201template <typename... Args>
202inline std::pair<typename HashMap<TKey, TValue, THash, TEqual, TAllocator>::iterator, bool> HashMap<TKey, TValue, THash, TEqual, TAllocator>::emplace(Args&&... args)
203{
204 return emplace_internal(std::forward<Args>(args)...);
205}
206
207template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
209{
210 auto it = find(key);
211 if (it == end())
212 return 0;
213
214 erase_internal(it._index);
215 return 1;
216}
217
218template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
220{
221 erase_internal(position._index);
222}
223
224template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
225template <typename... Args>
226inline std::pair<typename HashMap<TKey, TValue, THash, TEqual, TAllocator>::iterator, bool> HashMap<TKey, TValue, THash, TEqual, TAllocator>::emplace_internal(const TKey& key, Args&&... args)
227{
228 assert(!key_equal(key, _blank) && "Cannot emplace a blank key!");
229
230 reserve(_size + 1);
231
232 for (size_t index = key_to_index(key);; index = next_index(index))
233 {
234 if (key_equal(_buckets[index].first, key))
235 return std::make_pair(iterator(this, index), false);
236 if (key_equal(_buckets[index].first, _blank))
237 {
238 _buckets[index].first = key;
239 _buckets[index].second = TValue(std::forward<Args>(args)...);
240 ++_size;
241 return std::make_pair(iterator(this, index), true);
242 }
243 }
244}
245
246template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
248{
249 size_t current = index;
250 for (index = next_index(current);; index = next_index(index))
251 {
252 if (key_equal(_buckets[index].first, _blank))
253 {
254 _buckets[current].first = _blank;
255 --_size;
256 return;
257 }
258
259 // Move buckets with the same key hash closer to the first suitable position in the hash map
260 size_t base = key_to_index(_buckets[index].first);
261 if (diff(current, base) < diff(index, base))
262 {
263 _buckets[current] = _buckets[index];
264 current = index;
265 }
266 }
267}
268
269template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
270inline size_t HashMap<TKey, TValue, THash, TEqual, TAllocator>::key_to_index(const TKey& key) const noexcept
271{
272 size_t mask = _buckets.size() - 1;
273 return _hash(key) & mask;
274}
275
276template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
277inline size_t HashMap<TKey, TValue, THash, TEqual, TAllocator>::next_index(size_t index) const noexcept
278{
279 size_t mask = _buckets.size() - 1;
280 return (index + 1) & mask;
281}
282
283template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
284inline size_t HashMap<TKey, TValue, THash, TEqual, TAllocator>::diff(size_t index1, size_t index2) const noexcept
285{
286 size_t mask = _buckets.size() - 1;
287 return (_buckets.size() + (index1 - index2)) & mask;
288}
289
290template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
292{
293 capacity = std::max(capacity, 2 * size());
295 swap(temp);
296}
297
298template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
300{
301 if (_buckets.size() < 2 * count)
302 rehash(2 * count);
303}
304
305template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
307{
308 _size = 0;
309 for (auto& bucket : _buckets)
310 bucket.first = _blank;
311}
312
313template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
315{
316 using std::swap;
317 swap(_hash, hashmap._hash);
318 swap(_equal, hashmap._equal);
319 swap(_blank, hashmap._blank);
320 swap(_size, hashmap._size);
321 swap(_buckets, hashmap._buckets);
322}
323
324template <typename TKey, typename TValue, typename THash, typename TEqual, typename TAllocator>
326{
327 hashmap1.swap(hashmap2);
328}
329
330template <class TContainer, typename TKey, typename TValue>
331inline HashMapIterator<TContainer, TKey, TValue>::HashMapIterator(TContainer* container) noexcept : _container(container), _index(0)
332{
333 if (_container != nullptr)
334 {
335 if (_container->size() == 0)
336 {
337 // Hash map is empty
338 _container = nullptr;
339 _index = 0;
340 return;
341 }
342 else
343 {
344 for (size_t i = 0; i < _container->_buckets.size(); ++i)
345 {
346 if (!_container->key_equal(_container->_buckets[i].first, _container->_blank))
347 {
348 _index = i;
349 return;
350 }
351 }
352
353 assert(false && "Non empty hash map has no valid items!");
354 }
355 }
356}
357
358template <class TContainer, typename TKey, typename TValue>
360{
361 if (_container != nullptr)
362 {
363 for (size_t i = _index + 1; i < _container->_buckets.size(); ++i)
364 {
365 if (!_container->key_equal(_container->_buckets[i].first, _container->_blank))
366 {
367 _index = i;
368 return *this;
369 }
370 }
371
372 // End of the hash map
373 _container = nullptr;
374 _index = 0;
375 }
376
377 return *this;
378}
379
380template <class TContainer, typename TKey, typename TValue>
387
388template <class TContainer, typename TKey, typename TValue>
390{
391 assert(((_container != nullptr) && (_index < _container->_buckets.size())) && "Iterator must be valid!");
392
393 return _container->_buckets[_index];
394}
395
396template <class TContainer, typename TKey, typename TValue>
398{
399 return ((_container != nullptr) && (_index < _container->_buckets.size())) ? &_container->_buckets[_index] : nullptr;
400}
401
402template <class TContainer, typename TKey, typename TValue>
404{
405 using std::swap;
406 swap(_container, it._container);
407 swap(_index, it._index);
408}
409
410template <class TContainer, typename TKey, typename TValue>
415
416template <class TContainer, typename TKey, typename TValue>
417inline HashMapConstIterator<TContainer, TKey, TValue>::HashMapConstIterator(const TContainer* container) noexcept : _container(container), _index(0)
418{
419 if (_container != nullptr)
420 {
421 if (_container->size() == 0)
422 {
423 // Hash map is empty
424 _container = nullptr;
425 _index = 0;
426 return;
427 }
428 else
429 {
430 for (size_t i = 0; i < _container->_buckets.size(); ++i)
431 {
432 if (!_container->key_equal(_container->_buckets[i].first, _container->_blank))
433 {
434 _index = i;
435 return;
436 }
437 }
438
439 assert(false && "Non empty hash map has no valid items!");
440 }
441 }
442}
443
444template <class TContainer, typename TKey, typename TValue>
446{
447 if (_container != nullptr)
448 {
449 for (size_t i = _index + 1; i < _container->_buckets.size(); ++i)
450 {
451 if (!_container->key_equal(_container->_buckets[i].first, _container->_blank))
452 {
453 _index = i;
454 return *this;
455 }
456 }
457
458 // End of the hash map
459 _container = nullptr;
460 _index = 0;
461 }
462
463 return *this;
464}
465
466template <class TContainer, typename TKey, typename TValue>
473
474template <class TContainer, typename TKey, typename TValue>
476{
477 assert(((_container != nullptr) && (_index < _container->_buckets.size())) && "Iterator must be valid!");
478
479 return _container->_buckets[_index];
480}
481
482template <class TContainer, typename TKey, typename TValue>
484{
485 return ((_container != nullptr) && (_index < _container->_buckets.size())) ? &_container->_buckets[_index] : nullptr;
486}
487
488template <class TContainer, typename TKey, typename TValue>
490{
491 using std::swap;
492 swap(_container, it._container);
493 swap(_index, it._index);
494}
495
496template <class TContainer, typename TKey, typename TValue>
501
502template <class TContainer, typename TKey, typename TValue>
503inline HashMapReverseIterator<TContainer, TKey, TValue>::HashMapReverseIterator(TContainer* container) noexcept : _container(container), _index(0)
504{
505 if (_container != nullptr)
506 {
507 if (_container->size() == 0)
508 {
509 // Hash map is empty
510 _container = nullptr;
511 _index = 0;
512 return;
513 }
514 else
515 {
516 for (size_t i = _container->_buckets.size(); i-- > 0;)
517 {
518 if (!_container->key_equal(_container->_buckets[i].first, _container->_blank))
519 {
520 _index = i;
521 return;
522 }
523 }
524
525 assert(false && "Non empty hash map has no valid items!");
526 }
527 }
528}
529
530template <class TContainer, typename TKey, typename TValue>
532{
533 if (_container != nullptr)
534 {
535 for (size_t i = _index; i-- > 0;)
536 {
537 if (!_container->key_equal(_container->_buckets[i].first, _container->_blank))
538 {
539 _index = i;
540 return *this;
541 }
542 }
543
544 // End of the hash map
545 _container = nullptr;
546 _index = 0;
547 }
548
549 return *this;
550}
551
552template <class TContainer, typename TKey, typename TValue>
559
560template <class TContainer, typename TKey, typename TValue>
562{
563 assert(((_container != nullptr) && (_index < _container->_buckets.size())) && "Iterator must be valid!");
564
565 return _container->_buckets[_index];
566}
567
568template <class TContainer, typename TKey, typename TValue>
570{
571 return ((_container != nullptr) && (_index < _container->_buckets.size())) ? &_container->_buckets[_index] : nullptr;
572}
573
574template <class TContainer, typename TKey, typename TValue>
576{
577 using std::swap;
578 swap(_container, it._container);
579 swap(_index, it._index);
580}
581
582template <class TContainer, typename TKey, typename TValue>
587
588template <class TContainer, typename TKey, typename TValue>
589inline HashMapConstReverseIterator<TContainer, TKey, TValue>::HashMapConstReverseIterator(const TContainer* container) noexcept : _container(container), _index(0)
590{
591 if (_container != nullptr)
592 {
593 if (_container->size() == 0)
594 {
595 // Hash map is empty
596 _container = nullptr;
597 _index = 0;
598 return;
599 }
600 else
601 {
602 for (size_t i = _container->_buckets.size(); i-- > 0;)
603 {
604 if (!_container->key_equal(_container->_buckets[i].first, _container->_blank))
605 {
606 _index = i;
607 return;
608 }
609 }
610
611 assert(false && "Non empty hash map has no valid items!");
612 }
613 }
614}
615
616template <class TContainer, typename TKey, typename TValue>
618{
619 if (_container != nullptr)
620 {
621 for (size_t i = _index; i-- > 0;)
622 {
623 if (!_container->key_equal(_container->_buckets[i].first, _container->_blank))
624 {
625 _index = i;
626 return *this;
627 }
628 }
629
630 // End of the hash map
631 _container = nullptr;
632 _index = 0;
633 }
634
635 return *this;
636}
637
638template <class TContainer, typename TKey, typename TValue>
645
646template <class TContainer, typename TKey, typename TValue>
648{
649 assert(((_container != nullptr) && (_index < _container->_buckets.size())) && "Iterator must be valid!");
650
651 return _container->_buckets[_index];
652}
653
654template <class TContainer, typename TKey, typename TValue>
656{
657 return ((_container != nullptr) && (_index < _container->_buckets.size())) ? &_container->_buckets[_index] : nullptr;
658}
659
660template <class TContainer, typename TKey, typename TValue>
662{
663 using std::swap;
664 swap(_container, it._container);
665 swap(_index, it._index);
666}
667
668template <class TContainer, typename TKey, typename TValue>
673
674} // namespace CppCommon
Hash map constant iterator.
Definition hashmap.h:279
const_reference operator*() const noexcept
Definition hashmap.inl:475
friend void swap(HashMapConstIterator< UContainer, UKey, UValue > &it1, HashMapConstIterator< UContainer, UKey, UValue > &it2) noexcept
HashMapConstIterator & operator++() noexcept
Definition hashmap.inl:445
const value_type * const_pointer
Definition hashmap.h:288
const_pointer operator->() const noexcept
Definition hashmap.inl:483
const value_type & const_reference
Definition hashmap.h:286
Hash map constant reverse iterator.
Definition hashmap.h:391
const_reference operator*() const noexcept
Definition hashmap.inl:647
friend void swap(HashMapConstReverseIterator< UContainer, UKey, UValue > &it1, HashMapConstReverseIterator< UContainer, UKey, UValue > &it2) noexcept
const_pointer operator->() const noexcept
Definition hashmap.inl:655
HashMapConstReverseIterator & operator++() noexcept
Definition hashmap.inl:617
Hash map container.
Definition hashmap.h:45
iterator find(const TKey &key) noexcept
Find the iterator which points to the first item with the given key in the hash map or return end ite...
Definition hashmap.inl:129
reverse_iterator rbegin() noexcept
Get the reverse begin hash map iterator.
Definition hashmap.inl:93
std::pair< iterator, bool > insert(const value_type &item)
Insert a new item into the hash map.
Definition hashmap.inl:189
TValue mapped_type
Definition hashmap.h:54
void clear() noexcept
Clear the hash map.
Definition hashmap.inl:306
mapped_type & at(const TKey &key) noexcept
Access to the item with the given key or throw std::out_of_range exception.
Definition hashmap.inl:169
const_iterator cend() const noexcept
Definition hashmap.inl:87
const_iterator cbegin() const noexcept
Definition hashmap.inl:69
void rehash(size_t capacity)
Rehash the hash map to the given capacity or more.
Definition hashmap.inl:291
std::pair< iterator, bool > emplace(Args &&... args)
Emplace a new item into the hash map.
const_reverse_iterator crend() const noexcept
Definition hashmap.inl:123
const_reverse_iterator crbegin() const noexcept
Definition hashmap.inl:105
void reserve(size_t count)
Reserve the hash map capacity to fit the given count of items.
Definition hashmap.inl:299
iterator end() noexcept
Get the end hash map iterator.
Definition hashmap.inl:75
HashMap(size_t capacity=128, const TKey &blank=TKey(), const THash &hash=THash(), const TEqual &equal=TEqual(), const TAllocator &allocator=TAllocator())
Initialize the hash map with a given capacity and blank key value.
Definition hashmap.inl:12
std::pair< TKey, TValue > value_type
Definition hashmap.h:55
HashMap & operator=(const HashMap &hashmap)
Definition hashmap.inl:47
friend void swap(HashMap< UKey, UValue, UHash, UEqual, UAllocator > &hashmap1, HashMap< UKey, UValue, UHash, UEqual, UAllocator > &hashmap2) noexcept
size_t size() const noexcept
Get the hash map size.
Definition hashmap.h:96
reverse_iterator rend() noexcept
Get the reverse end hash map iterator.
Definition hashmap.inl:111
size_t erase(const TKey &key)
Erase the item with the given key from the hash map.
Definition hashmap.inl:208
std::pair< iterator, iterator > equal_range(const TKey &key) noexcept
Find the bounds of a range that includes all the elements in the hash map with the given key.
Definition hashmap.inl:157
iterator begin() noexcept
Get the begin hash map iterator.
Definition hashmap.inl:57
Hash map iterator.
Definition hashmap.h:224
friend void swap(HashMapIterator< UContainer, UKey, UValue > &it1, HashMapIterator< UContainer, UKey, UValue > &it2) noexcept
pointer operator->() noexcept
Definition hashmap.inl:397
HashMapIterator & operator++() noexcept
Definition hashmap.inl:359
reference operator*() noexcept
Definition hashmap.inl:389
Hash map reverse iterator.
Definition hashmap.h:336
reference operator*() noexcept
Definition hashmap.inl:561
HashMapReverseIterator & operator++() noexcept
Definition hashmap.inl:531
pointer operator->() noexcept
Definition hashmap.inl:569
friend void swap(HashMapReverseIterator< UContainer, UKey, UValue > &it1, HashMapReverseIterator< UContainer, UKey, UValue > &it2) noexcept
C++ Common project definitions.
void swap(FileCache &cache1, FileCache &cache2) noexcept
Definition filecache.inl:23