std::list usuwanie elementów nie spełniających warunku

Tym razem, piszę o problemie który już rozwiązałem, ale pomyślałem że może komuś się przyda (sam na sieci nic nie znalazłem)

Miałem do dyspozycji listę charów (jakiś string na którym musiałem usuwać dużo elementów):

usuwanie elementów iterując do przodu:

std::list<char> s;
// tutaj dodanie jakis elementow do s
for (std::list<char>::iterator i=s.begin(); i!=s.end(); ++i)
{
  powrot: // mozliwe ze da sie to zrobic jakos bez goto, ale aktualnie nie mam pomyslu jak
  if (*i=='a' || *i=='g') // jakis przykladowy warunek
  {
    i=s.erase(i);
    if (i!=s.end())
      goto pocz;
    else
      break;
  }
}

problem jaki pojawial sie przy probie normalnej iteracji byl taki, ze po usunieciu elementu pomijany byl jeden element.

usuwanie iterując do tyłu (tutaj część kodu znalazlem na necie):

std::list<char> s;
// tutaj dodanie jakis elementow do s
for (std::list<char>::reverse_iterator i=s.rbegin(); i!=s.rend(); ++i)
{
  powrot: // mozliwe ze da sie to zrobic jakos bez goto, ale aktualnie nie mam pomyslu jak
  if (*i=='a' || *i=='g') // jakis przykladowy warunek
  {
    i=std::list<char>::reverse_iterator(s.erase((++i).base())); --i;
  }
}

w kodzie mógł wkraść się jakiś błąd ponieważ przerabiałem swój rzeczywisty kod i różnie to bywa.

Bo przy usunięciu elementów iteratory tracą ważność. Użyj algorithm:

bool test(char c) { return c=='a' || c == 'g'; }

std::remove_if(s.begin(), s.end(), test);

winerfresh napisał(a)

bool test(char c) { return c=='a' || c == 'g'; }

std::remove_if(s.begin(), s.end(), test);

najnowsze kompilatory dopuszczają konstrukcję bez odrębnej funkcji:

remove_if(s.begin(),s.end(),[](char c){return c=='a' || c == 'g';});

winerfresh napisał(a)

Bo przy usunięciu elementów iteratory tracą ważność.

Na pewno to ten przypadek?

krwq napisał(a)

(...) ze po usunieciu elementu pomijany byl jeden element.

Był pomijany, bo erase zwraca iterator na następny element, a u Ciebie mimo to iterator był przewijany do przodu:

for (std::list<char>::iterator i = s.begin(); i != s.end();)
{
	if (*i == 'a' || *i == 'g') i = s.erase(i);
	else ++i;
}

u mnie ważne było żeby usuwać te elementy od przodu/tyłu (kilka iteracji), ponieważ musiałem zakończyć usuwanie w odpowiednim momencie (gdy długość listy była mniejsza od zadanej), dlatego bardziej jestem skłonny do użycia konstrukcji 0x666. konkretnie robiłem to zadanie: https://pl.spoj.pl/problems/WI_IDEN/
podejrzewam, że było można to zrobić szybciej, ale lubie sobie czasem z stla skorzystać dla wprawy :)

W sumie do tego zadania bardziej string się nadaje niż lista.

niby tak, ale jak sobie pomyślałem o usuwaniu pojedynczych znaków ze stringa, to stwierdziłem, że nie będzie to zbyt szybkie.

najszybciej będzie mieć dwa stringi - źródłowy i docelowy. nie ma potrzeby robić tego „w miejscu”.

winerfresh napisał(a)

A wie ktoś czy w GCC 4.5.0 to działa domyślnie czy przy trybie zgodności z C++0x

Działa domyślnie, ale z warningiem:

test.cpp: In function 'int main()':
test.cpp:5:7: warning: lambda expressions only available with -std=c++0x or -std
=gnu++0x

Wbrew temu co pisze, kod się kompiluje.

gcc version 4.5.0 (GCC)

pozwolę sobie powrócić do pierwszego postu. pytasz, czy da się bez goto~,
otóż tak: da się.
pamiętaj, że std::erase usuwa element i zwraca iterator ktory usunęło, ten iterator nadal ma poprawny adres elementu następującego po sobie, więc możemy ustawić iterator używany w pęli na adres następujący po usuniętym elemencie.

std::erase ustawia adres poprzedniego elementu w elemencie następującym ten, który usunęliśmy na adres elementu poprzedzającego ten, który usunęliśmy z listy. i vice-versa z drugiej strony, ale nie zmienia adresów w usuwanym iteratorze ;p
do meritum:

#include <list>
#include <iostream>
#include <iterator>//std::ostream_iterator
char a[]={'a','b','c','d','e','g','a','a','h','a'};
int main(int,char**)
{
std::list<char> s(a,a+10);
// tutaj dodanie jakis elementow do s

copy(s.begin(), s.end(),  std::ostream_iterator<char>(std::cout, " "));
std::cout<<"\n";

for (std::list<char>::iterator i=s.begin(); i!=s.end(); ++i)
{
  powrot: // mozliwe ze da sie to zrobic jakos bez goto, ale aktualnie nie mam pomyslu jak
  if (*i=='a' || *i=='g') // jakis przykladowy warunek
  {
    i=s.erase(i); //tutaj bylo ++s.erase(i), ale doszedlem do wniosku, ze sluszmnie mnie krwq zjechal xd 
    /*
    if (i!=s.end())
      goto powrot;
    else
      break;
	*/
  }
}

copy(s.begin(), s.end(), std::ostream_iterator<char>(std::cout, " "));
std::cout<<std::endl;
	return 0;
}

@down, w takim radzie trudno, jak wytlumaczysz to, ze moj kod dziala?

test30 napisał(a)

otóż tak: da się.
pamiętaj, że std::erase usuwa element i zwraca iterator ktory usunęło

nie zwraca iteratora który usunęło tylko następny iterator znajdujący się na liście.
http://www.cplusplus.com/reference/stl/list/erase/
"Return value
A bidirectional iterator pointing to the new location of the element that followed the last element erased by the function call, which is the list end if the operation erased the last element in the sequence."

gdyby zwracał ten sam iterator to:

1. nie bylo by problemu, po prostu uzylbym zwykle list->erase(i); i nie kombinowalbym dalej (i byloby nadal aktualne)
2. operacja przypisania kolejnego elementu spowodowalaby ze ominalbym kolejny element
3. zwiekszenie o jeden tymczasowej zmiennej zwroconej przez erase nie ma sensu

Ale kombinujecie...

bool predicate(char ch) { return ch == 'a' || ch == 'g'; }

s.remove_if(predicate);