Интересная логика Random access итераторов в STL контейнерах

[vScherba]

1. Самой логичной реализацией итераторов для std::vector является обычный указатель (завернутый в обертку или даже без нее). Отсюда такое поведение в релизе.
2. В отладочном режиме MS VC2008 и выше (скорее всего и в других компиляторах также) Вы получите кучу debug-assert'ов на своем примере. В debug как раз есть проверки на принадлежность итераторов конкретному контейнеру и многие другие проверки. Но в release такие проверки — это лишний оверхед.
3. Смысл сложения 2-х итераторов? Что в результате? Вычитание же не обделено смыслом.

[kibergus]

Кстати, в этом отладочном коде порой встречаются довольно забавные моменты. Например, в debug режиме lower_bound сначала за линейное время проверяет, что контейнер упорядочен, а потом быстро за логарифм ищет нужный элемент.

[f0b0s]

Очень разумно. Я одно время использовал «быстрый» отладочный stl, когда никаких проверок не делалось (во всяком случае если они дорогие), зато и в дебаге несильно тормозило — и чего, куча багов вот типа того, что несортированно было позакралось.
Дебаг на то и есть дебаг.
Еще интересно, как у них (msvc) сделана проверка валидности итераторов: там контейнер имеет указатель на первый созданный итератор. И каждый итератор имеет указатель на следующий. То есть получается односвязный список итераторов. И при каждой их инвалидации (clear(), например) вектор проходит по этому списку и проставляет флажок «не валиден». Перед каждой операцией итератор его проверяет. Вопрос: почему не сделано как в Java, почему итератор сам не может обращаться к вектору, а именно вектор их инвалидирует? Ответ: потому что, если в Java итератор имеет ссылку на контейнер, то тот точно будет валиден. А в случае с плюсами, если пользователь разрушит контейнер, то итератор будет ссылаться на мусор. Подробнее можно найти на ch9.ms

[vScherba]

Вполне логично. В дебаге чем больше проверок, тем лучше. Мы когда перевели свой проект с VS2003 на VS2008 несколько интересных багов обнаружили.

[gribozavr]

Не логично. O(N) проверка в lower_bound не соответствует требованиям сложности, указанным в стандарте.

[f0b0s]

Хорошо, Debug-режим не соответствует Стандарту. И чего? Не пользуйтесь этим «багнутым» режимом, в релизе все ок. Так что вполне логично, что как раз и разделено на 2 явных режима: дебаг и релиз, а не переключается флажками какими, так, что в релизе можно получить плохую сложность

[kibergus]

Это хорошо до тех пор, пока вы не пишете вычислительно сложные алгоритмы. У которых сложность и так большая. В итоге получается, что в debug режиме, даже на относительно простых примерах, дождаться конца вычисления просто невозможно.
Хотя, наверняка есть волшебные флаги, оптимизирующие это. Я с VS не работаю, подробностей не знаю.

[vScherba]

На дебаг режим это не распространяется. Много чего в дебаге не соответствует требованиям сложности.

[gribozavr]

Пункт стандарта в студию.

Hint: его нет. В стандарте вообще нет термина «дебаг режим».

[vScherba]

Я и не утверждал, что это в стандарте написано. Я хочу сказать, что дебаг режим не обязан поддерживать стандарт в требованиях эффективности. Главное, чтобы семантику не портил. Ведь польза этого режима как раз во всевозможных «тормозных» проверках. Иначе этот режим потеряет смысл, следуя требованиям эффективности

[gribozavr]

Требования стандарта не делятся на требования семантики, эффективности и ещё какие-то. Они все равноправны с точки зрения conformance. И если дебаг-проверки превращают мой nlogn алгоритм, использующий lower_bound в нереальный n^2, который не завершится в ближайший час даже на тестовых данных — то это баг реализации.

[vScherba]

Если я скажу, что отладочный режим компиляции предназначен не для полноценного соответствия стандарту, а в помощь программисту найти баги до выпуска в продакшн, Вы все равно со мной не согласитесь? Я согласен, что в Вашем конкретном примере отступление от стандарта дало больше вреда, чем пользы. В конкретном случае можно отключить проверку, настроив нужный макрос. Но убирать ее совсем не стоит — уж очень полезная фича.

[gribozavr]

В такой формулировке — соглашусь. И я никогда не говорил что checked STL — плохая вещь как концепция.

Просто меня задела фраза:
> На дебаг режим это не распространяется.
Которая подразумевает что для дебаг-режима есть какие-то особые требования conformance.

[vScherba]

> Которая подразумевает что для дебаг-режима есть какие-то особые требования conformance.
Похоже, я изначально неудачно выразил свою мысль.

[HuanTarget]

Согласен, что смысла в сложении мало. Просто нас учат, что при перегрузке операторов, по правилам хорошего тона нужно перегружать оба логически сопоставимые опретора, равно — не равно, больше — меньше, плюс — минус. Поэтому и обратил внимание.
Хотя если поискать, можно смысл придумать. Например при сложении результатом давать номер позиции, которая стоит дальше от начала.
Хотя ни в сложении, ни в вычитании итераторов, указывающих на разные вектора смысла не вижу никакого :)

[vScherba]

А 2 указателя пробовали сложить?

[f0b0s]

Началооось. Вот до того как учат «перегружать оба логически сопоставимые итераторы» учат более базовой вещи «перегружать только то, что имеет физический смысл». Вычитание его имеет — это расстояние. Например, мы вычитаем координаты вектора, чтобы получить его длину, или 2 временные метки (в плане просто 2 времени), чтобы получить продолжительность. А вот сложение координат или времени физического смысла не несут.

>>Например при сложении результатом давать номер позиции, которая стоит дальше от начала.
То есть переизобрести operator>?

[bazzilic]

Я в своё время делал класс математического вектора и, когда начал писать перегрузку операторов ему, увлекся и на автомате заодно перегрузил оператор деления по аналогии со скалярным умножением. Позже что-то там правил в этом классе, наткнулся на это чудо и долго соображал, шо за нафиг.

[f0b0s]

И кстати, обратный пример. Вот для строк определен только operator+. Какой же для них минус делать?

[StrangeAttractor]

Смысл сложения 2-х итераторов? Что в результате? Вычитание же не обделено смыслом.

Смысл сложения двух итераторов в моём (высокоуровневого функциональщика (Scala, C#), когда я кодил на C++ STL ещё не получила распространения) понимании — получить итератор, который пробежится по обеим коллекциям, а вот смысл вычитания итераторов не могу себе представить, поясните, пожалуйста, если не в тягость.

[gribozavr]

RandomAccessIterator — это по духу указатель. Поэтому вычитание даёт расстояние.

[daylight_warrior]

STL контейнеры были разработаны так, чтобы они работали максимально быстро и эффективно. Все проверки по принадлежности итераторов к одному и тому же контейнеру должен брать на себя программист.
А что смущает Вас в отсутствии сложения итераторов? Или даже поставим вопрос по-другому — зачем вам с точки зрения практической пользы нужно сложение итераторов?

[f0b0s]

Вероятно, автор топика еще и периодически складывает время для вычисления только одному ему известному величины :-)

[gribozavr]

Совет на миллион: почитайте, наконец, стандарт C++ (про итераторы, контейнеры и undefined behavior) и перестаньте удивляться задокументированному и логичному поведению языка (при условии что вы знаете правила игры, описанные в стандарте). Если вы находитесь на уровне «написать аналог std::vector» то ни Хабр, ни Вивипедия, при всём уважении, не могут быть авторитетными источниками.

[f0b0s]

Скажите, а вы на Си программировали или сразу с Си++ начали?
Все что вы описали — базовые вещи по указателям, наследниками (в общем смысле) которых и являются RA-итераторы.
И последнее: а стандарт-то вы поглядывали?

§ 24.2.1 An iterator j is called reachable from an iterator i if and only if there is a finite sequence of applications of the expression ++i that makes i == j. If j is reachable from i, they refer to elements of the same sequence.
§ 24.2.5 The domain of == for forward iterators is that of iterators over the same underlying sequence.

Пост из разряда как ВЫСТРЕЛИТЬ себе в ногу в Си++, это мы и без вас много каких способов знаем :-)

[kibergus]

Во-вторых, меня заинтересовал вопрос равенства итераторов. Исходя из определения, итератор должен обеспечивать доступ к элементам коллекции. Т. е. если два итератора принадлежат разным коллекциям, кэп подсказывает, что сравнивать их вообще нельзя.

Да, кстати, сравнение указателей на области памяти, полученные из разных вызовов выделения памяти ведет к undefined behavior. Они могут оказаться равными даже если указывают на разные области памяти. Правда это не касается алгоритмов из std:: типа std::less. Поэтому использовать указатели как ключи std::map все-таки можно.

[gribozavr]

> Они могут оказаться равными даже если указывают на разные области памяти

Так быть не может никогда.

А вот что может быть: malloc() и realloc() по стандарту возвращает указатель на новый объект, который отличается от остальных указателей. Поэтому компилятор может во время оптимизации считать что все области памяти не алиасятся и спокойно делать store forwarding как в этом примере:

$ cat /tmp/zzz.c
#include <stdio.h>
#include <stdlib.h>
 
int main() {
  int *p = (int*)malloc(sizeof(int));
  int *q = (int*)realloc(p, sizeof(int));
  *p = 1;
  *q = 2;
  if (p == q)
    printf("%d %d\n", *p, *q);
}
$ ./Release/bin/clang -O3 /tmp/zzz.c
$ ./a.out 
1 2

— blog.regehr.org/archives/767

[kibergus]

Алиасинг тут ни при чем.

А вот что может быть: malloc() и realloc() по стандарту возвращает указатель на новый объект, который отличается от остальных указателей

Да разные. Я не написал «Они могут оказаться равными даже если указывают на разные области памяти». Указатели разные, но операция сравнения, например на равенство, может возвращать истину.

Так быть не может никогда.

Стандарт говорит иначе. Тут надо вспоминать историю. Какого размера указатель на x86? Старом x86, 16 битном, с сегментными регистрами. Чтобы полностью адресовать данные нужно хранить и значение регистра и смещение от начала сегмента. Но мы же не хотим терять время на сравнение и того и того? Массив целиком лежит в одном сегменте данных, поэтому достаточно сравнить смещения. Поэтому указатели на данные, лежащие в разных сегментах могут оказаться равны.
Стандарт допускает такую организацию памяти, поэтому вводит хитрые правила сравнения указателей.

[gribozavr]

> А если стандарт почитать?

Мне почему-то кажется что я его читал побольше вашего…

[expr.eq]p1:

Two pointers of the same type compare equal if and only if they are both null, both point to the same function, or both represent the same address (3.9.2).

[basic.compound]p3:

A valid value of an object pointer type represents either the address of a byte in memory (1.7) or a null pointer (4.10).

[intro.memory]p1:

Every byte has a unique address.

> Какого размера указатель на x86? Старом x86, 16 битном, с сегментными регистрами. Чтобы полностью адресовать дынные нужно хранить и значение регистра и смещение от начала сегмента.

Исходя из цитат, приведённых выше, этот подход не соответствует стандарту. Каждый байт должен иметь уникальный адрес, который хранится в указателе. Полноценным указателем может считаться только far pointer.

[kibergus]

Действительно. Для отношения равенства результат определен. Но для < > <= и >= нет.

[gribozavr]

> Но для < > <= и >= нет.
И снова нет! Он определён в случае если два указателя указывают в один и тот же объект. [expr.rel]

Но это не важно, вы-то говорили про строгое равенство:
> Они могут оказаться равными даже если указывают на разные области памяти.

[kibergus]

И снова нет! Он определён в случае если два указателя указывают в один и тот же объект.

А я про это и говорил. Объект выделяется одиним куском. Нельзя выделить память под объект в два захода. Поэтому адреса сравнимы. Аналогично, если вы выделили память под несколько объектов сразу, то это массив, это один объект, и адреса сравнимы.

Но это не важно, вы-то говорили про строгое равенство:
> Они могут оказаться равными даже если указывают на разные области памяти.

Эту ошибку я признал. Кстати, в следующем предложении я уже говорил про <.