Re[2]: вопрос про stl, vector::erase - C/C++

Добрый день.

Мне надо в цикле перебирать значения хранящиеся в векторе. При определенном условии я должен удалить текущее знаечение из вектора и продолжить обход.

Сейчас сделал так:

...
table_iter_t it = table.begin();

for (int i=0; it != table.end(); it++, i++)
{
...
  if (cond)
  {
    table.erase(it);
    i--;
    it = table.begin()+i;
    continue;
  }
...
}

Легальный ли это код или лучше сделать c remove+erase?

Заранее спасибо за ответы.

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

BB>Добрый день.

BB>Мне надо в цикле перебирать значения хранящиеся в векторе. При определенном условии я должен удалить текущее знаечение из вектора и продолжить обход.

Для этого есть remove_if. Поищи по форуму...

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

BB>Легальный ли это код ...
При срабатывании условия при i == 0 получаем невалидный итератор.

BB>...или лучше сделать c remove+erase?
Конечно.

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

BB>Добрый день.

BB>Мне надо в цикле перебирать значения хранящиеся в векторе. При определенном условии я должен удалить текущее знаечение из вектора и продолжить обход.

BB>Сейчас сделал так:

Может тогда сделать напрямую, без it

for (int i=0; i != table.size();)
{
 ...
 if (cond)
  table.erase(table.begin()+i);
 else
  ++i; 
 ...
}

Насчет remove-erase, наверное лучше.

Еще можно удалять элементы начиная с хвоста

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

BB>Добрый день.

BB>Мне надо в цикле перебирать значения хранящиеся в векторе. При определенном условии я должен удалить текущее знаечение из вектора и продолжить обход.

BB>Сейчас сделал так:

BB>

BB>...
BB>table_iter_t it = table.begin();

BB>for (int i=0; it != table.end(); it++, i++)
BB>{
BB>...
BB>  if (cond)
BB>  {
BB>    table.erase(it);
BB>    i--;
BB>    it = table.begin()+i;
BB>    continue;
BB>  }
BB>...
BB>}
BB>

BB>Легальный ли это код или лучше сделать c remove+erase?

Не совсем если удалишь нулевой элемент потом i-- ...

BB>Заранее спасибо за ответы.

Должно работать:

table_iter_t it = table.begin();
while(it!=table.end){
  ...
  if (cond)
  {
        table.erase(it);
        //Значение итератора остается старым, но указывает на следующий элемент вектора
        continue;
    }
    ++it;
    ...

}

... << RSDN@Home 1.1.4 beta 3 rev. 241>>

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

BCM>Должно работать:
BCM>

BCM>table_iter_t it = table.begin();
BCM>while(it!=table.end){
BCM>  ...
BCM>  if (cond)
BCM>  {
BCM>        table.erase(it);
BCM>        //Значение итератора остается старым, но указывает на следующий элемент вектора
BCM>        continue;
BCM>    }
BCM>    ++it;
BCM>    ...
BCM>}
BCM>

Нет, не должно. После вызова erase итератор становится невалидным, и все дальнейшие операции с ним ведут к UB.
Однако в случае, когда итератор вектора — обычный указатель, то этот код будет работать, причем правильно. Но если поменяется реализация STL, и в этой реализации вектор будет иметь "полноценные" итераторы, то сюрпризы обеспечены.

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

B>Нет, не должно. После вызова erase итератор становится невалидным, и все дальнейшие операции с ним ведут к UB.
B>Однако в случае, когда итератор вектора — обычный указатель, то этот код будет работать, причем правильно. Но если поменяется реализация STL, и в этой реализации вектор будет иметь "полноценные" итераторы, то сюрпризы обеспечены.

Теоретически, да, и для полной и абсолютной совместимости так нельзя, но вряд-ли сушествует вариант stl где итератор vector реализован по иному

... << RSDN@Home 1.1.4 beta 3 rev. 241>>

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

BCM>Теоретически, да, и для полной и абсолютной совместимости так нельзя, но вряд-ли сушествует вариант stl где итератор vector реализован по иному

STLPort с включенным отладочным режимом.
DinkumSTL для VC7.

Зачем так сложно?
erase возвращает ближайший валидный итератор, следующий за удалённым значением, или .end() если в контейнере больше ничего нет.

   table_iter_t it = table.begin();
    while(it != table.end())
    {
      if (cond)
         it = table.erase(it);
      else 
         ++it;
    }

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

AG>Зачем так сложно?
AG>erase возвращает ближайший валидный итератор, следующий за удалённым значением, или .end() если в контейнере больше ничего нет.

AG>

AG>   table_iter_t it = table.begin();
AG>    while(it != table.end())
AG>    {
AG>      if (cond)
AG>         it = table.erase(it);
AG>      else 
AG>         ++it;
AG>    }
AG>

Так лучше, но еще лучше будет так:

table.erase(remove_if(table.begin(),table.end(), cond() ),table.end());

вызвывть erase в цикле — очень доргое удовольствие.

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

M>Так лучше, но еще лучше будет так:
M>

M>table.erase(remove_if(table.begin(),table.end(), cond() ),table.end()); 
M>

M>вызвывть erase в цикле — очень доргое удовольствие.

Конечно, код так выглядит более читаемо, но есть 2 неприятности, большая и маленькая

1. Не всегда удобно условие засовывать в предикат
2. С ассоциативными контейнерами remove_if врядли даст ожидаемый результат

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

AG>Конечно, код так выглядит более читаемо, но есть 2 неприятности, большая и маленькая

AG>1. Не всегда удобно условие засовывать в предикат
Тут могут помочь библиотеки типа boost::bind и boost::lambda, но, само собой, иногда явный цикл более выразителен.
AG>2. С ассоциативными контейнерами remove_if врядли даст ожидаемый результат
С ассоциативными контейнерами remove_if просто не будет компилиься.

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

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

AG>>Конечно, код так выглядит более читаемо, но есть 2 неприятности, большая и маленькая

AG>>1. Не всегда удобно условие засовывать в предикат
B>Тут могут помочь библиотеки типа boost::bind и boost::lambda, но, само собой, иногда явный цикл более выразителен.
AG>>2. С ассоциативными контейнерами remove_if врядли даст ожидаемый результат
B>С ассоциативными контейнерами remove_if просто не будет компилиься.

К сожалению, с setом отлично будет компилиться

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

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

AG>>Конечно, код так выглядит более читаемо, но есть 2 неприятности, большая и маленькая

AG>>1. Не всегда удобно условие засовывать в предикат
B>Тут могут помочь библиотеки типа boost::bind и boost::lambda, но, само собой, иногда явный цикл более выразителен.
AG>>2. С ассоциативными контейнерами remove_if врядли даст ожидаемый результат
B>С ассоциативными контейнерами remove_if просто не будет компилиься.

Если контейнер — std::set, то во всяком случае в VC 7.1 прекрасно компилируется, как ни странно. Говорят, что это момент в пресловутом стандарте, можно толковать двояко.

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

W>Если контейнер — std::set, то во всяком случае в VC 7.1 прекрасно компилируется, как ни странно. Говорят, что это момент в пресловутом стандарте, можно толковать двояко.

Действительно, по этому поводу есть C++ Standard Library Defect Report #103.

VC6, VC7 и VC7.1 с "родной" DinkumSTL легко проглатывают такое:

std::set<int> s;
s.insert(1);
s.insert(2);
...
*s.begin() = 10;

PS
Comeau да и VC + STLPort подобного безобразия не допускает...

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

AG>Зачем так сложно?
AG>erase возвращает ближайший валидный итератор, следующий за удалённым значением, или .end() если в контейнере больше ничего нет.

AG>

AG>   table_iter_t it = table.begin();
AG>    while(it != table.end())
AG>    {
AG>      if (cond)
AG>         it = table.erase(it);
AG>      else 
AG>         ++it;
AG>    }
AG>

Странно, у меня не убирает. Например

itPoint = points.begin();
while ( itPoint != points.end() )
{
    CGPoint thisPoint = (*itPoint); // все время те же значения!
    itPoint = points.erase(itPoint);
}

Похоже erase() не сдвигается сам к след валидному итератору. Хотя размер уменьшается

gok>Странно, у меня не убирает. Например

Атставить!
Был баг в собственной программе.

Все работает как запланировано!

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

B>Однако в случае, когда итератор вектора — обычный указатель, то этот код будет работать, причем правильно. Но если поменяется реализация STL, и в этой реализации вектор будет иметь "полноценные" итераторы, то сюрпризы обеспечены.

Ну дык всего то делов работать remov'ом с указателями а не итераторами, потом только resize сделать.

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

КД>Еще можно удалять элементы начиная с хвоста

Сложность квадратичная. Если удалять все нечётные например...

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

BB>Добрый день.

BB>Мне надо в цикле перебирать значения хранящиеся в векторе. При определенном условии я должен удалить текущее знаечение из вектора и продолжить обход.

BB>Сейчас сделал так:

BB>

BB>...
BB>table_iter_t it = table.begin();

BB>for (int i=0; it != table.end(); it++, i++)
BB>{
BB>...
BB>  if (cond)
BB>  {
BB>    table.erase(it);
BB>    i--;
BB>    it = table.begin()+i;
BB>    continue;
BB>  }
BB>...
BB>}
BB>

BB>Легальный ли это код или лучше сделать c remove+erase?

BB>Заранее спасибо за ответы.

Вариант c remove_if — erase выглядит примерно так. cond — у тебя предикат

table.erase( std::remove_if( table.begin(), table.end(), cond ), table.end() );

От:	BlackBox	---
Дата:	17.01.05 09:14
Оценка:

	От:	DangerDen
	Дата:	17.01.05 09:20
	Оценка:

	От:	Bell
	Дата:	17.01.05 09:22
	Оценка:	2 (1) +2

От:	Коваленко Дмитрий	http://www.ibprovider.com
Дата:	17.01.05 09:24
Оценка:

	От:	BacCM
	Дата:	17.01.05 09:30
	Оценка:

	От:	A.Grom
	Дата:	18.01.05 12:59
	Оценка:

	От:	A.Grom
	Дата:	18.01.05 13:30
	Оценка:

	От:	Warturtle
	Дата:	18.01.05 13:30
	Оценка:

	От:	gok
	Дата:	02.06.05 00:00
	Оценка: