Const iterator c что это
Совет 26. Старайтесь использовать iterator вместо const_iterator, reverse_iterator и const_reverse_iterator
Как известно, каждый стандартный контейнер поддерживает четыре типа итераторов. Для контейнера container тип iterator работает как T* тогда как const_iterator работает как const T* (также встречается запись T const* ). При увеличении iterator или const_iterator происходит переход к следующему элементу контейнера в прямом порядке перебора (от начала к концу контейнера). Итераторы reverse_iterator и const_reverse_iterator также работают как T* и const T* соответственно, но при увеличении эти итераторы переходят к следующему элементу в обратном порядке перебора (от конца к началу).
Рассмотрим несколько сигнатур insert и erase в контейнере vector :
iterator insert(iterator position, const T& x);
iterator erase(iterator position);
iterator erase(iterator rangeBegin, iterator rangeEnd);
На следующей диаграмме показаны преобразования, возможные между итераторами разных типов.
• Преобразование reverse_iterator в iterator может требовать дополнительной регулировки итератора. В совете 28 рассказано, когда и почему возникает такая необходимость.
typedef deque IntDeque; // Определения типов
typedef IntDeque:iterator Iter; // упрощают работу
typedef IntDeque::const_iterator ConstIter; // с контейнерами STL
// и типами итераторов
… // i и ci указывают на элементы
if (i==ci)… // Сравнить iterator
Именно это и происходит в хорошо спроектированных реализациях STL, но в некоторых случаях приведенный фрагмент не компилируется. Причина заключается в том, что такие реализации объявляют operator== функцией класса const_iterator вместо внешней функции. Впрочем, вас, вероятно, больше интересуют не корни проблемы, а ее решение, которое заключается в простом изменении порядка итераторов:
if (c==i)… // Обходное решение для тех случаев,
// когда приведенное выше сравнение не работает
Подобные проблемы возникают не только при сравнении, но и вообще при смешанном использовании iterator и const_iterator (или reverse_iterator и const_reverse_iterator ) в одном выражении, например, при попытке вычесть один итератор произвольного доступа из другого:
if (i-ci>=3)… // Если i находится минимум в трех позициях после ci…
ваш (правильный) код будет несправедливо отвергнут компилятором, если итераторы относятся к разным типам. Обходное решение остается прежним (перестановка i и ci ), но в этом случае приходится учитывать, что i-ci не заменяется на ci-i :
// предыдущая команда не компилируется
Совет 27. Используйте distance и advance для преобразования const_iterator в iterator
Я знаю, о чем вы думаете. «Если ничего не помогает, берем кувалду», не так ли? В мире C++ это может означать лишь одно: преобразование типа. Стыдитесь. И где вы набрались таких мыслей?
Давайте разберемся с вредным заблуждением относительно преобразования типа. Посмотрим, что происходит при преобразовании const_iterator в iterator :
typedef deque IntDeque; // Вспомогательные определения типов
typedef IntDeque::iterator Iter;
typedef IntDeque::const_iterator ConstIter;
Iter i(ci); // Ошибка! He существует автоматического
Iter i(const_cast (ci)); // Ошибка! Преобразование const_iterator
// в iterator невозможно!
typedef deque IntDeque; //См. ранее
typedef IntDeque::iterator Iter;
typedef IntDeque::const_iterator ConstIter;
… // Присвоить ci ссылку на d
Iter i(d.begin()); // Инициализировать i значением d.begin()
advance(i, distance(i, ci)); // Переместить i в позицию ci
Все хорошо, если бы этот вариант компилировался… но этого не происходит. Чтобы понять причины, рассмотрим объявление distance :
typename iterator_traits ::difference_type
distance(InputIterator first, InputIterator last);
Не обращайте внимания на то, что тип возвращаемого значения состоит из 56 символов и содержит упоминания зависимых типов (таких как differenceype). Вместо этого проанализируем использование параметра-типа InputIterator :
typename iterator_traits ::difference_type
distance(InputIterator first, InputIterator last);
advance(i, distance(i,ci)); // Переместить i в позицию ci
advanced.distance (i, ci)); // Вычислить расстояние между
// i и ci (как двумя const_iterator)
// и переместить i на это расстояние
Совет 28. Научитесь использовать функцию base
v.reserve(5); //См. совет 14
vector ::reverse_iterator ri = // Установить ri на элемент 3
find(v.rbegin(), v.rend(), 3);
vector ::iterator i(ri.base()); // Присвоить i результат вызова base
После выполнения этого фрагмента ситуация выглядит примерно так:
Рассмотрим операцию удаления элемента. Вернемся к взаимосвязи между ri и исходным вектором (по состоянию на момент, предшествующий вставке значения 99):
Однако к коду стоит присмотреться повнимательнее, поскольку вас ждет сюрприз:
… // См. ранее. В вектор v заносятся
vector ::reverse_iterator ri = // Установить ri на элемент 3
find(v.rbegin(), v.rend(), 3);
v.erase(—ri.base()); // Попытка стирания в позиции.
// для вектора обычно
v.erase((++ri).base()); // Удалить элемент, на который указывает ri;
// команда всегда компилируется
Совет 29. Рассмотрите возможность использования istreambuf_iterator при посимвольном вводе
string fileData(istream_iterator (inputFile)), // Прочитать inputFile
istream iterator ()); // в fileData
Чтобы сохранить пропуски, входящие в файл, достаточно включить режим чтения пропусков сбросом флага skipws для входного потока:
inputFile.unset(ios::skipws); // Включить режим
string fileData(istream_iterator (inputFile)), // Прочитать inputFile
istream_iterator ()); // в fileData.
Перейти на использование istreambuf_iterator при чтении файла так просто, что даже программист Visual Basic сделает это со второй попытки:
string fileData(istreambuf_iterator (inputFile)),
На этот раз сбрасывать флаг skpws не нужно, итераторы streambuf_iterator никогда не пропускают символы при вводе и просто возвращают следующий символ из буфера.
Раз уж речь зашла о буферизованных итераторах, следует упомянуть и об использовании ostreambuf_iterator при неформатном посимвольном выводе. По сравнению с ostream_iterator итераторы ostreambuf_iterator обладают меньшими затратами (при меньших возможностях), поэтому обычно они превосходят их по эффективности.
Как правильно реализовать пользовательские итераторы и const_iterators?
Я никогда не делал этого раньше, и мне не удалось найти подходящее руководство. Каковы рекомендации по созданию итераторов, и что я должен знать?
Я также хотел бы избежать дублирования кода (я чувствую это const_iterator и iterator делюсь многими вещами; один подкласс должен быть другим?).
Примечание: я почти уверен, что у Boost есть что-то, чтобы облегчить это, но я не могу использовать это здесь по многим глупым причинам.
Во избежание дублирования кода класс итератора должен быть классом шаблона и параметризоваться как «тип значения», «тип указателя», «ссылочный тип» или все из них (зависит от реализации). Например:
Обратите внимание iterator_type и const_iterator_type определения типов: это типы для ваших неконстантных и константных итераторов.
Я собираюсь показать вам, как вы можете легко определить итераторы для ваших пользовательских контейнеров, но на всякий случай я создал библиотеку c ++ 11, которая позволяет вам легко создавать пользовательские итераторы с пользовательским поведением для любого типа контейнера, смежного или Непоследовательный.
Вы можете найти его на Github
Вот простые шаги по созданию и использованию пользовательских итераторов:
Наконец, на определение наших пользовательских классов итераторов:
ПРИМЕЧАНИЕ. При определении пользовательских итераторов мы производим от стандартных категорий итераторов, чтобы алгоритмы STL знали тип итератора, который мы создали.
В этом примере я определяю итератор произвольного доступа и обратный итератор произвольного доступа:
Теперь где-нибудь в вашем пользовательском классе контейнера:
Векторные итераторы C++
Основными итераторами в C ++ являются итератор ввода, итератор вывода, итератор прямого действия, двунаправленный итератор и итератор произвольного доступа. Обратный итератор на самом деле не является итератором; это адаптер итератора. Есть несколько вариантов итераторов, например, постоянный итератор.
Итератор — это разработанный указатель. Как указатель, он указывает на объекты одного типа в памяти в разное время. Все итераторы могут быть разыменованы, за исключением выходного итератора, разыменование которого возможно только для набора типов. Возможность разыменования означает, что значение, на которое указывает указатель или итератор, может быть получено с помощью оператора косвенного обращения *. Таким же образом можно добавить целое число к некоторым итераторам, и с той же целью целое число будет добавлено к указателю.
Вопросы для этой статьи: что это за итераторы? Какие из этих итераторов используются с вектором C ++? Как эти итераторы используются с вектором C ++? Эта статья дает упрощенный ответ на все эти вопросы. В конце статьи, когда будут даны ответы на все эти вопросы, векторные итераторы C ++ станут интуитивно понятными и естественными (для читателя).
Summary Iterators в C ++
Входной итератор
Идея итератора ввода заключается в том, что программа получает входное значение. В отличие от итератора вывода, итератор ввода всегда можно разыменовать. Для двух итераторов ввода, a и b, «a == b» не означает «++ a == ++ b».
Итератор вывода
Идея итератора вывода состоит в том, чтобы программа выдавала выходное значение. В отличие от итератора ввода, итератор вывода не всегда можно разыменовать. Разыменовать его можно только для набора типов.
Прямой итератор
Прямой итератор может сканировать вектор от начала до конца, один за другим (с приращением). У него есть все требования к итератору ввода, а также дополнительные требования. Он может заменить итератор ввода. Для двух итераторов вперед, a и b, «a == b» означает «++ a == ++ b».
Двунаправленный итератор
Двунаправленный итератор может сканировать вектор от начала до конца, один за другим. От конца к началу, по одному (по убыванию). У него есть все требования прямого итератора, а также дополнительные требования. Он может заменить прямой итератор. Для двух двунаправленных итераторов a и b
“a == b” implies “++a == ++b”
and
“–a == –b” implies “a == b”.
Итератор произвольного доступа
Итератор произвольного доступа имеет все требования двунаправленного итератора, а также дополнительные требования. Он может заменить двунаправленный итератор. Итератор произвольного доступа имеет то преимущество, что если он в настоящее время указывает на первый элемент, а четвертый элемент требуется, он пропустит второй и третий элементы и укажет на четвертый элемент. Обратный переход вниз верен.
Обратный итератор
Обратите внимание, что C ++ не имеет обычного обратного итератора, поскольку у него есть прямой итератор. Итак, есть адаптер под названием Reverse Iterator. Есть и другие хорошие новости: обратный итератор отвечает всем требованиям двунаправленного итератора.
Постоянный итератор
Если итератор называется константным итератором, элемент, на который он указывает, изменить нельзя.
Построение векторов и доступ
Контейнеры в C ++: массив классов, двухсторонняя очередь, forward_list, список, вектор, карта, набор, unordered_map и unordered_set. Вектор — это контейнер. Некоторые шаблоны функций в стандартной библиотеке C ++ прямо или косвенно работают с итераторами. Контейнеры C ++, как и вектор, используют эти функции. Эти функции могут быть доступны программе C ++ с помощью любой из следующих директив включения:
Включение любого из других контейнеров также сделает доступными эти шаблоны функций. Шаблон функции предназначен для функции, которая может работать с разными типами данных. Вектор использует итераторы через эти шаблоны функций. Вот некоторые из шаблонов функций и их отношения с вектором:
Строительство
auto означает, что тип возвращаемого значения определяется при вычислении функции. c — объект класса C.
Пример векторного объекта, неявно созданного с помощью this:
Здесь объект c пуст.
Здесь E * — итератор, указывающий на первый элемент списка или контейнера. Его использование с вектором неявно будет с:
Функция шаблона более применима к оператору begin () (второй оператор).
Доступ
Это возвращает размер контейнера. Пример вектора:
Возвращает true, если список пуст, или false в противном случае. Пример вектора:
На выходе 0 для ложного.
Доступ к диапазону
Существуют и другие функции шаблона, которые используют итераторы, которые вектор использует для решения задач диапазона. Диапазон — это последовательный набор элементов контейнера.
Это возвращает итератор, указывающий на первый элемент в списке. auto здесь означает, что возвращаемое значение определяется при оценке. Пример для вектора:
Результатом будет A. Итератор, возвращенный здесь, является итератором с произвольным доступом. Можно было вернуть постоянный итератор с произвольным доступом — см. Ниже.
Возвращает постоянный итератор, указывающий на последний элемент списка. Векторный код:
На выходе будет «ED». Постоянный итератор можно увеличивать или уменьшать, но значение, на которое он указывает, нельзя изменить. Можно было вернуть нормальный итератор с произвольным доступом — см. Ниже.
Возвращает последнее значение в списке. rbegin () указывает на последний элемент списка, а не дальше последнего элемента списка, как это делает end (). Пример вектора:
Результатом будет: E D. С обратным итератором ++ имеет противоположный эффект для двунаправленного итератора.
Указывает непосредственно перед первым элементом списка. Пример вектора:
Выход — A B. С обратным итератором — имеет противоположный эффект для ++ двунаправленного итератора.
Под этим заголовком есть и другие функции шаблона — см. Ниже.
Вставить итераторы
reverse_iterator — это адаптер итератора, а не итератор. Итератор вставки также является адаптером итератора. Он удовлетворяет всем требованиям итератора вывода, а также его собственным требованиям. В C ++ он существует в трех формах: back_inserter, front_inserter и вставщик. У каждого из них есть свой конструктор.
back_inserter
Вставки сзади!
Важные прототипы:
Пример
вектора : вектор не имеет функции-члена вставки, которая вставляется сзади. Однако функцию-член push_back (t) можно увидеть так.
front_inserter
Вставки спереди!
Важные прототипы:
Пример
вектора : вектор не имеет функции-члена вставки, которая вставляется спереди. Вектор также не имеет функции-члена push_front (t).
Хорошая новость заключается в том, что у вектора есть функции-члены вставки, которые можно вставлять где угодно, в начало, внутри или в конец вектора.
inserter
Этот итератор будет вставлять в начало, внутри или в конец вектора.
for ( int i = ; i vtr. size ( ) ; i ++ )
cout vtr [ i ] «, « ;
cout endl ;
Выражение вставки вектора:
Он вставляет элемент непосредственно перед указателем (им), на который он указывает.
Move Iterator
Move_iterator также является адаптером итератора. Следующая программа похожа на пример из спецификации C ++:
cout «Vector Content:» endl ;
for ( int i = ; i vtr. size ( ) ; i ++ )
cout vtr [ i ] «, « ;
cout endl ;
Исходный список Содержание:
A, B, C, D, E,
Векторный контент:
A, B, C, D, E,
Этот итератор преобразует исходное значение в rvalue перед тем, как поместить его в место назначения.
Заключение
Основными итераторами в C ++ являются итератор ввода, итератор вывода, итератор прямого действия, двунаправленный итератор и итератор произвольного доступа. В стандартной библиотеке C ++ есть несколько шаблонов функций, которые используют эти итераторы. Вектор использует эти итераторы через шаблоны функций. У вектора есть разные имена для некоторых из этих итераторов. Существуют также адаптеры итератора: reverse_iterator, адаптер итератора и move_iterator. Также существуют несколько вариантов итераторов. Достаточно включить в программу все эти функции. После понимания роли этих итераторов, адаптеров и шаблонов функций, которые их используют, использование итераторов с векторами становится интуитивно понятным.
Преобразование итераторов и const_iterators
Общий контекст:
Я пытаюсь создать контейнер, который будет вести себя как оболочка вокруг многомерного массива заданных во время выполнения измерений — фактически базовый массив, конечно, является одномерным массивом общего размера. Основная часть заключается в том, что operator [] возвращает обертку на вложенный массив.
Я уже отметил следующие требования:
Конкретный контекст:
Стандартные контейнеры-итераторы не обеспечивают никакого преобразования из const_iterator для iterator потому что удаление констант может быть опасным. Я уже искал SO для этой проблемы и нашел Как убрать константность const_iterator? где ответы предлагают разные приемы для удаления константности у оператора. Так что теперь я задаюсь вопросом, должен ли я реализовать явный преобразование из const_iterator в итератор ала const_cast на указатели.
Вопрос:
Каковы риски в реализации явного преобразования из const_iterator в (не постоянный) iterator и чем он отличается от решений по связанному вопросу (скопировано здесь для удобства чтения):
используя аванс и расстояние (постоянное время от моих итераторов произвольного доступа)
Для ссылок, вот упрощенная и частичная реализация моих итераторов:
Решение
Оба указанных вами метода требуют неконстантного доступа к контейнеру, поэтому вы не можете получить доступ к базовым элементам const как неконстантным.
Как убрать константность const_iterator?
Любая идея о том, как лучше всего достичь этого?
Существует решение с постоянной сложностью времени в C++ 11: для любого последовательного, ассоциативного или неупорядоченного ассоциативного контейнера (включая все контейнеры стандартной библиотеки) вы можете вызвать функцию-член range-erase с пустым диапазоном:
Во-первых, самое простое: если ваши операции принимают аргументы как const (даже если внутренне применяется const_cast), я считаю, что это должно работать напрямую в большинстве реализаций (даже если это, вероятно, неопределенное поведение).
Если вы не можете изменить функторы, вы можете решить проблему с любой стороны: предоставить неконстантную обертку итератора вокруг константных итераторов или же предоставить обертку константного функтора вокруг неконстантных функторов.
Итератор фасада, долгий путь:
Это может быть не тот ответ, который вы хотели, но несколько связанный.
Я считаю, что это преобразование не нужно в хорошо разработанной программе.
В качестве обходного пути вы можете сделать следующее:
Но я думаю, что иногда это преобразование невозможно, потому что ваши алгоритмы могут не иметь доступа к контейнеру.
Вы можете вычесть итератор begin () из const_iterator, чтобы получить позицию, на которую указывает const_iterator, а затем добавить к ней begin (), чтобы получить неконстантный итератор. Я не думаю, что это будет очень эффективно для нелинейных контейнеров, но для линейных, таких как вектор, это займет постоянное время.
EDIT: похоже, работает только для линейных (произвольного доступа) контейнеров.
вы можете преобразовать свой указатель значения константного итератора в неконстантный указатель значения и использовать его непосредственно как-то так
Я подумал, что было бы интересно найти решение, которое работает для контейнеров, которых нет в стандартной библиотеке и которые не включают метод erase ().
Попытка использовать это приводит к зависанию Visual Studio 2013 при компиляции. Я не включаю тестовый пример, потому что предоставление информации читателям, которые могут быстро понять интерфейс, кажется хорошей идеей; Я не знаю, почему это зависает при компиляции. Это происходит, даже если const_iterator равен begin ().
