10b57cec5SDimitry Andric// -*- C++ -*- 20b57cec5SDimitry Andric//===-------------------------- iterator ----------------------------------===// 30b57cec5SDimitry Andric// 40b57cec5SDimitry Andric// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 50b57cec5SDimitry Andric// See https://llvm.org/LICENSE.txt for license information. 60b57cec5SDimitry Andric// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 70b57cec5SDimitry Andric// 80b57cec5SDimitry Andric//===----------------------------------------------------------------------===// 90b57cec5SDimitry Andric 100b57cec5SDimitry Andric#ifndef _LIBCPP_ITERATOR 110b57cec5SDimitry Andric#define _LIBCPP_ITERATOR 120b57cec5SDimitry Andric 130b57cec5SDimitry Andric/* 140b57cec5SDimitry Andric iterator synopsis 150b57cec5SDimitry Andric 16*5f7ddb14SDimitry Andric#include <concepts> 17*5f7ddb14SDimitry Andric 180b57cec5SDimitry Andricnamespace std 190b57cec5SDimitry Andric{ 20*5f7ddb14SDimitry Andrictemplate<class> struct incrementable_traits; // since C++20 21*5f7ddb14SDimitry Andrictemplate<class T> 22*5f7ddb14SDimitry Andric using iter_difference_t = see below; // since C++20 23*5f7ddb14SDimitry Andric 24*5f7ddb14SDimitry Andrictemplate<class> struct indirectly_readable_traits; // since C++20 25*5f7ddb14SDimitry Andrictemplate<class T> 26*5f7ddb14SDimitry Andric using iter_value_t = see below; // since C++20 270b57cec5SDimitry Andric 280b57cec5SDimitry Andrictemplate<class Iterator> 29*5f7ddb14SDimitry Andricstruct iterator_traits; 300b57cec5SDimitry Andric 310b57cec5SDimitry Andrictemplate<class T> 32*5f7ddb14SDimitry Andric requires is_object_v<T> // since C++20 33*5f7ddb14SDimitry Andricstruct iterator_traits<T*>; 34*5f7ddb14SDimitry Andric 35*5f7ddb14SDimitry Andrictemplate<dereferenceable T> 36*5f7ddb14SDimitry Andric using iter_reference_t = decltype(*declval<T&>()); 37*5f7ddb14SDimitry Andric 38*5f7ddb14SDimitry Andricnamespace ranges::inline unspecified { 39*5f7ddb14SDimitry Andric inline constexpr unspecified iter_move = unspecified; // since C++20, nodiscard as an extension 40*5f7ddb14SDimitry Andric}} 41*5f7ddb14SDimitry Andric 42*5f7ddb14SDimitry Andrictemplate<dereferenceable T> 43*5f7ddb14SDimitry Andric requires ... 44*5f7ddb14SDimitry Andricusing iter_rvalue_reference_t = decltype(ranges::iter_move(declval<T&>())); // since C++20 45*5f7ddb14SDimitry Andric 46*5f7ddb14SDimitry Andric// [iterator.concepts], iterator concepts 47*5f7ddb14SDimitry Andric// [iterator.concept.readable], concept indirectly_readable 48*5f7ddb14SDimitry Andrictemplate<class In> 49*5f7ddb14SDimitry Andric concept indirectly_readable = see below; // since C++20 50*5f7ddb14SDimitry Andric 51*5f7ddb14SDimitry Andrictemplate<indirectly_readable T> 52*5f7ddb14SDimitry Andric using iter_common_reference_t = 53*5f7ddb14SDimitry Andric common_reference_t<iter_reference_t<T>, iter_value_t<T>&>; // since C++20 54*5f7ddb14SDimitry Andric 55*5f7ddb14SDimitry Andric// [iterator.concept.writable], concept indirectly_writable 56*5f7ddb14SDimitry Andrictemplate<class Out, class T> 57*5f7ddb14SDimitry Andric concept indirectly_writable = see below; // since C++20 58*5f7ddb14SDimitry Andric 59*5f7ddb14SDimitry Andric// [iterator.concept.winc], concept weakly_incrementable 60*5f7ddb14SDimitry Andrictemplate<class I> 61*5f7ddb14SDimitry Andric concept weakly_incrementable = see below; // since C++20 62*5f7ddb14SDimitry Andric 63*5f7ddb14SDimitry Andric// [iterator.concept.inc], concept incrementable 64*5f7ddb14SDimitry Andrictemplate<class I> 65*5f7ddb14SDimitry Andric concept incrementable = see below; // since C++20 66*5f7ddb14SDimitry Andric 67*5f7ddb14SDimitry Andric// [iterator.concept.iterator], concept input_or_output_iterator 68*5f7ddb14SDimitry Andric template<class I> 69*5f7ddb14SDimitry Andric concept input_or_output_iterator = see below; // since C++20 70*5f7ddb14SDimitry Andric 71*5f7ddb14SDimitry Andric// [iterator.concept.sentinel], concept sentinel_for 72*5f7ddb14SDimitry Andrictemplate<class S, class I> 73*5f7ddb14SDimitry Andric concept sentinel_for = see below; // since C++20 74*5f7ddb14SDimitry Andric 75*5f7ddb14SDimitry Andric// [iterator.concept.sizedsentinel], concept sized_sentinel_for 76*5f7ddb14SDimitry Andrictemplate<class S, class I> 77*5f7ddb14SDimitry Andric inline constexpr bool disable_sized_sentinel_for = false; 78*5f7ddb14SDimitry Andric 79*5f7ddb14SDimitry Andrictemplate<class S, class I> 80*5f7ddb14SDimitry Andric concept sized_sentinel_for = see below; 81*5f7ddb14SDimitry Andric 82*5f7ddb14SDimitry Andric// [iterator.concept.input], concept input_iterator 83*5f7ddb14SDimitry Andrictemplate<class I> 84*5f7ddb14SDimitry Andric concept input_iterator = see below; // since C++20 85*5f7ddb14SDimitry Andric 86*5f7ddb14SDimitry Andric// [iterator.concept.output], concept output_iterator 87*5f7ddb14SDimitry Andrictemplate<class I, class T> 88*5f7ddb14SDimitry Andric concept output_iterator = see below; // since C++20 89*5f7ddb14SDimitry Andric 90*5f7ddb14SDimitry Andric// [iterator.concept.forward], concept forward_iterator 91*5f7ddb14SDimitry Andrictemplate<class I> 92*5f7ddb14SDimitry Andric concept forward_iterator = see below; // since C++20 93*5f7ddb14SDimitry Andric 94*5f7ddb14SDimitry Andric// [iterator.concept.bidir], concept bidirectional_iterator 95*5f7ddb14SDimitry Andrictemplate<class I> 96*5f7ddb14SDimitry Andric concept bidirectional_iterator = see below; // since C++20 97*5f7ddb14SDimitry Andric 98*5f7ddb14SDimitry Andric// [iterator.concept.random.access], concept random_access_iterator 99*5f7ddb14SDimitry Andrictemplate<class I> 100*5f7ddb14SDimitry Andric concept random_access_iterator = see below; // since C++20 101*5f7ddb14SDimitry Andric 102*5f7ddb14SDimitry Andric// [indirectcallable] 103*5f7ddb14SDimitry Andric// [indirectcallable.indirectinvocable] 104*5f7ddb14SDimitry Andrictemplate<class F, class I> 105*5f7ddb14SDimitry Andric concept indirectly_unary_invocable = see below; // since C++20 106*5f7ddb14SDimitry Andric 107*5f7ddb14SDimitry Andrictemplate<class F, class I> 108*5f7ddb14SDimitry Andric concept indirectly_regular_unary_invocable = see below; // since C++20 109*5f7ddb14SDimitry Andric 110*5f7ddb14SDimitry Andrictemplate<class F, class I> 111*5f7ddb14SDimitry Andric concept indirect_unary_predicate = see below; // since C++20 112*5f7ddb14SDimitry Andric 113*5f7ddb14SDimitry Andrictemplate<class F, class I1, class I2> 114*5f7ddb14SDimitry Andric concept indirect_binary_predicate = see below; // since C++20 115*5f7ddb14SDimitry Andric 116*5f7ddb14SDimitry Andrictemplate<class F, class I1, class I2 = I1> 117*5f7ddb14SDimitry Andric concept indirect_equivalence_relation = see below; // since C++20 118*5f7ddb14SDimitry Andric 119*5f7ddb14SDimitry Andrictemplate<class F, class I1, class I2 = I1> 120*5f7ddb14SDimitry Andric concept indirect_strict_weak_order = see below; // since C++20 121*5f7ddb14SDimitry Andric 122*5f7ddb14SDimitry Andrictemplate<class F, class... Is> 123*5f7ddb14SDimitry Andric using indirect_result_t = see below; // since C++20 124*5f7ddb14SDimitry Andric 125*5f7ddb14SDimitry Andric// [projected], projected 126*5f7ddb14SDimitry Andrictemplate<indirectly_readable I, indirectly_regular_unary_invocable<I> Proj> 127*5f7ddb14SDimitry Andric struct projected; // since C++20 128*5f7ddb14SDimitry Andric 129*5f7ddb14SDimitry Andrictemplate<weakly_incrementable I, indirectly_regular_unary_invocable<I> Proj> 130*5f7ddb14SDimitry Andric struct incrementable_traits<projected<I, Proj>>; // since C++20 131*5f7ddb14SDimitry Andric 132*5f7ddb14SDimitry Andric// [alg.req.ind.move], concept indirectly_movable 133*5f7ddb14SDimitry Andrictemplate<class In, class Out> 134*5f7ddb14SDimitry Andric concept indirectly_movable = see below; // since C++20 135*5f7ddb14SDimitry Andric 136*5f7ddb14SDimitry Andrictemplate<class In, class Out> 137*5f7ddb14SDimitry Andric concept indirectly_movable_storable = see below; // since C++20 138*5f7ddb14SDimitry Andric 139*5f7ddb14SDimitry Andric// [alg.req.ind.swap], concept indirectly_swappable 140*5f7ddb14SDimitry Andrictemplate<class I1, class I2 = I1> 141*5f7ddb14SDimitry Andric concept indirectly_swappable = see below; // since C++20 142*5f7ddb14SDimitry Andric 143*5f7ddb14SDimitry Andrictemplate<input_or_output_iterator I, sentinel_for<I> S> 144*5f7ddb14SDimitry Andric requires (!same_as<I, S> && copyable<I>) 145*5f7ddb14SDimitry Andricclass common_iterator; // since C++20 1460b57cec5SDimitry Andric 1470b57cec5SDimitry Andrictemplate<class Category, class T, class Distance = ptrdiff_t, 1480b57cec5SDimitry Andric class Pointer = T*, class Reference = T&> 149*5f7ddb14SDimitry Andricstruct iterator // deprecated in C++17 1500b57cec5SDimitry Andric{ 1510b57cec5SDimitry Andric typedef T value_type; 1520b57cec5SDimitry Andric typedef Distance difference_type; 1530b57cec5SDimitry Andric typedef Pointer pointer; 1540b57cec5SDimitry Andric typedef Reference reference; 1550b57cec5SDimitry Andric typedef Category iterator_category; 1560b57cec5SDimitry Andric}; 1570b57cec5SDimitry Andric 1580b57cec5SDimitry Andricstruct input_iterator_tag {}; 1590b57cec5SDimitry Andricstruct output_iterator_tag {}; 1600b57cec5SDimitry Andricstruct forward_iterator_tag : public input_iterator_tag {}; 1610b57cec5SDimitry Andricstruct bidirectional_iterator_tag : public forward_iterator_tag {}; 1620b57cec5SDimitry Andricstruct random_access_iterator_tag : public bidirectional_iterator_tag {}; 1630b57cec5SDimitry Andric 1640b57cec5SDimitry Andric// 27.4.3, iterator operations 1655ffd83dbSDimitry Andrictemplate <class InputIterator, class Distance> // constexpr in C++17 1665ffd83dbSDimitry Andric constexpr void advance(InputIterator& i, Distance n); 1670b57cec5SDimitry Andric 1680b57cec5SDimitry Andrictemplate <class InputIterator> // constexpr in C++17 1690b57cec5SDimitry Andric constexpr typename iterator_traits<InputIterator>::difference_type 1700b57cec5SDimitry Andric distance(InputIterator first, InputIterator last); 1710b57cec5SDimitry Andric 1720b57cec5SDimitry Andrictemplate <class InputIterator> // constexpr in C++17 1730b57cec5SDimitry Andric constexpr InputIterator next(InputIterator x, 1740b57cec5SDimitry Andrictypename iterator_traits<InputIterator>::difference_type n = 1); 1750b57cec5SDimitry Andric 1760b57cec5SDimitry Andrictemplate <class BidirectionalIterator> // constexpr in C++17 1770b57cec5SDimitry Andric constexpr BidirectionalIterator prev(BidirectionalIterator x, 1780b57cec5SDimitry Andric typename iterator_traits<BidirectionalIterator>::difference_type n = 1); 1790b57cec5SDimitry Andric 180*5f7ddb14SDimitry Andric// [range.iter.ops], range iterator operations 181*5f7ddb14SDimitry Andricnamespace ranges { 182*5f7ddb14SDimitry Andric // [range.iter.op.advance], ranges::advance 183*5f7ddb14SDimitry Andric template<input_or_output_iterator I> 184*5f7ddb14SDimitry Andric constexpr void advance(I& i, iter_difference_t<I> n); // since C++20 185*5f7ddb14SDimitry Andric template<input_or_output_iterator I, sentinel_for<I> S> 186*5f7ddb14SDimitry Andric constexpr void advance(I& i, S bound); // since C++20 187*5f7ddb14SDimitry Andric template<input_or_output_iterator I, sentinel_for<I> S> 188*5f7ddb14SDimitry Andric constexpr iter_difference_t<I> advance(I& i, iter_difference_t<I> n, S bound); // since C++20 189*5f7ddb14SDimitry Andric} 190*5f7ddb14SDimitry Andric 1910b57cec5SDimitry Andrictemplate <class Iterator> 1920b57cec5SDimitry Andricclass reverse_iterator 193*5f7ddb14SDimitry Andric : public iterator<typename iterator_traits<Iterator>::iterator_category, // until C++17 1940b57cec5SDimitry Andric typename iterator_traits<Iterator>::value_type, 1950b57cec5SDimitry Andric typename iterator_traits<Iterator>::difference_type, 1960b57cec5SDimitry Andric typename iterator_traits<Iterator>::pointer, 1970b57cec5SDimitry Andric typename iterator_traits<Iterator>::reference> 1980b57cec5SDimitry Andric{ 1990b57cec5SDimitry Andricprotected: 2000b57cec5SDimitry Andric Iterator current; 2010b57cec5SDimitry Andricpublic: 2020b57cec5SDimitry Andric typedef Iterator iterator_type; 2030b57cec5SDimitry Andric typedef typename iterator_traits<Iterator>::difference_type difference_type; 2040b57cec5SDimitry Andric typedef typename iterator_traits<Iterator>::reference reference; 2050b57cec5SDimitry Andric typedef typename iterator_traits<Iterator>::pointer pointer; 2060b57cec5SDimitry Andric 2070b57cec5SDimitry Andric constexpr reverse_iterator(); 2080b57cec5SDimitry Andric constexpr explicit reverse_iterator(Iterator x); 2090b57cec5SDimitry Andric template <class U> constexpr reverse_iterator(const reverse_iterator<U>& u); 2100b57cec5SDimitry Andric template <class U> constexpr reverse_iterator& operator=(const reverse_iterator<U>& u); 2110b57cec5SDimitry Andric constexpr Iterator base() const; 2120b57cec5SDimitry Andric constexpr reference operator*() const; 2130b57cec5SDimitry Andric constexpr pointer operator->() const; 2140b57cec5SDimitry Andric constexpr reverse_iterator& operator++(); 2150b57cec5SDimitry Andric constexpr reverse_iterator operator++(int); 2160b57cec5SDimitry Andric constexpr reverse_iterator& operator--(); 2170b57cec5SDimitry Andric constexpr reverse_iterator operator--(int); 2180b57cec5SDimitry Andric constexpr reverse_iterator operator+ (difference_type n) const; 2190b57cec5SDimitry Andric constexpr reverse_iterator& operator+=(difference_type n); 2200b57cec5SDimitry Andric constexpr reverse_iterator operator- (difference_type n) const; 2210b57cec5SDimitry Andric constexpr reverse_iterator& operator-=(difference_type n); 2220b57cec5SDimitry Andric constexpr reference operator[](difference_type n) const; 2230b57cec5SDimitry Andric}; 2240b57cec5SDimitry Andric 2250b57cec5SDimitry Andrictemplate <class Iterator1, class Iterator2> 2260b57cec5SDimitry Andricconstexpr bool // constexpr in C++17 2270b57cec5SDimitry Andricoperator==(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 2280b57cec5SDimitry Andric 2290b57cec5SDimitry Andrictemplate <class Iterator1, class Iterator2> 2300b57cec5SDimitry Andricconstexpr bool // constexpr in C++17 2310b57cec5SDimitry Andricoperator<(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 2320b57cec5SDimitry Andric 2330b57cec5SDimitry Andrictemplate <class Iterator1, class Iterator2> 2340b57cec5SDimitry Andricconstexpr bool // constexpr in C++17 2350b57cec5SDimitry Andricoperator!=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 2360b57cec5SDimitry Andric 2370b57cec5SDimitry Andrictemplate <class Iterator1, class Iterator2> 2380b57cec5SDimitry Andricconstexpr bool // constexpr in C++17 2390b57cec5SDimitry Andricoperator>(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 2400b57cec5SDimitry Andric 2410b57cec5SDimitry Andrictemplate <class Iterator1, class Iterator2> 2420b57cec5SDimitry Andricconstexpr bool // constexpr in C++17 2430b57cec5SDimitry Andricoperator>=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 2440b57cec5SDimitry Andric 2450b57cec5SDimitry Andrictemplate <class Iterator1, class Iterator2> 2460b57cec5SDimitry Andricconstexpr bool // constexpr in C++17 2470b57cec5SDimitry Andricoperator<=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 2480b57cec5SDimitry Andric 2490b57cec5SDimitry Andrictemplate <class Iterator1, class Iterator2> 2500b57cec5SDimitry Andricconstexpr auto 2510b57cec5SDimitry Andricoperator-(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y) 2520b57cec5SDimitry Andric-> decltype(__y.base() - __x.base()); // constexpr in C++17 2530b57cec5SDimitry Andric 2540b57cec5SDimitry Andrictemplate <class Iterator> 2550b57cec5SDimitry Andricconstexpr reverse_iterator<Iterator> 2560b57cec5SDimitry Andricoperator+(typename reverse_iterator<Iterator>::difference_type n, 2570b57cec5SDimitry Andric const reverse_iterator<Iterator>& x); // constexpr in C++17 2580b57cec5SDimitry Andric 2590b57cec5SDimitry Andrictemplate <class Iterator> 2600b57cec5SDimitry Andricconstexpr reverse_iterator<Iterator> make_reverse_iterator(Iterator i); // C++14, constexpr in C++17 2610b57cec5SDimitry Andric 2620b57cec5SDimitry Andrictemplate <class Container> 2630b57cec5SDimitry Andricclass back_insert_iterator 264*5f7ddb14SDimitry Andric : public iterator<output_iterator_tag, void, void, void, void> // until C++17 2650b57cec5SDimitry Andric{ 2660b57cec5SDimitry Andricprotected: 2670b57cec5SDimitry Andric Container* container; 2680b57cec5SDimitry Andricpublic: 2690b57cec5SDimitry Andric typedef Container container_type; 2700b57cec5SDimitry Andric typedef void value_type; 271*5f7ddb14SDimitry Andric typedef void difference_type; // until C++20 272*5f7ddb14SDimitry Andric typedef ptrdiff_t difference_type; // since C++20 2730b57cec5SDimitry Andric typedef void reference; 2740b57cec5SDimitry Andric typedef void pointer; 2750b57cec5SDimitry Andric 276*5f7ddb14SDimitry Andric explicit back_insert_iterator(Container& x); // constexpr in C++20 277*5f7ddb14SDimitry Andric back_insert_iterator& operator=(const typename Container::value_type& value); // constexpr in C++20 278*5f7ddb14SDimitry Andric back_insert_iterator& operator*(); // constexpr in C++20 279*5f7ddb14SDimitry Andric back_insert_iterator& operator++(); // constexpr in C++20 280*5f7ddb14SDimitry Andric back_insert_iterator operator++(int); // constexpr in C++20 2810b57cec5SDimitry Andric}; 2820b57cec5SDimitry Andric 283*5f7ddb14SDimitry Andrictemplate <class Container> back_insert_iterator<Container> back_inserter(Container& x); // constexpr in C++20 2840b57cec5SDimitry Andric 2850b57cec5SDimitry Andrictemplate <class Container> 2860b57cec5SDimitry Andricclass front_insert_iterator 287*5f7ddb14SDimitry Andric : public iterator<output_iterator_tag, void, void, void, void> // until C++17 2880b57cec5SDimitry Andric{ 2890b57cec5SDimitry Andricprotected: 2900b57cec5SDimitry Andric Container* container; 2910b57cec5SDimitry Andricpublic: 2920b57cec5SDimitry Andric typedef Container container_type; 2930b57cec5SDimitry Andric typedef void value_type; 294*5f7ddb14SDimitry Andric typedef void difference_type; // until C++20 295*5f7ddb14SDimitry Andric typedef ptrdiff_t difference_type; // since C++20 2960b57cec5SDimitry Andric typedef void reference; 2970b57cec5SDimitry Andric typedef void pointer; 2980b57cec5SDimitry Andric 299*5f7ddb14SDimitry Andric explicit front_insert_iterator(Container& x); // constexpr in C++20 300*5f7ddb14SDimitry Andric front_insert_iterator& operator=(const typename Container::value_type& value); // constexpr in C++20 301*5f7ddb14SDimitry Andric front_insert_iterator& operator*(); // constexpr in C++20 302*5f7ddb14SDimitry Andric front_insert_iterator& operator++(); // constexpr in C++20 303*5f7ddb14SDimitry Andric front_insert_iterator operator++(int); // constexpr in C++20 3040b57cec5SDimitry Andric}; 3050b57cec5SDimitry Andric 306*5f7ddb14SDimitry Andrictemplate <class Container> front_insert_iterator<Container> front_inserter(Container& x); // constexpr in C++20 3070b57cec5SDimitry Andric 3080b57cec5SDimitry Andrictemplate <class Container> 3090b57cec5SDimitry Andricclass insert_iterator 310*5f7ddb14SDimitry Andric : public iterator<output_iterator_tag, void, void, void, void> // until C++17 3110b57cec5SDimitry Andric{ 3120b57cec5SDimitry Andricprotected: 3130b57cec5SDimitry Andric Container* container; 3140b57cec5SDimitry Andric typename Container::iterator iter; 3150b57cec5SDimitry Andricpublic: 3160b57cec5SDimitry Andric typedef Container container_type; 3170b57cec5SDimitry Andric typedef void value_type; 318*5f7ddb14SDimitry Andric typedef void difference_type; // until C++20 319*5f7ddb14SDimitry Andric typedef ptrdiff_t difference_type; // since C++20 3200b57cec5SDimitry Andric typedef void reference; 3210b57cec5SDimitry Andric typedef void pointer; 3220b57cec5SDimitry Andric 323*5f7ddb14SDimitry Andric insert_iterator(Container& x, typename Container::iterator i); // constexpr in C++20 324*5f7ddb14SDimitry Andric insert_iterator& operator=(const typename Container::value_type& value); // constexpr in C++20 325*5f7ddb14SDimitry Andric insert_iterator& operator*(); // constexpr in C++20 326*5f7ddb14SDimitry Andric insert_iterator& operator++(); // constexpr in C++20 327*5f7ddb14SDimitry Andric insert_iterator& operator++(int); // constexpr in C++20 3280b57cec5SDimitry Andric}; 3290b57cec5SDimitry Andric 3300b57cec5SDimitry Andrictemplate <class Container, class Iterator> 331*5f7ddb14SDimitry Andricinsert_iterator<Container> inserter(Container& x, Iterator i); // constexpr in C++20 3320b57cec5SDimitry Andric 3330b57cec5SDimitry Andrictemplate <class Iterator> 3340b57cec5SDimitry Andricclass move_iterator { 3350b57cec5SDimitry Andricpublic: 3360b57cec5SDimitry Andric typedef Iterator iterator_type; 3370b57cec5SDimitry Andric typedef typename iterator_traits<Iterator>::difference_type difference_type; 3380b57cec5SDimitry Andric typedef Iterator pointer; 3390b57cec5SDimitry Andric typedef typename iterator_traits<Iterator>::value_type value_type; 3400b57cec5SDimitry Andric typedef typename iterator_traits<Iterator>::iterator_category iterator_category; 3410b57cec5SDimitry Andric typedef value_type&& reference; 3420b57cec5SDimitry Andric 3430b57cec5SDimitry Andric constexpr move_iterator(); // all the constexprs are in C++17 3440b57cec5SDimitry Andric constexpr explicit move_iterator(Iterator i); 3450b57cec5SDimitry Andric template <class U> 3460b57cec5SDimitry Andric constexpr move_iterator(const move_iterator<U>& u); 3470b57cec5SDimitry Andric template <class U> 3480b57cec5SDimitry Andric constexpr move_iterator& operator=(const move_iterator<U>& u); 3490b57cec5SDimitry Andric constexpr iterator_type base() const; 3500b57cec5SDimitry Andric constexpr reference operator*() const; 3510b57cec5SDimitry Andric constexpr pointer operator->() const; 3520b57cec5SDimitry Andric constexpr move_iterator& operator++(); 3530b57cec5SDimitry Andric constexpr move_iterator operator++(int); 3540b57cec5SDimitry Andric constexpr move_iterator& operator--(); 3550b57cec5SDimitry Andric constexpr move_iterator operator--(int); 3560b57cec5SDimitry Andric constexpr move_iterator operator+(difference_type n) const; 3570b57cec5SDimitry Andric constexpr move_iterator& operator+=(difference_type n); 3580b57cec5SDimitry Andric constexpr move_iterator operator-(difference_type n) const; 3590b57cec5SDimitry Andric constexpr move_iterator& operator-=(difference_type n); 3600b57cec5SDimitry Andric constexpr unspecified operator[](difference_type n) const; 3610b57cec5SDimitry Andricprivate: 3620b57cec5SDimitry Andric Iterator current; // exposition only 3630b57cec5SDimitry Andric}; 3640b57cec5SDimitry Andric 3650b57cec5SDimitry Andrictemplate <class Iterator1, class Iterator2> 3660b57cec5SDimitry Andricconstexpr bool // constexpr in C++17 3670b57cec5SDimitry Andricoperator==(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 3680b57cec5SDimitry Andric 3690b57cec5SDimitry Andrictemplate <class Iterator1, class Iterator2> 3700b57cec5SDimitry Andricconstexpr bool // constexpr in C++17 3710b57cec5SDimitry Andricoperator!=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 3720b57cec5SDimitry Andric 3730b57cec5SDimitry Andrictemplate <class Iterator1, class Iterator2> 3740b57cec5SDimitry Andricconstexpr bool // constexpr in C++17 3750b57cec5SDimitry Andricoperator<(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 3760b57cec5SDimitry Andric 3770b57cec5SDimitry Andrictemplate <class Iterator1, class Iterator2> 3780b57cec5SDimitry Andricconstexpr bool // constexpr in C++17 3790b57cec5SDimitry Andricoperator<=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 3800b57cec5SDimitry Andric 3810b57cec5SDimitry Andrictemplate <class Iterator1, class Iterator2> 3820b57cec5SDimitry Andricconstexpr bool // constexpr in C++17 3830b57cec5SDimitry Andricoperator>(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 3840b57cec5SDimitry Andric 3850b57cec5SDimitry Andrictemplate <class Iterator1, class Iterator2> 3860b57cec5SDimitry Andricconstexpr bool // constexpr in C++17 3870b57cec5SDimitry Andricoperator>=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 3880b57cec5SDimitry Andric 3890b57cec5SDimitry Andrictemplate <class Iterator1, class Iterator2> 3900b57cec5SDimitry Andricconstexpr auto // constexpr in C++17 3910b57cec5SDimitry Andricoperator-(const move_iterator<Iterator1>& x, 3920b57cec5SDimitry Andric const move_iterator<Iterator2>& y) -> decltype(x.base() - y.base()); 3930b57cec5SDimitry Andric 3940b57cec5SDimitry Andrictemplate <class Iterator> 3950b57cec5SDimitry Andricconstexpr move_iterator<Iterator> operator+( // constexpr in C++17 3960b57cec5SDimitry Andric typename move_iterator<Iterator>::difference_type n, 3970b57cec5SDimitry Andric const move_iterator<Iterator>& x); 3980b57cec5SDimitry Andric 3990b57cec5SDimitry Andrictemplate <class Iterator> // constexpr in C++17 4000b57cec5SDimitry Andricconstexpr move_iterator<Iterator> make_move_iterator(const Iterator& i); 4010b57cec5SDimitry Andric 402*5f7ddb14SDimitry Andric// [default.sentinel], default sentinel 403*5f7ddb14SDimitry Andricstruct default_sentinel_t; 404*5f7ddb14SDimitry Andricinline constexpr default_sentinel_t default_sentinel{}; 405*5f7ddb14SDimitry Andric 406*5f7ddb14SDimitry Andric// [iterators.counted], counted iterators 407*5f7ddb14SDimitry Andrictemplate<input_or_output_iterator I> class counted_iterator; 408*5f7ddb14SDimitry Andric 409*5f7ddb14SDimitry Andrictemplate<input_iterator I> 410*5f7ddb14SDimitry Andric requires see below 411*5f7ddb14SDimitry Andric struct iterator_traits<counted_iterator<I>>; 4120b57cec5SDimitry Andric 4130b57cec5SDimitry Andrictemplate <class T, class charT = char, class traits = char_traits<charT>, class Distance = ptrdiff_t> 4140b57cec5SDimitry Andricclass istream_iterator 415*5f7ddb14SDimitry Andric : public iterator<input_iterator_tag, T, Distance, const T*, const T&> // until C++17 4160b57cec5SDimitry Andric{ 4170b57cec5SDimitry Andricpublic: 418*5f7ddb14SDimitry Andric typedef input_iterator_tag iterator_category; 419*5f7ddb14SDimitry Andric typedef T value_type; 420*5f7ddb14SDimitry Andric typedef Distance difference_type; 421*5f7ddb14SDimitry Andric typedef const T* pointer; 422*5f7ddb14SDimitry Andric typedef const T& reference; 423*5f7ddb14SDimitry Andric 4240b57cec5SDimitry Andric typedef charT char_type; 4250b57cec5SDimitry Andric typedef traits traits_type; 4260b57cec5SDimitry Andric typedef basic_istream<charT, traits> istream_type; 4270b57cec5SDimitry Andric 4280b57cec5SDimitry Andric constexpr istream_iterator(); 4290b57cec5SDimitry Andric istream_iterator(istream_type& s); 4300b57cec5SDimitry Andric istream_iterator(const istream_iterator& x); 4310b57cec5SDimitry Andric ~istream_iterator(); 4320b57cec5SDimitry Andric 4330b57cec5SDimitry Andric const T& operator*() const; 4340b57cec5SDimitry Andric const T* operator->() const; 4350b57cec5SDimitry Andric istream_iterator& operator++(); 4360b57cec5SDimitry Andric istream_iterator operator++(int); 4370b57cec5SDimitry Andric}; 4380b57cec5SDimitry Andric 4390b57cec5SDimitry Andrictemplate <class T, class charT, class traits, class Distance> 4400b57cec5SDimitry Andricbool operator==(const istream_iterator<T,charT,traits,Distance>& x, 4410b57cec5SDimitry Andric const istream_iterator<T,charT,traits,Distance>& y); 4420b57cec5SDimitry Andrictemplate <class T, class charT, class traits, class Distance> 4430b57cec5SDimitry Andricbool operator!=(const istream_iterator<T,charT,traits,Distance>& x, 4440b57cec5SDimitry Andric const istream_iterator<T,charT,traits,Distance>& y); 4450b57cec5SDimitry Andric 4460b57cec5SDimitry Andrictemplate <class T, class charT = char, class traits = char_traits<charT> > 4470b57cec5SDimitry Andricclass ostream_iterator 448*5f7ddb14SDimitry Andric : public iterator<output_iterator_tag, void, void, void, void> // until C++17 4490b57cec5SDimitry Andric{ 4500b57cec5SDimitry Andricpublic: 451*5f7ddb14SDimitry Andric typedef output_iterator_tag iterator_category; 452*5f7ddb14SDimitry Andric typedef void value_type; 453*5f7ddb14SDimitry Andric typedef void difference_type; // until C++20 454*5f7ddb14SDimitry Andric typedef ptrdiff_t difference_type; // since C++20 455*5f7ddb14SDimitry Andric typedef void pointer; 456*5f7ddb14SDimitry Andric typedef void reference; 457*5f7ddb14SDimitry Andric 4580b57cec5SDimitry Andric typedef charT char_type; 4590b57cec5SDimitry Andric typedef traits traits_type; 4600b57cec5SDimitry Andric typedef basic_ostream<charT,traits> ostream_type; 4610b57cec5SDimitry Andric 4620b57cec5SDimitry Andric ostream_iterator(ostream_type& s); 4630b57cec5SDimitry Andric ostream_iterator(ostream_type& s, const charT* delimiter); 4640b57cec5SDimitry Andric ostream_iterator(const ostream_iterator& x); 4650b57cec5SDimitry Andric ~ostream_iterator(); 4660b57cec5SDimitry Andric ostream_iterator& operator=(const T& value); 4670b57cec5SDimitry Andric 4680b57cec5SDimitry Andric ostream_iterator& operator*(); 4690b57cec5SDimitry Andric ostream_iterator& operator++(); 4700b57cec5SDimitry Andric ostream_iterator& operator++(int); 4710b57cec5SDimitry Andric}; 4720b57cec5SDimitry Andric 4730b57cec5SDimitry Andrictemplate<class charT, class traits = char_traits<charT> > 4740b57cec5SDimitry Andricclass istreambuf_iterator 475*5f7ddb14SDimitry Andric : public iterator<input_iterator_tag, charT, traits::off_type, unspecified, charT> // until C++17 4760b57cec5SDimitry Andric{ 4770b57cec5SDimitry Andricpublic: 478*5f7ddb14SDimitry Andric typedef input_iterator_tag iterator_category; 479*5f7ddb14SDimitry Andric typedef charT value_type; 480*5f7ddb14SDimitry Andric typedef traits::off_type difference_type; 481*5f7ddb14SDimitry Andric typedef unspecified pointer; 482*5f7ddb14SDimitry Andric typedef charT reference; 483*5f7ddb14SDimitry Andric 4840b57cec5SDimitry Andric typedef charT char_type; 4850b57cec5SDimitry Andric typedef traits traits_type; 486*5f7ddb14SDimitry Andric typedef traits::int_type int_type; 4870b57cec5SDimitry Andric typedef basic_streambuf<charT, traits> streambuf_type; 4880b57cec5SDimitry Andric typedef basic_istream<charT, traits> istream_type; 4890b57cec5SDimitry Andric 4900b57cec5SDimitry Andric istreambuf_iterator() noexcept; 4910b57cec5SDimitry Andric istreambuf_iterator(istream_type& s) noexcept; 4920b57cec5SDimitry Andric istreambuf_iterator(streambuf_type* s) noexcept; 4930b57cec5SDimitry Andric istreambuf_iterator(a-private-type) noexcept; 4940b57cec5SDimitry Andric 4950b57cec5SDimitry Andric charT operator*() const; 4960b57cec5SDimitry Andric pointer operator->() const; 4970b57cec5SDimitry Andric istreambuf_iterator& operator++(); 4980b57cec5SDimitry Andric a-private-type operator++(int); 4990b57cec5SDimitry Andric 5000b57cec5SDimitry Andric bool equal(const istreambuf_iterator& b) const; 5010b57cec5SDimitry Andric}; 5020b57cec5SDimitry Andric 5030b57cec5SDimitry Andrictemplate <class charT, class traits> 5040b57cec5SDimitry Andricbool operator==(const istreambuf_iterator<charT,traits>& a, 5050b57cec5SDimitry Andric const istreambuf_iterator<charT,traits>& b); 5060b57cec5SDimitry Andrictemplate <class charT, class traits> 5070b57cec5SDimitry Andricbool operator!=(const istreambuf_iterator<charT,traits>& a, 5080b57cec5SDimitry Andric const istreambuf_iterator<charT,traits>& b); 5090b57cec5SDimitry Andric 5100b57cec5SDimitry Andrictemplate <class charT, class traits = char_traits<charT> > 5110b57cec5SDimitry Andricclass ostreambuf_iterator 512*5f7ddb14SDimitry Andric : public iterator<output_iterator_tag, void, void, void, void> // until C++17 5130b57cec5SDimitry Andric{ 5140b57cec5SDimitry Andricpublic: 515*5f7ddb14SDimitry Andric typedef output_iterator_tag iterator_category; 516*5f7ddb14SDimitry Andric typedef void value_type; 517*5f7ddb14SDimitry Andric typedef void difference_type; // until C++20 518*5f7ddb14SDimitry Andric typedef ptrdiff_t difference_type; // since C++20 519*5f7ddb14SDimitry Andric typedef void pointer; 520*5f7ddb14SDimitry Andric typedef void reference; 521*5f7ddb14SDimitry Andric 5220b57cec5SDimitry Andric typedef charT char_type; 5230b57cec5SDimitry Andric typedef traits traits_type; 5240b57cec5SDimitry Andric typedef basic_streambuf<charT, traits> streambuf_type; 5250b57cec5SDimitry Andric typedef basic_ostream<charT, traits> ostream_type; 5260b57cec5SDimitry Andric 5270b57cec5SDimitry Andric ostreambuf_iterator(ostream_type& s) noexcept; 5280b57cec5SDimitry Andric ostreambuf_iterator(streambuf_type* s) noexcept; 5290b57cec5SDimitry Andric ostreambuf_iterator& operator=(charT c); 5300b57cec5SDimitry Andric ostreambuf_iterator& operator*(); 5310b57cec5SDimitry Andric ostreambuf_iterator& operator++(); 5320b57cec5SDimitry Andric ostreambuf_iterator& operator++(int); 5330b57cec5SDimitry Andric bool failed() const noexcept; 5340b57cec5SDimitry Andric}; 5350b57cec5SDimitry Andric 5360b57cec5SDimitry Andrictemplate <class C> constexpr auto begin(C& c) -> decltype(c.begin()); 5370b57cec5SDimitry Andrictemplate <class C> constexpr auto begin(const C& c) -> decltype(c.begin()); 5380b57cec5SDimitry Andrictemplate <class C> constexpr auto end(C& c) -> decltype(c.end()); 5390b57cec5SDimitry Andrictemplate <class C> constexpr auto end(const C& c) -> decltype(c.end()); 5400b57cec5SDimitry Andrictemplate <class T, size_t N> constexpr T* begin(T (&array)[N]); 5410b57cec5SDimitry Andrictemplate <class T, size_t N> constexpr T* end(T (&array)[N]); 5420b57cec5SDimitry Andric 5430b57cec5SDimitry Andrictemplate <class C> auto constexpr cbegin(const C& c) -> decltype(std::begin(c)); // C++14 5440b57cec5SDimitry Andrictemplate <class C> auto constexpr cend(const C& c) -> decltype(std::end(c)); // C++14 5450b57cec5SDimitry Andrictemplate <class C> auto constexpr rbegin(C& c) -> decltype(c.rbegin()); // C++14 5460b57cec5SDimitry Andrictemplate <class C> auto constexpr rbegin(const C& c) -> decltype(c.rbegin()); // C++14 5470b57cec5SDimitry Andrictemplate <class C> auto constexpr rend(C& c) -> decltype(c.rend()); // C++14 5480b57cec5SDimitry Andrictemplate <class C> constexpr auto rend(const C& c) -> decltype(c.rend()); // C++14 5490b57cec5SDimitry Andrictemplate <class E> reverse_iterator<const E*> constexpr rbegin(initializer_list<E> il); // C++14 5500b57cec5SDimitry Andrictemplate <class E> reverse_iterator<const E*> constexpr rend(initializer_list<E> il); // C++14 5510b57cec5SDimitry Andrictemplate <class T, size_t N> reverse_iterator<T*> constexpr rbegin(T (&array)[N]); // C++14 5520b57cec5SDimitry Andrictemplate <class T, size_t N> reverse_iterator<T*> constexpr rend(T (&array)[N]); // C++14 5530b57cec5SDimitry Andrictemplate <class C> constexpr auto crbegin(const C& c) -> decltype(std::rbegin(c)); // C++14 5540b57cec5SDimitry Andrictemplate <class C> constexpr auto crend(const C& c) -> decltype(std::rend(c)); // C++14 5550b57cec5SDimitry Andric 5560b57cec5SDimitry Andric// 24.8, container access: 5570b57cec5SDimitry Andrictemplate <class C> constexpr auto size(const C& c) -> decltype(c.size()); // C++17 5580b57cec5SDimitry Andrictemplate <class T, size_t N> constexpr size_t size(const T (&array)[N]) noexcept; // C++17 5590b57cec5SDimitry Andric 5600b57cec5SDimitry Andrictemplate <class C> constexpr auto ssize(const C& c) 5610b57cec5SDimitry Andric -> common_type_t<ptrdiff_t, make_signed_t<decltype(c.size())>>; // C++20 5620b57cec5SDimitry Andrictemplate <class T, ptrdiff_t> constexpr ptrdiff_t ssize(const T (&array)[N]) noexcept; // C++20 5630b57cec5SDimitry Andric 5640b57cec5SDimitry Andrictemplate <class C> constexpr auto empty(const C& c) -> decltype(c.empty()); // C++17 5650b57cec5SDimitry Andrictemplate <class T, size_t N> constexpr bool empty(const T (&array)[N]) noexcept; // C++17 5660b57cec5SDimitry Andrictemplate <class E> constexpr bool empty(initializer_list<E> il) noexcept; // C++17 5670b57cec5SDimitry Andrictemplate <class C> constexpr auto data(C& c) -> decltype(c.data()); // C++17 5680b57cec5SDimitry Andrictemplate <class C> constexpr auto data(const C& c) -> decltype(c.data()); // C++17 5690b57cec5SDimitry Andrictemplate <class T, size_t N> constexpr T* data(T (&array)[N]) noexcept; // C++17 5700b57cec5SDimitry Andrictemplate <class E> constexpr const E* data(initializer_list<E> il) noexcept; // C++17 5710b57cec5SDimitry Andric 5720b57cec5SDimitry Andric} // std 5730b57cec5SDimitry Andric 5740b57cec5SDimitry Andric*/ 5750b57cec5SDimitry Andric 5760b57cec5SDimitry Andric#include <__config> 577*5f7ddb14SDimitry Andric#include <__debug> 5780b57cec5SDimitry Andric#include <__functional_base> 579*5f7ddb14SDimitry Andric#include <__iterator/access.h> 580*5f7ddb14SDimitry Andric#include <__iterator/advance.h> 581*5f7ddb14SDimitry Andric#include <__iterator/back_insert_iterator.h> 582*5f7ddb14SDimitry Andric#include <__iterator/common_iterator.h> 583*5f7ddb14SDimitry Andric#include <__iterator/concepts.h> 584*5f7ddb14SDimitry Andric#include <__iterator/counted_iterator.h> 585*5f7ddb14SDimitry Andric#include <__iterator/data.h> 586*5f7ddb14SDimitry Andric#include <__iterator/default_sentinel.h> 587*5f7ddb14SDimitry Andric#include <__iterator/distance.h> 588*5f7ddb14SDimitry Andric#include <__iterator/empty.h> 589*5f7ddb14SDimitry Andric#include <__iterator/erase_if_container.h> 590*5f7ddb14SDimitry Andric#include <__iterator/front_insert_iterator.h> 591*5f7ddb14SDimitry Andric#include <__iterator/incrementable_traits.h> 592*5f7ddb14SDimitry Andric#include <__iterator/insert_iterator.h> 593*5f7ddb14SDimitry Andric#include <__iterator/istreambuf_iterator.h> 594*5f7ddb14SDimitry Andric#include <__iterator/istream_iterator.h> 595*5f7ddb14SDimitry Andric#include <__iterator/iterator.h> 596*5f7ddb14SDimitry Andric#include <__iterator/iterator_traits.h> 597*5f7ddb14SDimitry Andric#include <__iterator/iter_move.h> 598*5f7ddb14SDimitry Andric#include <__iterator/iter_swap.h> 599*5f7ddb14SDimitry Andric#include <__iterator/move_iterator.h> 600*5f7ddb14SDimitry Andric#include <__iterator/next.h> 601*5f7ddb14SDimitry Andric#include <__iterator/ostreambuf_iterator.h> 602*5f7ddb14SDimitry Andric#include <__iterator/ostream_iterator.h> 603*5f7ddb14SDimitry Andric#include <__iterator/prev.h> 604*5f7ddb14SDimitry Andric#include <__iterator/projected.h> 605*5f7ddb14SDimitry Andric#include <__iterator/readable_traits.h> 606*5f7ddb14SDimitry Andric#include <__iterator/reverse_access.h> 607*5f7ddb14SDimitry Andric#include <__iterator/reverse_iterator.h> 608*5f7ddb14SDimitry Andric#include <__iterator/size.h> 609*5f7ddb14SDimitry Andric#include <__iterator/wrap_iter.h> 610*5f7ddb14SDimitry Andric#include <__memory/addressof.h> 611*5f7ddb14SDimitry Andric#include <__memory/pointer_traits.h> 612*5f7ddb14SDimitry Andric#include <__utility/forward.h> 613*5f7ddb14SDimitry Andric#include <compare> 614*5f7ddb14SDimitry Andric#include <concepts> // Mandated by the Standard. 6150b57cec5SDimitry Andric#include <cstddef> 6160b57cec5SDimitry Andric#include <initializer_list> 617*5f7ddb14SDimitry Andric#include <type_traits> 6180b57cec5SDimitry Andric#include <version> 6190b57cec5SDimitry Andric 6200b57cec5SDimitry Andric#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 6210b57cec5SDimitry Andric#pragma GCC system_header 6220b57cec5SDimitry Andric#endif 6230b57cec5SDimitry Andric 6240b57cec5SDimitry Andric#endif // _LIBCPP_ITERATOR 625