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

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

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

А>

А> std::list <int> List;
А> ...  
А> list <int>::iterator Iter = List.begin ();
А> while ( Iter != List.end () ) 
А>    List.erase ( Iter++ );
А>

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

.
А>Good luck

Я вот хочу немножко завистливо попридираться (Так просто для иллюстрации того факта, что придраться всегда есть к чему)

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

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

Нет, я не могу с ходу представить, как можно релизовать итератор контейнера 'std::list<int>' скалярным типом. Да и не нужно это никому. Но такая вот чисто теоретическая придирка к твоему коду может иметь место.

Здравствуйте 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 со всем вытекающими последствиями.

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

 std::list <int> List;
 ...  
 list <int>::iterator Iter = List.begin ();
 while ( Iter != List.end () ) 
    List.erase ( Iter++ );

Для for'a можно немного переделать.
Весь фокус в том, что постинкрементный operator++ ДЕЛАЕТ КОПИЮ текущего итератора, увеличивает текущий итератор и возвращает сохраненную копию. Таким образом, текущий итератор остается валидным :-).
Good luck

Здравствуйте 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>Здравствуйте Андрей Тарасевич, Вы писали:

АТ>>Я вот хочу немножко завистливо попридираться (Так просто для иллюстрации того факта, что придраться всегда есть к чему)

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

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

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

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

S>

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

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

.

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

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

АТ>

АТ>// Пример 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' — функция или нет?

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

Т.е. что-то такое:

for (std::list<int>::iterator it = items.begin(); it != items.end(); ++it)
{
  if (*it == 0)
    erase (it); //это есть неправильно.
}

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

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

Как еще можно такие циклы писать?

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

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

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

Здравствуйте Anton V. Kolotaev, Вы писали:

AVK>

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

Такой цикл плох тем, что при его использовния надо помнить, что нельзя использовать continue.

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

DG>Такой цикл плох тем, что при его использовния надо помнить, что нельзя использовать continue.
не верю

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

Например, сначала очистить от нулевых элементов, а потом сделать пользу.

ИМХО ты намудрил.

приведи пример, где такой continue все портит.

Здравствуйте Anton V. Kolotaev, Вы писали:

AVK>Например, сначала очистить от нулевых элементов, а потом сделать пользу.

AVK>ИМХО ты намудрил.

AVK>приведи пример, где такой continue все портит.

Первое, что нашлось.

            for (CallbacksTimeIndex::HardLowTimeIndex::TIndex::iterator it = pt->callbacks_time_index.hard_low_time_index.index.begin(), nit = it; 
              it != pt->callbacks_time_index.hard_low_time_index.index.end(); it = nit)
            {
              nit++;
              CallbackInfo callback = it->second->second;
              if (callback.low_time > cur_time)
                break;

  #ifdef _TRACE_HARD_QUERIES_
              DBG (CFormatString("Time: %t") << CoFileTimeNow());
  #endif
              Items::Items::iterator fit = pt->items.items.find (callback.item_handle);
              if (fit == pt->items.items.end())
                continue;
                            
              bool is_readed = false;
              ValueInfo & value = pt->items_cash[fit->second.kind];
              if ((value.quality & QUALITY_MASK) != QUALITY_BAD)
              {
                LONGLONG dtime = cur_time - FileTime2LongLong (value.time);
                if (2 * dtime < callback.period)
                  is_readed = true;
              }
              if (is_readed)
              {
                pt->UpdateQuery (it, value);
              }
              else
              {
                qmap[Kind2Kind(fit->second.kind)] = MapValue();
              }
            }

удаление элемента происходит в функции 'pt->UpdateQuery'.

P.S. Вот еще одна нехорошость твоего цикла, erase нужно обязательно вызывать из самого цикла, а часто хочется вынести удаление элемента в отдельную функцию...

Здравствуйте DarkGray,

Сложный случай.

Вариант с nit — по-моему, лучшее, что можно придумать.

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

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

DG>Т.е. что-то такое:
DG>

DG>for (std::list<int>::iterator it = items.begin(); it != items.end(); ++it)
DG>{
DG>  if (*it == 0)
DG>    erase (it); //это есть неправильно.
DG>}
DG>

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>

DG>Как еще можно такие циклы писать?

Может так подойдет?

std::list<int*> aCont;
...
std::list<int*>::iterator it = aCont.begin();
while(it != aCont.end())
{
   if(!(*it))
      it = aCont.erase(it);
   else
      ++it;
}

Здравствуйте Anton V. Kolotaev, Вы писали:

AVK>Здравствуйте DarkGray,

AVK>Сложный случай.

AVK>Вариант с nit — по-моему, лучшее, что можно придумать.

Для list согласен. А будет ли этот цикл корректно работать с vector? Как я себе представляю, при erase все последующие элементы должны сдвигаться.

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

AVK>>Вариант с nit — по-моему, лучшее, что можно придумать.

А>Для list согласен. А будет ли этот цикл корректно работать с vector? Как я себе представляю, при erase все последующие элементы должны сдвигаться.

Для вектора, конечно, корректно работать не будет

Но для вектора лучше использовать вот такой цикл:

std::vector<int> vec;

for (int i = vec.size() - 1; i >= 0; --i)
{
  vec::iterator it = std::advance (vec.begin(), i);
  if (*it == 0)
     std::erase(it);
}

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

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

.
А>Good luck

Super! А оценку негде поставить...

Здравствуйте Anton V. Kolotaev, Вы писали:

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

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

AVK>Super! А оценку негде поставить... :(
Ставь. Я запомню :-)))

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

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

AVK>>>Вариант с nit — по-моему, лучшее, что можно придумать.

А>>Для list согласен. А будет ли этот цикл корректно работать с vector? Как я себе представляю, при erase все последующие элементы должны сдвигаться.

DG>Для вектора, конечно, корректно работать не будет

DG>Но для вектора лучше использовать вот такой цикл:
DG>

DG>std::vector<int> vec;

DG>for (int i = vec.size() - 1; i >= 0; --i)
DG>{
DG>  vec::iterator it = std::advance (vec.begin(), i);
DG>  if (*it == 0)
DG>     std::erase(it);
DG>}
DG>

Я бы для вектора несколько по-другому сделал: копирование в любом случае нужно, а чтобы кучу раз не перемещать массив в памяти, просто скопировать нужные элементы в новый массив например:

int newsize = v.size();
for (vector<>::iterator i = v.begin(); i < v.size(); i++)
  if (*i == 0 ) newsize-- ; //этот элемент мы не скопируем
vector<> v2; v2.reserve(newsize); //только резервируем место
for (vector<>::iterator i = v.begin(); i < v.size(); i++)
  if (*i != 0 )
    v2.push_back(*i)
v.swap(v2); //swap не выполнит копирования
//здесь v2 выйдет за область видимости и уничтожится.

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

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

.
А>>>Good luck

AVK>>Super! А оценку негде поставить...

А>Ставь. Я запомню

дык — куда тебе ставить то =) — регься.

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

АТ>Я вот хочу немножко завистливо попридираться (Так просто для иллюстрации того факта, что придраться всегда есть к чему) :))

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

Если я не ошибаюсь, префиксный operator++() отличается от постфиксного operator++(int) именно тем, что префиксный возвращает уже увеличенное значение, а постфиксный — копию текущего значения.
(Извиняюсь за корявость высказывания, но надеюсь, меня все поняли ;-)). Это справедливо и для скалярных типов. (standard, 5.2.6 , 5.3.2)
То есть я хотел сказать, что такое поведение постфиксного operator++ (int) обусловлено стандартом

:)))

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

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

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

АТ>>>Я вот хочу немножко завистливо попридираться (Так просто для иллюстрации того факта, что придраться всегда есть к чему) :))

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

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

S>> :)))

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

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

A>В том-то и дело, что для неперегруженного постинкремента копия может и не делаться (т. е., например, для int это, по всей вероятности, будет просто ассемблерная инструкция инкремента, вставленная после использования).
operator++
Цитирую: 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]
Насчет ассемблера —

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

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

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

:-)))

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

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

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

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

АТ>>>>Я вот хочу немножко завистливо попридираться (Так просто для иллюстрации того факта, что придраться всегда есть к чему)

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

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

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

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

S>>>

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>

Ну и?

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

Здравствуйте 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, Вы писали:

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'

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

АТ>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'.

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

АТ>>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, зело хорошая книжка. Желание писать не-функторный код пропадает быстро.

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

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

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

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

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

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

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

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

	От:	santucco
	Дата:	25.07.02 07:24
	Оценка:	27 (5)

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

	От:	Андрей Тарасевич
	Дата:	24.07.02 16:52
	Оценка:	3 (1) -1

	От:	Андрей Тарасевич
	Дата:	26.07.02 16:55
	Оценка:	6 (1)

	От:	Аноним
	Дата:	24.07.02 07:25
	Оценка:	3 (1)

От:	DarkGray	http://blog.metatech.ru/post/ogni-razrabotki.aspx
Дата:	23.07.02 14:37
Оценка:

	От:	Anton V. Kolotaev
	Дата:	23.07.02 14:42
	Оценка: