YSTest: iterator.hpp 源文件

YSTest PreAlpha_b400_20130424 The YSLib Test Project

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

- 文件列表
- 文件成员

全部 类 命名空间 文件 函数 变量 类型定义 枚举 枚举值 友元 宏定义 组 页
iterator.hpp
浏览该文件的文档.
1 ﻿/*
2 Copyright by FrankHB 2011 - 2013.
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_iterator_hpp_
29 #define YB_INC_ystdex_iterator_hpp_ 1
30
31 #include "type_op.hpp" // for std::remove_reference, ystdex::*_tag;
32 #include <iterator> // for std::make_move_iterator, std::iterator,
33 // std::iterator_traits;
34 #include <utility> // for std::make_pair;
35 #include <memory> // for std::addressof;
36
37 namespace ystdex
38 {
39
55
61 template<typename _tIn, typename _fPred>
62 _tIn
63 next_if(_tIn i, _fPred f,
64 typename std::iterator_traits<_tIn>::difference_type n = 1)
65 {
66 return f(*i) ? std::next(i, n) : i;
67 }
68 template<typename _tIn, typename _type>
69 _tIn
70 next_if_eq(_tIn i, const _type& val,
71 typename std::iterator_traits<_tIn>::difference_type n = 1)
72 {
73 return *i == val ? std::next(i, n) : i;
74 }
76
82 template<typename _tBi, typename _fPred>
83 _tBi
84 prev_if(_tBi i, _fPred f,
85 typename std::iterator_traits<_tBi>::difference_type n = 1)
86 {
87 return f(*i) ? std::prev(i, n) : i;
88 }
89 template<typename _tBi, typename _type>
90 _tBi
91 prev_if_eq(_tBi i, const _type& val,
92 typename std::iterator_traits<_tBi>::difference_type n = 1)
93 {
94 return *i == val ? std::prev(i, n) : i;
95 }
97
99
100
106 template<typename _tIterator1, typename _tIterator2>
107 inline auto
108 make_move_iterator_pair(_tIterator1 it1, _tIterator2 it2) -> decltype(
109 std::make_pair(std::make_move_iterator(it1), std::make_move_iterator(it2)))
110 {
111 return std::make_pair(std::make_move_iterator(it1),
112 std::make_move_iterator(it2));
113 }
120 template<typename _tRange>
121 inline auto
122 make_move_iterator_pair(_tRange& c)
123 -> decltype(ystdex::make_move_iterator_pair(begin(c), end(c)))
124 {
125 return ystdex::make_move_iterator_pair(begin(c), end(c));
126 }
127
128
138 template<typename _type>
139 class pointer_iterator
140 {
141 public:
142 typedef _type* iterator_type;
143 typedef typename std::iterator_traits<iterator_type>::iterator_category
144 iterator_category;
145 typedef typename std::iterator_traits<iterator_type>::value_type value_type;
146 typedef typename std::iterator_traits<iterator_type>::difference_type
147 difference_type;
148 typedef typename std::iterator_traits<iterator_type>::pointer pointer;
149 typedef typename std::iterator_traits<iterator_type>::reference reference;
150
151 protected:
152 mutable pointer current;
153
154 public:
155 yconstfn
156 pointer_iterator(nullptr_t = {})
157 : current()
158 {}
160 template<typename _tPointer>
161 explicit yconstfn
162 pointer_iterator(_tPointer&& ptr)
163 : current(yforward(ptr))
164 {}
165 inline
166 pointer_iterator(const pointer_iterator&) = default;
167 inline
168 pointer_iterator(pointer_iterator&&) = default;
169
171 pointer_iterator&
172 operator+=(difference_type n)
173 {
174 current += n;
175 return *this;
176 }
177
179 pointer_iterator&
180 operator-=(difference_type n)
181 {
182 current -= n;
183 return *this;
184 }
185
186 yconstfn reference
187 operator*() const
188 {
189 return *current;
190 }
191
192 yconstfn pointer
193 operator->() const
194 {
195 return current;
196 }
197
198 inline pointer_iterator&
199 operator++()
200 {
201 ++current;
202 return *this;
203 }
204 yconstfn pointer_iterator
205 operator++(int)
206 {
207 return current++;
208 }
209
210 inline pointer_iterator&
211 operator--()
212 {
213 --current;
214 return *this;
215 }
216 yconstfn pointer_iterator
217 operator--(int)
218 {
219 return current--;
220 }
221
223 yconstfn reference
224 operator[](difference_type n) const
225 {
226 return current[n];
227 }
228
230 yconstfn pointer_iterator
231 operator+(difference_type n) const
232 {
233 return pointer_iterator(current + n);
234 }
235
237 yconstfn pointer_iterator
238 operator-(difference_type n) const
239 {
240 return pointer_iterator(current - n);
241 }
242
243 yconstfn
244 operator pointer() const
245 {
246 return current;
247 }
248 };
249
251
252 template<typename _type>
253 inline bool
254 operator==(const pointer_iterator<_type>& x, const pointer_iterator<_type>& y)
255 {
256 typedef typename pointer_iterator<_type>::pointer pointer;
257
258 return pointer(x) == pointer(y);
259 }
260
261 template<typename _type>
262 inline bool
263 operator!=(const pointer_iterator<_type>& x, const pointer_iterator<_type>& y)
264 {
265 return !(x == y);
266 }
268
269
278 template<typename _type>
279 struct pointer_classify
280 {
281 typedef _type type;
282 };
283
284 template<typename _type>
285 struct pointer_classify<_type*>
286 {
287 typedef pointer_iterator<_type> type;
288 };
290
291
299 template<typename _type, typename _tIterator = _type*,
300 typename _tTraits = std::iterator_traits<_tIterator>>
301 class pseudo_iterator
302 {
303 public:
304 typedef _tIterator iterator_type;
306 typedef _tTraits traits_type;
307 typedef typename traits_type::iterator_category iterator_category;
308 typedef typename traits_type::value_type value_type;
309 typedef typename traits_type::difference_type difference_type;
310 typedef typename traits_type::pointer pointer;
311 typedef typename traits_type::reference reference;
312
313 value_type value;
314
315 yconstfn
316 pseudo_iterator()
317 : value()
318 {}
319 explicit yconstfn
320 pseudo_iterator(value_type v)
321 : value(v)
322 {}
323 yconstfn inline
324 pseudo_iterator(const pseudo_iterator&) = default;
325 yconstfn inline
326 pseudo_iterator(pseudo_iterator&&) = default;
327
328 pseudo_iterator&
329 operator=(const pseudo_iterator&) = default;
330 pseudo_iterator&
331 operator=(pseudo_iterator&&) = default;
332
334 pseudo_iterator&
335 operator+=(difference_type)
336 {
337 return *this;
338 }
339
341 pseudo_iterator&
342 operator-=(difference_type)
343 {
344 return *this;
345 }
346
347 //前向迭代器需求。
348 yconstfn reference
349 operator*() const
350 {
351 return value;
352 }
353
354 yconstfn pointer
355 operator->() const
356 {
357 return this;
358 }
359
360 pseudo_iterator&
361 operator++()
362 {
363 return *this;
364 }
365
366 pseudo_iterator
367 operator++(int)
368 {
369 return *this;
370 }
371
372 //双向迭代器需求。
373 yconstfn pseudo_iterator&
374 operator--()
375 {
376 return *this;
377 }
378
379 yconstfn pseudo_iterator
380 operator--(int)
381 {
382 return *this;
383 }
384
385 //随机访问迭代器需求。
387 yconstfn reference
388 operator[](difference_type _n) const
389 {
390 return this[_n];
391 }
392
394 yconstfn pseudo_iterator
395 operator+(difference_type) const
396 {
397 return *this;
398 }
399
401 yconstfn pseudo_iterator
402 operator-(difference_type) const
403 {
404 return *this;
405 }
406 };
407
409
410 template<typename _type, typename _tIterator, typename _tTraits>
411 inline bool
412 operator==(const pseudo_iterator<_type, _tIterator, _tTraits>& x,
413 const pseudo_iterator<_type, _tIterator, _tTraits>& y)
414 {
415 return x.value == y.value;
416 }
417
418 template<typename _type, typename _tIterator, typename _tTraits>
419 inline bool
420 operator!=(const pseudo_iterator<_type, _tIterator, _tTraits>& x,
421 const pseudo_iterator<_type, _tIterator, _tTraits>& y)
422 {
423 return !(x == y);
424 }
426
427
436 template<typename _tIterator, typename _fTransformer>
437 class transformed_iterator : public pointer_classify<_tIterator>::type
438 {
439 public:
444 typedef typename pointer_classify<typename
445 remove_reference<_tIterator>::type>::type iterator_type;
446 typedef _fTransformer transformer_type;
448 typedef typename std::result_of<_fTransformer&(_tIterator&)>::type
449 transformed_type;
451
452 typedef typename add_rvalue_reference<
453 decltype(*std::declval<transformed_type>())>::type reference;
454 typedef typename remove_reference<reference>::type value_type;
455 typedef typename std::iterator_traits<iterator_type>::difference_type
456 difference_type;
457 typedef typename add_pointer<value_type>::type pointer;
459
460 protected:
461 mutable transformer_type transformer;
462
463 public:
465 template<typename _tIter, typename _tTran>
466 explicit yconstfn
467 transformed_iterator(_tIter&& i, _tTran&& f = {})
468 : iterator_type(yforward(i)), transformer(f)
469 {}
470
472 inline reference
473 operator*() const
474 {
475 return *transformer(get());
476 }
477
479 inline pointer
480 operator->() const
481 {
482 return std::addressof(operator*());
483 }
484
489 inline
490 operator iterator_type&()
491 {
492 return *this;
493 }
494
499 yconstfn
500 operator const iterator_type&() const
501 {
502 return *this;
503 }
504
509 inline iterator_type&
510 get()
511 {
512 return *this;
513 }
514
519 yconstfn const iterator_type&
520 get() const
521 {
522 return *this;
523 }
524 };
525
527
528 template<typename _type, typename _fTransformer>
529 inline bool
530 operator==(const transformed_iterator<_type, _fTransformer>& x,
531 const transformed_iterator<_type, _fTransformer>& y)
532 {
533 return x.get() == y.get();
534 }
535
536 template<typename _type, typename _fTransformer>
537 inline bool
538 operator!=(const transformed_iterator<_type, _fTransformer>& x,
539 const transformed_iterator<_type, _fTransformer>& y)
540 {
541 return !(x == y);
542 }
544
545
552 template<typename _tIterator, typename _fTransformer>
553 inline transformed_iterator<typename array_ref_decay<_tIterator>::type,
554 _fTransformer>
555 make_transform(_tIterator&& i, _fTransformer&& f)
556 {
557 return transformed_iterator<typename array_ref_decay<_tIterator>::type,
558 _fTransformer>(yforward(i), f);
559 }
560
561
566 namespace iterator_transformation
567 {
568 template<typename _tIterator>
569 static yconstfn auto
570 first(const _tIterator& i) -> decltype(std::addressof(i->first))
571 {
572 return std::addressof(i->first);
573 }
574 template<typename _tIterator>
575 static yconstfn auto
576 second(const _tIterator& i) -> decltype(std::addressof(i->second))
577 {
578 return std::addressof(i->second);
579 }
580 template<typename _tIterator>
581 static yconstfn auto
582 indirect(const _tIterator& i) -> decltype(*i)
583 {
584 return *i;
585 }
586 } // namespace iterator_transformation;
587
588
594 yconstexpr first_tag get_first{}, get_key{};
595 yconstexpr second_tag get_second{}, get_value{};
597 yconstexpr struct indirect_tag{} get_indirect{};
599
600
605 template<typename _tIterator>
606 inline auto
607 operator|(_tIterator&& i, first_tag)
608 -> decltype(make_transform(yforward(i), iterator_transformation::first<
609 typename array_ref_decay<_tIterator>::type>))
610 {
611 return make_transform(yforward(i), iterator_transformation::first<
612 typename array_ref_decay<_tIterator>::type>);
613 }
614 template<typename _tIterator>
615 inline auto
616 operator|(_tIterator&& i, second_tag)
617 -> decltype(make_transform(yforward(i), iterator_transformation::second<
618 typename array_ref_decay<_tIterator>::type>))
619 {
620 return make_transform(yforward(i), iterator_transformation::second<
621 typename array_ref_decay<_tIterator>::type>);
622 }
624 template<typename _tIterator>
625 inline auto
626 operator|(_tIterator&& i, indirect_tag)
627 -> decltype(make_transform(yforward(i), iterator_transformation::indirect<
628 typename array_ref_decay<_tIterator>::type>))
629 {
630 return make_transform(yforward(i), iterator_transformation::indirect<
631 typename array_ref_decay<_tIterator>::type>);
632 }
633
634
642 template<typename _tMaster, typename _tSlave,
643 class _tTraits = std::iterator_traits<_tMaster>>
644 class pair_iterator : private std::pair<_tMaster, _tSlave>
645 {
646 public:
647 typedef std::pair<_tMaster, _tSlave> pair_type;
648 typedef _tMaster iterator_type;
650 typedef _tTraits traits_type;
651 typedef typename traits_type::iterator_category iterator_category;
652 typedef typename traits_type::value_type value_type;
653 typedef typename traits_type::difference_type difference_type;
654 typedef typename traits_type::pointer pointer;
655 typedef typename traits_type::reference reference;
656
657 yconstfn
658 pair_iterator()
659 : std::pair<_tMaster, _tSlave>(_tMaster(), _tSlave())
660 {}
661 explicit yconstfn
662 pair_iterator(const _tMaster& _i)
663 : std::pair<_tMaster, _tSlave>(_i, _tSlave())
664 {}
665 yconstfn
666 pair_iterator(const _tMaster& _i, const _tSlave& _s)
667 : std::pair<_tMaster, _tSlave>(_i, _s)
668 {}
669 yconstfn
670 pair_iterator(const pair_iterator&) = default;
671 yconstfn
672 pair_iterator(pair_iterator&& _r)
673 : std::pair<_tMaster, _tSlave>(std::move(_r))
674 {}
675
676 inline pair_iterator&
677 operator=(const pair_iterator&) = default;
678 inline pair_iterator&
679 operator=(pair_iterator&&) = default;
680
682 pair_iterator&
683 operator+=(difference_type _n)
684 {
685 yunseq(this->first += _n, this->second += _n);
686 return *this;
687 }
688
690 pair_iterator&
691 operator-=(difference_type _n)
692 {
693 yunseq(this->first -= _n, this->second -= _n);
694 return *this;
695 }
696
697 //前向迭代器需求。
698 yconstfn reference
699 operator*() const
700 {
701 return *this->first;
702 }
703
704 yconstfn pointer
705 operator->() const
706 {
707 return this->first;
708 }
709
710 pair_iterator&
711 operator++()
712 {
713 yunseq(++this->first, ++this->second);
714 return *this;
715 }
716
717 pair_iterator
718 operator++(int)
719 {
720 auto i(*this);
721
722 ++*this;
723 return std::move(i);
724 }
725
726 //双向迭代器需求。
727 pair_iterator&
728 operator--()
729 {
730 yunseq(--this->first, --this->second);
731 return *this;
732 }
733
734 pair_iterator
735 operator--(int)
736 {
737 auto i(*this);
738
739 --*this;
740 return std::move(i);
741 }
742
743 //随机访问迭代器需求。
745 yconstfn reference
746 operator[](difference_type _n) const
747 {
748 return this->first[_n];
749 }
750
752 yconstfn pair_iterator
753 operator+(difference_type _n) const
754 {
755 return pair_iterator(this->first + _n, this->second + _n);
756 }
757
759 yconstfn pair_iterator
760 operator-(difference_type _n) const
761 {
762 return pair_iterator(this->first - _n, this->second - _n);
763 }
764
766 template<typename _tFirst, typename _tSecond, typename = typename
767 std::enable_if<is_convertible<_tMaster, _tFirst>::value
768 && is_convertible<_tSlave, _tSecond>::value, int>::type>
769 operator std::pair<_tFirst, _tSecond>()
770 {
771 return std::pair<_tFirst, _tSecond>(this->first, this->second);
772 }
773
774 yconstfn const pair_type&
775 base() const
776 {
777 return *this;
778 }
779 };
780
782
783 template<typename _tMaster, typename _tSlave>
784 bool
785 operator==(const pair_iterator<_tMaster, _tSlave>& x,
786 const pair_iterator<_tMaster, _tSlave>& y)
787 {
788 return x.base().first == y.base().first
789 && x.base().second == y.base().second();
790 }
791
792 template<typename _tMaster, typename _tSlave>
793 inline bool
794 operator!=(const pair_iterator<_tMaster, _tSlave>& x,
795 const pair_iterator<_tMaster, _tSlave>& y)
796 {
797 return !(x == y);
798 }
800
801
809 template<class _tContainer, typename _type>
810 class subscriptive_iterator
811 {
812 public:
813 typedef _tContainer container_type;
814 typedef std::random_access_iterator_tag iterator_category;
815 typedef _type value_type;
816 typedef ptrdiff_t difference_type;
817 typedef _type* pointer;
818 typedef _type& reference;
819
820 protected:
821 _tContainer* p_cont;
822 size_t idx;
823
824 public:
825 yconstfn
826 subscriptive_iterator(_tContainer& c, size_t i)
827 : p_cont(std::addressof(c)), idx(i)
828 {}
829
830 subscriptive_iterator&
831 operator+=(difference_type n)
832 {
833 idx += n;
834 return *this;
835 }
836
837 subscriptive_iterator&
838 operator-=(difference_type n)
839 {
840 yassume(!(idx < n));
841
842 idx -= n;
843 return *this;
844 }
845
846 reference
847 operator*()
848 {
849 return (*p_cont)[idx];
850 }
851
852 pointer
853 operator->()
854 {
855 return std::addressof(**this);
856 }
857
858 subscriptive_iterator&
859 operator++()
860 {
861 ++idx;
862 return *this;
863 }
864 subscriptive_iterator
865 operator++(int)
866 {
867 auto i(*this);
868
869 ++*this;
870 return std::move(i);
871 }
872
873 subscriptive_iterator
874 operator--()
875 {
876 --idx;
877 return *this;
878 }
879 subscriptive_iterator
880 operator--(int)
881 {
882 auto i(*this);
883
884 --*this;
885 return std::move(i);
886 }
887
888 reference
889 operator[](difference_type n) const
890 {
891 yassume(!(idx + n < 0));
892
893 return (*p_cont)[idx + n];
894 }
895
896 subscriptive_iterator
897 operator+(difference_type n) const
898 {
899 yassume(!(idx + n < 0));
900
901 return subscriptive_iterator(*p_cont, idx + n);
902 }
903
904 subscriptive_iterator
905 operator-(difference_type n) const
906 {
907 yassume(!(idx + n < 0));
908
909 return subscriptive_iterator(*p_cont, idx - n);
910 }
911
913 _tContainer*
914 container() const
915 {
916 return p_cont;
917 }
918
919 bool
920 equals(const subscriptive_iterator<_tContainer, _type>& i) const
921 {
922 return p_cont == i.p_cont && idx == i.idx;
923 }
924
926 size_t
927 index() const
928 {
929 return idx;
930 }
931 };
932
937 template<class _tContainer, typename _type>
938 bool
939 operator==(const subscriptive_iterator<_tContainer, _type>& x,
940 const subscriptive_iterator<_tContainer, _type>& y)
941 {
942 return x.equals(y);
943 }
944
949 template<class _tContainer, typename _type>
950 bool
951 operator!=(const subscriptive_iterator<_tContainer, _type>& x,
952 const subscriptive_iterator<_tContainer, _type>& y)
953 {
954 return !(x == y);
955 }
956
957 } // namespace ystdex;
958
959 #endif
960