10b57cec5SDimitry Andric// -*- C++ -*- 2*349cc55cSDimitry Andric//===----------------------------------------------------------------------===// 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 16fe6060f1SDimitry Andric#include <concepts> 17fe6060f1SDimitry Andric 180b57cec5SDimitry Andricnamespace std 190b57cec5SDimitry Andric{ 20fe6060f1SDimitry Andrictemplate<class> struct incrementable_traits; // since C++20 21fe6060f1SDimitry Andrictemplate<class T> 22fe6060f1SDimitry Andric using iter_difference_t = see below; // since C++20 23fe6060f1SDimitry Andric 24fe6060f1SDimitry Andrictemplate<class> struct indirectly_readable_traits; // since C++20 25fe6060f1SDimitry Andrictemplate<class T> 26fe6060f1SDimitry Andric using iter_value_t = see below; // since C++20 270b57cec5SDimitry Andric 280b57cec5SDimitry Andrictemplate<class Iterator> 29fe6060f1SDimitry Andricstruct iterator_traits; 300b57cec5SDimitry Andric 310b57cec5SDimitry Andrictemplate<class T> 32fe6060f1SDimitry Andric requires is_object_v<T> // since C++20 33fe6060f1SDimitry Andricstruct iterator_traits<T*>; 34fe6060f1SDimitry Andric 35fe6060f1SDimitry Andrictemplate<dereferenceable T> 36fe6060f1SDimitry Andric using iter_reference_t = decltype(*declval<T&>()); 37fe6060f1SDimitry Andric 38fe6060f1SDimitry Andricnamespace ranges::inline unspecified { 39fe6060f1SDimitry Andric inline constexpr unspecified iter_move = unspecified; // since C++20, nodiscard as an extension 40fe6060f1SDimitry Andric}} 41fe6060f1SDimitry Andric 42fe6060f1SDimitry Andrictemplate<dereferenceable T> 43fe6060f1SDimitry Andric requires ... 44fe6060f1SDimitry Andricusing iter_rvalue_reference_t = decltype(ranges::iter_move(declval<T&>())); // since C++20 45fe6060f1SDimitry Andric 46fe6060f1SDimitry Andric// [iterator.concepts], iterator concepts 47fe6060f1SDimitry Andric// [iterator.concept.readable], concept indirectly_readable 48fe6060f1SDimitry Andrictemplate<class In> 49fe6060f1SDimitry Andric concept indirectly_readable = see below; // since C++20 50fe6060f1SDimitry Andric 51fe6060f1SDimitry Andrictemplate<indirectly_readable T> 52fe6060f1SDimitry Andric using iter_common_reference_t = 53fe6060f1SDimitry Andric common_reference_t<iter_reference_t<T>, iter_value_t<T>&>; // since C++20 54fe6060f1SDimitry Andric 55fe6060f1SDimitry Andric// [iterator.concept.writable], concept indirectly_writable 56fe6060f1SDimitry Andrictemplate<class Out, class T> 57fe6060f1SDimitry Andric concept indirectly_writable = see below; // since C++20 58fe6060f1SDimitry Andric 59fe6060f1SDimitry Andric// [iterator.concept.winc], concept weakly_incrementable 60fe6060f1SDimitry Andrictemplate<class I> 61fe6060f1SDimitry Andric concept weakly_incrementable = see below; // since C++20 62fe6060f1SDimitry Andric 63fe6060f1SDimitry Andric// [iterator.concept.inc], concept incrementable 64fe6060f1SDimitry Andrictemplate<class I> 65fe6060f1SDimitry Andric concept incrementable = see below; // since C++20 66fe6060f1SDimitry Andric 67fe6060f1SDimitry Andric// [iterator.concept.iterator], concept input_or_output_iterator 68fe6060f1SDimitry Andric template<class I> 69fe6060f1SDimitry Andric concept input_or_output_iterator = see below; // since C++20 70fe6060f1SDimitry Andric 71fe6060f1SDimitry Andric// [iterator.concept.sentinel], concept sentinel_for 72fe6060f1SDimitry Andrictemplate<class S, class I> 73fe6060f1SDimitry Andric concept sentinel_for = see below; // since C++20 74fe6060f1SDimitry Andric 75fe6060f1SDimitry Andric// [iterator.concept.sizedsentinel], concept sized_sentinel_for 76fe6060f1SDimitry Andrictemplate<class S, class I> 77fe6060f1SDimitry Andric inline constexpr bool disable_sized_sentinel_for = false; 78fe6060f1SDimitry Andric 79fe6060f1SDimitry Andrictemplate<class S, class I> 80fe6060f1SDimitry Andric concept sized_sentinel_for = see below; 81fe6060f1SDimitry Andric 82fe6060f1SDimitry Andric// [iterator.concept.input], concept input_iterator 83fe6060f1SDimitry Andrictemplate<class I> 84fe6060f1SDimitry Andric concept input_iterator = see below; // since C++20 85fe6060f1SDimitry Andric 86fe6060f1SDimitry Andric// [iterator.concept.output], concept output_iterator 87fe6060f1SDimitry Andrictemplate<class I, class T> 88fe6060f1SDimitry Andric concept output_iterator = see below; // since C++20 89fe6060f1SDimitry Andric 90fe6060f1SDimitry Andric// [iterator.concept.forward], concept forward_iterator 91fe6060f1SDimitry Andrictemplate<class I> 92fe6060f1SDimitry Andric concept forward_iterator = see below; // since C++20 93fe6060f1SDimitry Andric 94fe6060f1SDimitry Andric// [iterator.concept.bidir], concept bidirectional_iterator 95fe6060f1SDimitry Andrictemplate<class I> 96fe6060f1SDimitry Andric concept bidirectional_iterator = see below; // since C++20 97fe6060f1SDimitry Andric 98fe6060f1SDimitry Andric// [iterator.concept.random.access], concept random_access_iterator 99fe6060f1SDimitry Andrictemplate<class I> 100fe6060f1SDimitry Andric concept random_access_iterator = see below; // since C++20 101fe6060f1SDimitry Andric 102fe6060f1SDimitry Andric// [indirectcallable] 103fe6060f1SDimitry Andric// [indirectcallable.indirectinvocable] 104fe6060f1SDimitry Andrictemplate<class F, class I> 105fe6060f1SDimitry Andric concept indirectly_unary_invocable = see below; // since C++20 106fe6060f1SDimitry Andric 107fe6060f1SDimitry Andrictemplate<class F, class I> 108fe6060f1SDimitry Andric concept indirectly_regular_unary_invocable = see below; // since C++20 109fe6060f1SDimitry Andric 110fe6060f1SDimitry Andrictemplate<class F, class I> 111fe6060f1SDimitry Andric concept indirect_unary_predicate = see below; // since C++20 112fe6060f1SDimitry Andric 113fe6060f1SDimitry Andrictemplate<class F, class I1, class I2> 114fe6060f1SDimitry Andric concept indirect_binary_predicate = see below; // since C++20 115fe6060f1SDimitry Andric 116fe6060f1SDimitry Andrictemplate<class F, class I1, class I2 = I1> 117fe6060f1SDimitry Andric concept indirect_equivalence_relation = see below; // since C++20 118fe6060f1SDimitry Andric 119fe6060f1SDimitry Andrictemplate<class F, class I1, class I2 = I1> 120fe6060f1SDimitry Andric concept indirect_strict_weak_order = see below; // since C++20 121fe6060f1SDimitry Andric 122fe6060f1SDimitry Andrictemplate<class F, class... Is> 123fe6060f1SDimitry Andric using indirect_result_t = see below; // since C++20 124fe6060f1SDimitry Andric 125fe6060f1SDimitry Andric// [projected], projected 126fe6060f1SDimitry Andrictemplate<indirectly_readable I, indirectly_regular_unary_invocable<I> Proj> 127fe6060f1SDimitry Andric struct projected; // since C++20 128fe6060f1SDimitry Andric 129fe6060f1SDimitry Andrictemplate<weakly_incrementable I, indirectly_regular_unary_invocable<I> Proj> 130fe6060f1SDimitry Andric struct incrementable_traits<projected<I, Proj>>; // since C++20 131fe6060f1SDimitry Andric 132fe6060f1SDimitry Andric// [alg.req.ind.move], concept indirectly_movable 133fe6060f1SDimitry Andrictemplate<class In, class Out> 134fe6060f1SDimitry Andric concept indirectly_movable = see below; // since C++20 135fe6060f1SDimitry Andric 136fe6060f1SDimitry Andrictemplate<class In, class Out> 137fe6060f1SDimitry Andric concept indirectly_movable_storable = see below; // since C++20 138fe6060f1SDimitry Andric 139fe6060f1SDimitry Andric// [alg.req.ind.swap], concept indirectly_swappable 140fe6060f1SDimitry Andrictemplate<class I1, class I2 = I1> 141fe6060f1SDimitry Andric concept indirectly_swappable = see below; // since C++20 142fe6060f1SDimitry Andric 143fe6060f1SDimitry Andrictemplate<input_or_output_iterator I, sentinel_for<I> S> 144fe6060f1SDimitry Andric requires (!same_as<I, S> && copyable<I>) 145fe6060f1SDimitry 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&> 149fe6060f1SDimitry 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 180fe6060f1SDimitry Andric// [range.iter.ops], range iterator operations 181fe6060f1SDimitry Andricnamespace ranges { 182fe6060f1SDimitry Andric // [range.iter.op.advance], ranges::advance 183fe6060f1SDimitry Andric template<input_or_output_iterator I> 184fe6060f1SDimitry Andric constexpr void advance(I& i, iter_difference_t<I> n); // since C++20 185fe6060f1SDimitry Andric template<input_or_output_iterator I, sentinel_for<I> S> 186fe6060f1SDimitry Andric constexpr void advance(I& i, S bound); // since C++20 187fe6060f1SDimitry Andric template<input_or_output_iterator I, sentinel_for<I> S> 188fe6060f1SDimitry Andric constexpr iter_difference_t<I> advance(I& i, iter_difference_t<I> n, S bound); // since C++20 189fe6060f1SDimitry Andric} 190fe6060f1SDimitry Andric 1910b57cec5SDimitry Andrictemplate <class Iterator> 1920b57cec5SDimitry Andricclass reverse_iterator 193fe6060f1SDimitry 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 264fe6060f1SDimitry 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; 271fe6060f1SDimitry Andric typedef void difference_type; // until C++20 272fe6060f1SDimitry Andric typedef ptrdiff_t difference_type; // since C++20 2730b57cec5SDimitry Andric typedef void reference; 2740b57cec5SDimitry Andric typedef void pointer; 2750b57cec5SDimitry Andric 276fe6060f1SDimitry Andric explicit back_insert_iterator(Container& x); // constexpr in C++20 277fe6060f1SDimitry Andric back_insert_iterator& operator=(const typename Container::value_type& value); // constexpr in C++20 278fe6060f1SDimitry Andric back_insert_iterator& operator*(); // constexpr in C++20 279fe6060f1SDimitry Andric back_insert_iterator& operator++(); // constexpr in C++20 280fe6060f1SDimitry Andric back_insert_iterator operator++(int); // constexpr in C++20 2810b57cec5SDimitry Andric}; 2820b57cec5SDimitry Andric 283fe6060f1SDimitry 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 287fe6060f1SDimitry 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; 294fe6060f1SDimitry Andric typedef void difference_type; // until C++20 295fe6060f1SDimitry Andric typedef ptrdiff_t difference_type; // since C++20 2960b57cec5SDimitry Andric typedef void reference; 2970b57cec5SDimitry Andric typedef void pointer; 2980b57cec5SDimitry Andric 299fe6060f1SDimitry Andric explicit front_insert_iterator(Container& x); // constexpr in C++20 300fe6060f1SDimitry Andric front_insert_iterator& operator=(const typename Container::value_type& value); // constexpr in C++20 301fe6060f1SDimitry Andric front_insert_iterator& operator*(); // constexpr in C++20 302fe6060f1SDimitry Andric front_insert_iterator& operator++(); // constexpr in C++20 303fe6060f1SDimitry Andric front_insert_iterator operator++(int); // constexpr in C++20 3040b57cec5SDimitry Andric}; 3050b57cec5SDimitry Andric 306fe6060f1SDimitry 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 310fe6060f1SDimitry 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; 318fe6060f1SDimitry Andric typedef void difference_type; // until C++20 319fe6060f1SDimitry Andric typedef ptrdiff_t difference_type; // since C++20 3200b57cec5SDimitry Andric typedef void reference; 3210b57cec5SDimitry Andric typedef void pointer; 3220b57cec5SDimitry Andric 323fe6060f1SDimitry Andric insert_iterator(Container& x, typename Container::iterator i); // constexpr in C++20 324fe6060f1SDimitry Andric insert_iterator& operator=(const typename Container::value_type& value); // constexpr in C++20 325fe6060f1SDimitry Andric insert_iterator& operator*(); // constexpr in C++20 326fe6060f1SDimitry Andric insert_iterator& operator++(); // constexpr in C++20 327fe6060f1SDimitry Andric insert_iterator& operator++(int); // constexpr in C++20 3280b57cec5SDimitry Andric}; 3290b57cec5SDimitry Andric 3300b57cec5SDimitry Andrictemplate <class Container, class Iterator> 331fe6060f1SDimitry 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 402fe6060f1SDimitry Andric// [default.sentinel], default sentinel 403fe6060f1SDimitry Andricstruct default_sentinel_t; 404fe6060f1SDimitry Andricinline constexpr default_sentinel_t default_sentinel{}; 405fe6060f1SDimitry Andric 406fe6060f1SDimitry Andric// [iterators.counted], counted iterators 407fe6060f1SDimitry Andrictemplate<input_or_output_iterator I> class counted_iterator; 408fe6060f1SDimitry Andric 409fe6060f1SDimitry Andrictemplate<input_iterator I> 410fe6060f1SDimitry Andric requires see below 411fe6060f1SDimitry Andric struct iterator_traits<counted_iterator<I>>; 4120b57cec5SDimitry Andric 413*349cc55cSDimitry Andric// [unreachable.sentinel], unreachable sentinel 414*349cc55cSDimitry Andricstruct unreachable_sentinel_t; 415*349cc55cSDimitry Andricinline constexpr unreachable_sentinel_t unreachable_sentinel{}; 416*349cc55cSDimitry Andric 4170b57cec5SDimitry Andrictemplate <class T, class charT = char, class traits = char_traits<charT>, class Distance = ptrdiff_t> 4180b57cec5SDimitry Andricclass istream_iterator 419fe6060f1SDimitry Andric : public iterator<input_iterator_tag, T, Distance, const T*, const T&> // until C++17 4200b57cec5SDimitry Andric{ 4210b57cec5SDimitry Andricpublic: 422fe6060f1SDimitry Andric typedef input_iterator_tag iterator_category; 423fe6060f1SDimitry Andric typedef T value_type; 424fe6060f1SDimitry Andric typedef Distance difference_type; 425fe6060f1SDimitry Andric typedef const T* pointer; 426fe6060f1SDimitry Andric typedef const T& reference; 427fe6060f1SDimitry Andric 4280b57cec5SDimitry Andric typedef charT char_type; 4290b57cec5SDimitry Andric typedef traits traits_type; 4300b57cec5SDimitry Andric typedef basic_istream<charT, traits> istream_type; 4310b57cec5SDimitry Andric 4320b57cec5SDimitry Andric constexpr istream_iterator(); 4330b57cec5SDimitry Andric istream_iterator(istream_type& s); 4340b57cec5SDimitry Andric istream_iterator(const istream_iterator& x); 4350b57cec5SDimitry Andric ~istream_iterator(); 4360b57cec5SDimitry Andric 4370b57cec5SDimitry Andric const T& operator*() const; 4380b57cec5SDimitry Andric const T* operator->() const; 4390b57cec5SDimitry Andric istream_iterator& operator++(); 4400b57cec5SDimitry Andric istream_iterator operator++(int); 4410b57cec5SDimitry Andric}; 4420b57cec5SDimitry Andric 4430b57cec5SDimitry Andrictemplate <class T, class charT, class traits, class Distance> 4440b57cec5SDimitry Andricbool operator==(const istream_iterator<T,charT,traits,Distance>& x, 4450b57cec5SDimitry Andric const istream_iterator<T,charT,traits,Distance>& y); 4460b57cec5SDimitry Andrictemplate <class T, class charT, class traits, class Distance> 4470b57cec5SDimitry Andricbool operator!=(const istream_iterator<T,charT,traits,Distance>& x, 4480b57cec5SDimitry Andric const istream_iterator<T,charT,traits,Distance>& y); 4490b57cec5SDimitry Andric 4500b57cec5SDimitry Andrictemplate <class T, class charT = char, class traits = char_traits<charT> > 4510b57cec5SDimitry Andricclass ostream_iterator 452fe6060f1SDimitry Andric : public iterator<output_iterator_tag, void, void, void, void> // until C++17 4530b57cec5SDimitry Andric{ 4540b57cec5SDimitry Andricpublic: 455fe6060f1SDimitry Andric typedef output_iterator_tag iterator_category; 456fe6060f1SDimitry Andric typedef void value_type; 457fe6060f1SDimitry Andric typedef void difference_type; // until C++20 458fe6060f1SDimitry Andric typedef ptrdiff_t difference_type; // since C++20 459fe6060f1SDimitry Andric typedef void pointer; 460fe6060f1SDimitry Andric typedef void reference; 461fe6060f1SDimitry Andric 4620b57cec5SDimitry Andric typedef charT char_type; 4630b57cec5SDimitry Andric typedef traits traits_type; 4640b57cec5SDimitry Andric typedef basic_ostream<charT,traits> ostream_type; 4650b57cec5SDimitry Andric 4660b57cec5SDimitry Andric ostream_iterator(ostream_type& s); 4670b57cec5SDimitry Andric ostream_iterator(ostream_type& s, const charT* delimiter); 4680b57cec5SDimitry Andric ostream_iterator(const ostream_iterator& x); 4690b57cec5SDimitry Andric ~ostream_iterator(); 4700b57cec5SDimitry Andric ostream_iterator& operator=(const T& value); 4710b57cec5SDimitry Andric 4720b57cec5SDimitry Andric ostream_iterator& operator*(); 4730b57cec5SDimitry Andric ostream_iterator& operator++(); 4740b57cec5SDimitry Andric ostream_iterator& operator++(int); 4750b57cec5SDimitry Andric}; 4760b57cec5SDimitry Andric 4770b57cec5SDimitry Andrictemplate<class charT, class traits = char_traits<charT> > 4780b57cec5SDimitry Andricclass istreambuf_iterator 479fe6060f1SDimitry Andric : public iterator<input_iterator_tag, charT, traits::off_type, unspecified, charT> // until C++17 4800b57cec5SDimitry Andric{ 4810b57cec5SDimitry Andricpublic: 482fe6060f1SDimitry Andric typedef input_iterator_tag iterator_category; 483fe6060f1SDimitry Andric typedef charT value_type; 484fe6060f1SDimitry Andric typedef traits::off_type difference_type; 485fe6060f1SDimitry Andric typedef unspecified pointer; 486fe6060f1SDimitry Andric typedef charT reference; 487fe6060f1SDimitry Andric 4880b57cec5SDimitry Andric typedef charT char_type; 4890b57cec5SDimitry Andric typedef traits traits_type; 490fe6060f1SDimitry Andric typedef traits::int_type int_type; 4910b57cec5SDimitry Andric typedef basic_streambuf<charT, traits> streambuf_type; 4920b57cec5SDimitry Andric typedef basic_istream<charT, traits> istream_type; 4930b57cec5SDimitry Andric 4940b57cec5SDimitry Andric istreambuf_iterator() noexcept; 4950b57cec5SDimitry Andric istreambuf_iterator(istream_type& s) noexcept; 4960b57cec5SDimitry Andric istreambuf_iterator(streambuf_type* s) noexcept; 4970b57cec5SDimitry Andric istreambuf_iterator(a-private-type) noexcept; 4980b57cec5SDimitry Andric 4990b57cec5SDimitry Andric charT operator*() const; 5000b57cec5SDimitry Andric pointer operator->() const; 5010b57cec5SDimitry Andric istreambuf_iterator& operator++(); 5020b57cec5SDimitry Andric a-private-type operator++(int); 5030b57cec5SDimitry Andric 5040b57cec5SDimitry Andric bool equal(const istreambuf_iterator& b) const; 5050b57cec5SDimitry Andric}; 5060b57cec5SDimitry Andric 5070b57cec5SDimitry Andrictemplate <class charT, class traits> 5080b57cec5SDimitry Andricbool operator==(const istreambuf_iterator<charT,traits>& a, 5090b57cec5SDimitry Andric const istreambuf_iterator<charT,traits>& b); 5100b57cec5SDimitry Andrictemplate <class charT, class traits> 5110b57cec5SDimitry Andricbool operator!=(const istreambuf_iterator<charT,traits>& a, 5120b57cec5SDimitry Andric const istreambuf_iterator<charT,traits>& b); 5130b57cec5SDimitry Andric 5140b57cec5SDimitry Andrictemplate <class charT, class traits = char_traits<charT> > 5150b57cec5SDimitry Andricclass ostreambuf_iterator 516fe6060f1SDimitry Andric : public iterator<output_iterator_tag, void, void, void, void> // until C++17 5170b57cec5SDimitry Andric{ 5180b57cec5SDimitry Andricpublic: 519fe6060f1SDimitry Andric typedef output_iterator_tag iterator_category; 520fe6060f1SDimitry Andric typedef void value_type; 521fe6060f1SDimitry Andric typedef void difference_type; // until C++20 522fe6060f1SDimitry Andric typedef ptrdiff_t difference_type; // since C++20 523fe6060f1SDimitry Andric typedef void pointer; 524fe6060f1SDimitry Andric typedef void reference; 525fe6060f1SDimitry Andric 5260b57cec5SDimitry Andric typedef charT char_type; 5270b57cec5SDimitry Andric typedef traits traits_type; 5280b57cec5SDimitry Andric typedef basic_streambuf<charT, traits> streambuf_type; 5290b57cec5SDimitry Andric typedef basic_ostream<charT, traits> ostream_type; 5300b57cec5SDimitry Andric 5310b57cec5SDimitry Andric ostreambuf_iterator(ostream_type& s) noexcept; 5320b57cec5SDimitry Andric ostreambuf_iterator(streambuf_type* s) noexcept; 5330b57cec5SDimitry Andric ostreambuf_iterator& operator=(charT c); 5340b57cec5SDimitry Andric ostreambuf_iterator& operator*(); 5350b57cec5SDimitry Andric ostreambuf_iterator& operator++(); 5360b57cec5SDimitry Andric ostreambuf_iterator& operator++(int); 5370b57cec5SDimitry Andric bool failed() const noexcept; 5380b57cec5SDimitry Andric}; 5390b57cec5SDimitry Andric 5400b57cec5SDimitry Andrictemplate <class C> constexpr auto begin(C& c) -> decltype(c.begin()); 5410b57cec5SDimitry Andrictemplate <class C> constexpr auto begin(const C& c) -> decltype(c.begin()); 5420b57cec5SDimitry Andrictemplate <class C> constexpr auto end(C& c) -> decltype(c.end()); 5430b57cec5SDimitry Andrictemplate <class C> constexpr auto end(const C& c) -> decltype(c.end()); 5440b57cec5SDimitry Andrictemplate <class T, size_t N> constexpr T* begin(T (&array)[N]); 5450b57cec5SDimitry Andrictemplate <class T, size_t N> constexpr T* end(T (&array)[N]); 5460b57cec5SDimitry Andric 5470b57cec5SDimitry Andrictemplate <class C> auto constexpr cbegin(const C& c) -> decltype(std::begin(c)); // C++14 5480b57cec5SDimitry Andrictemplate <class C> auto constexpr cend(const C& c) -> decltype(std::end(c)); // C++14 5490b57cec5SDimitry Andrictemplate <class C> auto constexpr rbegin(C& c) -> decltype(c.rbegin()); // C++14 5500b57cec5SDimitry Andrictemplate <class C> auto constexpr rbegin(const C& c) -> decltype(c.rbegin()); // C++14 5510b57cec5SDimitry Andrictemplate <class C> auto constexpr rend(C& c) -> decltype(c.rend()); // C++14 5520b57cec5SDimitry Andrictemplate <class C> constexpr auto rend(const C& c) -> decltype(c.rend()); // C++14 5530b57cec5SDimitry Andrictemplate <class E> reverse_iterator<const E*> constexpr rbegin(initializer_list<E> il); // C++14 5540b57cec5SDimitry Andrictemplate <class E> reverse_iterator<const E*> constexpr rend(initializer_list<E> il); // C++14 5550b57cec5SDimitry Andrictemplate <class T, size_t N> reverse_iterator<T*> constexpr rbegin(T (&array)[N]); // C++14 5560b57cec5SDimitry Andrictemplate <class T, size_t N> reverse_iterator<T*> constexpr rend(T (&array)[N]); // C++14 5570b57cec5SDimitry Andrictemplate <class C> constexpr auto crbegin(const C& c) -> decltype(std::rbegin(c)); // C++14 5580b57cec5SDimitry Andrictemplate <class C> constexpr auto crend(const C& c) -> decltype(std::rend(c)); // C++14 5590b57cec5SDimitry Andric 5600b57cec5SDimitry Andric// 24.8, container access: 5610b57cec5SDimitry Andrictemplate <class C> constexpr auto size(const C& c) -> decltype(c.size()); // C++17 5620b57cec5SDimitry Andrictemplate <class T, size_t N> constexpr size_t size(const T (&array)[N]) noexcept; // C++17 5630b57cec5SDimitry Andric 5640b57cec5SDimitry Andrictemplate <class C> constexpr auto ssize(const C& c) 5650b57cec5SDimitry Andric -> common_type_t<ptrdiff_t, make_signed_t<decltype(c.size())>>; // C++20 5660b57cec5SDimitry Andrictemplate <class T, ptrdiff_t> constexpr ptrdiff_t ssize(const T (&array)[N]) noexcept; // C++20 5670b57cec5SDimitry Andric 5680b57cec5SDimitry Andrictemplate <class C> constexpr auto empty(const C& c) -> decltype(c.empty()); // C++17 5690b57cec5SDimitry Andrictemplate <class T, size_t N> constexpr bool empty(const T (&array)[N]) noexcept; // C++17 5700b57cec5SDimitry Andrictemplate <class E> constexpr bool empty(initializer_list<E> il) noexcept; // C++17 5710b57cec5SDimitry Andrictemplate <class C> constexpr auto data(C& c) -> decltype(c.data()); // C++17 5720b57cec5SDimitry Andrictemplate <class C> constexpr auto data(const C& c) -> decltype(c.data()); // C++17 5730b57cec5SDimitry Andrictemplate <class T, size_t N> constexpr T* data(T (&array)[N]) noexcept; // C++17 5740b57cec5SDimitry Andrictemplate <class E> constexpr const E* data(initializer_list<E> il) noexcept; // C++17 5750b57cec5SDimitry Andric 5760b57cec5SDimitry Andric} // std 5770b57cec5SDimitry Andric 5780b57cec5SDimitry Andric*/ 5790b57cec5SDimitry Andric 5800b57cec5SDimitry Andric#include <__config> 581fe6060f1SDimitry Andric#include <__debug> 5820b57cec5SDimitry Andric#include <__functional_base> 583fe6060f1SDimitry Andric#include <__iterator/access.h> 584fe6060f1SDimitry Andric#include <__iterator/advance.h> 585fe6060f1SDimitry Andric#include <__iterator/back_insert_iterator.h> 586fe6060f1SDimitry Andric#include <__iterator/common_iterator.h> 587fe6060f1SDimitry Andric#include <__iterator/concepts.h> 588fe6060f1SDimitry Andric#include <__iterator/counted_iterator.h> 589fe6060f1SDimitry Andric#include <__iterator/data.h> 590fe6060f1SDimitry Andric#include <__iterator/default_sentinel.h> 591fe6060f1SDimitry Andric#include <__iterator/distance.h> 592fe6060f1SDimitry Andric#include <__iterator/empty.h> 593fe6060f1SDimitry Andric#include <__iterator/erase_if_container.h> 594fe6060f1SDimitry Andric#include <__iterator/front_insert_iterator.h> 595fe6060f1SDimitry Andric#include <__iterator/incrementable_traits.h> 596fe6060f1SDimitry Andric#include <__iterator/insert_iterator.h> 597fe6060f1SDimitry Andric#include <__iterator/istreambuf_iterator.h> 598fe6060f1SDimitry Andric#include <__iterator/istream_iterator.h> 599fe6060f1SDimitry Andric#include <__iterator/iterator.h> 600fe6060f1SDimitry Andric#include <__iterator/iterator_traits.h> 601fe6060f1SDimitry Andric#include <__iterator/iter_move.h> 602fe6060f1SDimitry Andric#include <__iterator/iter_swap.h> 603fe6060f1SDimitry Andric#include <__iterator/move_iterator.h> 604fe6060f1SDimitry Andric#include <__iterator/next.h> 605fe6060f1SDimitry Andric#include <__iterator/ostreambuf_iterator.h> 606fe6060f1SDimitry Andric#include <__iterator/ostream_iterator.h> 607fe6060f1SDimitry Andric#include <__iterator/prev.h> 608fe6060f1SDimitry Andric#include <__iterator/projected.h> 609fe6060f1SDimitry Andric#include <__iterator/readable_traits.h> 610fe6060f1SDimitry Andric#include <__iterator/reverse_access.h> 611fe6060f1SDimitry Andric#include <__iterator/reverse_iterator.h> 612fe6060f1SDimitry Andric#include <__iterator/size.h> 613*349cc55cSDimitry Andric#include <__iterator/unreachable_sentinel.h> 614fe6060f1SDimitry Andric#include <__iterator/wrap_iter.h> 615fe6060f1SDimitry Andric#include <__memory/addressof.h> 616fe6060f1SDimitry Andric#include <__memory/pointer_traits.h> 617fe6060f1SDimitry Andric#include <__utility/forward.h> 618fe6060f1SDimitry Andric#include <compare> 619fe6060f1SDimitry Andric#include <concepts> // Mandated by the Standard. 6200b57cec5SDimitry Andric#include <cstddef> 6210b57cec5SDimitry Andric#include <initializer_list> 622fe6060f1SDimitry Andric#include <type_traits> 6230b57cec5SDimitry Andric#include <version> 6240b57cec5SDimitry Andric 6250b57cec5SDimitry Andric#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 6260b57cec5SDimitry Andric#pragma GCC system_header 6270b57cec5SDimitry Andric#endif 6280b57cec5SDimitry Andric 6290b57cec5SDimitry Andric#endif // _LIBCPP_ITERATOR 630