C++ deque итератор признан недействительным после push_front()

Question

C++ deque итератор признан недействительным после push_front()

Сейчас я читаю книгу Джозуттиса по STL.

Насколько я знаю, вектор C++ - это массив c, который можно перераспределить. Итак, я понимаю, почему после push_back() все итераторы и ссылки могут стать недействительными.

Но мой вопрос о std::deque. Как я знаю, это массив больших блоков (c-массив c-массивов). Таким образом, push_front () вставляет элемент в начале и, если места нет, deque выделяет новый блок и помещает элемент в конец выделенного блока.

После вставки () в середине все ссылки и итераторы становятся недействительными, и я понимаю, почему - все элементы перемещаются. Но я действительно неправильно понимаю фразу "... после push_back() и push_front () все ссылки остаются действительными, а итераторы - нет" (ту же фразу можно найти @ standard:23.2.2.3)

Что это значит?! Если ссылки действительны, то deque не сможет перераспределить (== переместить) свои элементы. Так почему итераторы становятся недействительными? Почему я не могу использовать их после вставки неподвижных элементов? Или фраза означает, что я не могу быть уверен в равенстве итераторов для начала () или конца () и переполнения?

Также хочу отметить, что после erase () все итераторы и ссылки остаются в силе (кроме стертого:-)).

PS: пожалуйста, не отвечайте в "стандартной" форме: "его нельзя использовать, потому что СТАНДАРТ так говорит". Я хочу понять, почему, что может случиться.

9

c++ stl iterator deque

Источник

user129413 02 ноя '09 в 00:52

1 ответ

Решение

Другие вопросы по тегам c++ stl iterator deque

user12711 02 ноя '09 в 06:18 2009-11-02 06:18 · Accepted Answer · 2009-11-02 06:18

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

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

Array of pointers           
(if this grows                 Data Pages
 and gets copied,           (these never move
 iterators are invalid)      due to insert at ends)
-----------------          --------------------

 +----------+               +----------+
 |         -+-------------->|          |
 +----------+               +----------+
 |         -+---------+     |          |
 +----------+         |     +----------+
 |         -+---+     |     |          |
 +----------+   |     |     +----------+ 
                |     |
                |     |
                |     |
                |     |     +----------+
                |     +---->|          |
                |           +----------+
                |           |          |
                |           +----------+
                |           |          |
                |           +----------+ 
                |           
                |           +----------+
                +---------->|          |
                            +----------+
                            |          |
                            +----------+
                            |          |
                            +----------+