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

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

8 голосов
/ 02 ноября 2009

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

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

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

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

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

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

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

1 Ответ

8 голосов
/ 02 ноября 2009

Я думаю, что причина, по которой итераторы становятся недействительными, но ссылки не могут быть из-за возможной реализации 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)
-----------------          --------------------

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