123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562 |
- // Iterators -*- C++ -*-
- // Copyright (C) 2001-2022 Free Software Foundation, Inc.
- //
- // This file is part of the GNU ISO C++ Library. This library is free
- // software; you can redistribute it and/or modify it under the
- // terms of the GNU General Public License as published by the
- // Free Software Foundation; either version 3, or (at your option)
- // any later version.
- // This library is distributed in the hope that it will be useful,
- // but WITHOUT ANY WARRANTY; without even the implied warranty of
- // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- // GNU General Public License for more details.
- // Under Section 7 of GPL version 3, you are granted additional
- // permissions described in the GCC Runtime Library Exception, version
- // 3.1, as published by the Free Software Foundation.
- // You should have received a copy of the GNU General Public License and
- // a copy of the GCC Runtime Library Exception along with this program;
- // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
- // <http://www.gnu.org/licenses/>.
- /*
- *
- * Copyright (c) 1994
- * Hewlett-Packard Company
- *
- * Permission to use, copy, modify, distribute and sell this software
- * and its documentation for any purpose is hereby granted without fee,
- * provided that the above copyright notice appear in all copies and
- * that both that copyright notice and this permission notice appear
- * in supporting documentation. Hewlett-Packard Company makes no
- * representations about the suitability of this software for any
- * purpose. It is provided "as is" without express or implied warranty.
- *
- *
- * Copyright (c) 1996-1998
- * Silicon Graphics Computer Systems, Inc.
- *
- * Permission to use, copy, modify, distribute and sell this software
- * and its documentation for any purpose is hereby granted without fee,
- * provided that the above copyright notice appear in all copies and
- * that both that copyright notice and this permission notice appear
- * in supporting documentation. Silicon Graphics makes no
- * representations about the suitability of this software for any
- * purpose. It is provided "as is" without express or implied warranty.
- */
- /** @file bits/stl_iterator.h
- * This is an internal header file, included by other library headers.
- * Do not attempt to use it directly. @headername{iterator}
- *
- * This file implements reverse_iterator, back_insert_iterator,
- * front_insert_iterator, insert_iterator, __normal_iterator, and their
- * supporting functions and overloaded operators.
- */
- #ifndef _STL_ITERATOR_H
- #define _STL_ITERATOR_H 1
- #include <bits/cpp_type_traits.h>
- #include <bits/stl_iterator_base_types.h>
- #include <ext/type_traits.h>
- #include <bits/move.h>
- #include <bits/ptr_traits.h>
- #if __cplusplus >= 201103L
- # include <type_traits>
- #endif
- #if __cplusplus > 201703L
- # define __cpp_lib_array_constexpr 201811L
- # define __cpp_lib_constexpr_iterator 201811L
- #elif __cplusplus == 201703L
- # define __cpp_lib_array_constexpr 201803L
- #endif
- #if __cplusplus >= 202002L
- # include <compare>
- # include <new>
- # include <bits/exception_defines.h>
- # include <bits/iterator_concepts.h>
- # include <bits/stl_construct.h>
- #endif
- namespace std _GLIBCXX_VISIBILITY(default)
- {
- _GLIBCXX_BEGIN_NAMESPACE_VERSION
- /**
- * @addtogroup iterators
- * @{
- */
- #if __cpp_lib_concepts
- namespace __detail
- {
- // Weaken iterator_category _Cat to _Limit if it is derived from that,
- // otherwise use _Otherwise.
- template<typename _Cat, typename _Limit, typename _Otherwise = _Cat>
- using __clamp_iter_cat
- = __conditional_t<derived_from<_Cat, _Limit>, _Limit, _Otherwise>;
- }
- #endif
- // Ignore warnings about std::iterator.
- #pragma GCC diagnostic push
- #pragma GCC diagnostic ignored "-Wdeprecated-declarations"
- // 24.4.1 Reverse iterators
- /**
- * Bidirectional and random access iterators have corresponding reverse
- * %iterator adaptors that iterate through the data structure in the
- * opposite direction. They have the same signatures as the corresponding
- * iterators. The fundamental relation between a reverse %iterator and its
- * corresponding %iterator @c i is established by the identity:
- * @code
- * &*(reverse_iterator(i)) == &*(i - 1)
- * @endcode
- *
- * <em>This mapping is dictated by the fact that while there is always a
- * pointer past the end of an array, there might not be a valid pointer
- * before the beginning of an array.</em> [24.4.1]/1,2
- *
- * Reverse iterators can be tricky and surprising at first. Their
- * semantics make sense, however, and the trickiness is a side effect of
- * the requirement that the iterators must be safe.
- */
- template<typename _Iterator>
- class reverse_iterator
- : public iterator<typename iterator_traits<_Iterator>::iterator_category,
- typename iterator_traits<_Iterator>::value_type,
- typename iterator_traits<_Iterator>::difference_type,
- typename iterator_traits<_Iterator>::pointer,
- typename iterator_traits<_Iterator>::reference>
- {
- template<typename _Iter>
- friend class reverse_iterator;
- #if __cpp_lib_concepts
- // _GLIBCXX_RESOLVE_LIB_DEFECTS
- // 3435. three_way_comparable_with<reverse_iterator<int*>, [...]>
- template<typename _Iter>
- static constexpr bool __convertible = !is_same_v<_Iter, _Iterator>
- && convertible_to<const _Iter&, _Iterator>;
- #endif
- protected:
- _Iterator current;
- typedef iterator_traits<_Iterator> __traits_type;
- public:
- typedef _Iterator iterator_type;
- typedef typename __traits_type::pointer pointer;
- #if ! __cpp_lib_concepts
- typedef typename __traits_type::difference_type difference_type;
- typedef typename __traits_type::reference reference;
- #else
- using iterator_concept
- = __conditional_t<random_access_iterator<_Iterator>,
- random_access_iterator_tag,
- bidirectional_iterator_tag>;
- using iterator_category
- = __detail::__clamp_iter_cat<typename __traits_type::iterator_category,
- random_access_iterator_tag>;
- using value_type = iter_value_t<_Iterator>;
- using difference_type = iter_difference_t<_Iterator>;
- using reference = iter_reference_t<_Iterator>;
- #endif
- /**
- * The default constructor value-initializes member @p current.
- * If it is a pointer, that means it is zero-initialized.
- */
- // _GLIBCXX_RESOLVE_LIB_DEFECTS
- // 235 No specification of default ctor for reverse_iterator
- // 1012. reverse_iterator default ctor should value initialize
- _GLIBCXX17_CONSTEXPR
- reverse_iterator()
- _GLIBCXX_NOEXCEPT_IF(noexcept(_Iterator()))
- : current()
- { }
- /**
- * This %iterator will move in the opposite direction that @p x does.
- */
- explicit _GLIBCXX17_CONSTEXPR
- reverse_iterator(iterator_type __x)
- _GLIBCXX_NOEXCEPT_IF(noexcept(_Iterator(__x)))
- : current(__x)
- { }
- /**
- * The copy constructor is normal.
- */
- _GLIBCXX17_CONSTEXPR
- reverse_iterator(const reverse_iterator& __x)
- _GLIBCXX_NOEXCEPT_IF(noexcept(_Iterator(__x.current)))
- : current(__x.current)
- { }
- #if __cplusplus >= 201103L
- reverse_iterator& operator=(const reverse_iterator&) = default;
- #endif
- /**
- * A %reverse_iterator across other types can be copied if the
- * underlying %iterator can be converted to the type of @c current.
- */
- template<typename _Iter>
- #if __cpp_lib_concepts
- requires __convertible<_Iter>
- #endif
- _GLIBCXX17_CONSTEXPR
- reverse_iterator(const reverse_iterator<_Iter>& __x)
- _GLIBCXX_NOEXCEPT_IF(noexcept(_Iterator(__x.current)))
- : current(__x.current)
- { }
- #if __cplusplus >= 201103L
- template<typename _Iter>
- #if __cpp_lib_concepts
- requires __convertible<_Iter>
- && assignable_from<_Iterator&, const _Iter&>
- #endif
- _GLIBCXX17_CONSTEXPR
- reverse_iterator&
- operator=(const reverse_iterator<_Iter>& __x)
- _GLIBCXX_NOEXCEPT_IF(noexcept(current = __x.current))
- {
- current = __x.current;
- return *this;
- }
- #endif
- /**
- * @return @c current, the %iterator used for underlying work.
- */
- _GLIBCXX_NODISCARD
- _GLIBCXX17_CONSTEXPR iterator_type
- base() const
- _GLIBCXX_NOEXCEPT_IF(noexcept(_Iterator(current)))
- { return current; }
- /**
- * @return A reference to the value at @c --current
- *
- * This requires that @c --current is dereferenceable.
- *
- * @warning This implementation requires that for an iterator of the
- * underlying iterator type, @c x, a reference obtained by
- * @c *x remains valid after @c x has been modified or
- * destroyed. This is a bug: http://gcc.gnu.org/PR51823
- */
- _GLIBCXX_NODISCARD
- _GLIBCXX17_CONSTEXPR reference
- operator*() const
- {
- _Iterator __tmp = current;
- return *--__tmp;
- }
- /**
- * @return A pointer to the value at @c --current
- *
- * This requires that @c --current is dereferenceable.
- */
- _GLIBCXX_NODISCARD
- _GLIBCXX17_CONSTEXPR pointer
- operator->() const
- #if __cplusplus > 201703L && __cpp_concepts >= 201907L
- requires is_pointer_v<_Iterator>
- || requires(const _Iterator __i) { __i.operator->(); }
- #endif
- {
- // _GLIBCXX_RESOLVE_LIB_DEFECTS
- // 1052. operator-> should also support smart pointers
- _Iterator __tmp = current;
- --__tmp;
- return _S_to_pointer(__tmp);
- }
- /**
- * @return @c *this
- *
- * Decrements the underlying iterator.
- */
- _GLIBCXX17_CONSTEXPR reverse_iterator&
- operator++()
- {
- --current;
- return *this;
- }
- /**
- * @return The original value of @c *this
- *
- * Decrements the underlying iterator.
- */
- _GLIBCXX17_CONSTEXPR reverse_iterator
- operator++(int)
- {
- reverse_iterator __tmp = *this;
- --current;
- return __tmp;
- }
- /**
- * @return @c *this
- *
- * Increments the underlying iterator.
- */
- _GLIBCXX17_CONSTEXPR reverse_iterator&
- operator--()
- {
- ++current;
- return *this;
- }
- /**
- * @return A reverse_iterator with the previous value of @c *this
- *
- * Increments the underlying iterator.
- */
- _GLIBCXX17_CONSTEXPR reverse_iterator
- operator--(int)
- {
- reverse_iterator __tmp = *this;
- ++current;
- return __tmp;
- }
- /**
- * @return A reverse_iterator that refers to @c current - @a __n
- *
- * The underlying iterator must be a Random Access Iterator.
- */
- _GLIBCXX_NODISCARD
- _GLIBCXX17_CONSTEXPR reverse_iterator
- operator+(difference_type __n) const
- { return reverse_iterator(current - __n); }
- /**
- * @return *this
- *
- * Moves the underlying iterator backwards @a __n steps.
- * The underlying iterator must be a Random Access Iterator.
- */
- _GLIBCXX17_CONSTEXPR reverse_iterator&
- operator+=(difference_type __n)
- {
- current -= __n;
- return *this;
- }
- /**
- * @return A reverse_iterator that refers to @c current - @a __n
- *
- * The underlying iterator must be a Random Access Iterator.
- */
- _GLIBCXX_NODISCARD
- _GLIBCXX17_CONSTEXPR reverse_iterator
- operator-(difference_type __n) const
- { return reverse_iterator(current + __n); }
- /**
- * @return *this
- *
- * Moves the underlying iterator forwards @a __n steps.
- * The underlying iterator must be a Random Access Iterator.
- */
- _GLIBCXX17_CONSTEXPR reverse_iterator&
- operator-=(difference_type __n)
- {
- current += __n;
- return *this;
- }
- /**
- * @return The value at @c current - @a __n - 1
- *
- * The underlying iterator must be a Random Access Iterator.
- */
- _GLIBCXX_NODISCARD
- _GLIBCXX17_CONSTEXPR reference
- operator[](difference_type __n) const
- { return *(*this + __n); }
- #if __cplusplus > 201703L && __cpp_lib_concepts
- [[nodiscard]]
- friend constexpr iter_rvalue_reference_t<_Iterator>
- iter_move(const reverse_iterator& __i)
- noexcept(is_nothrow_copy_constructible_v<_Iterator>
- && noexcept(ranges::iter_move(--std::declval<_Iterator&>())))
- {
- auto __tmp = __i.base();
- return ranges::iter_move(--__tmp);
- }
- template<indirectly_swappable<_Iterator> _Iter2>
- friend constexpr void
- iter_swap(const reverse_iterator& __x,
- const reverse_iterator<_Iter2>& __y)
- noexcept(is_nothrow_copy_constructible_v<_Iterator>
- && is_nothrow_copy_constructible_v<_Iter2>
- && noexcept(ranges::iter_swap(--std::declval<_Iterator&>(),
- --std::declval<_Iter2&>())))
- {
- auto __xtmp = __x.base();
- auto __ytmp = __y.base();
- ranges::iter_swap(--__xtmp, --__ytmp);
- }
- #endif
- private:
- template<typename _Tp>
- static _GLIBCXX17_CONSTEXPR _Tp*
- _S_to_pointer(_Tp* __p)
- { return __p; }
- template<typename _Tp>
- static _GLIBCXX17_CONSTEXPR pointer
- _S_to_pointer(_Tp __t)
- { return __t.operator->(); }
- };
- ///@{
- /**
- * @param __x A %reverse_iterator.
- * @param __y A %reverse_iterator.
- * @return A simple bool.
- *
- * Reverse iterators forward comparisons to their underlying base()
- * iterators.
- *
- */
- #if __cplusplus <= 201703L || ! defined __cpp_lib_concepts
- template<typename _Iterator>
- _GLIBCXX_NODISCARD
- inline _GLIBCXX17_CONSTEXPR bool
- operator==(const reverse_iterator<_Iterator>& __x,
- const reverse_iterator<_Iterator>& __y)
- { return __x.base() == __y.base(); }
- template<typename _Iterator>
- _GLIBCXX_NODISCARD
- inline _GLIBCXX17_CONSTEXPR bool
- operator<(const reverse_iterator<_Iterator>& __x,
- const reverse_iterator<_Iterator>& __y)
- { return __y.base() < __x.base(); }
- template<typename _Iterator>
- _GLIBCXX_NODISCARD
- inline _GLIBCXX17_CONSTEXPR bool
- operator!=(const reverse_iterator<_Iterator>& __x,
- const reverse_iterator<_Iterator>& __y)
- { return !(__x == __y); }
- template<typename _Iterator>
- _GLIBCXX_NODISCARD
- inline _GLIBCXX17_CONSTEXPR bool
- operator>(const reverse_iterator<_Iterator>& __x,
- const reverse_iterator<_Iterator>& __y)
- { return __y < __x; }
- template<typename _Iterator>
- _GLIBCXX_NODISCARD
- inline _GLIBCXX17_CONSTEXPR bool
- operator<=(const reverse_iterator<_Iterator>& __x,
- const reverse_iterator<_Iterator>& __y)
- { return !(__y < __x); }
- template<typename _Iterator>
- _GLIBCXX_NODISCARD
- inline _GLIBCXX17_CONSTEXPR bool
- operator>=(const reverse_iterator<_Iterator>& __x,
- const reverse_iterator<_Iterator>& __y)
- { return !(__x < __y); }
- // _GLIBCXX_RESOLVE_LIB_DEFECTS
- // DR 280. Comparison of reverse_iterator to const reverse_iterator.
- template<typename _IteratorL, typename _IteratorR>
- _GLIBCXX_NODISCARD
- inline _GLIBCXX17_CONSTEXPR bool
- operator==(const reverse_iterator<_IteratorL>& __x,
- const reverse_iterator<_IteratorR>& __y)
- { return __x.base() == __y.base(); }
- template<typename _IteratorL, typename _IteratorR>
- _GLIBCXX_NODISCARD
- inline _GLIBCXX17_CONSTEXPR bool
- operator<(const reverse_iterator<_IteratorL>& __x,
- const reverse_iterator<_IteratorR>& __y)
- { return __x.base() > __y.base(); }
- template<typename _IteratorL, typename _IteratorR>
- _GLIBCXX_NODISCARD
- inline _GLIBCXX17_CONSTEXPR bool
- operator!=(const reverse_iterator<_IteratorL>& __x,
- const reverse_iterator<_IteratorR>& __y)
- { return __x.base() != __y.base(); }
- template<typename _IteratorL, typename _IteratorR>
- _GLIBCXX_NODISCARD
- inline _GLIBCXX17_CONSTEXPR bool
- operator>(const reverse_iterator<_IteratorL>& __x,
- const reverse_iterator<_IteratorR>& __y)
- { return __x.base() < __y.base(); }
- template<typename _IteratorL, typename _IteratorR>
- inline _GLIBCXX17_CONSTEXPR bool
- operator<=(const reverse_iterator<_IteratorL>& __x,
- const reverse_iterator<_IteratorR>& __y)
- { return __x.base() >= __y.base(); }
- template<typename _IteratorL, typename _IteratorR>
- _GLIBCXX_NODISCARD
- inline _GLIBCXX17_CONSTEXPR bool
- operator>=(const reverse_iterator<_IteratorL>& __x,
- const reverse_iterator<_IteratorR>& __y)
- { return __x.base() <= __y.base(); }
- #else // C++20
- template<typename _IteratorL, typename _IteratorR>
- [[nodiscard]]
- constexpr bool
- operator==(const reverse_iterator<_IteratorL>& __x,
- const reverse_iterator<_IteratorR>& __y)
- requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
- { return __x.base() == __y.base(); }
- template<typename _IteratorL, typename _IteratorR>
- [[nodiscard]]
- constexpr bool
- operator!=(const reverse_iterator<_IteratorL>& __x,
- const reverse_iterator<_IteratorR>& __y)
- requires requires { { __x.base() != __y.base() } -> convertible_to<bool>; }
- { return __x.base() != __y.base(); }
- template<typename _IteratorL, typename _IteratorR>
- [[nodiscard]]
- constexpr bool
- operator<(const reverse_iterator<_IteratorL>& __x,
- const reverse_iterator<_IteratorR>& __y)
- requires requires { { __x.base() > __y.base() } -> convertible_to<bool>; }
- { return __x.base() > __y.base(); }
- template<typename _IteratorL, typename _IteratorR>
- [[nodiscard]]
- constexpr bool
- operator>(const reverse_iterator<_IteratorL>& __x,
- const reverse_iterator<_IteratorR>& __y)
- requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
- { return __x.base() < __y.base(); }
- template<typename _IteratorL, typename _IteratorR>
- [[nodiscard]]
- constexpr bool
- operator<=(const reverse_iterator<_IteratorL>& __x,
- const reverse_iterator<_IteratorR>& __y)
- requires requires { { __x.base() >= __y.base() } -> convertible_to<bool>; }
- { return __x.base() >= __y.base(); }
- template<typename _IteratorL, typename _IteratorR>
- [[nodiscard]]
- constexpr bool
- operator>=(const reverse_iterator<_IteratorL>& __x,
- const reverse_iterator<_IteratorR>& __y)
- requires requires { { __x.base() <= __y.base() } -> convertible_to<bool>; }
- { return __x.base() <= __y.base(); }
- template<typename _IteratorL,
- three_way_comparable_with<_IteratorL> _IteratorR>
- [[nodiscard]]
- constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
- operator<=>(const reverse_iterator<_IteratorL>& __x,
- const reverse_iterator<_IteratorR>& __y)
- { return __y.base() <=> __x.base(); }
- // Additional, non-standard overloads to avoid ambiguities with greedy,
- // unconstrained overloads in associated namespaces.
- template<typename _Iterator>
- [[nodiscard]]
- constexpr bool
- operator==(const reverse_iterator<_Iterator>& __x,
- const reverse_iterator<_Iterator>& __y)
- requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
- { return __x.base() == __y.base(); }
- template<three_way_comparable _Iterator>
- [[nodiscard]]
- constexpr compare_three_way_result_t<_Iterator, _Iterator>
- operator<=>(const reverse_iterator<_Iterator>& __x,
- const reverse_iterator<_Iterator>& __y)
- { return __y.base() <=> __x.base(); }
- #endif // C++20
- ///@}
- #if __cplusplus < 201103L
- template<typename _Iterator>
- inline typename reverse_iterator<_Iterator>::difference_type
- operator-(const reverse_iterator<_Iterator>& __x,
- const reverse_iterator<_Iterator>& __y)
- { return __y.base() - __x.base(); }
- template<typename _IteratorL, typename _IteratorR>
- inline typename reverse_iterator<_IteratorL>::difference_type
- operator-(const reverse_iterator<_IteratorL>& __x,
- const reverse_iterator<_IteratorR>& __y)
- { return __y.base() - __x.base(); }
- #else
- // _GLIBCXX_RESOLVE_LIB_DEFECTS
- // DR 685. reverse_iterator/move_iterator difference has invalid signatures
- template<typename _IteratorL, typename _IteratorR>
- [[__nodiscard__]]
- inline _GLIBCXX17_CONSTEXPR auto
- operator-(const reverse_iterator<_IteratorL>& __x,
- const reverse_iterator<_IteratorR>& __y)
- -> decltype(__y.base() - __x.base())
- { return __y.base() - __x.base(); }
- #endif
- template<typename _Iterator>
- _GLIBCXX_NODISCARD
- inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
- operator+(typename reverse_iterator<_Iterator>::difference_type __n,
- const reverse_iterator<_Iterator>& __x)
- { return reverse_iterator<_Iterator>(__x.base() - __n); }
- #if __cplusplus >= 201103L
- // Same as C++14 make_reverse_iterator but used in C++11 mode too.
- template<typename _Iterator>
- inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
- __make_reverse_iterator(_Iterator __i)
- { return reverse_iterator<_Iterator>(__i); }
- # if __cplusplus >= 201402L
- # define __cpp_lib_make_reverse_iterator 201402L
- // _GLIBCXX_RESOLVE_LIB_DEFECTS
- // DR 2285. make_reverse_iterator
- /// Generator function for reverse_iterator.
- template<typename _Iterator>
- [[__nodiscard__]]
- inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
- make_reverse_iterator(_Iterator __i)
- { return reverse_iterator<_Iterator>(__i); }
- # if __cplusplus > 201703L && defined __cpp_lib_concepts
- template<typename _Iterator1, typename _Iterator2>
- requires (!sized_sentinel_for<_Iterator1, _Iterator2>)
- inline constexpr bool
- disable_sized_sentinel_for<reverse_iterator<_Iterator1>,
- reverse_iterator<_Iterator2>> = true;
- # endif // C++20
- # endif // C++14
- template<typename _Iterator>
- _GLIBCXX20_CONSTEXPR
- auto
- __niter_base(reverse_iterator<_Iterator> __it)
- -> decltype(__make_reverse_iterator(__niter_base(__it.base())))
- { return __make_reverse_iterator(__niter_base(__it.base())); }
- template<typename _Iterator>
- struct __is_move_iterator<reverse_iterator<_Iterator> >
- : __is_move_iterator<_Iterator>
- { };
- template<typename _Iterator>
- _GLIBCXX20_CONSTEXPR
- auto
- __miter_base(reverse_iterator<_Iterator> __it)
- -> decltype(__make_reverse_iterator(__miter_base(__it.base())))
- { return __make_reverse_iterator(__miter_base(__it.base())); }
- #endif // C++11
- // 24.4.2.2.1 back_insert_iterator
- /**
- * @brief Turns assignment into insertion.
- *
- * These are output iterators, constructed from a container-of-T.
- * Assigning a T to the iterator appends it to the container using
- * push_back.
- *
- * Tip: Using the back_inserter function to create these iterators can
- * save typing.
- */
- template<typename _Container>
- class back_insert_iterator
- : public iterator<output_iterator_tag, void, void, void, void>
- {
- protected:
- _Container* container;
- public:
- /// A nested typedef for the type of whatever container you used.
- typedef _Container container_type;
- #if __cplusplus > 201703L
- using difference_type = ptrdiff_t;
- #endif
- /// The only way to create this %iterator is with a container.
- explicit _GLIBCXX20_CONSTEXPR
- back_insert_iterator(_Container& __x)
- : container(std::__addressof(__x)) { }
- /**
- * @param __value An instance of whatever type
- * container_type::const_reference is; presumably a
- * reference-to-const T for container<T>.
- * @return This %iterator, for chained operations.
- *
- * This kind of %iterator doesn't really have a @a position in the
- * container (you can think of the position as being permanently at
- * the end, if you like). Assigning a value to the %iterator will
- * always append the value to the end of the container.
- */
- #if __cplusplus < 201103L
- back_insert_iterator&
- operator=(typename _Container::const_reference __value)
- {
- container->push_back(__value);
- return *this;
- }
- #else
- _GLIBCXX20_CONSTEXPR
- back_insert_iterator&
- operator=(const typename _Container::value_type& __value)
- {
- container->push_back(__value);
- return *this;
- }
- _GLIBCXX20_CONSTEXPR
- back_insert_iterator&
- operator=(typename _Container::value_type&& __value)
- {
- container->push_back(std::move(__value));
- return *this;
- }
- #endif
- /// Simply returns *this.
- _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
- back_insert_iterator&
- operator*()
- { return *this; }
- /// Simply returns *this. (This %iterator does not @a move.)
- _GLIBCXX20_CONSTEXPR
- back_insert_iterator&
- operator++()
- { return *this; }
- /// Simply returns *this. (This %iterator does not @a move.)
- _GLIBCXX20_CONSTEXPR
- back_insert_iterator
- operator++(int)
- { return *this; }
- };
- /**
- * @param __x A container of arbitrary type.
- * @return An instance of back_insert_iterator working on @p __x.
- *
- * This wrapper function helps in creating back_insert_iterator instances.
- * Typing the name of the %iterator requires knowing the precise full
- * type of the container, which can be tedious and impedes generic
- * programming. Using this function lets you take advantage of automatic
- * template parameter deduction, making the compiler match the correct
- * types for you.
- */
- template<typename _Container>
- _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
- inline back_insert_iterator<_Container>
- back_inserter(_Container& __x)
- { return back_insert_iterator<_Container>(__x); }
- /**
- * @brief Turns assignment into insertion.
- *
- * These are output iterators, constructed from a container-of-T.
- * Assigning a T to the iterator prepends it to the container using
- * push_front.
- *
- * Tip: Using the front_inserter function to create these iterators can
- * save typing.
- */
- template<typename _Container>
- class front_insert_iterator
- : public iterator<output_iterator_tag, void, void, void, void>
- {
- protected:
- _Container* container;
- public:
- /// A nested typedef for the type of whatever container you used.
- typedef _Container container_type;
- #if __cplusplus > 201703L
- using difference_type = ptrdiff_t;
- #endif
- /// The only way to create this %iterator is with a container.
- explicit _GLIBCXX20_CONSTEXPR
- front_insert_iterator(_Container& __x)
- : container(std::__addressof(__x)) { }
- /**
- * @param __value An instance of whatever type
- * container_type::const_reference is; presumably a
- * reference-to-const T for container<T>.
- * @return This %iterator, for chained operations.
- *
- * This kind of %iterator doesn't really have a @a position in the
- * container (you can think of the position as being permanently at
- * the front, if you like). Assigning a value to the %iterator will
- * always prepend the value to the front of the container.
- */
- #if __cplusplus < 201103L
- front_insert_iterator&
- operator=(typename _Container::const_reference __value)
- {
- container->push_front(__value);
- return *this;
- }
- #else
- _GLIBCXX20_CONSTEXPR
- front_insert_iterator&
- operator=(const typename _Container::value_type& __value)
- {
- container->push_front(__value);
- return *this;
- }
- _GLIBCXX20_CONSTEXPR
- front_insert_iterator&
- operator=(typename _Container::value_type&& __value)
- {
- container->push_front(std::move(__value));
- return *this;
- }
- #endif
- /// Simply returns *this.
- _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
- front_insert_iterator&
- operator*()
- { return *this; }
- /// Simply returns *this. (This %iterator does not @a move.)
- _GLIBCXX20_CONSTEXPR
- front_insert_iterator&
- operator++()
- { return *this; }
- /// Simply returns *this. (This %iterator does not @a move.)
- _GLIBCXX20_CONSTEXPR
- front_insert_iterator
- operator++(int)
- { return *this; }
- };
- /**
- * @param __x A container of arbitrary type.
- * @return An instance of front_insert_iterator working on @p x.
- *
- * This wrapper function helps in creating front_insert_iterator instances.
- * Typing the name of the %iterator requires knowing the precise full
- * type of the container, which can be tedious and impedes generic
- * programming. Using this function lets you take advantage of automatic
- * template parameter deduction, making the compiler match the correct
- * types for you.
- */
- template<typename _Container>
- _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
- inline front_insert_iterator<_Container>
- front_inserter(_Container& __x)
- { return front_insert_iterator<_Container>(__x); }
- /**
- * @brief Turns assignment into insertion.
- *
- * These are output iterators, constructed from a container-of-T.
- * Assigning a T to the iterator inserts it in the container at the
- * %iterator's position, rather than overwriting the value at that
- * position.
- *
- * (Sequences will actually insert a @e copy of the value before the
- * %iterator's position.)
- *
- * Tip: Using the inserter function to create these iterators can
- * save typing.
- */
- template<typename _Container>
- class insert_iterator
- : public iterator<output_iterator_tag, void, void, void, void>
- {
- #if __cplusplus > 201703L && defined __cpp_lib_concepts
- using _Iter = std::__detail::__range_iter_t<_Container>;
- #else
- typedef typename _Container::iterator _Iter;
- #endif
- protected:
- _Container* container;
- _Iter iter;
- public:
- /// A nested typedef for the type of whatever container you used.
- typedef _Container container_type;
- #if __cplusplus > 201703L && defined __cpp_lib_concepts
- using difference_type = ptrdiff_t;
- #endif
- /**
- * The only way to create this %iterator is with a container and an
- * initial position (a normal %iterator into the container).
- */
- _GLIBCXX20_CONSTEXPR
- insert_iterator(_Container& __x, _Iter __i)
- : container(std::__addressof(__x)), iter(__i) {}
- /**
- * @param __value An instance of whatever type
- * container_type::const_reference is; presumably a
- * reference-to-const T for container<T>.
- * @return This %iterator, for chained operations.
- *
- * This kind of %iterator maintains its own position in the
- * container. Assigning a value to the %iterator will insert the
- * value into the container at the place before the %iterator.
- *
- * The position is maintained such that subsequent assignments will
- * insert values immediately after one another. For example,
- * @code
- * // vector v contains A and Z
- *
- * insert_iterator i (v, ++v.begin());
- * i = 1;
- * i = 2;
- * i = 3;
- *
- * // vector v contains A, 1, 2, 3, and Z
- * @endcode
- */
- #if __cplusplus < 201103L
- insert_iterator&
- operator=(typename _Container::const_reference __value)
- {
- iter = container->insert(iter, __value);
- ++iter;
- return *this;
- }
- #else
- _GLIBCXX20_CONSTEXPR
- insert_iterator&
- operator=(const typename _Container::value_type& __value)
- {
- iter = container->insert(iter, __value);
- ++iter;
- return *this;
- }
- _GLIBCXX20_CONSTEXPR
- insert_iterator&
- operator=(typename _Container::value_type&& __value)
- {
- iter = container->insert(iter, std::move(__value));
- ++iter;
- return *this;
- }
- #endif
- /// Simply returns *this.
- _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
- insert_iterator&
- operator*()
- { return *this; }
- /// Simply returns *this. (This %iterator does not @a move.)
- _GLIBCXX20_CONSTEXPR
- insert_iterator&
- operator++()
- { return *this; }
- /// Simply returns *this. (This %iterator does not @a move.)
- _GLIBCXX20_CONSTEXPR
- insert_iterator&
- operator++(int)
- { return *this; }
- };
- #pragma GCC diagnostic pop
- /**
- * @param __x A container of arbitrary type.
- * @param __i An iterator into the container.
- * @return An instance of insert_iterator working on @p __x.
- *
- * This wrapper function helps in creating insert_iterator instances.
- * Typing the name of the %iterator requires knowing the precise full
- * type of the container, which can be tedious and impedes generic
- * programming. Using this function lets you take advantage of automatic
- * template parameter deduction, making the compiler match the correct
- * types for you.
- */
- #if __cplusplus > 201703L && defined __cpp_lib_concepts
- template<typename _Container>
- [[nodiscard]]
- constexpr insert_iterator<_Container>
- inserter(_Container& __x, std::__detail::__range_iter_t<_Container> __i)
- { return insert_iterator<_Container>(__x, __i); }
- #else
- template<typename _Container>
- _GLIBCXX_NODISCARD
- inline insert_iterator<_Container>
- inserter(_Container& __x, typename _Container::iterator __i)
- { return insert_iterator<_Container>(__x, __i); }
- #endif
- /// @} group iterators
- _GLIBCXX_END_NAMESPACE_VERSION
- } // namespace
- namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
- {
- _GLIBCXX_BEGIN_NAMESPACE_VERSION
- // This iterator adapter is @a normal in the sense that it does not
- // change the semantics of any of the operators of its iterator
- // parameter. Its primary purpose is to convert an iterator that is
- // not a class, e.g. a pointer, into an iterator that is a class.
- // The _Container parameter exists solely so that different containers
- // using this template can instantiate different types, even if the
- // _Iterator parameter is the same.
- template<typename _Iterator, typename _Container>
- class __normal_iterator
- {
- protected:
- _Iterator _M_current;
- typedef std::iterator_traits<_Iterator> __traits_type;
- #if __cplusplus >= 201103L
- template<typename _Iter>
- using __convertible_from
- = std::__enable_if_t<std::is_convertible<_Iter, _Iterator>::value>;
- #endif
- public:
- typedef _Iterator iterator_type;
- typedef typename __traits_type::iterator_category iterator_category;
- typedef typename __traits_type::value_type value_type;
- typedef typename __traits_type::difference_type difference_type;
- typedef typename __traits_type::reference reference;
- typedef typename __traits_type::pointer pointer;
- #if __cplusplus > 201703L && __cpp_lib_concepts
- using iterator_concept = std::__detail::__iter_concept<_Iterator>;
- #endif
- _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
- : _M_current(_Iterator()) { }
- explicit _GLIBCXX20_CONSTEXPR
- __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
- : _M_current(__i) { }
- // Allow iterator to const_iterator conversion
- #if __cplusplus >= 201103L
- template<typename _Iter, typename = __convertible_from<_Iter>>
- _GLIBCXX20_CONSTEXPR
- __normal_iterator(const __normal_iterator<_Iter, _Container>& __i)
- noexcept
- #else
- // N.B. _Container::pointer is not actually in container requirements,
- // but is present in std::vector and std::basic_string.
- template<typename _Iter>
- __normal_iterator(const __normal_iterator<_Iter,
- typename __enable_if<
- (std::__are_same<_Iter, typename _Container::pointer>::__value),
- _Container>::__type>& __i)
- #endif
- : _M_current(__i.base()) { }
- // Forward iterator requirements
- _GLIBCXX20_CONSTEXPR
- reference
- operator*() const _GLIBCXX_NOEXCEPT
- { return *_M_current; }
- _GLIBCXX20_CONSTEXPR
- pointer
- operator->() const _GLIBCXX_NOEXCEPT
- { return _M_current; }
- _GLIBCXX20_CONSTEXPR
- __normal_iterator&
- operator++() _GLIBCXX_NOEXCEPT
- {
- ++_M_current;
- return *this;
- }
- _GLIBCXX20_CONSTEXPR
- __normal_iterator
- operator++(int) _GLIBCXX_NOEXCEPT
- { return __normal_iterator(_M_current++); }
- // Bidirectional iterator requirements
- _GLIBCXX20_CONSTEXPR
- __normal_iterator&
- operator--() _GLIBCXX_NOEXCEPT
- {
- --_M_current;
- return *this;
- }
- _GLIBCXX20_CONSTEXPR
- __normal_iterator
- operator--(int) _GLIBCXX_NOEXCEPT
- { return __normal_iterator(_M_current--); }
- // Random access iterator requirements
- _GLIBCXX20_CONSTEXPR
- reference
- operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
- { return _M_current[__n]; }
- _GLIBCXX20_CONSTEXPR
- __normal_iterator&
- operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
- { _M_current += __n; return *this; }
- _GLIBCXX20_CONSTEXPR
- __normal_iterator
- operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
- { return __normal_iterator(_M_current + __n); }
- _GLIBCXX20_CONSTEXPR
- __normal_iterator&
- operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
- { _M_current -= __n; return *this; }
- _GLIBCXX20_CONSTEXPR
- __normal_iterator
- operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
- { return __normal_iterator(_M_current - __n); }
- _GLIBCXX20_CONSTEXPR
- const _Iterator&
- base() const _GLIBCXX_NOEXCEPT
- { return _M_current; }
- };
- // Note: In what follows, the left- and right-hand-side iterators are
- // allowed to vary in types (conceptually in cv-qualification) so that
- // comparison between cv-qualified and non-cv-qualified iterators be
- // valid. However, the greedy and unfriendly operators in std::rel_ops
- // will make overload resolution ambiguous (when in scope) if we don't
- // provide overloads whose operands are of the same type. Can someone
- // remind me what generic programming is about? -- Gaby
- #if __cpp_lib_three_way_comparison
- template<typename _IteratorL, typename _IteratorR, typename _Container>
- [[nodiscard]]
- constexpr bool
- operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
- const __normal_iterator<_IteratorR, _Container>& __rhs)
- noexcept(noexcept(__lhs.base() == __rhs.base()))
- requires requires {
- { __lhs.base() == __rhs.base() } -> std::convertible_to<bool>;
- }
- { return __lhs.base() == __rhs.base(); }
- template<typename _IteratorL, typename _IteratorR, typename _Container>
- [[nodiscard]]
- constexpr std::__detail::__synth3way_t<_IteratorR, _IteratorL>
- operator<=>(const __normal_iterator<_IteratorL, _Container>& __lhs,
- const __normal_iterator<_IteratorR, _Container>& __rhs)
- noexcept(noexcept(std::__detail::__synth3way(__lhs.base(), __rhs.base())))
- { return std::__detail::__synth3way(__lhs.base(), __rhs.base()); }
- template<typename _Iterator, typename _Container>
- [[nodiscard]]
- constexpr bool
- operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
- const __normal_iterator<_Iterator, _Container>& __rhs)
- noexcept(noexcept(__lhs.base() == __rhs.base()))
- requires requires {
- { __lhs.base() == __rhs.base() } -> std::convertible_to<bool>;
- }
- { return __lhs.base() == __rhs.base(); }
- template<typename _Iterator, typename _Container>
- [[nodiscard]]
- constexpr std::__detail::__synth3way_t<_Iterator>
- operator<=>(const __normal_iterator<_Iterator, _Container>& __lhs,
- const __normal_iterator<_Iterator, _Container>& __rhs)
- noexcept(noexcept(std::__detail::__synth3way(__lhs.base(), __rhs.base())))
- { return std::__detail::__synth3way(__lhs.base(), __rhs.base()); }
- #else
- // Forward iterator requirements
- template<typename _IteratorL, typename _IteratorR, typename _Container>
- _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
- inline bool
- operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
- const __normal_iterator<_IteratorR, _Container>& __rhs)
- _GLIBCXX_NOEXCEPT
- { return __lhs.base() == __rhs.base(); }
- template<typename _Iterator, typename _Container>
- _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
- inline bool
- operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
- const __normal_iterator<_Iterator, _Container>& __rhs)
- _GLIBCXX_NOEXCEPT
- { return __lhs.base() == __rhs.base(); }
- template<typename _IteratorL, typename _IteratorR, typename _Container>
- _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
- inline bool
- operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
- const __normal_iterator<_IteratorR, _Container>& __rhs)
- _GLIBCXX_NOEXCEPT
- { return __lhs.base() != __rhs.base(); }
- template<typename _Iterator, typename _Container>
- _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
- inline bool
- operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
- const __normal_iterator<_Iterator, _Container>& __rhs)
- _GLIBCXX_NOEXCEPT
- { return __lhs.base() != __rhs.base(); }
- // Random access iterator requirements
- template<typename _IteratorL, typename _IteratorR, typename _Container>
- _GLIBCXX_NODISCARD
- inline bool
- operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
- const __normal_iterator<_IteratorR, _Container>& __rhs)
- _GLIBCXX_NOEXCEPT
- { return __lhs.base() < __rhs.base(); }
- template<typename _Iterator, typename _Container>
- _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
- inline bool
- operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
- const __normal_iterator<_Iterator, _Container>& __rhs)
- _GLIBCXX_NOEXCEPT
- { return __lhs.base() < __rhs.base(); }
- template<typename _IteratorL, typename _IteratorR, typename _Container>
- _GLIBCXX_NODISCARD
- inline bool
- operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
- const __normal_iterator<_IteratorR, _Container>& __rhs)
- _GLIBCXX_NOEXCEPT
- { return __lhs.base() > __rhs.base(); }
- template<typename _Iterator, typename _Container>
- _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
- inline bool
- operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
- const __normal_iterator<_Iterator, _Container>& __rhs)
- _GLIBCXX_NOEXCEPT
- { return __lhs.base() > __rhs.base(); }
- template<typename _IteratorL, typename _IteratorR, typename _Container>
- _GLIBCXX_NODISCARD
- inline bool
- operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
- const __normal_iterator<_IteratorR, _Container>& __rhs)
- _GLIBCXX_NOEXCEPT
- { return __lhs.base() <= __rhs.base(); }
- template<typename _Iterator, typename _Container>
- _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
- inline bool
- operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
- const __normal_iterator<_Iterator, _Container>& __rhs)
- _GLIBCXX_NOEXCEPT
- { return __lhs.base() <= __rhs.base(); }
- template<typename _IteratorL, typename _IteratorR, typename _Container>
- _GLIBCXX_NODISCARD
- inline bool
- operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
- const __normal_iterator<_IteratorR, _Container>& __rhs)
- _GLIBCXX_NOEXCEPT
- { return __lhs.base() >= __rhs.base(); }
- template<typename _Iterator, typename _Container>
- _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
- inline bool
- operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
- const __normal_iterator<_Iterator, _Container>& __rhs)
- _GLIBCXX_NOEXCEPT
- { return __lhs.base() >= __rhs.base(); }
- #endif // three-way comparison
- // _GLIBCXX_RESOLVE_LIB_DEFECTS
- // According to the resolution of DR179 not only the various comparison
- // operators but also operator- must accept mixed iterator/const_iterator
- // parameters.
- template<typename _IteratorL, typename _IteratorR, typename _Container>
- #if __cplusplus >= 201103L
- // DR 685.
- [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
- inline auto
- operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
- const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
- -> decltype(__lhs.base() - __rhs.base())
- #else
- inline typename __normal_iterator<_IteratorL, _Container>::difference_type
- operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
- const __normal_iterator<_IteratorR, _Container>& __rhs)
- #endif
- { return __lhs.base() - __rhs.base(); }
- template<typename _Iterator, typename _Container>
- _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
- inline typename __normal_iterator<_Iterator, _Container>::difference_type
- operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
- const __normal_iterator<_Iterator, _Container>& __rhs)
- _GLIBCXX_NOEXCEPT
- { return __lhs.base() - __rhs.base(); }
- template<typename _Iterator, typename _Container>
- _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
- inline __normal_iterator<_Iterator, _Container>
- operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
- __n, const __normal_iterator<_Iterator, _Container>& __i)
- _GLIBCXX_NOEXCEPT
- { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
- _GLIBCXX_END_NAMESPACE_VERSION
- } // namespace
- namespace std _GLIBCXX_VISIBILITY(default)
- {
- _GLIBCXX_BEGIN_NAMESPACE_VERSION
- template<typename _Iterator, typename _Container>
- _GLIBCXX20_CONSTEXPR
- _Iterator
- __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
- _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value)
- { return __it.base(); }
- #if __cplusplus >= 201103L
- #if __cplusplus <= 201703L
- // Need to overload __to_address because the pointer_traits primary template
- // will deduce element_type of __normal_iterator<T*, C> as T* rather than T.
- template<typename _Iterator, typename _Container>
- constexpr auto
- __to_address(const __gnu_cxx::__normal_iterator<_Iterator,
- _Container>& __it) noexcept
- -> decltype(std::__to_address(__it.base()))
- { return std::__to_address(__it.base()); }
- #endif
- /**
- * @addtogroup iterators
- * @{
- */
- #if __cplusplus > 201703L && __cpp_lib_concepts
- template<semiregular _Sent>
- class move_sentinel
- {
- public:
- constexpr
- move_sentinel()
- noexcept(is_nothrow_default_constructible_v<_Sent>)
- : _M_last() { }
- constexpr explicit
- move_sentinel(_Sent __s)
- noexcept(is_nothrow_move_constructible_v<_Sent>)
- : _M_last(std::move(__s)) { }
- template<typename _S2> requires convertible_to<const _S2&, _Sent>
- constexpr
- move_sentinel(const move_sentinel<_S2>& __s)
- noexcept(is_nothrow_constructible_v<_Sent, const _S2&>)
- : _M_last(__s.base())
- { }
- template<typename _S2> requires assignable_from<_Sent&, const _S2&>
- constexpr move_sentinel&
- operator=(const move_sentinel<_S2>& __s)
- noexcept(is_nothrow_assignable_v<_Sent, const _S2&>)
- {
- _M_last = __s.base();
- return *this;
- }
- [[nodiscard]]
- constexpr _Sent
- base() const
- noexcept(is_nothrow_copy_constructible_v<_Sent>)
- { return _M_last; }
- private:
- _Sent _M_last;
- };
- #endif // C++20
- namespace __detail
- {
- #if __cplusplus > 201703L && __cpp_lib_concepts
- template<typename _Iterator>
- struct __move_iter_cat
- { };
- template<typename _Iterator>
- requires requires { typename iterator_traits<_Iterator>::iterator_category; }
- struct __move_iter_cat<_Iterator>
- {
- using iterator_category
- = __clamp_iter_cat<typename iterator_traits<_Iterator>::iterator_category,
- random_access_iterator_tag>;
- };
- #endif
- }
- // 24.4.3 Move iterators
- /**
- * Class template move_iterator is an iterator adapter with the same
- * behavior as the underlying iterator except that its dereference
- * operator implicitly converts the value returned by the underlying
- * iterator's dereference operator to an rvalue reference. Some
- * generic algorithms can be called with move iterators to replace
- * copying with moving.
- */
- template<typename _Iterator>
- class move_iterator
- #if __cplusplus > 201703L && __cpp_lib_concepts
- : public __detail::__move_iter_cat<_Iterator>
- #endif
- {
- _Iterator _M_current;
- using __traits_type = iterator_traits<_Iterator>;
- #if ! (__cplusplus > 201703L && __cpp_lib_concepts)
- using __base_ref = typename __traits_type::reference;
- #endif
- template<typename _Iter2>
- friend class move_iterator;
- #if __cpp_lib_concepts
- // _GLIBCXX_RESOLVE_LIB_DEFECTS
- // 3435. three_way_comparable_with<reverse_iterator<int*>, [...]>
- template<typename _Iter2>
- static constexpr bool __convertible = !is_same_v<_Iter2, _Iterator>
- && convertible_to<const _Iter2&, _Iterator>;
- #endif
- public:
- using iterator_type = _Iterator;
- #if __cplusplus > 201703L && __cpp_lib_concepts
- using iterator_concept = input_iterator_tag;
- // iterator_category defined in __move_iter_cat
- using value_type = iter_value_t<_Iterator>;
- using difference_type = iter_difference_t<_Iterator>;
- using pointer = _Iterator;
- using reference = iter_rvalue_reference_t<_Iterator>;
- #else
- typedef typename __traits_type::iterator_category iterator_category;
- typedef typename __traits_type::value_type value_type;
- typedef typename __traits_type::difference_type difference_type;
- // NB: DR 680.
- typedef _Iterator pointer;
- // _GLIBCXX_RESOLVE_LIB_DEFECTS
- // 2106. move_iterator wrapping iterators returning prvalues
- using reference
- = __conditional_t<is_reference<__base_ref>::value,
- typename remove_reference<__base_ref>::type&&,
- __base_ref>;
- #endif
- _GLIBCXX17_CONSTEXPR
- move_iterator()
- : _M_current() { }
- explicit _GLIBCXX17_CONSTEXPR
- move_iterator(iterator_type __i)
- : _M_current(std::move(__i)) { }
- template<typename _Iter>
- #if __cpp_lib_concepts
- requires __convertible<_Iter>
- #endif
- _GLIBCXX17_CONSTEXPR
- move_iterator(const move_iterator<_Iter>& __i)
- : _M_current(__i._M_current) { }
- template<typename _Iter>
- #if __cpp_lib_concepts
- requires __convertible<_Iter>
- && assignable_from<_Iterator&, const _Iter&>
- #endif
- _GLIBCXX17_CONSTEXPR
- move_iterator& operator=(const move_iterator<_Iter>& __i)
- {
- _M_current = __i._M_current;
- return *this;
- }
- #if __cplusplus <= 201703L
- [[__nodiscard__]]
- _GLIBCXX17_CONSTEXPR iterator_type
- base() const
- { return _M_current; }
- #else
- [[nodiscard]]
- constexpr const iterator_type&
- base() const & noexcept
- { return _M_current; }
- [[nodiscard]]
- constexpr iterator_type
- base() &&
- { return std::move(_M_current); }
- #endif
- [[__nodiscard__]]
- _GLIBCXX17_CONSTEXPR reference
- operator*() const
- #if __cplusplus > 201703L && __cpp_lib_concepts
- { return ranges::iter_move(_M_current); }
- #else
- { return static_cast<reference>(*_M_current); }
- #endif
- [[__nodiscard__]]
- _GLIBCXX17_CONSTEXPR pointer
- operator->() const
- { return _M_current; }
- _GLIBCXX17_CONSTEXPR move_iterator&
- operator++()
- {
- ++_M_current;
- return *this;
- }
- _GLIBCXX17_CONSTEXPR move_iterator
- operator++(int)
- {
- move_iterator __tmp = *this;
- ++_M_current;
- return __tmp;
- }
- #if __cpp_lib_concepts
- constexpr void
- operator++(int) requires (!forward_iterator<_Iterator>)
- { ++_M_current; }
- #endif
- _GLIBCXX17_CONSTEXPR move_iterator&
- operator--()
- {
- --_M_current;
- return *this;
- }
- _GLIBCXX17_CONSTEXPR move_iterator
- operator--(int)
- {
- move_iterator __tmp = *this;
- --_M_current;
- return __tmp;
- }
- [[__nodiscard__]]
- _GLIBCXX17_CONSTEXPR move_iterator
- operator+(difference_type __n) const
- { return move_iterator(_M_current + __n); }
- _GLIBCXX17_CONSTEXPR move_iterator&
- operator+=(difference_type __n)
- {
- _M_current += __n;
- return *this;
- }
- [[__nodiscard__]]
- _GLIBCXX17_CONSTEXPR move_iterator
- operator-(difference_type __n) const
- { return move_iterator(_M_current - __n); }
-
- _GLIBCXX17_CONSTEXPR move_iterator&
- operator-=(difference_type __n)
- {
- _M_current -= __n;
- return *this;
- }
- [[__nodiscard__]]
- _GLIBCXX17_CONSTEXPR reference
- operator[](difference_type __n) const
- #if __cplusplus > 201703L && __cpp_lib_concepts
- { return ranges::iter_move(_M_current + __n); }
- #else
- { return std::move(_M_current[__n]); }
- #endif
- #if __cplusplus > 201703L && __cpp_lib_concepts
- template<sentinel_for<_Iterator> _Sent>
- [[nodiscard]]
- friend constexpr bool
- operator==(const move_iterator& __x, const move_sentinel<_Sent>& __y)
- { return __x.base() == __y.base(); }
- template<sized_sentinel_for<_Iterator> _Sent>
- [[nodiscard]]
- friend constexpr iter_difference_t<_Iterator>
- operator-(const move_sentinel<_Sent>& __x, const move_iterator& __y)
- { return __x.base() - __y.base(); }
- template<sized_sentinel_for<_Iterator> _Sent>
- [[nodiscard]]
- friend constexpr iter_difference_t<_Iterator>
- operator-(const move_iterator& __x, const move_sentinel<_Sent>& __y)
- { return __x.base() - __y.base(); }
- [[nodiscard]]
- friend constexpr iter_rvalue_reference_t<_Iterator>
- iter_move(const move_iterator& __i)
- noexcept(noexcept(ranges::iter_move(__i._M_current)))
- { return ranges::iter_move(__i._M_current); }
- template<indirectly_swappable<_Iterator> _Iter2>
- friend constexpr void
- iter_swap(const move_iterator& __x, const move_iterator<_Iter2>& __y)
- noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
- { return ranges::iter_swap(__x._M_current, __y._M_current); }
- #endif // C++20
- };
- template<typename _IteratorL, typename _IteratorR>
- [[__nodiscard__]]
- inline _GLIBCXX17_CONSTEXPR bool
- operator==(const move_iterator<_IteratorL>& __x,
- const move_iterator<_IteratorR>& __y)
- #if __cplusplus > 201703L && __cpp_lib_concepts
- requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
- #endif
- { return __x.base() == __y.base(); }
- #if __cpp_lib_three_way_comparison
- template<typename _IteratorL,
- three_way_comparable_with<_IteratorL> _IteratorR>
- [[__nodiscard__]]
- constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
- operator<=>(const move_iterator<_IteratorL>& __x,
- const move_iterator<_IteratorR>& __y)
- { return __x.base() <=> __y.base(); }
- #else
- template<typename _IteratorL, typename _IteratorR>
- [[__nodiscard__]]
- inline _GLIBCXX17_CONSTEXPR bool
- operator!=(const move_iterator<_IteratorL>& __x,
- const move_iterator<_IteratorR>& __y)
- { return !(__x == __y); }
- #endif
- template<typename _IteratorL, typename _IteratorR>
- [[__nodiscard__]]
- inline _GLIBCXX17_CONSTEXPR bool
- operator<(const move_iterator<_IteratorL>& __x,
- const move_iterator<_IteratorR>& __y)
- #if __cplusplus > 201703L && __cpp_lib_concepts
- requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
- #endif
- { return __x.base() < __y.base(); }
- template<typename _IteratorL, typename _IteratorR>
- [[__nodiscard__]]
- inline _GLIBCXX17_CONSTEXPR bool
- operator<=(const move_iterator<_IteratorL>& __x,
- const move_iterator<_IteratorR>& __y)
- #if __cplusplus > 201703L && __cpp_lib_concepts
- requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
- #endif
- { return !(__y < __x); }
- template<typename _IteratorL, typename _IteratorR>
- [[__nodiscard__]]
- inline _GLIBCXX17_CONSTEXPR bool
- operator>(const move_iterator<_IteratorL>& __x,
- const move_iterator<_IteratorR>& __y)
- #if __cplusplus > 201703L && __cpp_lib_concepts
- requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
- #endif
- { return __y < __x; }
- template<typename _IteratorL, typename _IteratorR>
- [[__nodiscard__]]
- inline _GLIBCXX17_CONSTEXPR bool
- operator>=(const move_iterator<_IteratorL>& __x,
- const move_iterator<_IteratorR>& __y)
- #if __cplusplus > 201703L && __cpp_lib_concepts
- requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
- #endif
- { return !(__x < __y); }
- // Note: See __normal_iterator operators note from Gaby to understand
- // why we have these extra overloads for some move_iterator operators.
- template<typename _Iterator>
- [[__nodiscard__]]
- inline _GLIBCXX17_CONSTEXPR bool
- operator==(const move_iterator<_Iterator>& __x,
- const move_iterator<_Iterator>& __y)
- { return __x.base() == __y.base(); }
- #if __cpp_lib_three_way_comparison
- template<three_way_comparable _Iterator>
- [[__nodiscard__]]
- constexpr compare_three_way_result_t<_Iterator>
- operator<=>(const move_iterator<_Iterator>& __x,
- const move_iterator<_Iterator>& __y)
- { return __x.base() <=> __y.base(); }
- #else
- template<typename _Iterator>
- [[__nodiscard__]]
- inline _GLIBCXX17_CONSTEXPR bool
- operator!=(const move_iterator<_Iterator>& __x,
- const move_iterator<_Iterator>& __y)
- { return !(__x == __y); }
- template<typename _Iterator>
- [[__nodiscard__]]
- inline _GLIBCXX17_CONSTEXPR bool
- operator<(const move_iterator<_Iterator>& __x,
- const move_iterator<_Iterator>& __y)
- { return __x.base() < __y.base(); }
- template<typename _Iterator>
- [[__nodiscard__]]
- inline _GLIBCXX17_CONSTEXPR bool
- operator<=(const move_iterator<_Iterator>& __x,
- const move_iterator<_Iterator>& __y)
- { return !(__y < __x); }
- template<typename _Iterator>
- [[__nodiscard__]]
- inline _GLIBCXX17_CONSTEXPR bool
- operator>(const move_iterator<_Iterator>& __x,
- const move_iterator<_Iterator>& __y)
- { return __y < __x; }
- template<typename _Iterator>
- [[__nodiscard__]]
- inline _GLIBCXX17_CONSTEXPR bool
- operator>=(const move_iterator<_Iterator>& __x,
- const move_iterator<_Iterator>& __y)
- { return !(__x < __y); }
- #endif // ! C++20
- // DR 685.
- template<typename _IteratorL, typename _IteratorR>
- [[__nodiscard__]]
- inline _GLIBCXX17_CONSTEXPR auto
- operator-(const move_iterator<_IteratorL>& __x,
- const move_iterator<_IteratorR>& __y)
- -> decltype(__x.base() - __y.base())
- { return __x.base() - __y.base(); }
- template<typename _Iterator>
- [[__nodiscard__]]
- inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
- operator+(typename move_iterator<_Iterator>::difference_type __n,
- const move_iterator<_Iterator>& __x)
- { return __x + __n; }
- template<typename _Iterator>
- [[__nodiscard__]]
- inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
- make_move_iterator(_Iterator __i)
- { return move_iterator<_Iterator>(std::move(__i)); }
- template<typename _Iterator, typename _ReturnType
- = __conditional_t<__move_if_noexcept_cond
- <typename iterator_traits<_Iterator>::value_type>::value,
- _Iterator, move_iterator<_Iterator>>>
- inline _GLIBCXX17_CONSTEXPR _ReturnType
- __make_move_if_noexcept_iterator(_Iterator __i)
- { return _ReturnType(__i); }
- // Overload for pointers that matches std::move_if_noexcept more closely,
- // returning a constant iterator when we don't want to move.
- template<typename _Tp, typename _ReturnType
- = __conditional_t<__move_if_noexcept_cond<_Tp>::value,
- const _Tp*, move_iterator<_Tp*>>>
- inline _GLIBCXX17_CONSTEXPR _ReturnType
- __make_move_if_noexcept_iterator(_Tp* __i)
- { return _ReturnType(__i); }
- #if __cplusplus > 201703L && __cpp_lib_concepts
- // [iterators.common] Common iterators
- namespace __detail
- {
- template<typename _It>
- concept __common_iter_has_arrow = indirectly_readable<const _It>
- && (requires(const _It& __it) { __it.operator->(); }
- || is_reference_v<iter_reference_t<_It>>
- || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
- template<typename _It>
- concept __common_iter_use_postfix_proxy
- = (!requires (_It& __i) { { *__i++ } -> __can_reference; })
- && constructible_from<iter_value_t<_It>, iter_reference_t<_It>>
- && move_constructible<iter_value_t<_It>>;
- } // namespace __detail
- /// An iterator/sentinel adaptor for representing a non-common range.
- template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
- requires (!same_as<_It, _Sent>) && copyable<_It>
- class common_iterator
- {
- template<typename _Tp, typename _Up>
- static constexpr bool
- _S_noexcept1()
- {
- if constexpr (is_trivially_default_constructible_v<_Tp>)
- return is_nothrow_assignable_v<_Tp, _Up>;
- else
- return is_nothrow_constructible_v<_Tp, _Up>;
- }
- template<typename _It2, typename _Sent2>
- static constexpr bool
- _S_noexcept()
- { return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }
- class __arrow_proxy
- {
- iter_value_t<_It> _M_keep;
- constexpr
- __arrow_proxy(iter_reference_t<_It>&& __x)
- : _M_keep(std::move(__x)) { }
- friend class common_iterator;
- public:
- constexpr const iter_value_t<_It>*
- operator->() const noexcept
- { return std::__addressof(_M_keep); }
- };
- class __postfix_proxy
- {
- iter_value_t<_It> _M_keep;
- constexpr
- __postfix_proxy(iter_reference_t<_It>&& __x)
- : _M_keep(std::forward<iter_reference_t<_It>>(__x)) { }
- friend class common_iterator;
- public:
- constexpr const iter_value_t<_It>&
- operator*() const noexcept
- { return _M_keep; }
- };
- public:
- constexpr
- common_iterator()
- noexcept(is_nothrow_default_constructible_v<_It>)
- requires default_initializable<_It>
- : _M_it(), _M_index(0)
- { }
- constexpr
- common_iterator(_It __i)
- noexcept(is_nothrow_move_constructible_v<_It>)
- : _M_it(std::move(__i)), _M_index(0)
- { }
- constexpr
- common_iterator(_Sent __s)
- noexcept(is_nothrow_move_constructible_v<_Sent>)
- : _M_sent(std::move(__s)), _M_index(1)
- { }
- template<typename _It2, typename _Sent2>
- requires convertible_to<const _It2&, _It>
- && convertible_to<const _Sent2&, _Sent>
- constexpr
- common_iterator(const common_iterator<_It2, _Sent2>& __x)
- noexcept(_S_noexcept<const _It2&, const _Sent2&>())
- : _M_valueless(), _M_index(__x._M_index)
- {
- if (_M_index == 0)
- {
- if constexpr (is_trivially_default_constructible_v<_It>)
- _M_it = std::move(__x._M_it);
- else
- std::construct_at(std::__addressof(_M_it), __x._M_it);
- }
- else if (_M_index == 1)
- {
- if constexpr (is_trivially_default_constructible_v<_Sent>)
- _M_sent = std::move(__x._M_sent);
- else
- std::construct_at(std::__addressof(_M_sent), __x._M_sent);
- }
- }
- constexpr
- common_iterator(const common_iterator& __x)
- noexcept(_S_noexcept<const _It&, const _Sent&>())
- : _M_valueless(), _M_index(__x._M_index)
- {
- if (_M_index == 0)
- {
- if constexpr (is_trivially_default_constructible_v<_It>)
- _M_it = std::move(__x._M_it);
- else
- std::construct_at(std::__addressof(_M_it), __x._M_it);
- }
- else if (_M_index == 1)
- {
- if constexpr (is_trivially_default_constructible_v<_Sent>)
- _M_sent = std::move(__x._M_sent);
- else
- std::construct_at(std::__addressof(_M_sent), __x._M_sent);
- }
- }
- constexpr common_iterator&
- operator=(const common_iterator& __x)
- noexcept(is_nothrow_copy_assignable_v<_It>
- && is_nothrow_copy_assignable_v<_Sent>
- && is_nothrow_copy_constructible_v<_It>
- && is_nothrow_copy_constructible_v<_Sent>)
- {
- return this->operator=<_It, _Sent>(__x);
- }
- template<typename _It2, typename _Sent2>
- requires convertible_to<const _It2&, _It>
- && convertible_to<const _Sent2&, _Sent>
- && assignable_from<_It&, const _It2&>
- && assignable_from<_Sent&, const _Sent2&>
- constexpr common_iterator&
- operator=(const common_iterator<_It2, _Sent2>& __x)
- noexcept(is_nothrow_constructible_v<_It, const _It2&>
- && is_nothrow_constructible_v<_Sent, const _Sent2&>
- && is_nothrow_assignable_v<_It, const _It2&>
- && is_nothrow_assignable_v<_Sent, const _Sent2&>)
- {
- switch(_M_index << 2 | __x._M_index)
- {
- case 0b0000:
- _M_it = __x._M_it;
- break;
- case 0b0101:
- _M_sent = __x._M_sent;
- break;
- case 0b0001:
- _M_it.~_It();
- _M_index = -1;
- [[fallthrough]];
- case 0b1001:
- std::construct_at(std::__addressof(_M_sent), _Sent(__x._M_sent));
- _M_index = 1;
- break;
- case 0b0100:
- _M_sent.~_Sent();
- _M_index = -1;
- [[fallthrough]];
- case 0b1000:
- std::construct_at(std::__addressof(_M_it), _It(__x._M_it));
- _M_index = 0;
- break;
- default:
- __glibcxx_assert(__x._M_has_value());
- __builtin_unreachable();
- }
- return *this;
- }
- constexpr
- ~common_iterator()
- {
- switch (_M_index)
- {
- case 0:
- _M_it.~_It();
- break;
- case 1:
- _M_sent.~_Sent();
- break;
- }
- }
- [[nodiscard]]
- constexpr decltype(auto)
- operator*()
- {
- __glibcxx_assert(_M_index == 0);
- return *_M_it;
- }
- [[nodiscard]]
- constexpr decltype(auto)
- operator*() const requires __detail::__dereferenceable<const _It>
- {
- __glibcxx_assert(_M_index == 0);
- return *_M_it;
- }
- [[nodiscard]]
- constexpr decltype(auto)
- operator->() const requires __detail::__common_iter_has_arrow<_It>
- {
- __glibcxx_assert(_M_index == 0);
- if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
- return _M_it;
- else if constexpr (is_reference_v<iter_reference_t<_It>>)
- {
- auto&& __tmp = *_M_it;
- return std::__addressof(__tmp);
- }
- else
- return __arrow_proxy{*_M_it};
- }
- constexpr common_iterator&
- operator++()
- {
- __glibcxx_assert(_M_index == 0);
- ++_M_it;
- return *this;
- }
- constexpr decltype(auto)
- operator++(int)
- {
- __glibcxx_assert(_M_index == 0);
- if constexpr (forward_iterator<_It>)
- {
- common_iterator __tmp = *this;
- ++*this;
- return __tmp;
- }
- else if constexpr (!__detail::__common_iter_use_postfix_proxy<_It>)
- return _M_it++;
- else
- {
- __postfix_proxy __p(**this);
- ++*this;
- return __p;
- }
- }
- template<typename _It2, sentinel_for<_It> _Sent2>
- requires sentinel_for<_Sent, _It2>
- friend constexpr bool
- operator== [[nodiscard]] (const common_iterator& __x,
- const common_iterator<_It2, _Sent2>& __y)
- {
- switch(__x._M_index << 2 | __y._M_index)
- {
- case 0b0000:
- case 0b0101:
- return true;
- case 0b0001:
- return __x._M_it == __y._M_sent;
- case 0b0100:
- return __x._M_sent == __y._M_it;
- default:
- __glibcxx_assert(__x._M_has_value());
- __glibcxx_assert(__y._M_has_value());
- __builtin_unreachable();
- }
- }
- template<typename _It2, sentinel_for<_It> _Sent2>
- requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
- friend constexpr bool
- operator== [[nodiscard]] (const common_iterator& __x,
- const common_iterator<_It2, _Sent2>& __y)
- {
- switch(__x._M_index << 2 | __y._M_index)
- {
- case 0b0101:
- return true;
- case 0b0000:
- return __x._M_it == __y._M_it;
- case 0b0001:
- return __x._M_it == __y._M_sent;
- case 0b0100:
- return __x._M_sent == __y._M_it;
- default:
- __glibcxx_assert(__x._M_has_value());
- __glibcxx_assert(__y._M_has_value());
- __builtin_unreachable();
- }
- }
- template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
- requires sized_sentinel_for<_Sent, _It2>
- friend constexpr iter_difference_t<_It2>
- operator- [[nodiscard]] (const common_iterator& __x,
- const common_iterator<_It2, _Sent2>& __y)
- {
- switch(__x._M_index << 2 | __y._M_index)
- {
- case 0b0101:
- return 0;
- case 0b0000:
- return __x._M_it - __y._M_it;
- case 0b0001:
- return __x._M_it - __y._M_sent;
- case 0b0100:
- return __x._M_sent - __y._M_it;
- default:
- __glibcxx_assert(__x._M_has_value());
- __glibcxx_assert(__y._M_has_value());
- __builtin_unreachable();
- }
- }
- [[nodiscard]]
- friend constexpr iter_rvalue_reference_t<_It>
- iter_move(const common_iterator& __i)
- noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
- requires input_iterator<_It>
- {
- __glibcxx_assert(__i._M_index == 0);
- return ranges::iter_move(__i._M_it);
- }
- template<indirectly_swappable<_It> _It2, typename _Sent2>
- friend constexpr void
- iter_swap(const common_iterator& __x,
- const common_iterator<_It2, _Sent2>& __y)
- noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
- std::declval<const _It2&>())))
- {
- __glibcxx_assert(__x._M_index == 0);
- __glibcxx_assert(__y._M_index == 0);
- return ranges::iter_swap(__x._M_it, __y._M_it);
- }
- private:
- template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
- friend class common_iterator;
- constexpr bool _M_has_value() const noexcept { return _M_index < 2; }
- union
- {
- _It _M_it;
- _Sent _M_sent;
- unsigned char _M_valueless;
- };
- unsigned char _M_index; // 0==_M_it, 1==_M_sent, 2==valueless
- };
- template<typename _It, typename _Sent>
- struct incrementable_traits<common_iterator<_It, _Sent>>
- {
- using difference_type = iter_difference_t<_It>;
- };
- template<input_iterator _It, typename _Sent>
- struct iterator_traits<common_iterator<_It, _Sent>>
- {
- private:
- template<typename _Iter>
- struct __ptr
- {
- using type = void;
- };
- template<typename _Iter>
- requires __detail::__common_iter_has_arrow<_Iter>
- struct __ptr<_Iter>
- {
- using _CIter = common_iterator<_Iter, _Sent>;
- using type = decltype(std::declval<const _CIter&>().operator->());
- };
- static auto
- _S_iter_cat()
- {
- using _Traits = iterator_traits<_It>;
- if constexpr (requires { requires derived_from<typename _Traits::iterator_category,
- forward_iterator_tag>; })
- return forward_iterator_tag{};
- else
- return input_iterator_tag{};
- }
- public:
- using iterator_concept = __conditional_t<forward_iterator<_It>,
- forward_iterator_tag,
- input_iterator_tag>;
- using iterator_category = decltype(_S_iter_cat());
- using value_type = iter_value_t<_It>;
- using difference_type = iter_difference_t<_It>;
- using pointer = typename __ptr<_It>::type;
- using reference = iter_reference_t<_It>;
- };
- // [iterators.counted] Counted iterators
- namespace __detail
- {
- template<typename _It>
- struct __counted_iter_value_type
- { };
- template<indirectly_readable _It>
- struct __counted_iter_value_type<_It>
- { using value_type = iter_value_t<_It>; };
- template<typename _It>
- struct __counted_iter_concept
- { };
- template<typename _It>
- requires requires { typename _It::iterator_concept; }
- struct __counted_iter_concept<_It>
- { using iterator_concept = typename _It::iterator_concept; };
- template<typename _It>
- struct __counted_iter_cat
- { };
- template<typename _It>
- requires requires { typename _It::iterator_category; }
- struct __counted_iter_cat<_It>
- { using iterator_category = typename _It::iterator_category; };
- }
- /// An iterator adaptor that keeps track of the distance to the end.
- template<input_or_output_iterator _It>
- class counted_iterator
- : public __detail::__counted_iter_value_type<_It>,
- public __detail::__counted_iter_concept<_It>,
- public __detail::__counted_iter_cat<_It>
- {
- public:
- using iterator_type = _It;
- // value_type defined in __counted_iter_value_type
- using difference_type = iter_difference_t<_It>;
- // iterator_concept defined in __counted_iter_concept
- // iterator_category defined in __counted_iter_cat
- constexpr counted_iterator() requires default_initializable<_It> = default;
- constexpr
- counted_iterator(_It __i, iter_difference_t<_It> __n)
- : _M_current(std::move(__i)), _M_length(__n)
- { __glibcxx_assert(__n >= 0); }
- template<typename _It2>
- requires convertible_to<const _It2&, _It>
- constexpr
- counted_iterator(const counted_iterator<_It2>& __x)
- : _M_current(__x._M_current), _M_length(__x._M_length)
- { }
- template<typename _It2>
- requires assignable_from<_It&, const _It2&>
- constexpr counted_iterator&
- operator=(const counted_iterator<_It2>& __x)
- {
- _M_current = __x._M_current;
- _M_length = __x._M_length;
- return *this;
- }
- [[nodiscard]]
- constexpr const _It&
- base() const & noexcept
- { return _M_current; }
- [[nodiscard]]
- constexpr _It
- base() &&
- noexcept(is_nothrow_move_constructible_v<_It>)
- { return std::move(_M_current); }
- [[nodiscard]]
- constexpr iter_difference_t<_It>
- count() const noexcept { return _M_length; }
- [[nodiscard]]
- constexpr decltype(auto)
- operator*()
- noexcept(noexcept(*_M_current))
- {
- __glibcxx_assert( _M_length > 0 );
- return *_M_current;
- }
- [[nodiscard]]
- constexpr decltype(auto)
- operator*() const
- noexcept(noexcept(*_M_current))
- requires __detail::__dereferenceable<const _It>
- {
- __glibcxx_assert( _M_length > 0 );
- return *_M_current;
- }
- [[nodiscard]]
- constexpr auto
- operator->() const noexcept
- requires contiguous_iterator<_It>
- { return std::to_address(_M_current); }
- constexpr counted_iterator&
- operator++()
- {
- __glibcxx_assert(_M_length > 0);
- ++_M_current;
- --_M_length;
- return *this;
- }
- decltype(auto)
- operator++(int)
- {
- __glibcxx_assert(_M_length > 0);
- --_M_length;
- __try
- {
- return _M_current++;
- } __catch(...) {
- ++_M_length;
- __throw_exception_again;
- }
- }
- constexpr counted_iterator
- operator++(int) requires forward_iterator<_It>
- {
- auto __tmp = *this;
- ++*this;
- return __tmp;
- }
- constexpr counted_iterator&
- operator--() requires bidirectional_iterator<_It>
- {
- --_M_current;
- ++_M_length;
- return *this;
- }
- constexpr counted_iterator
- operator--(int) requires bidirectional_iterator<_It>
- {
- auto __tmp = *this;
- --*this;
- return __tmp;
- }
- [[nodiscard]]
- constexpr counted_iterator
- operator+(iter_difference_t<_It> __n) const
- requires random_access_iterator<_It>
- { return counted_iterator(_M_current + __n, _M_length - __n); }
- [[nodiscard]]
- friend constexpr counted_iterator
- operator+(iter_difference_t<_It> __n, const counted_iterator& __x)
- requires random_access_iterator<_It>
- { return __x + __n; }
- constexpr counted_iterator&
- operator+=(iter_difference_t<_It> __n)
- requires random_access_iterator<_It>
- {
- __glibcxx_assert(__n <= _M_length);
- _M_current += __n;
- _M_length -= __n;
- return *this;
- }
- [[nodiscard]]
- constexpr counted_iterator
- operator-(iter_difference_t<_It> __n) const
- requires random_access_iterator<_It>
- { return counted_iterator(_M_current - __n, _M_length + __n); }
- template<common_with<_It> _It2>
- [[nodiscard]]
- friend constexpr iter_difference_t<_It2>
- operator-(const counted_iterator& __x,
- const counted_iterator<_It2>& __y)
- { return __y._M_length - __x._M_length; }
- [[nodiscard]]
- friend constexpr iter_difference_t<_It>
- operator-(const counted_iterator& __x, default_sentinel_t)
- { return -__x._M_length; }
- [[nodiscard]]
- friend constexpr iter_difference_t<_It>
- operator-(default_sentinel_t, const counted_iterator& __y)
- { return __y._M_length; }
- constexpr counted_iterator&
- operator-=(iter_difference_t<_It> __n)
- requires random_access_iterator<_It>
- {
- __glibcxx_assert(-__n <= _M_length);
- _M_current -= __n;
- _M_length += __n;
- return *this;
- }
- [[nodiscard]]
- constexpr decltype(auto)
- operator[](iter_difference_t<_It> __n) const
- noexcept(noexcept(_M_current[__n]))
- requires random_access_iterator<_It>
- {
- __glibcxx_assert(__n < _M_length);
- return _M_current[__n];
- }
- template<common_with<_It> _It2>
- [[nodiscard]]
- friend constexpr bool
- operator==(const counted_iterator& __x,
- const counted_iterator<_It2>& __y)
- { return __x._M_length == __y._M_length; }
- [[nodiscard]]
- friend constexpr bool
- operator==(const counted_iterator& __x, default_sentinel_t)
- { return __x._M_length == 0; }
- template<common_with<_It> _It2>
- [[nodiscard]]
- friend constexpr strong_ordering
- operator<=>(const counted_iterator& __x,
- const counted_iterator<_It2>& __y)
- { return __y._M_length <=> __x._M_length; }
- [[nodiscard]]
- friend constexpr iter_rvalue_reference_t<_It>
- iter_move(const counted_iterator& __i)
- noexcept(noexcept(ranges::iter_move(__i._M_current)))
- requires input_iterator<_It>
- {
- __glibcxx_assert( __i._M_length > 0 );
- return ranges::iter_move(__i._M_current);
- }
- template<indirectly_swappable<_It> _It2>
- friend constexpr void
- iter_swap(const counted_iterator& __x,
- const counted_iterator<_It2>& __y)
- noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
- {
- __glibcxx_assert( __x._M_length > 0 && __y._M_length > 0 );
- ranges::iter_swap(__x._M_current, __y._M_current);
- }
- private:
- template<input_or_output_iterator _It2> friend class counted_iterator;
- _It _M_current = _It();
- iter_difference_t<_It> _M_length = 0;
- };
- template<input_iterator _It>
- requires same_as<__detail::__iter_traits<_It>, iterator_traits<_It>>
- struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
- {
- using pointer = __conditional_t<contiguous_iterator<_It>,
- add_pointer_t<iter_reference_t<_It>>,
- void>;
- };
- #endif // C++20
- /// @} group iterators
- template<typename _Iterator>
- _GLIBCXX20_CONSTEXPR
- auto
- __niter_base(move_iterator<_Iterator> __it)
- -> decltype(make_move_iterator(__niter_base(__it.base())))
- { return make_move_iterator(__niter_base(__it.base())); }
- template<typename _Iterator>
- struct __is_move_iterator<move_iterator<_Iterator> >
- {
- enum { __value = 1 };
- typedef __true_type __type;
- };
- template<typename _Iterator>
- _GLIBCXX20_CONSTEXPR
- auto
- __miter_base(move_iterator<_Iterator> __it)
- -> decltype(__miter_base(__it.base()))
- { return __miter_base(__it.base()); }
- #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
- #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
- std::__make_move_if_noexcept_iterator(_Iter)
- #else
- #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
- #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
- #endif // C++11
- #if __cpp_deduction_guides >= 201606
- // These helper traits are used for deduction guides
- // of associative containers.
- template<typename _InputIterator>
- using __iter_key_t = remove_const_t<
- typename iterator_traits<_InputIterator>::value_type::first_type>;
- template<typename _InputIterator>
- using __iter_val_t =
- typename iterator_traits<_InputIterator>::value_type::second_type;
- template<typename _T1, typename _T2>
- struct pair;
- template<typename _InputIterator>
- using __iter_to_alloc_t =
- pair<add_const_t<__iter_key_t<_InputIterator>>,
- __iter_val_t<_InputIterator>>;
- #endif // __cpp_deduction_guides
- _GLIBCXX_END_NAMESPACE_VERSION
- } // namespace
- #ifdef _GLIBCXX_DEBUG
- # include <debug/stl_iterator.h>
- #endif
- #endif
|