Основные понятия итератора

Основные понятия — это функция языка C++20, которая ограничивает параметры шаблона во время компиляции. Они помогают предотвратить неправильное создание экземпляра шаблона, указать требования к аргументам шаблона в доступной для чтения форме и предоставить более краткие ошибки, связанные с компилятором.

Рассмотрим следующий пример, который определяет концепцию, чтобы предотвратить создание экземпляра шаблона с типом, который не поддерживает разделение:

// 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 
}

При передаче компилятора в /diagnostics:caret Visual Studio 2022 версии 17.4 предварительной версии 4 или более поздней версии ошибка, которая оценивается как false, указывает непосредственно на требование dividable<char*>(a / b) выражения, которое завершилось сбоем.

Основные понятия итератора определяются в std пространстве имен и объявляются в файле заголовка <iterator> . Они используются в объявлениях адаптеров диапазона, представлений и т. д.

Существует шесть категорий итераторов. Они напрямую связаны с категориями диапазонов, перечисленных в разделе "Основные понятия диапазона".

Следующие понятия итератора перечислены в порядке увеличения возможностей. input_or_output_iterator находится в нижней части иерархии возможностей и contiguous_iterator находится на высоком уровне. Итераторы выше в иерархии, как правило, можно использовать вместо тех, которые ниже, но не наоборот. Например, random_access_iterator итератор можно использовать вместо forward_iteratorитератора, но не наоборот. Исключение — это input_iteratorисключение, которое нельзя использовать вместо output_iterator нее, так как он не может записываться.

В следующей таблице "Multi-pass" указывает, может ли итератор повторно вернуть один и тот же элемент несколько раз. Например, vector::iterator является многоадровным итератором, так как вы можете сделать копию итератора, считывать элементы в коллекции, а затем восстанавливать итератор до значения в копии, а затем повторно возвращать те же элементы. Если итератор является однопроходным, вы можете посетить только элементы коллекции один раз.

В следующей таблице "Примеры типов" относится к коллекциям и итераторам, удовлетворяющим концепции.

Концепция итератора	Описание	Направление	Чтение/запись	Многопроходная передача	Примеры типов
input_or_output_iterator C++20	Основа итеромии концепции таксономии.	Переслать	Чтение/запись	нет	istream_iterator, ostream_iterator
output_iterator C++20	Указывает итератор, в который можно написать.	Переслать	Напишите	нет	ostream, inserter
input_iterator C++20	Указывает итератор, который можно прочитать один раз.	Переслать	Читать	нет	istream, istreambuf_iterator
forward_iterator C++20	Указывает итератор, который может читать (и, возможно, записывать) несколько раз.	Переслать	Чтение/запись	да	vector, list
bidirectional_iterator C++20	Указывает итератор, который можно читать и записывать как вперед, так и назад.	Вперед или назад	Чтение/запись	да	list, set, multiset, map и multimap.
random_access_iterator C++20	Указывает итератор, который можно читать и записывать по индексу.	Вперед или назад	Чтение/запись	да	vector, , arraydeque
contiguous_iterator C++20	Указывает итератор, элементы которого последовательно находятся в памяти, имеют одинаковый размер и могут быть доступны с помощью арифметики указателя.	Вперед или назад	Чтение/запись	да	array, , vectorstring.

К другим понятиям итератора относятся:

Концепция итератора	Описание
sentinel_for C++20	Указывает, что тип является sentinel для типа итератора.
sized_sentinel_for C++20	Указывает, что итератор и его sentinel можно вычитать (используя -), чтобы найти их разницу в постоянном времени.

bidirectional_iterator

Поддерживает bidirectional_iterator чтение и запись вперед и назад.

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>;
};

Параметры

I
Итератор для проверки, чтобы узнать, является bidirectional_iteratorли это .

Замечания

A имеет возможности объекта bidirectional_iteratorforward_iterator, но также может выполнять итерацию назад.

Некоторые примеры контейнеров, которые можно использовать с помощью bidirectional_iteratorset: , multiset, map, multimap, vectorи list.

Пример: bidirectional_iterator

В следующем примере используется концепция, показывающая, bidirectional_iterator что vector<int> имеет :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

Указывает итератор, элементы которого последовательно находятся в памяти, имеют одинаковый размер и могут быть доступны с помощью арифметики указателя.

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>>>;
        };

Параметры

I
Тип для проверки, чтобы узнать, является contiguous_iteratorли это .

Замечания

Доступ contiguous_iterator к ней можно получить с помощью арифметики указателя, так как элементы выкладываются последовательно в памяти и имеют одинаковый размер. Ниже приведены некоторые примеры contiguous_iteratorarray: , vectorи string.

Пример: contiguous_iterator

В следующем примере используется contiguous_iterator концепция для отображения того, что у vector<int> него есть 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

Имеет возможности и input_iterator возможности output_iterator. Поддерживает итерацию по коллекции несколько раз.

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

Параметры

I
Итератор для проверки, чтобы узнать, является forward_iteratorли это .

Замечания

Может forward_iterator двигаться только вперед.

Некоторые примеры контейнеров, которые можно использовать с помощью forward_iteratorvector: , list, unordered_set, unordered_multiset, unordered_mapи unordered_multimap.

Пример: forward_iterator

В следующем примере используется forward_iterator концепция для отображения того, что у vector<int> него есть 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

Итератор input_iterator , который можно прочитать по крайней мере один раз.

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>;

Параметры

I
Тип для проверки, чтобы узнать, является input_iteratorли это .

Замечания

begin() Вызов input_iterator более одного раза приводит к неопределенному поведению. Тип, который только модели input_iterator не является многопроходным. Например, рассмотрите возможность чтения из стандартного входного (cin). В этом случае можно прочитать только текущий элемент один раз, и вы не можете повторно читать символы, которые вы уже прочитали. Только input_iterator считывает вперед, а не назад.

Пример: input_iterator

В следующем примере используется input_iterator концепция для отображения того, что istream_iterator у него есть 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

Основой input_or_output_iterator итеромии является концепция итеромии. Он поддерживает разыменовку и добавочный итератор. Все модели input_or_output_iteratorитератора.

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

Параметры

I
Тип для проверки, чтобы узнать, является input_or_output_iteratorли это .

Замечания

can-reference Концепция означает, что тип I является ссылкой, указателем или типом, который может быть неявно преобразован в ссылку.

Пример: input_or_output_iterator

В следующем примере используется концепция, показывающаяinput_or_output_iterator, vector<int> что имеет :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

Итератор output_iterator , на который можно написать.

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);
    };

Параметры

I
Тип для проверки, чтобы узнать, является output_iteratorли это .

T
Тип записываемых значений.

Замечания

Один output_iterator проход. То есть он может записывать только один и тот же элемент один раз.

Пример: output_iterator

В следующем примере используется концепция, показывающаяoutput_iterator, vector<int> что имеет :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

Объект random_access_iterator может считывать или записывать по индексу.

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>>;
    };

Параметры

I
Тип для проверки, чтобы узнать, является random_access_iteratorли это .

Замечания

A random_access_iterator имеет возможности input_iterator, и output_iteratorforward_iteratorbidirectional_iterator.

Ниже приведены некоторые примеры random_access_iteratorvector: , arrayи deque.

Пример: random_access_iterator

В следующем примере показано, что у 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

Указывает, что тип является sentinel для итератора.

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

Параметры

I
Тип итератора.

S
Тип для проверки, чтобы узнать, является ли это sentinel для I.

Замечания

Sentinel — это тип, который можно сравнить с итератором, чтобы определить, достиг ли итератор. Эта концепция определяет, является ли тип sentinel для одного из input_or_output_iterator типов, включая input_iterator, , output_iterator, forward_iteratorbidirectional_iteratorи .random_access_iteratorcontiguous_iterator

Пример: sentinel_for

В следующем примере используется концепция, показывающая sentinel_for , что vector<int>::iterator это sentinel для 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

Проверьте, что итератор и его sentinel можно вычитать, используя для - поиска разницы в постоянном времени.

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>>;
    };

Параметры

I
Тип итератора.

S
Тип sentinel для тестирования.

Пример: sized_sentinel_for

В следующем примере используется sized_sentinel_for концепция для проверки того, что sentinel для объекта vector<int> можно вычитать из итератора векторов в постоянное время:

// 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
}    

См. также

Основные понятия диапазона
Адаптеры диапазона
Просмотр классов