Насколько умен C++ итератор deque

Скажем, у меня есть std::deque<int> d, содержащий 100 значений, от 0 до 99. Учитывая следующее:

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

Кажется, строка ниже недействительна:

int invalidResult = *(d.begin() + 81); // might give me 81, but NOT GUARANTEED, right?

У меня такой вопрос: об этом позаботится итератор?

std::deque<int>::iterator it = d.begin();
int isThisValid = *(it + 81); // 81 every time? or does it result in undefined behavior?

В какой-то момент я думал, что итератор справится с любыми разрывами в базовом хранилище, но теперь я в этом не уверен. Очевидно, что если вы используете it++ 81 раз, в результате *it вы получите 81.

Кто-то может сказать наверняка?

Что бы это ни стоило, я не использую С++ 11.


c++ stl deque
person kmort    schedule 05.01.2017    source источник
comment
Какая часть смещения указателя имеет какое-либо отношение к d.begin() + 81?   -  person Kerrek SB    schedule 06.01.2017
comment
Вы спрашиваете, является ли итератор deque произвольным доступом? да. Это.   -  person    schedule 06.01.2017
comment
@KerrekSB Итак, они пытаются сказать, что не нужно брать адрес элемента, а затем смещать оттуда?   -  person kmort    schedule 06.01.2017
comment
@kmort да, это именно то, что они пытаются сказать. Хранилище двухсторонней очереди не является непрерывным, в отличие от вектора.   -  person Mark Ransom    schedule 06.01.2017
comment
@kmort: Да, это то, что обычно означает указатель.   -  person Kerrek SB    schedule 06.01.2017

Ответы (2)


arrow_upward
8
arrow_downward

Кажется, строка ниже недействительна:

int invalidResult = *(d.begin() + 81); // might give me 81, but NOT GUARANTEED, right?

Напротив. Заявление совершенно верно, и поведение гарантировано (при условии d.size() >= 82). Это связано с тем, что std::deque::begin возвращает итератор, а не указатель, поэтому указанное правило не применяется.

std::deque<int>::iterator it = d.begin();
int isThisValid = *(it + 81); // 81 every time? or does it result in undefined behavior?

Это в значительной степени эквивалентно предыдущему коду, за исключением того, что вы использовали именованную переменную вместо временного итератора. Поведение точно такое же.

Вот пример того, что вы не можете делать:

int* pointer = &d.front();
pointer[offset] = 42; // oops
person eerorika    schedule 05.01.2017
comment
Хорошо. Я рад, что итераторы прозрачно обрабатывают любые разрывы. Это означает, что мне нужно искать ошибку, которую я вижу, в другом месте. Спасибо! - person kmort; 06.01.2017
comment
Вы получаете еще больше гарантий от итератора: std::deque::begin() в настоящее время (C++17) возвращает LegacyRandomAccessIterator (en.cppreference.com/w/cpp/named_req/RandomAccessIterator), что означает, что d.begin() + 81 находится в O(1) (в то время как вызов it++ 81 раз находится в O(n)), что может значительно повысить производительность. - person Cherusker; 14.01.2019

arrow_upward
1
arrow_downward

Согласно этой ссылке и std::deque предоставляет RandomAccessIterator, который, безусловно, будет работать в соответствии с вашим примером.

std::deque<int>::iterator it = d.begin();
int isThisValid = *(it + 81); // will be fine assuming the deque is that large
person Galik    schedule 05.01.2017