2010-01-14 2 views
50

Есть ли способ проверить, является ли итератор (будь то из вектора, списка, deque ...) (все еще), с возможностью удаления, т. Е. Не был признан недействительным?Проверка правильности итератора

Я использую try - catch, но есть ли более прямой способ сделать это?

Пример: (который не работает)

list<int> l; 
for (i = 1; i<10; i++) { 
    l.push_back(i * 10); 
} 

itd = l.begin(); 
itd++; 
if (something) { 
    l.erase(itd); 
} 

/* now, in other place.. check if itd points to somewhere meaningful */ 
if (itd != l.end()) 
{ 
    // blablabla 
} 
+5

В C++, когда вы просто изменяете итератор и не используете значение, вы всегда должны использовать '++ itd'' 'itd ++'. –

+6

После просмотра вашего нового примера кода обратите внимание, что методы стирания STL возвращают следующий итератор, который является допустимым итератором (хотя он может быть итератором конца). Поэтому, чтобы помочь сохранить его, вы можете сделать это: if (something) { itd = l.erase (itd); } –

+0

Mmm ... Я вижу ... – huff

ответ

53

Я предполагаю, что вы имеете в виду, что «является итератором действительным», что он не был аннулирован из-за изменений в контейнере (например, вставка/стирание в/из вектора). В этом случае нет, вы не можете определить, является ли итератор (безопасно) неразрешимым.

+5

Хотя, я думаю, пришло время ввести 'Проверенный STL' в битву: проверенная цель stl состоит в том, чтобы поймать ошибки итераторов> использование недействительных итераторов или сравнение итераторы из разных контейнеров. Поездка по проверенному stl обязательно должна быть частью вашего тестового набора;) –

+0

@Matthieu M: Я не думаю, что это произойдет в ближайшем будущем, так как это будет стоить, по крайней мере, 1. сохранить указатель на каждый итератор, который ссылается на вектор 2. При недействительности прохождения каждого элемента списка Производительные ястребы будут стрелять в него с миль. :( –

+3

@Ajeet: проверенный STL уже существует, обычно испеченный в традиционном STL, но '# ifdef'. Он стоит, замедляя код, но MSVC, например, имеет 2 уровня проверок, первый из которых очень доступен (второй, безусловно, медленный ...) ** Запомните, что это очевидно только для ** Test **. –

9

Обычно вы проверить его, проверяя, если оно отличается от конца(), как

if (it != container.end()) 
{ 
    // then dereference 
} 

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

+2

Итак, когда вы уничтожаете элемент, на который указывает итератор в списке, или элемент, расположенный раньше на векторе, итератор затем указывает на конец? Я не в моем случае ... (я отредактирую вопрос, чтобы быть более понятным) – huff

+0

При удалении и вставке * все * итераторы и ссылки могут быть уничтожены. Итак, вам лучше получить новые итераторы, прежде чем продолжить. Это потому, что напр. для добавления нового элемента иногда придется перераспределять всю память. Тогда это приведет к аннулированию всех указателей, ссылок и итераторов (которые в большинстве случаев очень похожи на указатели). – daramarak

+0

@huff. Вы должны прочитать документацию API vector :: erase и list :: erase, чтобы понять поведение. Кроме того, здесь есть несколько серых областей, где API был (по-прежнему?) Несколько отличается для Microsoft и GCC реализации std :: map :: erase, если я могу правильно запомнить. –

0
if (iterator != container.end()) { 
    iterator is dereferencable ! 
} 

Если итератор не делает равный container.end() и не разыменовываемыми, ты делаешь что-то неправильно.

3

Попытка и ловли небезопасны, вы не будете или, по крайней мере, редко бросаете, если ваш итератор «вне пределов».

что, как говорят alemjerus, итератор всегда может быть разыменован. Независимо от того, что уродство лежит ниже. Вполне возможно, итерация в другие области памяти и запись в другие области, которые могут содержать другие объекты. Я смотрю на код, наблюдая переменные изменения без особых причин. Это ошибка, которую трудно обнаружить.

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

Моим лучшим советом было бы держать вас итераторами под контролем и всегда держать «конец» итератора под рукой, чтобы иметь возможность проверить, находитесь ли вы в «конце линии», так сказать.

+2

С «можно разыменовать» вы, вероятно, имеете в виду: никто не помешает вам это сделать. Однако неопределенное поведение будет происходить при разыменовании недействительных итераторов. – xtofl

+1

Да, есть разница между разыменованием и безопасным разыменованием ... – daramarak

21

Как сказал jdehaan, если итератор не был признан недействительным и указывает на контейнер, вы можете проверить его, сравнив его с container.end().

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

std::vector<int>::iterator iter = vec.begin(); 
vec.resize(vec.capacity() + 1); 
// iter is now singular, you may only perform assignment on it, 
// there is no way in general to determine whether it is singular or not 
4

Есть ли способ, чтобы проверить, если итератор (будь то из вектора, список, дека ...) есть (еще) разыменовываемый, то есть не был признан недействительными?

Нет, не существует.Вместо этого вы должны контролировать доступ к контейнеру, пока ваш итератор существует, например:

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

  • Если существует риск того, что другие потоки могут изменить контейнер, пока ваш поток выполняет итерацию, то для того, чтобы сделать этот сценарий потокобезопасным, ваш поток должен получить какой-то замок на контейнере (чтобы он не позволял другим потокам изменять контейнер, в то время как он использует итератор)

Работы, подобные ловушке исключения, не будут работать.

Это конкретный экземпляр более общей проблемы: «Могу ли я проверить/определить, является ли указатель действительным?», Ответ на который обычно «нет», вы не можете проверить его: вместо этого вы должны управлять всеми распределениями памяти и удалениями, чтобы знал, сохраняется ли какой-либо данный указатель ».

+0

И в многопоточном сценарии это будет сосать, не так ли? l.erase (itd); itd = l.end(); - И другая нить сравнивает itd с l.end(). - Да, я знаю, что это не идеально, но шансы на другую нить, возникающую после стирания и перед назначением, настолько удалены ... eheheh: D – huff

9

непортабельному Ответ: Да - в Visual Studio

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

Прочитайте об этом на VC10 here (эта система может и фактически заменяет каждый выпуск, поэтому найдите документы, относящиеся к вашей версии).

Редактировать Кроме того, я должен добавить: итераторы отладки в визуальной студии предназначены для немедленного взрыва при их использовании (вместо этого не определено поведение); не позволять «запрашивать» их состояние.

+0

Это очень полезно. – newprint

-1

использование сотрите с приращением:

 
    if (something) l.erase(itd++); 

так что вы можете проверить правильность итератора.

0

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

Когда вы выполняете следующее, итератор вставляется перед его передачей для стирания функции.

if (something) l.erase(itd++);

0

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

Эта функция использует первый заданный итератор, чтобы исключить из контейнера элемент, на который указывает этот итератор, и даже те, которые следуют за ним. Некоторые контейнеры стирают только один элемент для одного итератора, а некоторые другие контейнеры стирают все элементы, за которыми следует один итератор (включая элемент, указанный этим итератором), до конца контейнера.Если функция стирания получает два итератора, то два элемента, обозначенные каждым итератором, удаляются из контейнера, а все остальные между ними стираются также из контейнера, , но дело в том, что каждый итератор, который передается функция стирания любого std-контейнера становится недействительной! Также:

Каждый итератор, который указывает на какой-то элемент, который был стерт из контейнера теряет силу, но он не пропускает конец контейнера!

Это означает, что итератор, указывающий на какой-либо элемент, который был удален из контейнера, не может сравниться с container.end(). Этот итератор недействителен, и поэтому он не является разыменованным, т. Е. Вы не можете использовать ни операторы * nor ->, но также не увеличивать, т. Е. Вы не можете использовать оператор ++, а также не уменьшаться, т. Е. Вы не можете используйте оператор -.

Это также не сопоставимо !!! И.Е. вы не можете даже использовать ни == nor! = operator

Фактически вы не можете использовать какой-либо оператор, который объявлен и определен в итераторе std. Вы не можете ничего сделать с этим итератором, как нулевой указатель.

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

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

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

Я сделал одну функцию, которая проверяет, проверяет, знает и возвращает true, является ли данный итератор недействительным или нет. Вы можете использовать функцию memcpy для получения состояния любого объекта, элемента, структуры, класса и т. Д., И, конечно, мы всегда используем функцию memset сначала для очистки или удаления нового буфера, структуры, класса или любого объекта или элемента :

bool IsNull(list<int>::iterator& i) //In your example, you have used list<int>, but if your container is not list, then you have to change this parameter to the type of the container you are using, if it is either a vector or deque, and also the type of the element inside the container if necessary. 
{ 
    byte buffer[sizeof(i)]; 
    memset(buffer, 0, sizeof(i)); 
    memcpy(buffer, &i, sizeof(i)); 
    return *buffer == 0; //I found that the size of any iterator is 12 bytes long. I also found that if the first byte of the iterator that I copy to the buffer is zero, then the iterator is invalid. Otherwise it is valid. I like to call invalid iterators also as "null iterators". 
} 

Я уже тестировал эту функцию, прежде чем отправил ее туда и обнаружил, что эта функция работает на меня.

Я очень надеюсь, что я полностью ответил на ваш вопрос, а также очень помог вам!

+0

Извините, но это всего лишь набор бессмысленных анекдотов, увенчанный бессмысленными или вредными идеями.(A) 'erase' не удаляет« два элемента »на своих итераторах ввода; он # 2 является концом/эксклюзивным. (B) Это то, что неверные итераторы делают на вашей реализации за один раз; моя может никогда не сбой, может произойти сбой при выходе, может бросить абсолютно случайный 'assert' из GTK +, _etc ._... (B) Не распространять такие крайне опасные идеи: все итераторы имеют одинаковый размер, что все -0x00 является _somehow_ признаком недействительности (& есть какая-то точка 'memset'ing буфера перед' memcpy'ing над всем этим _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ –

0

Есть ли способ проверить, если итератор разыменовываемый

Да, с помощью GCC debugging containers доступен как расширения GNU. Вместо std::list вы можете использовать __gnu_debug::list. Следующий код будет прерван, как только будет использован недопустимый итератор. Поскольку отладочные контейнеры налагают дополнительные накладные расходы, они предназначены только при отладке.

#include <debug/list> 

int main() { 
    __gnu_debug::list<int> l; 
    for (int i = 1; i < 10; i++) { 
    l.push_back(i * 10); 
    } 

    auto itd = l.begin(); 
    itd++; 
    l.erase(itd); 

    /* now, in other place.. check if itd points to somewhere meaningful */ 
    if (itd != l.end()) { 
    // blablabla 
    } 
} 

$ ./a.out 
/usr/include/c++/7/debug/safe_iterator.h:552: 
Error: attempt to compare a singular iterator to a past-the-end iterator. 

Objects involved in the operation: 
    iterator "lhs" @ 0x0x7ffda4c57fc0 { 
     type = __gnu_debug::_Safe_iterator<std::_List_iterator<int>, std::__debug::list<int, std::allocator<int> > > (mutable iterator); 
     state = singular; 
     references sequence with type 'std::__debug::list<int, std::allocator<int> >' @ 0x0x7ffda4c57ff0 
    } 
    iterator "rhs" @ 0x0x7ffda4c580c0 { 
     type = __gnu_debug::_Safe_iterator<std::_List_iterator<int>, std::__debug::list<int, std::allocator<int> > > (mutable iterator); 
     state = past-the-end; 
     references sequence with type 'std::__debug::list<int, std::allocator<int> >' @ 0x0x7ffda4c57ff0 
    } 
Aborted (core dumped)