Namespaces
Variants
Views
Actions

Difference between revisions of "cpp/iterator"

From cppreference.com
< cpp
m (P1878R1 rename)
(→‎Range access: expand "range access availability")
Line 141: Line 141:
 
These non-member functions provide a generic interface for containers, plain arrays, and {{lc|std::initializer_list}}.
 
These non-member functions provide a generic interface for containers, plain arrays, and {{lc|std::initializer_list}}.
 
{{dsc begin}}
 
{{dsc begin}}
 +
{{dsc header | array}}
 +
{{dsc header | deque}}
 +
{{dsc header | forward_list}}
 
{{dsc header | iterator}}
 
{{dsc header | iterator}}
 +
{{dsc header | list}}
 +
{{dsc header | map}}
 +
{{dsc header | regex}}
 +
{{dsc header | set}}
 +
{{dsc header | span}}
 +
{{dsc header | string}}
 +
{{dsc header | string_view}}
 +
{{dsc header | unordered_map}}
 +
{{dsc header | unordered_set}}
 +
{{dsc header | vector}}
 
{{dsc namespace | std}}
 
{{dsc namespace | std}}
 
{{dsc inc | cpp/iterator/dsc begin}}
 
{{dsc inc | cpp/iterator/dsc begin}}

Revision as of 20:14, 6 April 2020

 
C++
 
Iterator library
Iterator concepts
Iterator primitives
Algorithm concepts and utilities
Indirect callable concepts
Common algorithm requirements
(C++20)
(C++20)
(C++20)
Utilities
(C++20)
Iterator adaptors
Range access
(C++11)(C++14)
(C++14)(C++14)  
(C++11)(C++14)
(C++14)(C++14)  
(C++17)(C++20)
(C++17)
(C++17)
 

The iterator library provides definitions for five(until C++17)six(since C++17) kinds of iterators as well as iterator traits, adaptors, and utility functions.

Contents

Iterator categories

There are five(until C++17)six(since C++17) kinds of iterators: LegacyInputIterator, LegacyOutputIterator, LegacyForwardIterator, LegacyBidirectionalIterator, LegacyRandomAccessIterator, and LegacyContiguousIterator(since C++17).

Instead of being defined by specific types, each category of iterator is defined by the operations that can be performed on it. This definition means that any type that supports the necessary operations can be used as an iterator -- for example, a pointer supports all of the operations required by LegacyRandomAccessIterator, so a pointer can be used anywhere a LegacyRandomAccessIterator is expected.

All of the iterator categories (except LegacyOutputIterator) can be organized into a hierarchy, where more powerful iterator categories (e.g. LegacyRandomAccessIterator) support the operations of less powerful categories (e.g. LegacyInputIterator). If an iterator falls into one of these categories and also satisfies the requirements of LegacyOutputIterator, then it is called a mutable iterator and supports both input and output. Non-mutable iterators are called constant iterators.

Iterator category Defined operations
LegacyContiguousIterator LegacyRandomAccessIterator LegacyBidirectionalIterator LegacyForwardIterator LegacyInputIterator
  • read
  • increment (without multiple passes)
  • increment (with multiple passes)
  • decrement
  • random access
  • contiguous storage

Iterators that fall into one of the above categories and also meet the requirements of LegacyOutputIterator are called mutable iterators.

LegacyOutputIterator
  • write
  • increment (without multiple passes)

Note: LegacyContiguousIterator category was only formally specified in C++17, but the iterators of std::vector, std::basic_string, std::array, and std::valarray, as well as pointers into C arrays are often treated as a separate category in pre-C++17 code.


C++20 iterator concepts

C++20 introduces a new system of iterators based on concepts that are different from C++17 iterators. While the basic taxonomy remains similar, the requirements for individual iterator categories are somewhat different.

Defined in namespace std
(C++20)
 specifies that a type is indirectly readable by applying operator *
(concept) [edit]
(C++20)
 specifies that a value can be written to an iterator's referenced object
(concept) [edit]
(C++20)
 specifies that a semiregular type can be incremented with pre- and post-increment operators
(concept) [edit]
(C++20)
 specifies that the increment operation on a weakly_incrementable type is equality-preserving and that the type is equality_comparable
(concept) [edit]
(C++20)
 specifies that objects of a type can be incremented and dereferenced
(concept) [edit]
(C++20)
 specifies a type is a sentinel for an input_or_output_iterator type
(concept) [edit]
(C++20)
 specifies that the - operator can be applied to an iterator and a sentinel to calculate their difference in constant time
(concept) [edit]
(C++20)
 specifies that a type is an input iterator, that is, its referenced values can be read and it can be both pre- and post-incremented
(concept) [edit]
(C++20)
 specifies that a type is an output iterator for a given value type, that is, values of that type can be written to it and it can be both pre- and post-incremented
(concept) [edit]
(C++20)
 specifies that an input_iterator is a forward iterator, supporting equality comparison and multi-pass
(concept) [edit]
(C++20)
 specifies that a forward_iterator is a bidirectional iterator, supporting movement backwards
(concept) [edit]
(C++20)
 specifies that a bidirectional_iterator is a random-access iterator, supporting advancement in constant time and subscripting
(concept) [edit]
(C++20)
 specifies that a random_access_iterator is a contiguous iterator, referring to elements that are contiguous in memory
(concept) [edit]

Iterator associated types

Defined in namespace std
(C++20)
 computes the difference type of a weakly_incrementable type
(class template) [edit]
(C++20)
 computes the value type of an indirectly_readable type
(class template) [edit]
(C++20)(C++20)(C++23)(C++20)(C++20)(C++20)
 computes the associated types of an iterator
(alias template)[edit]

Iterator customization points

Defined in namespace std::ranges
(C++20)
 casts the result of dereferencing an object to its associated rvalue reference type
(customization point object)[edit]
(C++20)
 swaps the values referenced by two dereferenceable objects
(customization point object)[edit]
(since C++20)

Iterator primitives

provides uniform interface to the properties of an iterator
(class template) [edit]
(C++20)
 empty class types used to indicate iterator categories
(class) [edit]
(deprecated in C++17)
 base class to ease the definition of required types for simple iterators
(class template) [edit]

Iterator adaptors

iterator adaptor for reverse-order traversal
(class template) [edit]
(C++14)
 creates a std::reverse_iterator of type inferred from the argument
(function template) [edit]
(C++11)
 iterator adaptor which dereferences to an rvalue
(class template) [edit]
(C++20)
 sentinel adaptor for std::move_iterator
(class template) [edit]
(C++11)
 creates a std::move_iterator of type inferred from the argument
(function template) [edit]
(C++20)
 adapts an iterator type and its sentinel into a common iterator type
(class template) [edit]
(C++20)
 default sentinel for use with iterators that know the bound of their range
(class) [edit]
(C++20)
 iterator adaptor that tracks the distance to the end of the range
(class template) [edit]
(C++20)
 sentinel that always compares unequal to any weakly_incrementable type
(class) [edit]
iterator adaptor for insertion at the end of a container
(class template) [edit]
creates a std::back_insert_iterator of type inferred from the argument
(function template) [edit]
iterator adaptor for insertion at the front of a container
(class template) [edit]
creates a std::front_insert_iterator of type inferred from the argument
(function template) [edit]
iterator adaptor for insertion into a container
(class template) [edit]
creates a std::insert_iterator of type inferred from the argument
(function template) [edit]

Stream iterators

input iterator that reads from std::basic_istream
(class template) [edit]
output iterator that writes to std::basic_ostream
(class template) [edit]
input iterator that reads from std::basic_streambuf
(class template) [edit]
output iterator that writes to std::basic_streambuf
(class template) [edit]

Iterator operations

Defined in header <iterator>
advances an iterator by given distance
(function template) [edit]
returns the distance between two iterators
(function template) [edit]
(C++11)
 increment an iterator
(function template) [edit]
(C++11)
 decrement an iterator
(function template) [edit]
(C++20)
 advances an iterator by given distance or to a given bound
(niebloid)[edit]
(C++20)
 returns the distance between an iterator and a sentinel, or between the beginning and end of a range
(niebloid)[edit]
(C++20)
 increment an iterator by a given distance or to a bound
(niebloid)[edit]
(C++20)
 decrement an iterator by a given distance or to a bound
(niebloid)[edit]

Range access

These non-member functions provide a generic interface for containers, plain arrays, and std::initializer_list.

Defined in header <array>
Defined in header <deque>
Defined in header <forward_list>
Defined in header <iterator>
Defined in header <list>
Defined in header <map>
Defined in header <regex>
Defined in header <set>
Defined in header <span>
Defined in header <string>
Defined in header <string_view>
Defined in header <unordered_map>
Defined in header <unordered_set>
Defined in header <vector>
Defined in namespace std
(C++11)(C++14)
 returns an iterator to the beginning of a container or array
(function template) [edit]
(C++11)(C++14)
 returns an iterator to the end of a container or array
(function template) [edit]
(C++14)
 returns a reverse iterator to the beginning of a container or array
(function template) [edit]
(C++14)
 returns a reverse end iterator for a container or array
(function template) [edit]
(C++17)(C++20)
 returns the size of a container or array
(function template) [edit]
(C++17)
 checks whether the container is empty
(function template) [edit]
(C++17)
 obtains the pointer to the underlying array
(function template) [edit]
Defined in header <ranges>
Defined in namespace std::ranges
(C++20)
 returns an iterator to the beginning of a range
(customization point object)[edit]
(C++20)
 returns a sentinel indicating the end of a range
(customization point object)[edit]
(C++20)
 returns a reverse iterator to a range
(customization point object)[edit]
(C++20)
 returns a reverse end iterator to a range
(customization point object)[edit]
(C++20)
 returns an integer equal to the size of a range
(customization point object)[edit]
(C++20)
 checks whether a range is empty
(customization point object)[edit]
(C++20)
 obtains a pointer to the beginning of a contiguous range
(customization point object)[edit]
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/iterator&oldid=117541"