depish/cppdraft_translate
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
cppdraft_translate/cppdraft/iterator/primitives.md
Leonov Artur (Depish) 043225d523 Init
2025-10-25 03:02:53 +03:00

435 lines
20 KiB
Markdown
Raw Permalink Blame History

This file contains invisible Unicode characters

This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

[iterator.primitives]
# 24 Iterators library [[iterators]](./#iterators)
## 24.4 Iterator primitives [iterator.primitives]
### [24.4.1](#general) General [[iterator.primitives.general]](iterator.primitives.general)
[1](#general-1)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2738)
To simplify the use of iterators, the library provides
several classes and functions[.](#general-1.sentence-1)
### [24.4.2](#std.iterator.tags) Standard iterator tags [[std.iterator.tags]](std.iterator.tags)
[1](#std.iterator.tags-1)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2744)
It is often desirable for a
function template specialization
to find out what is the most specific category of its iterator
argument, so that the function can select the most efficient algorithm at compile time[.](#std.iterator.tags-1.sentence-1)
To facilitate this, the
library introduces[*category tag*](#def:category_tag "24.4.2 Standard iterator tags [std.iterator.tags]") classes which are used as compile time tags for algorithm selection[.](#std.iterator.tags-1.sentence-2)
They are:output_iterator_tag,input_iterator_tag,forward_iterator_tag,bidirectional_iterator_tag,random_access_iterator_tag,
andcontiguous_iterator_tag[.](#std.iterator.tags-1.sentence-3)
For every iterator of typeI,iterator_traits<I>​::​iterator_category shall be defined to be a category tag that describes the
iterator's behavior[.](#std.iterator.tags-1.sentence-4)
Additionally,iterator_traits<I>​::​iterator_concept may be used to indicate conformance to
the iterator concepts ([[iterator.concepts]](iterator.concepts "24.3.4 Iterator concepts"))[.](#std.iterator.tags-1.sentence-5)
namespace std {struct output_iterator_tag { }; struct input_iterator_tag { }; struct forward_iterator_tag: public input_iterator_tag { }; struct bidirectional_iterator_tag: public forward_iterator_tag { }; struct random_access_iterator_tag: public bidirectional_iterator_tag { }; struct contiguous_iterator_tag: public random_access_iterator_tag { };}
[2](#std.iterator.tags-2)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2788)
[*Example [1](#std.iterator.tags-example-1)*:
A program-defined iterator BinaryTreeIterator can be included into the bidirectional iterator category by
specializing the iterator_traits template:template<class T> struct iterator_traits<BinaryTreeIterator<T>> {using iterator_category = bidirectional_iterator_tag; using difference_type = ptrdiff_t; using value_type = T; using pointer = T*; using reference = T&;};
— *end example*]
[3](#std.iterator.tags-3)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2804)
[*Example [2](#std.iterator.tags-example-2)*:
Ifevolve() is well-defined for bidirectional iterators, but can be implemented more
efficiently for random access iterators, then the implementation is as follows:template<class BidirectionalIterator>inline void evolve(BidirectionalIterator first, BidirectionalIterator last) { evolve(first, last, typename iterator_traits<BidirectionalIterator>::iterator_category());}template<class BidirectionalIterator>void evolve(BidirectionalIterator first, BidirectionalIterator last,
bidirectional_iterator_tag) {// more generic, but less efficient algorithm}template<class RandomAccessIterator>void evolve(RandomAccessIterator first, RandomAccessIterator last,
random_access_iterator_tag) {// more efficient, but less generic algorithm}
— *end example*]
### [24.4.3](#iterator.operations) Iterator operations [[iterator.operations]](iterator.operations)
[1](#iterator.operations-1)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2834)
Since only random access iterators provide+ and- operators, the library provides two
function templatesadvance anddistance[.](#iterator.operations-1.sentence-1)
These
function templates
use+ and- for random access iterators (and are, therefore, constant
time for them); for input, forward and bidirectional iterators they use++ to provide linear time
implementations[.](#iterator.operations-1.sentence-2)
[🔗](#lib:advance)
`template<class InputIterator, class Distance>
constexpr void advance(InputIterator& i, Distance n);
`
[2](#iterator.operations-2)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2863)
*Preconditions*: n is negative only for bidirectional iterators[.](#iterator.operations-2.sentence-1)
[3](#iterator.operations-3)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2868)
*Effects*: Increments i by n if n is non-negative, and
decrements i by -n otherwise[.](#iterator.operations-3.sentence-1)
[🔗](#lib:distance)
`template<class InputIterator>
constexpr typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last);
`
[4](#iterator.operations-4)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2882)
*Preconditions*: last is reachable from first, orInputIterator meets
the *Cpp17RandomAccessIterator* requirements andfirst is reachable from last[.](#iterator.operations-4.sentence-1)
[5](#iterator.operations-5)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2889)
*Effects*: If InputIterator meets the *Cpp17RandomAccessIterator* requirements,
returns (last - first); otherwise, incrementsfirst until last is reached and returns
the number of increments[.](#iterator.operations-5.sentence-1)
[🔗](#lib:next)
`template<class InputIterator>
constexpr InputIterator next(InputIterator x,
typename iterator_traits<InputIterator>::difference_type n = 1);
`
[6](#iterator.operations-6)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2905)
*Effects*: Equivalent to: advance(x, n); return x;
[🔗](#lib:prev)
`template<class BidirectionalIterator>
constexpr BidirectionalIterator prev(BidirectionalIterator x,
typename iterator_traits<BidirectionalIterator>::difference_type n = 1);
`
[7](#iterator.operations-7)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2918)
*Effects*: Equivalent to: advance(x, -n); return x;
### [24.4.4](#range.iter.ops) Range iterator operations [[range.iter.ops]](range.iter.ops)
#### [24.4.4.1](#range.iter.ops.general) General [[range.iter.ops.general]](range.iter.ops.general)
[1](#range.iter.ops.general-1)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2927)
The library includes the function templatesranges​::​advance, ranges​::​distance,ranges​::​next, and ranges​::​prev to manipulate iterators[.](#range.iter.ops.general-1.sentence-1)
These operations adapt to the set of operators
provided by each iterator category to provide the most efficient implementation
possible for a concrete iterator type[.](#range.iter.ops.general-1.sentence-2)
[*Example [1](#range.iter.ops.general-example-1)*:
ranges​::​advance uses the + operator to move a[random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]") forward n steps in constant time[.](#range.iter.ops.general-1.sentence-3)
For an iterator type that does not model [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]"),ranges​::​advance instead performs n individual increments with
the ++ operator[.](#range.iter.ops.general-1.sentence-4)
— *end example*]
[2](#range.iter.ops.general-2)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2942)
The entities defined in [[range.iter.ops]](#range.iter.ops "24.4.4 Range iterator operations") are
algorithm function objects ([[alg.func.obj]](alg.func.obj "16.3.3.4 Algorithm function objects"))[.](#range.iter.ops.general-2.sentence-1)
#### [24.4.4.2](#range.iter.op.advance) ranges​::​advance [[range.iter.op.advance]](range.iter.op.advance)
[🔗](#lib:advance_)
`template<[input_or_output_iterator](iterator.concept.iterator#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") I>
constexpr void ranges::advance(I& i, iter_difference_t<I> n);
`
[1](#range.iter.op.advance-1)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2955)
*Preconditions*: If I does not model [bidirectional_iterator](iterator.concept.bidir#concept:bidirectional_iterator "24.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]"),n is not negative[.](#range.iter.op.advance-1.sentence-1)
[2](#range.iter.op.advance-2)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2960)
*Effects*:
- [(2.1)](#range.iter.op.advance-2.1)
If I models [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]"),
equivalent to i += n[.](#range.iter.op.advance-2.1.sentence-1)
- [(2.2)](#range.iter.op.advance-2.2)
Otherwise, if n is non-negative, increments i by n[.](#range.iter.op.advance-2.2.sentence-1)
- [(2.3)](#range.iter.op.advance-2.3)
Otherwise, decrements i by -n[.](#range.iter.op.advance-2.3.sentence-1)
[🔗](#lib:advance__)
`template<[input_or_output_iterator](iterator.concept.iterator#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I> S>
constexpr void ranges::advance(I& i, S bound);
`
[3](#range.iter.op.advance-3)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2978)
*Preconditions*: Either [assignable_from](concept.assignable#concept:assignable_from "18.4.8 Concept assignable_­from [concept.assignable]")<I&, S> || [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<S, I> is modeled, or
[i, bound) denotes a range[.](#range.iter.op.advance-3.sentence-1)
[4](#range.iter.op.advance-4)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L2983)
*Effects*:
- [(4.1)](#range.iter.op.advance-4.1)
If I and S model [assignable_from](concept.assignable#concept:assignable_from "18.4.8 Concept assignable_­from [concept.assignable]")<I&, S>,
equivalent to i = std​::​move(bound)[.](#range.iter.op.advance-4.1.sentence-1)
- [(4.2)](#range.iter.op.advance-4.2)
Otherwise, if S and I model [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<S, I>,
equivalent to ranges​::​advance(i, bound - i)[.](#range.iter.op.advance-4.2.sentence-1)
- [(4.3)](#range.iter.op.advance-4.3)
Otherwise, while bool(i != bound) is true,
increments i[.](#range.iter.op.advance-4.3.sentence-1)
[🔗](#lib:advance___)
`template<[input_or_output_iterator](iterator.concept.iterator#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I> S>
constexpr iter_difference_t<I> ranges::advance(I& i, iter_difference_t<I> n, S bound);
`
[5](#range.iter.op.advance-5)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3002)
*Preconditions*: If n > 0, [i, bound) denotes a range[.](#range.iter.op.advance-5.sentence-1)
If n == 0, [i, bound) or [bound, i) denotes a range[.](#range.iter.op.advance-5.sentence-2)
If n < 0, [bound, i) denotes a range,I models [bidirectional_iterator](iterator.concept.bidir#concept:bidirectional_iterator "24.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]"), andI and S model [same_as](concept.same#concept:same_as "18.4.2 Concept same_­as [concept.same]")<I, S>[.](#range.iter.op.advance-5.sentence-3)
[6](#range.iter.op.advance-6)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3010)
*Effects*:
- [(6.1)](#range.iter.op.advance-6.1)
If S and I model [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<S, I>:
* [(6.1.1)](#range.iter.op.advance-6.1.1)
If ​|n| ≥ |bound - i|,
equivalent to ranges​::​advance(i, bound)[.](#range.iter.op.advance-6.1.1.sentence-1)
* [(6.1.2)](#range.iter.op.advance-6.1.2)
Otherwise, equivalent to ranges​::​advance(i, n)[.](#range.iter.op.advance-6.1.2.sentence-1)
- [(6.2)](#range.iter.op.advance-6.2)
Otherwise,
* [(6.2.1)](#range.iter.op.advance-6.2.1)
if n is non-negative,
while bool(i != bound) is true,
increments i but at most n times[.](#range.iter.op.advance-6.2.1.sentence-1)
* [(6.2.2)](#range.iter.op.advance-6.2.2)
Otherwise,
while bool(i != bound) is true,
decrements i but at most -n times[.](#range.iter.op.advance-6.2.2.sentence-1)
[7](#range.iter.op.advance-7)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3030)
*Returns*: n - M, where M is the difference between
the ending and starting positions of i[.](#range.iter.op.advance-7.sentence-1)
#### [24.4.4.3](#range.iter.op.distance) ranges​::​distance [[range.iter.op.distance]](range.iter.op.distance)
[🔗](#lib:distance_)
`template<class I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I> S>
requires (![sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<S, I>)
constexpr iter_difference_t<I> ranges::distance(I first, S last);
`
[1](#range.iter.op.distance-1)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3045)
*Preconditions*: [first, last) denotes a range[.](#range.iter.op.distance-1.sentence-1)
[2](#range.iter.op.distance-2)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3049)
*Effects*: Increments first until last is reached and
returns the number of increments[.](#range.iter.op.distance-2.sentence-1)
[🔗](#lib:distance__)
`template<class I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]")<decay_t<I>> S>
constexpr iter_difference_t<decay_t<I>> ranges::distance(I&& first, S last);
`
[3](#range.iter.op.distance-3)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3062)
*Effects*: Equivalent to:if constexpr (!is_array_v<remove_reference_t<I>>)return last - first;elsereturn last - static_cast<decay_t<I>>(first);
[🔗](#lib:distance___)
`template<[range](range.range#concept:range "25.4.2 Ranges [range.range]") R>
constexpr range_difference_t<R> ranges::distance(R&& r);
`
[4](#range.iter.op.distance-4)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3080)
*Effects*: If R models [sized_range](range.sized#concept:sized_range "25.4.4 Sized ranges [range.sized]"), equivalent to:return static_cast<range_difference_t<R>>(ranges::size(r)); // [[range.prim.size]](range.prim.size "25.3.10 ranges​::​size")
Otherwise, equivalent to:return ranges::distance(ranges::begin(r), ranges::end(r)); // [[range.access]](range.access "25.3 Range access")
#### [24.4.4.4](#range.iter.op.next) ranges​::​next [[range.iter.op.next]](range.iter.op.next)
[🔗](#lib:next_)
`template<[input_or_output_iterator](iterator.concept.iterator#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") I>
constexpr I ranges::next(I x);
`
[1](#range.iter.op.next-1)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3101)
*Effects*: Equivalent to: ++x; return x;
[🔗](#lib:next__)
`template<[input_or_output_iterator](iterator.concept.iterator#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") I>
constexpr I ranges::next(I x, iter_difference_t<I> n);
`
[2](#range.iter.op.next-2)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3113)
*Effects*: Equivalent to: ranges​::​advance(x, n); return x;
[🔗](#lib:next___)
`template<[input_or_output_iterator](iterator.concept.iterator#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I> S>
constexpr I ranges::next(I x, S bound);
`
[3](#range.iter.op.next-3)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3125)
*Effects*: Equivalent to: ranges​::​advance(x, bound); return x;
[🔗](#lib:next____)
`template<[input_or_output_iterator](iterator.concept.iterator#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<I> S>
constexpr I ranges::next(I x, iter_difference_t<I> n, S bound);
`
[4](#range.iter.op.next-4)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3137)
*Effects*: Equivalent to: ranges​::​advance(x, n, bound); return x;
#### [24.4.4.5](#range.iter.op.prev) ranges​::​prev [[range.iter.op.prev]](range.iter.op.prev)
[🔗](#lib:prev_)
`template<[bidirectional_iterator](iterator.concept.bidir#concept:bidirectional_iterator "24.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]") I>
constexpr I ranges::prev(I x);
`
[1](#range.iter.op.prev-1)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3150)
*Effects*: Equivalent to: --x; return x;
[🔗](#lib:prev__)
`template<[bidirectional_iterator](iterator.concept.bidir#concept:bidirectional_iterator "24.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]") I>
constexpr I ranges::prev(I x, iter_difference_t<I> n);
`
[2](#range.iter.op.prev-2)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3162)
*Effects*: Equivalent to: ranges​::​advance(x, -n); return x;
[🔗](#lib:prev___)
`template<[bidirectional_iterator](iterator.concept.bidir#concept:bidirectional_iterator "24.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]") I>
constexpr I ranges::prev(I x, iter_difference_t<I> n, I bound);
`
[3](#range.iter.op.prev-3)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/iterators.tex#L3174)
*Effects*: Equivalent to: ranges​::​advance(x, -n, bound); return x;
Reference in New Issue View Git Blame Copy Permalink