Namespaces
Variants
Views
Actions

Difference between revisions of "cpp/iterator/bidirectional iterator"

From cppreference.com
< cpp‎ | iterator
m (→‎See also: +random_access_iterator)
m (in-house fmt.)
 
(3 intermediate revisions by 3 users not shown)
Line 2: Line 2:
 
{{cpp/iterator/navbar}}
 
{{cpp/iterator/navbar}}
 
{{ddcl|header=iterator|since=c++20|1=
 
{{ddcl|header=iterator|since=c++20|1=
−
template<class I>
+
template< class I >
−
  concept bidirectional_iterator =
+
    concept bidirectional_iterator =
−
    std::forward_iterator<I> &&
+
        std::forward_iterator<I> &&
−
    std::derived_from</*ITER_CONCEPT*/<I>, std::bidirectional_iterator_tag> &&
+
        std::derived_from</*ITER_CONCEPT*/<I>, std::bidirectional_iterator_tag> &&
−
    requires(I i) {
+
        requires(I i) {
−
      { --i } -> std::same_as<I&>;
+
            { --i } -> std::same_as<I&>;
−
      { i-- } -> std::same_as<I>;
+
            { i-- } -> std::same_as<I>;
−
    };
+
        };
 
}}
 
}}
  
Line 19: Line 19:
 
A bidirectional iterator {{tt|r}} is said to be ''decrementable'' if and only if there exists some {{tt|s}} such that {{c|1=++s == r}}.
 
A bidirectional iterator {{tt|r}} is said to be ''decrementable'' if and only if there exists some {{tt|s}} such that {{c|1=++s == r}}.
  
−
{{tt|bidirectional_iterator&lt;I>}} is modeled only if all the concepts it subsumes are modeled, and given two objects {{tt|a}} and {{tt|b}} of type {{tt|I}}:
+
{{co|std::bidirectional_iterator<I>}} is modeled only if all the concepts it subsumes are modeled, and given two objects {{tt|a}} and {{tt|b}} of type {{tt|I}}:
 
* If {{tt|a}} is decrementable, {{tt|a}} is in the domain of the expressions {{c|--a}} and {{c|a--}}.
 
* If {{tt|a}} is decrementable, {{tt|a}} is in the domain of the expressions {{c|--a}} and {{c|a--}}.
−
* Pre-decrement yields an lvalue that refers to the operand: {{c|1=std::addressof(--a) == std::addressof(a)}};
+
* Pre-decrement yields an lvalue that refers to the operand: {{c|1=std::addressof(--a) == std::addressof(a)}}.
 
* Post-decrement yields the previous value of the operand: if {{c|1=bool(a == b)}}, then {{c|1=bool(a-- == b)}}.
 
* Post-decrement yields the previous value of the operand: if {{c|1=bool(a == b)}}, then {{c|1=bool(a-- == b)}}.
−
* Post-decrement and pre-decrement perform the same modification on its operand: If {{c|1=bool(a == b)}}, then after evaluating both {{tt|a--}} and {{tt|--b}}, {{c|1=bool(a == b)}} still holds.
+
* Post-decrement and pre-decrement perform the same modification on its operand: If {{c|1=bool(a == b)}}, then after evaluating both {{c|a--}} and {{c|--b}}, {{c|1=bool(a == b)}} still holds.
 
* Increment and decrement are inverses of each other:
 
* Increment and decrement are inverses of each other:
 
:* If {{tt|a}} is incrementable and {{c|1=bool(a == b)}}, then {{c|1=bool(--(++a) == b)}}.
 
:* If {{tt|a}} is incrementable and {{c|1=bool(a == b)}}, then {{c|1=bool(--(++a) == b)}}.
Line 30: Line 30:
 
{{cpp/concepts/equality preservation}}
 
{{cpp/concepts/equality preservation}}
  
−
=== Notes ===
+
===Notes===
 
Unlike the {{named req|BidirectionalIterator}} requirements, the {{tt|bidirectional_iterator}} concept does not require dereference to return an lvalue.
 
Unlike the {{named req|BidirectionalIterator}} requirements, the {{tt|bidirectional_iterator}} concept does not require dereference to return an lvalue.
 +
 +
===Example===
 +
A minimum bidirectional iterator.
 +
 +
{{source|1=
 +
#include <cstddef>
 +
#include <iterator>
 +
 +
struct SimpleBidiIterator
 +
{
 +
    using difference_type = std::ptrdiff_t;
 +
    using value_type = int;
 +
 +
    int operator*() const;
 +
 +
    SimpleBidiIterator& operator++();
 +
 +
    SimpleBidiIterator operator++(int)
 +
    {
 +
        auto tmp = *this;
 +
        ++*this;
 +
        return tmp;
 +
    }
 +
 +
    SimpleBidiIterator& operator--();
 +
 +
    SimpleBidiIterator operator--(int)
 +
    {
 +
        auto tmp = *this;
 +
        --*this;
 +
        return tmp;
 +
    }
 +
 +
    bool operator==(const SimpleBidiIterator&) const;
 +
};
 +
 +
static_assert(std::bidirectional_iterator<SimpleBidiIterator>);
 +
}}
  
 
===See also===
 
===See also===

Latest revision as of 13:34, 13 May 2024

 
C++
 
Iterator library
Iterator concepts
(C++20)
bidirectional_iterator
(C++20)
(C++20)
(C++20)


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)
 
Defined in header <iterator>
template< class I >

    concept bidirectional_iterator =
        std::forward_iterator<I> &&
        std::derived_from</*ITER_CONCEPT*/<I>, std::bidirectional_iterator_tag> &&
        requires(I i) {
            { --i } -> std::same_as<I&>;
            { i-- } -> std::same_as<I>;

        };
 (since C++20)

The concept bidirectional_iterator refines forward_iterator by adding the ability to move an iterator backward.

Contents

[edit] Iterator concept determination

Definition of this concept is specified via an exposition-only alias template /*ITER_CONCEPT*/.

In order to determine /*ITER_CONCEPT*/<I>, let ITER_TRAITS<I> denote I if the specialization std::iterator_traits<I> is generated from the primary template, or std::iterator_traits<I> otherwise:

  • If ITER_TRAITS<I>::iterator_concept is valid and names a type, /*ITER_CONCEPT*/<I> denotes the type.
  • Otherwise, if ITER_TRAITS<I>::iterator_category is valid and names a type, /*ITER_CONCEPT*/<I> denotes the type.
  • Otherwise, if std::iterator_traits<I> is generated from the primary template, /*ITER_CONCEPT*/<I> denotes std::random_access_iterator_tag.
  • Otherwise, /*ITER_CONCEPT*/<I> does not denote a type and results in a substitution failure.

[edit] Semantic requirements

A bidirectional iterator r is said to be decrementable if and only if there exists some s such that ++s == r.

std::bidirectional_iterator<I> is modeled only if all the concepts it subsumes are modeled, and given two objects a and b of type I:

  • If a is decrementable, a is in the domain of the expressions --a and a--.
  • Pre-decrement yields an lvalue that refers to the operand: std::addressof(--a) == std::addressof(a).
  • Post-decrement yields the previous value of the operand: if bool(a == b), then bool(a-- == b).
  • Post-decrement and pre-decrement perform the same modification on its operand: If bool(a == b), then after evaluating both a-- and --b, bool(a == b) still holds.
  • Increment and decrement are inverses of each other:
  • If a is incrementable and bool(a == b), then bool(--(++a) == b).
  • If a is decrementable and bool(a == b), then bool(++(--a) == b).

[edit] Equality preservation

Expressions declared in requires expressions of the standard library concepts are required to be equality-preserving (except where stated otherwise).

[edit] Notes

Unlike the LegacyBidirectionalIterator requirements, the bidirectional_iterator concept does not require dereference to return an lvalue.

[edit] Example

A minimum bidirectional iterator. 

#include <cstddef>
#include <iterator>
 
struct SimpleBidiIterator
{
    using difference_type = std::ptrdiff_t;
    using value_type = int;
 
    int operator*() const;
 
    SimpleBidiIterator& operator++();
 
    SimpleBidiIterator operator++(int)
    {
        auto tmp = *this;
        ++*this;
        return tmp;
    }
 
    SimpleBidiIterator& operator--();
 
    SimpleBidiIterator operator--(int)
    {
        auto tmp = *this;
        --*this;
        return tmp;
    }
 
    bool operator==(const SimpleBidiIterator&) const;
};
 
static_assert(std::bidirectional_iterator<SimpleBidiIterator>);

[edit] See also

(C++20)
 specifies that an input_iterator is a forward iterator, supporting equality comparison and multi-pass
(concept) [edit]
(C++20)
 specifies that a bidirectional_iterator is a random-access iterator, supporting advancement in constant time and subscripting
(concept) [edit]
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/iterator/bidirectional_iterator&oldid=171722"