YSTest: list.hpp 源文件

YSTest PreAlpha_b900_20201012 The YSLib Test Project

list.hpp
浏览该文件的文档.
1 /*
2 © 2019-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
28 #ifndef YB_INC_ystdex_list_hpp_
29 #define YB_INC_ystdex_list_hpp_ 1
30
31 #include "node_base.h" // for "node_base.h", std::move, std::addressof;
32 #include <list> // for <list>, std::initializer_list;
33 #include "allocator.hpp" // for aligned_storage_t, standard_layout_storage,
34 // bidirectional_iteratable, equality_comparable, totally_ordered,
35 // rebind_alloc_t, allocator_traits, yverify, false_, true_,
36 // ystdex::make_move_if_noexcept_iterator, std::advance, ystdex::alloc_on_move,
37 // allocator_guard, allocator_guard_delete, ystdex::alloc_on_swap,
38 // ystdex::swap_dependent, std::allocator, is_object, is_unqualified, and_,
39 // is_allocator_for, ystdex::reverse_iterator, is_nothrow_constructible, less,
40 // ref_eq, equal_to;
41 #include "base.h" // for noncopyable, nonmovable;
42 #include "iterator_trait.hpp" // for enable_for_input_iterator_t;
43 #include <algorithm> // for std::equal, std::lexicographical_compare;
44
45 namespace ystdex
46 {
47
48 #if false
49 // NOTE: For exposition only. Since %ystdex::list has some C++20 features
50 // not proveded by ISO C++17, it should not be in %cpp2017 inline namespace.
51 #if (__cpp_lib_incomplete_container_elements >= 201505L \
52 || __cplusplus >= 201703L) && ((__cpp_lib_erase_if >= 201811L \
53 && __cpp_lib_list_remove_return_type >= 201806L) || __cplusplus >= 201811L)
54 # define YB_Has_Cpp20_list true
55 #else
56 # define YB_Has_Cpp20_list false
57 #endif
58 #undef YB_Has_Cpp20_list
59 #endif
60
61
63 namespace details
64 {
65
66 template<typename _type>
67 class list_node : public list_node_base
68 {
69 private:
70 standard_layout_storage<aligned_storage_t<sizeof(_type), yalignof(_type)>>
71 storage;
72
73 public:
75 YB_ATTR_nodiscard YB_PURE yconstfn_relaxed _type*
76 access_ptr() ynothrow
77 {
78 return static_cast<_type*>(storage.access());
79 }
81 YB_ATTR_nodiscard YB_PURE yconstfn const _type*
82 access_ptr() const ynothrow
83 {
84 return static_cast<const _type*>(storage.access());
85 }
86 };
87
88
89 // XXX: See $2019-09 @ %Documentation::Workflow.
91 template<typename>
92 class list_const_iterator;
93
94
95 template<typename _type>
96 class list_iterator
97 : public bidirectional_iteratable<list_iterator<_type>, _type&>
98 {
100 template<typename, class>
101 friend class list_rep;
103 template<typename>
104 friend class list_const_iterator;
105
106 public:
107 using iterator_category = std::bidirectional_iterator_tag;
108 using value_type = _type;
109 using pointer = _type*;
110 using reference = _type&;
111 using difference_type = ptrdiff_t;
112
113 private:
114 using base_ptr = list_node_base::base_ptr;
115
116 base_ptr p_node{};
117
118 public:
119 list_iterator() ynothrow = default;
120 explicit
121 list_iterator(base_ptr x) ynothrow
122 : p_node(x)
123 {}
124
125 YB_ATTR_nodiscard YB_PURE list_iterator
126 cast_mutable() const ynothrow
127 {
128 return *this;
129 }
130
131 YB_ATTR_nodiscard YB_PURE reference
132 operator*() const ynothrow
133 {
134 return *static_cast< list_node<_type>*>(p_node)->access_ptr();
135 }
136
137 list_iterator&
138 operator++() ynothrow
139 {
140 p_node = p_node->next;
141 return *this;
142 }
143
144 list_iterator&
145 operator--() ynothrow
146 {
147 p_node = p_node->prev;
148 return *this;
149 }
150
151 YB_ATTR_nodiscard YB_PURE bool
152 operator==(const list_iterator& x) const ynothrow
153 {
154 return p_node == x.p_node;
155 }
156 };
157
158
159 template<typename _type>
160 class list_const_iterator
161 : public bidirectional_iteratable<list_const_iterator<_type>, const _type&>,
162 public equality_comparable<list_const_iterator<_type>, list_iterator<_type>>
163 {
165 template<typename, class>
166 friend class list_rep;
167
168 public:
169 using iterator_category = std::bidirectional_iterator_tag;
170 using value_type = _type;
172 using pointer = const _type*;
174 using reference = const _type&;
175 using difference_type = ptrdiff_t;
176
177 private:
178 using base_ptr = list_node_base::const_base_ptr;
179 using iterator = list_iterator<_type>;
180
181 base_ptr p_node = {};
182
183 public:
184 list_const_iterator() ynothrow = default;
185 explicit
186 list_const_iterator(base_ptr x) ynothrow
187 : p_node(x)
188 {}
189 list_const_iterator(const iterator& x) ynothrow
190 : p_node(x.p_node)
191 {}
192
193 YB_ATTR_nodiscard YB_PURE iterator
194 cast_mutable() const ynothrow
195 {
196 return iterator(const_cast<typename iterator::base_ptr>(p_node));
197 }
198
199 YB_ATTR_nodiscard YB_PURE reference
200 operator*() const ynothrow
201 {
202 return *static_cast<const list_node<_type>*>(p_node)->access_ptr();
203 }
204
205 list_const_iterator&
206 operator++() ynothrow
207 {
208 p_node = p_node->next;
209 return *this;
210 }
211
212 list_const_iterator&
213 operator--() ynothrow
214 {
215 p_node = p_node->prev;
216 return *this;
217 }
218
219 YB_ATTR_nodiscard YB_PURE bool
220 operator==(const list_const_iterator& x) const ynothrow
221 {
222 return p_node == x.p_node;
223 }
224 YB_ATTR_nodiscard YB_PURE bool
225 operator==(const iterator& x) const ynothrow
226 {
227 return p_node == x.p_node;
228 }
229 };
230
231
238 template<typename _type, class _tAlloc>
239 class list_rep
240 {
241 public:
242 using size_type = size_t;
243 using difference_type = ptrdiff_t;
244 using allocator_type = _tAlloc;
245 using iterator = list_iterator<_type>;
246 using const_iterator = list_const_iterator<_type>;
247
248 protected:
249 using base_ptr = list_node_base*;
250 using const_base_ptr = const list_node_base*;
251
252 private:
253 using value_node = list_node<_type>;
254
255 public:
256 using link_type = value_node*;
257 using const_link_type = const value_node*;
258
259 private:
260 using node_allocator = rebind_alloc_t<_tAlloc, list_node<_type>>;
261 using node_ator_traits = allocator_traits<node_allocator>;
262 using equal_alloc_or_pocma = or_<typename node_ator_traits::is_always_equal,
263 typename node_ator_traits::propagate_on_container_move_assignment>;
264
265 protected:
266 // TODO: Resolve LWG 2112 with %is_final support.
267 struct components : node_allocator
268 {
269 list_header header{};
270
271 components() ynoexcept_spec(node_allocator())
272 : node_allocator()
273 {}
275 explicit
276 components(node_allocator a) ynothrow
277 : node_allocator(std::move(a))
278 {}
279 components(const components& x)
280 : node_allocator(
281 node_ator_traits::select_on_container_copy_construction(x))
282 {}
283 components(components&&) = default;
285 components(components&& x, node_allocator a) ynothrow
286 : node_allocator(std::move(a)), header(std::move(x.header))
287 {}
288 };
289
290 private:
291 struct node_remove : private noncopyable, private nonmovable
292 {
293 list_rep& list;
294 base_ptr head;
295 base_ptr* p_tail;
296
297 explicit
298 node_remove(list_rep& l) ynothrow
299 : list(l), head(&list.objects.header), p_tail(std::addressof(head))
300 {}
301 ~node_remove()
302 {
303 list.clear_nodes_from(head);
304 }
305
306 // NOTE: Track pending nodes in a singly linked list.
307 void
308 detach(iterator position) ynothrowv
309 {
310 const auto removed(position.p_node);
311
312 yverify(list.objects.header != removed);
313 --list.objects.header.node_count;
314 removed->unhook();
315 removed->next = &list.objects.header;
316 *p_tail = removed;
317 p_tail = &removed->next;
318 }
319 };
320
321 protected:
322 components objects;
323
324 public:
325 list_rep() = default;
326 list_rep(const allocator_type& a) ynothrow
327 : objects(node_allocator(a))
328 {}
329 list_rep(const list_rep& x)
330 : objects(x.objects)
331 {
332 init_range(x.begin(), x.end());
333 }
334 list_rep(list_rep&&) = default;
335 list_rep(list_rep&& x, const allocator_type& a)
336 ynoexcept(node_ator_traits::is_always_equal::value)
337 : list_rep(std::move(x), node_allocator(a),
338 typename node_ator_traits::is_always_equal())
339 {}
340
341 private:
343 list_rep(list_rep&& x, node_allocator a, true_) ynothrow
344 : objects(std::move(x.objects), std::move(a))
345 {}
347 list_rep(list_rep&& x, node_allocator a, false_)
348 : objects(std::move(a))
349 {
350 if(get_node_allocator() == x.get_node_allocator())
351 move_nodes(std::move(x));
352 else
353 insert_range(begin(),
354 ystdex::make_move_if_noexcept_iterator(x.begin()),
355 ystdex::make_move_if_noexcept_iterator(x.end()));
356 }
357
358 public:
359 ~list_rep() ynothrow
360 {
361 clear_nodes();
362 }
363
364 list_rep&
365 operator=(const list_rep& x)
366 {
367 if(std::addressof(x) != this)
368 {
369 if(typename
370 node_ator_traits::propagate_on_container_copy_assignment())
371 {
372 auto& this_alloc(get_node_allocator());
373 auto& that_alloc(x.get_node_allocator());
374
375 if(!typename node_ator_traits::is_always_equal()
376 && this_alloc != that_alloc)
377 clear();
378 ystdex::alloc_on_copy(this_alloc, that_alloc);
379 }
380 assign_range(x.begin(), x.end());
381 }
382 return *this;
383 }
384 list_rep&
385 operator=(list_rep&& x) ynoexcept(yimpl(equal_alloc_or_pocma()))
386 {
387 move_assign_elements(x, equal_alloc_or_pocma());
388 return *this;
389 }
390
391 template<typename _tIn>
392 void
393 init_range(_tIn first, _tIn last)
394 {
395 for(; first != last; ++first)
396 insert_it(end(), *first);
397 }
398
399 template<typename _tIn>
400 void
401 assign_range(_tIn first, _tIn last)
402 {
403 auto i(begin());
404 const auto j(end());
405
406 // XXX: Excessive order refinment by ','?
407 for(; i != j && first != last; ++i, static_cast<void>(++first))
408 *i = *first;
409 if(first == last)
410 erase_range(i, j);
411 else
412 insert_range(j, first, last);
413 }
414
415 YB_ATTR_nodiscard YB_PURE allocator_type
416 get_allocator() const ynothrow
417 {
418 return allocator_type(get_node_allocator());
419 }
420
421 YB_ATTR_nodiscard YB_PURE node_allocator&
422 get_node_allocator() ynothrow
423 {
424 return objects;
425 }
426 YB_ATTR_nodiscard YB_PURE const node_allocator&
427 get_node_allocator() const ynothrow
428 {
429 return objects;
430 }
431
432 YB_ATTR_nodiscard YB_PURE iterator
433 begin() ynothrow
434 {
435 return iterator(objects.header.next);
436 }
437 YB_ATTR_nodiscard YB_PURE const_iterator
438 begin() const ynothrow
439 {
440 return const_iterator(objects.header.next);
441 }
442
443 YB_ATTR_nodiscard YB_PURE iterator
444 end() ynothrow
445 {
446 return iterator(&objects.header);
447 }
448 YB_ATTR_nodiscard YB_PURE const_iterator
449 end() const ynothrow
450 {
451 return const_iterator(&objects.header);
452 }
453
454 YB_ATTR_nodiscard YB_PURE bool
455 empty() const ynothrowv
456 {
457 // XXX: This is not a narrow contract. It checks the sanity of the
458 // implementation.
459 yverify((objects.header.next == &objects.header) == (size() == 0));
460 return size() == 0;
461 }
462
463 YB_ATTR_nodiscard YB_PURE size_type
464 size() const ynothrowv
465 {
466 // XXX: This is not a narrow contract. It checks the sanity of the
467 // implementation.
468 yverify(std::distance(begin(), end())
469 == difference_type(objects.header.node_count));
470 return objects.header.node_count;
471 }
472
473 YB_ATTR_nodiscard YB_PURE size_type
474 max_size() const ynothrow
475 {
476 return node_ator_traits::max_size(get_node_allocator());
477 }
478
479 const_iterator
480 resize_pos(size_type& sz) const
481 {
482 const_iterator i;
483 const size_type len(size());
484
485 if(sz < len)
486 {
487 if(sz <= len / 2)
488 {
489 i = begin();
490 std::advance(i, sz);
491 }
492 else
493 {
494 const ptrdiff_t n_erase(len - sz);
495
496 i = end();
497 std::advance(i, -n_erase);
498 }
499 sz = 0;
500 return i;
501 }
502 else
503 i = end();
504 sz -= len;
505 return i;
506 }
507
508 void
509 append_default(size_type n)
510 {
511 size_type i(0);
512
513 try
514 {
515 for(; i < n; ++i)
516 create_node()->hook(&objects.header);
517 }
518 catch(...)
519 {
520 auto cur(objects.header.prev);
521
522 for(; i != 0; --i)
523 {
524 yverify(&objects.header.prev != &objects.header);
525
526 const auto nd = link_type(cur);
527
528 cur = nd->prev;
529 drop_node(nd);
530 }
531 cur->next = &objects.header;
532 throw;
533 }
534 objects.header.node_count += n;
535 }
536
537 protected:
538 void
539 move_nodes(list_rep&& x) ynothrow
540 {
541 objects.header.move_nodes(std::move(x.objects.header));
542 }
543
548 void
549 move_assign_elements(list_rep& x, false_)
550 {
551 if(get_node_allocator() == x.get_node_allocator())
552 move_assign_elements(x, true_());
553 else
554 assign_range(ystdex::make_move_if_noexcept_iterator(x.begin()),
555 ystdex::make_move_if_noexcept_iterator(x.end()));
556 }
558 void
559 move_assign_elements(list_rep& x, true_) ynothrow
560 {
561 clear_nodes();
562 move_nodes(std::move(x));
563 ystdex::alloc_on_move(get_node_allocator(), x.get_node_allocator());
564 }
565
566 public:
567 template<typename... _tParams>
568 void
569 insert_it(iterator position, _tParams&&... args)
570 {
571 attach_node(create_node(yforward(args)...), position.p_node);
572 }
573
574 template<typename _tIn>
575 iterator
576 insert_range(iterator position, _tIn first, _tIn last)
577 {
578 if(first != last)
579 {
580 list_rep tmp(get_node_allocator());
581
582 tmp.init_range(first, last);
583
584 auto i(tmp.begin());
585
586 splice(position, tmp);
587 return i;
588 }
589 return position.cast_mutable();
590 }
591
592 void
593 erase_it(iterator position) ynothrow
594 {
595 drop_node(detach_node(position.p_node));
596 }
597
598 iterator
599 erase_one(iterator position) ynothrow
600 {
601 const auto next(position.p_node->next);
602
603 erase_it(position);
604 return iterator(next);
605 }
606
607 void
608 erase_range(iterator first, iterator last) ynothrow
609 {
610 // XXX: The naive implementation have good performance in general.
611 #if false
612 if(first == begin() && last == end())
613 clear();
614 else
615 #endif
616 {
617 #if false
618 size_type n(0);
619 const auto eptr(last.p_node);
620 auto cur(first.p_node);
621 const auto prev(cur->prev);
622
623 while(cur != eptr)
624 {
625 const auto nd = link_type(cur);
626
627 cur = nd->next;
628 drop_node(nd);
629 ++n;
630 }
631 objects.header.node_count -= n;
632 yunseq(prev->next = eptr, eptr->prev = prev);
633 #else
634 while(first != last)
635 first = erase_one(first);
636 #endif
637 }
638 }
639
640 void
641 pop_back() ynothrowv
642 {
643 yverify(!empty());
644 erase_it(iterator(objects.header.prev));
645 }
646
647 template<typename... _tParams>
648 iterator
649 emplace(const_iterator position, _tParams&&... args)
650 {
651 const auto nd(create_node(yforward(args)...));
652
653 attach_node(nd, position.cast_mutable().p_node);
654 return iterator(nd);
655 }
656
657 protected:
658 YB_ATTR_nodiscard typename node_ator_traits::pointer
659 allocate_node()
660 {
661 return node_ator_traits::allocate(objects, 1);
662 }
663
664 void
665 deallocate_node(typename node_ator_traits::pointer p) ynothrow
666 {
667 node_ator_traits::deallocate(objects, p, 1);
668 }
669
670 template<typename... _tParams>
671 void
672 construct_node(link_type nd, _tParams&&... args)
673 {
674 // XXX: Ensure no need to use placment new for the node.
675 static_assert(is_trivially_default_constructible<value_node>(),
676 "Invalid node type found.");
677 auto& a(get_node_allocator());
678 // NOTE: This should be same to %deallocate_node(nd) on exception
679 // thrown.
680 allocator_guard<node_allocator>
681 gd(nd, allocator_guard_delete<node_allocator>(a, 1));
682
683 node_ator_traits::construct(a, nd->access_ptr(), yforward(args)...);
684 gd.release();
685 }
686
687 template<typename... _tParams>
688 YB_ATTR_nodiscard YB_ATTR_returns_nonnull link_type
689 create_node(_tParams&&... args)
690 {
691 const auto nd(allocate_node());
692
693 construct_node(nd, yforward(args)...);
694 return nd;
695 }
696
697 void
698 destroy_node(link_type nd) ynothrow
699 {
700 // XXX: Ensure no need to use explicit destructor call for the node.
701 static_assert(is_trivially_destructible<value_node>(),
702 "Invalid node type found.");
703 node_ator_traits::destroy(get_node_allocator(), nd->access_ptr());
704 }
705
706 void
707 drop_node(link_type nd) ynothrow
708 {
709 destroy_node(nd);
710 deallocate_node(nd);
711 }
712
713 private:
714 void
715 attach_node(link_type nd, base_ptr position) ynothrow
716 {
717 nd->hook(position);
718 ++objects.header.node_count;
719 }
720
721 YB_ATTR_nodiscard link_type
722 detach_node(base_ptr cur)
723 {
724 const auto nd = link_type(cur);
725
726 --objects.header.node_count;
727 nd->unhook();
728 return nd;
729 }
730
731 public:
732 void
733 clear() ynothrow
734 {
735 clear_nodes();
736 objects.header.reset();
737 }
738
739 private:
740 void
741 clear_nodes() ynothrow
742 {
743 clear_nodes_from(objects.header.next);
744 }
745
746 void
747 clear_nodes_from(base_ptr cur) ynothrow
748 {
749 while(cur != &objects.header)
750 {
751 const auto nd = link_type(cur);
752
753 cur = nd->next;
754 drop_node(nd);
755 }
756 }
757
758 public:
759 friend void
760 swap(list_rep& x, list_rep& y) ynothrow
761 {
762 list_node_base::swap(x.objects.header, y.objects.header);
763 std::swap(x.objects.header.node_count, y.objects.header.node_count);
764 ystdex::alloc_on_swap(x.get_node_allocator(), y.get_node_allocator());
765 }
766
767 private:
768 void
769 expects_same_allocators(list_rep& x) ynothrowv
770 {
771 // NOTE: [list.ops] specifies the behavior is undefined in %splice if
772 // the allocators are not equal.
773 expects_same_allocators(x,
774 typename node_ator_traits::is_always_equal());
775 }
776 void
777 expects_same_allocators(list_rep& x, false_) ynothrowv
778 {
779 yunused(x);
780 // NOTE: [list.ops] specifies the behavior is undefined in %splice if
781 // the allocators are not equal.
782 yverify(x.get_node_allocator() == get_node_allocator());
783 }
784 void
785 expects_same_allocators(list_rep&, true_) ynothrow
786 {}
787
788 void
789 transfer_range(iterator position, iterator first, iterator last)
790 {
791 position.p_node->transfer(first.p_node, last.p_node);
792 }
793 void
794 transfer_range(iterator position, const_iterator first, const_iterator last)
795 {
796 transfer_range(position, first.cast_mutable(), last.cast_mutable());
797 }
798
799 public:
800 void
801 splice(iterator position, list_rep& x) ynothrowv
802 {
803 expects_same_allocators(x);
804 yverify(std::addressof(x) != this);
805 if(!x.empty())
806 {
807 transfer_range(position, x.begin(), x.end());
808 objects.header.node_count += x.objects.header.node_count;
809 x.objects.header.node_count = 0;
810 }
811 }
812 void
813 splice(iterator position, list_rep& x, const_iterator i) ynothrowv
814 {
815 expects_same_allocators(x);
816 // XXX: Use %YB_VerifyIterator?
817 yverify(i != x.end());
818
819 auto j(i);
820
821 ++j;
822 if(!(position == i || position == j))
823 {
824 transfer_range(position, i, j),
825 ++objects.header.node_count,
826 --x.objects.header.node_count;
827 }
828 }
829 void
830 splice(iterator position, list_rep& x, const_iterator first,
831 const_iterator last) ynothrowv
832 {
833 expects_same_allocators(x);
834 if(first != last)
835 {
836 // XXX: Use %YB_VerifyIterator?
837 yverify(first != x.end());
838
839 const auto n(size_t(std::distance(first, last)));
840
841 if(position != last)
842 transfer_range(position, first, last),
843 objects.header.node_count += n,
844 x.objects.header.node_count -= n;
845 }
846 }
847
848 private:
849 template<typename _func>
850 size_type
851 remove_for(_func f)
852 {
853 const auto old_size(size());
854 const auto last(end());
855 auto first(begin());
856
857 while(first != last)
858 {
859 auto next(first);
860
861 ++next;
862 f(first);
863 first = next;
864 }
865 return old_size - size();
866 }
867
868 public:
869 size_type
870 remove(const _type& value)
871 {
872 auto extra(end());
873 auto n_removed(remove_for([&, this](iterator i){
874 if(*i == value)
875 {
876 if(!ref_eq<>()(*i, value))
877 erase_it(i);
878 else
879 extra = i;
880 }
881 }));
882
883 if(extra != end())
884 {
885 erase_it(extra);
886 ++n_removed;
887 }
888 return n_removed;
889 }
890
891 template<typename _fPred>
892 size_type
893 remove_if(_fPred& pred)
894 {
895 node_remove op(*this);
896
897 return remove_for([&](iterator i){
898 if(pred(*i))
899 op.detach(i);
900 });
901 }
902
903 template<typename _fBiPred>
904 size_type
905 unique(_fBiPred& binary_pred)
906 {
907 node_remove op(*this);
908 const auto last(end());
909 auto first(begin());
910
911 if(first != last)
912 {
913 const auto old_size(size());
914 auto next(first);
915
916 while(++next != last)
917 {
918 if(binary_pred(*first, *next))
919 op.detach(first);
920 first = next;
921 }
922 return old_size - size();
923 }
924 return 0;
925 }
926
928 template<typename _fComp>
929 void
930 merge(list_rep& x, _fComp& comp)
931 {
932 expects_same_allocators(x);
933 if(std::addressof(x) != this)
934 {
935 auto first1(begin()), first2(x.begin()), last1(end()),
936 last2(x.end());
937 const size_t orig_size(x.size());
938
939 try
940 {
941 while(first1 != last1 && first2 != last2)
942 if(comp(*first2, *first1))
943 {
944 auto next(first2);
945
946 transfer_range(first1, first2, ++next);
947 first2 = next;
948 }
949 else
950 ++first1;
951 if(first2 != last2)
952 transfer_range(last1, first2, last2);
953 objects.header.node_count += x.objects.header.node_count;
954 x.objects.header.node_count = 0;
955 }
956 catch(...)
957 {
958 const size_t dist(std::distance(first2, last2));
959
960 objects.header.node_count += orig_size - dist;
961 x.objects.header.node_count = dist;
962 throw;
963 }
964 }
965 }
966
967 // NOTE: This is basically a stable quick sort implementation for lists,
968 // returning the suggested pivot iterator as the new first iterator of a
969 // range possibly necessary to be sorted later.
970 template<typename _fComp>
971 iterator
972 sort(iterator first, iterator last, size_type n, _fComp& comp)
973 {
974 yverify(std::distance(first, last) == n);
975 if(n > 1)
976 {
977 const auto half(n / 2);
978 auto mid(std::next(first, half));
979
980 first = sort(first, mid, half, comp);
981 mid = sort(mid, last, n - half, comp);
982
983 auto next(first);
984
985 for(bool init(true);; init = {})
986 {
987 // NOTE: [first, mid) and [mid, last) are sorted and non-empty.
988 // XXX: Use %YB_VerifyIterator?
989 yverify(mid != end());
990 yverify(first != end());
991 // NOTE: This is stable as no equivalent elements will cause
992 // the reordering implemented as the splice operation.
993 if(comp(*mid, *first))
994 {
995 // NOTE: Note %mid will be spliced before %first. As the
996 // result of %transfer_range, the range needing to be
997 // sorted (and guaranteed sorted after this call) is
998 // expanded. This only requires the update at the first
999 // iteration, since all other operations do not expand the
1000 // range any more.
1001 if(init)
1002 next = mid;
1003 {
1004 auto new_mid(mid);
1005 auto j(mid);
1006
1007 ++j;
1008 if(!(first == mid || first == j))
1009 transfer_range(first, mid, j),
1010 mid = new_mid;
1011 }
1012 if(mid == last)
1013 return next;
1014 }
1015 else
1016 {
1017 ++first;
1018 if(first == mid)
1019 return next;
1020 }
1021 }
1022 }
1023 return first;
1024 }
1025
1026 void
1027 reverse() ynothrow
1028 {
1029 objects.header.reverse_nodes();
1030 }
1031 };
1032
1033 } // namespace details;
1034
1049 template<typename _type, class _tAlloc = std::allocator<_type>>
1050 class list : private totally_ordered<list<_type, _tAlloc>>
1051 {
1052 public:
1053 using value_type = _type;
1060 static_assert(and_<is_object<_type>, is_unqualified<_type>>(),
1061 "The value type for allocator shall be an unqualified object type.");
1062 static_assert(is_allocator_for<_tAlloc, value_type>(),
1063 "Value type mismatched to the allocator found.");
1064 using allocator_type = _tAlloc;
1065
1066 private:
1067 using ator_traits = allocator_traits<allocator_type>;
1068 using rep_type = details::list_rep<_type, _tAlloc>;
1069
1070 public:
1071 using pointer = typename ator_traits::pointer;
1072 using const_pointer = typename ator_traits::const_pointer;
1073 using reference = value_type&;
1074 using const_reference = const value_type&;
1076 using size_type = typename rep_type::size_type;
1078 using difference_type = typename rep_type::difference_type;
1080
1081 using iterator = typename rep_type::iterator;
1082 using const_iterator = typename rep_type::const_iterator;
1084 using reverse_iterator = ystdex::reverse_iterator<iterator>;
1085 using const_reverse_iterator = ystdex::reverse_iterator<const_iterator>;
1086
1087 private:
1088 rep_type rep;
1089
1090 public:
1091 list() yimpl(= default);
1092 explicit
1093 list(const allocator_type& a) ynothrow
1094 : rep(a)
1095 {}
1096 explicit
1097 list(size_type n, const allocator_type& a = allocator_type())
1098 : rep(a)
1099 {
1100 for(; n != 0; --n)
1101 emplace_back();
1102 }
1103 list(size_type n, const value_type& value,
1104 const allocator_type& a = allocator_type())
1105 : rep(a)
1106 {
1107 init_fill(n, value);
1108 }
1109 // NOTE: The resolution has been implemented in libstdc++ since r184911,
1110 // see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=43813.
1116 template<typename _tIn,
1117 yimpl(typename = enable_for_input_iterator_t<_tIn>)>
1118 list(_tIn first, _tIn last, const allocator_type& a = allocator_type())
1119 : rep(a)
1120 {
1121 init_range(first, last);
1122 }
1123 list(std::initializer_list<value_type> il,
1124 const allocator_type& a = allocator_type())
1125 : rep(a)
1126 {
1127 init_range(il.begin(), il.end());
1128 }
1129 list(const list&) yimpl(= default);
1130 list(const list& x, const allocator_type& a)
1131 : rep(a)
1132 {
1133 init_range(x.begin(), x.end());
1134 }
1135 // XXX: The exception specification is strengthened to 'noexcept'.
1136 // In ISO C++17 there is no explicit exception specification.
1137 list(list&&) yimpl(= default);
1138 // XXX: The exception specification is strengthened to noexcept
1139 // specification having the operand equivalent to the conjunction of
1140 // %std::allocator_traits::is_always_equal trait of the internal node. In
1141 // ISO C++17 there is no explicit exception specification.
1142 list(list&& x, const allocator_type& a)
1143 yimpl(ynoexcept(is_nothrow_constructible<
1144 rep_type, rep_type&&, const allocator_type&>()))
1145 : rep(std::move(x.rep), a)
1146 {}
1147
1148 public:
1149 ~list() yimpl(= default);
1150
1151 list&
1152 operator=(const list&) yimpl(= default);
1153 // XXX: The exception specification is changed. ISO C++17 only requires
1154 // conditional non-throwing exception specification when the allocator
1155 // meets %std::allocator_traits<allocator_type>::is_always_equal, with
1156 // regardless to %propagate_on_container_move_assignment of the node
1157 // allocator. Here the %allocator_traits of the internal node is also used
1158 // instead. See https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91541 and LWG
1159 // 3267.
1160 list&
1161 operator=(list&&) yimpl(= default);
1162 list&
1163 operator=(std::initializer_list<value_type> il)
1164 {
1165 assign(il);
1166 return *this;
1167 }
1168
1169 private:
1170 void
1171 init_fill(size_type n, const value_type& x)
1172 {
1173 for(; n != 0; --n)
1174 push_back(x);
1175 }
1176
1182 template<typename _tIn>
1183 void
1184 init_range(_tIn first, _tIn last)
1185 {
1186 rep.init_range(first, last);
1187 }
1188
1189 void
1190 assign_fill(size_type n, const value_type& val)
1191 {
1192 iterator i = begin();
1193 for(; i != end() && n > 0; ++i, --n)
1194 *i = val;
1195 if(n > 0)
1196 insert(end(), n, val);
1197 else
1198 erase(i, end());
1199 }
1200
1201 public:
1202 void
1203 assign(size_type n, const value_type& val)
1204 {
1205 assign_fill(n, val);
1206 }
1212 template<typename _tIn, yimpl(typename = enable_for_input_iterator_t<_tIn>)>
1213 void
1214 assign(_tIn first, _tIn last)
1215 {
1216 rep.assign_range(first, last);
1217 }
1218 void
1219 assign(std::initializer_list<value_type> il)
1220 {
1221 rep.assign_range(il.begin(), il.end());
1222 }
1223
1224 YB_ATTR_nodiscard YB_PURE allocator_type
1225 get_allocator() const ynothrow
1226 {
1227 return rep.get_allocator();
1228 }
1229
1230 YB_ATTR_nodiscard YB_PURE iterator
1231 begin() ynothrow
1232 {
1233 return rep.begin();
1234 }
1235 YB_ATTR_nodiscard YB_PURE const_iterator
1236 begin() const ynothrow
1237 {
1238 return rep.begin();
1239 }
1240
1241 YB_ATTR_nodiscard YB_PURE iterator
1242 end() ynothrow
1243 {
1244 return rep.end();
1245 }
1246 YB_ATTR_nodiscard YB_PURE const_iterator
1247 end() const ynothrow
1248 {
1249 return rep.end();
1250 }
1251
1252 YB_ATTR_nodiscard YB_PURE reverse_iterator
1253 rbegin() ynothrow
1254 {
1255 return reverse_iterator(end());
1256 }
1257 YB_ATTR_nodiscard YB_PURE const_reverse_iterator
1258 rbegin() const ynothrow
1259 {
1260 return const_reverse_iterator(end());
1261 }
1262
1263 YB_ATTR_nodiscard YB_PURE reverse_iterator
1264 rend() ynothrow
1265 {
1266 return reverse_iterator(begin());
1267 }
1268 YB_ATTR_nodiscard YB_PURE const_reverse_iterator
1269 rend() const ynothrow
1270 {
1271 return const_reverse_iterator(begin());
1272 }
1273
1274 YB_ATTR_nodiscard YB_PURE const_iterator
1275 cbegin() const ynothrow
1276 {
1277 return begin();
1278 }
1279
1280 YB_ATTR_nodiscard YB_PURE const_iterator
1281 cend() const ynothrow
1282 {
1283 return end();
1284 }
1285
1286 YB_ATTR_nodiscard YB_PURE const_reverse_iterator
1287 crbegin() const ynothrow
1288 {
1289 return const_reverse_iterator(end());
1290 }
1291
1292 YB_ATTR_nodiscard YB_PURE const_reverse_iterator
1293 crend() const ynothrow
1294 {
1295 return const_reverse_iterator(begin());
1296 }
1297
1298 YB_ATTR_nodiscard YB_PURE bool
1299 empty() const ynothrow
1300 {
1301 return rep.empty();
1302 }
1303
1304 YB_ATTR_nodiscard YB_PURE size_type
1305 size() const ynothrow
1306 {
1307 return rep.size();
1308 }
1309
1310 YB_ATTR_nodiscard YB_PURE size_type
1311 max_size() const ynothrow
1312 {
1313 return rep.max_size();
1314 }
1315
1316 void
1317 resize(size_type sz)
1318 {
1319 const auto i(rep.resize_pos(sz));
1320
1321 if(sz != 0)
1322 rep.append_default(sz);
1323 else
1324 erase(i, end());
1325 }
1326 void
1327 resize(size_type sz, const value_type& x)
1328 {
1329 const auto i(rep.resize_pos(sz));
1330
1331 if(sz != 0)
1332 insert(end(), sz, x);
1333 else
1334 erase(i, end());
1335 }
1336
1337 YB_ATTR_nodiscard YB_PURE reference
1338 front() ynothrow
1339 {
1340 return *begin();
1341 }
1342 YB_ATTR_nodiscard YB_PURE const_reference
1343 front() const ynothrow
1344 {
1345 return *begin();
1346 }
1347
1348 YB_ATTR_nodiscard YB_PURE reference
1349 back() ynothrow
1350 {
1351 auto i(end());
1352
1353 --i;
1354 return *i;
1355 }
1356 YB_ATTR_nodiscard YB_PURE const_reference
1357 back() const ynothrow
1358 {
1359 auto i(cend());
1360
1361 --i;
1362 return *i;
1363 }
1364
1366 template<typename... _tParams>
1367 reference
1368 emplace_front(_tParams&&... args)
1369 {
1370 rep.insert_it(begin(), yforward(args)...);
1371 return front();
1372 }
1373
1375 template<typename... _tParams>
1376 reference
1377 emplace_back(_tParams&&... args)
1378 {
1379 rep.insert_it(end(), yforward(args)...);
1380 return back();
1381 }
1382
1383 void
1384 push_front(const value_type& x)
1385 {
1386 rep.insert_it(begin(), x);
1387 }
1388 void
1389 push_front(value_type&& x)
1390 {
1391 rep.insert_it(begin(), std::move(x));
1392 }
1393
1394 void
1395 pop_front() yimpl(ynothrowv)
1396 {
1397 yverify(!empty());
1398 rep.erase_it(begin());
1399 }
1400
1401 void
1402 push_back(const value_type& x)
1403 {
1404 rep.insert_it(end(), x);
1405 }
1406 void
1407 push_back(value_type&& x)
1408 {
1409 rep.insert_it(end(), std::move(x));
1410 }
1411
1412 void
1413 pop_back() yimpl(ynothrowv)
1414 {
1415 rep.pop_back();
1416 }
1417
1418 template<typename... _tParams>
1419 iterator
1420 emplace(const_iterator position, _tParams&&... args)
1421 {
1422 return rep.emplace(position, yforward(args)...);
1423 }
1424
1425 iterator
1426 insert(const_iterator position, const value_type& x)
1427 {
1428 return rep.emplace(position, x);
1429 }
1430 iterator
1431 insert(const_iterator position, value_type&& x)
1432 {
1433 return rep.emplace(position, std::move(x));
1434 }
1435 iterator
1436 insert(const_iterator p, std::initializer_list<value_type> il)
1437 {
1438 return insert(p, il.begin(), il.end());
1439 }
1440 iterator
1441 insert(const_iterator position, size_type n, const value_type& x)
1442 {
1443 if(n != 0)
1444 {
1445 list tmp(n, x, get_allocator());
1446 auto i(tmp.begin());
1447
1448 splice(position, tmp);
1449 return i;
1450 }
1451 return position.cast_mutable();
1452 }
1458 template<typename _tIn,
1459 yimpl(typename = enable_for_input_iterator_t<_tIn>)>
1460 iterator
1461 insert(const_iterator position, _tIn first, _tIn last)
1462 {
1463 return rep.insert_range(position, first, last);
1464 }
1465
1466 iterator
1467 erase(const_iterator position) yimpl(ynothrow)
1468 {
1469 return rep.erase_one(position.cast_mutable());
1470 }
1471 iterator
1472 erase(const_iterator first, const_iterator last) yimpl(ynothrow)
1473 {
1474 auto res(last.cast_mutable());
1475
1476 rep.erase_range(first.cast_mutable(), res);
1477 return res;
1478 }
1479
1480 // XXX: The exception specification is strengthened. ISO C++17 only requires
1481 // conditional non-throwing exception specification when the allocator
1482 // meets %std::allocator_traits<allocator_type>::is_always_equal.
1483 void
1484 swap(list& x) ynothrow
1485 {
1486 ystdex::swap_dependent(rep, x.rep);
1487 }
1488 friend void
1489 swap(list<_type, _tAlloc>& x, list<_type, _tAlloc>& y)
1490 ynoexcept_spec(x.swap(y))
1491 {
1492 x.swap(y);
1493 }
1494
1495 void
1496 clear() ynothrow
1497 {
1498 rep.clear();
1499 }
1500
1501 void
1502 splice(const_iterator position, list& x) yimpl(ynothrowv)
1503 {
1504 rep.splice(position.cast_mutable(), x.rep);
1505 }
1506 void
1507 splice(const_iterator position, list&& x) yimpl(ynothrowv)
1508 {
1509 splice(position, x);
1510 }
1511 void
1512 splice(const_iterator position, list& x, const_iterator i) yimpl(ynothrowv)
1513 {
1514 rep.splice(position.cast_mutable(), x.rep, i);
1515 }
1516 void
1517 splice(const_iterator position, list&& x, const_iterator i) yimpl(ynothrowv)
1518 {
1519 splice(position, x, i);
1520 }
1521 void
1522 splice(const_iterator position, list& x, const_iterator first,
1523 const_iterator last) yimpl(ynothrowv)
1524 {
1525 rep.splice(position.cast_mutable(), x.rep, first, last);
1526 }
1527 void
1528 splice(const_iterator position, list&& x, const_iterator first,
1529 const_iterator last) yimpl(ynothrowv)
1530 {
1531 splice(position, x, first, last);
1532 }
1533
1535
1536 size_type
1537 remove(const _type& value)
1538 {
1539 return rep.remove(value);
1540 }
1541
1542 template<typename _fPred>
1543 size_type
1544 remove_if(_fPred pred)
1545 {
1546 return rep.remove_if(pred);
1547 }
1548
1549 size_type
1550 unique()
1551 {
1552 return unique(equal_to<>());
1553 }
1554 template<typename _fBiPred>
1555 size_type
1556 unique(_fBiPred binary_pred)
1557 {
1558 return rep.unique(binary_pred);
1559 }
1561
1562 void
1563 merge(list& x)
1564 {
1565 merge(std::move(x), less<>());
1566 }
1567 void
1568 merge(list&& x)
1569 {
1570 merge(x);
1571 }
1573 template<typename _fComp>
1574 void
1575 merge(list& x, _fComp comp)
1576 {
1577 rep.merge(x.rep, comp);
1578 }
1579 template<typename _fComp>
1580 void
1581 merge(list&& x, _fComp comp)
1582 {
1583 merge(x, comp);
1584 }
1585
1586 void
1587 sort()
1588 {
1589 sort(less<>());
1590 }
1591 template<typename _fComp>
1592 void
1593 sort(_fComp comp)
1594 {
1595 rep.sort(begin(), end(), size(), comp);
1596 }
1597
1598 void
1599 reverse() ynothrow
1600 {
1601 rep.reverse();
1602 }
1603
1604 YB_ATTR_nodiscard YB_PURE friend bool
1605 operator==(const list& x, const list& y)
1606 {
1607 return x.size() == y.size()
1608 && std::equal(x.cbegin(), x.cend(), y.cbegin());
1609 }
1610
1611 YB_ATTR_nodiscard YB_PURE friend bool
1612 operator<(const list& x, const list& y)
1613 {
1614 return std::lexicographical_compare(x.cbegin(), x.cend(), y.cbegin(),
1615 y.cend());
1616 }
1617 };
1618
1619 } // namespace ystdex;
1620
1621 #endif
1622
ystdex::details::list_rep::merge
void merge(list_rep &x, _fComp &comp)
Definition: list.hpp:930
ystdex::list::rbegin
const_reverse_iterator rbegin() const
Definition: list.hpp:1258
ystdex::details::list_rep::assign_range
void assign_range(_tIn first, _tIn last)
Definition: list.hpp:401
ystdex::details::list_rep::components::components
components(components &&x, node_allocator a)
Definition: list.hpp:285
ystdex::details::list_rep::clear_nodes_from
void clear_nodes_from(base_ptr cur)
Definition: list.hpp:747
ystdex::details::list_rep::remove_if
size_type remove_if(_fPred &pred)
Definition: list.hpp:893
ystdex::details::list_const_iterator::value_type
_type value_type
Definition: list.hpp:170
ystdex::list::sort
void sort(_fComp comp)
Definition: list.hpp:1593
YB_ATTR_nodiscard
#define YB_ATTR_nodiscard
标记返回值不被忽略的属性。
Definition: ydef.h:715
iterator_trait.hpp
迭代器特征。
ystdex::list::insert
iterator insert(const_iterator position, value_type &&x)
Definition: list.hpp:1431
ystdex::details::list_iterator::p_node
base_ptr p_node
Definition: list.hpp:116
ystdex::details::list_const_iterator::iterator_category
std::bidirectional_iterator_tag iterator_category
Definition: list.hpp:169
ystdex::list::erase
iterator erase(const_iterator position)
Definition: list.hpp:1467
ystdex::list::push_back
void push_back(value_type &&x)
Definition: list.hpp:1407
ystdex::details::list_rep::init_range
void init_range(_tIn first, _tIn last)
Definition: list.hpp:393
ystdex::list::splice
void splice(const_iterator position, list &&x)
Definition: list.hpp:1507
ystdex::details::list_rep::detach_node
link_type detach_node(base_ptr cur)
Definition: list.hpp:722
ystdex::list::emplace_front
reference emplace_front(_tParams &&... args)
Definition: list.hpp:1368
x
const EncapsulationBase & x
Definition: NPLA1Forms.cpp:1536
ystdex::list::splice
void splice(const_iterator position, list &&x, const_iterator first, const_iterator last)
Definition: list.hpp:1528
ystdex::cpp2017::swap
void swap(optional< _type > &x, optional< _type > &y)
Definition: optional.h:888
ystdex::list::push_front
void push_front(value_type &&x)
Definition: list.hpp:1389
ystdex::list< chunk_pr_t, polymorphic_allocator< chunk_pr_t > >::const_iterator
typename rep_type::const_iterator const_iterator
Definition: list.hpp:1082
ystdex::details::list_node_base::transfer
void transfer(base_ptr, base_ptr)
Definition: node_base.cpp:77
ystdex::alloc_on_swap
void alloc_on_swap(_tAlloc &x, _tAlloc &y)
按分配器特征在传播容器时交换分配器。
Definition: allocator.hpp:1050
ystdex::list::~list
~list()=default
ystdex::details::list_const_iterator::operator--
list_const_iterator & operator--()
Definition: list.hpp:213
ystdex::list::empty
bool empty() const
Definition: list.hpp:1299
ystdex::details::list_node::storage
standard_layout_storage< aligned_storage_t< sizeof(_type), std::alignment_of< _type >::value > > storage
Definition: list.hpp:71
ystdex::list::list
list(std::initializer_list< value_type > il, const allocator_type &a=allocator_type())
Definition: list.hpp:1123
ystdex::details::list_rep::attach_node
void attach_node(link_type nd, base_ptr position)
Definition: list.hpp:715
ystdex::details::list_iterator::list_iterator
list_iterator()=default
ystdex::list::cbegin
const_iterator cbegin() const
Definition: list.hpp:1275
ystdex::details::list_iterator::cast_mutable
list_iterator cast_mutable() const
Definition: list.hpp:126
ystdex::details::list_rep::get_allocator
allocator_type get_allocator() const
Definition: list.hpp:416
base.h
基类实用设施。
YB_PURE
#define YB_PURE
指示函数或函数模板实例为纯函数。
Definition: ydef.h:919
ystdex::details::list_rep::clear_nodes
void clear_nodes()
Definition: list.hpp:741
ystdex::details::list_rep::move_nodes
void move_nodes(list_rep &&x)
Definition: list.hpp:539
ystdex::list::crbegin
const_reverse_iterator crbegin() const
Definition: list.hpp:1287
ystdex::list::resize
void resize(size_type sz, const value_type &x)
Definition: list.hpp:1327
ystdex::list::merge
void merge(list &x, _fComp comp)
Definition: list.hpp:1575
ystdex::details::list_rep::components::components
components()
Definition: list.hpp:271
ystdex::list::splice
void splice(const_iterator position, list &x)
Definition: list.hpp:1502
ystdex::details::list_rep::swap
friend void swap(list_rep &x, list_rep &y)
Definition: list.hpp:760
yalignof
#define yalignof(_type)
指定特定类型的对齐。
Definition: ydef.h:1053
ystdex::list< chunk_pr_t, polymorphic_allocator< chunk_pr_t > >::const_pointer
typename ator_traits::const_pointer const_pointer
Definition: list.hpp:1072
ystdex::details::list_rep::splice
void splice(iterator position, list_rep &x)
Definition: list.hpp:801
ystdex::list::list
list(const list &x, const allocator_type &a)
Definition: list.hpp:1130
ystdex::list::merge
void merge(list &&x)
Definition: list.hpp:1568
ystdex::list::front
const_reference front() const
Definition: list.hpp:1343
ystdex::cpp2017::allocator_traits
Definition: allocator.hpp:384
ystdex::details::list_rep::end
const_iterator end() const
Definition: list.hpp:449
ystdex::details::list_rep::max_size
size_type max_size() const
Definition: list.hpp:474
ystdex::cpp2017::reverse_iterator
Definition: range.hpp:116
ystdex::list::list
list(const list &)=default
ystdex::details::list_node::access_ptr
const _type * access_ptr() const
Definition: list.hpp:82
ystdex::details::list_const_iterator::iterator
list_iterator< _type > iterator
Definition: list.hpp:179
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::list_rep::node_remove::head
base_ptr head
Definition: list.hpp:294
ystdex::details::list_rep::end
iterator end()
Definition: list.hpp:444
ystdex::list::rep
rep_type rep
Definition: list.hpp:1088
ystdex::details::list_iterator::value_type
_type value_type
Definition: list.hpp:108
ystdex::any_ops::advance
@ advance
Definition: any_iterator.hpp:81
ystdex::details::list_iterator::operator==
bool operator==(const list_iterator &x) const
Definition: list.hpp:152
ystdex::details::list_rep::remove_for
size_type remove_for(_func f)
Definition: list.hpp:851
ystdex::list::splice
void splice(const_iterator position, list &x, const_iterator first, const_iterator last)
Definition: list.hpp:1522
ystdex::details::list_iterator::pointer
_type * pointer
Definition: list.hpp:109
ystdex::details::list_const_iterator::operator==
bool operator==(const iterator &x) const
Definition: list.hpp:225
platform::size_t
YB_ATTR_nodiscard YF_API size_t
Definition: FileIO.h:1345
ystdex::details::list_rep::node_remove::~node_remove
~node_remove()
Definition: list.hpp:301
ystdex::cpp2014::aligned_storage_t
typename aligned_storage< _vLen, _vAlign >::type aligned_storage_t
Definition: meta.hpp:187
ystdex::details::list_node_base::base_ptr
list_node_base * base_ptr
Definition: node_base.h:48
ystdex::details::list_node_base::prev
base_ptr prev
Definition: node_base.h:53
ystdex::details::list_rep::begin
const_iterator begin() const
Definition: list.hpp:438
ystdex::make_move_if_noexcept_iterator
_tRet make_move_if_noexcept_iterator(_tIter it)
按 std::move_if_noexcept 的条件构造转移迭代器或非转移迭代器。
Definition: iterator_op.hpp:128
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::list::list
list(list &&)=default
ystdex::details::list_rep::components::header
list_header header
Definition: list.hpp:269
ystdex::cpp2014::equal_to<>
ystdex::cpp2014::less<>
ystdex::list::assign
void assign(size_type n, const value_type &val)
Definition: list.hpp:1203
next
tidy_ptr< slink > next
Definition: memory_resource.cpp:223
ystdex::details::list_rep::list_rep
list_rep(list_rep &&x, node_allocator a, true_)
Definition: list.hpp:343
ynoexcept_spec
#define ynoexcept_spec(...)
表达式 noexcept 异常规范。
Definition: ydef.h:1181
ystdex::list::pop_front
void pop_front()
Definition: list.hpp:1395
ystdex::any_ops::distance
@ distance
Definition: any_iterator.hpp:82
ystdex::details::list_const_iterator::pointer
const _type * pointer
Definition: list.hpp:172
ystdex::list::back
const_reference back() const
Definition: list.hpp:1357
ystdex::details::list_rep::reverse
void reverse()
Definition: list.hpp:1027
ystdex::details::list_rep::node_remove::node_remove
node_remove(list_rep &l)
Definition: list.hpp:298
ystdex::details::list_rep< _type, std::allocator< _type > >::node_allocator
rebind_alloc_t< std::allocator< _type >, list_node< _type > > node_allocator
Definition: list.hpp:260
ystdex::details::list_rep::insert_it
void insert_it(iterator position, _tParams &&... args)
Definition: list.hpp:569
ystdex::details::list_node_base::next
base_ptr next
Definition: node_base.h:52
ystdex::details::list_rep::splice
void splice(iterator position, list_rep &x, const_iterator first, const_iterator last)
Definition: list.hpp:830
ystdex::details::list_rep::erase_one
iterator erase_one(iterator position)
Definition: list.hpp:599
ystdex::list::crend
const_reverse_iterator crend() const
Definition: list.hpp:1293
ystdex::details::list_rep::allocate_node
node_ator_traits::pointer allocate_node()
Definition: list.hpp:659
ystdex::list::reverse
void reverse()
Definition: list.hpp:1599
ystdex::list::splice
void splice(const_iterator position, list &x, const_iterator i)
Definition: list.hpp:1512
CHRLib::f
f(d, s)
yconstfn_relaxed
#define yconstfn_relaxed
指定编译时没有 C++11 限制和隐式成员 const 的常量函数。
Definition: ydef.h:1097
ystdex::list::swap
void swap(list &x)
Definition: list.hpp:1484
NPL::A1::Internals::cur
_fCurrent && cur
Definition: NPLA1Internals.h:591
ystdex::details::list_rep::erase_it
void erase_it(iterator position)
Definition: list.hpp:593
ystdex::swap_dependent
void swap_dependent(_type &x, _type &y)(is_nothrow_swappable< _type >())
支持基于 ystdex_swap::swap 的 ADL 的左值交换。
Definition: swap.hpp:371
ystdex::details::list_rep::transfer_range
void transfer_range(iterator position, const_iterator first, const_iterator last)
Definition: list.hpp:794
ystdex::details::list_rep::empty
bool empty() const
Definition: list.hpp:455
ystdex::details::list_rep::get_node_allocator
const node_allocator & get_node_allocator() const
Definition: list.hpp:427
ystdex::details::list_rep::resize_pos
const_iterator resize_pos(size_type &sz) const
Definition: list.hpp:480
ystdex::details::list_rep::get_node_allocator
node_allocator & get_node_allocator()
Definition: list.hpp:422
ystdex::details::list_rep
列表表示类型模板。
Definition: list.hpp:240
allocator.hpp
分配器接口。
ystdex::list::insert
iterator insert(const_iterator position, size_type n, const value_type &x)
Definition: list.hpp:1441
ystdex::list< chunk_pr_t, polymorphic_allocator< chunk_pr_t > >::pointer
typename ator_traits::pointer pointer
Definition: list.hpp:1071
ystdex::list::operator==
friend bool operator==(const list &x, const list &y)
Definition: list.hpp:1605
ystdex::details::list_const_iterator::list_const_iterator
list_const_iterator()=default
ystdex::details::list_rep::remove
size_type remove(const _type &value)
Definition: list.hpp:870
ystdex::details::list_rep::const_iterator
list_const_iterator< _type > const_iterator
Definition: list.hpp:246
ystdex::details::list_header
Definition: node_base.h:84
ystdex::details::list_rep::components::components
components(components &&)=default
ystdex::list::max_size
size_type max_size() const
Definition: list.hpp:1311
CHRLib::args
YB_ATTR_nodiscard _tParams && args
Definition: CharacterProcessing.h:649
ystdex::details::list_rep::list_rep
list_rep(list_rep &&)=default
ystdex::list::push_front
void push_front(const value_type &x)
Definition: list.hpp:1384
ystdex::details::list_const_iterator::operator++
list_const_iterator & operator++()
Definition: list.hpp:206
ystdex::standard_layout_storage
任意标准布局类型对象提供空间的存储。
Definition: type_pun.hpp:308
ystdex::details::list_rep< _type, std::allocator< _type > >::difference_type
ptrdiff_t difference_type
Definition: list.hpp:243
ystdex::details::list_rep::create_node
link_type create_node(_tParams &&... args)
Definition: list.hpp:689
ystdex::allocator_guard_delete
释放分配器分配的存储资源的删除器。
Definition: allocator.hpp:767
yverify
#define yverify(_expr)
验证：执行语义。
Definition: cassert.h:144
ystdex::list::assign
void assign(_tIn first, _tIn last)
Definition: list.hpp:1214
ystdex::bases::nonmovable
不可转移对象：禁止继承此类的对象调用默认原型的转移构造函数和转移赋值操作符。
Definition: base.h:90
ystdex::list::erase
iterator erase(const_iterator first, const_iterator last)
Definition: list.hpp:1472
ystdex::details::list_const_iterator::list_const_iterator
list_const_iterator(const iterator &x)
Definition: list.hpp:189
YB_ATTR_returns_nonnull
#define YB_ATTR_returns_nonnull
指示返回非空属性。
Definition: ydef.h:761
ystdex::details::list_node
Definition: list.hpp:68
ystdex::details::list_iterator::iterator_category
std::bidirectional_iterator_tag iterator_category
Definition: list.hpp:107
ystdex::details::list_const_iterator::operator*
reference operator*() const
Definition: list.hpp:200
ystdex::details::list_node::access_ptr
_type * access_ptr()
Definition: list.hpp:76
ystdex::list< chunk_pr_t, polymorphic_allocator< chunk_pr_t > >::allocator_type
polymorphic_allocator< chunk_pr_t > allocator_type
Definition: list.hpp:1064
ystdex::details::list_rep::node_remove
Definition: list.hpp:292
ystdex::details::ebases
Definition: operators.hpp:108
ystdex::details::list_iterator::operator++
list_iterator & operator++()
Definition: list.hpp:138
ystdex::details::list_rep::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: list.hpp:263
ystdex::or_
逻辑或。
Definition: integral_constant.hpp:172
yforward
#define yforward(_expr)
根据参数类型使用 std::forward 转发对应参数。
Definition: ydef.h:1508
ystdex::details::list_rep::emplace
iterator emplace(const_iterator position, _tParams &&... args)
Definition: list.hpp:649
ystdex::details::list_rep< _type, std::allocator< _type > >::size_type
size_t size_type
Definition: list.hpp:242
ystdex::list::emplace_back
reference emplace_back(_tParams &&... args)
Definition: list.hpp:1377
ystdex::details::list_rep::components::components
components(node_allocator a)
Definition: list.hpp:276
node_base.h
作为节点序列容器实现的节点基础。
ystdex::list::clear
void clear()
Definition: list.hpp:1496
ystdex::details::list_rep::append_default
void append_default(size_type n)
Definition: list.hpp:509
ystdex::list::operator<
friend bool operator<(const list &x, const list &y)
Definition: list.hpp:1612
ystdex::list::remove_if
size_type remove_if(_fPred pred)
Definition: list.hpp:1544
ystdex::details::list_rep::move_assign_elements
void move_assign_elements(list_rep &x, false_)
转移赋值可能不相等的不在转移赋值时传播的分配器的容器元素。
Definition: list.hpp:549
ystdex::list::list
list(_tIn first, _tIn last, const allocator_type &a=allocator_type())
Definition: list.hpp:1118
ystdex::list::assign_fill
void assign_fill(size_type n, const value_type &val)
Definition: list.hpp:1190
ystdex::details::list_rep::size
size_type size() const
Definition: list.hpp:464
ystdex::details::list_node_base::reverse_nodes
void reverse_nodes()
Definition: node_base.cpp:101
ystdex::details::list_iterator::reference
_type & reference
Definition: list.hpp:110
ystdex::details::list_header::move_nodes
void move_nodes(list_header &&)
Definition: node_base.cpp:145
ystdex::details::list_iterator
Definition: list.hpp:98
ystdex::details::list_rep::node_remove::list
list_rep & list
Definition: list.hpp:293
std
Definition: optional.h:982
ystdex::details::list_rep::drop_node
void drop_node(link_type nd)
Definition: list.hpp:707
ystdex::details::list_rep::list_rep
list_rep(const allocator_type &a)
Definition: list.hpp:326
ystdex::details::list_rep::erase_range
void erase_range(iterator first, iterator last)
Definition: list.hpp:608
ystdex::list< chunk_pr_t, polymorphic_allocator< chunk_pr_t > >::value_type
chunk_pr_t value_type
Definition: list.hpp:1053
YSLib::i
return i
Definition: YCoreUtilities.h:177
ystdex::details::list_const_iterator::operator==
bool operator==(const list_const_iterator &x) const
Definition: list.hpp:220
ystdex::details::list_rep::move_assign_elements
void move_assign_elements(list_rep &x, true_)
转移赋值相等或在转移赋值时传播的分配器的容器元素。
Definition: list.hpp:559
ystdex::list::insert
iterator insert(const_iterator position, _tIn first, _tIn last)
Definition: list.hpp:1461
yunseq
#define yunseq
无序列依赖表达式组求值。
Definition: ydef.h:1535
ystdex::list::insert
iterator insert(const_iterator p, std::initializer_list< value_type > il)
Definition: list.hpp:1436
ystdex::list::pop_back
void pop_back()
Definition: list.hpp:1413
ystdex::dep_ops::totally_ordered
details::flat_ops< _type, _type2, _tOpt, less_than_comparable, equality_comparable > totally_ordered
Definition: operators.hpp:389
ystdex::details::list_rep< _type, std::allocator< _type > >::allocator_type
std::allocator< _type > allocator_type
Definition: list.hpp:244
ystdex::details::list_iterator::operator*
reference operator*() const
Definition: list.hpp:132
ystdex::details::list_rep::expects_same_allocators
void expects_same_allocators(list_rep &x)
Definition: list.hpp:769
ystdex::details::list_rep::node_remove::p_tail
base_ptr * p_tail
Definition: list.hpp:295
ystdex::rebind_alloc_t
typename allocator_traits< _tAlloc >::template rebind_alloc< _type > rebind_alloc_t
Definition: allocator.hpp:423
ystdex::enable_for_input_iterator_t
enable_if_t< details::input_iterator_reqirement_t< _tParam >::value, _type > enable_for_input_iterator_t
选择输入迭代器类型的特定重载避免和其它类型冲突。
Definition: iterator_trait.hpp:107
ystdex::list::begin
iterator begin()
Definition: list.hpp:1231
ystdex::details::list_rep::node_remove::detach
void detach(iterator position)
Definition: list.hpp:308
ystdex::details::list_node_base::hook
void hook(base_ptr)
Definition: node_base.cpp:114
ystdex::list< chunk_pr_t, polymorphic_allocator< chunk_pr_t > >::const_reference
const value_type & const_reference
Definition: list.hpp:1074
YSLib::UI::y
SPos SPos y
Definition: YWidget.cpp:44
ystdex::ref_eq
引用等价关系仿函数。
Definition: functor.hpp:450
ystdex::list::const_reverse_iterator
ystdex::reverse_iterator< const_iterator > const_reverse_iterator
Definition: list.hpp:1085
ystdex::details::list_rep::splice
void splice(iterator position, list_rep &x, const_iterator i)
Definition: list.hpp:813
ystdex::details::list_rep::construct_node
void construct_node(link_type nd, _tParams &&... args)
Definition: list.hpp:672
ystdex::true_
bool_< true > true_
Definition: integral_constant.hpp:109
ystdex::details::list_rep::components::components
components(const components &x)
Definition: list.hpp:279
ystdex::list::rbegin
reverse_iterator rbegin()
Definition: list.hpp:1253
ystdex::details::list_iterator::operator--
list_iterator & operator--()
Definition: list.hpp:145
ystdex::list< chunk_pr_t, polymorphic_allocator< chunk_pr_t > >::difference_type
typename rep_type::difference_type difference_type
Definition: list.hpp:1078
ystdex::list::assign
void assign(std::initializer_list< value_type > il)
Definition: list.hpp:1219
ystdex::details::list_const_iterator::p_node
base_ptr p_node
Definition: list.hpp:181
ystdex::list::rend
reverse_iterator rend()
Definition: list.hpp:1264
ystdex::list::swap
friend void swap(list< _type, _tAlloc > &x, list< _type, _tAlloc > &y)
Definition: list.hpp:1489
ystdex::list::init_fill
void init_fill(size_type n, const value_type &x)
Definition: list.hpp:1171
ystdex::list::list
list(size_type n, const allocator_type &a=allocator_type())
Definition: list.hpp:1097
ystdex::details::list_node_base::const_base_ptr
const list_node_base * const_base_ptr
Definition: node_base.h:49
ystdex::list::emplace
iterator emplace(const_iterator position, _tParams &&... args)
Definition: list.hpp:1420
ystdex::details::list_header::node_count
size_t node_count
Definition: node_base.h:86
ystdex::details::list_const_iterator::cast_mutable
iterator cast_mutable() const
Definition: list.hpp:194
ystdex::details::list_rep::list_rep
list_rep()=default
ystdex::list::end
const_iterator end() const
Definition: list.hpp:1247
ystdex::list::begin
const_iterator begin() const
Definition: list.hpp:1236
ystdex::list::list
list(size_type n, const value_type &value, const allocator_type &a=allocator_type())
Definition: list.hpp:1103
ystdex::details::list_rep::sort
iterator sort(iterator first, iterator last, size_type n, _fComp &comp)
Definition: list.hpp:972
ynothrowv
#define ynothrowv
YSLib 无异常抛出保证验证：有条件地使用无异常抛出规范。
Definition: ydef.h:1219
ystdex
<memory> 特性测试宏。
Definition: ydef.h:1262
ystdex::alloc_on_move
void alloc_on_move(_tAlloc &x, _tAlloc &y)
按分配器特征在传播容器时转移分配器。
Definition: allocator.hpp:1038
ystdex::details::list_rep::insert_range
iterator insert_range(iterator position, _tIn first, _tIn last)
Definition: list.hpp:576
ystdex::list::unique
size_type unique(_fBiPred binary_pred)
Definition: list.hpp:1556
ystdex::details::list_header::reset
void reset()
Definition: node_base.h:100
ystdex::is_allocator_for
判断类型是指定值类型的分配器。
Definition: allocator.hpp:607
YSLib::_tParams
YB_ATTR_nodiscard YB_PURE typename _tParams
Definition: ValueNode.h:1294
ystdex::list::init_range
void init_range(_tIn first, _tIn last)
Definition: list.hpp:1184
ystdex::list::sort
void sort()
Definition: list.hpp:1587
ystdex::details::list_rep::transfer_range
void transfer_range(iterator position, iterator first, iterator last)
Definition: list.hpp:789
ystdex::list::insert
iterator insert(const_iterator position, const value_type &x)
Definition: list.hpp:1426
ystdex::standard_layout_storage::access
void * access()
Definition: type_pun.hpp:335
ystdex::details::list_node_base
Definition: node_base.h:47
ystdex::list::back
reference back()
Definition: list.hpp:1349
ystdex::list::end
iterator end()
Definition: list.hpp:1242
ystdex::details::list_rep::begin
iterator begin()
Definition: list.hpp:433
ystdex::addressof
enable_if_t< has_no_overloaded_addressof< _type >::value, _type * > addressof(_type &r)
尝试对非重载 operator& 提供 constexpr 的 std::addressof 替代。
Definition: addressof.hpp:131
ystdex::details::list_rep::expects_same_allocators
void expects_same_allocators(list_rep &x, false_)
Definition: list.hpp:777
ystdex::list::size
size_type size() const
Definition: list.hpp:1305
ystdex::cpp2014::equal
bool equal(_tIn1 first1, _tIn1 last1, _tIn2 first2, _tIn2 last2, _fBiPred binary_pred)
Definition: algorithm.hpp:205
ystdex::list::merge
void merge(list &x)
Definition: list.hpp:1563
ystdex::details::list_rep::deallocate_node
void deallocate_node(typename node_ator_traits::pointer p)
Definition: list.hpp:665
ystdex::details::list_rep::~list_rep
~list_rep()
Definition: list.hpp:359
ystdex::any_ops::destroy
@ destroy
销毁被管理的对象。
Definition: any.h:292
ystdex::details::list_iterator::difference_type
ptrdiff_t difference_type
Definition: list.hpp:111
ystdex::details::list_const_iterator::difference_type
ptrdiff_t difference_type
Definition: list.hpp:175
ystdex::list::list
list()=default
ystdex::details::list_rep::objects
components objects
Definition: list.hpp:322
ystdex::details::list_rep::list_rep
list_rep(list_rep &&x, const allocator_type &a)
Definition: list.hpp:335
ystdex::details::list_rep::pop_back
void pop_back()
Definition: list.hpp:641
platform::p
return p p
Definition: YCLib/FileSystem.h:209
ystdex::details::list_rep::operator=
list_rep & operator=(list_rep &&x)
Definition: list.hpp:385
ystdex::alloc_on_copy
void alloc_on_copy(_tAlloc &x, const _tAlloc &y)
按分配器特征在传播容器时复制赋值分配器。
Definition: allocator.hpp:1017
ystdex::list::rend
const_reverse_iterator rend() const
Definition: list.hpp:1269
ystdex::is_unqualified
判断指定类型是否为无限定的指定类型。
Definition: meta.hpp:681
ystdex::list< chunk_pr_t, polymorphic_allocator< chunk_pr_t > >::size_type
typename rep_type::size_type size_type
Definition: list.hpp:1076
const
const Decapsulate const Decapsulate &y ynothrow ContextNode &ctx const
Definition: NPLA1Forms.cpp:1629
yimpl
#define yimpl(...)
实现标签。
Definition: ydef.h:413
ystdex::details::list_const_iterator::reference
const _type & reference
Definition: list.hpp:174
ystdex::false_
bool_< false > false_
Definition: integral_constant.hpp:110
ystdex::list::unique
size_type unique()
Definition: list.hpp:1550
ynothrow
#define ynothrow
YSLib 无异常抛出保证：若支持 noexcept 关键字， 指定特定的 noexcept 异常规范。
Definition: ydef.h:1199
ystdex::list< chunk_pr_t, polymorphic_allocator< chunk_pr_t > >::reference
value_type & reference
Definition: list.hpp:1073
ystdex::bases::noncopyable
不可复制对象：禁止派生类调用默认原型的复制构造函数和复制赋值操作符。
Definition: base.h:50
ystdex::details::list_rep::unique
size_type unique(_fBiPred &binary_pred)
Definition: list.hpp:905
ystdex::details::list_rep::link_type
value_node * link_type
Definition: list.hpp:256
ystdex::details::list_rep::expects_same_allocators
void expects_same_allocators(list_rep &, true_)
Definition: list.hpp:785
ystdex::allocator_guard
std::unique_ptr< alloc_value_t< _tAlloc >, allocator_guard_delete< _tAlloc > > allocator_guard
分配器守卫。
Definition: allocator.hpp:869
yunused
#define yunused(...)
标记未使用的表达式。
Definition: ydef.h:1458
ystdex::details::list_rep::clear
void clear()
Definition: list.hpp:733
ynoexcept
#define ynoexcept(...)
YSLib 无异常抛出保证：指定特定的异常规范。
Definition: ydef.h:1151
ystdex::list::push_back
void push_back(const value_type &x)
Definition: list.hpp:1402
ystdex::details::list_rep::iterator
list_iterator< _type > iterator
Definition: list.hpp:245
ystdex::list::front
reference front()
Definition: list.hpp:1338
ystdex::list::reverse_iterator
ystdex::reverse_iterator< iterator > reverse_iterator
Definition: list.hpp:1084
ystdex::details::list_rep::operator=
list_rep & operator=(const list_rep &x)
Definition: list.hpp:365
ystdex::list::get_allocator
allocator_type get_allocator() const
Definition: list.hpp:1225
ystdex::list::resize
void resize(size_type sz)
Definition: list.hpp:1317
ystdex::details::list_rep::destroy_node
void destroy_node(link_type nd)
Definition: list.hpp:698
ystdex::details::list_node_base::swap
static void swap(list_node_base &, list_node_base &)
Definition: node_base.cpp:38
ystdex::details::list_rep::list_rep
list_rep(const list_rep &x)
Definition: list.hpp:329
ystdex::details::list_const_iterator
Definition: list.hpp:92
ystdex::list
列表容器。
Definition: list.hpp:1051
ystdex::list::remove
size_type remove(const _type &value)
Definition: list.hpp:1537
yconstfn
#define yconstfn
指定编译时常量函数。
Definition: ydef.h:1073
ystdex::list::splice
void splice(const_iterator position, list &&x, const_iterator i)
Definition: list.hpp:1517
ystdex::list< chunk_pr_t, polymorphic_allocator< chunk_pr_t > >::iterator
typename rep_type::iterator iterator
Definition: list.hpp:1081
YSLib::a
YB_PURE const _type * a
Definition: YCoreUtilities.h:168
platform::l
return l
Definition: YCLib/FileSystem.h:402
ystdex::details::list_rep::components
Definition: list.hpp:268
ystdex::list::merge
void merge(list &&x, _fComp comp)
Definition: list.hpp:1581
ystdex::details::list_rep::list_rep
list_rep(list_rep &&x, node_allocator a, false_)
Definition: list.hpp:347
ystdex::and_
逻辑操作元函数。
Definition: integral_constant.hpp:151
ystdex::list::cend
const_iterator cend() const
Definition: list.hpp:1281