1 // This is free and unencumbered software released into the public domain.
3 // Anyone is free to copy, modify, publish, use, compile, sell, or
4 // distribute this software, either in source code form or as a compiled
5 // binary, for any purpose, commercial or non-commercial, and by any
8 // -------------------------------------------------------
9 // Written by Clifford Wolf <clifford@clifford.at> in 2014
10 // -------------------------------------------------------
22 const int hashtable_size_trigger
= 2;
23 const int hashtable_size_factor
= 3;
25 // The XOR version of DJB2
26 inline unsigned int mkhash(unsigned int a
, unsigned int b
) {
27 return ((a
<< 5) + a
) ^ b
;
30 // traditionally 5381 is used as starting value for the djb2 hash
31 const unsigned int mkhash_init
= 5381;
33 // The ADD version of DJB2
34 // (use this version for cache locality in b)
35 inline unsigned int mkhash_add(unsigned int a
, unsigned int b
) {
36 return ((a
<< 5) + a
) + b
;
39 inline unsigned int mkhash_xorshift(unsigned int a
) {
44 } else if (sizeof(a
) == 8) {
49 throw std::runtime_error("mkhash_xorshift() only implemented for 32 bit and 64 bit ints");
53 template<typename T
> struct hash_ops
{
54 static inline bool cmp(const T
&a
, const T
&b
) {
57 static inline unsigned int hash(const T
&a
) {
64 static inline bool cmp(T a
, T b
) {
69 template<> struct hash_ops
<int32_t> : hash_int_ops
71 static inline unsigned int hash(int32_t a
) {
75 template<> struct hash_ops
<int64_t> : hash_int_ops
77 static inline unsigned int hash(int64_t a
) {
78 return mkhash((unsigned int)(a
), (unsigned int)(a
>> 32));
82 template<> struct hash_ops
<std::string
> {
83 static inline bool cmp(const std::string
&a
, const std::string
&b
) {
86 static inline unsigned int hash(const std::string
&a
) {
94 template<typename P
, typename Q
> struct hash_ops
<std::pair
<P
, Q
>> {
95 static inline bool cmp(std::pair
<P
, Q
> a
, std::pair
<P
, Q
> b
) {
98 static inline unsigned int hash(std::pair
<P
, Q
> a
) {
99 return mkhash(hash_ops
<P
>::hash(a
.first
), hash_ops
<Q
>::hash(a
.second
));
103 template<typename
... T
> struct hash_ops
<std::tuple
<T
...>> {
104 static inline bool cmp(std::tuple
<T
...> a
, std::tuple
<T
...> b
) {
107 template<size_t I
= 0>
108 static inline typename
std::enable_if
<I
== sizeof...(T
), unsigned int>::type
hash(std::tuple
<T
...>) {
111 template<size_t I
= 0>
112 static inline typename
std::enable_if
<I
!= sizeof...(T
), unsigned int>::type
hash(std::tuple
<T
...> a
) {
113 typedef hash_ops
<typename
std::tuple_element
<I
, std::tuple
<T
...>>::type
> element_ops_t
;
114 return mkhash(hash
<I
+1>(a
), element_ops_t::hash(std::get
<I
>(a
)));
118 template<typename T
> struct hash_ops
<std::vector
<T
>> {
119 static inline bool cmp(std::vector
<T
> a
, std::vector
<T
> b
) {
122 static inline unsigned int hash(std::vector
<T
> a
) {
123 unsigned int h
= mkhash_init
;
125 h
= mkhash(h
, hash_ops
<T
>::hash(k
));
130 struct hash_cstr_ops
{
131 static inline bool cmp(const char *a
, const char *b
) {
132 for (int i
= 0; a
[i
] || b
[i
]; i
++)
137 static inline unsigned int hash(const char *a
) {
138 unsigned int hash
= mkhash_init
;
140 hash
= mkhash(hash
, *(a
++));
145 struct hash_ptr_ops
{
146 static inline bool cmp(const void *a
, const void *b
) {
149 static inline unsigned int hash(const void *a
) {
154 struct hash_obj_ops
{
155 static inline bool cmp(const void *a
, const void *b
) {
159 static inline unsigned int hash(const T
*a
) {
160 return a
? a
->hash() : 0;
165 inline unsigned int mkhash(const T
&v
) {
166 return hash_ops
<T
>().hash(v
);
169 inline int hashtable_size(int min_size
)
171 static std::vector
<int> zero_and_some_primes
= {
172 0, 23, 29, 37, 47, 59, 79, 101, 127, 163, 211, 269, 337, 431, 541, 677,
173 853, 1069, 1361, 1709, 2137, 2677, 3347, 4201, 5261, 6577, 8231, 10289,
174 12889, 16127, 20161, 25219, 31531, 39419, 49277, 61603, 77017, 96281,
175 120371, 150473, 188107, 235159, 293957, 367453, 459317, 574157, 717697,
176 897133, 1121423, 1401791, 1752239, 2190299, 2737937, 3422429, 4278037,
177 5347553, 6684443, 8355563, 10444457, 13055587, 16319519, 20399411,
178 25499291, 31874149, 39842687, 49803361, 62254207, 77817767, 97272239,
179 121590311, 151987889, 189984863, 237481091, 296851369, 371064217
182 for (auto p
: zero_and_some_primes
)
183 if (p
>= min_size
) return p
;
185 if (sizeof(int) == 4)
186 throw std::length_error("hash table exceeded maximum size. use a ILP64 abi for larger tables.");
188 for (auto p
: zero_and_some_primes
)
189 if (100129 * p
> min_size
) return 100129 * p
;
191 throw std::length_error("hash table exceeded maximum size.");
194 template<typename K
, typename T
, typename OPS
= hash_ops
<K
>> class dict
;
195 template<typename K
, int offset
= 0, typename OPS
= hash_ops
<K
>> class idict
;
196 template<typename K
, typename OPS
= hash_ops
<K
>> class pool
;
197 template<typename K
, typename OPS
= hash_ops
<K
>> class mfp
;
199 template<typename K
, typename T
, typename OPS
>
204 std::pair
<K
, T
> udata
;
208 entry_t(const std::pair
<K
, T
> &udata
, int next
) : udata(udata
), next(next
) { }
209 entry_t(std::pair
<K
, T
> &&udata
, int next
) : udata(std::move(udata
)), next(next
) { }
212 std::vector
<int> hashtable
;
213 std::vector
<entry_t
> entries
;
217 static inline void do_assert(bool) { }
219 static inline void do_assert(bool cond
) {
220 if (!cond
) throw std::runtime_error("dict<> assert failed.");
224 int do_hash(const K
&key
) const
226 unsigned int hash
= 0;
227 if (!hashtable
.empty())
228 hash
= ops
.hash(key
) % (unsigned int)(hashtable
.size());
235 hashtable
.resize(hashtable_size(entries
.capacity() * hashtable_size_factor
), -1);
237 for (int i
= 0; i
< int(entries
.size()); i
++) {
238 do_assert(-1 <= entries
[i
].next
&& entries
[i
].next
< int(entries
.size()));
239 int hash
= do_hash(entries
[i
].udata
.first
);
240 entries
[i
].next
= hashtable
[hash
];
245 int do_erase(int index
, int hash
)
247 do_assert(index
< int(entries
.size()));
248 if (hashtable
.empty() || index
< 0)
251 int k
= hashtable
[hash
];
252 do_assert(0 <= k
&& k
< int(entries
.size()));
255 hashtable
[hash
] = entries
[index
].next
;
257 while (entries
[k
].next
!= index
) {
259 do_assert(0 <= k
&& k
< int(entries
.size()));
261 entries
[k
].next
= entries
[index
].next
;
264 int back_idx
= entries
.size()-1;
266 if (index
!= back_idx
)
268 int back_hash
= do_hash(entries
[back_idx
].udata
.first
);
270 k
= hashtable
[back_hash
];
271 do_assert(0 <= k
&& k
< int(entries
.size()));
274 hashtable
[back_hash
] = index
;
276 while (entries
[k
].next
!= back_idx
) {
278 do_assert(0 <= k
&& k
< int(entries
.size()));
280 entries
[k
].next
= index
;
283 entries
[index
] = std::move(entries
[back_idx
]);
294 int do_lookup(const K
&key
, int &hash
) const
296 if (hashtable
.empty())
299 if (entries
.size() * hashtable_size_trigger
> hashtable
.size()) {
300 ((dict
*)this)->do_rehash();
304 int index
= hashtable
[hash
];
306 while (index
>= 0 && !ops
.cmp(entries
[index
].udata
.first
, key
)) {
307 index
= entries
[index
].next
;
308 do_assert(-1 <= index
&& index
< int(entries
.size()));
314 int do_insert(const K
&key
, int &hash
)
316 if (hashtable
.empty()) {
317 entries
.push_back(entry_t(std::pair
<K
, T
>(key
, T()), -1));
321 entries
.push_back(entry_t(std::pair
<K
, T
>(key
, T()), hashtable
[hash
]));
322 hashtable
[hash
] = entries
.size() - 1;
324 return entries
.size() - 1;
327 int do_insert(const std::pair
<K
, T
> &value
, int &hash
)
329 if (hashtable
.empty()) {
330 entries
.push_back(entry_t(value
, -1));
332 hash
= do_hash(value
.first
);
334 entries
.push_back(entry_t(value
, hashtable
[hash
]));
335 hashtable
[hash
] = entries
.size() - 1;
337 return entries
.size() - 1;
341 class const_iterator
: public std::iterator
<std::forward_iterator_tag
, std::pair
<K
, T
>>
347 const_iterator(const dict
*ptr
, int index
) : ptr(ptr
), index(index
) { }
350 const_iterator
operator++() { index
--; return *this; }
351 bool operator<(const const_iterator
&other
) const { return index
> other
.index
; }
352 bool operator==(const const_iterator
&other
) const { return index
== other
.index
; }
353 bool operator!=(const const_iterator
&other
) const { return index
!= other
.index
; }
354 const std::pair
<K
, T
> &operator*() const { return ptr
->entries
[index
].udata
; }
355 const std::pair
<K
, T
> *operator->() const { return &ptr
->entries
[index
].udata
; }
358 class iterator
: public std::iterator
<std::forward_iterator_tag
, std::pair
<K
, T
>>
364 iterator(dict
*ptr
, int index
) : ptr(ptr
), index(index
) { }
367 iterator
operator++() { index
--; return *this; }
368 bool operator<(const iterator
&other
) const { return index
> other
.index
; }
369 bool operator==(const iterator
&other
) const { return index
== other
.index
; }
370 bool operator!=(const iterator
&other
) const { return index
!= other
.index
; }
371 std::pair
<K
, T
> &operator*() { return ptr
->entries
[index
].udata
; }
372 std::pair
<K
, T
> *operator->() { return &ptr
->entries
[index
].udata
; }
373 const std::pair
<K
, T
> &operator*() const { return ptr
->entries
[index
].udata
; }
374 const std::pair
<K
, T
> *operator->() const { return &ptr
->entries
[index
].udata
; }
375 operator const_iterator() const { return const_iterator(ptr
, index
); }
382 dict(const dict
&other
)
384 entries
= other
.entries
;
393 dict
&operator=(const dict
&other
) {
394 entries
= other
.entries
;
399 dict
&operator=(dict
&&other
) {
405 dict(const std::initializer_list
<std::pair
<K
, T
>> &list
)
407 for (auto &it
: list
)
411 template<class InputIterator
>
412 dict(InputIterator first
, InputIterator last
)
417 template<class InputIterator
>
418 void insert(InputIterator first
, InputIterator last
)
420 for (; first
!= last
; ++first
)
424 std::pair
<iterator
, bool> insert(const K
&key
)
426 int hash
= do_hash(key
);
427 int i
= do_lookup(key
, hash
);
429 return std::pair
<iterator
, bool>(iterator(this, i
), false);
430 i
= do_insert(key
, hash
);
431 return std::pair
<iterator
, bool>(iterator(this, i
), true);
434 std::pair
<iterator
, bool> insert(const std::pair
<K
, T
> &value
)
436 int hash
= do_hash(value
.first
);
437 int i
= do_lookup(value
.first
, hash
);
439 return std::pair
<iterator
, bool>(iterator(this, i
), false);
440 i
= do_insert(value
, hash
);
441 return std::pair
<iterator
, bool>(iterator(this, i
), true);
444 int erase(const K
&key
)
446 int hash
= do_hash(key
);
447 int index
= do_lookup(key
, hash
);
448 return do_erase(index
, hash
);
451 iterator
erase(iterator it
)
453 int hash
= do_hash(it
->first
);
454 do_erase(it
.index
, hash
);
458 int count(const K
&key
) const
460 int hash
= do_hash(key
);
461 int i
= do_lookup(key
, hash
);
462 return i
< 0 ? 0 : 1;
465 int count(const K
&key
, const_iterator it
) const
467 int hash
= do_hash(key
);
468 int i
= do_lookup(key
, hash
);
469 return i
< 0 || i
> it
.index
? 0 : 1;
472 iterator
find(const K
&key
)
474 int hash
= do_hash(key
);
475 int i
= do_lookup(key
, hash
);
478 return iterator(this, i
);
481 const_iterator
find(const K
&key
) const
483 int hash
= do_hash(key
);
484 int i
= do_lookup(key
, hash
);
487 return const_iterator(this, i
);
492 int hash
= do_hash(key
);
493 int i
= do_lookup(key
, hash
);
495 throw std::out_of_range("dict::at()");
496 return entries
[i
].udata
.second
;
499 const T
& at(const K
&key
) const
501 int hash
= do_hash(key
);
502 int i
= do_lookup(key
, hash
);
504 throw std::out_of_range("dict::at()");
505 return entries
[i
].udata
.second
;
508 T
at(const K
&key
, const T
&defval
) const
510 int hash
= do_hash(key
);
511 int i
= do_lookup(key
, hash
);
514 return entries
[i
].udata
.second
;
517 T
& operator[](const K
&key
)
519 int hash
= do_hash(key
);
520 int i
= do_lookup(key
, hash
);
522 i
= do_insert(std::pair
<K
, T
>(key
, T()), hash
);
523 return entries
[i
].udata
.second
;
526 template<typename Compare
= std::less
<K
>>
527 void sort(Compare comp
= Compare())
529 std::sort(entries
.begin(), entries
.end(), [comp
](const entry_t
&a
, const entry_t
&b
){ return comp(b
.udata
.first
, a
.udata
.first
); });
533 void swap(dict
&other
)
535 hashtable
.swap(other
.hashtable
);
536 entries
.swap(other
.entries
);
539 bool operator==(const dict
&other
) const {
540 if (size() != other
.size())
542 for (auto &it
: entries
) {
543 auto oit
= other
.find(it
.udata
.first
);
544 if (oit
== other
.end() || !(oit
->second
== it
.udata
.second
))
550 bool operator!=(const dict
&other
) const {
551 return !operator==(other
);
554 void reserve(size_t n
) { entries
.reserve(n
); }
555 size_t size() const { return entries
.size(); }
556 bool empty() const { return entries
.empty(); }
557 void clear() { hashtable
.clear(); entries
.clear(); }
559 iterator
begin() { return iterator(this, int(entries
.size())-1); }
560 iterator
end() { return iterator(nullptr, -1); }
562 const_iterator
begin() const { return const_iterator(this, int(entries
.size())-1); }
563 const_iterator
end() const { return const_iterator(nullptr, -1); }
566 template<typename K
, typename OPS
>
569 template<typename
, int, typename
> friend class idict
;
578 entry_t(const K
&udata
, int next
) : udata(udata
), next(next
) { }
581 std::vector
<int> hashtable
;
582 std::vector
<entry_t
> entries
;
586 static inline void do_assert(bool) { }
588 static inline void do_assert(bool cond
) {
589 if (!cond
) throw std::runtime_error("pool<> assert failed.");
593 int do_hash(const K
&key
) const
595 unsigned int hash
= 0;
596 if (!hashtable
.empty())
597 hash
= ops
.hash(key
) % (unsigned int)(hashtable
.size());
604 hashtable
.resize(hashtable_size(entries
.capacity() * hashtable_size_factor
), -1);
606 for (int i
= 0; i
< int(entries
.size()); i
++) {
607 do_assert(-1 <= entries
[i
].next
&& entries
[i
].next
< int(entries
.size()));
608 int hash
= do_hash(entries
[i
].udata
);
609 entries
[i
].next
= hashtable
[hash
];
614 int do_erase(int index
, int hash
)
616 do_assert(index
< int(entries
.size()));
617 if (hashtable
.empty() || index
< 0)
620 int k
= hashtable
[hash
];
622 hashtable
[hash
] = entries
[index
].next
;
624 while (entries
[k
].next
!= index
) {
626 do_assert(0 <= k
&& k
< int(entries
.size()));
628 entries
[k
].next
= entries
[index
].next
;
631 int back_idx
= entries
.size()-1;
633 if (index
!= back_idx
)
635 int back_hash
= do_hash(entries
[back_idx
].udata
);
637 k
= hashtable
[back_hash
];
639 hashtable
[back_hash
] = index
;
641 while (entries
[k
].next
!= back_idx
) {
643 do_assert(0 <= k
&& k
< int(entries
.size()));
645 entries
[k
].next
= index
;
648 entries
[index
] = std::move(entries
[back_idx
]);
659 int do_lookup(const K
&key
, int &hash
) const
661 if (hashtable
.empty())
664 if (entries
.size() * hashtable_size_trigger
> hashtable
.size()) {
665 ((pool
*)this)->do_rehash();
669 int index
= hashtable
[hash
];
671 while (index
>= 0 && !ops
.cmp(entries
[index
].udata
, key
)) {
672 index
= entries
[index
].next
;
673 do_assert(-1 <= index
&& index
< int(entries
.size()));
679 int do_insert(const K
&value
, int &hash
)
681 if (hashtable
.empty()) {
682 entries
.push_back(entry_t(value
, -1));
684 hash
= do_hash(value
);
686 entries
.push_back(entry_t(value
, hashtable
[hash
]));
687 hashtable
[hash
] = entries
.size() - 1;
689 return entries
.size() - 1;
693 class const_iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
699 const_iterator(const pool
*ptr
, int index
) : ptr(ptr
), index(index
) { }
702 const_iterator
operator++() { index
--; return *this; }
703 bool operator==(const const_iterator
&other
) const { return index
== other
.index
; }
704 bool operator!=(const const_iterator
&other
) const { return index
!= other
.index
; }
705 const K
&operator*() const { return ptr
->entries
[index
].udata
; }
706 const K
*operator->() const { return &ptr
->entries
[index
].udata
; }
709 class iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
715 iterator(pool
*ptr
, int index
) : ptr(ptr
), index(index
) { }
718 iterator
operator++() { index
--; return *this; }
719 bool operator==(const iterator
&other
) const { return index
== other
.index
; }
720 bool operator!=(const iterator
&other
) const { return index
!= other
.index
; }
721 K
&operator*() { return ptr
->entries
[index
].udata
; }
722 K
*operator->() { return &ptr
->entries
[index
].udata
; }
723 const K
&operator*() const { return ptr
->entries
[index
].udata
; }
724 const K
*operator->() const { return &ptr
->entries
[index
].udata
; }
725 operator const_iterator() const { return const_iterator(ptr
, index
); }
732 pool(const pool
&other
)
734 entries
= other
.entries
;
743 pool
&operator=(const pool
&other
) {
744 entries
= other
.entries
;
749 pool
&operator=(pool
&&other
) {
755 pool(const std::initializer_list
<K
> &list
)
757 for (auto &it
: list
)
761 template<class InputIterator
>
762 pool(InputIterator first
, InputIterator last
)
767 template<class InputIterator
>
768 void insert(InputIterator first
, InputIterator last
)
770 for (; first
!= last
; ++first
)
774 std::pair
<iterator
, bool> insert(const K
&value
)
776 int hash
= do_hash(value
);
777 int i
= do_lookup(value
, hash
);
779 return std::pair
<iterator
, bool>(iterator(this, i
), false);
780 i
= do_insert(value
, hash
);
781 return std::pair
<iterator
, bool>(iterator(this, i
), true);
784 int erase(const K
&key
)
786 int hash
= do_hash(key
);
787 int index
= do_lookup(key
, hash
);
788 return do_erase(index
, hash
);
791 iterator
erase(iterator it
)
793 int hash
= do_hash(*it
);
794 do_erase(it
.index
, hash
);
798 int count(const K
&key
) const
800 int hash
= do_hash(key
);
801 int i
= do_lookup(key
, hash
);
802 return i
< 0 ? 0 : 1;
805 int count(const K
&key
, const_iterator it
) const
807 int hash
= do_hash(key
);
808 int i
= do_lookup(key
, hash
);
809 return i
< 0 || i
> it
.index
? 0 : 1;
812 iterator
find(const K
&key
)
814 int hash
= do_hash(key
);
815 int i
= do_lookup(key
, hash
);
818 return iterator(this, i
);
821 const_iterator
find(const K
&key
) const
823 int hash
= do_hash(key
);
824 int i
= do_lookup(key
, hash
);
827 return const_iterator(this, i
);
830 bool operator[](const K
&key
)
832 int hash
= do_hash(key
);
833 int i
= do_lookup(key
, hash
);
837 template<typename Compare
= std::less
<K
>>
838 void sort(Compare comp
= Compare())
840 std::sort(entries
.begin(), entries
.end(), [comp
](const entry_t
&a
, const entry_t
&b
){ return comp(b
.udata
, a
.udata
); });
846 iterator it
= begin();
852 void swap(pool
&other
)
854 hashtable
.swap(other
.hashtable
);
855 entries
.swap(other
.entries
);
858 bool operator==(const pool
&other
) const {
859 if (size() != other
.size())
861 for (auto &it
: entries
)
862 if (!other
.count(it
.udata
))
867 bool operator!=(const pool
&other
) const {
868 return !operator==(other
);
871 void reserve(size_t n
) { entries
.reserve(n
); }
872 size_t size() const { return entries
.size(); }
873 bool empty() const { return entries
.empty(); }
874 void clear() { hashtable
.clear(); entries
.clear(); }
876 iterator
begin() { return iterator(this, int(entries
.size())-1); }
877 iterator
end() { return iterator(nullptr, -1); }
879 const_iterator
begin() const { return const_iterator(this, int(entries
.size())-1); }
880 const_iterator
end() const { return const_iterator(nullptr, -1); }
883 template<typename K
, int offset
, typename OPS
>
886 pool
<K
, OPS
> database
;
889 typedef typename pool
<K
, OPS
>::const_iterator const_iterator
;
891 int operator()(const K
&key
)
893 int hash
= database
.do_hash(key
);
894 int i
= database
.do_lookup(key
, hash
);
896 i
= database
.do_insert(key
, hash
);
900 int at(const K
&key
) const
902 int hash
= database
.do_hash(key
);
903 int i
= database
.do_lookup(key
, hash
);
905 throw std::out_of_range("idict::at()");
909 int at(const K
&key
, int defval
) const
911 int hash
= database
.do_hash(key
);
912 int i
= database
.do_lookup(key
, hash
);
918 int count(const K
&key
) const
920 int hash
= database
.do_hash(key
);
921 int i
= database
.do_lookup(key
, hash
);
922 return i
< 0 ? 0 : 1;
925 void expect(const K
&key
, int i
)
927 int j
= (*this)(key
);
929 throw std::out_of_range("idict::expect()");
932 const K
&operator[](int index
) const
934 return database
.entries
.at(index
- offset
).udata
;
937 void swap(idict
&other
)
939 database
.swap(other
.database
);
942 void reserve(size_t n
) { database
.reserve(n
); }
943 size_t size() const { return database
.size(); }
944 bool empty() const { return database
.empty(); }
945 void clear() { database
.clear(); }
947 const_iterator
begin() const { return database
.begin(); }
948 const_iterator
end() const { return database
.end(); }
951 template<typename K
, typename OPS
>
954 mutable idict
<K
, 0, OPS
> database
;
955 mutable std::vector
<int> parents
;
958 typedef typename idict
<K
, 0, OPS
>::const_iterator const_iterator
;
960 int operator()(const K
&key
) const
962 int i
= database(key
);
963 parents
.resize(database
.size(), -1);
967 const K
&operator[](int index
) const
969 return database
[index
];
972 int ifind(int i
) const
976 while (parents
[p
] != -1)
980 int next_k
= parents
[k
];
988 void imerge(int i
, int j
)
1002 int next_k
= parents
[k
];
1010 int lookup(const K
&a
) const
1012 return ifind((*this)(a
));
1015 const K
&find(const K
&a
) const
1017 int i
= database
.at(a
, -1);
1020 return (*this)[ifind(i
)];
1023 void merge(const K
&a
, const K
&b
)
1025 imerge((*this)(a
), (*this)(b
));
1028 void promote(const K
&a
)
1030 int i
= database
.at(a
, -1);
1035 void swap(mfp
&other
)
1037 database
.swap(other
.database
);
1038 parents
.swap(other
.parents
);
1041 void reserve(size_t n
) { database
.reserve(n
); }
1042 size_t size() const { return database
.size(); }
1043 bool empty() const { return database
.empty(); }
1044 void clear() { database
.clear(); parents
.clear(); }
1046 const_iterator
begin() const { return database
.begin(); }
1047 const_iterator
end() const { return database
.end(); }
1050 } /* namespace hashlib */