Re[5]: Цикл по Stl-коллекции, если нужно удаление - C/C++

Здравствуйте achp, Вы писали:

A>>>Э нет, мсье Тарасевич прав, тут есть где развернуться буквоеду! Гы-гы!

S>>>>>>Весь фокус в том, что постинкрементный operator++ ДЕЛАЕТ КОПИЮ текущего итератора, увеличивает текущий итератор и возвращает сохраненную копию. Таким образом, текущий итератор остается валидным

.

A>>>В том-то и дело, что для неперегруженного постинкремента копия может и не делаться (т. е., например, для int это, по всей вероятности, будет просто ассемблерная инструкция инкремента, вставленная после использования).

S>>operator++
S>>Цитирую: The value obtained by applying a postfix ++ is a value that the operand had before applying the operator [Note: the value obtained is a copy of the original value]
S>>Насчет ассемблера —
S>>

S>>int main ()
S>>{
S>>    int A = 0;
S>>    int B = 0;
S>>    B = A++;
S>>    return 0;
S>>}
S>>

S>>вот дезассемблированный кусок с коментариями
S>>

S>>// инициализация A
S>>0x8048556 <main+6>:     mov    DWORD PTR [ebp-4],0x0
S>>// инициализация B
S>>0x804855d <main+13>:    mov    DWORD PTR [ebp-8],0x0
S>>// делается копия A в eax
S>>0x8048564 <main+20>:    mov    eax,DWORD PTR [ebp-4]
S>>// содержимое eax записывается в B
S>>0x8048567 <main+23>:    mov    DWORD PTR [ebp-8],eax
S>>// инкрементируется A
S>>0x804856a <main+26>:    inc    DWORD PTR [ebp-4]
S>>

S>>

A>Ну и?

A>PS. Вообще, это такая дребедень — про побочные эффекты выражений и точки следования; лучше о них не задумываться, а то голова треснет!

Я имел ввиду. что промежуточная копия все-таки делается.
Замнем для ясности

Здравствуйте achp, Вы писали:

A>Здравствуйте santucco, Вы писали:
S>>Здравствуйте achp, Вы писали:
товарищи santucco & achp ! Настоятельно рекомендую пользоваться клавиатурой для
адекватного квотирования сообщения собеседника.

Здравствуйте santucco, Вы писали:

АТ>>Надо сказать, что это хоть и очень надежная, но все-таки завязка на особенность конкретной реализации (или даже всех конкретных реалиаций

). Описанный тобой алгоритм работы постинкремента относится только к перегруженному постинкременту, но не ко встроенному постинкременту. Таким образом, если вдруг каким-то образом окажется, что итератор контейнера 'std::list<int>' является скалярным типом, то все, что ты сказал о постинкременте не будет соответствовать действительности.

S>Если я не ошибаюсь, префиксный operator++() отличается от постфиксного operator++(int) именно тем, что префиксный возвращает уже увеличенное значение, а постфиксный — копию текущего значения.
S>(Извиняюсь за корявость высказывания, но надеюсь, меня все поняли

). Это справедливо и для скалярных типов. (standard, 5.2.6 , 5.3.2)
S>То есть я хотел сказать, что такое поведение постфиксного operator++ (int) обусловлено стандартом

Нет. Стандарт только говорит, что значение выражения 'i++' равно тому значению 'i', которое 'i' имело до инкремента. Это совсем не означает, что компилятору нужно делать какую-то копию переменной 'i'. И это совсем не означает, что вычисление значения выражения 'i++' сразу сопровождается увеличением значения 'i'. Увеличение значения 'i' — это побочный эффект оператора '++'. Он может произойти когда угодно (не позже следующей точки следования).

Я не хочу переписывать то, что уже десять раз писал. Интересующиеся могут посмотреть вот эту дискуссию на ту же тему в 'fido7.nice.sources' (начиная с того момента, когда в дискуссию вступил я

http://groups.google.com/groups?dq=&hl=en&lr=&ie=UTF-8&oe=UTF-8&threadm=3D3B19D2.6441E5F6%40telocity.com

Здравствуйте santucco, Вы писали:

S>>>[/ccode]
S>>>вот дезассемблированный кусок с коментариями
S>>>

S>>>// инициализация A
S>>>0x8048556 <main+6>:     mov    DWORD PTR [ebp-4],0x0
S>>>// инициализация B
S>>>0x804855d <main+13>:    mov    DWORD PTR [ebp-8],0x0
S>>>// делается копия A в eax
S>>>0x8048564 <main+20>:    mov    eax,DWORD PTR [ebp-4]
S>>>// содержимое eax записывается в B
S>>>0x8048567 <main+23>:    mov    DWORD PTR [ebp-8],eax
S>>>// инкрементируется A
S>>>0x804856a <main+26>:    inc    DWORD PTR [ebp-4]
S>>>

S>Я имел ввиду. что промежуточная копия все-таки делается.

Никакой "умышленной" промежуточной копии в твоем дизасемблированном примере не делается. Регистр 'eax' использовался не потому, что нужна была копия, а потому, что у x86 команда 'mov' не имеет формата память-память. Если бы она ее имела, то код мог бы быть таким

mov    DWORD PTR [ebp-4],0x0
mov    DWORD PTR [ebp-8],0x0
mov    DWORD PTR [ebp-8],DWORD PTR [ebp-4]
inc    DWORD PTR [ebp-4]

Никаких копий.

На самом деле, делается копия или не делается — ниакого значения не имеет. Значение имеет то, когда происходит сдвиг оригинального итератора в коде 'List.erase( Iter++ )' — до вызова 'erase' или после.

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

1) Сделать копию 'Iter' (назовем ее 'Iter_Copy')
2) Сдвинуть 'Iter'
3) Вызвать 'erase(Iter_Copy)'

Заметь, что к моменту вызова 'erase' значение 'Iter' уже поменялось и уже не соответствует удаляемому элементу. Поэтому этот итератор остается валидным и все работает нормально.

Есди бы 'Iter' было объектом скалярного типа, то оператор '++' уже не являлся бы функцией. Момент сдвига 'Iter' был бы уже не определен. В частности, компилятор мог бы работать по вышеприведенному алгоритму, а мог бы и работать по вот такому алгоритму:

1) Вызвать 'erase(Iter)'
2) Сдвинуть 'Iter'

В этом варианте к моменту сдвига 'Iter' соответствует удаленному элементу. Резултат — неопределеное поведение. Твой дизасемблированный вариант как раз является иллюстрацией такого порядка выполнения: заметь, что присваивание значения из 'A' в 'B' сделано до увеличения значения 'A'.

Здравствуйте Андрей Тарасевич, Вы писали:

АТ>Здравствуйте santucco, Вы писали:

S>>>>[/ccode]
S>>>>вот дезассемблированный кусок с коментариями
S>>>>

S>>>>// инициализация A
S>>>>0x8048556 <main+6>:     mov    DWORD PTR [ebp-4],0x0
S>>>>// инициализация B
S>>>>0x804855d <main+13>:    mov    DWORD PTR [ebp-8],0x0
S>>>>// делается копия A в eax
S>>>>0x8048564 <main+20>:    mov    eax,DWORD PTR [ebp-4]
S>>>>// содержимое eax записывается в B
S>>>>0x8048567 <main+23>:    mov    DWORD PTR [ebp-8],eax
S>>>>// инкрементируется A
S>>>>0x804856a <main+26>:    inc    DWORD PTR [ebp-4]
S>>>>

S>>Я имел ввиду. что промежуточная копия все-таки делается.

АТ>Никакой "умышленной" промежуточной копии в твоем дизасемблированном примере не делается. Регистр 'eax' использовался не потому, что нужна была копия, а потому, что у x86 команда 'mov' не имеет формата память-память. Если бы она ее имела, то код мог бы быть таким

АТ>

АТ>mov    DWORD PTR [ebp-4],0x0
АТ>mov    DWORD PTR [ebp-8],0x0
АТ>mov    DWORD PTR [ebp-8],DWORD PTR [ebp-4]
АТ>inc    DWORD PTR [ebp-4]
АТ>

АТ>Никаких копий.

АТ>На самом деле, делается копия или не делается — ниакого значения не имеет. Значение имеет то, когда происходит сдвиг оригинального итератора в коде 'List.erase( Iter++ )' — до вызова 'erase' или после.

АТ>Вариант с итератором класс-типа будет работать правильно по единственной причине — использованный оператор '++' является пользовательской функцией, которая вызыватся и производит все свои действия (влючая сдвиг итератора) до того, как призсходит вызов 'erase'. Т.е. этот код работает по такому алгоритму:

АТ>1) Сделать копию 'Iter' (назовем ее 'Iter_Copy')
АТ>2) Сдвинуть 'Iter'
АТ>3) Вызвать 'erase(Iter_Copy)'

АТ>Заметь, что к моменту вызова 'erase' значение 'Iter' уже поменялось и уже не соответствует удаляемому элементу. Поэтому этот итератор остается валидным и все работает нормально.

АТ>Есди бы 'Iter' было объектом скалярного типа, то оператор '++' уже не являлся бы функцией. Момент сдвига 'Iter' был бы уже не определен. В частности, компилятор мог бы работать по вышеприведенному алгоритму, а мог бы и работать по вот такому алгоритму:

АТ>1) Вызвать 'erase(Iter)'
АТ>2) Сдвинуть 'Iter'

АТ>В этом варианте к моменту сдвига 'Iter' соответствует удаленному элементу. Резултат — неопределеное поведение. Твой дизасемблированный вариант как раз является иллюстрацией такого порядка выполнения: заметь, что присваивание значения из 'A' в 'B' сделано до увеличения значения 'A'.
Я дико извиняюсь, может я чего недопонимаю, но если бы я вместо

 int B = A++;

написал бы

 any_func ( A++ );

в any_func () попала бы копия A, не так ли?
И не важно, что что момент сдвига A был бы после вызова any_func () — то, что в any_func () передается, никакой связи с A уже не имеет

Здравствуйте Андрей Тарасевич, Вы писали:

АТ>Есди бы 'Iter' было объектом скалярного типа, то оператор '++' уже не являлся бы функцией. Момент сдвига 'Iter' был бы уже не определен. В частности, компилятор мог бы работать по вышеприведенному алгоритму, а мог бы и работать по вот такому алгоритму:

АТ>1) Вызвать 'erase(Iter)'
АТ>2) Сдвинуть 'Iter'

А разве здесь нет точки следования?

Здравствуйте santucco, Вы писали:

АТ>>Вариант с итератором класс-типа будет работать правильно по единственной причине — использованный оператор '++' является пользовательской функцией, которая вызыватся и производит все свои действия (влючая сдвиг итератора) до того, как призсходит вызов 'erase'. Т.е. этот код работает по такому алгоритму:

АТ>>1) Сделать копию 'Iter' (назовем ее 'Iter_Copy')
АТ>>2) Сдвинуть 'Iter'
АТ>>3) Вызвать 'erase(Iter_Copy)'

АТ>>Заметь, что к моменту вызова 'erase' значение 'Iter' уже поменялось и уже не соответствует удаляемому элементу. Поэтому этот итератор остается валидным и все работает нормально.

АТ>>Есди бы 'Iter' было объектом скалярного типа, то оператор '++' уже не являлся бы функцией. Момент сдвига 'Iter' был бы уже не определен. В частности, компилятор мог бы работать по вышеприведенному алгоритму, а мог бы и работать по вот такому алгоритму:

АТ>>1) Вызвать 'erase(Iter)'
АТ>>2) Сдвинуть 'Iter'

АТ>>В этом варианте к моменту сдвига 'Iter' соответствует удаленному элементу. Резултат — неопределеное поведение. Твой дизасемблированный вариант как раз является иллюстрацией такого порядка выполнения: заметь, что присваивание значения из 'A' в 'B' сделано до увеличения значения 'A'.
S>Я дико извиняюсь, может я чего недопонимаю, но если бы я вместо
S>

S> int B = A++;
S>

S>написал бы
S>

S> any_func ( A++ );
S>

S>в any_func () попала бы копия A, не так ли?
S>И не важно, что что момент сдвига A был бы после вызова any_func () — то, что в any_func () передается, никакой связи с A уже не имеет :-)))

Как это не имеет? Разумеется имеет. Вернемся к примеру с итератором и 'std::list'. Пусть унест есть список 'list' и итератор 'it', который указывает куда-то внутрь списка. Рассмотрим такой код:

// Пример 1
std::list<int>::iterator it2 = it;
list.erase(it2);
it++;

Что произойдет при выполнении этого кода? Скорее всего, программа рухнет при попытке выполнить '++' (а если и не рухнет, то все равно ничего хорошего из этого не выйдет). Программа рухнет, несмотря на то, что 'erase' работало с итератором 'it2', а '++' мы применяем к итератору 'it'. Казалось бы — 'it' и 'it2' два совешенно независимых итератора, 'it2' — это просто копия 'it', которая "никакой связи с 'it' уже не имеет". Почему же программа рухает? Потому, что связь (хоть и косвенная) между итераторами 'it' и 'it2' есть. Она заключается в том, что оба этих итератора указывают на один и тот же элемент. Если этот элемент уничтожить, что все итераторы, связанные с ним, "подвиснут" и поптыка применить к ним '++' приведет к падению программы.

Исходный вариант

// Пример 2
list.erase(it++);

с итератором класс-типа работает нормально по той причине, что сдвиг ('++') итератора гарантированно происходит до вызова метода 'erase'. Т.е. этот код эквивалентен вот такому:

// Пример 3
std::list<int>::iterator it2 = it;
it++;
list.erase(it2);

Итератор 'it' остается валидным только потому, что он был сдвинут операцией '++' до того, как произошло удаление, т.е. он успел "убежать" с удаляемого элемента.

Но гарантия на то, что '++' будет произведен до удаления имеет место быть только для иетраторов класс-типов. Если бы 'std::list<int>::iterator' являлся скалярным типом, то к нему применялся бы встроенный оператор '++'. В этом случае нельзя было бы гарантировать, что сдвиг итератора произойдет до 'erase' и компилятор имел бы полное право транслировать код примера 2 в что-то подобное примеру 1 со всем вытекающими последствиями.

АТ>1) Вызвать 'erase(Iter)'
АТ>2) Сдвинуть 'Iter'

АТ>В этом варианте к моменту сдвига 'Iter' соответствует удаленному элементу. Резултат — неопределеное поведение. Твой дизасемблированный вариант как раз является иллюстрацией такого порядка выполнения: заметь, что присваивание значения из 'A' в 'B' сделано до увеличения значения 'A'.

Но, мы же говорим о скаляре, не так ли ? Как увеличение указателя (скаляра) может привести к неопределённому поведению ?

void nof(int *) {}
int i[10];
int * p=i-1;
nof(p++);

Если ISO C++ усматривает в этом коде undefined behaviour, то я разочарован в С++.

Здравствуйте Аноним, Вы писали:

А>Но, мы же говорим о скаляре, не так ли ? Как увеличение указателя (скаляра) может привести к неопределённому поведению ?

А>void nof(int *) {}
А>int i[10];
А>int * p=i-1;

Здесь уже неопределенное поведение — при вычислении 'i-1'.

Здравствуйте Андрей Тарасевич, Вы писали:

АТ>

АТ>// Пример 2
АТ>list.erase(it++);
АТ>

АТ>с итератором класс-типа работает нормально по той причине, что сдвиг ('++') итератора гарантированно происходит до вызова метода 'erase'. Т.е. этот код эквивалентен вот такому:

АТ>

АТ>// Пример 3
АТ>std::list<int>::iterator it2 = it;
АТ>it++;
АТ>list.erase(it2);
АТ>

АТ>Итератор 'it' остается валидным только потому, что он был сдвинут операцией '++' до того, как произошло удаление, т.е. он успел "убежать" с удаляемого элемента.

АТ>Но гарантия на то, что '++' будет произведен до удаления имеет место быть только для иетраторов класс-типов. Если бы 'std::list<int>::iterator' являлся скалярным типом, то к нему применялся бы встроенный оператор '++'. В этом случае нельзя было бы гарантировать, что сдвиг итератора произойдет до 'erase' и компилятор имел бы полное право транслировать код примера 2 в что-то подобное примеру 1 со всем вытекающими последствиями.

Что-то я не пойму: 'erase' — функция или нет?

Здравствуйте Аноним, Вы писали:

АТ>>1) Вызвать 'erase(Iter)'
АТ>>2) Сдвинуть 'Iter'

АТ>>В этом варианте к моменту сдвига 'Iter' соответствует удаленному элементу. Резултат — неопределеное поведение. Твой дизасемблированный вариант как раз является иллюстрацией такого порядка выполнения: заметь, что присваивание значения из 'A' в 'B' сделано до увеличения значения 'A'.

А>Но, мы же говорим о скаляре, не так ли ? Как увеличение указателя (скаляра) может привести к неопределённому поведению ?

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

А>void nof(int *) {}
А>int i[10];
А>int * p=i-1;
А>nof(p++);

А>Если ISO C++ усматривает в этом коде undefined behaviour, то я разочарован в С++.

Да, это undefined behavior. Вот это тоже undefined behavior:

int* p = new int[10];
delete[] p;
p++; // <- undefined behavior т.к. массива уже нет

Правда причин для разочарования я тут не вижу.

Здравствуйте Андрей Тарасевич, Вы писали:

АТ>Здравствуйте Аноним, Вы писали:

АТ>>>1) Вызвать 'erase(Iter)'
АТ>>>2) Сдвинуть 'Iter'

АТ>>>В этом варианте к моменту сдвига 'Iter' соответствует удаленному элементу. Резултат — неопределеное поведение. Твой дизасемблированный вариант как раз является иллюстрацией такого порядка выполнения: заметь, что присваивание значения из 'A' в 'B' сделано до увеличения значения 'A'.

А>>Но, мы же говорим о скаляре, не так ли ? Как увеличение указателя (скаляра) может привести к неопределённому поведению ?

АТ>С++ разрешает применять адресную арифметику только к указателям, которые в данный момент указывают на элемент некотрого существующего массива или на воображаемый элемент, следующий за последним элементом массива.

Как же так ? Ведь указатель — это просто N битное число, и его увеличнение — дело N битной арифметики.
А про "воображаемый элемент" я вообще не понял. Это что за элемент такой ?
И, последний вопрос — нельзя ли ссылочку на стандарт ?

Здравствуйте Аноним, Вы писали:

АТ>>С++ разрешает применять адресную арифметику только к указателям, которые в данный момент указывают на элемент некотрого существующего массива или на воображаемый элемент, следующий за последним элементом массива.

А>Как же так ? Ведь указатель — это просто N битное число, и его увеличнение — дело N битной арифметики.

Откуда это ты такое взял? Это в плоской модели памяти указатель является "просто числом". А в сегментной адресации, например, все намного сложнее.

А>А про "воображаемый элемент" я вообще не понял. Это что за элемент такой ?

Вооображаемый. Вот пример кода:

int i[10];
int p = i + 10;

Теперь 'p' указывает не несуществующий элемент массива ('i[10]'), следующий за последним элементом ('i[9]'). Тем не менее этот код не вызывает неопределенного поведения, ибо адресная арифметика C++ разрешает создание указателей на такой воображаемый элемент.

А>И, последний вопрос — нельзя ли ссылочку на стандарт ?

Можно, конечно. В стандарте С++ арифметические операции над указателями описаны в 5.7. Сравнение указателей — в 5.9. Там это все подробно и описано. Аналогичные разделы есть в стандарте C.

Здравствуйте Аноним, Вы писали:

АТ>>Но гарантия на то, что '++' будет произведен до удаления имеет место быть только для иетраторов класс-типов. Если бы 'std::list<int>::iterator' являлся скалярным типом, то к нему применялся бы встроенный оператор '++'. В этом случае нельзя было бы гарантировать, что сдвиг итератора произойдет до 'erase' и компилятор имел бы полное право транслировать код примера 2 в что-то подобное примеру 1 со всем вытекающими последствиями.

А>Что-то я не пойму: 'erase' — функция или нет?

Хм... Что-то я уже и сам сомневаюсь в правильности своих рассуждений. Действительно, 'erase' — функция и, будучи функцией, имеет точку следования на входе. Следовательно, побочный эффект '++' должен выполнится до вызова 'erase'. ОК, замяли. Посыпаю голову пеплом. Все будет работать нормально и со скалярными типами.

Здравствуйте, DarkGray, Вы писали:

DG>А как уважаемый All пишет цикл по Stl-ной коллекции, если во время этого самого цикла нужна возможность удаления текущего элемента?

DG>Сейчас пишу так:
DG>

DG>for (std::list<int>::iterator it = items.begin(), nit; it != items.end(); it = nit)
DG>{
DG>  nit = it; ++nit;
DG>  if (*it == 0)
DG>    erase (it); 
DG>}
DG>

в этом примере всё летит в тартарары, если удаляется последний элемент списка. Лучше с while использовать, что ниже подсказали.

PS: я видел дату сообщения.

DG>P.S. Я знаю, что есть remove_if, но меня интересует именно for

Здравствуйте, Bell, Вы писали:

B>Здравствуйте DarkGray, Вы писали:

DG>>


B>      it = aCont.erase(it);
B>

По стандарту erase ничего не возвращает, такое прокатывает только на MSVC

Здравствуйте, DarkGray, Вы писали:

DG>P.S. Я знаю, что есть remove_if, но меня интересует именно for

Почитали бы Вы, батенька, Effective STL, зело хорошая книжка. Желание писать не-функторный код пропадает быстро.

Здравствуйте, Аноним, Вы писали:

DG>>P.S. Я знаю, что есть remove_if, но меня интересует именно for
А>Почитали бы Вы, батенька, Effective STL, зело хорошая книжка. Желание писать не-функторный код пропадает быстро.
Ничего страшного, увлечение функторным кодом проходит

Здравствуйте, DEMON HOOD, Вы писали:

DH>в этом примере всё летит в тартарары, если удаляется последний элемент списка. Лучше с while использовать, что ниже подсказали.

Интересно узнать почему...

Здравствуйте, Андрей Тарасевич, Вы писали:

АТ>Откуда это ты такое взял? Это в плоской модели памяти указатель является "просто числом". А в сегментной адресации, например, все намного сложнее.

Смешались в кучу кони, люди... (к) старший заряжающий

Чтобы при работе адресной арифметики "навредить" сегментной адресации (хинт: вообще-то в "плоской" модели она такая же "сегментная" — просто там "сегменты" 32- или 64-битные...) — это надо в компилятор много-много спирта залить. Ну или же, поскольку природа его не биологическая, применить к нему крепкие вихревые токи...

ЗЫ. Я видел дату исходного сообщения. Холивар действительно интересный и полезный. Вообще-то, имхо, "сбить" целочисленный индекс невозможно: он либо есть, либо его нет. Если операция _удаления_ "сбивает" идексацию — сколько индекс элемента за удаляемым не сохраняй — все равно получишь ж. В связанных списках как раз не работает одно и работает другое — "инкремент" индекса (итератора) после удаления соотв. элемента и предварительный инкремент итератора перед удалением — исходя из природы связанного списка. Будет ли та же процедура работать в векторе?

	От:	santucco
	Дата:	25.07.02 10:03
	Оценка:

	От:	Igor Soukhov
	Дата:	25.07.02 17:08
	Оценка:

	От:	Андрей Тарасевич
	Дата:	25.07.02 17:55
	Оценка:	3 (1)

	От:	Андрей Тарасевич
	Дата:	25.07.02 18:31
	Оценка:

	От:	santucco
	Дата:	26.07.02 08:12
	Оценка:

	От:	AndrewJD
	Дата:	11.12.07 14:18
	Оценка:	1 (1) +2