kblib 0.2.3
General utilities library for modern C++
direct_map.h
Go to the documentation of this file.
1/* *****************************************************************************
2 * kblib is a general utility library for C++14 and C++17, intended to provide
3 * performant high-level abstractions and more expressive ways to do simple
4 * things.
5 *
6 * Copyright (c) 2021 killerbee
7 *
8 * This program is free software: you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with this program. If not, see <https://www.gnu.org/licenses/>.
20 * ****************************************************************************/
21
31#ifndef DIRECT_MAP_H
32#define DIRECT_MAP_H
33
34#include <kblib/fakestd.h>
35#include <kblib/iterators.h>
36#include <kblib/tdecl.h>
37
38#include <array>
39#include <bitset>
40#include <cinttypes>
41#include <climits>
42#include <limits>
43#include <new>
44#include <optional>
45
46namespace KBLIB_NS {
47
53
54 template <typename T>
56 = (std::numeric_limits<T>::digits + std::numeric_limits<T>::is_signed
57 < std::numeric_limits<std::uintmax_t>::digits)
58 ? static_cast<std::uintmax_t>(1)
59 << to_unsigned(std::numeric_limits<T>::digits
60 + std::numeric_limits<T>::is_signed)
61 : 0;
62 static_assert(range_of<unsigned char> == 1u << to_unsigned(CHAR_BIT), "");
63 static_assert(range_of<signed char> == 1u << to_unsigned(CHAR_BIT), "");
64
65 template <typename T, bool
66 = std::is_trivially_default_constructible<T>::value and
67 std::is_trivially_destructible<T>::value>
68 struct alignas(T) storage_for : private std::array<byte, sizeof(T)> {
69 template <
70 typename... Args,
71 enable_if_t<std::is_constructible<T, Args&&...>::value, int> = 0>
72 constexpr auto construct(Args&&... args) noexcept(
73 std::is_nothrow_constructible<T, Args&&...>::value) -> T& {
74 return *new (this->data()) T(std::forward<Args>(args)...);
75 }
76 storage_for() = default;
77 storage_for(const storage_for&) = delete;
79
80 auto operator=(const storage_for&) -> storage_for& = delete;
81 auto operator=(storage_for&&) -> storage_for& = delete;
82
83 ~storage_for() = default;
84
85 constexpr auto destroy() noexcept -> void { get()->~T(); }
86
87#if __cpp_lib_launder
88# define LAUNDER(x) std::launder(x)
89#else
90# define LAUNDER(x) (x)
91#endif
92 KBLIB_NODISCARD constexpr auto get() & noexcept -> T* {
93 return LAUNDER(reinterpret_cast<T*>(this->data()));
94 }
95 KBLIB_NODISCARD constexpr auto get() const& noexcept -> const T* {
96 return LAUNDER(reinterpret_cast<const T*>(this->data()));
97 }
98#undef LAUNDER
99 };
100 template <typename T>
101 struct alignas(T) storage_for<T, true> {
102 private:
103 T t;
104
105 public:
106 template <
107 typename... Args,
108 enable_if_t<std::is_constructible<T, Args&&...>::value, int> = 0>
109 constexpr auto construct(Args&&... args) noexcept(
110 std::is_nothrow_constructible<T, Args&&...>::value) -> T& {
111 return *new (&t) T(std::forward<Args>(args)...);
112 }
113
114 constexpr auto destroy() noexcept -> void {}
115
116 KBLIB_NODISCARD constexpr auto get() & noexcept -> T* { return &t; }
117 KBLIB_NODISCARD constexpr auto get() const& noexcept -> const T* {
118 return &t;
119 }
120 };
121
122} // namespace detail_direct_map
123
124template <typename Key, typename T, typename allocator = void>
126 // Allocating direct_map
127 public:
128 using key_type = Key;
129 using mapped_type = T;
130 using value_type = std::pair<const Key, T>;
131 using size_type = std::size_t;
132 using difference_type = std::ptrdiff_t;
133
137 using const_pointer = const value_type*;
138
139 private:
140 constexpr static std::ptrdiff_t key_range{detail_direct_map::range_of<Key>};
142
143 using held_type
144 = std::pair<std::bitset<key_range>, std::array<storage_type, key_range>>;
145
146 template <typename V>
147 class iter {
148 public:
150 std::ptrdiff_t pos;
151
152 constexpr iter(decltype(storage) s, std::ptrdiff_t p)
153 : storage(s)
154 , pos(p) {
155 if (not storage) {
156 pos = max();
157 }
158 }
159 constexpr iter()
160 : iter(nullptr, max()) {}
161
162 using value_type = typename direct_map::value_type;
163 using difference_type = typename direct_map::difference_type;
164 using reference = copy_const_t<V, value_type>&;
165 using pointer = copy_const_t<V, value_type>*;
166 using iterator_category = std::bidirectional_iterator_tag;
167
168 KBLIB_NODISCARD constexpr auto operator*() const noexcept -> reference {
169 return *storage->second[uindex(pos)].get();
170 }
171 KBLIB_NODISCARD constexpr auto operator->() const noexcept -> pointer {
172 return storage->second[uindex(pos)].get();
173 }
174
175 constexpr auto operator++() noexcept -> iter& {
176 if (pos == max()) {
177 // not required in general, but direct_map::iterator guarantees that
178 // ++end() == end() because it simplifies the implementation and is
179 // unlikely to be a significant performance impact
180 return *this;
181 }
182 for (auto i : range(++pos, index(max()))) {
183 if (storage->first.test(uindex(i))) {
184 pos = i;
185 return *this;
186 }
187 }
188 pos = index(max());
189 return *this;
190 }
191 constexpr auto operator++(int) noexcept -> iter {
192 iter it = *this;
193 ++*this;
194 return it;
195 }
196
197 constexpr auto operator--() noexcept -> iter& {
198 for (auto i : range(pos - 1, index(min()), -1)) {
199 if (storage->first.test(uindex(i))) {
200 pos = i;
201 return *this;
202 }
203 }
204 pos = index(min());
205 return *this;
206 }
207 constexpr auto operator--(int) noexcept -> iter {
208 iter it = *this;
209 --*this;
210 return it;
211 }
212
213 KBLIB_NODISCARD friend constexpr auto operator==(iter l, iter r) noexcept
214 -> bool {
215 return l.storage == r.storage and l.pos == r.pos;
216 }
217 KBLIB_NODISCARD friend constexpr auto operator!=(iter l, iter r) noexcept
218 -> bool {
219 return not (l == r);
220 }
221#define DECL_OP(op) \
222 KBLIB_NODISCARD friend constexpr auto operator op(iter l, \
223 iter r) noexcept->bool { \
224 assert(l.storage == r.storage); \
225 return l.pos op r.pos; \
226 }
227 DECL_OP(<)
228 DECL_OP(>)
229 DECL_OP(>=)
230 DECL_OP(<=)
231#undef DECL_OP
232
233 constexpr auto swap(iter& other) noexcept -> void {
234 kblib::swap(storage, other.storage);
235 kblib::swap(pos, other.pos);
236 }
237 };
238
239 public:
240 using iterator = iter<value_type>;
241 using const_iterator = iter<const value_type>;
242 using reverse_iterator = std::reverse_iterator<iterator>;
243 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
244
245 constexpr direct_map() noexcept = default;
246
247 template <typename InputIt>
248 constexpr direct_map(InputIt first, InputIt last)
249 : storage() {
250 if (first != last) {
251 allocate();
252 for (auto v : indirect(first, last)) {
253 construct(v.first, v.second);
254 }
255 }
256 }
257 // TODO(killerbee13): copy construction for allocating direct_map
258 constexpr direct_map(const direct_map& other)
259 : storage()
260 , _size(other._size) {
261 if (not other.empty()) {
262 allocate();
263 storage->first = other.storage->first;
264 for (auto k : range(+min(), max() + 1)) {
265 if (contains(k)) { // the bitmap is already copied from other
266 do_construct(k, other.at(k));
267 }
268 }
269 }
270 }
271
272 constexpr direct_map(direct_map&& other) noexcept
273 : storage(std::move(other.storage))
274 , _size(std::exchange(other._size, 0)) {}
275
276 constexpr direct_map(std::initializer_list<value_type> init)
277 : direct_map(init.begin(), init.end()) {}
278
282 KBLIB_CXX20(constexpr) ~direct_map() { clear(); }
283
284 constexpr auto operator=(const direct_map& other) -> direct_map& {
285 if (this == &other) {
286 return *this;
287 }
288 clear();
289 storage.assign(in_place_agg, other.storage->first);
290 _size = other._size;
291 for (auto k : range(+min(), max() + 1)) {
292 if (contains(k)) { // the bitmap is already copied from other
293 do_construct(k, other.at(k));
294 bitmap().set(index(k));
295 }
296 }
297 return *this;
298 }
299 constexpr auto operator=(direct_map&& other) noexcept
300 -> direct_map& = default;
301 constexpr auto operator=(std::initializer_list<value_type> init)
302 -> direct_map& {
303 clear();
304 for (auto it : init) {
305 construct(it->first, it->second);
306 }
307 return *this;
308 }
309
310 KBLIB_NODISCARD constexpr auto at(Key key) & -> T& {
311 if (contains(key)) {
312 return unsafe_at(key).get()->second;
313 } else {
314 throw std::out_of_range("direct_map: key out of range");
315 }
316 }
317 KBLIB_NODISCARD constexpr auto at(Key key) && -> T&& {
318 if (contains(key)) {
319 return std::move(unsafe_at(key).get()->second);
320 } else {
321 throw std::out_of_range("direct_map: key out of range");
322 }
323 }
324 KBLIB_NODISCARD constexpr auto at(Key key) const& -> const T& {
325 if (contains(key)) {
326 return unsafe_at(key).get()->second;
327 } else {
328 throw std::out_of_range("direct_map: key out of range");
329 }
330 }
331 KBLIB_NODISCARD constexpr auto at(Key key) const&& -> const T&& {
332 if (contains(key)) {
333 return std::move(unsafe_at(key).get()->second);
334 } else {
335 throw std::out_of_range("direct_map: key out of range");
336 }
337 }
338
339 KBLIB_NODISCARD constexpr T& operator[](Key key) noexcept(
340 std::is_nothrow_default_constructible<T>::value) {
341 return try_emplace(key).first->second;
342 }
343
344 KBLIB_NODISCARD constexpr auto begin() & noexcept -> iterator {
345 return {storage.get(), cbegin().pos};
346 }
347 KBLIB_NODISCARD constexpr auto begin() const& noexcept -> const_iterator {
348 return {storage.get(), cbegin().pos};
349 }
350 KBLIB_NODISCARD constexpr auto cbegin() const& noexcept -> const_iterator {
351 if (not empty()) {
352 if (contains(to_key(min()))) {
353 return {storage.get(), min()};
354 } else {
355 return ++const_iterator{storage.get(), min()};
356 }
357 } else {
358 return end();
359 }
360 }
361
362 KBLIB_NODISCARD constexpr auto end() & noexcept -> iterator {
363 return {storage.get(), max()};
364 }
365 KBLIB_NODISCARD constexpr auto end() const& noexcept -> const_iterator {
366 return {storage.get(), max()};
367 }
368 KBLIB_NODISCARD constexpr auto cend() const& noexcept -> const_iterator {
369 return {storage.get(), max()};
370 }
371
372 KBLIB_NODISCARD constexpr auto rbegin() & noexcept -> auto {
373 return std::make_reverse_iterator(end());
374 }
375 KBLIB_NODISCARD constexpr auto rbegin() const& noexcept -> auto {
376 return std::make_reverse_iterator(end());
377 }
378 KBLIB_NODISCARD constexpr auto crbegin() const& noexcept -> auto {
379 return std::make_reverse_iterator(cend());
380 }
381
382 KBLIB_NODISCARD constexpr auto rend() & noexcept -> auto {
383 return std::make_reverse_iterator(begin());
384 }
385 KBLIB_NODISCARD constexpr auto rend() const& noexcept -> auto {
386 return std::make_reverse_iterator(begin());
387 }
388 KBLIB_NODISCARD constexpr auto crend() const& noexcept -> auto {
389 return std::make_reverse_iterator(cbegin());
390 }
391
392 KBLIB_NODISCARD constexpr auto empty() const& noexcept -> bool {
393 return _size == 0;
394 }
395
396 KBLIB_NODISCARD constexpr auto size() const& noexcept -> std::size_t {
397 return _size;
398 }
399 KBLIB_NODISCARD constexpr auto ssize() const& noexcept -> std::ptrdiff_t {
400 return _size;
401 }
402
403 KBLIB_NODISCARD constexpr static auto max_size() noexcept -> std::size_t {
404 return key_range;
405 }
406
407 constexpr auto clear() noexcept -> void {
408 if (_size == 0) {
409 return;
410 }
411 for (auto i : range(+min(), max() + 1)) {
412 auto j = static_cast<Key>(i);
413 if (contains(j)) {
414 unsafe_at(j).destroy();
415 }
416 }
417 storage.reset();
418 _size = 0;
419 }
420
421 constexpr auto insert(const value_type& value) -> std::pair<iterator, bool> {
422 if (not contains(value.first)) {
423 construct(value.first, value.second);
424 return {{storage.get(), index(value.first)}, true};
425 } else {
426 return {{storage.get(), index(value.first)}, false};
427 }
428 }
429 template <typename U>
430 constexpr auto insert(U&& value)
432 std::pair<iterator, bool>> {
433 if (not contains(value.first)) {
434 construct(value.first, std::forward<U>(value.second));
435 return {{storage.get(), index(value.first)}, true};
436 } else {
437 return {{storage.get(), index(value.first)}, false};
438 }
439 }
440 constexpr auto insert(value_type&& value) -> std::pair<iterator, bool> {
441 if (not contains(value.first)) {
442 construct(value.first, std::move(value.second));
443 return {{storage.get(), index(value.first)}, true};
444 } else {
445 return {{storage.get(), index(value.first)}, false};
446 }
447 }
448
449 template <typename U>
450 constexpr auto insert_or_assign(Key key, U&& value)
451 -> std::pair<iterator, bool> {
452 if (not contains(key)) {
453 construct(key, std::forward<U>(value));
454 return {{storage.get(), index(key)}, true};
455 } else {
456 *unsafe_at(key).get() = std::forward<U>(value);
457 return {{storage.get(), index(key)}, false};
458 }
459 }
460 template <typename... Args>
461 constexpr auto try_emplace(Key key, Args&&... args)
462 -> std::pair<iterator, bool> {
463 if (not contains(key)) {
464 construct(key, std::forward<Args>(args)...);
465 return {{storage.get(), index(key)}, true};
466 } else {
467 return {{storage.get(), index(key)}, false};
468 }
469 }
470
471 constexpr auto erase(iterator pos) noexcept -> iterator {
472 assert(contains(to_key(pos.pos)));
473 bitmap().reset(pos.pos);
474 unsafe_at(to_key(pos.pos)).destroy();
475 --_size;
476 return ++pos;
477 }
478 constexpr auto erase(const_iterator pos) noexcept -> iterator {
479 assert(contains(to_key(pos.pos)));
480 bitmap().reset(pos.pos);
481 unsafe_at(to_key(pos.pos)).destroy();
482 --_size;
483 return ++pos;
484 }
485
486 constexpr auto erase(iterator first, iterator last) noexcept -> iterator {
487 for (auto i : range(first.pos, last.pos)) {
488 if (contains(to_key(i))) {
489 bitmap().reset(i);
490 unsafe_at(to_key(i)).destroy();
491 --_size;
492 }
493 }
494 return ++last;
495 }
496
497 constexpr auto erase(Key key) noexcept -> std::size_t {
498 if (contains(key)) {
499 bitmap().reset(index(key));
500 unsafe_at(key).destroy();
501 --_size;
502 return 1;
503 } else {
504 return 0;
505 }
506 }
507
508 constexpr auto swap(direct_map& other) noexcept -> void {
509 using std::swap;
510 swap(storage, other.storage);
511 swap(_size, other._size);
512 }
513
514 KBLIB_NODISCARD constexpr auto contains(Key key) const noexcept -> bool {
515 return storage and bitmap().test(uindex(key));
516 }
517 KBLIB_NODISCARD constexpr auto count(Key key) const noexcept -> std::size_t {
518 return contains(key);
519 }
520
521 KBLIB_NODISCARD constexpr auto find(Key key) & noexcept -> iterator {
522 return contains(key) ? iterator{storage.get(), index(key)} : end();
523 }
524 KBLIB_NODISCARD constexpr auto find(Key key) const& noexcept
525 -> const_iterator {
526 return contains(key) ? iterator{storage.get(), index(key)} : end();
527 }
528
529 KBLIB_NODISCARD constexpr auto equal_range(Key key) & noexcept
530 -> std::pair<iterator, iterator> {
531 return {lower_bound(key), upper_bound(key)};
532 }
533 KBLIB_NODISCARD constexpr auto equal_range(Key key) const& noexcept
534 -> std::pair<const_iterator, const_iterator> {
535 return {lower_bound(key), upper_bound(key)};
536 }
537
538 KBLIB_NODISCARD constexpr auto lower_bound(Key key) & noexcept -> iterator {
539 if (contains(key)) {
540 return find(key);
541 } else {
542 return ++iterator{storage.get(), index(key)};
543 }
544 }
545 KBLIB_NODISCARD constexpr auto lower_bound(Key key) const& noexcept
546 -> const_iterator {
547 if (contains(key)) {
548 return find(key);
549 } else {
550 return ++iterator{storage.get(), index(key)};
551 }
552 }
553
554 KBLIB_NODISCARD constexpr auto upper_bound(Key key) & noexcept -> iterator {
555 // if the key exists, upper_bound is the next one
556 auto l = lower_bound(key);
557 if (l.pos == index(key)) {
558 return ++l;
559 // otherwise upper_bound == lower_bound
560 } else {
561 return l;
562 }
563 }
564 KBLIB_NODISCARD constexpr auto upper_bound(Key key) const& noexcept
565 -> const_iterator {
566 // if the key exists, upper_bound is the next one
567 auto l = lower_bound(key);
568 if (l.pos == index(key)) {
569 return ++l;
570 // otherwise upper_bound == lower_bound
571 } else {
572 return l;
573 }
574 }
575
576 KBLIB_NODISCARD constexpr static auto min() noexcept -> Key {
578 }
579 KBLIB_NODISCARD constexpr static auto max() noexcept -> Key {
581 }
582
583 KBLIB_NODISCARD friend constexpr auto operator==(
584 const direct_map& l,
585 const direct_map& r) noexcept(noexcept(std::declval<T&>()
586 == std::declval<T&>())) -> bool {
587 if (l.size() != r.size()) {
588 return false;
589 }
590 for (auto i : kblib::range(+min(), max() + 1)) {
591 if (l.contains(i) != r.contains(i)) {
592 return false;
593 } else if (l.contains(i)) {
594 if (l.at(i) != r.at(i)) {
595 return false;
596 }
597 }
598 }
599 return true;
600 }
601
602 KBLIB_NODISCARD friend constexpr auto operator!=(
603 const direct_map& l,
604 const direct_map& r) noexcept(noexcept(std::declval<T&>()
605 == std::declval<T&>())) -> bool {
606 return not (l == r);
607 }
608
609 KBLIB_NODISCARD friend constexpr auto operator<(
610 const direct_map& l,
611 const direct_map& r) noexcept(noexcept(std::declval<T&>(),
612 std::declval<T&>())) -> bool {
613 return kblib::lexicographical_compare(l.begin(), l.end(), r.begin(),
614 r.end());
615 }
616 KBLIB_NODISCARD friend constexpr auto operator>(
617 const direct_map& l,
618 const direct_map& r) noexcept(noexcept(std::declval<T&>(),
619 std::declval<T&>())) -> bool {
620 return r < l;
621 }
622 KBLIB_NODISCARD friend constexpr auto operator<=(
623 const direct_map& l,
624 const direct_map& r) noexcept(noexcept(std::declval<T&>(),
625 std::declval<T&>())) -> bool {
626 return not (r < l);
627 }
628 KBLIB_NODISCARD friend constexpr auto operator>=(
629 const direct_map& l,
630 const direct_map& r) noexcept(noexcept(std::declval<T&>(),
631 std::declval<T&>())) -> bool {
632 return not (l < r);
633 }
634
635 KBLIB_NODISCARD constexpr static auto index(Key key) noexcept
636 -> std::ptrdiff_t {
637 return to_signed(key);
638 }
639 KBLIB_NODISCARD constexpr static auto uindex(Key key) noexcept
640 -> std::size_t {
641 return to_unsigned(key);
642 }
643 KBLIB_NODISCARD constexpr static auto to_key(std::ptrdiff_t i) noexcept
644 -> Key {
645 return Key(i);
646 }
647
648 private:
649 KBLIB_NODISCARD constexpr auto bitmap() noexcept -> std::bitset<key_range>& {
650 return storage->first;
651 }
652 KBLIB_NODISCARD constexpr const std::bitset<key_range>& bitmap()
653 const noexcept {
654 return storage->first;
655 }
656
657 KBLIB_NODISCARD constexpr auto unsafe_at(Key key) & -> storage_type& {
658 return storage->second[uindex(key)];
659 }
660 KBLIB_NODISCARD constexpr auto unsafe_at(Key key) && -> storage_type&& {
661 return storage->second[uindex(key)];
662 }
663 KBLIB_NODISCARD constexpr auto unsafe_at(Key key) const& -> const
664 storage_type& {
665 return storage->second[uindex(key)];
666 }
667 KBLIB_NODISCARD constexpr auto unsafe_at(Key key) const&& -> const
668 storage_type&& {
669 return storage->second[uindex(key)];
670 }
671
672 auto allocate() -> void {
673 if (not storage) {
674 storage.assign();
675 }
676 }
677
678 template <typename... Args>
679 constexpr void construct(Key key, Args&&... args) noexcept(
680 std::is_nothrow_constructible<value_type, Args&&...>::value) {
681 allocate();
682 if (not storage->first.test(uindex(key))) {
683 do_construct(key, std::forward<Args>(args)...);
684 // doing these after construction maintains exception safety.
685 storage->first.set(uindex(key));
686 ++_size;
687 }
688 }
689
690 template <typename... Args>
691 constexpr void do_construct(Key key, Args&&... args) noexcept(
692 std::is_nothrow_constructible<value_type, Args&&...>::value) {
693 storage->second[uindex(key)].construct(
694 std::piecewise_construct, std::forward_as_tuple(key),
695 std::forward_as_tuple(std::forward<Args>(args)...));
696 }
697
698 // TODO(killerbee13): Implement, test, and document direct_map
699 // TODO(killerbee13): allocator support for direct_map
701 std::size_t _size{};
702};
703
704template <typename Key, typename T>
705class direct_map<Key, T, void> {
706 // Non-allocating direct_map
707 public:
708 using key_type = Key;
709 using mapped_type = T;
710 using value_type = std::pair<const Key, T>;
711 using size_type = std::size_t;
712 using difference_type = std::ptrdiff_t;
713
717 using const_pointer = const value_type*;
718
719 private:
720 constexpr static std::ptrdiff_t key_range{detail_direct_map::range_of<Key>};
722
723 template <typename V>
724 class iter {
725 public:
727 std::ptrdiff_t pos;
728
729 constexpr iter(decltype(map) s, std::ptrdiff_t p)
730 : map(s)
731 , pos(p) {
732 if (not map) {
733 pos = max();
734 }
735 }
736 constexpr iter()
737 : iter(nullptr, max()) {}
738
739 using value_type = typename direct_map::value_type;
740 using difference_type = typename direct_map::difference_type;
741 using reference = copy_const_t<V, value_type>&;
742 using pointer = copy_const_t<V, value_type>*;
743 using iterator_category = std::bidirectional_iterator_tag;
744
745 KBLIB_NODISCARD constexpr auto operator*() const -> reference {
746 return *map->elems[uindex(pos)].get();
747 }
748 KBLIB_NODISCARD constexpr auto operator->() const -> pointer {
749 return map->elems[uindex(pos)].get();
750 }
751
752 constexpr auto operator++() -> iter& {
753 if (pos == max()) {
754 // not required in general, but direct_map::iterator guarantees that
755 // ++end() == end() because it simplifies the implementation and is
756 // unlikely to be a significant performance impact
757 return *this;
758 }
759 for (auto i : range(++pos, index(max()))) {
760 if (map->active_elems.test(uindex(i))) {
761 pos = i;
762 return *this;
763 }
764 }
765 pos = index(max());
766 return *this;
767 }
768 constexpr auto operator++(int) -> iter {
769 iter it = *this;
770 ++*this;
771 return it;
772 }
773
774 constexpr auto operator--() -> iter& {
775 for (auto i : range(pos - 1, index(min()), -1)) {
776 if (map->active_elems.test(uindex(i))) {
777 pos = i;
778 return *this;
779 }
780 }
781 pos = index(min());
782 return *this;
783 }
784 constexpr auto operator--(int) -> iter {
785 iter it = *this;
786 --*this;
787 return it;
788 }
789
790 KBLIB_NODISCARD friend constexpr auto operator==(iter l, iter r) noexcept
791 -> bool {
792 return l.map == r.map and l.pos == r.pos;
793 }
794 KBLIB_NODISCARD friend constexpr auto operator!=(iter l, iter r) noexcept
795 -> bool {
796 return not (l == r);
797 }
798
799#define DECL_OP(op) \
800 KBLIB_NODISCARD friend constexpr auto operator op(iter l, \
801 iter r) noexcept->bool { \
802 assert(l.map == r.map); \
803 return l.pos op r.pos; \
804 }
805 DECL_OP(<)
806 DECL_OP(>)
807 DECL_OP(>=)
808 DECL_OP(<=)
809#undef DECL_OP
810
811 constexpr auto swap(iter& other) noexcept -> void {
812 kblib::swap(map, other.map);
813 kblib::swap(pos, other.pos);
814 }
815 };
816
817 public:
818 using iterator = iter<value_type>;
819 using const_iterator = iter<const value_type>;
820 using reverse_iterator = std::reverse_iterator<iterator>;
821 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
822
823 constexpr direct_map() noexcept = default;
824
825 template <typename InputIt>
826 constexpr direct_map(InputIt first, InputIt last) {
827 for (auto&& v : indirect(first, last)) {
828 construct(std::forward<decltype(v)>(v).first,
829 std::forward<decltype(v)>(v).second);
830 }
831 }
832
833 constexpr direct_map(const direct_map& other)
834 : active_elems{other.active_elems}
835 , _size(other._size) {
836 for (const key_type k : range(+min(), max() + 1)) {
837 if (contains(k)) { // the bitmap is already copied from other
838 do_construct(k, other.unsafe_at(k).get()->second);
839 bitmap().set(uindex(k));
840 }
841 }
842 }
843
844 constexpr direct_map(direct_map&& other) noexcept(
845 std::is_nothrow_move_constructible<value_type>::value)
846 : active_elems{other.active_elems}
847 , _size(other._size) {
848 for (const key_type k : range(+min(), max() + 1)) {
849 if (contains(k)) { // the bitmap is already copied from other
850 do_construct(k, std::move(other.unsafe_at(k).get()->second));
851 bitmap().set(uindex(k));
852 }
853 }
854 }
855
856 constexpr direct_map(std::initializer_list<value_type> init)
857 : direct_map(init.begin(), init.end()) {}
858
859 // TODO(killerbee13): Remove this and allow it to be trivially destructible
860 // for trivial Key and T
861 KBLIB_CXX20(constexpr) ~direct_map() { clear(); }
862
863 constexpr auto operator=(const direct_map& other) -> direct_map& {
864 if (this == &other) {
865 return *this;
866 }
867 clear();
868 active_elems = other.active_elems;
869 _size = other._size;
870 for (const key_type k : range(+min(), max() + 1)) {
871 if (contains(k)) { // the bitmap is already copied from other
872 do_construct(k, other.unsafe_at(k).get()->second);
873 bitmap().set(uindex(k));
874 }
875 }
876 return *this;
877 }
878 constexpr auto operator=(direct_map&& other) noexcept(
879 std::is_nothrow_move_constructible<T>::value) -> direct_map& {
880 if (this == &other) {
881 return *this;
882 }
883 active_elems = other.active_elems;
884 _size = other._size;
885 for (const key_type k : range(+min(), max() + 1)) {
886 if (contains(k)) { // the bitmap is already copied from other
887 do_construct(k, std::move(other.unsafe_at(k).get()->second));
888 bitmap().set(uindex(k));
889 }
890 }
891 return *this;
892 }
893 constexpr auto operator=(std::initializer_list<value_type> init)
894 -> direct_map& {
895 clear();
896 for (auto it : init) {
897 construct(it->first, it->second);
898 }
899 return *this;
900 }
901
902 KBLIB_NODISCARD constexpr auto at(Key key) & -> T& {
903 if (contains(key)) {
904 return unsafe_at(key).get()->second;
905 } else {
906 throw std::out_of_range("direct_map: key out of range");
907 }
908 }
909 KBLIB_NODISCARD constexpr auto at(Key key) && -> T&& {
910 if (contains(key)) {
911 return std::move(unsafe_at(key).get()->second);
912 } else {
913 throw std::out_of_range("direct_map: key out of range");
914 }
915 }
916 KBLIB_NODISCARD constexpr auto at(Key key) const& -> const T& {
917 if (contains(key)) {
918 return unsafe_at(key).get()->second;
919 } else {
920 throw std::out_of_range("direct_map: key out of range");
921 }
922 }
923 KBLIB_NODISCARD constexpr auto at(Key key) const&& -> const T&& {
924 if (contains(key)) {
925 return std::move(unsafe_at(key).get()->second);
926 } else {
927 throw std::out_of_range("direct_map: key out of range");
928 }
929 }
930
931 KBLIB_NODISCARD constexpr T& operator[](Key key) noexcept(
932 std::is_nothrow_default_constructible<T>::value) {
933 return try_emplace(key).first->second;
934 }
935
936 KBLIB_NODISCARD constexpr auto begin() & noexcept -> iterator {
937 return {this, cbegin().pos};
938 }
939 KBLIB_NODISCARD constexpr auto begin() const& noexcept -> const_iterator {
940 return {this, cbegin().pos};
941 }
942 KBLIB_NODISCARD constexpr auto cbegin() const& noexcept -> const_iterator {
943 if (not empty()) {
944 if (contains(to_key(min()))) {
945 return {this, min()};
946 } else {
947 return ++const_iterator{this, min()};
948 }
949 } else {
950 return end();
951 }
952 }
953
954 KBLIB_NODISCARD constexpr auto end() & noexcept -> iterator {
955 return {this, max()};
956 }
957 KBLIB_NODISCARD constexpr auto end() const& noexcept -> const_iterator {
958 return {this, max()};
959 }
960 KBLIB_NODISCARD constexpr auto cend() const& noexcept -> const_iterator {
961 return {this, max()};
962 }
963
964 KBLIB_NODISCARD constexpr auto rbegin() & noexcept -> reverse_iterator {
965 return std::make_reverse_iterator(end());
966 }
967 KBLIB_NODISCARD constexpr auto rbegin() const& noexcept
969 return std::make_reverse_iterator(end());
970 }
971 KBLIB_NODISCARD constexpr auto crbegin() const& noexcept
973 return std::make_reverse_iterator(crend());
974 }
975
976 KBLIB_NODISCARD constexpr auto rend() & noexcept -> reverse_iterator {
977 return std::make_reverse_iterator(begin());
978 }
979 KBLIB_NODISCARD constexpr auto rend() const& noexcept
981 return std::make_reverse_iterator(begin());
982 }
983 KBLIB_NODISCARD constexpr auto crend() const& noexcept
985 return std::make_reverse_iterator(cbegin());
986 }
987
988 KBLIB_NODISCARD constexpr auto empty() const& noexcept -> bool {
989 return _size == 0;
990 }
991
992 KBLIB_NODISCARD constexpr auto size() const& noexcept -> std::size_t {
993 return _size;
994 }
995 KBLIB_NODISCARD constexpr auto ssize() const& noexcept -> std::ptrdiff_t {
996 return _size;
997 }
998
999 KBLIB_NODISCARD constexpr static auto max_size() noexcept -> std::size_t {
1000 return key_range;
1001 }
1002
1003 constexpr auto clear() noexcept -> void {
1004 for (auto i : range(+min(), max() + 1)) {
1005 auto j = static_cast<Key>(i);
1006 if (contains(j)) {
1007 unsafe_at(j).destroy();
1008 }
1009 }
1010 _size = 0;
1011 }
1012
1013 constexpr auto insert(const value_type& value) -> std::pair<iterator, bool> {
1014 if (not contains(value.first)) {
1015 construct(value.first, value.second);
1016 return {{this, index(value.first)}, true};
1017 } else {
1018 return {{this, index(value.first)}, false};
1019 }
1020 }
1021 template <typename U>
1022 constexpr auto insert(U&& value)
1024 std::pair<iterator, bool>> {
1025 if (not contains(value.first)) {
1026 construct(value.first, std::forward<U>(value.second));
1027 return {{this, index(value.first)}, true};
1028 } else {
1029 return {{this, index(value.first)}, false};
1030 }
1031 }
1032 constexpr auto insert(value_type&& value) -> std::pair<iterator, bool> {
1033 if (not contains(value.first)) {
1034 construct(value.first, std::move(value.second));
1035 return {{this, index(value.first)}, true};
1036 } else {
1037 return {{this, index(value.first)}, false};
1038 }
1039 }
1040
1041 template <typename U>
1042 constexpr auto insert_or_assign(Key key, U&& value)
1043 -> std::pair<iterator, bool> {
1044 if (not contains(key)) {
1045 construct(key, std::forward<U>(value));
1046 return {{this, index(key)}, true};
1047 } else {
1048 *unsafe_at(key).get() = std::forward<U>(value);
1049 return {{this, index(key)}, false};
1050 }
1051 }
1052 template <typename... Args>
1053 constexpr auto try_emplace(Key key, Args&&... args)
1054 -> std::pair<iterator, bool> {
1055 if (not contains(key)) {
1056 construct(key, std::forward<Args>(args)...);
1057 return {{this, index(key)}, true};
1058 } else {
1059 return {{this, index(key)}, false};
1060 }
1061 }
1062
1063 constexpr auto erase(iterator pos) noexcept -> iterator {
1064 assert(contains(to_key(pos.pos)));
1065 destroy(to_key(pos.pos));
1066 return ++pos;
1067 }
1068 constexpr auto erase(const_iterator pos) noexcept -> iterator {
1069 assert(contains(to_key(pos.pos)));
1070 destroy(to_key(pos.pos));
1071 return ++pos;
1072 }
1073
1074 constexpr auto erase(iterator first, iterator last) noexcept -> iterator {
1075 for (auto i : range(first.pos, last.pos)) {
1076 if (contains(to_key(i))) {
1077 destroy(to_key(i));
1078 }
1079 }
1080 return ++last;
1081 }
1082
1083 constexpr auto erase(Key key) noexcept -> std::size_t {
1084 if (contains(key)) {
1085 destroy(key);
1086 return 1;
1087 } else {
1088 return 0;
1089 }
1090 }
1091
1092 constexpr auto swap(direct_map& other) noexcept(
1093 std::is_nothrow_move_constructible<value_type>::value and
1095 using std::swap;
1096 for (const key_type k : range(+min(), max() + 1)) {
1097 if (contains(k)) {
1098 if (other.contains(k)) {
1099 kblib::swap(unsafe_at(k).get()->second,
1100 other.unsafe_at(k).get()->second);
1101 } else {
1102 other.construct(k, std::move(unsafe_at(k).get()->second));
1103 destroy(k);
1104 }
1105 } else if (other.contains(k)) {
1106 construct(k, std::move(other.unsafe_at(k).get()->second));
1107 other.destroy(k);
1108 } else {
1109 // do nothing
1110 }
1111 }
1112
1113 swap(active_elems, other.active_elems);
1114 swap(_size, other._size);
1115 }
1116
1117 KBLIB_NODISCARD constexpr auto contains(Key key) const noexcept -> bool {
1118 return bitmap().test(uindex(key));
1119 }
1120 KBLIB_NODISCARD constexpr auto count(Key key) const noexcept -> std::size_t {
1121 return contains(key);
1122 }
1123
1124 KBLIB_NODISCARD constexpr auto find(Key key) & noexcept -> iterator {
1125 return contains(key) ? iterator{this, index(key)} : end();
1126 }
1127 KBLIB_NODISCARD constexpr auto find(Key key) const& noexcept
1128 -> const_iterator {
1129 return contains(key) ? iterator{this, index(key)} : end();
1130 }
1131
1132 KBLIB_NODISCARD constexpr auto equal_range(Key key) & noexcept
1133 -> std::pair<iterator, iterator> {
1134 return {lower_bound(key), upper_bound(key)};
1135 }
1136 KBLIB_NODISCARD constexpr auto equal_range(Key key) const& noexcept
1137 -> std::pair<const_iterator, const_iterator> {
1138 return {lower_bound(key), upper_bound(key)};
1139 }
1140
1141 KBLIB_NODISCARD constexpr auto lower_bound(Key key) & noexcept -> iterator {
1142 if (contains(key)) {
1143 return find(key);
1144 } else {
1145 return ++iterator{this, index(key)};
1146 }
1147 }
1148 KBLIB_NODISCARD constexpr auto lower_bound(Key key) const& noexcept
1149 -> const_iterator {
1150 if (contains(key)) {
1151 return find(key);
1152 } else {
1153 return ++iterator{this, index(key)};
1154 }
1155 }
1156
1157 KBLIB_NODISCARD constexpr auto upper_bound(Key key) & noexcept -> iterator {
1158 // if the key exists, upper_bound is the next one
1159 auto l = lower_bound(key);
1160 if (l.pos == index(key)) {
1161 return ++l;
1162 // otherwise upper_bound == lower_bound
1163 } else {
1164 return l;
1165 }
1166 }
1167 KBLIB_NODISCARD constexpr auto upper_bound(Key key) const& noexcept
1168 -> const_iterator {
1169 // if the key exists, upper_bound is the next one
1170 auto l = lower_bound(key);
1171 if (l.pos == index(key)) {
1172 return ++l;
1173 // otherwise upper_bound == lower_bound
1174 } else {
1175 return l;
1176 }
1177 }
1178
1179 KBLIB_NODISCARD constexpr static auto min() noexcept -> Key {
1181 }
1182 KBLIB_NODISCARD constexpr static auto max() noexcept -> Key {
1184 }
1185
1186 KBLIB_NODISCARD friend constexpr auto operator==(
1187 const direct_map& l,
1188 const direct_map& r) noexcept(noexcept(std::declval<T&>()
1189 == std::declval<T&>())) -> bool {
1190 if (l.size() != r.size()) {
1191 return false;
1192 }
1193 for (const key_type i : kblib::range(+min(), max() + 1)) {
1194 if (l.contains(i) != r.contains(i)) {
1195 return false;
1196 } else if (l.contains(i)) {
1197 if (l.at(i) != r.at(i)) {
1198 return false;
1199 }
1200 }
1201 }
1202 return true;
1203 }
1204
1205 KBLIB_NODISCARD friend constexpr auto operator!=(
1206 const direct_map& l,
1207 const direct_map& r) noexcept(noexcept(std::declval<T&>()
1208 == std::declval<T&>())) -> bool {
1209 return not (l == r);
1210 }
1211
1212 KBLIB_NODISCARD friend constexpr auto operator<(
1213 const direct_map& l,
1214 const direct_map& r) noexcept(noexcept(std::declval<T&>(),
1215 std::declval<T&>())) -> bool {
1216 return kblib::lexicographical_compare(l.begin(), l.end(), r.begin(),
1217 r.end());
1218 }
1219 KBLIB_NODISCARD friend constexpr auto operator>(
1220 const direct_map& l,
1221 const direct_map& r) noexcept(noexcept(std::declval<T&>(),
1222 std::declval<T&>())) -> bool {
1223 return r < l;
1224 }
1225 KBLIB_NODISCARD friend constexpr auto operator<=(
1226 const direct_map& l,
1227 const direct_map& r) noexcept(noexcept(std::declval<T&>(),
1228 std::declval<T&>())) -> bool {
1229 return not (r < l);
1230 }
1231 KBLIB_NODISCARD friend constexpr auto operator>=(
1232 const direct_map& l,
1233 const direct_map& r) noexcept(noexcept(std::declval<T&>(),
1234 std::declval<T&>())) -> bool {
1235 return not (l < r);
1236 }
1237
1238 KBLIB_NODISCARD constexpr static auto index(Key key) noexcept
1239 -> std::ptrdiff_t {
1240 return to_signed(key);
1241 }
1242 KBLIB_NODISCARD constexpr static auto uindex(Key key) noexcept
1243 -> std::size_t {
1244 return to_unsigned(key);
1245 }
1246 KBLIB_NODISCARD constexpr static auto to_key(std::ptrdiff_t i) noexcept
1247 -> Key {
1248 return Key(i);
1249 }
1250
1251 private:
1252 KBLIB_NODISCARD constexpr auto bitmap() noexcept -> std::bitset<key_range>& {
1253 return active_elems;
1254 }
1255 KBLIB_NODISCARD constexpr auto bitmap() const noexcept
1256 -> const std::bitset<key_range>& {
1257 return active_elems;
1258 }
1259
1260 KBLIB_NODISCARD constexpr auto unsafe_at(Key key) & -> storage_type& {
1261 return elems[uindex(key)];
1262 }
1263 KBLIB_NODISCARD constexpr auto unsafe_at(Key key) && -> storage_type&& {
1264 return elems[uindex(key)];
1265 }
1266 KBLIB_NODISCARD constexpr auto unsafe_at(Key key) const& -> const
1267 storage_type& {
1268 return elems[uindex(key)];
1269 }
1270 KBLIB_NODISCARD constexpr auto unsafe_at(Key key) const&& -> const
1271 storage_type&& {
1272 return elems[uindex(key)];
1273 }
1274
1275 template <typename... Args>
1276 constexpr auto construct(Key key, Args&&... args) noexcept(
1277 std::is_nothrow_constructible<value_type, Args&&...>::value) -> void {
1278 if (not active_elems.test(uindex(key))) {
1279 do_construct(key, std::forward<Args>(args)...);
1280 // doing these after construction maintains exception safety.
1281 active_elems.set(uindex(key));
1282 ++_size;
1283 }
1284 }
1285
1286 template <typename... Args>
1287 constexpr auto do_construct(Key key, Args&&... args) noexcept(
1288 std::is_nothrow_constructible<value_type, Args&&...>::value) -> void {
1289 elems[uindex(key)].construct(
1290 std::piecewise_construct, std::forward_as_tuple(key),
1291 std::forward_as_tuple(std::forward<Args>(args)...));
1292 }
1293
1294 auto destroy(Key key) -> void {
1295 assert(contains(key));
1296
1297 bitmap().reset(uindex(key));
1298 unsafe_at(key).destroy();
1299 --_size;
1300 }
1301
1302 // TODO(killerbee13): Implement, test, and document direct_map
1303
1304 std::bitset<key_range> active_elems;
1305 std::array<storage_type, key_range> elems;
1306
1307 std::size_t _size{};
1308};
1309
1310} // namespace KBLIB_NS
1311
1312#endif // DIRECT_MAP_H
KBLIB_NODISCARD constexpr auto count(Key key) const noexcept -> std::size_t
Definition: direct_map.h:1120
KBLIB_NODISCARD constexpr auto equal_range(Key key) &noexcept -> std::pair< iterator, iterator >
Definition: direct_map.h:1132
KBLIB_NODISCARD constexpr auto end() &noexcept -> iterator
Definition: direct_map.h:954
constexpr auto erase(iterator first, iterator last) noexcept -> iterator
Definition: direct_map.h:1074
KBLIB_NODISCARD static constexpr auto max() noexcept -> Key
Definition: direct_map.h:1182
KBLIB_NODISCARD constexpr auto contains(Key key) const noexcept -> bool
Definition: direct_map.h:1117
KBLIB_NODISCARD constexpr auto size() const &noexcept -> std::size_t
Definition: direct_map.h:992
KBLIB_NODISCARD constexpr auto at(Key key) const &-> const T &
Definition: direct_map.h:916
KBLIB_NODISCARD constexpr auto ssize() const &noexcept -> std::ptrdiff_t
Definition: direct_map.h:995
constexpr auto insert_or_assign(Key key, U &&value) -> std::pair< iterator, bool >
Definition: direct_map.h:1042
constexpr auto insert(U &&value) -> return_assert_t< std::is_constructible< value_type, U && >::value, std::pair< iterator, bool > >
Definition: direct_map.h:1022
KBLIB_NODISCARD constexpr auto upper_bound(Key key) &noexcept -> iterator
Definition: direct_map.h:1157
KBLIB_NODISCARD static constexpr auto min() noexcept -> Key
Definition: direct_map.h:1179
constexpr auto insert(const value_type &value) -> std::pair< iterator, bool >
Definition: direct_map.h:1013
KBLIB_NODISCARD static constexpr auto index(Key key) noexcept -> std::ptrdiff_t
Definition: direct_map.h:1238
KBLIB_NODISCARD constexpr auto rbegin() const &noexcept -> const_reverse_iterator
Definition: direct_map.h:967
iter< const value_type > const_iterator
Definition: direct_map.h:819
KBLIB_NODISCARD constexpr auto upper_bound(Key key) const &noexcept -> const_iterator
Definition: direct_map.h:1167
KBLIB_NODISCARD friend constexpr auto operator==(const direct_map &l, const direct_map &r) noexcept(noexcept(std::declval< T & >()==std::declval< T & >())) -> bool
Definition: direct_map.h:1186
constexpr auto erase(iterator pos) noexcept -> iterator
Definition: direct_map.h:1063
KBLIB_NODISCARD constexpr auto find(Key key) &noexcept -> iterator
Definition: direct_map.h:1124
KBLIB_NODISCARD constexpr auto find(Key key) const &noexcept -> const_iterator
Definition: direct_map.h:1127
constexpr auto clear() noexcept -> void
Definition: direct_map.h:1003
const value_type * const_pointer
Definition: direct_map.h:717
KBLIB_NODISCARD constexpr auto cbegin() const &noexcept -> const_iterator
Definition: direct_map.h:942
KBLIB_NODISCARD friend constexpr auto operator>=(const direct_map &l, const direct_map &r) noexcept(noexcept(std::declval< T & >(), std::declval< T & >())) -> bool
Definition: direct_map.h:1231
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: direct_map.h:821
constexpr auto operator=(direct_map &&other) noexcept(std::is_nothrow_move_constructible< T >::value) -> direct_map &
Definition: direct_map.h:878
KBLIB_NODISCARD constexpr auto rbegin() &noexcept -> reverse_iterator
Definition: direct_map.h:964
KBLIB_NODISCARD constexpr auto at(Key key) &&-> T &&
Definition: direct_map.h:909
KBLIB_NODISCARD constexpr auto crend() const &noexcept -> const_reverse_iterator
Definition: direct_map.h:983
constexpr direct_map(const direct_map &other)
Definition: direct_map.h:833
constexpr direct_map(direct_map &&other) noexcept(std::is_nothrow_move_constructible< value_type >::value)
Definition: direct_map.h:844
KBLIB_NODISCARD constexpr T & operator[](Key key) noexcept(std::is_nothrow_default_constructible< T >::value)
Definition: direct_map.h:931
KBLIB_NODISCARD constexpr auto at(Key key) &-> T &
Definition: direct_map.h:902
KBLIB_NODISCARD constexpr auto at(Key key) const &&-> const T &&
Definition: direct_map.h:923
std::reverse_iterator< iterator > reverse_iterator
Definition: direct_map.h:820
constexpr direct_map() noexcept=default
constexpr auto erase(Key key) noexcept -> std::size_t
Definition: direct_map.h:1083
KBLIB_NODISCARD friend constexpr auto operator>(const direct_map &l, const direct_map &r) noexcept(noexcept(std::declval< T & >(), std::declval< T & >())) -> bool
Definition: direct_map.h:1219
KBLIB_NODISCARD constexpr auto begin() const &noexcept -> const_iterator
Definition: direct_map.h:939
KBLIB_NODISCARD constexpr auto end() const &noexcept -> const_iterator
Definition: direct_map.h:957
constexpr direct_map(std::initializer_list< value_type > init)
Definition: direct_map.h:856
constexpr auto swap(direct_map &other) noexcept(std::is_nothrow_move_constructible< value_type >::value and fakestd::is_nothrow_swappable< T >::value) -> void
Definition: direct_map.h:1092
KBLIB_NODISCARD constexpr auto cend() const &noexcept -> const_iterator
Definition: direct_map.h:960
KBLIB_NODISCARD constexpr auto rend() const &noexcept -> const_reverse_iterator
Definition: direct_map.h:979
KBLIB_NODISCARD static constexpr auto max_size() noexcept -> std::size_t
Definition: direct_map.h:999
KBLIB_NODISCARD constexpr auto lower_bound(Key key) const &noexcept -> const_iterator
Definition: direct_map.h:1148
KBLIB_CXX20(constexpr) ~direct_map()
Definition: direct_map.h:861
KBLIB_NODISCARD friend constexpr auto operator<=(const direct_map &l, const direct_map &r) noexcept(noexcept(std::declval< T & >(), std::declval< T & >())) -> bool
Definition: direct_map.h:1225
KBLIB_NODISCARD static constexpr auto uindex(Key key) noexcept -> std::size_t
Definition: direct_map.h:1242
constexpr auto insert(value_type &&value) -> std::pair< iterator, bool >
Definition: direct_map.h:1032
KBLIB_NODISCARD constexpr auto empty() const &noexcept -> bool
Definition: direct_map.h:988
KBLIB_NODISCARD constexpr auto lower_bound(Key key) &noexcept -> iterator
Definition: direct_map.h:1141
KBLIB_NODISCARD constexpr auto rend() &noexcept -> reverse_iterator
Definition: direct_map.h:976
constexpr auto erase(const_iterator pos) noexcept -> iterator
Definition: direct_map.h:1068
KBLIB_NODISCARD friend constexpr auto operator!=(const direct_map &l, const direct_map &r) noexcept(noexcept(std::declval< T & >()==std::declval< T & >())) -> bool
Definition: direct_map.h:1205
constexpr auto operator=(const direct_map &other) -> direct_map &
Definition: direct_map.h:863
constexpr auto operator=(std::initializer_list< value_type > init) -> direct_map &
Definition: direct_map.h:893
KBLIB_NODISCARD constexpr auto begin() &noexcept -> iterator
Definition: direct_map.h:936
const value_type & const_reference
Definition: direct_map.h:715
KBLIB_NODISCARD friend constexpr auto operator<(const direct_map &l, const direct_map &r) noexcept(noexcept(std::declval< T & >(), std::declval< T & >())) -> bool
Definition: direct_map.h:1212
std::pair< const Key, T > value_type
Definition: direct_map.h:710
KBLIB_NODISCARD static constexpr auto to_key(std::ptrdiff_t i) noexcept -> Key
Definition: direct_map.h:1246
KBLIB_NODISCARD constexpr auto equal_range(Key key) const &noexcept -> std::pair< const_iterator, const_iterator >
Definition: direct_map.h:1136
constexpr auto try_emplace(Key key, Args &&... args) -> std::pair< iterator, bool >
Definition: direct_map.h:1053
KBLIB_NODISCARD constexpr auto crbegin() const &noexcept -> const_reverse_iterator
Definition: direct_map.h:971
iter< value_type > iterator
Definition: direct_map.h:240
KBLIB_NODISCARD constexpr auto rend() const &noexcept -> auto
Definition: direct_map.h:385
constexpr auto insert(const value_type &value) -> std::pair< iterator, bool >
Definition: direct_map.h:421
KBLIB_NODISCARD constexpr auto begin() const &noexcept -> const_iterator
Definition: direct_map.h:347
constexpr auto insert_or_assign(Key key, U &&value) -> std::pair< iterator, bool >
Definition: direct_map.h:450
constexpr auto clear() noexcept -> void
Definition: direct_map.h:407
constexpr direct_map(const direct_map &other)
Definition: direct_map.h:258
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: direct_map.h:243
KBLIB_NODISCARD constexpr auto size() const &noexcept -> std::size_t
Definition: direct_map.h:396
KBLIB_NODISCARD constexpr auto crbegin() const &noexcept -> auto
Definition: direct_map.h:378
constexpr auto erase(iterator pos) noexcept -> iterator
Definition: direct_map.h:471
KBLIB_NODISCARD constexpr auto at(Key key) const &-> const T &
Definition: direct_map.h:324
KBLIB_NODISCARD constexpr auto rbegin() const &noexcept -> auto
Definition: direct_map.h:375
value_type * pointer
Definition: direct_map.h:136
constexpr auto operator=(const direct_map &other) -> direct_map &
Definition: direct_map.h:284
KBLIB_NODISCARD constexpr auto find(Key key) &noexcept -> iterator
Definition: direct_map.h:521
constexpr auto erase(const_iterator pos) noexcept -> iterator
Definition: direct_map.h:478
KBLIB_NODISCARD constexpr auto upper_bound(Key key) const &noexcept -> const_iterator
Definition: direct_map.h:564
KBLIB_NODISCARD constexpr auto rend() &noexcept -> auto
Definition: direct_map.h:382
KBLIB_NODISCARD friend constexpr auto operator==(const direct_map &l, const direct_map &r) noexcept(noexcept(std::declval< T & >()==std::declval< T & >())) -> bool
Definition: direct_map.h:583
KBLIB_NODISCARD constexpr auto rbegin() &noexcept -> auto
Definition: direct_map.h:372
KBLIB_NODISCARD constexpr auto equal_range(Key key) const &noexcept -> std::pair< const_iterator, const_iterator >
Definition: direct_map.h:533
KBLIB_NODISCARD constexpr auto end() const &noexcept -> const_iterator
Definition: direct_map.h:365
constexpr auto erase(iterator first, iterator last) noexcept -> iterator
Definition: direct_map.h:486
KBLIB_NODISCARD friend constexpr auto operator>=(const direct_map &l, const direct_map &r) noexcept(noexcept(std::declval< T & >(), std::declval< T & >())) -> bool
Definition: direct_map.h:628
KBLIB_NODISCARD constexpr auto contains(Key key) const noexcept -> bool
Definition: direct_map.h:514
KBLIB_NODISCARD constexpr auto begin() &noexcept -> iterator
Definition: direct_map.h:344
KBLIB_NODISCARD static constexpr auto max_size() noexcept -> std::size_t
Definition: direct_map.h:403
KBLIB_NODISCARD constexpr auto ssize() const &noexcept -> std::ptrdiff_t
Definition: direct_map.h:399
value_type & reference
Definition: direct_map.h:134
std::size_t size_type
Definition: direct_map.h:131
KBLIB_NODISCARD constexpr auto cbegin() const &noexcept -> const_iterator
Definition: direct_map.h:350
constexpr auto try_emplace(Key key, Args &&... args) -> std::pair< iterator, bool >
Definition: direct_map.h:461
KBLIB_NODISCARD static constexpr auto uindex(Key key) noexcept -> std::size_t
Definition: direct_map.h:639
KBLIB_NODISCARD static constexpr auto max() noexcept -> Key
Definition: direct_map.h:579
constexpr auto swap(direct_map &other) noexcept -> void
Definition: direct_map.h:508
KBLIB_NODISCARD constexpr auto empty() const &noexcept -> bool
Definition: direct_map.h:392
KBLIB_NODISCARD friend constexpr auto operator>(const direct_map &l, const direct_map &r) noexcept(noexcept(std::declval< T & >(), std::declval< T & >())) -> bool
Definition: direct_map.h:616
KBLIB_NODISCARD constexpr auto at(Key key) &&-> T &&
Definition: direct_map.h:317
KBLIB_NODISCARD constexpr auto at(Key key) const &&-> const T &&
Definition: direct_map.h:331
KBLIB_NODISCARD constexpr auto end() &noexcept -> iterator
Definition: direct_map.h:362
KBLIB_NODISCARD constexpr auto equal_range(Key key) &noexcept -> std::pair< iterator, iterator >
Definition: direct_map.h:529
std::ptrdiff_t difference_type
Definition: direct_map.h:132
constexpr direct_map(std::initializer_list< value_type > init)
Definition: direct_map.h:276
std::pair< const Key, T > value_type
Definition: direct_map.h:130
KBLIB_NODISCARD constexpr auto upper_bound(Key key) &noexcept -> iterator
Definition: direct_map.h:554
const value_type * const_pointer
Definition: direct_map.h:137
KBLIB_NODISCARD static constexpr auto min() noexcept -> Key
Definition: direct_map.h:576
KBLIB_CXX20(constexpr) ~direct_map()
Definition: direct_map.h:282
KBLIB_NODISCARD friend constexpr auto operator<=(const direct_map &l, const direct_map &r) noexcept(noexcept(std::declval< T & >(), std::declval< T & >())) -> bool
Definition: direct_map.h:622
constexpr auto operator=(direct_map &&other) noexcept -> direct_map &=default
constexpr auto operator=(std::initializer_list< value_type > init) -> direct_map &
Definition: direct_map.h:301
KBLIB_NODISCARD constexpr auto cend() const &noexcept -> const_iterator
Definition: direct_map.h:368
std::reverse_iterator< iterator > reverse_iterator
Definition: direct_map.h:242
KBLIB_NODISCARD constexpr auto crend() const &noexcept -> auto
Definition: direct_map.h:388
KBLIB_NODISCARD constexpr auto find(Key key) const &noexcept -> const_iterator
Definition: direct_map.h:524
constexpr auto erase(Key key) noexcept -> std::size_t
Definition: direct_map.h:497
KBLIB_NODISCARD constexpr auto at(Key key) &-> T &
Definition: direct_map.h:310
KBLIB_NODISCARD friend constexpr auto operator!=(const direct_map &l, const direct_map &r) noexcept(noexcept(std::declval< T & >()==std::declval< T & >())) -> bool
Definition: direct_map.h:602
KBLIB_NODISCARD constexpr auto lower_bound(Key key) &noexcept -> iterator
Definition: direct_map.h:538
constexpr auto insert(value_type &&value) -> std::pair< iterator, bool >
Definition: direct_map.h:440
KBLIB_NODISCARD constexpr T & operator[](Key key) noexcept(std::is_nothrow_default_constructible< T >::value)
Definition: direct_map.h:339
iter< const value_type > const_iterator
Definition: direct_map.h:241
KBLIB_NODISCARD friend constexpr auto operator<(const direct_map &l, const direct_map &r) noexcept(noexcept(std::declval< T & >(), std::declval< T & >())) -> bool
Definition: direct_map.h:609
KBLIB_NODISCARD static constexpr auto index(Key key) noexcept -> std::ptrdiff_t
Definition: direct_map.h:635
constexpr auto insert(U &&value) -> enable_if_t< std::is_constructible< value_type, U && >::value, std::pair< iterator, bool > >
Definition: direct_map.h:430
constexpr direct_map() noexcept=default
KBLIB_NODISCARD constexpr auto lower_bound(Key key) const &noexcept -> const_iterator
Definition: direct_map.h:545
constexpr direct_map(direct_map &&other) noexcept
Definition: direct_map.h:272
KBLIB_NODISCARD constexpr auto count(Key key) const noexcept -> std::size_t
Definition: direct_map.h:517
KBLIB_NODISCARD static constexpr auto to_key(std::ptrdiff_t i) noexcept -> Key
Definition: direct_map.h:643
const value_type & const_reference
Definition: direct_map.h:135
#define DECL_OP(op)
Definition: direct_map.h:799
#define LAUNDER(x)
Definition: direct_map.h:90
This header provides some features of C++17 <type_traits> and other headers for C++14,...
This file provides some iterators, ranges, iterator/range adapters, and operations that can be perfor...
KBLIB_CONSTANT auto range_of
Definition: direct_map.h:56
constexpr struct kblib::nums::min_t min
constexpr struct kblib::nums::max_t max
constexpr auto contains(InputIt begin, InputIt end, const Value &val) noexcept(noexcept(*begin==val)) -> enable_if_t< is_input_iterator< InputIt >::value, bool >
Determine if a range contains a value.
Definition: algorithm.h:1052
constexpr auto exchange(T &obj, U &&new_value) -> T
Definition: fakestd.h:725
auto map(F f, T &&... t) noexcept(noexcept(std::tuple{ kblib::apply(f, std::forward< T >(t))...})) -> enable_if_t< not any_void< decltype(kblib::apply(f, std::forward< T >(t)))... >, decltype(std::tuple{kblib::apply(f, std::forward< T >(t))...})>
Definition: simple.h:75
constexpr auto to_signed(I x) -> std::make_signed_t< I >
Cast integral argument to corresponding signed type.
Definition: fakestd.h:599
typename std::enable_if< B, T >::type enable_if_t
Definition: fakestd.h:61
struct kblib::@0 swap
constexpr auto range(Value min, Value max, Delta step=0) -> range_t< Value, Delta >
Constructs a range from beginning, end, and step amount. The range is half-open, that is min is in th...
Definition: iterators.h:621
constexpr auto indirect(Iter1 begin, Iter2 end) noexcept(noexcept(indirect_range< Iter1, Iter2 >{begin, end})) -> indirect_range< Iter1, Iter2 >
Create a range from an iterator pair. Primarily useful for range-for loops.
Definition: iterators.h:1060
auto get(punner< Types... > &p) noexcept -> decltype(auto)
Definition: bits.h:737
constexpr auto find(ForwardIt begin, EndIt end, const Elem &value) noexcept(noexcept(*begin==value)) -> ForwardIt
Finds a value in range [begin, end). If not found, returns end. It also allows for a sentinel end ite...
Definition: algorithm.h:290
typename return_assert< V, T >::type return_assert_t
Definition: fakestd.h:550
constexpr auto operator*(construct_type l, bool r) noexcept -> construct_type
Definition: poly_obj.h:60
constexpr auto lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2) -> bool
Definition: fakestd.h:1086
constexpr struct kblib::in_place_agg_t in_place_agg
typename copy_const< C, V >::type copy_const_t
Definition: fakestd.h:877
constexpr auto to_unsigned(I x) -> std::make_unsigned_t< I >
Cast integral argument to corresponding unsigned type.
Definition: fakestd.h:592
Definition: bits.h:721
Definition: traits.cpp:4
constexpr auto destroy() noexcept -> void
Definition: direct_map.h:114
KBLIB_NODISCARD constexpr auto get() &noexcept -> T *
Definition: direct_map.h:116
KBLIB_NODISCARD constexpr auto get() const &noexcept -> const T *
Definition: direct_map.h:117
constexpr auto construct(Args &&... args) noexcept(std::is_nothrow_constructible< T, Args &&... >::value) -> T &
Definition: direct_map.h:109
constexpr auto construct(Args &&... args) noexcept(std::is_nothrow_constructible< T, Args &&... >::value) -> T &
Definition: direct_map.h:72
KBLIB_NODISCARD constexpr auto get() &noexcept -> T *
Definition: direct_map.h:92
auto operator=(storage_for &&) -> storage_for &=delete
storage_for(storage_for &&)=delete
auto operator=(const storage_for &) -> storage_for &=delete
KBLIB_NODISCARD constexpr auto get() const &noexcept -> const T *
Definition: direct_map.h:95
storage_for(const storage_for &)=delete
constexpr auto destroy() noexcept -> void
Definition: direct_map.h:85
Provides macros and basic templates used by the rest of kblib.
#define KBLIB_CONSTANT
Definition: tdecl.h:137
#define KBLIB_NS
Definition: tdecl.h:113
#define KBLIB_NODISCARD
This internal macro is used to provide a fallback for [[nodiscard]] in C++14.
Definition: tdecl.h:129