Как разыменовать итератор c

Ленивые итераторы и диапазоны в C++

Для того, чтобы упростить написание и чтение кода, программисты периодически придумывают всякие техники. Об одной из таких техник я уже писал в публикации Долой циклы, или Неленивая композиция алгоритмов в C++.

Однако есть и классическая, более распространённая техника для борьбы с циклами — использование итераторов и диапазонов для ленивых операций над последовательностями. Всё это уже сто лет есть в Бусте и других сторонних библиотеках (к примеру, range-v3) и постепенно просачивается в стандартную библиотеку.

Хотя, в некотором смысле, и в стандартной библиотеке ленивые итераторы уже есть давно (см. std::reverse_iterator ).

Данная публикация — это краткий ликбез о том, что такое ленивые итераторы и диапазоны, зачем они нужны и как ими пользоваться.

Итератор

Начнём с простого. Что вообще такое итератор?

Понять суть концепции довольно легко. Сам по себе итератор — это обобщение указателя. При этом главное, что нужно знать — это два способа взаимодействия с итератором:

• Продвижение (например, ++i или i + n );
• Разыменование ( *i ).

И в эти взаимодействия мы можем внедряться и переопределять их так, как нам нужно.

Ленивость

Внедрение в операции над диапазонами может быть сколь угодно хитрым и сложным (простые примеры я привёл ниже). Ленивость же состоит в том, что нет никаких промежуточных результатов. Все вычисления происходят только тогда, когда вызываются операции разыменования или продвижения.

Определение 1. Итератор e достижим из итератора b , если существует схема f продвижения итератора b такая, что f(b) = e .

Допустим, у нас есть некая последовательность элементов, заданная двумя итераторами: на начало и конец этой последовательности (при этом конец достижим из начала). Теперь мы преобразуем оба этих итератора каким-то способом и получаем два новых итератора. Если преобразование итераторов корректно, т.е. образ конца первой последовательности достижим из образа начала первой последовательности, то мы получили новую последовательность. При этом длина и элементы новой последовательности могут отличаться от длины и элементов исходной.

В этом и состоит ленивость — мы получили новую последовательность без изменений в старой. Мы не трогали хранимые объекты, а только переопределили способ их отображения и обхода по ним.

Transform Iterator

Простой пример внедрения в операцию разыменования — это boost::transform_iterator .

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

Таким образом, каждому итератору i типа I мы поставили в соответствие итератор j типа J такой, что *j = f(*i) .

auto v = std::vector; // 2 4 6 8 auto i = v.begin(); auto t = boost::make_transform_iterator(i, [] (auto x) ); assert(*t == 2); ++t; assert(*t == 4); . 

Filter Iterator

Пример внедрения в продвижение — это boost::filter_iterator .

Он оборачивает продвижение, причём относительно «хитрым» образом. Он выбрасывает из рассмотрения все элементы исходной последовательности, которые не удовлетворяют заданному предикату. Единственное отличие — обёрнутый итератор сразу же позиционируется на нужном элементе, если у исходной последовательности есть префикс, все элементы которого не удовлетворяют предикату.

Таким образом, мы «выбросили» из исходной последовательности итераторы i такие, что p(*i) == false , и в результирующей последовательности, для каждого итератора j типа J выполняется p(*j) == true .

auto v = std::vector; // ^ ^ auto i = v.begin(); auto f = boost::make_filter_iterator(i, [] (auto x) ); assert(*i == 2); ++i; assert(*i == 4);

Ленивые диапазоны

Итератор — это обобщение указателя. Поэтому итератор, как и указатель, сам по себе не знает, когда нужно остановиться. Имея только итератор на начало последовательности, нельзя сказать, где конец этой последовательности. Поэтому мы объединяем пару итераторов — начало и конец — в диапазон.

При этом диапазон — это уже более сложная конструкция, и у него другой интерфейс, похожий на интерфейс контейнеров:

• Взятие итераторов на начало и конец ( r.begin() , r.end() );
• Взятие первого элемента диапазона ( r.front() );
• Проверка на пустоту ( r.empty() ).

Разница только в том, что диапазон не владеет элементами, которые он задаёт. Хотя бы потому что канонический диапазон — это просто пара итераторов (к примеру, std::equal_range ).

Важно отметить, что диапазон принято задавать полуинтервалом [b, e) . Это значит, что итератор-начало b указывает на первый элемент последовательности, а итератор-конец e указывает на элемент после последнего. Таким образом, когда мы приходим в итератор-конец, мы точно знаем, что последовательность закончилась.

Transform Range

На основе преобразующих итераторов можно собрать диапазон (см. boost::iterator_range ).

auto v = std::vector; auto l = [] (auto x) ; auto tb = boost::make_transform_iterator(v.begin(), l); auto te = boost::make_transform_iterator(v.end(), l); auto tr = boost::make_iterator_range(tb, te); for (auto x: tr)

auto v = std::vector; auto tr = boost::adaptors::transform(v, [] (auto x) ); for (auto x: tr)

auto v = std::vector; auto tr = std::ranges::views::transform(v, [] (auto x) ); for (auto x: tr)

Stride

Другой пример ленивого диапазона — это boost::strided .

Он оборачивает исходный диапазон так, что в новом диапазоне остаются только кратные позиции исходного диапазона.

auto v = std::vector; // ^ ^ auto s = boost::adaptors::strided(v, 2); assert(s.front() == 1); s.advance_begin(); assert(s.front() == 3);

Компоновка

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

Например, если мы хотим для некоей последовательности чисел:

• возвести их в квадрат,
• взять только каждый четвёртый элемент,
• и оставить только чётные числа,

то можно это сделать так:

auto v = std::vector; auto r = v | transformed([] (auto x) ) | strided(4) | filtered([] (auto x) );

auto v = std::vector; auto r = v | std::views::transformed([] (auto x) ) // | strided(4) // В C++20 такого нет. | std::views::filtered([] (auto x) );

Ещё раз хочу подчеркнуть, что этот код не производит никаких вычислений. Он только сохраняет «схемы» работы с диапазоном, а настоящие вычисления будут происходить только во время продвижения или разыменования обёрнутого итератора.

Суть итераторов и диапазонов

Помимо C++, в некоторых языках программировани также существует концепция под названием «итератор», но эта концепция зачастую имеет какой-то свой, альтернативный смысл.
К примеру, «итераторы» в языках Java и C# знают свой предел. С точки зрения языка C++ это, скорее, диапазоны.

В C++ итератор — это именно обобщение указателя. По сути указатель — это самый сильный (или наиболее конкретный) итератор, причём иерархия следующая:

• Однопроходный итератор (input iterator);
• Однонаправленный итератор (forward iterator);
• Двунаправленный итератор (bidirectional iterator);
• Итератор произвольного доступа (random access iterator);
• Непрерывный итератор (contiguous iterator);
• Указатель.

Диапазон же можно рассматривать именно как пару итераторов (даже если это на самом деле не так). Диапазон уже знает, где у него конец, может накладывать дополнительную логику на операции с итераторами и т.д. Также диапазон может быть сконвертирован обратно в итераторы (потому что диапазон — это пара итераторов, как уже было сказано выше).

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

Один из примеров создания сложной операции над диапазонами я привёл в статье Ленивые операции над множествами в C++.

Разименование итератора в std::set

Доброго времени суток! Я недавно начал заниматься программированием и сейчас возникла потребность в рассмотрении контейнера std::set(далее именуемый контейнер). И у меня возникло несколько вопросов, поискав в интернете не нашел подходящих ответов, решил спросить у знающих людей, которые могли бы помочь мне. И так суть вопроса, имеется контейнер типа const char* в который мы добавляем 2 элемента.

typedef std::tr1::unordered_set unordered_set; unordered_set myUnorderedSet; myUnorderedSet.insert("testAction"); myUnorderedSet.insert("testActionTwo"); 

далее если пробежаться по контейнеру

for ( unordered_set::iterator it = myUnorderedSet.begin(); it != myUnorderedSet.end(); ++it )

можно вывести значения хранящиеся в данном контейнере. Затем я пытаюсь найти нужное мне значение используя метод find().

unordered_set::iterator = myUnorderedSet.find("testAction"); 

Как получить значение данного итератора, для того чтобы можно было сравнить его со значение которое я добавлял в контейнер*? И почему при такой записи

я получаю ошибку компиляции: list iterator is not dereferencable. Не совсем понимаю, ведь

for ( unordered_set::iterator it = myUnorderedSet.begin(); it != myUnorderedSet.end(); ++it )

мы можем применить операцию разыменования. Заранее благодарен за ответы!
Отслеживать
задан 18 ноя 2013 в 11:51
171 2 2 серебряных знака 13 13 бронзовых знаков

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

смотрим описание метода find() тут(ru) или тут(en) и видим что если find ничего не находит то возвращает итератор на end() , то есть на элемент следующий за последним и он (итератор end() ) действительно не разыменуемый (is not dereferencable)

то есть имея массив из 5 элементов [0,1,2,3,4] find ненайдя ничего вернёт [5] то есть end()

соответственно для проверки «а нашлось ли чего нибудь» сравниваем if(iterator==myUnorderedSet.end())

почему так происходит?

в set’e вы храните не строку testAction а указатель на неё и в функции find() сравниваются указатели!

когда вы пишите строку в хардкоде то она помещается в специально отведённое место в программе, а вместо неё используется указатель на это место, написав два раза одинаковую строку testAction получаем две строки в специально отведённом месте (НО компиляторы могут с оптимизировать такие строки, в итоге имеем UB)

как сравнивать строки?

в STL есть тип данных(class) для строк string пихаем строки в стринг и при сравнении будет происходить преобразование

string str="hello world";// или string str("hello world"); if(str=="hello world")//TRUE 

Итераторы в C++: введение

Всем привет! Изучая контейнеры STL, мы использовали новый вид переменных — итераторы. Так давайте узнаем, зачем ими пользуются?

Что такое итератор

Итератор — это такая структура данных, которая используется для обращения к определенному элементу в контейнерах STL. Обычно из используют с контейнерами set , list , а у вектора для этого применяют индексы.

Кстати по мере того, как мы будем изучать итераторы, вам все больше будет казаться, что итераторы и есть указатели (это мы разберем ниже).

Как создать итератор

Для создания итератора мы должны с самого начала программы подключить библиотеку .

#include 

Далее для его создании нам потребуется использовать вот эту схему:

контейнер> его тип> :: iterator имя итератора>;

• — указываем требуемый контейнер, на который и будет ссылаться итератор. Например map , vector , list .
• — указываем тип контейнера.

Вам нужно помнить! Если вы создали итератор и случайно ввели не тот тип данных, который указали при создании контейнера, то ваша программа будет работать неправильно и вообще может сломается.

Методы начала и конца контейнеров

У каждого контейнера имеются два метода, которые, как указатели передают итератору начало или конец контейнера — begin() и end().

• Метод begin() отправит итератор на начала контейнера.
• А метод end() отправит на конец. А если точнее, то на одну ячейку больше последней. Если мы попытаемся вывести эту ячейку у нас появятся проблемы с компилятором 🙂 .

Их мы можем использовать даже без подключения библиотеки , что очень удобно.

Также при инициализации итератора мы можем с самого начала написать, куда он будет указывать:

vector int> i_am_vector; vector int> :: iterator it = i_am_vector.begin();

Итератор на vector

Для итератора на vector вы можете:

• Выполнять операцию разыменования (обращаться к значению элемента на которое указывает итератор), как мы это делали с указателем.

int x = *it;

• Использовать инкремент ( it++, ++it ) и декремент ( it—, —it ).
• Применять арифметические операции. Так например мы можем сместить итератор на пять ячеек в право, вот так:

it += 5;

• Сравнивать на равенства.

if (it == it2)  ...

• Передать переменной разницу итераторов.

int x = it - it2;

Использовать выше сказанные операции можно только с идентичными итераторами, которые указывают на одинаковый контейнер и тип.

Есть исключение из правил — если вы создадите два одинаковых итератора на map то при сравнивании они не будут одинаковы.

Например, если мы создали два итератора на один и тот же контейнер, но указали для них разный тип данных и решили использовать выше сказанные операции — то компилятор начнет ругаться.

vector int> vector_first; vector double> vector_second; vector int> :: iterator it = vector_first.begin(); vector double> :: iterator it2 = vector_second.begin(); if (it == it2)  // ошибка! cout  <"it == it2"; >

Итератор на list, set, map

Для итераторов на list , set , map немного урезан функционал. Так вы не можете:

• Использовать арифметические операции.

it += 5; // it *= 2; // it /= 3; // ошибка it -= 5; //

• Применять операции сравнения ( > и < ):

if (it > it_second)  ... // // ошибка if (it  it_second)  ... //

Все остальное можно использовать:

• Применять инкремент и декремент.

it--; // все it++; // нормально!

• Использовать операцию разыменования.

cout  *it; *it += 5;

• Сравнивать два итератора на равенство и неравенства:

if (it == it_second)  ... // // правильно if (it != it_second)  ... //

Кстати использовать арифметические операции, чтобы увеличить итератор на один, как это делает инкремент — нельзя.

Но вы можете сказать: “Так что мы можем двигать итератор только на один элемент? Это же неудобно!“. Да было бы совсем не гибко со стороны C++ делать вот такое, но они позаботились и создали функцию — advanсe() , она заменяет операции увеличения и уменьшения над итераторами.

Вот как она работает:

advance(итератор>, значение>);

• — сюда мы должны указать итератор, который и нужно изменить.
• — тут мы должны вписать число на которое должны увеличить или уменьшить итератор.

Если мы увеличиваем итератор, то используем оператор + к числу. Но можно и просто записать число без оператора + .

Если же нужно уменьшить итератор, то мы добавляем оператор — .

advanсe(it, 5); // сместили на 5 ячеек

Как работают итераторы

Чтобы понять, как работают итераторы, давайте разберем их использование на практике. В примере ниже с помощью итератора мы выводим содержимое вектора на экран:

#include #include #include using namespace std; int main()  setlocale(0, ""); vector name_vector; name_vector.push_back(3); name_vector.push_back(4); name_vector.push_back(6); vector int> :: iterator it; for (it = name_vector.end() - 1; it >= name_vector.begin(); it--)  cout  <*it  <" "; > system("pause"); return 0; >

• В строке 10: создали вектор name_vector .
• Дальше в последующих трех строках занимаемся его заполнением.
• В строке 16: создали итератор под именем it .
• В цикле for мы написали, что итератор указывает на последнюю ячейку вектора. С помощью вот такой не замысловатой конструкции :

it = name_vector.end() - 1;

Выше мы говорили, что метод end() указывает на одну ячейку больше последней. Поэтому, чтобы обратится к последнему элементу в векторе нам понадобилось отнять 1.

• Используя операцию разыменования, в теле цикла, мы вывели все элементы.

cout  *it;

Вы наверняка заметили, что мы выводим элеме