YSTest: tree.h 源文件

YSTest PreAlpha_b900_20201012 The YSLib Test Project

tree.h
浏览该文件的文档.
1 /*
2 © 2018-2020 FrankHB.
3
4 This file is part of the YSLib project, and may only be used,
5 modified, and distributed under the terms of the YSLib project
6 license, LICENSE.TXT. By continuing to use, modify, or distribute
7 this file you indicate that you have read the license and
8 understand and accept it fully.
9 */
10
39 #ifndef YB_INC_ystdex_tree_hpp_
40 #define YB_INC_ystdex_tree_hpp_ 1
41
42 #include "allocator.hpp" // for allocator_traits, is_move_assignable,
43 // ystdex::swap_dependent, YAssert, yassume, yconstraint, true_, false_,
44 // std::pointer_traits, is_nothrow_copy_constructible, aligned_storage_t,
45 // standard_layout_storage, std::allocator, std::bidirectional_iterator_tag,
46 // rebind_alloc_t, ystdex::reverse_iterator, is_same, cond_t,
47 // is_nothrow_move_assignable, or_, and_, is_invocable, std::declval,
48 // ystdex::alloc_on_copy, std::move_if_noexcept,
49 // is_trivially_default_constructible, allocator_guard_delete, allocator_guard,
50 // is_trivially_destructible, std::pair, enable_if_t, is_nothrow_swappable,
51 // ystdex::alloc_on_swap, ystdex::alloc_on_move;
52 #include "optional.h" // for optional, bidirectional_iteratable,
53 // equality_comparable, totally_ordered, has_mem_is_transparent;
54 #include "utility.hpp" // for noncopyable, ystdex::as_const;
55 #include "iterator_trait.hpp" // for has_iterator_value_type;
56 #include <algorithm> // for std::equal, std::lexicographical_compare;
57
58 namespace ystdex
59 {
60
62
63 namespace details
64 {
65
66 inline namespace rb_tree
67 {
68
69 template<typename, typename, typename, typename, class>
70 class tree;
71
72 } // unnamed namespace;
73
75 //{@
77 template<typename _type, class _tNodeAlloc>
78 class node_handle_base
79 {
80 template<typename, typename, typename, typename, class>
81 friend class tree;
82
83 public:
84 using allocator_type = rebind_alloc_t<_tNodeAlloc, _type>;
85
86 private:
88 using node_ator_traits = allocator_traits<_tNodeAlloc>;
89
90 optional<_tNodeAlloc> alloc{};
91
92 protected:
93 typename node_ator_traits::pointer ptr{};
94
95 yconstfn
96 node_handle_base() ynothrow = default;
97 ~node_handle_base()
98 {
99 destroy();
100 }
101
102 node_handle_base(node_handle_base&& nh) ynothrow
103 : alloc(std::move(nh.alloc)), ptr(nh.ptr)
104 {
105 nh.ptr = {};
106 nh.alloc = nullopt;
107 }
108 node_handle_base(typename node_ator_traits::pointer p, const _tNodeAlloc& a)
109 : ptr(p), alloc(a)
110 {}
111
112 node_handle_base&
113 operator=(node_handle_base&& nh) ynothrow
114 {
115 destroy();
116 ptr = nh.ptr;
117 move_assign(nh, is_move_assignable<_tNodeAlloc>());
118 yunseq(nh.ptr = {}, nh.alloc = nullopt);
119 return *this;
120 }
121
122 public:
123 explicit
124 operator bool() const ynothrow
125 {
126 return ptr;
127 }
128
129 protected:
130 void
131 swap_base(node_handle_base& nh) ynothrow
132 {
133 ystdex::swap_dependent(ptr, nh.ptr);
134 if(node_ator_traits::propagate_on_container_swap::value || !alloc
135 || !nh.alloc)
136 alloc.swap(nh.alloc);
137 else
138 YAssert(alloc == nh.alloc, "Unequal allocators found.");
139 }
140
141 private:
142 void
143 destroy() ynothrow
144 {
145 if(ptr)
146 {
147 allocator_type a(*alloc);
148
149 allocator_traits<allocator_type>::destroy(a, ptr->access_ptr());
150 node_ator_traits::deallocate(*alloc, ptr, 1);
151 }
152 }
153
154 public:
155 allocator_type
156 get_allocator() const ynothrow
157 {
158 yconstraint(!this->empty());
159 return allocator_type(*alloc);
160 }
161
162 YB_ATTR_nodiscard bool
163 empty() const ynothrow
164 {
165 return !ptr;
166 }
167
168 void
169 move_assign(node_handle_base& nh, true_)
170 {
171 if(node_ator_traits::propagate_on_container_move_assignment() || !alloc)
172 alloc = std::move(nh.alloc);
173 else
174 YAssert(alloc == nh.alloc, "Unequal allocators found.");
175 }
176 void
177 move_assign(false_)
178 {
179 yassume(alloc);
180 }
181 };
182
183
185 template<typename _tKey, typename _type, typename _tNodeAlloc>
186 class node_handle : public node_handle_base<_type, _tNodeAlloc>
187 {
188 template<typename, typename, typename, typename, class>
189 friend class tree;
190 // TODO: Add unordered associative container support?
191
192 private:
194 using ator_traits = allocator_traits<_tNodeAlloc>;
195 template<typename _tObj>
196 using ptr_t = typename std::pointer_traits<typename
197 ator_traits::pointer>::template rebind<remove_reference_t<_tObj>>;
198
199 ptr_t<_tKey> p_key = {};
200 ptr_t<typename _type::second_type> p_mapped = {};
201
202 public:
203 yconstfn
204 node_handle() ynothrow = default;
205
206 private:
207 node_handle(typename ator_traits::pointer p, const _tNodeAlloc& a)
208 : node_handle_base<_type, _tNodeAlloc>(p, a)
209 {
210 if(p)
211 {
212 auto& k(const_cast<_tKey&>(p->access_ptr()->first));
213
214 p_key = pointer_to(k);
215 p_mapped = pointer_to(p->access_ptr()->second);
216 }
217 else
218 {
219 p_key = {};
220 p_mapped = {};
221 }
222 }
223
224 public:
225 node_handle(node_handle&&) ynothrow = default;
226 ~node_handle() = default;
227
228 node_handle&
229 operator=(node_handle&&) ynothrow = default;
230
231 using key_type = _tKey;
232 using mapped_type = typename _type::second_type;
233
234 const key_type&
235 ckey() const ynothrowv
236 {
237 return key();
238 }
239
240 key_type&
241 key() const ynothrowv
242 {
243 yconstraint(!this->empty());
244 return *p_key;
245 }
246
247 mapped_type&
248 mapped() const ynothrowv
249 {
250 yconstraint(!this->empty());
251 return *p_mapped;
252 }
253
254 void
255 swap(node_handle& nh) ynothrow
256 {
257 this->swap_base(nh);
258 ystdex::swap_dependent(p_key, nh.p_key);
259 ystdex::swap_dependent(p_mapped, nh.p_mapped);
260 }
261
262 friend void
263 swap(node_handle& x, node_handle& y) ynoexcept_spec(x.swap(y))
264 {
265 x.swap(y);
266 }
267
268 private:
269 template<typename _tObj>
270 inline ptr_t<_tObj>
271 pointer_to(_tObj& obj)
272 {
273 return std::pointer_traits<ptr_t<_type>>::pointer_to(obj);
274 }
275 };
276
277
279 template<typename _type, typename _tNodeAlloc>
280 class node_handle<_type, _type, _tNodeAlloc>
281 : public node_handle_base<_type, _tNodeAlloc>
282 {
283 template<typename, typename, typename, typename, class>
284 friend class tree;
285 // TODO: Add unordered associative container support?
286
287 private:
289 using ator_traits = allocator_traits<_tNodeAlloc>;
290
291 public:
292 using value_type = _type;
293
294 yconstfn
295 node_handle() ynothrow = default;
296
297 private:
298 node_handle(typename ator_traits::pointer p, const _tNodeAlloc& a)
299 : node_handle_base<_type, _tNodeAlloc>(p, a)
300 {}
301
302 public:
303 ~node_handle() = default;
304 node_handle(node_handle&&) ynothrow = default;
305
306 node_handle&
307 operator=(node_handle&&) ynothrow = default;
308
309 value_type&
310 value() const ynothrowv
311 {
312 yconstraint(!this->empty());
313 return *this->ptr->access_ptr();
314 }
315
316 const value_type&
317 ckey() const ynothrowv
318 {
319 return value();
320 }
321
322 friend void
323 swap(node_handle& x, node_handle& y) ynothrow
324 {
325 x->swap_base(y);
326 }
327 };
328
329
331 template<typename _tIter, typename _tNodeHandle>
332 struct node_insert_return
333 {
334 _tIter position = _tIter();
335 bool inserted = {};
336 _tNodeHandle node;
337 };
339
340
341 inline namespace rb_tree
342 {
343
344 enum class tree_color : bool
345 {
346 red = false,
347 black = true
348 };
349
350
352
353 struct tree_node_base
354 {
355 using base_ptr = tree_node_base*;
356 using const_base_ptr = const tree_node_base*;
357
358 // XXX: Uninitialized.
359 tree_color color;
360 base_ptr parent, left, right;
361
362 YB_PURE static base_ptr
363 maximum(base_ptr x) ynothrow
364 {
365 while(x->right)
366 x = x->right;
367 return x;
368 }
369 YB_PURE static const_base_ptr
370 maximum(const_base_ptr x) ynothrow
371 {
372 while(x->right)
373 x = x->right;
374 return x;
375 }
376
377 YB_PURE static base_ptr
378 minimum(base_ptr x) ynothrow
379 {
380 while(x->left)
381 x = x->left;
382 return x;
383 }
384 YB_PURE static const_base_ptr
385 minimum(const_base_ptr x) ynothrow
386 {
387 while(x->left)
388 x = x->left;
389 return x;
390 }
391
393 void
394 initialize() ynothrow
395 {
396 reset_links();
397 color = tree_color::red;
398 }
399
400 void
401 reset_links() ynothrow
402 {
403 parent = {};
404 left = this;
405 right = this;
406 }
407 };
408
409
410 // TODO: Optimize once %is_final is supported.
411 template<typename _tKeyComp>
412 struct tree_key_compare
413 {
414 _tKeyComp key_compare{};
415
417 tree_key_compare() ynoexcept_spec(_tKeyComp())
418 {}
419 tree_key_compare(const _tKeyComp& comp)
420 : key_compare(comp)
421 {}
422 tree_key_compare(const tree_key_compare&) = default;
423 // NOTE: As per ISO C++17 [associative.reqmts], the comparison object shall
424 // be copy constructible.
425 // XXX: This is copied.
426 tree_key_compare(tree_key_compare&& x)
427 ynoexcept(is_nothrow_copy_constructible<_tKeyComp>())
428 : key_compare(x.key_compare)
429 {}
430 };
431
432
433 struct tree_header : tree_node_base
434 {
435 size_t node_count;
436
437 tree_header() ynothrow
438 : node_count(0)
439 {
440 initialize();
441 }
442 tree_header(tree_header&& x) ynothrow
443 {
444 if(x.parent)
445 move_data(x);
446 else
447 {
448 initialize();
449 node_count = 0;
450 }
451 }
452
454 void
455 move_data(tree_header& from) ynothrow
456 {
457 base() = from.base();
458 yunseq(parent->parent = &base(), node_count = from.node_count);
459 from.reset();
460 }
461
463 void
464 reset() ynothrow
465 {
466 reset_links();
467 node_count = 0;
468 }
469
471 YB_ATTR_nodiscard YB_PURE tree_node_base&
472 base() ynothrow
473 {
474 return *this;
475 }
476 };
477
478
479 template<typename _type>
480 class tree_node : public tree_node_base
481 {
482 private:
483 standard_layout_storage<aligned_storage_t<sizeof(_type), yalignof(_type)>>
484 storage;
485
486 public:
487 YB_PURE yconstfn_relaxed YB_PURE _type*
488 access_ptr()
489 {
490 return static_cast<_type*>(storage.access());
491 }
492 YB_PURE yconstfn YB_PURE const _type*
493 access_ptr() const
494 {
495 return static_cast<const _type*>(storage.access());
496 }
497 };
499
500
501 YB_API YB_PURE tree_node_base*
502 tree_increment(tree_node_base*) ynothrow;
503 YB_API YB_PURE const tree_node_base*
504 tree_increment(const tree_node_base*) ynothrow;
505
506 YB_API YB_PURE tree_node_base*
507 tree_decrement(tree_node_base*) ynothrow;
508 YB_API YB_PURE const tree_node_base*
509 tree_decrement(const tree_node_base*) ynothrow;
510
511
513
514 template<typename, typename _type, class, typename,
515 class = std::allocator<_type>>
516 class tree;
517
518 template<typename>
519 class tree_const_iterator;
520
521
522 template<typename _type>
523 class tree_iterator
524 : public bidirectional_iteratable<tree_iterator<_type>, _type&>
525 {
526 // XXX: Partial specialization is not allowed here by ISO C++.
527 template<typename, typename, class, typename, class>
528 friend class tree;
529 template<typename>
530 friend class tree_const_iterator;
531
532 public:
533 using iterator_category = std::bidirectional_iterator_tag;
534 using value_type = _type;
535 using pointer = _type*;
536 using reference = _type&;
537 using difference_type = ptrdiff_t;
538
539 private:
541 using base_ptr = tree_node_base::base_ptr;
543 using link_type = tree_node<_type>*;
544
545 base_ptr p_node = {};
546
547 public:
548 tree_iterator() ynothrow = default;
549 explicit
550 tree_iterator(base_ptr x) ynothrow
551 : p_node(x)
552 {}
553
554 YB_ATTR_nodiscard YB_PURE reference
555 operator*() const ynothrow
556 {
557 return *link_type(p_node)->access_ptr();
558 }
559
560 tree_iterator&
561 operator++() ynothrow
562 {
563 p_node = tree_increment(p_node);
564 return *this;
565 }
566
567 tree_iterator&
568 operator--() ynothrow
569 {
570 p_node = tree_decrement(p_node);
571 return *this;
572 }
573
574 YB_ATTR_nodiscard YB_PURE bool
575 operator==(const tree_iterator& x) const ynothrow
576 {
577 return p_node == x.p_node;
578 }
579 };
580
581
582 template<typename _type>
583 class tree_const_iterator
584 : public bidirectional_iteratable<tree_const_iterator<_type>, const _type&>,
585 public equality_comparable<tree_const_iterator<_type>, tree_iterator<_type>>
586 {
587 // XXX: Partial specialization is not allowed here by ISO C++.
588 template<typename, typename, class, typename, class>
589 friend class tree;
590
591 public:
592 using iterator_category = std::bidirectional_iterator_tag;
593 using value_type = _type;
594 using pointer = const _type*;
595 using reference = const _type&;
596 using difference_type = ptrdiff_t;
597
598 private:
600 using iterator = tree_iterator<_type>;
602 using base_ptr = tree_node_base::const_base_ptr;
604 using link_type = const tree_node<_type>*;
605
606 base_ptr p_node = {};
607
608 public:
609 tree_const_iterator() ynothrow = default;
610 explicit
611 tree_const_iterator(base_ptr x) ynothrow
612 : p_node(x)
613 {}
614 tree_const_iterator(const iterator& it) ynothrow
615 : p_node(it.p_node)
616 {}
617
618 YB_ATTR_nodiscard YB_PURE iterator
619 cast_mutable() const ynothrow
620 {
621 return iterator(const_cast<typename iterator::base_ptr>(p_node));
622 }
623
624 YB_ATTR_nodiscard YB_PURE reference
625 operator*() const ynothrow
626 {
627 return *link_type(p_node)->access_ptr();
628 }
629
630 tree_const_iterator&
631 operator++() ynothrow
632 {
633 p_node = tree_increment(p_node);
634 return *this;
635 }
636
637 tree_const_iterator&
638 operator--() ynothrow
639 {
640 p_node = tree_decrement(p_node);
641 return *this;
642 }
643
644 YB_ATTR_nodiscard YB_PURE bool
645 operator==(const tree_const_iterator& x) const ynothrow
646 {
647 return p_node == x.p_node;
648 }
649 YB_ATTR_nodiscard YB_PURE bool
650 operator==(const iterator& x) const ynothrow
651 {
652 return p_node == x.p_node;
653 }
654 };
656
657
658 YB_API void
659 tree_insert_and_rebalance(bool, tree_node_base*, tree_node_base*,
660 tree_node_base&) ynothrow;
661
662 YB_API tree_node_base*
663 tree_rebalance_for_erase(tree_node_base*, tree_node_base&) ynothrow;
664
665 YB_API YB_PURE size_t
666 tree_black_count(const tree_node_base*, const tree_node_base*) ynothrow;
667
668
669 template<typename, typename>
670 struct tree_merge_helper
671 {
672 ~tree_merge_helper() = delete;
673 };
674
675
677 template<typename _tKey, typename _type, typename _fKeyOfValue, typename _fComp,
678 class _tAlloc>
679 class tree
680 : private totally_ordered<tree<_tKey, _type, _fKeyOfValue, _fComp, _tAlloc>>
681 {
682 static_assert(is_invocable<_fComp&, const _tKey&, const _tKey&>(),
683 "Invalid comparison object type found.");
684 // XXX: LWG 2542.
685 static_assert(is_invocable<const _fComp&, const _tKey&, const _tKey&>(),
686 "Invalid comparison object type found.");
687
688 template<typename, typename>
689 friend struct tree_merge_helper;
690
691 public:
692 using key_type = _tKey;
693 using value_type = _type;
694 using pointer = value_type*;
695 using const_pointer = const value_type*;
696 using reference = value_type&;
697 using const_reference = const value_type&;
698 using size_type = size_t;
699 using difference_type = ptrdiff_t;
704 using allocator_type = _tAlloc;
705 using iterator = tree_iterator<value_type>;
706 using const_iterator = tree_const_iterator<value_type>;
707 using reverse_iterator = ystdex::reverse_iterator<iterator>;
708 using const_reverse_iterator = ystdex::reverse_iterator<const_iterator>;
709
710 private:
712 using value_node = tree_node<value_type>;
713 using node_allocator = rebind_alloc_t<_tAlloc, value_node>;
714
715 public:
716 using node_type = node_handle<_tKey, _type, node_allocator>;
717 using insert_return_type = node_insert_return<
718 cond_t<is_same<_tKey, _type>, const_iterator, iterator>, node_type>;
719
720 protected:
721 using base_ptr = tree_node_base*;
722 using const_base_ptr = const tree_node_base*;
723 using link_type = value_node*;
724 using const_link_type = const value_node*;
725
726 private:
728 using node_ator_traits = allocator_traits<node_allocator>;
730 using equal_alloc_or_pocma = or_<typename node_ator_traits::is_always_equal,
731 typename node_ator_traits::propagate_on_container_move_assignment>;
732 struct alloc_node
733 {
734 tree& tree_ref;
735
736 alloc_node(tree& t)
737 : tree_ref(t)
738 {}
739
740 template<typename _tParam>
741 inline link_type
742 operator()(_tParam&& arg) const
743 {
744 return tree_ref.create_node(yforward(arg));
745 }
746
747 template<typename _tParam>
748 link_type
749 reconstruct(base_ptr p, _tParam&& arg) const
750 {
751 const auto nd = link_type(p);
752
753 tree_ref.destroy_node(nd);
754 tree_ref.construct_node(nd, yforward(arg));
755 return nd;
756 }
757 };
758 struct reuse_or_alloc_node : protected alloc_node, private noncopyable
759 {
760 mutable base_ptr root;
761 mutable base_ptr nodes;
762
763 reuse_or_alloc_node(tree& t)
764 : alloc_node(t), root(t.root()), nodes(t.rightmost())
765 {
766 if(root)
767 {
768 root->parent = {};
769 if(nodes->left)
770 nodes = nodes->left;
771 }
772 else
773 nodes = {};
774 }
775 ~reuse_or_alloc_node()
776 {
777 alloc_node::tree_ref.erase_node(link_type(root));
778 }
779
780 template<typename _tParam>
781 link_type
782 operator()(_tParam&& arg) const
783 {
784 if(nodes)
785 return alloc_node::reconstruct(adjust(), yforward(arg));
786 return alloc_node::operator()(yforward(arg));
787 }
788
790 base_ptr
791 adjust() const
792 {
793 auto node(nodes);
794
795 nodes = nodes->parent;
796 if(nodes)
797 {
798 if(nodes->right == node)
799 {
800 nodes->right = {};
801 if(nodes->left)
802 {
803 nodes = nodes->left;
804 while(nodes->right)
805 nodes = nodes->right;
806 if(nodes->left)
807 nodes = nodes->left;
808 }
809 }
810 else
811 nodes->left = {};
812 }
813 else
814 root = {};
815 return node;
816 }
817 };
818 template<typename _fComp2>
819 using compatible_tree_type
820 = tree<_tKey, _type, _fKeyOfValue, _fComp2, _tAlloc>;
821
822 protected:
823 // TODO: Resolve LWG 2112 with %is_final support.
824 template<typename _tKeyComp>
825 struct components : node_allocator, tree_key_compare<_tKeyComp>
826 {
827 using base_key_compare = tree_key_compare<_tKeyComp>;
828
829 tree_header header{};
830
832 components() ynoexcept(
833 noexcept(node_allocator()) && noexcept(base_key_compare()))
834 : node_allocator(), base_key_compare()
835 {}
837 explicit
838 components(node_allocator a) ynothrow
839 : node_allocator(std::move(a))
840 {}
841 components(const _tKeyComp& comp, node_allocator&& a)
842 : node_allocator(std::move(a)), base_key_compare(comp)
843 {}
844 components(const components& x)
845 : node_allocator(
846 node_ator_traits::select_on_container_copy_construction(x)),
847 base_key_compare(x.key_compare)
848 {}
849 components(components&&) = default;
851 components(components&& x, node_allocator a)
852 : node_allocator(std::move(a)), base_key_compare(std::move(x)),
853 header(std::move(x.header))
854 {}
855
857 void
858 move_data(components& from) ynothrow
859 {
860 header.move_data(from.header);
861 }
862 };
863
864 components<_fComp> objects;
865
866 public:
867 tree() = default;
868 tree(const allocator_type& a)
869 : objects(node_allocator(a))
870 {}
871 tree(const _fComp& comp, const allocator_type& a = allocator_type())
872 : objects(comp, node_allocator(a))
873 {}
874 tree(const tree& x)
875 : objects(x.objects)
876 {
877 if(x.root())
878 root() = copy_node(x);
879 }
880 tree(const tree& x, const allocator_type& a)
881 : objects(x.objects.key_compare, node_allocator(a))
882 {
883 if(x.root())
884 root() = copy_node(x);
885 }
886 tree(tree&&) = default;
887 tree(tree&& x, const allocator_type& a)
888 : tree(std::move(x), node_allocator(a))
889 {}
891
892 tree(tree&& x, node_allocator&& a)
893 // XXX: %is_nothrow_constructible is not usable for the incomplete type.
894 ynoexcept(noexcept(tree(std::move(x),
895 std::move(a), typename node_ator_traits::is_always_equal())))
896 : tree(std::move(x), std::move(a),
897 typename node_ator_traits::is_always_equal())
898 {}
899
900 private:
902 tree(tree&& x, node_allocator a, true_)
903 ynoexcept(is_nothrow_default_constructible<_fComp>())
904 : objects(std::move(x.objects), std::move(a))
905 {}
907 tree(tree&& x, node_allocator a, false_)
908 : objects(x.objects.key_compare, std::move(a))
909 {
910 if(x.root())
911 move_data(x, false_());
912 }
914
915 public:
916 ~tree() ynothrow
917 {
918 clear_nodes();
919 }
920
921 tree&
922 operator=(const tree& x)
923 {
924 if(&x != this)
925 {
926 if(typename
927 node_ator_traits::propagate_on_container_copy_assignment())
928 {
929 auto& this_alloc(get_node_allocator());
930 auto& that_alloc(x.get_node_allocator());
931
932 if(!typename node_ator_traits::is_always_equal()
933 && this_alloc != that_alloc)
934 clear();
935 ystdex::alloc_on_copy(this_alloc, that_alloc);
936 }
937
938 reuse_or_alloc_node roan(*this);
939
940 objects.header.reset();
941 objects.key_compare = x.objects.key_compare;
942 if(x.root())
943 root() = copy_node(x, roan);
944 }
945 return *this;
946 }
948 tree&
949 operator=(tree&& x) ynoexcept(and_<equal_alloc_or_pocma,
950 is_nothrow_move_assignable<_fComp>>())
951 {
952 // NOTE: Like ISO C++ [res.on.arguments], moving same object to itself
953 // is not supported to meet the postcondition of the move assignment,
954 // and the result is unspecified. Since it is still well-defined, there
955 // is no assertion here.
956 // XXX: Moving from an ancestor to its subtree (composed by elements of
957 // recursive container type) is also not supported and it would
958 // typically lead to resource leaks, however there is no check anyway.
959 // This is different to ISO C++ as associative containers do not
960 // support incomplete element types so the recursive container type
961 // itself causes undefined behavior in such cases. Use %swap if the
962 // operand can reference to the object itself or its subtrees thereby.
963 objects.key_compare = std::move(x.objects.key_compare);
964 move_assign_elements(x, equal_alloc_or_pocma());
965 return *this;
966 }
967
968 private:
973 void
974 move_data(tree& x, false_)
975 {
976 if(get_node_allocator() == x.get_node_allocator())
977 move_data(x, true_());
978 else
979 {
980 alloc_node an(*this);
981
982 root() = copy_node(x, [&an](const value_type& cval){
983 return an(std::move_if_noexcept(const_cast< value_type&>(cval)));
984 });
985 }
986 }
991 void
992 move_data(tree& x, true_) ynothrow
993 {
994 objects.move_data(x.objects);
995 }
996
1001 void
1002 move_assign_elements(tree& x, false_)
1003 {
1004 if(get_node_allocator() == x.get_node_allocator())
1005 move_assign_elements(x, true_());
1006 else
1007 {
1008 // NOTE: Try to move reusing existing nodes.
1009 reuse_or_alloc_node roan(*this);
1010
1011 objects.header.reset();
1012 if(x.root())
1013 {
1014 root() = copy_node(x, [&roan](const value_type& cval){
1015 return roan(
1016 std::move_if_noexcept(const_cast< value_type&>(cval)));
1017 });
1018 x.clear();
1019 }
1020 }
1021 }
1026 void
1027 move_assign_elements(tree& x, true_) ynothrow
1028 {
1029 clear_nodes();
1030 if(x.root())
1031 move_data(x, true_());
1032 else
1033 objects.header.reset();
1034 ystdex::alloc_on_move(get_node_allocator(), x.get_node_allocator());
1035 }
1036
1037 public:
1038 YB_ATTR_nodiscard allocator_type
1039 get_allocator() const ynothrow
1040 {
1041 return allocator_type(get_node_allocator());
1042 }
1043
1044 YB_ATTR_nodiscard YB_PURE node_allocator&
1045 get_node_allocator() ynothrow
1046 {
1047 return objects;
1048 }
1049 YB_ATTR_nodiscard YB_PURE const node_allocator&
1050 get_node_allocator() const ynothrow
1051 {
1052 return objects;
1053 }
1054
1055 YB_ATTR_nodiscard YB_PURE iterator
1056 begin() ynothrow
1057 {
1058 return iterator(objects.header.left);
1059 }
1060 YB_ATTR_nodiscard YB_PURE const_iterator
1061 begin() const ynothrow
1062 {
1063 return const_iterator(objects.header.left);
1064 }
1065
1066 YB_ATTR_nodiscard YB_PURE iterator
1067 end() ynothrow
1068 {
1069 return iterator(&objects.header);
1070 }
1071 YB_ATTR_nodiscard YB_PURE const_iterator
1072 end() const ynothrow
1073 {
1074 return const_iterator(&objects.header);
1075 }
1076
1077 YB_ATTR_nodiscard YB_PURE reverse_iterator
1078 rbegin() ynothrow
1079 {
1080 return reverse_iterator(end());
1081 }
1082 YB_ATTR_nodiscard YB_PURE const_reverse_iterator
1083 rbegin() const ynothrow
1084 {
1085 return const_reverse_iterator(end());
1086 }
1087 YB_ATTR_nodiscard YB_PURE reverse_iterator
1088 rend() ynothrow
1089 {
1090 return reverse_iterator(begin());
1091 }
1092
1093 YB_ATTR_nodiscard YB_PURE const_reverse_iterator
1094 rend() const ynothrow
1095 {
1096 return const_reverse_iterator(begin());
1097 }
1098
1099 YB_ATTR_nodiscard bool
1100 empty() const ynothrow
1101 {
1102 return objects.header.node_count == 0;
1103 }
1104
1105 YB_ATTR_nodiscard size_type
1106 size() const ynothrow
1107 {
1108 return objects.header.node_count;
1109 }
1110
1111 YB_ATTR_nodiscard size_type
1112 max_size() const ynothrow
1113 {
1114 return node_ator_traits::max_size(get_node_allocator());
1115 }
1116
1117 protected:
1119 YB_ALLOCATOR YB_ATTR_returns_nonnull link_type
1120 allocate_node()
1121 {
1122 return node_ator_traits::allocate(get_node_allocator(), 1);
1123 }
1124
1126 void
1127 deallocate_node(link_type p) ynothrow
1128 {
1129 node_ator_traits::deallocate(get_node_allocator(), p, 1);
1130 }
1131
1132 template<typename... _tParams>
1133 void
1134 construct_node(link_type nd, _tParams&&... args)
1135 {
1136 // XXX: Ensure no need to use placment new for the node.
1137 static_assert(is_trivially_default_constructible<value_node>(),
1138 "Invalid node type found.");
1139 auto& a(get_node_allocator());
1140 // NOTE: This should be same to %deallocate_node(nd) on exception
1141 // thrown.
1142 allocator_guard<node_allocator>
1143 gd(nd, allocator_guard_delete<node_allocator>(a, 1));
1144
1145 node_ator_traits::construct(a, nd->access_ptr(), yforward(args)...);
1146 gd.release();
1147 }
1148
1149 template<typename... _tParams>
1150 YB_ATTR_nodiscard inline link_type
1151 create_node(_tParams&&... args)
1152 {
1153 const auto nd(allocate_node());
1154
1155 construct_node(nd, yforward(args)...);
1156 return nd;
1157 }
1158
1159 void
1160 destroy_node(link_type nd) ynothrow
1161 {
1162 // XXX: Ensure no need to use explicit destructor call for the node.
1163 static_assert(is_trivially_destructible<value_node>(),
1164 "Invalid node type found.");
1165 node_ator_traits::destroy(get_node_allocator(), nd->access_ptr());
1166 }
1167
1168 void
1169 drop_node(link_type nd) ynothrow
1170 {
1171 destroy_node(nd);
1172 deallocate_node(nd);
1173 }
1174
1175 private:
1177 void
1178 attach_node(bool insert_left, base_ptr p, link_type nd)
1179 {
1180 tree_insert_and_rebalance(insert_left, nd, p, objects.header);
1181 ++objects.header.node_count;
1182 }
1183
1185 YB_ATTR_nodiscard link_type
1186 detach_node(base_ptr cur)
1187 {
1188 --objects.header.node_count;
1189 return link_type(tree_rebalance_for_erase(cur, objects.header));
1190 }
1191
1192 protected:
1193 base_ptr&
1194 root() ynothrow
1195 {
1196 return objects.header.parent;
1197 }
1198 const_base_ptr
1199 root() const ynothrow
1200 {
1201 return objects.header.parent;
1202 }
1203
1204 base_ptr&
1205 leftmost() ynothrow
1206 {
1207 return objects.header.left;
1208 }
1209 const_base_ptr
1210 leftmost() const ynothrow
1211 {
1212 return objects.header.left;
1213 }
1214
1215 base_ptr&
1216 rightmost() ynothrow
1217 {
1218 return objects.header.right;
1219 }
1220 const_base_ptr
1221 rightmost() const ynothrow
1222 {
1223 return objects.header.right;
1224 }
1225
1226 link_type
1227 node_begin() ynothrow
1228 {
1229 return link_type(objects.header.parent);
1230 }
1231 const_link_type
1232 node_begin() const ynothrow
1233 {
1234 return const_link_type(objects.header.parent);
1235 }
1236
1237 base_ptr
1238 node_end() ynothrow
1239 {
1240 return &objects.header;
1241 }
1242 const_base_ptr
1243 node_end() const ynothrow
1244 {
1245 return &objects.header;
1246 }
1247
1248 static const _tKey&
1249 select_key(const_base_ptr x)
1250 {
1251 return _fKeyOfValue()(select_value(x));
1252 }
1253 static const _tKey&
1254 select_key(const_link_type x)
1255 {
1256 return _fKeyOfValue()(select_value(x));
1257 }
1258
1259 static const_reference
1260 select_value(const_link_type x)
1261 {
1262 return *x->access_ptr();
1263 }
1264 static const_reference
1265 select_value(const_base_ptr x)
1266 {
1267 return *const_link_type(x)->access_ptr();
1268 }
1269
1270 static link_type
1271 get_left(base_ptr x) ynothrow
1272 {
1273 return link_type(x->left);
1274 }
1275 static const_link_type
1276 get_left(const_base_ptr x) ynothrow
1277 {
1278 return const_link_type(x->left);
1279 }
1280
1281 static link_type
1282 get_right(base_ptr x) ynothrow
1283 {
1284 return link_type(x->right);
1285 }
1286 static const_link_type
1287 get_right(const_base_ptr x) ynothrow
1288 {
1289 return const_link_type(x->right);
1290 }
1291
1292 YB_PURE static base_ptr
1293 maximum(base_ptr x) ynothrow
1294 {
1295 return tree_node_base::maximum(x);
1296 }
1297 YB_PURE static const_base_ptr
1298 maximum(const_base_ptr x) ynothrow
1299 {
1300 return tree_node_base::maximum(x);
1301 }
1302
1303 YB_PURE static base_ptr
1304 minimum(base_ptr x) ynothrow
1305 {
1306 return tree_node_base::minimum(x);
1307 }
1308 YB_PURE static const_base_ptr
1309 minimum(const_base_ptr x) ynothrow
1310 {
1311 return tree_node_base::minimum(x);
1312 }
1313
1314 private:
1316 template<typename _tParam>
1317 inline bool
1318 is_insert_left(base_ptr p, const _tParam& arg)
1319 {
1320 return p == node_end() || !objects.key_compare(select_key(p), arg);
1321 }
1322
1324 template<typename _tParam>
1325 inline bool
1326 is_insert_left_strict(base_ptr p, const _tParam& arg)
1327 {
1328 return p == node_end() || objects.key_compare(arg, select_key(p));
1329 }
1330
1332 iterator
1333 insert_attach(bool insert_left, base_ptr p, link_type nd)
1334 {
1335 attach_node(insert_left, p, nd);
1336 return iterator(nd);
1337 }
1338
1340 bool
1341 insert_left_q(const std::pair<base_ptr, base_ptr>& pr, const key_type& k)
1342 {
1343 return bool(pr.first) || is_insert_left_strict(pr.second, k);
1344 }
1345
1346 iterator
1347 insert_node(base_ptr x, base_ptr p, link_type nd)
1348 {
1349 return insert_attach(bool(x)
1350 || is_insert_left_strict(p, select_key(nd)), p, nd);
1351 }
1352
1353 template<typename _tParam>
1354 iterator
1355 insert_equal_lower(_tParam&& v)
1356 {
1357 auto x(node_begin());
1358 auto y(node_end());
1359
1360 while(x)
1361 {
1362 y = x;
1363 x = !objects.key_compare(select_key(x), _fKeyOfValue()(v))
1364 ? get_left(x) : get_right(x);
1365 }
1366
1367 // NOTE: This is checked first to avoid stray node allocated when the
1368 // key comparation throws.
1369 const bool insert_left(is_insert_left(y, _fKeyOfValue()(v)));
1370
1371 return insert_attach(insert_left, y, create_node(yforward(v)));
1372 }
1373
1374 iterator
1375 insert_equal_lower_node(link_type nd)
1376 {
1377 auto x(node_begin());
1378 auto y(node_end());
1379
1380 while(x)
1381 {
1382 y = x;
1383 x = !objects.key_compare(select_key(x), select_key(nd))
1384 ? get_left(x) : get_right(x);
1385 }
1386 return insert_attach(is_insert_left(y, select_key(nd)), y, nd);
1387 }
1388
1389 template<class _tNodeGen>
1390 link_type
1391 copy_node(const_link_type x, base_ptr p, const _tNodeGen& node_gen)
1392 {
1393 yassume(x), yassume(p);
1394
1395 const auto clone_node([&](const_link_type s){
1396 link_type res(node_gen(*s->access_ptr()));
1397
1398 yunseq(res->color = s->color, res->left = {}, res->right = {});
1399 return res;
1400 });
1401 const auto top(clone_node(x));
1402
1403 top->parent = p;
1404 try
1405 {
1406 if(x->right)
1407 top->right = copy_node(get_right(x), top, node_gen);
1408 p = top;
1409 x = get_left(x);
1410
1411 while(x)
1412 {
1413 const auto y(clone_node(x));
1414
1415 p->left = y;
1416 y->parent = p;
1417 if(x->right)
1418 y->right = copy_node(get_right(x), y, node_gen);
1419 p = y;
1420 x = get_left(x);
1421 }
1422 }
1423 catch(...)
1424 {
1425 erase_node(top);
1426 throw;
1427 }
1428 return top;
1429 }
1430 template<class _tNodeGen>
1431 link_type
1432 copy_node(const tree& x, const _tNodeGen& node_gen)
1433 {
1434 const auto root(copy_node(x.node_begin(), node_end(), node_gen));
1435
1436 yunseq(leftmost() = minimum(root), rightmost() = maximum(root),
1437 objects.header.node_count = x.objects.header.node_count);
1438 return root;
1439 }
1440 link_type
1441 copy_node(const tree& x)
1442 {
1443 alloc_node an(*this);
1444
1445 return copy_node(x, an);
1446 }
1447
1448 void
1449 erase_node(link_type x) ynothrow
1450 {
1451 while(x)
1452 {
1453 erase_node(get_right(x));
1454
1455 auto y(get_left(x));
1456
1457 drop_node(x);
1458 x = y;
1459 }
1460 }
1461
1462 template<typename _tIter, class _tTree, typename _tLink, typename _tBasePtr>
1463 YB_ATTR_nodiscard YB_PURE static _tIter
1464 lower_bound_impl(_tTree& t, _tLink x, _tBasePtr y, const _tKey& k)
1465 {
1466 while(x)
1467 if(!t.objects.key_compare(select_key(x), k))
1468 {
1469 y = x;
1470 x = get_left(x);
1471 }
1472 else
1473 x = get_right(x);
1474 return _tIter(y);
1475 }
1476 template<typename _tIter, class _tTree>
1477 YB_ATTR_nodiscard YB_PURE static inline _tIter
1478 lower_bound_impl(_tTree& t, const key_type& k)
1479 {
1480 return lower_bound_impl<_tIter>(t, t.node_begin(), t.node_end(), k);
1481 }
1482
1483 template<typename _tIter, class _tTree, typename _tLink, typename _tBasePtr>
1484 YB_ATTR_nodiscard YB_PURE static _tIter
1485 upper_bound_impl(_tTree& t, _tLink x, _tBasePtr y, const _tKey& k)
1486 {
1487 while(x)
1488 if(t.objects.key_compare(k, select_key(x)))
1489 {
1490 y = x;
1491 x = get_left(x);
1492 }
1493 else
1494 x = get_right(x);
1495 return _tIter(y);
1496 }
1497 template<typename _tIter, class _tTree>
1498 YB_ATTR_nodiscard YB_PURE static inline _tIter
1499 upper_bound_impl(_tTree& t, const key_type& k)
1500 {
1501 return lower_bound_impl<_tIter>(t, t.node_begin(), t.node_end(), k);
1502 }
1503
1505 template<typename _tIter, class _tTree>
1506 YB_ATTR_nodiscard YB_PURE std::pair<_tIter, _tIter>
1507 equal_range_impl(_tTree& t, const key_type& k)
1508 {
1509 using pr_t = std::pair<_tIter, _tIter>;
1510 auto x(t.node_begin());
1511 auto y(t.node_end());
1512
1513 while(x)
1514 {
1515 const auto& t_comp(t.objects.key_compare);
1516
1517 if(t_comp(select_key(x), k))
1518 x = get_right(x);
1519 else if(t_comp(k, select_key(x)))
1520 {
1521 y = x;
1522 x = get_left(x);
1523 }
1524 else
1525 {
1526 auto xu(x);
1527 auto yu(y);
1528
1529 y = x;
1530 x = get_left(x);
1531 xu = get_right(xu);
1532 return pr_t(lower_bound_impl<_tIter>(t, x, y, k),
1533 upper_bound_impl<_tIter>(t, xu, yu, k));
1534 }
1535 }
1536 return pr_t(_tIter(y), _tIter(y));
1537 }
1538
1539 template<typename _tIter, class _tTree>
1540 YB_ATTR_nodiscard YB_PURE static _tIter
1541 find_impl(_tTree& t, const key_type& k)
1542 {
1543 const auto
1544 j(lower_bound_impl<_tIter>(t, t.node_begin(), t.node_end(), k));
1545
1546 return (j == t.end()
1547 || t.objects.key_compare(k, select_key(j.p_node))) ? t.end() : j;
1548 }
1549
1550 iterator
1551 lower_bound_link(link_type x, base_ptr y, const _tKey& k)
1552 {
1553 return lower_bound_impl<iterator>(*this, x, y, k);
1554 }
1555 const_iterator
1556 lower_bound_link(const_link_type x, const_base_ptr y, const _tKey& k) const
1557 {
1558 return lower_bound_impl<const_iterator>(*this, x, y, k);
1559 }
1560
1561 iterator
1562 upper_bound_link(link_type x, base_ptr y, const _tKey& k)
1563 {
1564 return upper_bound_impl<iterator>(*this, x, y, k);
1565 }
1566 const_iterator
1567 upper_bound_link(const_link_type x, const_base_ptr y, const _tKey& k) const
1568 {
1569 return upper_bound_impl<const_iterator>(*this, x, y, k);
1570 }
1571
1572 public:
1573 YB_ATTR_nodiscard YB_PURE std::pair<base_ptr, base_ptr>
1574 get_insert_unique_pos(const key_type& k)
1575 {
1576 using res_t = std::pair<base_ptr, base_ptr>;
1577 auto x(node_begin());
1578 auto y(node_end());
1579 bool comp(true);
1580
1581 while(x)
1582 {
1583 y = x;
1584 comp = objects.key_compare(k, select_key(x));
1585 x = comp ? get_left(x) : get_right(x);
1586 }
1587
1588 auto j = iterator(y);
1589
1590 if(comp)
1591 {
1592 if(j == begin())
1593 return res_t(x, y);
1594 else
1595 --j;
1596 }
1597 if(objects.key_compare(select_key(j.p_node), k))
1598 return res_t(x, y);
1599 return res_t(j.p_node, {});
1600 }
1601
1602 YB_ATTR_nodiscard YB_PURE std::pair<base_ptr, base_ptr>
1603 get_insert_equal_pos(const key_type& k)
1604 {
1605 auto x(node_begin());
1606 auto y(node_end());
1607
1608 while(x)
1609 {
1610 y = x;
1611 x = objects.key_compare(k, select_key(x)) ? get_left(x)
1612 : get_right(x);
1613 }
1614 return std::pair<base_ptr, base_ptr>(x, y);
1615 }
1616
1617 YB_ATTR_nodiscard YB_PURE std::pair<base_ptr, base_ptr>
1618 get_insert_hint_unique_pos(const_iterator position, const key_type& k)
1619 {
1620 // TODO: Simplify.
1621 using res_t = std::pair<base_ptr, base_ptr>;
1622 auto mpos(position.cast_mutable());
1623
1624 if(mpos.p_node == node_end())
1625 {
1626 if(size() > 0 && objects.key_compare(select_key(rightmost()), k))
1627 return res_t({}, rightmost());
1628 else
1629 return get_insert_unique_pos(k);
1630 }
1631 else if(objects.key_compare(k, select_key(mpos.p_node)))
1632 {
1633 auto before(mpos);
1634
1635 if(mpos.p_node == leftmost())
1636 return res_t(leftmost(), leftmost());
1637 else if(objects.key_compare(select_key((--before).p_node), k))
1638 return !get_right(before.p_node) ? res_t({}, before.p_node)
1639 : res_t(mpos.p_node, mpos.p_node);
1640 else
1641 return get_insert_unique_pos(k);
1642 }
1643 else if(objects.key_compare(select_key(mpos.p_node), k))
1644 {
1645 auto after(mpos);
1646
1647 if(mpos.p_node == rightmost())
1648 return res_t({}, rightmost());
1649 else if(objects.key_compare(k, select_key((++after).p_node)))
1650 return !get_right(mpos.p_node) ? res_t({}, mpos.p_node)
1651 : res_t(after.p_node, after.p_node);
1652 else
1653 return get_insert_unique_pos(k);
1654 }
1655 else
1656 return res_t(mpos.p_node, {});
1657 }
1658
1659 YB_ATTR_nodiscard YB_PURE std::pair<base_ptr, base_ptr>
1660 get_insert_hint_equal_pos(const_iterator position, const key_type& k)
1661 {
1662 using res_t = std::pair<base_ptr, base_ptr>;
1663 auto mpos(position.cast_mutable());
1664
1665 if(mpos.p_node == node_end())
1666 {
1667 if(size() > 0 && !objects.key_compare(k, select_key(rightmost())))
1668 return res_t(0, rightmost());
1669 else
1670 return get_insert_equal_pos(k);
1671 }
1672 else if(!objects.key_compare(select_key(mpos.p_node), k))
1673 {
1674 auto before(mpos);
1675
1676 if(mpos.p_node == leftmost())
1677 return res(leftmost(), leftmost());
1678 else if(!objects.key_compare(k, select_key((--before).p_node)))
1679 {
1680 if(!get_right(before.p_node))
1681 return res_t(0, before.p_node);
1682 else
1683 return res_t(mpos.p_node, mpos.p_node);
1684 }
1685 else
1686 return get_insert_equal_pos(k);
1687 }
1688 else
1689 {
1690 auto after(mpos);
1691
1692 if(mpos.p_node == rightmost())
1693 return res_t(0, rightmost());
1694 else if(!objects.key_compare(select_key((++after).p_node), k))
1695 {
1696 if(!get_right(mpos.p_node))
1697 return res_t({}, mpos.p_node);
1698 else
1699 return res_t(after.p_node, after.p_node);
1700 }
1701 else
1702 return res_t({}, {});
1703 }
1704 }
1705
1706 template<typename _tParam>
1707 std::pair<iterator, bool>
1708 insert_unique(_tParam&& v)
1709 {
1710 alloc_node an(*this);
1711
1712 return insert_unique(yforward(v), an);
1713 }
1715 template<typename _tParam, class _tNodeGen>
1716 std::pair<iterator, bool>
1717 insert_unique(_tParam&& v, const _tNodeGen& node_gen)
1718 {
1719 using res_t = std::pair<iterator, bool>;
1720 const auto& k(_fKeyOfValue()(v));
1721 const auto res(get_insert_unique_pos(k));
1722
1723 if(res.second)
1724 {
1725 // NOTE: This is checked first to avoid stray node allocated when
1726 // the key comparation throws.
1727 const bool insert_left(insert_left_q(res, k));
1728
1729 // XXX: Assume the key in the constructed node is equivalent to %k.
1730 return res_t(insert_attach(insert_left, res.second,
1731 link_type(node_gen(yforward(v)))), true);
1732 }
1733 return res_t(iterator(res.first), {});
1734 }
1735
1736 template<typename _tParam>
1737 iterator
1738 insert_equal(_tParam&& v)
1739 {
1740 alloc_node an(*this);
1741
1742 return insert_equal(yforward(v), an);
1743 }
1745 template<typename _tParam, class _tNodeGen>
1746 iterator
1747 insert_equal(_tParam&& v, const _tNodeGen& node_gen)
1748 {
1749 const auto& k(_fKeyOfValue()(v));
1750 const auto res(get_insert_equal_pos(k));
1751 // NOTE: This is checked first to avoid stray node allocated when the
1752 // key comparation throws.
1753 const bool insert_left(insert_left_q(res, k));
1754
1755 // XXX: Assume the key in the constructed node is equivalent to %k.
1756 return insert_attach(insert_left, res.second,
1757 link_type(node_gen(yforward(v))));
1758 }
1759
1760 template<typename _tParam>
1761 iterator
1762 insert_hint_unique(const_iterator position, _tParam&& x)
1763 {
1764 alloc_node an(*this);
1765
1766 return insert_hint_unique(position, yforward(x), an);
1767 }
1768 template<typename _tParam, class _tNodeGen>
1769 iterator
1770 insert_hint_unique(const_iterator position, _tParam&& v,
1771 const _tNodeGen& node_gen)
1772 {
1773 const auto& k(_fKeyOfValue()(v));
1774 const auto res(get_insert_hint_unique_pos(position, k));
1775
1776 if(res.second)
1777 {
1778 // NOTE: This is checked first to avoid stray node allocated when
1779 // the key comparation throws.
1780 const bool insert_left(insert_left_q(res, k));
1781
1782 // XXX: Assume the key in the constructed node is equivalent to %k.
1783 return insert_attach(insert_left, res.second,
1784 link_type(node_gen(yforward(v))));
1785 }
1786 return iterator(res.first);
1787 }
1788
1789 template<typename _tParam>
1790 inline iterator
1791 insert_hint_equal(const_iterator position, _tParam&& x)
1792 {
1793 alloc_node an(*this);
1794
1795 return insert_hint_equal(position, yforward(x), an);
1796 }
1797 template<typename _tParam, class _tNodeGen>
1798 iterator
1799 insert_hint_equal(const_iterator position, _tParam&& v,
1800 const _tNodeGen& node_gen)
1801 {
1802 const auto& k(_fKeyOfValue()(v));
1803 const auto res(get_insert_hint_equal_pos(position, k));
1804
1805 if(res.second)
1806 {
1807 // NOTE: This is checked first to avoid stray node allocated when
1808 // the key comparation throws.
1809 const bool insert_left(insert_left_q(res, k));
1810
1811 // XXX: Assume the key in the constructed node is equivalent to %k.
1812 return insert_attach(insert_left, res.second,
1813 link_type(node_gen(yforward(v))));
1814 }
1815 return insert_equal_lower(yforward(v));
1816 }
1817
1818 private:
1819 // XXX: The return type can be incomplete before this template is
1820 // instantiated.
1822 template<typename _func, yimpl(typename _tRes
1823 = decltype(std::declval<_func&>()(std::declval<const key_type&>())))>
1824 inline _tRes
1825 insert_or_drop(link_type nd, _func f)
1826 {
1827 try
1828 {
1829 return f(select_key(nd));
1830 }
1831 catch(...)
1832 {
1833 drop_node(nd);
1834 throw;
1835 }
1836 }
1837
1838 public:
1839 template<typename... _tParams>
1840 YB_FLATTEN inline std::pair<iterator, bool>
1841 emplace_unique(_tParams&&... args)
1842 {
1843 return emplace_unique_node(create_node(yforward(args)...));
1844 }
1845
1846 private:
1848 std::pair<iterator, bool>
1849 emplace_unique_node(link_type nd)
1850 {
1851 return insert_or_drop(nd,
1852 [&](const key_type& k) -> std::pair<iterator, bool>{
1853 const auto pr(get_insert_unique_pos(k));
1854
1855 if(pr.second)
1856 return {insert_node(pr.first, pr.second, nd), true};
1857 drop_node(nd);
1858 return {iterator(pr.first), {}};
1859 });
1860 }
1861
1862 public:
1863 template<typename... _tParams>
1864 YB_FLATTEN inline iterator
1865 emplace_equal(_tParams&&... args)
1866 {
1867 return emplace_equal_node(create_node(yforward(args)...));
1868 }
1869
1870 private:
1872 iterator
1873 emplace_equal_node(link_type nd)
1874 {
1875 return insert_or_drop(nd, [&](const key_type& k){
1876 const auto pr(get_insert_equal_pos(k));
1877
1878 return insert_node(pr.first, pr.second, nd);
1879 });
1880 }
1881
1882 public:
1883 template<typename... _tParams>
1884 YB_FLATTEN inline iterator
1885 emplace_hint_unique(const_iterator position, _tParams&&... args)
1886 {
1887 return
1888 emplace_hint_unique_node(position, create_node(yforward(args)...));
1889 }
1890
1891 private:
1893 iterator
1894 emplace_hint_unique_node(const_iterator position, link_type nd)
1895 {
1896 return insert_or_drop(nd, [&](const key_type& k){
1897 const auto pr(get_insert_hint_unique_pos(position, k));
1898
1899 if(pr.second)
1900 return insert_node(pr.first, pr.second, nd);
1901 drop_node(nd);
1902 return iterator(pr.first);
1903 });
1904 }
1905
1906 public:
1907 template<typename... _tParams>
1908 YB_FLATTEN inline iterator
1909 emplace_hint_equal(const_iterator position, _tParams&&... args)
1910 {
1911 return
1912 emplace_hint_equal_node(position, create_node(yforward(args)...));
1913 }
1914
1915 private:
1917 iterator
1918 emplace_hint_equal_node(const_iterator position, link_type nd)
1919 {
1920 return insert_or_drop([&](const key_type& k){
1921 const auto pr(get_insert_hint_equal_pos(position, k));
1922
1923 return pr.second ? insert_node(pr.first, pr.second, nd)
1924 : insert_equal_lower_node(nd);
1925 });
1926 }
1927
1928 public:
1930
1931 template<typename _tIn>
1932 enable_if_t<has_iterator_value_type<value_type, _tIn>::value>
1933 insert_range_unique(_tIn first, _tIn last)
1934 {
1935 alloc_node an(*this);
1936
1937 for(; first != last; ++first)
1938 insert_unique(*first, an);
1939 }
1940 template<typename _tIn>
1941 enable_if_t<!has_iterator_value_type<value_type, _tIn>::value>
1942 insert_range_unique(_tIn first, _tIn last)
1943 {
1944 for(; first != last; ++first)
1945 emplace_hint_unique(end(), *first);
1946 }
1947
1948 template<typename _tIn>
1949 enable_if_t<has_iterator_value_type<value_type, _tIn>::value>
1950 insert_range_equal(_tIn first, _tIn last)
1951 {
1952 alloc_node an(*this);
1953
1954 for(; first != last; ++first)
1955 insert_equal(*first, an);
1956 }
1957 template<typename _tIn>
1958 enable_if_t<!has_iterator_value_type<value_type, _tIn>::value>
1959 insert_range_equal(_tIn first, _tIn last)
1960 {
1961 alloc_node an(*this);
1962
1963 for(; first != last; ++first)
1964 emplace_hint_equal(end(), *first);
1965 }
1967
1968 private:
1970 void
1971 erase_it(iterator position)
1972 {
1973 drop_node(detach_node(position.p_node));
1974 }
1976 void
1977 erase_it(iterator first, iterator last)
1978 {
1979 if(first == begin() && last == end())
1980 clear();
1981 else
1982 while(first != last)
1983 erase_it(first++);
1984 }
1985
1986 public:
1987 YB_FLATTEN iterator
1988 erase(const_iterator position)
1989 {
1990 yconstraint(position != end());
1991
1992 auto res(position.cast_mutable());
1993
1994 ++res;
1995 erase_it(position.cast_mutable());
1996 return res;
1997 }
1998 YB_FLATTEN iterator
1999 erase(iterator position)
2000 {
2001 yconstraint(position != end());
2002
2003 auto res(position);
2004
2005 ++res;
2006 erase_it(position);
2007 return res;
2008 }
2009 YB_FLATTEN size_type
2010 erase(const key_type& x)
2011 {
2012 const auto pr(equal_range(x));
2013 const size_type old_size(size());
2014
2015 erase_it(pr.first, pr.second);
2016 return old_size - size();
2017 }
2018 YB_FLATTEN iterator
2019 erase(const_iterator first, const_iterator last)
2020 {
2021 const auto res(last.cast_mutable());
2022
2023 erase_it(first.cast_mutable(), res);
2024 return res;
2025 }
2026 YB_FLATTEN void
2027 erase(const key_type* first, const key_type* last)
2028 {
2029 while(first != last)
2030 erase(*first++);
2031 }
2032
2034 friend void
2035 swap(tree& x, tree& y) ynoexcept(is_nothrow_swappable<_fComp>())
2036 {
2037 if(!x.root())
2038 {
2039 if(y.root())
2040 x.objects.move_data(y.objects);
2041 }
2042 else if(!y.root())
2043 y.objects.move_data(x.objects);
2044 else
2045 {
2046 std::swap(x.root(), y.root());
2047 std::swap(x.leftmost(), y.leftmost());
2048 std::swap(x.rightmost(), y.rightmost());
2049 yunseq(x.root()->parent = x.node_end(),
2050 y.root()->parent = y.node_end());
2051 std::swap(x.objects.header.node_count, y.objects.header.node_count);
2052 }
2053 // NOTE: As libstdc++'s implementation, the header's color does not
2054 // change.
2055 std::swap(x.objects.key_compare, y.objects.key_compare);
2056 ystdex::alloc_on_swap(x.get_node_allocator(), y.get_node_allocator());
2057 }
2058
2059 void
2060 clear() ynothrow
2061 {
2062 clear_nodes();
2063 objects.header.reset();
2064 }
2065
2066 private:
2068 void
2069 clear_nodes() ynothrow
2070 {
2071 erase_node(node_begin());
2072 }
2073
2074 public:
2075 YB_ATTR_nodiscard _fComp
2076 key_comp() const
2077 {
2078 return objects.key_compare;
2079 }
2080
2081 YB_ATTR_nodiscard YB_PURE iterator
2082 find(const key_type& k)
2083 {
2084 return find_impl<iterator>(*this, k);
2085 }
2086 YB_ATTR_nodiscard YB_PURE const_iterator
2087 find(const key_type& k) const
2088 {
2089 return find_impl<const_iterator>(*this, k);
2090 }
2091
2092 YB_ATTR_nodiscard YB_PURE size_type
2093 count(const key_type& k) const
2094 {
2095 const auto pr(equal_range(k));
2096
2097 return size_type(std::distance(pr.first, pr.second));
2098 }
2099
2100 YB_ATTR_nodiscard YB_PURE iterator
2101 lower_bound(const key_type& k)
2102 {
2103 return lower_bound_impl<iterator>(*this, k);
2104 }
2105 YB_ATTR_nodiscard YB_PURE const_iterator
2106 lower_bound(const key_type& k) const
2107 {
2108 return lower_bound_impl<const_iterator>(*this, k);
2109 }
2110
2111 YB_ATTR_nodiscard YB_PURE iterator
2112 upper_bound(const key_type& k)
2113 {
2114 return upper_bound_impl<iterator>(*this, k);
2115 }
2116 YB_ATTR_nodiscard YB_PURE const_iterator
2117 upper_bound(const key_type& k) const
2118 {
2119 return upper_bound_impl<const_iterator>(*this, k);
2120 }
2121
2122 YB_ATTR_nodiscard YB_PURE std::pair<iterator, iterator>
2123 equal_range(const key_type& k)
2124 {
2125 return equal_range_impl<iterator>(*this, k);
2126 }
2127 YB_ATTR_nodiscard YB_PURE std::pair<const_iterator, const_iterator>
2128 equal_range(const key_type& k) const
2129 {
2130 return equal_range_impl<iterator>(*this, k);
2131 }
2132
2134
2135 template<typename _tTransKey, typename
2136 = enable_if_t<has_mem_is_transparent<_fComp, _tTransKey>::value>>
2137 YB_ATTR_nodiscard YB_PURE inline iterator
2138 find_tr(const _tTransKey& k)
2139 {
2140 return ystdex::as_const(*this).find_tr(k).cast_mutable();
2141 }
2142 template<typename _tTransKey, typename
2143 = enable_if_t<has_mem_is_transparent<_fComp, _tTransKey>::value>>
2144 YB_ATTR_nodiscard YB_PURE const_iterator
2145 find_tr(const _tTransKey& k) const
2146 {
2147 const auto j(lower_bound_tr(k));
2148
2149 return j != end() && objects.key_compare(k, select_key(j.p_node))
2150 ? end() : j;
2151 }
2152
2153 template<typename _tTransKey, typename
2154 = enable_if_t<has_mem_is_transparent<_fComp, _tTransKey>::value>>
2155 YB_ATTR_nodiscard YB_PURE inline size_type
2156 count_tr(const _tTransKey& k) const
2157 {
2158 const auto pr(equal_range_tr(k));
2159
2160 return std::distance(pr.first, pr.second);
2161 }
2162
2163 template<typename _tTransKey, typename
2164 = enable_if_t<has_mem_is_transparent<_fComp, _tTransKey>::value>>
2165 YB_ATTR_nodiscard YB_PURE inline iterator
2166 lower_bound_tr(const _tTransKey& k)
2167 {
2168 return ystdex::as_const(*this).lower_bound_tr(k).cast_mutable();
2169 }
2170 template<typename _tTransKey, typename
2171 = enable_if_t<has_mem_is_transparent<_fComp, _tTransKey>::value>>
2172 YB_ATTR_nodiscard YB_PURE const_iterator
2173 lower_bound_tr(const _tTransKey& k) const
2174 {
2175 auto x(node_begin());
2176 auto y(node_end());
2177
2178 while(x)
2179 if(!objects.key_compare(select_key(x), k))
2180 {
2181 y = x;
2182 x = get_left(x);
2183 }
2184 else
2185 x = get_right(x);
2186 return const_iterator(y);
2187 }
2188
2189 template<typename _tTransKey, typename
2190 = enable_if_t<has_mem_is_transparent<_fComp, _tTransKey>::value>>
2191 YB_ATTR_nodiscard YB_PURE inline iterator
2192 upper_bound_tr(const _tTransKey& k)
2193 {
2194 return ystdex::as_const(*this).upper_bound_tr(k).cast_mutable();
2195 }
2196 template<typename _tTransKey, typename
2197 = enable_if_t<has_mem_is_transparent<_fComp, _tTransKey>::value>>
2198 YB_ATTR_nodiscard YB_PURE const_iterator
2199 upper_bound_tr(const _tTransKey& k) const
2200 {
2201 auto x(node_begin());
2202 auto y(node_end());
2203
2204 while(x)
2205 if(objects.key_compare(k, select_key(x)))
2206 {
2207 y = x;
2208 x = get_left(x);
2209 }
2210 else
2211 x = get_right(x);
2212 return const_iterator(y);
2213 }
2214
2215 template<typename _tTransKey, typename
2216 = enable_if_t<has_mem_is_transparent<_fComp, _tTransKey>::value>>
2217 YB_ATTR_nodiscard YB_PURE inline std::pair<iterator, iterator>
2218 equal_range_tr(const _tTransKey& k)
2219 {
2220 const auto pr(ystdex::as_const(*this).equal_range_tr(k));
2221
2222 return {pr.first.cast_mutable(), pr.second.cast_mutable()};
2223 }
2224 template<typename _tTransKey, typename
2225 = enable_if_t<has_mem_is_transparent<_fComp, _tTransKey>::value>>
2226 YB_ATTR_nodiscard YB_PURE std::pair<const_iterator, const_iterator>
2227 equal_range_tr(const _tTransKey& k) const
2228 {
2229 auto low(lower_bound_tr(k));
2230 auto high(low);
2231 auto& t_cmp(objects.key_compare);
2232
2233 while(high != end() && !t_cmp(k, select_key(high.p_node)))
2234 ++high;
2235 return {low, high};
2236 }
2238
2244 YB_ATTR_nodiscard YB_PURE bool
2245 rb_verify() const
2246 {
2247 if(objects.header.node_count == 0 || begin() == end())
2248 return objects.header.node_count == 0 && begin() == end()
2249 && objects.header.left == node_end()
2250 && objects.header.right == node_end();
2251
2252 const auto len(tree_black_count(leftmost(), root()));
2253
2254 for(const_iterator it(begin()); it != end(); ++it)
2255 {
2256 const auto x(const_link_type(it.p_node));
2257 const auto l(get_left(x));
2258 const auto r(get_right(x));
2259
2260 if(x->color == tree_color::red)
2261 if((l && l->color == tree_color::red)
2262 || (r && r->color == tree_color::red))
2263 return {};
2264 if(l && objects.key_compare(select_key(x), select_key(l)))
2265 return {};
2266 if(r && objects.key_compare(select_key(r), select_key(x)))
2267 return {};
2268 if(!l && !r && tree_black_count(x, root()) != len)
2269 return {};
2270 }
2271 if(leftmost() != tree_node_base::minimum(root()))
2272 return {};
2273 if(rightmost() != tree_node_base::maximum(root()))
2274 return {};
2275 return true;
2276 }
2277
2278 template<typename _tIter>
2279 void
2280 assign_unique(_tIter first, _tIter last)
2281 {
2282 reuse_or_alloc_node roan(*this);
2283
2284 objects.header.reset();
2285 for(; first != last; ++first)
2286 insert_hint_unique(end(), *first, roan);
2287 }
2288
2289 template<typename _tIter>
2290 void
2291 assign_equal(_tIter first, _tIter last)
2292 {
2293 reuse_or_alloc_node roan(*this);
2294
2295 objects.header.reset();
2296 for(; first != last; ++first)
2297 insert_hint_equal(end(), *first, roan);
2298 }
2299
2300 insert_return_type
2301 reinsert_node_unique(node_type&& nh)
2302 {
2303 insert_return_type ret;
2304
2305 if(nh.empty())
2306 ret.position = end();
2307 else
2308 {
2309 YAssert(get_node_allocator() == *nh.alloc,
2310 "Mismatched allocators found.");
2311
2312 const auto pr(get_insert_unique_pos(nh.ckey()));
2313
2314 if(pr.second)
2315 {
2316 ret.position = insert_node(pr.first, pr.second, nh.m_ptr);
2317 nh.m_ptr = nullptr;
2318 ret.inserted = true;
2319 }
2320 else
2321 {
2322 ret.node = std::move(nh);
2323 ret.position = iterator(pr.first);
2324 ret.inserted = {};
2325 }
2326 }
2327 return ret;
2328 }
2329
2330 iterator
2331 reinsert_node_equal(node_type&& nh)
2332 {
2333 iterator ret;
2334
2335 if(nh.empty())
2336 ret = end();
2337 else
2338 {
2339 YAssert(get_node_allocator() == *nh.alloc,
2340 "Mismatched allocators found.");
2341
2342 const auto res(get_insert_equal_pos(nh.ckey()));
2343
2344 ret = res.second ? insert_node(res.first, res.second, nh.m_ptr)
2345 : insert_equal_lower_node(nh.m_ptr);
2346 nh.m_ptr = {};
2347 }
2348 return ret;
2349 }
2350
2351 iterator
2352 reinsert_node_hint_unique(const_iterator hint, node_type&& nh)
2353 {
2354 iterator ret;
2355 if(nh.empty())
2356 ret = end();
2357 else
2358 {
2359 YAssert(get_node_allocator() == *nh.alloc,
2360 "Mismatched allocators found.");
2361
2362 const auto res(get_insert_hint_unique_pos(hint, nh.ckey()));
2363
2364 if(res.second)
2365 {
2366 ret = insert_node(res.first, res.second, nh.m_ptr);
2367 nh.m_ptr = {};
2368 }
2369 else
2370 ret = iterator(res.first);
2371 }
2372 return ret;
2373 }
2374
2375 iterator
2376 reinsert_node_hint_equal(const_iterator hint, node_type&& nh)
2377 {
2378 iterator ret;
2379 if(nh.empty())
2380 ret = end();
2381 else
2382 {
2383 YAssert(get_node_allocator() == *nh.alloc,
2384 "Mismatched allocators found.");
2385
2386 const auto res(get_insert_hint_equal_pos(hint, nh.ckey()));
2387
2388 ret = res.second ? insert_node(res.first, res.second, nh.m_ptr)
2389 : insert_equal_lower_node(nh.m_ptr);
2390 nh.m_ptr = {};
2391 }
2392 return ret;
2393 }
2394
2395 YB_ATTR_nodiscard node_type
2396 extract(const_iterator position)
2397 {
2398 const auto ptr(tree_rebalance_for_erase(position.cast_mutable().p_node,
2399 objects.header));
2400
2401 --objects.header.node_count;
2402 return {link_type(ptr), get_node_allocator()};
2403 }
2404 YB_ATTR_nodiscard node_type
2405 extract(const key_type& k)
2406 {
2407 node_type nh;
2408 const auto position(find(k));
2409
2410 if(position != end())
2411 nh = extract(const_iterator(position));
2412 return nh;
2413 }
2414
2416 template<typename _fComp2>
2417 void
2418 merge_unique(compatible_tree_type<_fComp2>& src) ynothrow
2419 {
2420 auto i(src.begin());
2421 const auto end(src.end());
2422
2423 while(i != end)
2424 {
2425 auto position = i++;
2426 auto res = get_insert_unique_pos(_fKeyOfValue()(*position));
2427 if(res.second)
2428 {
2429 auto& src_objs(tree_merge_helper<tree, _fComp2>::get_components(
2430 src));
2431 const auto ptr(tree_rebalance_for_erase(position.p_node,
2432 src_objs.header));
2433
2434 --src_objs.node_count;
2435 insert_node(res.first, res.second, link_type(ptr));
2436 }
2437 }
2438 }
2439
2441 template<typename _fComp2>
2442 void
2443 merge_equal(compatible_tree_type<_fComp2>& src) ynothrow
2444 {
2445 auto i(src.begin());
2446 const auto end(src.end());
2447
2448 while(i != end)
2449 {
2450 const auto position(i++);
2451 const auto pr(get_insert_equal_pos(_fKeyOfValue()(*position)));
2452
2453 if(pr.second)
2454 {
2455 auto& src_objs(tree_merge_helper<tree, _fComp2>::get_components(
2456 src));
2457 const auto ptr(
2458 tree_rebalance_for_erase(position.p_node, src_objs.header));
2459
2460 --src_objs.node_count;
2461 insert_node(pr.first, pr.second, link_type(ptr));
2462 }
2463 }
2464 }
2465
2466 friend bool
2467 operator==(const tree& x, const tree& y)
2468 {
2469 return x.size() == y.size()
2470 && std::equal(x.cbegin(), x.cend(), y.cbegin());
2471 }
2472
2473 friend bool
2474 operator<(const tree& x, const tree& y)
2475 {
2476 return std::lexicographical_compare(x.cbegin(), x.cend(), y.cbegin(),
2477 y.cend());
2478 }
2479 };
2480
2482 template<typename _tKey, typename _type, typename _fKeyOfValue,
2483 typename _fComp1, class _tAlloc, typename _fComp2>
2484 struct tree_merge_helper<
2485 tree<_tKey, _type, _fKeyOfValue, _fComp1, _tAlloc>, _fComp2>
2486 {
2487 private:
2488 friend class tree<_tKey, _type, _fKeyOfValue, _fComp1, _tAlloc>;
2489
2490 static auto
2491 get_components(tree<_tKey, _type, _fKeyOfValue, _fComp2, _tAlloc>& tree)
2492 -> decltype((tree.objects))
2493 {
2494 return tree.objects;
2495 }
2496 };
2497
2498 } // inline namespace rb_tree;
2499
2500 } // namespace details;
2502
2503 } // namespace ystdex;
2504
2505 #endif
2506
ystdex::details::rb_tree::tree::operator=
tree & operator=(const tree &x)
Definition: tree.h:922
ystdex::details::rb_tree::tree::upper_bound_tr
iterator upper_bound_tr(const _tTransKey &k)
Definition: tree.h:2192
ystdex::details::rb_tree::tree::lower_bound_tr
const_iterator lower_bound_tr(const _tTransKey &k) const
Definition: tree.h:2173
ystdex::details::rb_tree::tree_header::base
tree_node_base & base()
Definition: tree.h:472
ystdex::details::rb_tree::tree::tree
tree(const tree &x, const allocator_type &a)
Definition: tree.h:880
ystdex::details::rb_tree::tree::get_node_allocator
const node_allocator & get_node_allocator() const
Definition: tree.h:1050
YB_ATTR_nodiscard
#define YB_ATTR_nodiscard
标记返回值不被忽略的属性。
Definition: ydef.h:715
iterator_trait.hpp
迭代器特征。
ystdex::details::rb_tree::tree::upper_bound
iterator upper_bound(const key_type &k)
Definition: tree.h:2112
ystdex::details::rb_tree::tree_const_iterator::operator++
tree_const_iterator & operator++()
Definition: tree.h:631
ystdex::details::rb_tree::tree::insert_range_equal
enable_if_t< has_iterator_value_type< value_type, _tIn >::value > insert_range_equal(_tIn first, _tIn last)
Definition: tree.h:1950
ystdex::details::rb_tree::tree::tree
tree(const _fComp &comp, const allocator_type &a=allocator_type())
Definition: tree.h:871
ystdex::cpp2017::is_nothrow_swappable
Definition: swap.hpp:77
ystdex::details::node_handle_base::move_assign
void move_assign(false_)
Definition: tree.h:177
ystdex::details::rb_tree::tree::link_type
value_node * link_type
Definition: tree.h:723
ystdex::details::rb_tree::tree::swap
friend void swap(tree &x, tree &y)
Definition: tree.h:2035
x
const EncapsulationBase & x
Definition: NPLA1Forms.cpp:1536
ystdex::details::rb_tree::tree_const_iterator::tree_const_iterator
tree_const_iterator(const iterator &it)
Definition: tree.h:614
ystdex::details::rb_tree::tree::node_begin
link_type node_begin()
Definition: tree.h:1227
ystdex::cpp2017::swap
void swap(optional< _type > &x, optional< _type > &y)
Definition: optional.h:888
ystdex::details::rb_tree::tree::find
iterator find(const key_type &k)
Definition: tree.h:2082
ystdex::details::rb_tree::tree::maximum
static base_ptr maximum(base_ptr x)
Definition: tree.h:1293
ystdex::alloc_on_swap
void alloc_on_swap(_tAlloc &x, _tAlloc &y)
按分配器特征在传播容器时交换分配器。
Definition: allocator.hpp:1050
ystdex::details::rb_tree::tree_node::access_ptr
const _type * access_ptr() const
Definition: tree.h:493
ystdex::details::rb_tree::tree::insert_hint_unique
iterator insert_hint_unique(const_iterator position, _tParam &&v, const _tNodeGen &node_gen)
Definition: tree.h:1770
ystdex::details::rb_tree::tree::emplace_hint_equal
iterator emplace_hint_equal(const_iterator position, _tParams &&... args)
Definition: tree.h:1909
ystdex::details::rb_tree::tree_node
Definition: tree.h:481
ystdex::details::rb_tree::tree_black_count
size_t tree_black_count(const tree_node_base *, const tree_node_base *)
Definition: tree.cpp:385
ystdex::details::rb_tree::tree::reuse_or_alloc_node
Definition: tree.h:759
ystdex::details::node_handle< _type, _type, _tNodeAlloc >::swap
friend void swap(node_handle &x, node_handle &y)
Definition: tree.h:323
ystdex::details::rb_tree::tree::empty
bool empty() const
Definition: tree.h:1100
ystdex::details::node_handle::node_handle
node_handle(node_handle &&)=default
ystdex::details::rb_tree::tree::components::header
tree_header header
Definition: tree.h:829
ystdex::details::rb_tree::tree::insert_hint_equal
iterator insert_hint_equal(const_iterator position, _tParam &&x)
Definition: tree.h:1791
ystdex::details::rb_tree::tree::extract
node_type extract(const_iterator position)
Definition: tree.h:2396
ystdex::details::rb_tree::tree::node_type
node_handle< _tKey, _type, node_allocator > node_type
Definition: tree.h:716
ystdex::details::node_insert_return::inserted
bool inserted
Definition: tree.h:335
ystdex::details::rb_tree::tree::reinsert_node_hint_equal
iterator reinsert_node_hint_equal(const_iterator hint, node_type &&nh)
Definition: tree.h:2376
ystdex::details::node_handle::p_mapped
ptr_t< typename _type::second_type > p_mapped
Definition: tree.h:200
YB_PURE
#define YB_PURE
指示函数或函数模板实例为纯函数。
Definition: ydef.h:919
ystdex::details::rb_tree::tree_const_iterator::link_type
const tree_node< _type > * link_type
Definition: tree.h:604
ystdex::details::rb_tree::tree::rend
reverse_iterator rend()
Definition: tree.h:1088
ystdex::details::rb_tree::tree::assign_unique
void assign_unique(_tIter first, _tIter last)
Definition: tree.h:2280
ystdex::details::rb_tree::tree::clear_nodes
void clear_nodes()
Definition: tree.h:2069
ystdex::details::rb_tree::tree_node_base::left
base_ptr left
Definition: tree.h:360
ystdex::details::rb_tree::tree::components::move_data
void move_data(components &from)
Definition: tree.h:858
ystdex::details::rb_tree::tree::reinsert_node_unique
insert_return_type reinsert_node_unique(node_type &&nh)
Definition: tree.h:2301
yalignof
#define yalignof(_type)
指定特定类型的对齐。
Definition: ydef.h:1053
ystdex::details::rb_tree::tree_key_compare::tree_key_compare
tree_key_compare(const tree_key_compare &)=default
YSLib::Drawing::r
The boundary is out of the const Graphics const Rect const Point const Point Color c const Rect const Rect & r
Definition: YDraw.h:174
ystdex::details::rb_tree::tree
Definition: tree.h:70
ystdex::details::rb_tree::tree_node_base::initialize
void initialize()
Definition: tree.h:394
ystdex::details::node_handle< _type, _type, _tNodeAlloc >::node_handle
node_handle()=default
ystdex::details::rb_tree::tree_node_base
Definition: tree.h:354
ystdex::details::rb_tree::tree::components::components
components(node_allocator a)
Definition: tree.h:838
ystdex::details::rb_tree::tree::tree
tree(const tree &x)
Definition: tree.h:874
ystdex::cpp2017::optional::swap
void swap(optional &o)
Definition: optional.h:575
ystdex::details::rb_tree::tree::leftmost
base_ptr & leftmost()
Definition: tree.h:1205
ystdex::details::rb_tree::tree::emplace_unique
std::pair< iterator, bool > emplace_unique(_tParams &&... args)
Definition: tree.h:1841
ystdex::details::rb_tree::tree< key_type, value_type, first_of<>, key_compare, allocator_type >::const_pointer
const value_type * const_pointer
Definition: tree.h:695
ystdex::details::rb_tree::tree::emplace_hint_unique_node
iterator emplace_hint_unique_node(const_iterator position, link_type nd)
Definition: tree.h:1894
ystdex::details::rb_tree::tree::find_tr
const_iterator find_tr(const _tTransKey &k) const
Definition: tree.h:2145
ystdex::details::rb_tree::tree_iterator
Definition: tree.h:525
ystdex::cpp2017::allocator_traits
Definition: allocator.hpp:384
ystdex::cpp2017::reverse_iterator
Definition: range.hpp:116
ystdex::details::rb_tree::tree< key_type, value_type, first_of<>, key_compare, allocator_type >::const_reference
const value_type & const_reference
Definition: tree.h:697
ystdex::details::rb_tree::tree_merge_helper::~tree_merge_helper
~tree_merge_helper()=delete
ystdex::details::rb_tree::tree::copy_node
link_type copy_node(const tree &x, const _tNodeGen &node_gen)
Definition: tree.h:1432
ystdex::cpp2014::enable_if_t
typename enable_if< _bCond, _type >::type enable_if_t
Definition: meta.hpp:199
ystdex::details::node_handle::p_key
ptr_t< _tKey > p_key
Definition: tree.h:199
ystdex::dep_ops::equality_comparable
_t< details::ops_seq< _type, _type2, _tOpt, cond_t< is_same< _type, _type2 >, index_sequence< 7 >, index_sequence< 6, 7, 8 > >> > equality_comparable
Definition: operators.hpp:265
ystdex::details::rb_tree::tree::lower_bound_impl
static _tIter lower_bound_impl(_tTree &t, _tLink x, _tBasePtr y, const _tKey &k)
Definition: tree.h:1464
ystdex::details::rb_tree::tree::begin
const_iterator begin() const
Definition: tree.h:1061
YB_FLATTEN
#define YB_FLATTEN
标记函数尽可能内联定义内的调用。
Definition: ydef.h:843
ystdex::details::rb_tree::tree_const_iterator::reference
const _type & reference
Definition: tree.h:595
ystdex::details::rb_tree::tree::tree
tree(tree &&)=default
platform::size_t
YB_ATTR_nodiscard YF_API size_t
Definition: FileIO.h:1345
ystdex::details::rb_tree::tree::construct_node
void construct_node(link_type nd, _tParams &&... args)
Definition: tree.h:1134
ystdex::details::node_insert_return::position
_tIter position
Definition: tree.h:334
ystdex::details::rb_tree::tree_iterator::p_node
base_ptr p_node
Definition: tree.h:545
ystdex::details::rb_tree::tree_node::storage
standard_layout_storage< aligned_storage_t< sizeof(_type), std::alignment_of< _type >::value > > storage
Definition: tree.h:484
ystdex::details::rb_tree::tree::components::components
components(const components &x)
Definition: tree.h:844
ystdex::cpp2014::aligned_storage_t
typename aligned_storage< _vLen, _vAlign >::type aligned_storage_t
Definition: meta.hpp:187
ystdex::details::rb_tree::tree_header::tree_header
tree_header(tree_header &&x)
Definition: tree.h:442
ystdex::details::rb_tree::tree::insert_hint_unique
iterator insert_hint_unique(const_iterator position, _tParam &&x)
Definition: tree.h:1762
ystdex::any_ops::construct
auto construct(any_storage &storage, _tParams &&... args) -> enable_if_t< is_convertible< well_formed_t< decltype(_tHandler::manage), decltype(_tHandler::init(storage, std::forward< decltype(args)>(args)...))>, any_manager >::value, any_manager >
使用指定处理器初始化存储。
Definition: any.h:418
ystdex::details::rb_tree::tree::upper_bound_impl
static _tIter upper_bound_impl(_tTree &t, _tLink x, _tBasePtr y, const _tKey &k)
Definition: tree.h:1485
ystdex::details::rb_tree::tree::select_value
static const_reference select_value(const_link_type x)
Definition: tree.h:1260
ystdex::details::rb_tree::tree_iterator::value_type
_type value_type
Definition: tree.h:534
ystdex::details::rb_tree::tree::rightmost
const_base_ptr rightmost() const
Definition: tree.h:1221
ystdex::details::rb_tree::tree::upper_bound_impl
static _tIter upper_bound_impl(_tTree &t, const key_type &k)
Definition: tree.h:1499
ystdex::details::rb_tree::tree::components::components
components(const _tKeyComp &comp, node_allocator &&a)
Definition: tree.h:841
ynoexcept_spec
#define ynoexcept_spec(...)
表达式 noexcept 异常规范。
Definition: ydef.h:1181
ystdex::details::node_handle
映射容器的节点句柄。
Definition: tree.h:187
ystdex::details::rb_tree::tree::reuse_or_alloc_node::operator()
link_type operator()(_tParam &&arg) const
Definition: tree.h:782
ystdex::details::rb_tree::tree< key_type, value_type, first_of<>, key_compare, allocator_type >::value_type
value_type value_type
Definition: tree.h:693
ystdex::details::rb_tree::tree::deallocate_node
void deallocate_node(link_type p)
Definition: tree.h:1127
ystdex::details::rb_tree::tree::lower_bound_tr
iterator lower_bound_tr(const _tTransKey &k)
Definition: tree.h:2166
ystdex::details::node_handle_base::node_handle_base
node_handle_base(node_handle_base &&nh)
Definition: tree.h:102
ystdex::details::rb_tree::tree_iterator::operator*
reference operator*() const
Definition: tree.h:555
ystdex::details::node_handle_base::node_handle_base
node_handle_base(typename node_ator_traits::pointer p, const _tNodeAlloc &a)
Definition: tree.h:108
ystdex::any_ops::distance
@ distance
Definition: any_iterator.hpp:82
ystdex::details::rb_tree::tree_node_base::color
tree_color color
Definition: tree.h:359
ystdex::details::rb_tree::tree_header
Definition: tree.h:434
ystdex::details::rb_tree::tree::alloc_node
Definition: tree.h:733
ystdex::details::rb_tree::tree::copy_node
link_type copy_node(const tree &x)
Definition: tree.h:1441
ystdex::details::rb_tree::tree::get_right
static const_link_type get_right(const_base_ptr x)
Definition: tree.h:1287
ystdex::details::rb_tree::tree_node_base::reset_links
void reset_links()
Definition: tree.h:401
ystdex::details::rb_tree::tree_const_iterator::pointer
const _type * pointer
Definition: tree.h:594
ystdex::details::rb_tree::tree::insert_range_unique
enable_if_t<!has_iterator_value_type< value_type, _tIn >::value > insert_range_unique(_tIn first, _tIn last)
Definition: tree.h:1942
ystdex::details::node_handle::mapped
mapped_type & mapped() const
Definition: tree.h:248
ystdex::details::rb_tree::tree::lower_bound
const_iterator lower_bound(const key_type &k) const
Definition: tree.h:2106
ystdex::details::rb_tree::tree::destroy_node
void destroy_node(link_type nd)
Definition: tree.h:1160
ystdex::details::node_handle::mapped_type
typename _type::second_type mapped_type
Definition: tree.h:232
ystdex::details::node_handle< _type, _type, _tNodeAlloc >::~node_handle
~node_handle()=default
ystdex::details::rb_tree::tree::emplace_equal
iterator emplace_equal(_tParams &&... args)
Definition: tree.h:1865
ystdex::details::node_handle_base::alloc
optional< _tNodeAlloc > alloc
Definition: tree.h:90
ystdex::details::rb_tree::tree::key_comp
_fComp key_comp() const
Definition: tree.h:2076
ystdex::details::rb_tree::tree::reinsert_node_equal
iterator reinsert_node_equal(node_type &&nh)
Definition: tree.h:2331
ystdex::details::node_handle_base::node_handle_base
node_handle_base()=default
ystdex::details::rb_tree::tree::end
iterator end()
Definition: tree.h:1067
CHRLib::f
f(d, s)
yconstfn_relaxed
#define yconstfn_relaxed
指定编译时没有 C++11 限制和隐式成员 const 的常量函数。
Definition: ydef.h:1097
NPL::A1::Internals::cur
_fCurrent && cur
Definition: NPLA1Internals.h:591
ystdex::details::rb_tree::tree_key_compare::key_compare
_tKeyComp key_compare
Definition: tree.h:414
ystdex::details::rb_tree::tree::attach_node
void attach_node(bool insert_left, base_ptr p, link_type nd)
Definition: tree.h:1178
ystdex::details::rb_tree::tree_const_iterator::operator==
bool operator==(const tree_const_iterator &x) const
Definition: tree.h:645
ystdex::details::rb_tree::tree_node_base::right
base_ptr right
Definition: tree.h:360
YAssert
#define YAssert(_expr, _msg)
Definition: cassert.h:154
ystdex::details::rb_tree::tree_const_iterator::difference_type
ptrdiff_t difference_type
Definition: tree.h:596
ystdex::swap_dependent
void swap_dependent(_type &x, _type &y)(is_nothrow_swappable< _type >())
支持基于 ystdex_swap::swap 的 ADL 的左值交换。
Definition: swap.hpp:371
ystdex::details::rb_tree::tree::get_left
static link_type get_left(base_ptr x)
Definition: tree.h:1271
ystdex::details::rb_tree::tree::root
const_base_ptr root() const
Definition: tree.h:1199
ystdex::details::rb_tree::tree::operator=
tree & operator=(tree &&x)
Definition: tree.h:949
allocator.hpp
分配器接口。
ystdex::details::node_handle::ptr_t
typename std::pointer_traits< typename ator_traits::pointer >::template rebind< remove_reference_t< _tObj > > ptr_t
Definition: tree.h:197
ystdex::details::rb_tree::tree::rightmost
base_ptr & rightmost()
Definition: tree.h:1216
ystdex::details::node_handle::key
key_type & key() const
Definition: tree.h:241
ystdex::details::rb_tree::tree::erase
void erase(const key_type *first, const key_type *last)
Definition: tree.h:2027
ystdex::details::rb_tree::tree_iterator::iterator_category
std::bidirectional_iterator_tag iterator_category
Definition: tree.h:533
ystdex::details::rb_tree::tree_header::node_count
size_t node_count
Definition: tree.h:435
ystdex::details::rb_tree::tree::select_key
static const _tKey & select_key(const_link_type x)
Definition: tree.h:1254
CHRLib::args
YB_ATTR_nodiscard _tParams && args
Definition: CharacterProcessing.h:649
ystdex::details::rb_tree::tree::rb_verify
bool rb_verify() const
验证红黑树满足约束。
Definition: tree.h:2245
ystdex::details::rb_tree::tree::erase_it
void erase_it(iterator first, iterator last)
Definition: tree.h:1977
ystdex::details::rb_tree::tree_rebalance_for_erase
tree_node_base * tree_rebalance_for_erase(tree_node_base *, tree_node_base &)
Definition: tree.cpp:245
ystdex::details::rb_tree::tree_header::reset
void reset()
Definition: tree.h:464
ystdex::details::rb_tree::tree::max_size
size_type max_size() const
Definition: tree.h:1112
ystdex::details::rb_tree::tree::size
size_type size() const
Definition: tree.h:1106
ystdex::details::rb_tree::tree::insert_equal
iterator insert_equal(_tParam &&v, const _tNodeGen &node_gen)
Definition: tree.h:1747
yassume
#define yassume(_expr)
假定：环境语义。
Definition: cassert.h:96
ystdex::standard_layout_storage
任意标准布局类型对象提供空间的存储。
Definition: type_pun.hpp:308
ystdex::details::rb_tree::tree_color::red
@ red
ystdex::details::rb_tree::tree_node_base::minimum
static const_base_ptr minimum(const_base_ptr x)
Definition: tree.h:385
ystdex::details::rb_tree::tree_iterator::reference
_type & reference
Definition: tree.h:536
ystdex::allocator_guard_delete
释放分配器分配的存储资源的删除器。
Definition: allocator.hpp:767
ystdex::details::rb_tree::tree::node_begin
const_link_type node_begin() const
Definition: tree.h:1232
ystdex::details::rb_tree::tree::insert_equal_lower_node
iterator insert_equal_lower_node(link_type nd)
Definition: tree.h:1375
ystdex::cpp2017::optional
可选值对象包装。
Definition: optional.h:81
YB_ATTR_returns_nonnull
#define YB_ATTR_returns_nonnull
指示返回非空属性。
Definition: ydef.h:761
ystdex::details::rb_tree::tree< key_type, value_type, first_of<>, key_compare, allocator_type >::key_type
key_type key_type
Definition: tree.h:692
ystdex::details::node_handle_base::move_assign
void move_assign(node_handle_base &nh, true_)
Definition: tree.h:169
ystdex::details::rb_tree::tree_iterator::difference_type
ptrdiff_t difference_type
Definition: tree.h:537
ystdex::details::rb_tree::tree::insert_range_equal
enable_if_t<!has_iterator_value_type< value_type, _tIn >::value > insert_range_equal(_tIn first, _tIn last)
Definition: tree.h:1959
ystdex::details::rb_tree::tree::lower_bound_link
iterator lower_bound_link(link_type x, base_ptr y, const _tKey &k)
Definition: tree.h:1551
ystdex::details::rb_tree::tree::is_insert_left_strict
bool is_insert_left_strict(base_ptr p, const _tParam &arg)
Definition: tree.h:1326
ystdex::details::rb_tree::tree_node_base::maximum
static const_base_ptr maximum(const_base_ptr x)
Definition: tree.h:370
YB_ALLOCATOR
#define YB_ALLOCATOR
指示返回指针的函数或函数模板若为非空值则对应的存储不和其它对象指针共享别名。
Definition: ydef.h:785
ystdex::details::rb_tree::tree::objects
components< _fComp > objects
Definition: tree.h:864
ystdex::details::rb_tree::tree::tree
tree(const allocator_type &a)
Definition: tree.h:868
ystdex::details::ebases
Definition: operators.hpp:108
ystdex::details::rb_tree::tree::detach_node
link_type detach_node(base_ptr cur)
Definition: tree.h:1186
ystdex::or_
逻辑或。
Definition: integral_constant.hpp:172
yforward
#define yforward(_expr)
根据参数类型使用 std::forward 转发对应参数。
Definition: ydef.h:1508
ystdex::details::node_handle::swap
void swap(node_handle &nh)
Definition: tree.h:255
ystdex::details::rb_tree::tree::maximum
static const_base_ptr maximum(const_base_ptr x)
Definition: tree.h:1298
ystdex::details::rb_tree::tree::insert_left_q
bool insert_left_q(const std::pair< base_ptr, base_ptr > &pr, const key_type &k)
Definition: tree.h:1341
ystdex::details::rb_tree::tree::end
const_iterator end() const
Definition: tree.h:1072
ystdex::details::node_handle< _type, _type, _tNodeAlloc >::value_type
_type value_type
Definition: tree.h:292
ystdex::details::node_handle::swap
friend void swap(node_handle &x, node_handle &y)
Definition: tree.h:263
ystdex::details::rb_tree::tree::merge_unique
void merge_unique(compatible_tree_type< _fComp2 > &src)
从兼容容器合并唯一的键。
Definition: tree.h:2418
ystdex::details::node_handle< _type, _type, _tNodeAlloc >::node_handle
node_handle(node_handle &&)=default
ystdex::details::rb_tree::tree::drop_node
void drop_node(link_type nd)
Definition: tree.h:1169
ystdex::details::rb_tree::tree::erase_it
void erase_it(iterator position)
Definition: tree.h:1971
ystdex::details::rb_tree::tree::move_data
void move_data(tree &x, false_)
转移可能不相等分配器的容器元素。
Definition: tree.h:974
YSLib::Drawing::src
src
Definition: YGDI.h:442
ystdex::details::rb_tree::tree::emplace_hint_equal_node
iterator emplace_hint_equal_node(const_iterator position, link_type nd)
Definition: tree.h:1918
ystdex::cpp2017::is_invocable
Definition: invoke.hpp:364
ystdex::details::rb_tree::tree::copy_node
link_type copy_node(const_link_type x, base_ptr p, const _tNodeGen &node_gen)
Definition: tree.h:1391
ystdex::details::rb_tree::tree::const_link_type
const value_node * const_link_type
Definition: tree.h:724
ystdex::details::rb_tree::tree_const_iterator::operator==
bool operator==(const iterator &x) const
Definition: tree.h:650
ystdex::details::rb_tree::tree::count
size_type count(const key_type &k) const
Definition: tree.h:2093
ystdex::details::node_handle_base::destroy
void destroy()
Definition: tree.h:143
ystdex::details::rb_tree::tree::get_left
static const_link_type get_left(const_base_ptr x)
Definition: tree.h:1276
ystdex::details::rb_tree::tree_node_base::const_base_ptr
const tree_node_base * const_base_ptr
Definition: tree.h:356
ystdex::details::rb_tree::tree::emplace_unique_node
std::pair< iterator, bool > emplace_unique_node(link_type nd)
Definition: tree.h:1849
ystdex::details::rb_tree::tree_header::tree_header
tree_header()
Definition: tree.h:437
ystdex::details::rb_tree::tree::root
base_ptr & root()
Definition: tree.h:1194
ystdex::details::rb_tree::tree::minimum
static const_base_ptr minimum(const_base_ptr x)
Definition: tree.h:1309
ystdex::details::rb_tree::tree::reuse_or_alloc_node::adjust
base_ptr adjust() const
Definition: tree.h:791
std
Definition: optional.h:982
ystdex::details::rb_tree::tree::equal_range
std::pair< const_iterator, const_iterator > equal_range(const key_type &k) const
Definition: tree.h:2128
ystdex::details::rb_tree::tree_node_base::minimum
static base_ptr minimum(base_ptr x)
Definition: tree.h:378
ystdex::details::rb_tree::tree::insert_attach
iterator insert_attach(bool insert_left, base_ptr p, link_type nd)
Definition: tree.h:1333
ystdex::details::rb_tree::tree_node_base::parent
base_ptr parent
Definition: tree.h:360
ystdex::details::rb_tree::tree::get_right
static link_type get_right(base_ptr x)
Definition: tree.h:1282
ystdex::details::rb_tree::tree::allocate_node
link_type allocate_node()
Definition: tree.h:1120
ystdex::details::rb_tree::tree_iterator::pointer
_type * pointer
Definition: tree.h:535
ystdex::details::rb_tree::tree::insert_or_drop
_tRes insert_or_drop(link_type nd, _func f)
Definition: tree.h:1825
ystdex::details::rb_tree::tree::get_insert_unique_pos
std::pair< base_ptr, base_ptr > get_insert_unique_pos(const key_type &k)
Definition: tree.h:1574
ystdex::details::rb_tree::tree::insert_unique
std::pair< iterator, bool > insert_unique(_tParam &&v)
Definition: tree.h:1708
ystdex::details::node_insert_return
Definition: tree.h:333
ystdex::details::rb_tree::tree_const_iterator::iterator_category
std::bidirectional_iterator_tag iterator_category
Definition: tree.h:592
YSLib::i
return i
Definition: YCoreUtilities.h:177
ystdex::details::rb_tree::tree< key_type, value_type, first_of<>, key_compare, allocator_type >::pointer
value_type * pointer
Definition: tree.h:694
ystdex::details::rb_tree::tree::find
const_iterator find(const key_type &k) const
Definition: tree.h:2087
ystdex::details::rb_tree::tree::move_assign_elements
void move_assign_elements(tree &x, true_)
转移赋值相等或在转移赋值时传播的分配器的容器元素。
Definition: tree.h:1027
yunseq
#define yunseq
无序列依赖表达式组求值。
Definition: ydef.h:1535
ystdex::details::rb_tree::tree::components
Definition: tree.h:826
ystdex::dep_ops::totally_ordered
details::flat_ops< _type, _type2, _tOpt, less_than_comparable, equality_comparable > totally_ordered
Definition: operators.hpp:389
ystdex::details::rb_tree::tree_iterator::link_type
tree_node< _type > * link_type
Definition: tree.h:543
ystdex::details::rb_tree::tree::select_value
static const_reference select_value(const_base_ptr x)
Definition: tree.h:1265
ystdex::details::rb_tree::tree_color
tree_color
Definition: tree.h:345
ystdex::details::rb_tree::tree_const_iterator
Definition: tree.h:519
ystdex::details::rb_tree::tree::find_tr
iterator find_tr(const _tTransKey &k)
Definition: tree.h:2138
ystdex::details::rb_tree::tree::move_data
void move_data(tree &x, true_)
转移相等分配器的容器元素。
Definition: tree.h:992
utility.hpp
实用设施。
ystdex::details::rb_tree::tree_iterator::operator--
tree_iterator & operator--()
Definition: tree.h:568
ystdex::details::node_handle< _type, _type, _tNodeAlloc >::ckey
const value_type & ckey() const
Definition: tree.h:317
ystdex::details::rb_tree::tree::lower_bound_link
const_iterator lower_bound_link(const_link_type x, const_base_ptr y, const _tKey &k) const
Definition: tree.h:1556
ystdex::details::rb_tree::tree::alloc_node::reconstruct
link_type reconstruct(base_ptr p, _tParam &&arg) const
Definition: tree.h:749
ystdex::rebind_alloc_t
typename allocator_traits< _tAlloc >::template rebind_alloc< _type > rebind_alloc_t
Definition: allocator.hpp:423
ystdex::details::rb_tree::tree_const_iterator::cast_mutable
iterator cast_mutable() const
Definition: tree.h:619
ystdex::details::rb_tree::tree::erase
iterator erase(const_iterator position)
Definition: tree.h:1988
ystdex::details::rb_tree::tree::is_insert_left
bool is_insert_left(base_ptr p, const _tParam &arg)
Definition: tree.h:1318
ystdex::details::rb_tree::tree::get_insert_equal_pos
std::pair< base_ptr, base_ptr > get_insert_equal_pos(const key_type &k)
Definition: tree.h:1603
ystdex::details::rb_tree::tree::reuse_or_alloc_node::nodes
base_ptr nodes
Definition: tree.h:761
ystdex::details::rb_tree::tree::emplace_equal_node
iterator emplace_equal_node(link_type nd)
Definition: tree.h:1873
ystdex::details::rb_tree::tree::extract
node_type extract(const key_type &k)
Definition: tree.h:2405
yconstraint
#define yconstraint(_expr)
约束：接口语义。
Definition: cassert.h:125
YSLib::UI::y
SPos SPos y
Definition: YWidget.cpp:44
ystdex::details::rb_tree::tree::iterator
tree_iterator< value_type > iterator
Definition: tree.h:705
ystdex::details::rb_tree::tree::get_insert_hint_equal_pos
std::pair< base_ptr, base_ptr > get_insert_hint_equal_pos(const_iterator position, const key_type &k)
Definition: tree.h:1660
ystdex::details::node_handle_base::allocator_type
rebind_alloc_t< _tNodeAlloc, _type > allocator_type
Definition: tree.h:84
ystdex::details::rb_tree::tree::alloc_node::tree_ref
tree & tree_ref
Definition: tree.h:734
ystdex::details::rb_tree::tree::get_allocator
allocator_type get_allocator() const
Definition: tree.h:1039
ystdex::true_
bool_< true > true_
Definition: integral_constant.hpp:109
ystdex::details::rb_tree::tree_key_compare::tree_key_compare
tree_key_compare(const _tKeyComp &comp)
Definition: tree.h:419
ystdex::details::rb_tree::tree::upper_bound_link
iterator upper_bound_link(link_type x, base_ptr y, const _tKey &k)
Definition: tree.h:1562
ystdex::details::rb_tree::tree::leftmost
const_base_ptr leftmost() const
Definition: tree.h:1210
ystdex::details::node_handle_base
节点句柄基类。
Definition: tree.h:79
CHRLib::s
_tDst const _tSrc * s
Definition: CharacterProcessing.h:143
ystdex::details::rb_tree::tree::erase
iterator erase(iterator position)
Definition: tree.h:1999
ystdex::details::node_handle_base::empty
bool empty() const
Definition: tree.h:163
ystdex::details::rb_tree::tree::insert_hint_equal
iterator insert_hint_equal(const_iterator position, _tParam &&v, const _tNodeGen &node_gen)
Definition: tree.h:1799
ystdex::cond_t
_t< cond< _tCond, _tThen, _tElse > > cond_t
Definition: meta.hpp:794
ystdex::details::rb_tree::tree::find_impl
static _tIter find_impl(_tTree &t, const key_type &k)
Definition: tree.h:1541
ystdex::details::rb_tree::tree< key_type, value_type, first_of<>, key_compare, allocator_type >::allocator_type
allocator_type allocator_type
分配器类型。
Definition: tree.h:704
ystdex::details::rb_tree::tree_key_compare
Definition: tree.h:413
ystdex::details::rb_tree::tree_iterator::operator==
bool operator==(const tree_iterator &x) const
Definition: tree.h:575
ystdex::details::rb_tree::tree_key_compare::tree_key_compare
tree_key_compare()
Definition: tree.h:417
ystdex::details::rb_tree::tree::upper_bound_tr
const_iterator upper_bound_tr(const _tTransKey &k) const
Definition: tree.h:2199
ystdex::details::rb_tree::tree_merge_helper
Definition: tree.h:671
ystdex::details::rb_tree::tree_const_iterator::iterator
tree_iterator< _type > iterator
Definition: tree.h:600
optional.h
可选值包装类型。
ystdex::details::rb_tree::tree::reuse_or_alloc_node::reuse_or_alloc_node
reuse_or_alloc_node(tree &t)
Definition: tree.h:763
ystdex::details::rb_tree::tree::operator<
friend bool operator<(const tree &x, const tree &y)
Definition: tree.h:2474
YB_API
#define YB_API
YBase 应用程序编程接口：用于向库文件约定链接。
Definition: ydef.h:985
ystdex::details::rb_tree::tree::equal_range_tr
std::pair< iterator, iterator > equal_range_tr(const _tTransKey &k)
Definition: tree.h:2218
ystdex::details::node_handle::ckey
const key_type & ckey() const
Definition: tree.h:235
ystdex::details::rb_tree::tree_increment
tree_node_base * tree_increment(tree_node_base *)
Definition: tree.cpp:136
ystdex::details::node_handle_base::swap_base
void swap_base(node_handle_base &nh)
Definition: tree.h:131
ystdex::details::rb_tree::tree_decrement
tree_node_base * tree_decrement(tree_node_base *)
Definition: tree.cpp:147
ystdex::details::rb_tree::tree::upper_bound
const_iterator upper_bound(const key_type &k) const
Definition: tree.h:2117
v
byte v
Definition: CharRenderer.cpp:76
ystdex::details::rb_tree::tree::erase
iterator erase(const_iterator first, const_iterator last)
Definition: tree.h:2019
ystdex::details::rb_tree::tree::create_node
link_type create_node(_tParams &&... args)
Definition: tree.h:1151
ystdex::details::rb_tree::tree::insert_return_type
node_insert_return< cond_t< is_same< _tKey, _type >, const_iterator, iterator >, node_type > insert_return_type
Definition: tree.h:718
ystdex::details::rb_tree::tree::const_iterator
tree_const_iterator< value_type > const_iterator
Definition: tree.h:706
ynothrowv
#define ynothrowv
YSLib 无异常抛出保证验证：有条件地使用无异常抛出规范。
Definition: ydef.h:1219
ystdex
<memory> 特性测试宏。
Definition: ydef.h:1262
ystdex::details::node_handle_base::ptr
node_ator_traits::pointer ptr
Definition: tree.h:93
ystdex::alloc_on_move
void alloc_on_move(_tAlloc &x, _tAlloc &y)
按分配器特征在传播容器时转移分配器。
Definition: allocator.hpp:1038
ystdex::details::rb_tree::tree::merge_equal
void merge_equal(compatible_tree_type< _fComp2 > &src)
从兼容容器合并等价的键。
Definition: tree.h:2443
ystdex::details::rb_tree::tree::insert_equal_lower
iterator insert_equal_lower(_tParam &&v)
Definition: tree.h:1355
ystdex::details::rb_tree::tree::reuse_or_alloc_node::~reuse_or_alloc_node
~reuse_or_alloc_node()
Definition: tree.h:775
ystdex::details::rb_tree::tree::insert_equal
iterator insert_equal(_tParam &&v)
Definition: tree.h:1738
ystdex::details::rb_tree::tree::equal_range_tr
std::pair< const_iterator, const_iterator > equal_range_tr(const _tTransKey &k) const
Definition: tree.h:2227
ystdex::details::rb_tree::tree::insert_node
iterator insert_node(base_ptr x, base_ptr p, link_type nd)
Definition: tree.h:1347
YSLib::_tParams
YB_ATTR_nodiscard YB_PURE typename _tParams
Definition: ValueNode.h:1294
ystdex::details::rb_tree::tree::operator==
friend bool operator==(const tree &x, const tree &y)
Definition: tree.h:2467
ystdex::details::rb_tree::tree::move_assign_elements
void move_assign_elements(tree &x, false_)
转移赋值可能不相等的不在转移赋值时传播的分配器的容器元素。
Definition: tree.h:1002
ystdex::details::rb_tree::tree::tree
tree(tree &&x, const allocator_type &a)
Definition: tree.h:887
ystdex::details::rb_tree::tree_node::access_ptr
_type * access_ptr()
Definition: tree.h:488
ystdex::details::rb_tree::tree::select_key
static const _tKey & select_key(const_base_ptr x)
Definition: tree.h:1249
ystdex::details::rb_tree::tree::emplace_hint_unique
iterator emplace_hint_unique(const_iterator position, _tParams &&... args)
Definition: tree.h:1885
ystdex::standard_layout_storage::access
void * access()
Definition: type_pun.hpp:335
ystdex::details::rb_tree::tree_const_iterator::tree_const_iterator
tree_const_iterator()=default
ystdex::details::rb_tree::tree_const_iterator::p_node
base_ptr p_node
Definition: tree.h:606
ystdex::details::rb_tree::tree::begin
iterator begin()
Definition: tree.h:1056
ystdex::details::rb_tree::tree_key_compare::tree_key_compare
tree_key_compare(tree_key_compare &&x)
Definition: tree.h:426
ystdex::details::rb_tree::tree::components::components
components(components &&x, node_allocator a)
Definition: tree.h:851
ystdex::cpp2014::equal
bool equal(_tIn1 first1, _tIn1 last1, _tIn2 first2, _tIn2 last2, _fBiPred binary_pred)
Definition: algorithm.hpp:205
ystdex::details::rb_tree::tree::const_reverse_iterator
ystdex::reverse_iterator< const_iterator > const_reverse_iterator
Definition: tree.h:708
ystdex::details::rb_tree::tree::count_tr
size_type count_tr(const _tTransKey &k) const
Definition: tree.h:2156
ystdex::details::rb_tree::tree::node_end
const_base_ptr node_end() const
Definition: tree.h:1243
ystdex::details::rb_tree::tree::clear
void clear()
Definition: tree.h:2060
ystdex::details::rb_tree::tree::reuse_or_alloc_node::root
base_ptr root
Definition: tree.h:760
ystdex::details::node_handle::node_handle
node_handle()=default
ystdex::details::rb_tree::tree< key_type, value_type, first_of<>, key_compare, allocator_type >::node_allocator
rebind_alloc_t< allocator_type, value_node > node_allocator
Definition: tree.h:713
ystdex::any_ops::destroy
@ destroy
销毁被管理的对象。
Definition: any.h:292
ystdex::details::rb_tree::tree_const_iterator::operator*
reference operator*() const
Definition: tree.h:625
ystdex::details::node_handle_base::operator=
node_handle_base & operator=(node_handle_base &&nh)
Definition: tree.h:113
ystdex::details::rb_tree::tree::components::components
components()
Definition: tree.h:832
ystdex::details::rb_tree::tree_color::black
@ black
ystdex::details::rb_tree::tree_iterator::tree_iterator
tree_iterator()=default
ystdex::details::rb_tree::tree::erase_node
void erase_node(link_type x)
Definition: tree.h:1449
ystdex::details::rb_tree::tree< key_type, value_type, first_of<>, key_compare, allocator_type >::difference_type
ptrdiff_t difference_type
Definition: tree.h:699
ystdex::details::rb_tree::tree::rend
const_reverse_iterator rend() const
Definition: tree.h:1094
ystdex::details::node_handle::key_type
_tKey key_type
Definition: tree.h:231
platform::p
return p p
Definition: YCLib/FileSystem.h:209
ystdex::alloc_on_copy
void alloc_on_copy(_tAlloc &x, const _tAlloc &y)
按分配器特征在传播容器时复制赋值分配器。
Definition: allocator.hpp:1017
ystdex::details::rb_tree::tree< key_type, value_type, first_of<>, key_compare, allocator_type >::size_type
size_t size_type
Definition: tree.h:698
ystdex::details::rb_tree::tree::insert_unique
std::pair< iterator, bool > insert_unique(_tParam &&v, const _tNodeGen &node_gen)
Definition: tree.h:1717
ystdex::details::rb_tree::tree::components::components
components(components &&)=default
ystdex::details::rb_tree::tree_node_base::base_ptr
tree_node_base * base_ptr
Definition: tree.h:355
ystdex::details::rb_tree::tree::get_node_allocator
node_allocator & get_node_allocator()
Definition: tree.h:1045
const
const Decapsulate const Decapsulate &y ynothrow ContextNode &ctx const
Definition: NPLA1Forms.cpp:1629
yimpl
#define yimpl(...)
实现标签。
Definition: ydef.h:413
ystdex::details::rb_tree::tree::alloc_node::alloc_node
alloc_node(tree &t)
Definition: tree.h:736
ystdex::details::rb_tree::tree::tree
tree()=default
ystdex::details::rb_tree::tree::equal_range
std::pair< iterator, iterator > equal_range(const key_type &k)
Definition: tree.h:2123
platform::bool
YB_ATTR_nodiscard std::FILE *fp bool
Definition: FileIO.h:1271
ystdex::details::rb_tree::tree::~tree
~tree()
Definition: tree.h:916
ystdex::path_category::node
@ node
ystdex::details::node_insert_return::node
_tNodeHandle node
Definition: tree.h:336
ystdex::false_
bool_< false > false_
Definition: integral_constant.hpp:110
ystdex::details::rb_tree::tree_node_base::maximum
static base_ptr maximum(base_ptr x)
Definition: tree.h:363
ystdex::details::rb_tree::tree::alloc_node::operator()
link_type operator()(_tParam &&arg) const
Definition: tree.h:742
ynothrow
#define ynothrow
YSLib 无异常抛出保证：若支持 noexcept 关键字， 指定特定的 noexcept 异常规范。
Definition: ydef.h:1199
ystdex::details::rb_tree::tree::lower_bound
iterator lower_bound(const key_type &k)
Definition: tree.h:2101
ystdex::bases::noncopyable
不可复制对象：禁止派生类调用默认原型的复制构造函数和复制赋值操作符。
Definition: base.h:50
ystdex::details::rb_tree::tree::tree
tree(tree &&x, node_allocator a, false_)
Definition: tree.h:907
ystdex::details::rb_tree::tree::base_ptr
tree_node_base * base_ptr
Definition: tree.h:721
ystdex::details::rb_tree::tree::upper_bound_link
const_iterator upper_bound_link(const_link_type x, const_base_ptr y, const _tKey &k) const
Definition: tree.h:1567
ystdex::details::rb_tree::tree::node_end
base_ptr node_end()
Definition: tree.h:1238
ystdex::details::rb_tree::tree_insert_and_rebalance
void tree_insert_and_rebalance(bool, tree_node_base *, tree_node_base *, tree_node_base &)
Definition: tree.cpp:158
ystdex::details::rb_tree::tree::rbegin
reverse_iterator rbegin()
Definition: tree.h:1078
ystdex::details::rb_tree::tree::reinsert_node_hint_unique
iterator reinsert_node_hint_unique(const_iterator hint, node_type &&nh)
Definition: tree.h:2352
ystdex::allocator_guard
std::unique_ptr< alloc_value_t< _tAlloc >, allocator_guard_delete< _tAlloc > > allocator_guard
分配器守卫。
Definition: allocator.hpp:869
ystdex::details::rb_tree::tree::get_insert_hint_unique_pos
std::pair< base_ptr, base_ptr > get_insert_hint_unique_pos(const_iterator position, const key_type &k)
Definition: tree.h:1618
ynoexcept
#define ynoexcept(...)
YSLib 无异常抛出保证：指定特定的异常规范。
Definition: ydef.h:1151
ystdex::details::rb_tree::tree::tree
tree(tree &&x, node_allocator &&a)
Definition: tree.h:892
ystdex::details::rb_tree::tree_iterator::operator++
tree_iterator & operator++()
Definition: tree.h:561
ystdex::details::rb_tree::tree_header::move_data
void move_data(tree_header &from)
Definition: tree.h:455
ystdex::details::rb_tree::tree::equal_alloc_or_pocma
or_< typename node_ator_traits::is_always_equal, typename node_ator_traits::propagate_on_container_move_assignment > equal_alloc_or_pocma
Definition: tree.h:731
ystdex::details::rb_tree::tree::reverse_iterator
ystdex::reverse_iterator< iterator > reverse_iterator
Definition: tree.h:707
ystdex::details::rb_tree::tree::erase
size_type erase(const key_type &x)
Definition: tree.h:2010
ystdex::details::rb_tree::tree::tree
tree(tree &&x, node_allocator a, true_)
Definition: tree.h:902
ystdex::details::rb_tree::tree::minimum
static base_ptr minimum(base_ptr x)
Definition: tree.h:1304
ystdex::details::rb_tree::tree::equal_range_impl
std::pair< _tIter, _tIter > equal_range_impl(_tTree &t, const key_type &k)
Definition: tree.h:1507
ystdex::details::rb_tree::tree::lower_bound_impl
static _tIter lower_bound_impl(_tTree &t, const key_type &k)
Definition: tree.h:1478
ystdex::details::rb_tree::tree< key_type, value_type, first_of<>, key_compare, allocator_type >::reference
value_type & reference
Definition: tree.h:696
ystdex::details::rb_tree::tree_const_iterator::operator--
tree_const_iterator & operator--()
Definition: tree.h:638
ystdex::cpp2017::as_const
add_const_t< _type > & as_const(_type &t)
转换 const 引用。
Definition: utility.hpp:77
ystdex::details::rb_tree::tree::rbegin
const_reverse_iterator rbegin() const
Definition: tree.h:1083
ystdex::details::rb_tree::tree::insert_range_unique
enable_if_t< has_iterator_value_type< value_type, _tIn >::value > insert_range_unique(_tIn first, _tIn last)
Definition: tree.h:1933
yconstfn
#define yconstfn
指定编译时常量函数。
Definition: ydef.h:1073
YSLib::a
YB_PURE const _type * a
Definition: YCoreUtilities.h:168
NPL::_tParam
_tParam
Definition: NPLA.h:2367
platform::l
return l
Definition: YCLib/FileSystem.h:402
ystdex::details::node_handle::pointer_to
ptr_t< _tObj > pointer_to(_tObj &obj)
Definition: tree.h:271
ystdex::details::rb_tree::tree_merge_helper< tree< _tKey, _type, _fKeyOfValue, _fComp1, _tAlloc >, _fComp2 >::get_components
static auto get_components(tree< _tKey, _type, _fKeyOfValue, _fComp2, _tAlloc > &tree) -> decltype((tree.objects))
Definition: tree.h:2491
ystdex::details::rb_tree::tree::const_base_ptr
const tree_node_base * const_base_ptr
Definition: tree.h:722
ystdex::and_
逻辑操作元函数。
Definition: integral_constant.hpp:151
ystdex::details::node_handle_base::get_allocator
allocator_type get_allocator() const
Definition: tree.h:156
ystdex::details::rb_tree::tree_const_iterator::value_type
_type value_type
Definition: tree.h:593
ystdex::details::rb_tree::tree::assign_equal
void assign_equal(_tIter first, _tIter last)
Definition: tree.h:2291