Conceitos do iterador

Os conceitos são um recurso da linguagem C++20 que restringe os parâmetros de modelo em tempo de compilação. Eles ajudam a evitar a instanciação incorreta do modelo, especificam os requisitos de argumento do modelo em um formato legível e fornecem erros de compilador relacionados ao modelo mais sucintos.

Considere o exemplo a seguir, que define um conceito para evitar instanciar o modelo com um tipo que não dá suporte à divisão:

// requires /std:c++20 or later
#include <iostream>

// Definition of dividable concept which requires 
// that arguments a & b of type T support division
template <typename T>
concept dividable = requires (T a, T b)
{
    a / b;
};

// Apply the concept to a template.
// The template will only be instantiated if argument T supports division.
// This prevents the template from being instantiated with types that don't support division.
// This could have been applied to the parameter of a template function, but because
// most of the concepts in the <ranges> library are applied to classes, this form is demonstrated.
template <class T> requires dividable<T>
class DivideEmUp
{
public:
    T Divide(T x, T y)
    {
        return x / y;
    }
};

int main()
{
    DivideEmUp<int> dividerOfInts;
    std::cout << dividerOfInts.Divide(6, 3); // outputs 2
    // The following line will not compile because the template can't be instantiated 
    // with char* because char* can be divided
    DivideEmUp<char*> dividerOfCharPtrs; // compiler error: cannot deduce template arguments 
}

Quando você passa a opção /diagnostics:caret do compilador para o Visual Studio 2022 versão 17.4 versão prévia 4 ou posterior, o erro que o conceito dividable<char*> avaliou como falso apontará diretamente para o requisito (a / b) de expressão que falhou.

Os conceitos do iterador são definidos no std namespace e são declarados <iterator> no arquivo de cabeçalho. Eles são usados nas declarações de adaptadores de intervalo, exibições e assim por diante.

Existem seis categorias de iteradores. Eles estão diretamente relacionados às categorias de intervalos listadas em Conceitos de intervalo.

Os conceitos de iterador a seguir são listados em ordem crescente de capacidade. input_or_output_iterator está na extremidade inferior da hierarquia de capacidade e contiguous_iterator está na extremidade superior. Os iteradores mais altos na hierarquia geralmente podem ser usados no lugar daqueles que são mais baixos, mas não vice-versa. Por exemplo, um random_access_iterator iterador pode ser usado no lugar de um forward_iterator, mas não o contrário. Uma exceção é input_iterator, que não pode ser usado no lugar de output_iterator porque não pode gravar.

Na tabela a seguir, "Multi-pass" refere-se a se o iterador pode revisitar o mesmo elemento mais de uma vez. Por exemplo, vector::iterator é um iterador de várias passagens porque você pode fazer uma cópia do iterador, ler os elementos na coleção e, em seguida, restaurar o iterador para o valor na cópia e revisitar os mesmos elementos novamente. Se um iterador for de passagem única, você só poderá visitar os elementos na coleção uma vez.

Na tabela a seguir, "Tipos de exemplo" refere-se a coleções/iteradores que atendem ao conceito.

Conceito de iterador	Descrição	Direção	Leitura/gravação	Passagem múltipla	Tipos de exemplo
input_or_output_iteratorC++20	A base da taxonomia do conceito do iterador.	Antecipado	Leitura/gravação	não	istream_iterator, ostream_iterator
output_iteratorC++20	Especifica um iterador no qual você pode gravar.	Antecipado	Gravar	não	ostream, inserter
input_iteratorC++20	Especifica um iterador do qual você pode ler uma vez.	Antecipado	Ler	não	istream, istreambuf_iterator
forward_iteratorC++20	Especifica um iterador que pode ler (e possivelmente gravar) várias vezes.	Antecipado	Leitura/gravação	sim	vector, list
bidirectional_iteratorC++20	Especifica um iterador que você pode ler e gravar para frente e para trás.	Avançar ou recuar	Leitura/gravação	sim	..................list, set, multiset, map e multimap.
random_access_iteratorC++20	Especifica um iterador que você pode ler e gravar por índice.	Avançar ou recuar	Leitura/gravação	sim	vector, array, deque
contiguous_iteratorC++20	Especifica um iterador cujos elementos são sequenciais na memória, têm o mesmo tamanho e podem ser acessados usando aritmética de ponteiro.	Avançar ou recuar	Leitura/gravação	sim	array, vector string.

Outros conceitos de iterador incluem:

Conceito de iterador	Descrição
sentinel_forC++20	Especifica que um tipo é um sentinela para um tipo de iterador.
sized_sentinel_forC++20	Especifica que um iterador e seu sentinela podem ser subtraídos (usando -) para encontrar sua diferença em tempo constante.

bidirectional_iterator

A bidirectional_iterator suporta leitura e escrita para frente e para trás.

template<class I>
concept bidirectional_iterator =
    forward_iterator<I> &&
    derived_from<ITER_CONCEPT(I), bidirectional_iterator_tag> &&
    requires(I i) {
        {--i} -> same_as<I&>;
        {i--} -> same_as<I>;
};

Parâmetros

I
O iterador a ser testado para ver se é um bidirectional_iteratorarquivo .

Comentários

A bidirectional_iterator tem os recursos de um forward_iterator, mas também pode iterar para trás.

Alguns exemplos de contêineres que podem ser usados com um bidirectional_iterator são , multiset, map, multimap, e vectorlist.set

Exemplo: bidirectional_iterator

O exemplo a seguir usa o bidirectional_iterator conceito para mostrar que vector<int> tem um bidirectional_iterator:

// requires /std:c++20 or later
#include <iostream>
#include <vector>

int main()
{
    std::cout << std::boolalpha << std::bidirectional_iterator<std::vector<int>::iterator> << '\n'; // outputs "true"

    // another way to test
    std::vector<int> v = {0,1,2};
    std::cout << std::boolalpha << std::contiguous_iterator<decltype(v)::iterator>; // outputs true
}

contiguous_iterator

Especifica um iterador cujos elementos são sequenciais na memória, têm o mesmo tamanho e podem ser acessados usando aritmética de ponteiro.

template<class I>
    concept contiguous_iterator =
        random_access_iterator<I> &&
        derived_from<ITER_CONCEPT(I), contiguous_iterator_tag> &&
        is_lvalue_reference_v<iter_reference_t<I>> &&
        same_as<iter_value_t<I>, remove_cvref_t<iter_reference_t<I>>> &&
        requires(const I& i) {
            { to_address(i) } -> same_as<add_pointer_t<iter_reference_t<I>>>;
        };

Parâmetros

I
O tipo a ser testado para ver se é um contiguous_iteratorarquivo .

Comentários

A contiguous_iterator pode ser acessado por aritmética de ponteiro porque os elementos são dispostos sequencialmente na memória e têm o mesmo tamanho. Alguns exemplos de um contiguous_iterator são array, vector, e string.

Exemplo: contiguous_iterator

O exemplo a seguir usa o contiguous_iterator conceito para mostrar que a vector<int> tem um contiguous_iterator:

// requires /std:c++20 or later
#include <iostream>
#include <vector>

int main()
{
    // Show that vector<int> has a contiguous_iterator
    std::cout << std::boolalpha << std::contiguous_iterator<std::vector<int>::iterator> << '\n'; // outputs "true"
    
    // another way to test
    std::vector<int> v = {0,1,2};
    std::cout << std::boolalpha << std::contiguous_iterator<decltype(v)::iterator>; // outputs true
}

forward_iterator

Tem os recursos de um input_iterator e um output_iterator. Dá suporte à iteração em uma coleção várias vezes.

template<class I>
    concept forward_iterator =
        input_iterator<I> &&
        derived_from<ITER_CONCEPT(I), forward_iterator_tag> &&
        incrementable<I> &&
        sentinel_for<I, I>;

Parâmetros

I
O iterador a ser testado para ver se é um forward_iteratorarquivo .

Comentários

A forward_iterator só pode seguir em frente.

Alguns exemplos de contêineres que podem ser usados com um forward_iterator são , list, unordered_set, unordered_multiset, e unordered_mapunordered_multimap.vector

Exemplo: forward_iterator

O exemplo a seguir usa o forward_iterator conceito para mostrar que a vector<int> tem um forward_iterator:

// requires /std:c++20 or later
#include <iostream>
#include <vector>

int main()
{
    // Show that vector has a forward_iterator
    std::cout << std::boolalpha << std::forward_iterator<std::vector<int>::iterator> << '\n'; // outputs "true"

    // another way to test
    std::vector<int> v = {0,1,2};
    std::cout << std::boolalpha << std::forward_iterator<decltype(v)::iterator>; // outputs true
}

input_iterator

An input_iterator é um iterador que você pode ler pelo menos uma vez.

template<class I>
concept input_iterator =
    input_or_output_iterator<I> &&
    indirectly_readable<I> &&
    requires { typename ITER_CONCEPT(I); } &&
    derived_from<ITER_CONCEPT(I), input_iterator_tag>;

Parâmetros

I
O tipo a ser testado para ver se é um input_iteratorarquivo .

Comentários

Chamar begin() um input_iterator mais de uma vez resulta em comportamento indefinido. Um tipo que apenas modela input_iterator não é multi-pass. Considere a leitura da entrada padrão (cin), por exemplo. Nesse caso, você só pode ler o elemento atual uma vez e não pode reler os caracteres que já leu. An input_iterator só lê para frente, não para trás.

Exemplo: input_iterator

O exemplo a seguir usa o input_iterator conceito para mostrar que an istream_iterator tem um input_iterator:

// requires /std:c++20 or later
#include <iostream>

int main()
{
    // Show that a istream_iterator has an input_iterator
    std::cout << std::boolalpha << std::input_iterator<std::istream_iterator<int>>; // outputs true
}

input_or_output_iterator

An input_or_output_iterator é a base da taxonomia do conceito do iterador. Ele dá suporte à desreferenciação e ao incremento de um iterador. Cada iterador modela input_or_output_iterator.

template<class I>
concept input_or_output_iterator =
    requires(I i) {
        { *i } -> can-reference;
    } &&
    weakly_incrementable<I>;

Parâmetros

I
O tipo a ser testado para ver se é um input_or_output_iteratorarquivo .

Comentários

O conceito can-reference significa que o tipo I é uma referência, um ponteiro ou um tipo que pode ser convertido implicitamente em uma referência.

Exemplo: input_or_output_iterator

O exemplo a seguir usa o input_or_output_iterator conceito para mostrar que vector<int> tem um input_or_output_iterator:

// requires /std:c++20 or later
#include <iostream>

int main()
{
    // Show that a vector has an input_or_output_iterator
    std::cout << std::boolalpha << std::input_or_output_iterator<std::vector<int>::iterator> << '\n'; // outputs true

    // another way to test
    std::vector<int> v = {0,1,2};
    std::cout << std::boolalpha << std::input_or_output_iterator<decltype(v)::iterator>; // outputs true
}

output_iterator

An output_iterator é um iterador no qual você pode escrever.

template<class I, class T>
concept output_iterator =
    input_or_output_iterator<I> &&
    indirectly_writable<I, T> &&
    requires(I i, T&& t) {
        *i++ = std::forward<T>(t);
    };

Parâmetros

I
O tipo a ser testado para ver se é um output_iteratorarquivo .

T
O tipo dos valores a serem gravados.

Comentários

Um output_iterator é uma única passagem. Ou seja, ele só pode gravar no mesmo elemento uma vez.

Exemplo: output_iterator

O exemplo a seguir usa o output_iterator conceito para mostrar que vector<int> tem um output_iterator:

// requires /std:c++20 or later
#include <iostream>
#include <vector>

int main()
{
    // Show that vector<int> has an output_iterator
    std::cout << std::boolalpha << std::output_iterator<std::vector<int>::iterator, int> << "\n"; // outputs "true"

    // another way to test
    std::vector<int> v = {0,1,2,3,4,5};
    std::cout << std::boolalpha << std::output_iterator<decltype(v)::iterator, int>; // outputs true
}

random_access_iterator

A random_access_iterator pode ler ou escrever por índice.

template<class I>
concept random_access_iterator =
    bidirectional_iterator<I> &&
    derived_from<ITER_CONCEPT(I), random_access_iterator_tag> &&
    totally_ordered<I> &&
    sized_sentinel_for<I, I> &&
    requires(I i, const I j, const iter_difference_t<I> n) {
        { i += n } -> same_as<I&>;
        { j + n } -> same_as<I>;
        { n + j } -> same_as<I>;
        { i -= n } -> same_as<I&>;
        { j - n } -> same_as<I>;
        { j[n] } -> same_as<iter_reference_t<I>>;
    };

Parâmetros

I
O tipo a ser testado para ver se é um random_access_iteratorarquivo .

Comentários

A random_access_iterator tem as capacidades de um input_iterator, output_iterator, forward_iteratore bidirectional_iterator.

Alguns exemplos de um random_access_iterator são vector, array, e deque.

Exemplo: random_access_iterator

O exemplo a seguir mostra que a tem um vector<int> random_access_iterator:

// requires /std:c++20 or later
#include <iostream>
#include <vector>

int main()
{
    // Show that vector<int> has a random_access_iterator
    std::cout << std::boolalpha << std::random_access_iterator<std::vector<int>::iterator> << '\n'; // outputs "true"

    // another way to test
    std::vector<int> v = {0,1,2};
    std::cout << std::boolalpha << std::random_access_iterator<decltype(v)::iterator>; // outputs true
}    

sentinel_for

Especifica que um tipo é um sentinela para um iterador.

template<class S, class I>
concept sentinel_for =
    semiregular<S> &&
    input_or_output_iterator<I> &&
    weakly-equality-comparable-with <S, I>;

Parâmetros

I
O tipo de iterador.

S
O tipo a ser testado para ver se é uma sentinela para I.

Comentários

Um sentinela é um tipo que pode ser comparado a um iterador para determinar se o iterador chegou ao fim. Esse conceito determina se um tipo é um sentinela input_or_output_iterator para um dos tipos, que inclui input_iterator, output_iterator, forward_iterator, bidirectional_iterator, , random_access_iteratore contiguous_iterator.

Exemplo: sentinel_for

O exemplo a seguir usa o sentinel_for conceito para mostrar que vector<int>::iterator é uma sentinela para vector<int>:

// requires /std:c++20 or later
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = {0, 1, 2};
    std::vector<int>::iterator i = v.begin();
    // show that vector<int>::iterator is a sentinel for vector<int>
    std::cout << std::boolalpha << std::sentinel_for<std::vector<int>::iterator, decltype(i)>; // outputs true
}    

sized_sentinel_for

Teste se um iterador e sua sentinela podem ser subtraídos usando - para encontrar a diferença, em tempo constante.

template<class S, class I>
concept sized_sentinel_for =
    sentinel_for<S, I> &&
    !disable_sized_sentinel_for<remove_cv_t<S>, remove_cv_t<I>> &&
    requires(const I& i, const S& s) {
        {s - i} -> same_as<iter_difference_t<I>>;
        {i - s} -> same_as<iter_difference_t<I>>;
    };

Parâmetros

I
O tipo de iterador.

S
O tipo sentinela a ser testado.

Comentários

Exemplo: sized_sentinel_for

O exemplo a seguir usa o sized_sentinel_for conceito para verificar se os fóruns vector<int> sentinela podem ser subtraídos do iterador de vetores em tempo constante:

// requires /std:c++20 or later
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = { 1, 2, 3 };
    std::vector<int>::iterator i = v.begin();
    std::vector<int>::iterator end = v.end();
    // use the sized_sentinel_for concept to verify that i can be subtracted from end in constant time
    std::cout << std::boolalpha << std::sized_sentinel_for<decltype(end), decltype(i)> << "\n"; // outputs true
    std::cout << end - i; // outputs 3
}    

Confira também

Conceitos de alcance
Adaptadores de gama
Ver aulas