Блог

Проблема контейнеров STL заключается в том, что итераторы могут быть признаны недействительными при изменении контейнера. Возможно ли, чтобы контейнер объявил, что он изменился, добавив вызов has_changed()?

Обычно перед определенными операциями выполняется запрос empty(). Если контейнер установил bool для операций, которые будут влиять на итераторы, такие как insert() или erase(), тогда было бы возможно запросить has_changed() перед повторным использованием итератора.

Сумасшедший?

РЕДАКТИРОВАТЬ Спасибо за кучу хороших ответов и пищу для размышлений. Я хотел бы наградить более одного победителя.

Своего рода безумие, хотя и с благими намерениями.

Я думаю, что основная проблема с этим заключается в том, как контейнер узнает, когда он имеет «неизмененный»? Другими словами, что-то стирается и устанавливается флаг «изменено». Что является ускоряющим событием, при котором он сбрасывает флаг, потому что он возвращается в нормальное или стабильное состояние? На самом деле в недопустимом состоянии находятся итераторы, а не контейнер.

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

(Приблизительный) способ работы отказоустойчивых итераторов в Java заключается в том, что контейнер увеличивает счетчик при каждом его изменении. Итераторы копируют этот счетчик при создании и увеличивают его каждый раз, когда контейнер изменяется с их помощью. Если итератор обнаруживает несоответствие, он выдает исключение.

C обладает замечательным свойством, заключающимся в том, что некоторые операции делают недействительными некоторые итераторы в контейнере, но не другие. Например, предположение, что зарезервировано достаточное пространство vector::insert , делает недействительными итераторы после точки вставки, но не раньше.

Другой сложный случай list::remove . Это оставляет действительными все итераторы, кроме удаленного, и все его копии.

Как вы можете себе представить, было бы довольно сложно отследить это точно. На практике случается так, что ваша реализация может предлагать варианты отладки, в которых итераторы будут делать все возможное, чтобы определить, являются ли они допустимыми или нет. Однако это может зависеть от деталей реализации того, будут ли они в настоящее время «работать», а не от того, гарантирует ли стандарт, что они все еще работают.

В C можно было бы сделать что-то похожее на «номер версии» в Java, но это дало бы ложные срабатывания итераторов, которые кажутся недействительными, но на самом деле являются действительными.

Правила признания недействительными итераторов достаточно ясны, чтобы, если вы платите по правилам, вам не нужно запрашивать контейнер, когда его контейнеры признаны недействительными.

Более того, итераторы не всегда признаются недействительными одновременно. Удаление элемента из середины вектора делает недействительным только этот элемент и следующий за ним. Но итераторы, указывающие на начало вектора, остаются действительными.

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

Таким образом, вы не можете спросить контейнер, является ли ваш итератор допустимым.

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

Это было бы неэффективно, потому что контейнеру нужно было бы А) предоставить еще одно поле данных и Б) соответствующим образом обновить его. STL, однако, был придуман в попытке сделать невозможное и объединить эффективность с абстракцией. (И я должен добавить, что это удалось.)

Если вам нужно сохранить ссылки в изменяющемся контейнере, либо используйте тот, который не делает недействительными итераторы ( std::list , std::set ), либо сохраняйте индексы в std::vector .

Это технически возможно, и MSVC реализует «проверенные итераторы» (http://msdn.microsoft.com/en-us/library/aa985965.aspx ), которые предоставляют аналогичную функциональность. Хотя вы не получаете уведомления, когда итератор становится недействительным, и вы не можете напрямую запросить состояние (о котором я знаю), генерируется исключение и / или вызывается invalid_parameter в зависимости от того, как настроена сборка.

Однако это явно нестандартно и значительно снижает производительность. Это полезно для отладки.

Возможно ли, чтобы контейнер объявил, что он изменился, добавив вызов 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