#c
#c
Вопрос:
Проблема контейнеров STL заключается в том, что итераторы могут быть признаны недействительными при изменении контейнера. Возможно ли, чтобы контейнер объявил, что он изменился, добавив вызов has_changed()?
Обычно перед определенными операциями выполняется запрос empty(). Если контейнер установил bool для операций, которые будут влиять на итераторы, такие как insert() или erase(), тогда было бы возможно запросить has_changed() перед повторным использованием итератора.
Сумасшедший?
РЕДАКТИРОВАТЬ Спасибо за кучу хороших ответов и пищу для размышлений. Я хотел бы наградить более одного победителя.
Комментарии:
1. Итак, что бы вы сделали, если бы у вас был
Container::has_changed()
метод? Что бы вы сделали со своими итераторами?2. На самом деле вы, вероятно, хотели бы
bool Container::is_still_valid(Container::iterator)
. Это касается как возражений «изменено с тех пор?», так и возражений «не все итераторы становятся недействительными при каждом изменении». (Я назвал этоis_still_valid
потому что реализация намного проще, если вы ограничиваете ее итераторами, которые были действительны для этого контейнера в прошлом)
Ответ №1:
Своего рода безумие, хотя и с благими намерениями.
Я думаю, что основная проблема с этим заключается в том, как контейнер узнает, когда он имеет «неизмененный»? Другими словами, что-то стирается и устанавливается флаг «изменено». Что является ускоряющим событием, при котором он сбрасывает флаг, потому что он возвращается в нормальное или стабильное состояние? На самом деле в недопустимом состоянии находятся итераторы, а не контейнер.
Я думаю, что для того, чтобы это работало на всех итераторах, нужно было бы быть намного, намного умнее, чем они есть в настоящее время, и работать больше как наблюдатели за контейнером. Контейнер может отправлять зарегистрированным итераторам событие, которое он изменил, и они могут проверять свое собственное состояние перед попыткой выполнения операции. Но даже в этом есть так много дыр, что это, вероятно, привело бы к большему беспорядку, чем то, что вы пытаетесь решить.
Комментарии:
1. Согласен с ответом, некоторые реализации добавляют поддержку обнаружения изменений, в частности, реализация Dinkumware, поставляемая с VS, может быть скомпилирована с проверенными итераторами, которые обнаружат (и прервут), если контейнер изменился. Я полагаю, что фактическая реализация объясняется в видеоролике channel9. Обратите внимание, что проверенные итераторы работают намного медленнее, чем непроверенные. Влияние на производительность (как памяти, так и процессора) не является незначительным — ну, оно будет, если вы не используете итераторы широко…
Ответ №2:
(Приблизительный) способ работы отказоустойчивых итераторов в Java заключается в том, что контейнер увеличивает счетчик при каждом его изменении. Итераторы копируют этот счетчик при создании и увеличивают его каждый раз, когда контейнер изменяется с их помощью. Если итератор обнаруживает несоответствие, он выдает исключение.
C обладает замечательным свойством, заключающимся в том, что некоторые операции делают недействительными некоторые итераторы в контейнере, но не другие. Например, предположение, что зарезервировано достаточное пространство vector::insert
, делает недействительными итераторы после точки вставки, но не раньше.
Другой сложный случай list::remove
. Это оставляет действительными все итераторы, кроме удаленного, и все его копии.
Как вы можете себе представить, было бы довольно сложно отследить это точно. На практике случается так, что ваша реализация может предлагать варианты отладки, в которых итераторы будут делать все возможное, чтобы определить, являются ли они допустимыми или нет. Однако это может зависеть от деталей реализации того, будут ли они в настоящее время «работать», а не от того, гарантирует ли стандарт, что они все еще работают.
В C можно было бы сделать что-то похожее на «номер версии» в Java, но это дало бы ложные срабатывания итераторов, которые кажутся недействительными, но на самом деле являются действительными.
Ответ №3:
Правила признания недействительными итераторов достаточно ясны, чтобы, если вы платите по правилам, вам не нужно запрашивать контейнер, когда его контейнеры признаны недействительными.
Более того, итераторы не всегда признаются недействительными одновременно. Удаление элемента из середины вектора делает недействительным только этот элемент и следующий за ним. Но итераторы, указывающие на начало вектора, остаются действительными.
В списках итераторы обычно становятся недействительными только тогда, когда уничтожается конкретный узел, на который они указывают.
Таким образом, вы не можете спросить контейнер, является ли ваш итератор допустимым.
В реализациях обычных стандартных библиотек есть возможность включить дополнительные проверки во время выполнения, аналогичные тем, которые вы запрашиваете, хотя реализация более сложная (она должна быть, чтобы быть правильной), и это снижает производительность.
Комментарии:
1. Я не уверен, что согласен с тем, что «правила признания итераторов недействительными достаточно ясны». Кажется, существует множество правил. Они имеют смысл, когда вы думаете о том, почему они являются правилами, но все еще не всегда ясно или очевидно, когда операция сделает недействительным итератор (и какие итераторы могут быть признаны недействительными). Как указано в ваших следующих двух пунктах…
2. @Micheal: И правила тоже не слишком специфичны. Добавление к вектору может сделать недействительными все итераторы в нем. (Конечно, я мог бы проверить его емкость в зависимости от размера, но это именно то, о чем спрашивал OP.)
3. Верно, но есть явный компромисс. Чем более интеллектуальными и «безопасными» вы создаете итераторы, тем худшую производительность вы получите, тем менее универсальными они будут (удачи, чтобы указатель вел себя подобным образом), и тем сложнее их будет реализовать (и реализовать правильно). Правила иногда говорят вам не более чем «ваш итератор может быть признан недействительным», но они достаточно ясны, чтобы с ними можно было работать
Ответ №4:
Это было бы неэффективно, потому что контейнеру нужно было бы А) предоставить еще одно поле данных и Б) соответствующим образом обновить его. STL, однако, был придуман в попытке сделать невозможное и объединить эффективность с абстракцией. (И я должен добавить, что это удалось.)
Если вам нужно сохранить ссылки в изменяющемся контейнере, либо используйте тот, который не делает недействительными итераторы ( std::list
, std::set
), либо сохраняйте индексы в std::vector
.
Ответ №5:
Это технически возможно, и MSVC реализует «проверенные итераторы» (http://msdn.microsoft.com/en-us/library/aa985965.aspx ), которые предоставляют аналогичную функциональность. Хотя вы не получаете уведомления, когда итератор становится недействительным, и вы не можете напрямую запросить состояние (о котором я знаю), генерируется исключение и / или вызывается invalid_parameter
в зависимости от того, как настроена сборка.
Однако это явно нестандартно и значительно снижает производительность. Это полезно для отладки.
Ответ №6:
Возможно ли, чтобы контейнер объявил, что он изменился, добавив вызов has_changed()?
Я думаю, да, это может быть реализовано. Вот одна очень простая попытка (не такая элегантная, но все же):
bool has_changed(std::vector<int> amp;v)
{
static std::map<void*, size_t> has_changed_info;
void *ptr = amp;v;
std::map<void*, size_t>::iterator it = has_changed_info.find(ptr);
if (it == has_changed_info.end())
{
has_changed_info[ptr] = v.capacity();
return false;
}
if ( it->second != v.capacity() )
{
it->second = v.capacity();
return true;
}
return false;
}
Тестирование кода как:
int main() {
std::vector<int> v;
has_changed(v);
for ( int i = 0 ; i < 100 ; i )
{
v.push_back(i);
if (has_changed(v))
cout << "changed at " << i << endl;
}
return 0;
}
Вывод (GCC-4.3.4):
changed when inserting i = 0
changed when inserting i = 1
changed when inserting i = 2
changed when inserting i = 4
changed when inserting i = 8
changed when inserting i = 16
changed when inserting i = 32
changed when inserting i = 64
Онлайн-демонстрация:http://www.ideone.com/QmO5q