Как ссылки могут быть действительными, пока итераторы становятся недействительными в deque
У меня возникли трудности с пониманием этой концепции. Из этого нить здесь говорится
Дек требует, чтобы любая вставка спереди или сзади сохраняла
любая ссылка на элемент-член действительна. Это нормально для итераторов
признаны недействительными, но сами члены должны оставаться на том же месте в
объем памяти.
Я был под впечатлением от этот поток, который заявляет
Указатель на самом деле является типом итератора. Фактически для некоторых типов контейнеров соответствующий итератор может быть
реализован просто как указатель.Если у нас есть указатель и итератор, каждый из которых ссылается на одно и то же
элемент контейнера, то любая операция, которая делает его недействительным, будет
лишить законной силы другого.
поэтому, если итератор становится недействительным, ссылки также становятся недействительными.
Мой вопрос: как это возможно? Если итератор, который указывает на определенный адрес памяти, становится недействительным, как может быть действительной ссылка на этот адрес?
Обновить:
Я понимаю, что deque реализуется случайными порциями памяти, и эти порции памяти отслеживаются независимой структурой данных, такой как динамический массив. Однако у меня возникают трудности с пониманием того, как итератор может быть недействительным, но ссылка может быть действительной, поскольку, по сути, итератор является обобщенным указателем на содержимое структуры данных. Это заставляет меня думать, что итератор может указывать на что-то еще, в то время как указатель указывает на фактический элемент? Рассмотрим следующую диаграмму вектора.
Из того, что я понимаю на диаграмме выше для вектора, это то, что если содержимое указателя изменяется, итератор также изменяется. Как это отличается для deque.
Решение
Думайте о deque с точки зрения следующего:
template<typename T>
struct deque_stub {
using Page = std::array<T, 32>; // Note: Not really, rather uninitialised memory of some size;
std::vector<std::unique_ptr<Page>> pointers_to_pages;
std::size_t end_insert{32};
std::size_t start_elem{0};
// read further
};
Deque — это в основном некоторый контейнер, хранящий указатели на страницы, которые содержат некоторые элементы. (The start_elem а также end_insert члены должны отслеживать, где, с точки зрения смещения на странице, допустимый диапазон элементов начинается и заканчивается.)
Вставка в конечном итоге изменяет этот контейнер, когда требуется новая страница:
template<typename X>
void push_back(X&& element) {
if (end_insert == 32) {
// get a new page at the end
pointers_to_pages.push_back(make_unique<Page>());
end_insert = 0;
}
(*(pointers_to_pages.back()))[end_insert] = std::forward<X>(element);
++end_insert;
}
template<typename X>
void push_front(X&& element) {
if (start_elem == 0) {
pointers_to_pages.insert(
pointers_to_pages.begin(), std::make_unique<Page>());
start_elem = 32;
}
--start_elem;
(*(pointers_to_pages.front()))[start_elem] = std::forward<X>(element);
}
Итератор в эту очередь должен уметь «перепрыгивать» через страницы. Самый простой способ добиться этого — сохранить итератор на текущей странице контейнера. pointers_to_pages:
struct iterator {
std::size_t pos;
std::vector<std::unique_ptr<Page>>::iterator page;
// other members to detect page boundaries etc.
};
Но с тех пор page Итератор, итератор в векторе, может быть признан недействительным при изменении вектора (что происходит, когда требуется новая страница), весь итератор в deque может стать недействительным при вставке элементов. (Это можно «исправить», не используя вектор в качестве контейнера для указателей, хотя это, вероятно, будет иметь другие негативные побочные эффекты.)
В качестве примера рассмотрим дек с одной, но полной страницей. Таким образом, вектор, содержащий указатели на страницы, содержит только один элемент, скажем, по адресу. 0x10и давайте далее предположим, что его текущая емкость также составляет всего 1 элемент. Сама страница хранится по какому-то адресу, скажем 0x100,
Таким образом, первый элемент deque фактически хранится в 0x100, но использование итератора в deque означает сначала смотреть на 0x10 для адреса страницы.
Теперь, если мы добавим еще один элемент в конце, нам понадобится новая страница для его хранения. Поэтому мы выделяем один и сохраняем указатель на эту новую страницу в векторе. Так как его емкость меньше нового размера (1 < 2), ему нужно выделить новую большую область памяти и переместить туда ее текущее содержимое. Допустим, что новая область находится на 0x20, Память, где указатели были сохранены ранее (0x10) освобожден.
Теперь тот же элемент сверху до вставки остается по тому же адресу (0x100), но итератор к нему пройдет через 0x20, Итератор сверху, доступ к 0x10, таким образом, является недействительным.
Поскольку элемент находится по тому же адресу, указатели и ссылки на него остаются действительными, жесткими.
Другие решения
Потому что вы цитируете ответ неправильно, и потому что итераторы намного больше, чем просто указатели. Для начала итератору связанного списка нужен указатель на элемент, а также указатели «следующий» и «предыдущий». Прямо там, на этом простом примере, ваше представление о том, что «итератор — это обобщенный указатель на содержимое структуры данных» полностью выдувается из воды.
deque является более сложным, чем полностью смежная структура (например, vector) и более сложная, чем полностью несмежная структура (т.е. list). Когда deque растет, его общая структура формируется, чтобы соответствовать, с минимумом перераспределения фактических элементов (часто, никто).
В результате этого, даже когда определенные элементы не перемещаются, «контрольные элементы», которые разрешают доступ к ним, могут нуждаться в обновлении новыми метаданными, например, о том, где находятся соседние элементы (которые могут быть сделал двигаться) сейчас есть.
Теперь deque не может волшебным образом обновить итераторы, которые уже где-то были созданы: все, что он может сделать, это документировать, что ваши старые итераторы недействительны и что вы должны получить новые обычным способом.