YSTest: container.hpp 源文件

YSTest PreAlpha_b700_20160611 The YSLib Test Project

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

- 文件列表
- 文件成员

container.hpp
浏览该文件的文档.
1 /*
2 © 2010-2016 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
343 template<class _type>
344 using range_size_t = decltype(size(std::declval<_type>()));
345
346 template<class _type>
347 using has_range_size = is_detected_convertible<size_t, range_size_t, _type>;
349
350 template<typename _tRange>
351 yconstfn auto
352 range_size(const _tRange& c, true_type) -> decltype(size(c))
353 {
354 return size(c);
355 }
356 template<typename _tRange>
357 inline auto
358 range_size(const _tRange& c, false_type)
359 -> decltype(std::distance(begin(c), end(c)))
360 {
361 return std::distance(begin(c), end(c));
362 }
363
364 } // namespace details;
365
383 template<typename _tRange>
384 yconstfn auto
385 range_size(const _tRange& c)
386 -> decltype(details::range_size(c, details::has_range_size<_tRange>()))
387 {
388 return details::range_size(c, details::has_range_size<_tRange>());
389 }
390 #if __cplusplus <= 201402L
391
395 template<typename _tElem>
396 yconstfn size_t
397 range_size(std::initializer_list<_tElem> il)
398 {
399 return size(il);
400 }
401 #endif
402
403
404
410 template<class _tCon, typename... _tParams>
411 inline void
412 assign(_tCon& con, _tParams&&... args)
413 {
414 con.assign(yforward(args)...);
415 }
416 template<class _tCon, typename _type, size_t _vN>
417 inline void
418 assign(_tCon& con, const _type(&arr)[_vN])
419 {
420 con.assign(arr, arr + _vN);
421 }
423
424
433 template<class _tCon, typename _tIn>
434 void
435 concat(_tCon& con, _tIn first, _tIn last)
436 {
437 con.insert(end(con), std::make_move_iterator(first),
438 std::make_move_iterator(last));
439 }
440 template<class _tCon, typename _tRange>
441 void
442 concat(_tCon& con, _tRange&& c)
443 {
444 con.insert(end(con), begin(yforward(c)), end(yforward(c)));
445 }
447
448
461 template<typename _tCon, typename _tIn>
462 typename _tCon::const_iterator
463 insert_reversed(_tCon& con, typename _tCon::const_iterator i, _tIn first,
464 _tIn last)
465 {
466 for(; first != last; ++first)
467 {
468 yconstraint(!is_undereferenceable(first));
469 i = con.insert(i, *first);
470 }
471 return i;
472 }
474
475
481 template<typename _tCon>
482 class container_inserter
483 {
484 public:
485 using container_type = _tCon;
486
487 protected:
488 _tCon* container;
489
490 public:
491 container_inserter(_tCon& con)
492 : container(&con)
493 {}
494
495 template<typename... _tParams>
496 auto
497 operator()(_tParams&&... args)
498 -> decltype(container->insert(yforward(args)...))
499 {
500 yassume(container);
501 return container->insert(yforward(args)...);
502 }
503 };
504
509 template<typename _tCon, typename... _tParams>
510 inline void
511 seq_insert(_tCon& con, _tParams&&... args)
512 {
513 ystdex::seq_apply(container_inserter<_tCon>(con), yforward(args)...);
514 }
515
516
518 namespace details
519 {
520
521 template<class _tCon, typename _tKey>
522 bool
523 exists(const _tCon& con, const _tKey& key,
524 decltype(std::declval<_tCon>().count()) = 1U)
525 {
526 return con.count(key) != 0;
527 }
528 template<class _tCon, typename _tKey>
529 bool
530 exists(const _tCon& con, const _tKey& key, ...)
531 {
532 return con.find(key) != end(con);
533 }
534
535
537
538 template<class _type, typename... _tParams>
539 using mem_remove_t
540 = decltype(std::declval<_type>().remove(std::declval<_tParams>()...));
541
542 template<typename _type, typename... _tParams>
543 using has_mem_remove = is_detected<mem_remove_t, _type, _tParams...>;
544
545 template<class _type, typename... _tParams>
546 using mem_remove_if_t
547 = decltype(std::declval<_type>().remove_if(std::declval<_tParams>()...));
548
549 template<typename _type, typename... _tParams>
550 using has_mem_remove_if = is_detected<mem_remove_if_t, _type, _tParams...>;
551
552 template<class _type>
553 using key_type_t = typename _type::key_type;
554
555 template<typename _type>
556 using has_mem_key_type = is_detected<key_type_t, _type>;
557
558
559 template<typename _tSeqCon, typename _type>
560 inline void
561 erase_remove(_tSeqCon& con, decltype(begin(con)) first,
562 decltype(end(con)) last, const _type& value)
563 {
564 con.erase(std::remove(first, last, value), last);
565 }
566
567 template<typename _tSeqCon, typename _fPred>
568 inline void
569 erase_remove_if(_tSeqCon& con, decltype(begin(con)) first,
570 decltype(end(con)) last, _fPred pred)
571 {
572 con.erase(std::remove_if(first, last, pred), last);
573 }
574
575 template<typename _tSeqCon, typename _type>
576 inline void
577 erase_all_in_seq(_tSeqCon& con, _type&& value, true_type)
578 {
579 con.remove(yforward(value));
580 }
581 template<typename _tSeqCon, typename _type>
582 inline void
583 erase_all_in_seq(_tSeqCon& con, const _type& value, false_type)
584 {
585 details::erase_remove(con, begin(con), end(con), value);
586 }
587
588 template<typename _tSeqCon, typename _fPred>
589 inline void
590 erase_all_if_in_seq(_tSeqCon& con, _fPred pred, true_type)
591 {
592 con.remove_if(pred);
593 }
594 template<typename _tSeqCon, typename _fPred>
595 inline void
596 erase_all_if_in_seq(_tSeqCon& con, _fPred pred, false_type)
597 {
598 details::erase_remove_if(con, begin(con), end(con), pred);
599 }
600
601 template<typename _tCon, typename _type>
602 void
603 erase_all(_tCon& con, decltype(cbegin(con)) first, decltype(cend(con)) last,
604 const _type& value, true_type)
605 {
606 while(first != last)
607 if(*first == value)
608 con.erase(first++);
609 else
610 ++first;
611 }
612 template<typename _tCon, typename _type>
613 inline void
614 erase_all(_tCon& con, const _type& value, true_type)
615 {
616 details::erase_all(con, cbegin(con), cend(con), value, true_type());
617 }
618 template<typename _tCon, typename _type>
619 inline void
620 erase_all(_tCon& con, decltype(begin(con)) first, decltype(end(con)) last,
621 const _type& value, false_type)
622 {
623 details::erase_remove(con, first, last, value);
624 }
625 template<typename _tCon, typename _type>
626 inline void
627 erase_all(_tCon& con, const _type& value, false_type)
628 {
629 details::erase_all_in_seq(con, value, has_mem_remove<_tCon>());
630 }
631
632 template<typename _tCon, typename _fPred>
633 void
634 erase_all_if(_tCon& con, decltype(cbegin(con)) first, decltype(cend(con)) last,
635 _fPred pred, true_type)
636 {
637 while(first != last)
638 if(pred(*first))
639 con.erase(first++);
640 else
641 ++first;
642 }
643 template<typename _tCon, typename _fPred>
644 inline void
645 erase_all_if(_tCon& con, _fPred pred, true_type)
646 {
647 details::erase_all_if(con, cbegin(con), cend(con), pred, true_type());
648 }
649 template<typename _tCon, typename _fPred>
650 inline void
651 erase_all_if(_tCon& con, decltype(begin(con)) first, decltype(end(con)) last,
652 _fPred pred, false_type)
653 {
654 details::erase_remove_if(con, first, last, pred);
655 }
656 template<typename _tCon, typename _fPred>
657 inline void
658 erase_all_if(_tCon& con, _fPred pred, false_type)
659 {
660 details::erase_all_if_in_seq(con, pred, has_mem_remove_if<_tCon>());
661 }
663
664 } // namespace details;
665
667
668
675 template<class _tCon, typename _tKey>
676 inline bool
677 exists(const _tCon& con, const _tKey& key)
678 {
679 return details::exists(con, key);
680 }
681
682
694 template<typename _tCon, typename _tIter>
695 inline void
696 erase_all(_tCon& con, _tIter first, _tIter last)
697 {
698 con.erase(first, last);
699 }
700 template<typename _tCon, typename _tIter, typename _type>
701 inline void
702 erase_all(_tCon& con, _tIter first, _tIter last, const _type& value)
703 {
704 details::erase_all(con, first, last, value,
705 details::has_mem_key_type<_tCon>());
706 }
707 template<typename _tCon, typename _type>
708 inline void
709 erase_all(_tCon& con, const _type& value)
710 {
711 details::erase_all(con, value, details::has_mem_key_type<_tCon>());
712 }
714
721 template<typename _tCon, typename _tIter, typename _fPred>
722 inline void
723 erase_all_if(_tCon& con, _tIter first, _tIter last, _fPred pred)
724 {
725 details::erase_all_if(con, first, last, pred,
726 details::has_mem_key_type<_tCon>());
727 }
728 template<typename _tCon, typename _fPred>
729 inline void
730 erase_all_if(_tCon& con, _fPred pred)
731 {
732 details::erase_all_if(con, pred, details::has_mem_key_type<_tCon>());
733 }
735
736
738
739
743 template<class _tAssocCon, typename _tKey>
744 bool
745 erase_first(_tAssocCon& con, const _tKey& k)
746 {
747 const auto i(con.find(k));
748
749 if(i != end(con))
750 {
751 con.erase(i);
752 return true;
753 }
754 return {};
755 }
756
762 template<class _tAssocCon>
763 inline typename _tAssocCon::size_type
764 erase_multi(_tAssocCon& con, const typename _tAssocCon::key_type& k)
765 {
766 return con.erase(k);
767 }
768 template<class _tAssocCon, typename _tKey>
769 typename _tAssocCon::size_type
770 erase_multi(_tAssocCon& con, const _tKey& k)
771 {
772 const auto pr(con.equal_range(k));
773
774 if(pr.first != pr.second)
775 {
776 const auto n(std::distance(pr.first, pr.second));
777
778 con.erase(pr.first, pr.second);
779 return n;
780 }
781 return 0;
782 }
784
785
793 template<typename _tCon>
794 typename _tCon::const_iterator
795 erase_n(_tCon& con, typename _tCon::const_iterator i,
796 typename _tCon::difference_type n)
797 {
798 yassume(n <= std::distance(i, cend(con)));
799 return con.erase(i, std::next(i, n));
800 }
802 template<typename _tCon>
803 typename _tCon::iterator
804 erase_n(_tCon& con, typename _tCon::iterator i,
805 typename _tCon::difference_type n)
806 {
807 yassume(n <= std::distance(i, end(con)));
808 return con.erase(i, std::next(i, n));
809 }
811
812
818 template<class _tCon>
819 inline typename _tCon::iterator
820 cast_mutable(_tCon& con, typename _tCon::const_iterator i)
821 {
822 return con.erase(i, i);
823 }
824 template<class _tCon, typename _type>
825 inline std::pair<typename _tCon::iterator, _type>
826 cast_mutable(_tCon& con,
827 const std::pair<typename _tCon::const_iterator, _type>& pr)
828 {
829 return {ystdex::cast_mutable(con, pr.first), pr.second};
830 }
832
833
839 template<class _tCon>
840 inline void
841 sort_unique(_tCon& con)
842 {
843 con.erase(ystdex::sort_unique(begin(con), end(con)), end(con));
844 }
845
846
852 template<class _tCon>
853 _tCon&&
854 trail(_tCon&& con, const typename decay_t<_tCon>::value_type& value = {})
855 {
856 if(!con.empty() && !(con.back() == value))
857 con.push_back(value);
858 return static_cast<_tCon&&>(con);
859 }
860 template<class _tCon, typename... _tParams>
861 _tCon&&
862 trail(_tCon&& con, _tParams&&... args)
863 {
864 if(!con.empty())
865 {
866 typename decay_t<_tCon>::value_type val(yforward(args)...);
867
868 if(!(con.back() == val))
869 con.emplace_back(std::move(val));
870 }
871 return static_cast<_tCon&&>(con);
872 }
874
875
880 template<class _tCon>
881 bool
882 pop_back_val(_tCon& con, const typename _tCon::value_type& value)
883 {
884 if(!con.empty() && con.back() == value)
885 {
886 con.pop_back();
887 return true;
888 }
889 return {};
890 }
891
896 template<class _tCon>
897 bool
898 pop_front_val(_tCon& con, const typename _tCon::value_type& value)
899 {
900 if(!con.empty() && con.front() == value)
901 {
902 con.pop_front();
903 return true;
904 }
905 return {};
906 }
907
908
915 template<class _tVector, typename _tIn>
916 void
917 vector_concat(_tVector& vec, _tIn first, _tIn last)
918 {
919 vec.reserve(size(vec) + std::distance(first, last));
920 ystdex::concat(vec, first, last);
921 }
922 template<class _tVector, typename _tRange>
923 void
924 vector_concat(_tVector& vec, _tRange&& c)
925 {
926 vec.reserve(size(vec) + ystdex::range_size(c));
927 ystdex::concat(vec, yforward(c));
928 }
930
931
939 template<class _tVector, typename _func>
940 _tVector
941 retry_for_vector(typename _tVector::size_type s, _func f)
942 {
943 yconstraint(s != 0);
944
945 _tVector res;
946
947 for(res.resize(s); f(res, s) && s < res.max_size() yimpl(/ 2); )
948 res.resize(s *= yimpl(2));
949 return res;
950 }
951
952
953
961 template<class _tAssocCon, typename _tKey, typename _func>
962 auto
963 replace_value(_tAssocCon& con, const _tKey& k, _func f)
964 -> decltype(con.emplace_hint(con.erase(con.find(k)), f(*con.find(k))))
965 {
966 auto i(con.find(k));
967
968 return i != end(con) ? con.emplace_hint(con.erase(i), f(*i)) : i;
969 }
970
971
977 template<class _tAssocCon, typename _tKey, typename... _tParams>
978 using is_piecewise_mapped = is_constructible<typename _tAssocCon::value_type,
979 std::piecewise_construct_t, std::tuple<_tKey&&>, std::tuple<_tParams&&...>>;
980
981
987 template<class _tAssocCon, typename _tKey, typename... _tParams>
988 inline yimpl(enable_if_t)<is_piecewise_mapped<_tAssocCon, _tKey,
989 _tParams...>::value, typename _tAssocCon::iterator>
990 emplace_hint_in_place(_tAssocCon& con, typename _tAssocCon::const_iterator hint,
991 _tKey&& k, _tParams&&... args)
992 {
993 return con.emplace_hint(hint, std::piecewise_construct,
994 std::forward_as_tuple(yforward(k)),
995 std::forward_as_tuple(yforward(args)...));
996 }
997 template<class _tAssocCon, typename _tKey, typename... _tParams>
998 inline yimpl(enable_if_t)<!is_piecewise_mapped<_tAssocCon, _tKey,
999 _tParams...>::value, typename _tAssocCon::iterator>
1000 emplace_hint_in_place(_tAssocCon& con, typename _tAssocCon::const_iterator hint,
1001 _tKey&&, _tParams&&... args)
1002 {
1003 return con.emplace_hint(hint, yforward(args)...);
1004 }
1006
1008 namespace details
1009 {
1010
1011 template<class _type>
1012 using mapped_type_t = typename _type::mapped_type;
1013
1014 template<class _tAssocCon>
1015 inline const typename _tAssocCon::key_type&
1016 extract_key(const typename _tAssocCon::value_type& val, false_type)
1017 {
1018 return val;
1019 }
1020 template<class _tAssocCon>
1021 inline const typename _tAssocCon::key_type&
1022 extract_key(const typename _tAssocCon::value_type& val, true_type)
1023 {
1024 return val.first;
1025 }
1026
1027
1029 template<class _tAssocCon, typename _tKey, typename _tParam>
1030 std::pair<typename _tAssocCon::iterator, bool>
1031 insert_or_assign(std::pair<typename _tAssocCon::iterator, bool> pr,
1032 _tAssocCon& con, _tKey&& k, _tParam&& arg)
1033 {
1034 if(pr.first)
1035 pr.first
1036 = emplace_hint_in_place(con, pr.second, yforward(k), yforward(arg));
1037 else
1038 pr.second = yforward(arg);
1039 return pr;
1040 }
1041
1042 } // unnamed namespace details;
1043
1049 template<class _tAssocCon, typename _type,
1050 yimpl(typename = enable_if_convertible_t<const _type&,
1051 const typename _tAssocCon::value_type&>)>
1052 inline const typename _tAssocCon::key_type&
1053 extract_key(const _type& val)
1054 {
1055 return details::extract_key<_tAssocCon>(val,
1056 is_detected<details::mapped_type_t, _tAssocCon>());
1057 }
1058 template<class _tAssocCon, typename _tKey,
1059 yimpl(typename = enable_if_inconvertible_t<const _tKey&,
1060 const typename _tAssocCon::value_type&>)>
1061 inline const _tKey&
1062 extract_key(const _tKey& k)
1063 {
1064 return k;
1065 }
1067
1068
1080 template<class _tAssocCon, typename _tKey>
1081 std::pair<typename _tAssocCon::const_iterator, bool>
1082 search_map(const _tAssocCon& con, const _tKey& k)
1083 {
1084 const auto i(con.lower_bound(k));
1085
1086 return {i, i == end(con) || con.key_comp()(k, extract_key<_tAssocCon>(*i))};
1087 }
1088 template<class _tAssocCon, typename _tKey>
1089 inline std::pair<typename _tAssocCon::iterator, bool>
1090 search_map(_tAssocCon& con, const _tKey& k)
1091 {
1092 return ystdex::cast_mutable(con, ystdex::search_map(ystdex::as_const(con), k));
1093 }
1095
1097
1103 template<class _tAssocCon, typename _tKey>
1104 std::pair<typename _tAssocCon::const_iterator, bool>
1105 search_map(const _tAssocCon& con, typename _tAssocCon::const_iterator hint,
1106 const _tKey& k)
1107 {
1108 if(!con.empty())
1109 {
1110 const auto& comp(con.key_comp());
1111 const bool fit_before(hint == cbegin(con)
1112 || bool(comp(extract_key(*std::prev(hint)), k))),
1113 fit_after(hint == cend(con)
1114 || bool(comp(k, extract_key(*std::next(hint)))));
1115
1116 if(fit_before == fit_after)
1117 return {hint, fit_before && fit_after};
1118 return ystdex::search_map(con, k);
1119 }
1120 yconstraint(hint == cend(con));
1121 return {hint, true};
1122 }
1123 template<class _tAssocCon, typename _tKey>
1124 inline std::pair<typename _tAssocCon::iterator, bool>
1125 search_map(_tAssocCon& con, typename _tAssocCon::const_iterator hint,
1126 const _tKey& k)
1127 {
1128 return ystdex::cast_mutable(con,
1129 ystdex::search_map(ystdex::as_const(con), hint, k));
1130 }
1132
1139 template<typename _func, class _tAssocCon, typename... _tParams>
1140 std::pair<typename _tAssocCon::const_iterator, bool>
1141 search_map(_func f, const _tAssocCon& con, _tParams&&... args)
1142 {
1143 auto pr(ystdex::search_map(con, yforward(args)...));
1144
1145 if(pr.second)
1146 pr.first = f(pr.first);
1147 return pr;
1148 }
1149 template<typename _func, class _tAssocCon, typename... _tParams>
1150 inline std::pair<typename _tAssocCon::iterator, bool>
1151 search_map(_func f, _tAssocCon& con, _tParams&&... args)
1152 {
1153 return ystdex::cast_mutable(con,
1154 ystdex::search_map(f, ystdex::as_const(con), yforward(args)...));
1155 }
1157
1158
1159
1166
1168 template<class _tAssocCon, typename _tKey, typename... _tParams>
1169 std::pair<typename _tAssocCon::iterator, bool>
1170 try_emplace(_tAssocCon& con, _tKey&& k, _tParams&&... args)
1171 {
1172 // XXX: Blocked. 'yforward' may cause G++ 5.2 silent crash.
1173 return ystdex::search_map([&](typename _tAssocCon::const_iterator i){
1174 return emplace_hint_in_place(con, i, yforward(k),
1175 std::forward<_tParams>(args)...);
1176 }, con, k);
1177 }
1178
1179 template<class _tAssocCon, typename _tKey, typename... _tParams>
1180 std::pair<typename _tAssocCon::iterator, bool>
1181 try_emplace_hint(_tAssocCon& con, typename _tAssocCon::const_iterator hint,
1182 _tKey&& k, _tParams&&... args)
1183 {
1184 // XXX: Blocked. 'yforward' may cause G++ 5.2 silent crash.
1185 return ystdex::search_map([&](typename _tAssocCon::const_iterator i){
1186 return emplace_hint_in_place(con, i, yforward(k),
1187 std::forward<_tParams>(args)...);
1188 }, con, hint, k);
1189 }
1191
1193
1194 template<class _tAssocCon, typename _tKey, typename _tParam>
1195 inline std::pair<typename _tAssocCon::iterator, bool>
1196 insert_or_assign(_tAssocCon& con, _tKey&& k, _tParam&& arg)
1197 {
1198 return details::insert_or_assign(ystdex::search_map(con, k), con,
1199 yforward(k), yforward(arg));
1200 }
1201
1202 template<class _tAssocCon, typename _tKey, typename _tParam>
1203 inline std::pair<typename _tAssocCon::iterator, bool>
1204 insert_or_assign_hint(_tAssocCon& con, typename _tAssocCon::const_iterator hint,
1205 _tKey&& k, _tParam&& arg)
1206 {
1207 return details::insert_or_assign(ystdex::search_map(con, hint, k), con,
1208 yforward(k), yforward(arg));
1209 }
1211
1212
1213
1214 } // namespace ystdex;
1215
1216 #endif
1217
ystdex::cast_mutable
_tCon::iterator cast_mutable(_tCon &con, typename _tCon::const_iterator i)
移除 const_iterator 的 const 限定。
Definition: container.hpp:820
ystdex::erase_all_if
void erase_all_if(_tCon &con, _tIter first, _tIter last, _fPred pred)
删除指定容器中指定区间中的或全部满足谓词的元素。
Definition: container.hpp:723
yassume
#define yassume(_expr)
假定：环境语义。
Definition: cassert.h:99
ystdex::details::erase_all_if_in_seq
void erase_all_if_in_seq(_tSeqCon &con, _fPred pred, true_type)
Definition: container.hpp:590
YSLib::Drawing::x
The boundary is out of the const Rect SDst SPos x
Definition: YDraw.h:127
ystdex::details::erase_all
void erase_all(_tCon &con, decltype(cbegin(con)) first, decltype(cend(con)) last, const _type &value, true_type)
Definition: container.hpp:603
ynothrow
#define ynothrow
YSLib 无异常抛出保证：若支持 noexcept 关键字， 指定特定的 noexcept 异常规范。
Definition: ydef.h:740
ystdex::erase_multi
_tAssocCon::size_type erase_multi(_tAssocCon &con, const typename _tAssocCon::key_type &k)
删除指定关联容器中等价于指定键的所有元素。
Definition: container.hpp:764
ystdex::container_adaptor::container_type
_tSeqCon container_type
Definition: container.hpp:54
ystdex::enable_if_convertible_t
enable_if_t< is_convertible< _tFrom, _tTo >::value, _type > enable_if_convertible_t
Definition: type_traits.hpp:993
ystdex::try_emplace
std::pair< typename _tAssocCon::iterator, bool > try_emplace(_tAssocCon &con, _tKey &&k, _tParams &&...args)
Definition: container.hpp:1170
yconstraint
#define yconstraint(_expr)
约束：接口语义。
Definition: cassert.h:82
ystdex::is_detected
typename details::detector< nonesuch, void, _gOp, _tParams... >::value_t is_detected
Definition: type_traits.hpp:667
ystdex::sequence_container_adaptor::base
container_adaptor< _tSeqCon > base
Definition: container.hpp:200
ystdex::swap
void swap(container_adaptor< _tSeqCon > &x, container_adaptor< _tSeqCon > &y)
Definition: container.hpp:179
ystdex::cpp2014::cend
auto cend(const _tRange &c) -> decltype(std::end(c))
Definition: range.hpp:87
ystdex::operator!=
bool operator!=(nullptr_t lhs, const _type &rhs)
Definition: ydef.h:882
iterator.hpp
通用迭代器。
ystdex::cpp2014::enable_if_t
typename enable_if< _bCond, _type >::type enable_if_t
Definition: type_traits.hpp:350
utility.hpp
实用设施。
ystdex::container_adaptor::container_adaptor
container_adaptor(size_type n)
Definition: container.hpp:72
ystdex::enable_if_inconvertible_t
enable_if_t<!is_convertible< _tFrom, _tTo >::value, _type > enable_if_inconvertible_t
Definition: type_traits.hpp:998
ystdex::container_adaptor
容器适配器。
Definition: container.hpp:51
ystdex::vector_concat
void vector_concat(_tVector &vec, _tIn first, _tIn last)
插入元素到 vector 末尾。
Definition: container.hpp:917
ystdex::details::range_size_t
decltype(size(std::declval< _type >())) range_size_t
Definition: container.hpp:344
ystdex::sequence_container_adaptor
序列容器适配器。
Definition: container.hpp:197
ystdex::container_adaptor::operator==
friend bool operator==(const container_adaptor &x, const container_adaptor &y)
满足容器要求。
Definition: container.hpp:120
ystdex::details::extract_key
const _tAssocCon::key_type & extract_key(const typename _tAssocCon::value_type &val, false_type)
Definition: container.hpp:1016
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:1031
ystdex::sequence_container_adaptor::sequence_container_adaptor
sequence_container_adaptor()=default
满足序列容器要求。
ystdex::insert_or_assign
std::pair< typename _tAssocCon::iterator, bool > insert_or_assign(_tAssocCon &con, _tKey &&k, _tParam &&arg)
Definition: container.hpp:1196
ystdex::assign
void assign(_tCon &con, const _type(&arr)[_vN])
Definition: container.hpp:418
ystdex::container_adaptor::size_type
typename container_type::size_type size_type
Definition: container.hpp:68
ystdex::sequence_container_adaptor::sequence_container_adaptor
sequence_container_adaptor(size_type n, const value_type &value)
Definition: container.hpp:214
ystdex::container_adaptor::reference
typename container_type::reference reference
Definition: container.hpp:63
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:1181
CHRLib::c
c
Definition: CharacterProcessing.h:81
ystdex::sequence_container_adaptor::sequence_container_adaptor
sequence_container_adaptor(size_type n)
Definition: container.hpp:211
ystdex::pop_front_val
bool pop_front_val(_tCon &con, const typename _tCon::value_type &value)
若容器起始存在指定值的元素则移除。
Definition: container.hpp:898
yimpl
#define yimpl(...)
实现标签。
Definition: ydef.h:256
ystdex::assign
void assign(_tCon &con, _tParams &&...args)
插入参数指定的元素到容器。
Definition: container.hpp:412
ystdex::sequence_container_adaptor::operator=
sequence_container_adaptor & operator=(std::initializer_list< value_type > il)
Definition: container.hpp:248
ystdex::container_adaptor::get_container
const container_type & get_container() const
Definition: container.hpp:145
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:979
ystdex::container_adaptor::container_adaptor
container_adaptor(_tIn first, _tIn last)
Definition: container.hpp:79
ystdex::exists
bool exists(const _tCon &con, const _tKey &key)
判断指定的容器中存在指定的键。
Definition: container.hpp:677
ystdex::container_adaptor::difference_type
typename container_type::difference_type difference_type
Definition: container.hpp:67
ystdex::sequence_container_adaptor::sequence_container_adaptor
sequence_container_adaptor(std::initializer_list< value_type > il)
Definition: container.hpp:230
ystdex::container_inserter::container_inserter
container_inserter(_tCon &con)
Definition: container.hpp:491
ystdex::trail
_tCon && trail(_tCon &&con, const typename decay_t< _tCon >::value_type &value={})
保证非空容器以参数指定的元素结尾。
Definition: container.hpp:854
functional.hpp
函数和可调用对象。
std
Definition: memory.hpp:1100
ystdex::sequence_container_adaptor::sequence_container_adaptor
sequence_container_adaptor(_tIn first, _tIn last)
Definition: container.hpp:218
ystdex::details::has_mem_remove_if
is_detected< mem_remove_if_t, _type, _tParams... > has_mem_remove_if
Definition: container.hpp:550
ystdex::container_adaptor::const_reference
typename container_type::const_reference const_reference
Definition: container.hpp:64
ystdex::sequence_container_adaptor::operator=
sequence_container_adaptor & operator=(const sequence_container_adaptor &)=default
ystdex::details::erase_all_in_seq
void erase_all_in_seq(_tSeqCon &con, _type &&value, true_type)
Definition: container.hpp:577
ystdex::container_adaptor::const_iterator
typename container_type::const_iterator const_iterator
Definition: container.hpp:66
ystdex::size
auto size(const _tRange &c) -> decltype(c.size())
类容器访问。
Definition: range.hpp:233
ystdex::container_adaptor::operator=
container_adaptor & operator=(std::initializer_list< value_type > il)
Definition: container.hpp:113
ystdex::erase_first
bool erase_first(_tAssocCon &con, const _tKey &k)
删除指定关联容器中等价于指定键的起始元素。
Definition: container.hpp:745
ystdex::container_adaptor::base
container_type base
Definition: container.hpp:57
ystdex::details::range_size
auto range_size(const _tRange &c, true_type) -> decltype(size(c))
Definition: container.hpp:352
ystdex::seq_insert
void seq_insert(_tCon &con, _tParams &&...args)
顺序插入值至指定容器。
Definition: container.hpp:511
ystdex::container_adaptor::swap
void swap(container_adaptor &con)
Definition: container.hpp:151
ystdex::container_inserter
容器插入函数对象。
Definition: container.hpp:482
ystdex::container_inserter::container_type
_tCon container_type
Definition: container.hpp:485
ystdex::details::erase_remove
void erase_remove(_tSeqCon &con, decltype(begin(con)) first, decltype(end(con)) last, const _type &value)
Definition: container.hpp:561
ystdex::details::mapped_type_t
typename _type::mapped_type mapped_type_t
Definition: container.hpp:1012
ystdex
特性测试宏。
Definition: ydef.h:796
ystdex::sort_unique
_tRandom sort_unique(_tRandom first, _tRandom last)
排序指定序列范围，保留不重复元素的区间。
Definition: algorithm.hpp:506
ystdex::insert_reversed
_tCon::const_iterator insert_reversed(_tCon &con, typename _tCon::const_iterator i, _tIn first, _tIn last)
逆向插入范围到容器的指定位置。
Definition: container.hpp:463
ystdex::container_adaptor::container_adaptor
container_adaptor(size_type n, const value_type &value)
Definition: container.hpp:75
ystdex::details::erase_all_if
void erase_all_if(_tCon &con, decltype(cbegin(con)) first, decltype(cend(con)) last, _fPred pred, true_type)
Definition: container.hpp:634
ystdex::sequence_container_adaptor::operator==
friend bool operator==(const sequence_container_adaptor &x, const sequence_container_adaptor &y)
满足容器要求。
Definition: container.hpp:255
ystdex::emplace_hint_in_place
enable_if_t< is_piecewise_mapped< _tAssocCon, _tKey, _tParams... >::value, typename _tAssocCon::iterator > emplace_hint_in_place(_tAssocCon &con, typename _tAssocCon::const_iterator hint, _tKey &&k, _tParams &&...args)
带有提示的原地插入构造。
Definition: container.hpp:990
ystdex::details::has_mem_remove
is_detected< mem_remove_t, _type, _tParams... > has_mem_remove
Definition: container.hpp:543
ystdex::erase_all
void erase_all(_tCon &con, _tIter first, _tIter last)
删除指定容器中指定区间中的或全部元素。
Definition: container.hpp:696
ystdex::is_undereferenceable
bool is_undereferenceable(const _tIter &)
Definition: deref_op.hpp:45
YSLib::UI::y
SPos SPos y
Definition: YWidget.cpp:44
YSLib::i
return i
Definition: YCoreUtilities.h:176
ystdex::container_adaptor::get_container
container_type & get_container()
Definition: container.hpp:138
ystdex::path_category::empty
ystdex::make_container
_tCon make_container(_tIter first, _tIter last)
构造指定类型的容器。
Definition: container.hpp:308
ystdex::erase_n
_tCon::const_iterator erase_n(_tCon &con, typename _tCon::const_iterator i, typename _tCon::difference_type n)
删除指定容器中指定迭代器起始指定数量的元素。
Definition: container.hpp:795
ystdex::details::mem_remove_if_t
decltype(std::declval< _type >().remove_if(std::declval< _tParams >()...)) mem_remove_if_t
Definition: container.hpp:547
ystdex::search_map
std::pair< typename _tAssocCon::const_iterator, bool > search_map(const _tAssocCon &con, const _tKey &k)
按指定键搜索指定关联容器。
Definition: container.hpp:1082
ystdex::details::mem_remove_t
decltype(std::declval< _type >().remove(std::declval< _tParams >()...)) mem_remove_t
Definition: container.hpp:540
ystdex::details::has_range_size
is_detected_convertible< size_t, range_size_t, _type > has_range_size
Definition: container.hpp:347
ystdex::container_adaptor::iterator
typename container_type::iterator iterator
Definition: container.hpp:65
yconstfn
#define yconstfn
指定编译时常量函数。
Definition: ydef.h:654
ystdex::container_inserter::container
_tCon * container
Definition: container.hpp:488
ystdex::is_detected_convertible
is_convertible< detected_t< _gOp, _tParams... >, _tTo > is_detected_convertible
Definition: type_traits.hpp:686
ystdex::container_adaptor::container_adaptor
container_adaptor()=default
ystdex::details::has_mem_key_type
is_detected< key_type_t, _type > has_mem_key_type
Definition: container.hpp:556
ystdex::range_size
auto range_size(const _tRange &c) -> decltype(details::range_size(c, details::has_range_size< _tRange >()))
取范围大小。
Definition: container.hpp:385
yforward
#define yforward(_expr)
根据参数类型使用 std::forward 传递对应参数。
Definition: ydef.h:969
ystdex::container_adaptor::value_type
typename container_type::value_type value_type
满足容器要求。
Definition: container.hpp:62
ystdex::details::erase_remove_if
void erase_remove_if(_tSeqCon &con, decltype(begin(con)) first, decltype(end(con)) last, _fPred pred)
Definition: container.hpp:569
ystdex::concat
void concat(_tCon &con, _tIn first, _tIn last)
插入元素到容器末尾。
Definition: container.hpp:435
ystdex::cpp2011::begin
_type * begin(_type(&&array)[_vN])
Definition: range.hpp:46
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:1204
YSLib::IO::f
const string &path const String &path _func f
Definition: YSLib/Service/FileSystem.h:430
CHRLib::args
_tParams && args
Definition: CharacterProcessing.h:538
ystdex::pop_back_val
bool pop_back_val(_tCon &con, const typename _tCon::value_type &value)
若容器末尾存在指定值的元素则移除。
Definition: container.hpp:882
ystdex::cpp2014::cbegin
auto cbegin(const _tRange &c) -> decltype(std::begin(c))
Definition: range.hpp:79
ystdex::container_inserter::operator()
auto operator()(_tParams &&...args) -> decltype(container->insert(std::forward< decltype(args)>(args)...))
Definition: container.hpp:497
ystdex::seq_apply
void seq_apply(_func &&)
顺序递归调用。
Definition: functional.hpp:225
ystdex::swap
void swap(sequence_container_adaptor< _tSeqCon > &x, sequence_container_adaptor< _tSeqCon > &y)
Definition: container.hpp:292
algorithm.hpp
泛型算法。
ystdex::container_adaptor::container_adaptor
container_adaptor(std::initializer_list< value_type > il)
Definition: container.hpp:92
ystdex::details::key_type_t
typename _type::key_type key_type_t
Definition: container.hpp:553
ystdex::cpp2011::end
_type * end(_type(&&array)[_vN])
Definition: range.hpp:54
CHRLib::s
_tDst const _tSrc * s
Definition: CharacterProcessing.h:140
ystdex::any_ops::distance
Definition: any_iterator.hpp:74
ystdex::as_const
add_const_t< _type > & as_const(_type &t)
转换 const 引用。
Definition: utility.hpp:50
ystdex::container_adaptor::operator=
container_adaptor & operator=(const container_adaptor &)=default
满足容器要求。
platform::n
size_t n
Definition: YCLib/FileSystem.cpp:321
ystdex::extract_key
const _tAssocCon::key_type & extract_key(const _type &val)
从关联容器的值取键。
Definition: container.hpp:1053
ystdex::retry_for_vector
_tVector retry_for_vector(typename _tVector::size_type s, _func f)
从第一参数指定的起始缓冲区大小循环取向量结果，按需扩大缓冲区。
Definition: container.hpp:941
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:963
ystdex::details::exists
bool exists(const _tCon &con, const _tKey &key, decltype(std::declval< _tCon >().count())=1U)
Definition: container.hpp:523