Line data Source code
1 0 : // Distributed under the MIT License.
2 : // See LICENSE.txt for details.
3 :
4 : #pragma once
5 :
6 : #include <array>
7 : #include <cstddef>
8 : #include <iterator>
9 : #include <memory> // std::addressof
10 : #include <optional>
11 : #include <pup.h>
12 : #include <pup_stl.h>
13 : #include <type_traits>
14 :
15 : #include "Utilities/Algorithm.hpp"
16 : #include "Utilities/ConstantExpressions.hpp"
17 : #include "Utilities/ErrorHandling/Assert.hpp"
18 : #include "Utilities/ForceInline.hpp"
19 : #include "Utilities/GetOutput.hpp"
20 : #include "Utilities/Gsl.hpp"
21 : #include "Utilities/Numeric.hpp"
22 : #include "Utilities/PrintHelpers.hpp"
23 : #include "Utilities/Serialization/PupStlCpp17.hpp"
24 : #include "Utilities/TMPL.hpp"
25 : #include "Utilities/TypeTraits.hpp"
26 :
27 : /// \cond
28 : template <size_t MaxSize, class Key, class ValueType, class Hash,
29 : class KeyEqual>
30 : class FixedHashMapIterator;
31 : /// \endcond
32 :
33 : namespace FixedHashMap_detail {
34 : template <typename T, typename = std::void_t<>>
35 : struct has_is_perfect_member : std::false_type {};
36 :
37 : template <typename T>
38 : struct has_is_perfect_member<T,
39 : std::void_t<decltype(T::template is_perfect<0>)>>
40 : : std::true_type {};
41 :
42 : template <typename T>
43 : constexpr bool has_is_perfect_member_v = has_is_perfect_member<T>::value;
44 :
45 : template <class T, size_t MaxSize,
46 : bool HasIsPerfect = has_is_perfect_member_v<T>>
47 : constexpr bool is_perfect = T::template is_perfect<MaxSize>;
48 :
49 : template <class T, size_t MaxSize>
50 : constexpr bool is_perfect<T, MaxSize, false> = false;
51 : } // namespace FixedHashMap_detail
52 :
53 : /*!
54 : * \ingroup DataStructuresGroup
55 : * \brief A hash table with a compile-time specified maximum size and ability to
56 : * efficiently handle perfect hashes.
57 : *
58 : * There are a few requirements on the types passed to `FixedHashMap`. These
59 : * are:
60 : * - `Key` is CopyConstructible for copy and move semantics, as well as
61 : * serialization
62 : * - `ValueType` is MoveConstructible
63 : * - If `Hash` is a perfect hash for some values of `MaxSize` then in order to
64 : * use the perfect hashing improvements `Hash` must have a member variable
65 : * template `is_perfect` that takes as its only template parameter a `size_t`
66 : * equal to `MaxSize`. A perfect hash must map each `Key` to `[0, MaxSize)`
67 : * uniquely.
68 : * - Keys are distinct.
69 : *
70 : * The interface is similar to std::unordered_map, so see the documentation for
71 : * that for details.
72 : *
73 : * #### Implementation Details
74 : *
75 : * - Uses linear probing for non-perfect hashes.
76 : * - The hash `Hash` is assumed to be a perfect hash for `MaxSize` if
77 : * `Hash::template is_perfect<MaxSize>` is true.
78 : */
79 : template <size_t MaxSize, class Key, class ValueType,
80 : class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
81 1 : class FixedHashMap {
82 0 : static constexpr bool hash_is_perfect =
83 : FixedHashMap_detail::is_perfect<Hash, MaxSize>;
84 :
85 : public:
86 0 : using key_type = Key;
87 0 : using mapped_type = ValueType;
88 0 : using value_type = std::pair<const key_type, mapped_type>;
89 0 : using size_type = size_t;
90 0 : using difference_type = ptrdiff_t;
91 0 : using hasher = Hash;
92 0 : using key_equal = KeyEqual;
93 0 : using reference = value_type&;
94 0 : using const_reference = const value_type&;
95 0 : using pointer = value_type*;
96 0 : using const_pointer = const value_type*;
97 0 : using iterator =
98 : FixedHashMapIterator<MaxSize, key_type, value_type, hasher, key_equal>;
99 0 : using const_iterator =
100 : FixedHashMapIterator<MaxSize, key_type, const value_type, hasher,
101 : key_equal>;
102 :
103 0 : FixedHashMap() = default;
104 0 : FixedHashMap(std::initializer_list<value_type> init);
105 0 : FixedHashMap(const FixedHashMap&) = default;
106 0 : FixedHashMap& operator=(const FixedHashMap& other);
107 0 : FixedHashMap(FixedHashMap&&) = default;
108 0 : FixedHashMap& operator=(FixedHashMap&& other);
109 0 : ~FixedHashMap() = default;
110 :
111 0 : iterator begin() { return unconst(cbegin()); }
112 0 : const_iterator begin() const {
113 : return const_iterator(data_.begin(), data_.end());
114 : }
115 0 : const_iterator cbegin() const { return begin(); }
116 :
117 0 : iterator end() { return unconst(cend()); }
118 0 : const_iterator end() const {
119 : return const_iterator(data_.end(), data_.end());
120 : }
121 0 : const_iterator cend() const { return end(); }
122 :
123 0 : bool empty() const { return size_ == 0; }
124 0 : size_t size() const { return size_; }
125 :
126 0 : void clear();
127 :
128 : /// @{
129 : /// Inserts the element if it does not exists.
130 1 : std::pair<iterator, bool> insert(const value_type& value) {
131 : return insert(value_type(value));
132 : }
133 1 : std::pair<iterator, bool> insert(value_type&& value) {
134 : // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast)
135 : return insert_or_assign_impl<false>(const_cast<key_type&&>(value.first),
136 : std::move(value.second));
137 : }
138 : template <typename... Args>
139 1 : std::pair<iterator, bool> emplace(Args&&... args) {
140 : return insert(value_type(std::forward<Args>(args)...));
141 : }
142 : /// @}
143 : /// @{
144 : /// Inserts the element if it does not exists, otherwise assigns to it the new
145 : /// value.
146 : template <class M>
147 1 : std::pair<iterator, bool> insert_or_assign(const key_type& key, M&& obj) {
148 : return insert_or_assign(key_type{key}, std::forward<M>(obj));
149 : }
150 : template <class M>
151 1 : std::pair<iterator, bool> insert_or_assign(key_type&& key, M&& obj) {
152 : return insert_or_assign_impl<true>(std::move(key), std::forward<M>(obj));
153 : }
154 : /// @}
155 :
156 0 : iterator erase(const const_iterator& pos);
157 0 : size_t erase(const key_type& key);
158 :
159 0 : mapped_type& at(const key_type& key);
160 0 : const mapped_type& at(const key_type& key) const;
161 0 : mapped_type& operator[](const key_type& key);
162 :
163 0 : size_t count(const key_type& key) const;
164 0 : iterator find(const key_type& key) {
165 : return unconst(std::as_const(*this).find(key));
166 : }
167 0 : const_iterator find(const key_type& key) const {
168 : auto it = get_data_entry(key);
169 : return it != data_.end() and is_set(*it) ? const_iterator(&*it, data_.end())
170 : : end();
171 : }
172 :
173 : /// Check if `key` is in the map
174 1 : bool contains(const key_type& key) const { return find(key) != end(); }
175 :
176 : /// Get key equal function object
177 1 : key_equal key_eq() const { return key_equal{}; }
178 : /// Get hash function object
179 1 : hasher hash_function() const { return hasher{}; }
180 :
181 : // NOLINTNEXTLINE(google-runtime-references)
182 0 : void pup(PUP::er& p) {
183 : size_t version = 0;
184 : p | version;
185 : // Remember to increment the version number when making changes to this
186 : // function. Retain support for unpacking data written by previous versions
187 : // whenever possible. See `Domain` docs for details.
188 : if (version >= 0) {
189 : p | data_;
190 : p | size_;
191 : }
192 : }
193 :
194 : private:
195 : template <size_t FMaxSize, class FKey, class FValueType, class FHash,
196 : class FKeyEqual>
197 : // NOLINTNEXTLINE(readability-redundant-declaration) false positive
198 0 : friend bool operator==(
199 : const FixedHashMap<FMaxSize, FKey, FValueType, FHash, FKeyEqual>& a,
200 : const FixedHashMap<FMaxSize, FKey, FValueType, FHash, FKeyEqual>& b);
201 :
202 : template <bool Assign, class M>
203 0 : std::pair<iterator, bool> insert_or_assign_impl(key_type&& key, M&& obj);
204 :
205 0 : using storage_type = std::array<std::optional<value_type>, MaxSize>;
206 :
207 0 : SPECTRE_ALWAYS_INLINE size_type hash(const key_type& key) const {
208 : if constexpr (hash_is_perfect) {
209 : return Hash{}(key);
210 : } else {
211 : return Hash{}(key) % MaxSize;
212 : }
213 : }
214 :
215 : template <bool IsInserting>
216 0 : typename storage_type::iterator get_data_entry(const Key& key);
217 :
218 0 : typename storage_type::const_iterator get_data_entry(const Key& key) const {
219 : // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast)
220 : return const_cast<FixedHashMap&>(*this).get_data_entry<false>(key);
221 : }
222 :
223 0 : iterator unconst(const const_iterator& it) {
224 : return iterator(&it.get_optional() - data_.begin() + data_.begin(),
225 : data_.end());
226 : }
227 :
228 0 : SPECTRE_ALWAYS_INLINE static bool is_set(
229 : const std::optional<value_type>& opt) {
230 : return static_cast<bool>(opt);
231 : }
232 :
233 0 : storage_type data_{};
234 0 : size_t size_ = 0;
235 : };
236 :
237 : /// \cond HIDDEN_SYMBOLS
238 : template <size_t MaxSize, class Key, class ValueType, class Hash,
239 : class KeyEqual>
240 : class FixedHashMapIterator {
241 : public:
242 : using iterator_category = std::forward_iterator_tag;
243 : using value_type = std::remove_const_t<ValueType>;
244 : using difference_type = ptrdiff_t;
245 : using pointer = ValueType*;
246 : using reference = ValueType&;
247 :
248 : FixedHashMapIterator() = default;
249 :
250 : /// Implicit conversion from mutable to const iterator.
251 : // NOLINTNEXTLINE(google-explicit-constructor)
252 : operator FixedHashMapIterator<MaxSize, Key, const ValueType, Hash, KeyEqual>()
253 : const {
254 : return {entry_, end_};
255 : }
256 :
257 : reference operator*() const {
258 : ASSERT(entry_ != nullptr, "Invalid FixedHashMapIterator");
259 : ASSERT(is_set(*entry_),
260 : "FixedHashMapIterator points to an invalid value in the map.");
261 : // deference pointer, then dereference std::optional
262 : return entry_->value();
263 : }
264 : pointer operator->() const {
265 : ASSERT(entry_ != nullptr, "Invalid FixedHashMapIterator");
266 : ASSERT(is_set(*entry_),
267 : "FixedHashMapIterator points to an invalid value in the map.");
268 : return std::addressof(entry_->value());
269 : }
270 :
271 : FixedHashMapIterator& operator++();
272 : FixedHashMapIterator operator++(int);
273 :
274 : private:
275 : friend class FixedHashMap<MaxSize, Key, typename value_type::second_type,
276 : Hash, KeyEqual>;
277 : friend class FixedHashMapIterator<MaxSize, Key, value_type, Hash, KeyEqual>;
278 :
279 : friend bool operator==(const FixedHashMapIterator& a,
280 : const FixedHashMapIterator& b) {
281 : return a.entry_ == b.entry_;
282 : }
283 : friend bool operator<(const FixedHashMapIterator& a,
284 : const FixedHashMapIterator& b) {
285 : return a.entry_ < b.entry_;
286 : }
287 :
288 : // The rest of the comparison operators don't need access to the
289 : // class internals, but they need to be instantiated for each
290 : // instantiation of the class.
291 : friend bool operator!=(const FixedHashMapIterator& a,
292 : const FixedHashMapIterator& b) {
293 : return not(a == b);
294 : }
295 : friend bool operator>(const FixedHashMapIterator& a,
296 : const FixedHashMapIterator& b) {
297 : return b < a;
298 : }
299 : friend bool operator<=(const FixedHashMapIterator& a,
300 : const FixedHashMapIterator& b) {
301 : return not(b < a);
302 : }
303 : friend bool operator>=(const FixedHashMapIterator& a,
304 : const FixedHashMapIterator& b) {
305 : return not(a < b);
306 : }
307 :
308 : using map_optional_type = std::optional<std::remove_const_t<ValueType>>;
309 : using optional_type =
310 : tmpl::conditional_t<std::is_const<ValueType>::value,
311 : const map_optional_type, map_optional_type>;
312 :
313 : SPECTRE_ALWAYS_INLINE static bool is_set(const optional_type& opt) {
314 : return static_cast<bool>(opt);
315 : }
316 :
317 : FixedHashMapIterator(optional_type* const entry, optional_type* const end)
318 : : entry_(entry), end_(end) {
319 : if (entry_ != end_ and not*entry_) {
320 : operator++();
321 : }
322 : }
323 :
324 : optional_type& get_optional() const { return *entry_; }
325 :
326 : optional_type* entry_{nullptr};
327 : optional_type* end_{nullptr};
328 : };
329 :
330 : template <size_t MaxSize, class Key, class ValueType, class Hash,
331 : class KeyEqual>
332 : FixedHashMapIterator<MaxSize, Key, ValueType, Hash, KeyEqual>&
333 : FixedHashMapIterator<MaxSize, Key, ValueType, Hash, KeyEqual>::operator++() {
334 : ASSERT(entry_ != end_,
335 : "Tried to increment an end iterator, which is undefined behavior.");
336 : // Move to next element, which might not be the next element in the std::array
337 : do {
338 : ++entry_; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic)
339 : } while (entry_ < end_ and not is_set(*entry_));
340 : return *this;
341 : }
342 :
343 : template <size_t MaxSize, class Key, class ValueType, class Hash,
344 : class KeyEqual>
345 : FixedHashMapIterator<MaxSize, Key, ValueType, Hash, KeyEqual>
346 : FixedHashMapIterator<MaxSize, Key, ValueType, Hash, KeyEqual>::operator++(int) {
347 : const auto ret = *this;
348 : operator++();
349 : return ret;
350 : }
351 : /// \endcond
352 :
353 : template <size_t MaxSize, class Key, class ValueType, class Hash,
354 : class KeyEqual>
355 : FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>&
356 : FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::operator=(
357 : const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& other) {
358 : if (this == &other) {
359 : return *this;
360 : }
361 : clear();
362 : size_ = other.size_;
363 : for (size_t i = 0; i < data_.size(); ++i) {
364 : const auto& other_optional = gsl::at(other.data_, i);
365 : if (is_set(other_optional)) {
366 : // The std::optionals cannot be assigned to because they
367 : // contain the map keys, which are const, so we have to replace
368 : // the contents instead, since that counts as a destroy +
369 : // initialize.
370 : gsl::at(data_, i).emplace(*other_optional);
371 : }
372 : }
373 : return *this;
374 : }
375 :
376 : template <size_t MaxSize, class Key, class ValueType, class Hash,
377 : class KeyEqual>
378 : FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>&
379 : FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::operator=(
380 : FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>&& other) {
381 : if (this == &other) {
382 : return *this;
383 : }
384 : clear();
385 : size_ = other.size_;
386 : for (size_t i = 0; i < data_.size(); ++i) {
387 : auto& other_optional = gsl::at(other.data_, i);
388 : if (is_set(other_optional)) {
389 : // The std::optionals cannot be assigned to because they
390 : // contain the map keys, which are const, so we have to replace
391 : // the contents instead, since that counts as a destroy +
392 : // initialize.
393 : gsl::at(data_, i).emplace(std::move(*other_optional));
394 : }
395 : }
396 : return *this;
397 : }
398 :
399 : template <size_t MaxSize, class Key, class ValueType, class Hash,
400 : class KeyEqual>
401 : FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::FixedHashMap(
402 : std::initializer_list<value_type> init) {
403 : // size_ is set by calling insert
404 : for (const auto& entry : init) {
405 : insert(entry);
406 : }
407 : }
408 :
409 : template <size_t MaxSize, class Key, class ValueType, class Hash,
410 : class KeyEqual>
411 : void FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::clear() {
412 : for (auto& entry : data_) {
413 : entry.reset();
414 : }
415 : size_ = 0;
416 : }
417 :
418 : template <size_t MaxSize, class Key, class ValueType, class Hash,
419 : class KeyEqual>
420 : template <bool Assign, class M>
421 : auto FixedHashMap<MaxSize, Key, ValueType, Hash,
422 0 : KeyEqual>::insert_or_assign_impl(key_type&& key, M&& obj)
423 : -> std::pair<iterator, bool> {
424 : auto data_it = get_data_entry<true>(key);
425 : if (UNLIKELY(data_it == data_.end())) {
426 : ERROR("Unable to insert element into FixedHashMap of maximum size "
427 : << MaxSize << " because it is full. If the current size (" << size_
428 : << ") is not equal to the maximum size then please file an issue "
429 : "with the code you used to produce this error. "
430 : << (hash_is_perfect ? " If a perfect hash is used and it hashes to "
431 : "past the last element stored, then this "
432 : "error may also be triggered."
433 : : ""));
434 : }
435 : // data_it points to either the existing element or a new bucket to place the
436 : // element.
437 : const auto is_new_entry = not is_set(*data_it);
438 : if (is_new_entry or Assign) {
439 : if (is_new_entry) {
440 : ++size_;
441 : }
442 : data_it->emplace(std::move(key), std::forward<M>(obj));
443 : }
444 : return std::make_pair(iterator{data_it, data_.end()}, is_new_entry);
445 : }
446 :
447 : template <size_t MaxSize, class Key, class ValueType, class Hash,
448 : class KeyEqual>
449 : auto FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::erase(
450 : const const_iterator& pos) -> iterator {
451 : auto next_it = &(unconst(pos).get_optional());
452 : --size_;
453 : next_it->reset();
454 : // pos now points to an unset entry, advance to next valid one
455 : do {
456 : ++next_it;
457 : if (next_it == data_.end()) {
458 : next_it = data_.begin();
459 : }
460 : if (is_set(*next_it)) {
461 : return {next_it, data_.end()};
462 : }
463 : } while (next_it != &pos.get_optional());
464 : return end();
465 : }
466 :
467 : template <size_t MaxSize, class Key, class ValueType, class Hash,
468 : class KeyEqual>
469 : size_t FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::erase(
470 : const key_type& key) {
471 : auto it = get_data_entry<false>(key);
472 : if (it == data_.end() or not is_set(*it)) {
473 : return 0;
474 : }
475 : it->reset();
476 : --size_;
477 : return 1;
478 : }
479 :
480 : template <size_t MaxSize, class Key, class ValueType, class Hash,
481 : class KeyEqual>
482 : auto FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::at(
483 : const key_type& key) -> mapped_type& {
484 : auto it = get_data_entry<false>(key);
485 : if (it == data_.end() or not is_set(*it)) {
486 : throw std::out_of_range(get_output(key) + " not in FixedHashMap");
487 : }
488 : return it->value().second;
489 : }
490 :
491 : template <size_t MaxSize, class Key, class ValueType, class Hash,
492 : class KeyEqual>
493 : auto FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::at(
494 : const key_type& key) const -> const mapped_type& {
495 : // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast)
496 : return const_cast<FixedHashMap&>(*this).at(key);
497 : }
498 :
499 : template <size_t MaxSize, class Key, class ValueType, class Hash,
500 : class KeyEqual>
501 : auto FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::operator[](
502 : const key_type& key) -> mapped_type& {
503 : auto it = get_data_entry<true>(key);
504 : if (it == data_.end()) {
505 : ERROR("Unable to insert element into FixedHashMap of maximum size "
506 : << MaxSize << " because it is full. If the current size (" << size_
507 : << ") is not equal to the maximum size then please file an issue "
508 : "with the code you used to produce this error. "
509 : << (hash_is_perfect ? " If a perfect hash is used and it hashes to "
510 : "past the last element stored, then this "
511 : "error may also be triggered."
512 : : ""));
513 : }
514 : if (not is_set(*it)) {
515 : ++size_;
516 : it->emplace(key, mapped_type{});
517 : }
518 : return it->value().second;
519 : }
520 :
521 : template <size_t MaxSize, class Key, class ValueType, class Hash,
522 : class KeyEqual>
523 : size_t FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::count(
524 : const key_type& key) const {
525 : const auto it = get_data_entry(key);
526 : return it == data_.end() or not is_set(*it) ? 0 : 1;
527 : }
528 :
529 : template <size_t MaxSize, class Key, class ValueType, class Hash,
530 : class KeyEqual>
531 : template <bool IsInserting>
532 0 : auto FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::get_data_entry(
533 : const Key& key) -> typename storage_type::iterator {
534 : const auto hashed_key = hash(key);
535 : auto it = data_.begin() + hashed_key;
536 : if constexpr (not hash_is_perfect) {
537 : // First search for an existing key.
538 : while (not is_set(*it) or it->value().first != key) {
539 : if (++it == data_.end()) {
540 : it = data_.begin();
541 : }
542 : if (UNLIKELY(it == data_.begin() + hashed_key)) {
543 : // not found, return end iterator to storage_type
544 : it = data_.end();
545 : break;
546 : }
547 : }
548 : // If we are inserting an element but couldn't find an existing key, then
549 : // find the first available bucket.
550 : if (IsInserting and it == data_.end()) {
551 : it = data_.begin() + hashed_key;
552 : while (is_set(*it)) {
553 : if (++it == data_.end()) {
554 : it = data_.begin();
555 : }
556 : if (UNLIKELY(it == data_.begin() + hashed_key)) {
557 : // could not find any open bucket
558 : return data_.end();
559 : }
560 : }
561 : }
562 : }
563 : return it;
564 : }
565 :
566 : template <size_t MaxSize, class Key, class ValueType, class Hash,
567 : class KeyEqual>
568 0 : bool operator==(
569 : const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& a,
570 : const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& b) {
571 : if (a.size_ != b.size_) {
572 : return false;
573 : }
574 : for (const auto& [key, value] : a) {
575 : const auto found_in_b = b.find(key);
576 : if (found_in_b == b.end() or found_in_b->second != value) {
577 : return false;
578 : }
579 : }
580 : return true;
581 : }
582 :
583 : template <size_t MaxSize, class Key, class ValueType, class Hash,
584 : class KeyEqual>
585 0 : bool operator!=(
586 : const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& a,
587 : const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& b) {
588 : return not(a == b);
589 : }
590 :
591 : template <size_t MaxSize, class Key, class ValueType, class Hash,
592 : class KeyEqual>
593 0 : std::ostream& operator<<(
594 : std::ostream& os,
595 : const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& m) {
596 : unordered_print_helper(
597 : os, std::begin(m), std::end(m),
598 : [](std::ostream& out,
599 : typename FixedHashMap<MaxSize, Key, ValueType, Hash,
600 : KeyEqual>::const_iterator it) {
601 : out << "[" << it->first << "," << it->second << "]";
602 : });
603 : return os;
604 : }
|
