YSTest: container.hpp 源文件

YSTest PreAlpha_b800_20170810 The YSLib Test Project

- 首页
- 相关页面
- 模块
- 命名空间
- 类
- 文件

- 文件列表
- 文件成员

container.hpp
浏览该文件的文档.
1 /*
2 © 2010-2017 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_container_hpp_
29 #define YB_INC_ystdex_container_hpp_ 1
30
31 #include "iterator.hpp" // for begin, end, make_transform, size, std::distance,
32 // std::make_move_iterator, cbegin, cend, std::piecewise_construct_t,
33 // std::piecewise_construct;
34 #include "functional.hpp" // for std::declval, is_detected_convertible;
35 #include "utility.hpp" // for std::initializer_list, ystdex::as_const;
36 #include "algorithm.hpp" // for is_undereferenceable, sort_unique;
37
38 namespace ystdex
39 {
40
50 template<class _tSeqCon>
51 class container_adaptor : protected _tSeqCon
52 {
53 protected:
54 using container_type = _tSeqCon;
55
56 private:
57 using base = container_type;
58
59 public:
61
62 using value_type = typename container_type::value_type;
63 using reference = typename container_type::reference;
64 using const_reference = typename container_type::const_reference;
65 using iterator = typename container_type::iterator;
66 using const_iterator = typename container_type::const_iterator;
67 using difference_type = typename container_type::difference_type;
68 using size_type = typename container_type::size_type;
69
70 container_adaptor() = default;
71 explicit
72 container_adaptor(size_type n)
73 : base(n)
74 {}
75 container_adaptor(size_type n, const value_type& value)
76 : base(n, value)
77 {}
78 template<class _tIn>
79 container_adaptor(_tIn first, _tIn last)
80 : base(std::move(first), std::move(last))
81 {}
82 container_adaptor(const container_adaptor&) = default;
83 #if YB_IMPL_MSCPP
84 container_adaptor(container_adaptor&& con)
86 : base(static_cast<base&&>(con))
87 {}
88 #else
89 container_adaptor(container_adaptor&&) = default;
90 #endif
91
92 container_adaptor(std::initializer_list<value_type> il)
93 : base(il)
94 {}
95
97
98 container_adaptor&
99 operator=(const container_adaptor&) = default;
100 container_adaptor&
101 #if YB_IMPL_MSCPP
102 operator=(container_adaptor&& con)
104 {
105 static_cast< base&>(*this) = static_cast< base&&>(con);
106 return *this;
107 }
108 #else
109 operator=(container_adaptor&&) = default;
110 #endif
111
112 container_adaptor&
113 operator=(std::initializer_list<value_type> il)
114 {
115 base::operator=(il);
116 }
117
119 friend bool
120 operator==(const container_adaptor& x, const container_adaptor& y)
121 {
122 return static_cast<const container_type&>(x)
123 == static_cast<const container_type&>(y);
124 }
125
127
128 using container_type::begin;
129
130 using container_type::end;
131
132 using container_type::cbegin;
133
134 using container_type::cend;
135
137 container_type&
138 get_container() ynothrow
139 {
140 return *this;
141 }
142
144 const container_type&
145 get_container() const ynothrow
146 {
147 return *this;
148 }
149
150 void
151 swap(container_adaptor& con) ynothrow
152 {
153 return base::swap(static_cast<container_type&>(con));
154 }
155
156 using base::size;
157
158 using base::max_size;
159
160 using base::empty;
162 };
163
169 template<class _tSeqCon>
170 inline bool
171 operator!=(const container_adaptor<_tSeqCon>& x,
172 const container_adaptor<_tSeqCon>& y)
173 {
174 return !(x == y);
175 }
176
177 template<class _tSeqCon>
178 void
179 swap(container_adaptor<_tSeqCon>& x,
180 container_adaptor<_tSeqCon>& y) ynothrow
181 {
182 x.swap(y);
183 }
185
186
196 template<class _tSeqCon>
197 class sequence_container_adaptor : protected container_adaptor<_tSeqCon>
198 {
199 private:
200 using base = container_adaptor<_tSeqCon>;
201
202 public:
203 using container_type = typename base::container_type;
204 using value_type = typename container_type::value_type;
205 using size_type = typename container_type::size_type;
206
208
209 sequence_container_adaptor() = default;
210 explicit
211 sequence_container_adaptor(size_type n)
212 : base(n)
213 {}
214 sequence_container_adaptor(size_type n, const value_type& value)
215 : base(n, value)
216 {}
217 template<class _tIn>
218 sequence_container_adaptor(_tIn first, _tIn last)
219 : base(std::move(first), std::move(last))
220 {}
221 sequence_container_adaptor(const sequence_container_adaptor&) = default;
222 #if YB_IMPL_MSCPP
223 sequence_container_adaptor(sequence_container_adaptor&& con)
225 : base(static_cast<base&&>(con))
226 {}
227 #else
228 sequence_container_adaptor(sequence_container_adaptor&&) = default;
229 #endif
230 sequence_container_adaptor(std::initializer_list<value_type> il)
231 : base(il)
232 {}
233
234 sequence_container_adaptor&
235 operator=(const sequence_container_adaptor&) = default;
236 sequence_container_adaptor&
237 #if YB_IMPL_MSCPP
238 operator=(sequence_container_adaptor&& con)
240 {
241 static_cast< base&>(*this) = static_cast< base&&>(con);
242 return *this;
243 }
244 #else
245 operator=(sequence_container_adaptor&&) = default;
246 #endif
247 sequence_container_adaptor&
248 operator=(std::initializer_list<value_type> il)
249 {
250 base::operator=(il);
251 }
252
254 friend bool
255 operator==(const sequence_container_adaptor& x,
256 const sequence_container_adaptor& y)
257 {
258 return static_cast<const container_type&>(x)
259 == static_cast<const container_type&>(y);
260 }
261
262 // using container_type::emplace;
263
264 using container_type::insert;
265
266 using container_type::erase;
267
268 using container_type::clear;
269
270 using container_type::assign;
272
274 using base::get_container;
275 };
276
282 template<class _tSeqCon>
283 inline bool
284 operator!=(const sequence_container_adaptor<_tSeqCon>& x,
285 const sequence_container_adaptor<_tSeqCon>& y)
286 {
287 return !(x == y);
288 }
289
290 template<class _tSeqCon>
291 void
292 swap(sequence_container_adaptor<_tSeqCon>& x,
293 sequence_container_adaptor<_tSeqCon>& y) ynothrow
294 {
295 x.swap(y);
296 }
298
299
306 template<class _tCon, typename _tIter>
307 inline _tCon
308 make_container(_tIter first, _tIter last)
309 {
310 return _tCon(first, last);
311 }
313
314 template<class _tCon, typename _tRange>
315 inline _tCon
316 make_container(_tRange&& c)
317 {
318 return _tCon(begin(yforward(c)), end(yforward(c)));
319 }
320 template<class _tCon, typename _tRange, typename _func>
321 inline _tCon
322 make_container(_tRange&& c, _func f)
323 {
324 return _tCon(ystdex::make_transform(begin(c), f),
325 ystdex::make_transform(end(c), f));
326 }
328 template<class _tCon, typename _tElem>
329 inline _tCon
330 make_container(std::initializer_list<_tElem> il)
331 {
332 return _tCon(il.begin(), il.end());
333 }
335
336
338 namespace details
339 {
340
342 template<class _type>
343 using range_size_t = decltype(size(std::declval<_type>()));
344
346 template<class _type>
347 using has_range_size = is_detected_convertible<size_t, range_size_t, _type>;
348
350 template<typename _tRange>
351 yconstfn auto
352 range_size(const _tRange& c, true_) -> decltype(size(c))
353 {
354 return size(c);
355 }
357 template<typename _tRange>
358 inline auto
359 range_size(const _tRange& c, false_)
360 -> decltype(std::distance(begin(c), end(c)))
361 {
362 return std::distance(begin(c), end(c));
363 }
364
365 } // namespace details;
366
384 template<typename _tRange>
385 yconstfn auto
386 range_size(const _tRange& c)
387 -> decltype(details::range_size(c, details::has_range_size<_tRange>()))
388 {
389 return details::range_size(c, details::has_range_size<_tRange>());
390 }
391 #if __cplusplus <= 201402L
392
396 template<typename _tElem>
397 yconstfn size_t
398 range_size(std::initializer_list<_tElem> il)
399 {
400 return size(il);
401 }
402 #endif
403
404
405
411 template<class _tCon, typename... _tParams>
412 inline void
413 assign(_tCon& con, _tParams&&... args)
414 {
415 con.assign(yforward(args)...);
416 }
417 template<class _tCon, typename _type, size_t _vN>
418 inline void
419 assign(_tCon& con, const _type(&arr)[_vN])
420 {
421 con.assign(arr, arr + _vN);
422 }
424
425
434 template<class _tCon, typename _tIn>
435 void
436 concat(_tCon& con, _tIn first, _tIn last)
437 {
438 con.insert(end(con), std::make_move_iterator(first),
439 std::make_move_iterator(last));
440 }
441 template<class _tCon, typename _tRange>
442 void
443 concat(_tCon& con, _tRange&& c)
444 {
445 con.insert(end(con), begin(yforward(c)), end(yforward(c)));
446 }
448
449
462 template<typename _tCon, typename _tIn>
463 typename _tCon::const_iterator
464 insert_reversed(_tCon& con, typename _tCon::const_iterator i, _tIn first,
465 _tIn last)
466 {
467 for(; first != last; ++first)
468 {
469 yconstraint(!is_undereferenceable(first));
470 i = con.insert(i, *first);
471 }
472 return i;
473 }
475
476
482 template<typename _tCon>
483 class container_inserter
484 {
485 public:
486 using container_type = _tCon;
487
488 protected:
489 _tCon* container;
490
491 public:
492 container_inserter(_tCon& con)
493 : container(&con)
494 {}
495
496 template<typename... _tParams>
497 auto
498 operator()(_tParams&&... args)
499 -> decltype(container->insert(yforward(args)...))
500 {
501 yassume(container);
502 return container->insert(yforward(args)...);
503 }
504 };
505
510 template<typename _tCon, typename... _tParams>
511 inline void
512 seq_insert(_tCon& con, _tParams&&... args)
513 {
514 ystdex::seq_apply(container_inserter<_tCon>(con), yforward(args)...);
515 }
516
517
519 namespace details
520 {
521
522 template<class _tCon, typename _tKey>
523 bool
524 exists(const _tCon& con, const _tKey& key,
525 decltype(std::declval<_tCon>().count()) = 1U)
526 {
527 return con.count(key) != 0;
528 }
529 template<class _tCon, typename _tKey>
530 bool
531 exists(const _tCon& con, const _tKey& key, ...)
532 {
533 return con.find(key) != end(con);
534 }
535
536
538
539 template<class _type, typename... _tParams>
540 using mem_remove_t
541 = decltype(std::declval<_type>().remove(std::declval<_tParams>()...));
542
543 template<typename _type, typename... _tParams>
544 using has_mem_remove = is_detected<mem_remove_t, _type, _tParams...>;
545
546 template<class _type, typename... _tParams>
547 using mem_remove_if_t
548 = decltype(std::declval<_type>().remove_if(std::declval<_tParams>()...));
549
550 template<typename _type, typename... _tParams>
551 using has_mem_remove_if = is_detected<mem_remove_if_t, _type, _tParams...>;
552
553 template<class _type>
554 using key_type_t = typename _type::key_type;
555
556 template<typename _type>
557 using has_mem_key_type = is_detected<key_type_t, _type>;
558
559
560 template<typename _tSeqCon, typename _type>
561 inline void
562 erase_remove(_tSeqCon& con, decltype(begin(con)) first,
563 decltype(end(con)) last, const _type& value)
564 {
565 con.erase(std::remove(first, last, value), last);
566 }
567
568 template<typename _tSeqCon, typename _fPred>
569 inline void
570 erase_remove_if(_tSeqCon& con, decltype(begin(con)) first,
571 decltype(end(con)) last, _fPred pred)
572 {
573 con.erase(std::remove_if(first, last, pred), last);
574 }
576
578
579 template<typename _tSeqCon, typename _type>
580 inline void
581 erase_all_in_seq(_tSeqCon& con, _type&& value, true_)
582 {
583 con.remove(yforward(value));
584 }
585 template<typename _tSeqCon, typename _type>
586 inline void
587 erase_all_in_seq(_tSeqCon& con, const _type& value, false_)
588 {
589 details::erase_remove(con, begin(con), end(con), value);
590 }
591
592 template<typename _tSeqCon, typename _fPred>
593 inline void
594 erase_all_if_in_seq(_tSeqCon& con, _fPred pred, true_)
595 {
596 con.remove_if(pred);
597 }
598 template<typename _tSeqCon, typename _fPred>
599 inline void
600 erase_all_if_in_seq(_tSeqCon& con, _fPred pred, false_)
601 {
602 details::erase_remove_if(con, begin(con), end(con), pred);
603 }
604
605 template<typename _tCon, typename _type>
606 void
607 erase_all(_tCon& con, decltype(cbegin(con)) first, decltype(cend(con)) last,
608 const _type& value, true_)
609 {
610 while(first != last)
611 if(*first == value)
612 con.erase(first++);
613 else
614 ++first;
615 }
616 template<typename _tCon, typename _type>
617 inline void
618 erase_all(_tCon& con, const _type& value, true_)
619 {
620 details::erase_all(con, cbegin(con), cend(con), value, true_());
621 }
622 template<typename _tCon, typename _type>
623 inline void
624 erase_all(_tCon& con, decltype(begin(con)) first, decltype(end(con)) last,
625 const _type& value, false_)
626 {
627 details::erase_remove(con, first, last, value);
628 }
629 template<typename _tCon, typename _type>
630 inline void
631 erase_all(_tCon& con, const _type& value, false_)
632 {
633 details::erase_all_in_seq(con, value, has_mem_remove<_tCon>());
634 }
635
636 template<typename _tCon, typename _fPred>
637 void
638 erase_all_if(_tCon& con, decltype(cbegin(con)) first, decltype(cend(con)) last,
639 _fPred pred, true_)
640 {
641 while(first != last)
642 if(pred(*first))
643 con.erase(first++);
644 else
645 ++first;
646 }
647 template<typename _tCon, typename _fPred>
648 inline void
649 erase_all_if(_tCon& con, _fPred pred, true_)
650 {
651 details::erase_all_if(con, cbegin(con), cend(con), pred, true_());
652 }
653 template<typename _tCon, typename _fPred>
654 inline void
655 erase_all_if(_tCon& con, decltype(begin(con)) first, decltype(end(con)) last,
656 _fPred pred, false_)
657 {
658 details::erase_remove_if(con, first, last, pred);
659 }
660 template<typename _tCon, typename _fPred>
661 inline void
662 erase_all_if(_tCon& con, _fPred pred, false_)
663 {
664 details::erase_all_if_in_seq(con, pred, has_mem_remove_if<_tCon>());
665 }
667
668 } // namespace details;
669
671
672
679 template<class _tCon, typename _tKey>
680 inline bool
681 exists(const _tCon& con, const _tKey& key)
682 {
683 return details::exists(con, key);
684 }
685
686
698 template<typename _tCon, typename _tIter>
699 inline void
700 erase_all(_tCon& con, _tIter first, _tIter last)
701 {
702 con.erase(first, last);
703 }
704 template<typename _tCon, typename _tIter, typename _type>
705 inline void
706 erase_all(_tCon& con, _tIter first, _tIter last, const _type& value)
707 {
708 details::erase_all(con, first, last, value,
709 details::has_mem_key_type<_tCon>());
710 }
711 template<typename _tCon, typename _type>
712 inline void
713 erase_all(_tCon& con, const _type& value)
714 {
715 details::erase_all(con, value, details::has_mem_key_type<_tCon>());
716 }
718
725 template<typename _tCon, typename _tIter, typename _fPred>
726 inline void
727 erase_all_if(_tCon& con, _tIter first, _tIter last, _fPred pred)
728 {
729 details::erase_all_if(con, first, last, pred,
730 details::has_mem_key_type<_tCon>());
731 }
732 template<typename _tCon, typename _fPred>
733 inline void
734 erase_all_if(_tCon& con, _fPred pred)
735 {
736 details::erase_all_if(con, pred, details::has_mem_key_type<_tCon>());
737 }
739
740
742
743
747 template<class _tAssocCon, typename _tKey>
748 bool
749 erase_first(_tAssocCon& con, const _tKey& k)
750 {
751 const auto i(con.find(k));
752
753 if(i != end(con))
754 {
755 con.erase(i);
756 return true;
757 }
758 return {};
759 }
760
766 template<class _tAssocCon>
767 inline typename _tAssocCon::size_type
768 erase_multi(_tAssocCon& con, const typename _tAssocCon::key_type& k)
769 {
770 return con.erase(k);
771 }
772 template<class _tAssocCon, typename _tKey>
773 typename _tAssocCon::size_type
774 erase_multi(_tAssocCon& con, const _tKey& k)
775 {
776 const auto pr(con.equal_range(k));
777
778 if(pr.first != pr.second)
779 {
780 const auto n(std::distance(pr.first, pr.second));
781
782 con.erase(pr.first, pr.second);
783 return n;
784 }
785 return 0;
786 }
788
789
797 template<typename _tCon>
798 typename _tCon::const_iterator
799 erase_n(_tCon& con, typename _tCon::const_iterator i,
800 typename _tCon::difference_type n)
801 {
802 yassume(n <= std::distance(i, cend(con)));
803 return con.erase(i, std::next(i, n));
804 }
806 template<typename _tCon>
807 typename _tCon::iterator
808 erase_n(_tCon& con, typename _tCon::iterator i,
809 typename _tCon::difference_type n)
810 {
811 yassume(n <= std::distance(i, end(con)));
812 return con.erase(i, std::next(i, n));
813 }
815
816
822 template<class _tCon>
823 inline typename _tCon::iterator
824 cast_mutable(_tCon& con, typename _tCon::const_iterator i)
825 {
826 return con.erase(i, i);
827 }
828 template<class _tCon, typename _type>
829 inline std::pair<typename _tCon::iterator, _type>
830 cast_mutable(_tCon& con,
831 const std::pair<typename _tCon::const_iterator, _type>& pr)
832 {
833 return {ystdex::cast_mutable(con, pr.first), pr.second};
834 }
836
837
843 template<class _tCon>
844 inline void
845 sort_unique(_tCon& con)
846 {
847 con.erase(ystdex::sort_unique(begin(con), end(con)), end(con));
848 }
849
850
856 template<class _tCon>
857 _tCon&&
858 trail(_tCon&& con, const typename decay_t<_tCon>::value_type& value = {})
859 {
860 if(!con.empty() && !(con.back() == value))
861 con.push_back(value);
862 return static_cast<_tCon&&>(con);
863 }
864 template<class _tCon, typename... _tParams>
865 _tCon&&
866 trail(_tCon&& con, _tParams&&... args)
867 {
868 if(!con.empty())
869 {
870 typename decay_t<_tCon>::value_type val(yforward(args)...);
871
872 if(!(con.back() == val))
873 con.emplace_back(std::move(val));
874 }
875 return static_cast<_tCon&&>(con);
876 }
878
879
884 template<class _tCon>
885 bool
886 pop_back_val(_tCon& con, const typename _tCon::value_type& value)
887 {
888 if(!con.empty() && con.back() == value)
889 {
890 con.pop_back();
891 return true;
892 }
893 return {};
894 }
895
900 template<class _tCon>
901 bool
902 pop_front_val(_tCon& con, const typename _tCon::value_type& value)
903 {
904 if(!con.empty() && con.front() == value)
905 {
906 con.pop_front();
907 return true;
908 }
909 return {};
910 }
911
912
919 template<class _tVector, typename _tIn>
920 void
921 vector_concat(_tVector& vec, _tIn first, _tIn last)
922 {
923 vec.reserve(size(vec) + std::distance(first, last));
924 ystdex::concat(vec, first, last);
925 }
926 template<class _tVector, typename _tRange>
927 void
928 vector_concat(_tVector& vec, _tRange&& c)
929 {
930 vec.reserve(size(vec) + ystdex::range_size(c));
931 ystdex::concat(vec, yforward(c));
932 }
934
935
943 template<class _tVector, typename _func>
944 _tVector
945 retry_for_vector(typename _tVector::size_type s, _func f)
946 {
947 yconstraint(s != 0);
948
949 _tVector res;
950
951 for(res.resize(s); f(res, s) && s < res.max_size() yimpl(/ 2); )
952 res.resize(s *= yimpl(2));
953 return res;
954 }
955
956
957
965 template<class _tAssocCon, typename _tKey, typename _func>
966 auto
967 replace_value(_tAssocCon& con, const _tKey& k, _func f)
968 -> decltype(con.emplace_hint(con.erase(con.find(k)), f(*con.find(k))))
969 {
970 auto i(con.find(k));
971
972 return i != end(con) ? con.emplace_hint(con.erase(i), f(*i)) : i;
973 }
974
975
981 template<class _tAssocCon, typename _tKey, typename... _tParams>
982 using is_piecewise_mapped = is_constructible<typename _tAssocCon::value_type,
983 std::piecewise_construct_t, std::tuple<_tKey&&>, std::tuple<_tParams&&...>>;
984
985
987 namespace details
988 {
989
991 template<class _tAssocCon>
992 struct assoc_con_traits
993 {
995
996 template<typename _tKey, typename... _tParams>
997 static inline typename _tAssocCon::iterator
998 emplace_hint_in_place(false_, _tAssocCon& con,
999 typename _tAssocCon::const_iterator hint, _tKey&&, _tParams&&... args)
1000 {
1001 return con.emplace_hint(hint, yforward(args)...);
1002 }
1003 template<typename _tKey, typename... _tParams>
1004 static inline typename _tAssocCon::iterator
1005 emplace_hint_in_place(true_, _tAssocCon& con,
1006 typename _tAssocCon::const_iterator hint, _tKey&& k, _tParams&&... args)
1007 {
1008 return con.emplace_hint(hint, std::piecewise_construct,
1009 std::forward_as_tuple(yforward(k)),
1010 std::forward_as_tuple(yforward(args)...));
1011 }
1012
1013 static inline const typename _tAssocCon::key_type&
1014 extract_key(false_, const typename _tAssocCon::value_type& val)
1015 {
1016 return val;
1017 }
1018 static inline const typename _tAssocCon::key_type&
1019 extract_key(true_, const typename _tAssocCon::value_type& val)
1020 {
1021 return val.first;
1022 }
1024
1026
1027 static inline typename _tAssocCon::value_type&
1028 extract_mapped(false_, typename _tAssocCon::value_type& val)
1029 {
1030 return val;
1031 }
1032 static inline const typename _tAssocCon::value_type&
1033 extract_mapped(false_, const typename _tAssocCon::value_type& val)
1034 {
1035 return val;
1036 }
1037 template<typename _tMap = _tAssocCon>
1038 static inline typename _tMap::mapped_type&
1039 extract_mapped(true_, typename _tAssocCon::value_type& val)
1040 {
1041 return val.second;
1042 }
1043 template<typename _tMap = _tAssocCon>
1044 static inline const typename _tMap::mapped_type&
1045 extract_mapped(true_, const typename _tAssocCon::value_type& val)
1046 {
1047 return val.second;
1048 }
1050 };
1051
1052 template<class _type>
1053 using mapped_type_t = typename _type::mapped_type;
1054
1055 } // unnamed namespace details;
1056
1061 template<class _tAssocCon, typename _tKey, typename... _tParams>
1062 inline auto
1063 emplace_hint_in_place(_tAssocCon& con, typename _tAssocCon::const_iterator hint,
1064 _tKey&& k, _tParams&&... args) -> typename _tAssocCon::iterator
1065 {
1066 return details::assoc_con_traits<_tAssocCon>::emplace_hint_in_place(
1067 is_piecewise_mapped<_tAssocCon, _tKey, _tParams...>(), con, hint,
1068 yforward(k), yforward(args)...);
1069 }
1070
1075 template<class _tAssocCon, typename _type,
1076 yimpl(typename = enable_if_convertible_t<const _type&,
1077 const typename _tAssocCon::value_type&>)>
1078 inline const typename _tAssocCon::key_type&
1079 extract_key(const _type& val)
1080 {
1081 return details::assoc_con_traits<_tAssocCon>::extract_key(
1082 is_detected<details::mapped_type_t, _tAssocCon>(), val);
1083 }
1084
1089 template<class _tAssocCon, typename _type,
1090 yimpl(typename = enable_if_convertible_t<_type&,
1091 typename _tAssocCon::value_type&>)>
1092 inline const auto
1093 extract_mapped(_type& val)
1094 -> decltype(details::assoc_con_traits<_tAssocCon>::extract_mapped(
1095 is_detected<details::mapped_type_t, _tAssocCon>(), val))
1096 {
1097 return details::assoc_con_traits<_tAssocCon>::extract_mapped(
1098 is_detected<details::mapped_type_t, _tAssocCon>(), val);
1099 }
1100
1101
1103 namespace details
1104 {
1105
1110 template<class _tAssocCon, typename _tKey, typename _tParam>
1111 std::pair<typename _tAssocCon::iterator, bool>
1112 insert_or_assign(std::pair<typename _tAssocCon::iterator, bool> pr,
1113 _tAssocCon& con, _tKey&& k, _tParam&& arg)
1114 {
1115 if(pr.second)
1116 pr.first
1117 = emplace_hint_in_place(con, pr.first, yforward(k), yforward(arg));
1118 else
1119 extract_mapped<_tAssocCon>(*pr.first) = yforward(arg);
1120 return pr;
1121 }
1122
1123 } // namespace details;
1124
1125
1137 template<class _tAssocCon, typename _tKey>
1138 std::pair<typename _tAssocCon::const_iterator, bool>
1139 search_map(const _tAssocCon& con, const _tKey& k)
1140 {
1141 const auto i(con.lower_bound(k));
1142
1143 return {i, i == end(con) || con.key_comp()(k, extract_key<_tAssocCon>(*i))};
1144 }
1145 template<class _tAssocCon, typename _tKey>
1146 inline std::pair<typename _tAssocCon::iterator, bool>
1147 search_map(_tAssocCon& con, const _tKey& k)
1148 {
1149 return
1150 ystdex::cast_mutable(con, ystdex::search_map(ystdex::as_const(con), k));
1151 }
1153
1155
1161 template<class _tAssocCon, typename _tKey>
1162 std::pair<typename _tAssocCon::const_iterator, bool>
1163 search_map(const _tAssocCon& con, typename _tAssocCon::const_iterator hint,
1164 const _tKey& k)
1165 {
1166 if(!con.empty())
1167 {
1168 const auto& comp(con.key_comp());
1169 const bool fit_before(hint == cbegin(con)
1170 || bool(comp(extract_key(*std::prev(hint)), k))),
1171 fit_after(hint == cend(con)
1172 || bool(comp(k, extract_key(*std::next(hint)))));
1173
1174 if(fit_before == fit_after)
1175 return {hint, fit_before && fit_after};
1176 return ystdex::search_map(con, k);
1177 }
1178 yconstraint(hint == cend(con));
1179 return {hint, true};
1180 }
1181 template<class _tAssocCon, typename _tKey>
1182 inline std::pair<typename _tAssocCon::iterator, bool>
1183 search_map(_tAssocCon& con, typename _tAssocCon::const_iterator hint,
1184 const _tKey& k)
1185 {
1186 return ystdex::cast_mutable(con,
1187 ystdex::search_map(ystdex::as_const(con), hint, k));
1188 }
1190
1199 template<typename _func, class _tAssocCon, typename... _tParams>
1200 std::pair<typename _tAssocCon::const_iterator, bool>
1201 search_map_by(_func f, const _tAssocCon& con, _tParams&&... args)
1202 {
1203 auto pr(ystdex::search_map(con, yforward(args)...));
1204
1205 if(pr.second)
1206 pr.first = f(pr.first);
1207 return pr;
1208 }
1209 template<typename _func, class _tAssocCon, typename... _tParams>
1210 inline std::pair<typename _tAssocCon::iterator, bool>
1211 search_map_by(_func f, _tAssocCon& con, _tParams&&... args)
1212 {
1213 return ystdex::cast_mutable(con,
1214 ystdex::search_map_by(f, ystdex::as_const(con), yforward(args)...));
1215 }
1217
1218
1219
1226
1228 template<class _tAssocCon, typename _tKey, typename... _tParams>
1229 std::pair<typename _tAssocCon::iterator, bool>
1230 try_emplace(_tAssocCon& con, _tKey&& k, _tParams&&... args)
1231 {
1232 // XXX: Blocked. 'yforward' may cause G++ 5.2 silent crash.
1233 return ystdex::search_map_by([&](typename _tAssocCon::const_iterator i){
1234 return emplace_hint_in_place(con, i, yforward(k),
1235 std::forward<_tParams>(args)...);
1236 }, con, k);
1237 }
1238
1239 template<class _tAssocCon, typename _tKey, typename... _tParams>
1240 std::pair<typename _tAssocCon::iterator, bool>
1241 try_emplace_hint(_tAssocCon& con, typename _tAssocCon::const_iterator hint,
1242 _tKey&& k, _tParams&&... args)
1243 {
1244 // XXX: Blocked. 'yforward' may cause G++ 5.2 silent crash.
1245 return ystdex::search_map_by([&](typename _tAssocCon::const_iterator i){
1246 return emplace_hint_in_place(con, i, yforward(k),
1247 std::forward<_tParams>(args)...);
1248 }, con, hint, k);
1249 }
1251
1257 template<class _tAssocCon, typename _tKey, typename _tParam>
1258 inline std::pair<typename _tAssocCon::iterator, bool>
1259 insert_or_assign(_tAssocCon& con, _tKey&& k, _tParam&& arg)
1260 {
1261 return details::insert_or_assign(ystdex::search_map(con, k), con,
1262 yforward(k), yforward(arg));
1263 }
1264
1265 template<class _tAssocCon, typename _tKey, typename _tParam>
1266 inline std::pair<typename _tAssocCon::iterator, bool>
1267 insert_or_assign_hint(_tAssocCon& con, typename _tAssocCon::const_iterator hint,
1268 _tKey&& k, _tParam&& arg)
1269 {
1270 return details::insert_or_assign(ystdex::search_map(con, hint, k), con,
1271 yforward(k), yforward(arg));
1272 }
1274
1275
1276
1277 } // namespace ystdex;
1278
1279 #endif
1280
ystdex::extract_mapped
const auto extract_mapped(_type &val) -> decltype(details::assoc_con_traits< _tAssocCon >::extract_mapped(is_detected< details::mapped_type_t, _tAssocCon >(), val))
从关联容器的值取映射的值。
Definition: container.hpp:1093
ystdex::details::assoc_con_traits::extract_key
static const _tAssocCon::key_type & extract_key(true_, const typename _tAssocCon::value_type &val)
Definition: container.hpp:1019
algorithm.hpp
泛型算法。
ystdex::sequence_container_adaptor::sequence_container_adaptor
sequence_container_adaptor(std::initializer_list< value_type > il)
Definition: container.hpp:230
ystdex::details::has_mem_remove_if
is_detected< mem_remove_if_t, _type, _tParams... > has_mem_remove_if
Definition: container.hpp:551
ystdex::container_adaptor::operator=
container_adaptor & operator=(const container_adaptor &)=default
满足容器要求。
ystdex::container_adaptor::size_type
typename container_type::size_type size_type
Definition: container.hpp:68
ystdex::container_inserter
容器插入函数对象。
Definition: container.hpp:483
ystdex::details::has_range_size
is_detected_convertible< size_t, range_size_t, _type > has_range_size
Definition: container.hpp:347
ystdex::container_adaptor::reference
typename container_type::reference reference
Definition: container.hpp:63
ystdex::details::erase_remove
void erase_remove(_tSeqCon &con, decltype(begin(con)) first, decltype(end(con)) last, const _type &value)
Definition: container.hpp:562
ystdex::container_adaptor::get_container
container_type & get_container()
Definition: container.hpp:138
ystdex::true_
bool_< true > true_
Definition: type_traits.hpp:391
ystdex::retry_for_vector
_tVector retry_for_vector(typename _tVector::size_type s, _func f)
从第一参数指定的起始缓冲区大小循环取向量结果，按需扩大缓冲区。
Definition: container.hpp:945
ystdex::assign
void assign(_tCon &con, const _type(&arr)[_vN])
Definition: container.hpp:419
ystdex::container_adaptor::difference_type
typename container_type::difference_type difference_type
Definition: container.hpp:67
yconstfn
#define yconstfn
指定编译时常量函数。
Definition: ydef.h:680
ystdex::sequence_container_adaptor::sequence_container_adaptor
sequence_container_adaptor(size_type n, const value_type &value)
Definition: container.hpp:214
iterator.hpp
通用迭代器。
ystdex::details::assoc_con_traits::emplace_hint_in_place
static _tAssocCon::iterator emplace_hint_in_place(false_, _tAssocCon &con, typename _tAssocCon::const_iterator hint, _tKey &&, _tParams &&...args)
Definition: container.hpp:998
ystdex::sequence_container_adaptor::operator==
friend bool operator==(const sequence_container_adaptor &x, const sequence_container_adaptor &y)
满足容器要求。
Definition: container.hpp:255
ystdex::container_adaptor::operator=
container_adaptor & operator=(std::initializer_list< value_type > il)
Definition: container.hpp:113
YSLib::UI::y
SPos SPos y
Definition: YWidget.cpp:44
NPL::x
const TermNode &term ynothrow const TermNode &term ynothrow const TermNode &term ynothrow TermNode &term const TermNode &term ValueNode &node const ValueNode &node const _type & x
Definition: SContext.h:94
ystdex::extract_key
const _tAssocCon::key_type & extract_key(const _type &val)
从关联容器的值取键。
Definition: container.hpp:1079
ystdex::container_adaptor::value_type
typename container_type::value_type value_type
满足容器要求。
Definition: container.hpp:62
ystdex::false_
bool_< false > false_
Definition: type_traits.hpp:392
ystdex::details::erase_all_if_in_seq
void erase_all_if_in_seq(_tSeqCon &con, _fPred pred, true_)
Definition: container.hpp:594
CHRLib::f
f(d, s)
ystdex::details::assoc_con_traits::extract_mapped
static _tAssocCon::value_type & extract_mapped(false_, typename _tAssocCon::value_type &val)
Definition: container.hpp:1028
ystdex::details::mem_remove_t
decltype(std::declval< _type >().remove(std::declval< _tParams >()...)) mem_remove_t
Definition: container.hpp:541
ystdex::container_adaptor
容器适配器。
Definition: container.hpp:51
yimpl
#define yimpl(...)
实现标签。
Definition: ydef.h:262
ystdex::container_adaptor::container_adaptor
container_adaptor(size_type n)
Definition: container.hpp:72
ystdex::details::assoc_con_traits::extract_mapped
static const _tAssocCon::value_type & extract_mapped(false_, const typename _tAssocCon::value_type &val)
Definition: container.hpp:1033
ystdex::erase_multi
_tAssocCon::size_type erase_multi(_tAssocCon &con, const typename _tAssocCon::key_type &k)
删除指定关联容器中等价于指定键的所有元素。
Definition: container.hpp:768
ystdex::cpp2014::cend
auto cend(const _tRange &c) -> decltype(std::end(c))
Definition: range.hpp:87
CHRLib::args
_tParams && args
Definition: CharacterProcessing.h:538
ystdex::details::has_mem_key_type
is_detected< key_type_t, _type > has_mem_key_type
Definition: container.hpp:557
ystdex::is_undereferenceable
bool is_undereferenceable(const _tIter &)
Definition: deref_op.hpp:45
ystdex::pop_back_val
bool pop_back_val(_tCon &con, const typename _tCon::value_type &value)
若容器末尾存在指定值的元素则移除。
Definition: container.hpp:886
ystdex::cpp2011::end
_type * end(_type(&&array)[_vN])
Definition: range.hpp:54
ystdex::sequence_container_adaptor
序列容器适配器。
Definition: container.hpp:197
ystdex::container_adaptor::container_type
_tSeqCon container_type
Definition: container.hpp:54
ystdex::replace_value
auto replace_value(_tAssocCon &con, const _tKey &k, _func f) -> decltype(con.emplace_hint(con.erase(con.find(k)), f(*con.find(k))))
替换关联容器的值。
Definition: container.hpp:967
ystdex::try_emplace
std::pair< typename _tAssocCon::iterator, bool > try_emplace(_tAssocCon &con, _tKey &&k, _tParams &&...args)
Definition: container.hpp:1230
ystdex::is_piecewise_mapped
is_constructible< typename _tAssocCon::value_type, std::piecewise_construct_t, std::tuple< _tKey && >, std::tuple< _tParams &&... >> is_piecewise_mapped
判断关联容器、键和参数类型是否可以按 map 的方式无转移地构造。
Definition: container.hpp:983
ystdex::details::erase_remove_if
void erase_remove_if(_tSeqCon &con, decltype(begin(con)) first, decltype(end(con)) last, _fPred pred)
Definition: container.hpp:570
ystdex::seq_insert
void seq_insert(_tCon &con, _tParams &&...args)
顺序插入值至指定容器。
Definition: container.hpp:512
ystdex::trail
_tCon && trail(_tCon &&con, const typename decay_t< _tCon >::value_type &value={})
保证非空容器以参数指定的元素结尾。
Definition: container.hpp:858
ystdex::container_adaptor::base
container_type base
Definition: container.hpp:57
ystdex::operator!=
bool operator!=(nullptr_t lhs, const _type &rhs)
Definition: ydef.h:908
ystdex::emplace_hint_in_place
auto emplace_hint_in_place(_tAssocCon &con, typename _tAssocCon::const_iterator hint, _tKey &&k, _tParams &&...args) -> typename _tAssocCon::iterator
带有提示的原地插入构造。
Definition: container.hpp:1063
ystdex::container_adaptor::container_adaptor
container_adaptor()=default
ystdex::swap
void swap(sequence_container_adaptor< _tSeqCon > &x, sequence_container_adaptor< _tSeqCon > &y)
Definition: container.hpp:292
ystdex::path_category::empty
ystdex::insert_or_assign_hint
std::pair< typename _tAssocCon::iterator, bool > insert_or_assign_hint(_tAssocCon &con, typename _tAssocCon::const_iterator hint, _tKey &&k, _tParam &&arg)
Definition: container.hpp:1267
ystdex::pop_front_val
bool pop_front_val(_tCon &con, const typename _tCon::value_type &value)
若容器起始存在指定值的元素则移除。
Definition: container.hpp:902
ystdex::any_ops::distance
Definition: any_iterator.hpp:82
ystdex::details::mem_remove_if_t
decltype(std::declval< _type >().remove_if(std::declval< _tParams >()...)) mem_remove_if_t
Definition: container.hpp:548
ystdex::erase_n
_tCon::const_iterator erase_n(_tCon &con, typename _tCon::const_iterator i, typename _tCon::difference_type n)
删除指定容器中指定迭代器起始指定数量的元素。
Definition: container.hpp:799
ystdex::erase_all_if
void erase_all_if(_tCon &con, _tIter first, _tIter last, _fPred pred)
删除指定容器中指定区间中的或全部满足谓词的元素。
Definition: container.hpp:727
ynothrow
#define ynothrow
YSLib 无异常抛出保证：若支持 noexcept 关键字， 指定特定的 noexcept 异常规范。
Definition: ydef.h:766
ystdex::details::erase_all_if
void erase_all_if(_tCon &con, decltype(cbegin(con)) first, decltype(cend(con)) last, _fPred pred, true_)
Definition: container.hpp:638
ystdex::container_inserter::container_inserter
container_inserter(_tCon &con)
Definition: container.hpp:492
ystdex::sequence_container_adaptor::base
container_adaptor< _tSeqCon > base
Definition: container.hpp:200
ystdex::details::exists
bool exists(const _tCon &con, const _tKey &key, decltype(std::declval< _tCon >().count())=1U)
Definition: container.hpp:524
CHRLib::s
_tDst const _tSrc * s
Definition: CharacterProcessing.h:140
ystdex::exists
bool exists(const _tCon &con, const _tKey &key)
判断指定的容器中存在指定的键。
Definition: container.hpp:681
ystdex::cpp2014::cbegin
auto cbegin(const _tRange &c) -> decltype(std::begin(c))
Definition: range.hpp:79
ystdex
特性测试宏。
Definition: ydef.h:822
YSLib::i
return i
Definition: YCoreUtilities.h:176
ystdex::container_adaptor::container_adaptor
container_adaptor(std::initializer_list< value_type > il)
Definition: container.hpp:92
ystdex::details::assoc_con_traits::extract_key
static const _tAssocCon::key_type & extract_key(false_, const typename _tAssocCon::value_type &val)
Definition: container.hpp:1014
ystdex::concat
void concat(_tCon &con, _tIn first, _tIn last)
插入元素到容器末尾。
Definition: container.hpp:436
ystdex::details::assoc_con_traits::extract_mapped
static const _tMap::mapped_type & extract_mapped(true_, const typename _tAssocCon::value_type &val)
Definition: container.hpp:1045
ystdex::details::erase_all
void erase_all(_tCon &con, decltype(cbegin(con)) first, decltype(cend(con)) last, const _type &value, true_)
Definition: container.hpp:607
ystdex::container_inserter::container_type
_tCon container_type
Definition: container.hpp:486
functional.hpp
函数和可调用对象。
ystdex::try_emplace_hint
std::pair< typename _tAssocCon::iterator, bool > try_emplace_hint(_tAssocCon &con, typename _tAssocCon::const_iterator hint, _tKey &&k, _tParams &&...args)
Definition: container.hpp:1241
ystdex::assign
void assign(_tCon &con, _tParams &&...args)
插入参数指定的元素到容器。
Definition: container.hpp:413
ystdex::details::assoc_con_traits::emplace_hint_in_place
static _tAssocCon::iterator emplace_hint_in_place(true_, _tAssocCon &con, typename _tAssocCon::const_iterator hint, _tKey &&k, _tParams &&...args)
Definition: container.hpp:1005
ystdex::search_map
std::pair< typename _tAssocCon::const_iterator, bool > search_map(const _tAssocCon &con, const _tKey &k)
按指定键搜索指定关联容器。
Definition: container.hpp:1139
ystdex::details::assoc_con_traits::extract_mapped
static _tMap::mapped_type & extract_mapped(true_, typename _tAssocCon::value_type &val)
Definition: container.hpp:1039
ystdex::details::key_type_t
typename _type::key_type key_type_t
Definition: container.hpp:554
ystdex::sequence_container_adaptor::sequence_container_adaptor
sequence_container_adaptor()=default
满足序列容器要求。
ystdex::swap
void swap(container_adaptor< _tSeqCon > &x, container_adaptor< _tSeqCon > &y)
Definition: container.hpp:179
ystdex::container_adaptor::iterator
typename container_type::iterator iterator
Definition: container.hpp:65
ystdex::container_adaptor::container_adaptor
container_adaptor(size_type n, const value_type &value)
Definition: container.hpp:75
std
Definition: memory.hpp:1183
ystdex::container_adaptor::get_container
const container_type & get_container() const
Definition: container.hpp:145
ystdex::insert_reversed
_tCon::const_iterator insert_reversed(_tCon &con, typename _tCon::const_iterator i, _tIn first, _tIn last)
逆向插入范围到容器的指定位置。
Definition: container.hpp:464
ystdex::vector_concat
void vector_concat(_tVector &vec, _tIn first, _tIn last)
插入元素到 vector 末尾。
Definition: container.hpp:921
ystdex::details::range_size
auto range_size(const _tRange &c, true_) -> decltype(size(c))
Definition: container.hpp:352
ystdex::container_adaptor::swap
void swap(container_adaptor &con)
Definition: container.hpp:151
ystdex::container_inserter::container
_tCon * container
Definition: container.hpp:489
ystdex::details::has_mem_remove
is_detected< mem_remove_t, _type, _tParams... > has_mem_remove
Definition: container.hpp:544
ystdex::is_detected_convertible
is_convertible< detected_t< _gOp, _tParams... >, _tTo > is_detected_convertible
Definition: type_traits.hpp:727
ystdex::sequence_container_adaptor::sequence_container_adaptor
sequence_container_adaptor(_tIn first, _tIn last)
Definition: container.hpp:218
ystdex::make_container
_tCon make_container(_tIter first, _tIter last)
构造指定类型的容器。
Definition: container.hpp:308
ystdex::sequence_container_adaptor::operator=
sequence_container_adaptor & operator=(const sequence_container_adaptor &)=default
utility.hpp
实用设施。
ystdex::sequence_container_adaptor::operator=
sequence_container_adaptor & operator=(std::initializer_list< value_type > il)
Definition: container.hpp:248
ystdex::details::range_size_t
decltype(size(std::declval< _type >())) range_size_t
Definition: container.hpp:343
ystdex::insert_or_assign
std::pair< typename _tAssocCon::iterator, bool > insert_or_assign(_tAssocCon &con, _tKey &&k, _tParam &&arg)
Definition: container.hpp:1259
CHRLib::c
c
Definition: CharacterProcessing.h:81
ystdex::container_adaptor::const_reference
typename container_type::const_reference const_reference
Definition: container.hpp:64
yforward
#define yforward(_expr)
根据参数类型使用 std::forward 传递对应参数。
Definition: ydef.h:995
yassume
#define yassume(_expr)
假定：环境语义。
Definition: cassert.h:105
ystdex::container_adaptor::container_adaptor
container_adaptor(_tIn first, _tIn last)
Definition: container.hpp:79
ystdex::container_adaptor::const_iterator
typename container_type::const_iterator const_iterator
Definition: container.hpp:66
ystdex::enable_if_convertible_t
enable_if_t< is_convertible< _tFrom, _tTo >::value, _type > enable_if_convertible_t
Definition: type_traits.hpp:1052
ystdex::is_detected
typename details::detector< nonesuch, void, _gOp, _tParams... >::value_t is_detected
Definition: type_traits.hpp:708
ystdex::sort_unique
_tRandom sort_unique(_tRandom first, _tRandom last)
排序指定序列范围，保留不重复元素的区间。
Definition: algorithm.hpp:512
ystdex::as_const
add_const_t< _type > & as_const(_type &t)
转换 const 引用。
Definition: utility.hpp:51
ystdex::cpp2011::begin
_type * begin(_type(&&array)[_vN])
Definition: range.hpp:46
ystdex::details::mapped_type_t
typename _type::mapped_type mapped_type_t
Definition: container.hpp:1053
ystdex::size
auto size(const _tRange &c) -> decltype(c.size())
类容器访问。
Definition: range.hpp:233
ystdex::erase_first
bool erase_first(_tAssocCon &con, const _tKey &k)
删除指定关联容器中等价于指定键的起始元素。
Definition: container.hpp:749
ystdex::container_adaptor::operator==
friend bool operator==(const container_adaptor &x, const container_adaptor &y)
满足容器要求。
Definition: container.hpp:120
ystdex::range_size
auto range_size(const _tRange &c) -> decltype(details::range_size(c, details::has_range_size< _tRange >()))
取范围大小。
Definition: container.hpp:386
yconstraint
#define yconstraint(_expr)
约束：接口语义。
Definition: cassert.h:88
ystdex::search_map_by
std::pair< typename _tAssocCon::const_iterator, bool > search_map_by(_func f, const _tAssocCon &con, _tParams &&...args)
按指定键值搜索指定映射并执行操作。
Definition: container.hpp:1201
ystdex::sequence_container_adaptor::sequence_container_adaptor
sequence_container_adaptor(size_type n)
Definition: container.hpp:211
ystdex::erase_all
void erase_all(_tCon &con, _tIter first, _tIter last)
删除指定容器中指定区间中的或全部元素。
Definition: container.hpp:700
ystdex::container_inserter::operator()
auto operator()(_tParams &&...args) -> decltype(container->insert(std::forward< decltype(args)>(args)...))
Definition: container.hpp:498
ystdex::details::assoc_con_traits
Definition: container.hpp:992
ystdex::details::erase_all_in_seq
void erase_all_in_seq(_tSeqCon &con, _type &&value, true_)
Definition: container.hpp:581
ystdex::seq_apply
void seq_apply(_func &&)
顺序递归调用。
Definition: functional.hpp:224
ystdex::cast_mutable
_tCon::iterator cast_mutable(_tCon &con, typename _tCon::const_iterator i)
移除 const_iterator 的 const 限定。
Definition: container.hpp:824
ystdex::details::insert_or_assign
std::pair< typename _tAssocCon::iterator, bool > insert_or_assign(std::pair< typename _tAssocCon::iterator, bool > pr, _tAssocCon &con, _tKey &&k, _tParam &&arg)
Definition: container.hpp:1112