librerias - vector stl c++ ejemplos

Borrar elementos de una lista STL

Question

Quiero hacer una función que mueva elementos de una lista STL a otra si coinciden con una determinada condición.

Este código no es la manera de hacerlo. Lo más probable es que el iterador sea invalidado por la función borrar () y cause un problema:

for(std::list<MyClass>::iterator it = myList.begin(); it != myList.end(); it++)
{
  if(myCondition(*it))
  {
    myOtherList.push_back(*it);
    myList.erase(it);
  }
}

Entonces, ¿alguien puede sugerir una mejor manera de hacer esto?

Answer 1

Solución 1

template<typename Fwd, typename Out, typename Operation>
Fwd move_if(Fwd first, Fwd last, Out result, Operation op)
{
    Fwd swap_pos = first;
    for( ; first != last; ++first ) {
        if( !op(*first) ) *swap_pos++ = *first;
        else *result++ = *first;
    }
    return swap_pos;
}

La idea es simple Lo que quiere hacer es eliminar elementos de un contenedor y colocarlos en otro si un predicado es verdadero. Así que tome el código del algoritmo std::remove() , que ya elimina la parte, y adáptela a sus necesidades adicionales. En el código anterior, agregué la línea else para copiar el elemento cuando el predicado es verdadero.

Tenga en cuenta que debido a que usamos el código std::remove() , el algoritmo en realidad no reduce el contenedor de entrada. Sin embargo, devuelve el iterador final actualizado del contenedor de entrada, por lo que puede usarlo e ignorar los elementos adicionales. Use la expresión borrar-borrar si realmente desea reducir el tamaño del contenedor de entrada.

Solución 2

template<typename Bidi, typename Out, typename Operation>
Bidi move_if(Bidi first, Bidi last, Out result, Operation op)
{
    Bidi new_end = partition(first, last, not1(op));
    copy(new_end, last, result);
    return new_end;
}

El segundo enfoque usa el STL para implementar el algoritmo. Personalmente, me resulta más legible que la primera solución, pero tiene dos inconvenientes: en primer lugar, requiere los iteradores bidireccionales más potentes para el contenedor de entrada, en lugar de los iteradores directos que utilizamos en la primera solución. En segundo lugar, y esto puede ser o no un problema para usted, no se garantiza que los contenedores tengan el mismo orden que antes de la llamada a std::partition() . Si desea mantener el orden, reemplace esa llamada con una llamada a std::stable_partition() . std::stable_partition() puede ser un poco más lenta, pero tiene la misma complejidad de tiempo de ejecución que std::partition() .

De cualquier manera: Llamar a la función

list<int>::iterator p = move_if(l1.begin(), l1.end(),
                                back_inserter(l2),
                                bind2nd(less<int>(), 3));

Observaciones finales

Mientras escribía el código, me encontré con un dilema: ¿qué debería devolver el algoritmo move_if() ? Por un lado, el algoritmo debería devolver un iterador que apunta a la nueva posición final del contenedor de entrada, de modo que quien llama puede usar el idioma borrar-eliminar para reducir el contenedor. Pero, por otro lado, el algoritmo debería devolver la posición del final del contenedor de resultados, porque de lo contrario podría ser costoso para la persona que llama encontrarlo. En la primera solución, el iterador de result apunta a esta posición cuando el algoritmo termina, mientras que en la segunda solución es el iterador devuelto por std::copy() que apunta a esta posición. Podría devolver un par de iteradores, pero, para simplificar, simplemente devuelvo uno de los iteradores.

Answer 2

Otro intento:

for(std::list<MyClass>::iterator it = myList.begin(); it != myList.end; ) {
    std::list<MyClass>::iterator eraseiter = it;
    ++it;
    if(myCondition(*eraseiter)) {
        myOtherList.push_back(*eraseiter);
        myList.erase(eraseiter);
    }
}

Answer 3

template <typename ForwardIterator, typename OutputIterator, typename Predicate>
void splice_if(ForwardIterator begin, ForwardIterator end, OutputIterator out, Predicate pred)
{
    ForwardIterator it = begin;
    while( it != end )
    {
        if( pred(*it) )
        {
            *begin++ = *out++ = *it;
        }
        ++it;
    }
    return begin;
}

myList.erase( 
    splice_if( myList.begin(), myList.end(), back_inserter(myOutputList),
        myCondition
    ),
    myList.end()
)

Answer 4

Las listas STL tienen una característica interesante: el método splice() permite mover elementos de una lista a otra de forma destructiva.

splice() funciona en tiempo constante, y no copia los elementos ni realiza asignaciones / desasignaciones de tiendas libres. Tenga en cuenta que ambas listas deben ser del mismo tipo, y deben ser instancias de listas separadas (no dos referencias a la misma lista).

Aquí hay un ejemplo de cómo puedes usar splice() :

for(std::list<MyClass>::iterator it = myList.begin(); it != myList.end(); ) {
    if(myCondition(*it)) {
        std::list<MyClass>::iterator oldIt = it++;
        myOtherList.splice(myOtherList.end(), myList, oldIt);
    } else {
        ++it;
    }
}

Answer 5

Erase devuelve un iterador que apunta al elemento después del borrado:

std::list<MyClass>::iterator it = myList.begin();
while (it != myList.end())
{
  if(myCondition(*it))
  {
    myOtherList.push_back(*it);
    it = myList.erase(it);
  }
  else
  {
    ++it;
  }
}

Answer 6

std::list<MyClass>::iterator endMatching =
    partition(myList.begin(), myList.end(), myCondition);
myOtherList.splice(myOtherList.begin(), myList, endMatching, myList.end());

Tenga en cuenta que partition () le proporciona lo suficiente para discriminar los objetos coincidentes de los que no coinciden. (list :: splice () es barato, sin embargo)

Consulte el siguiente código en un caso concreto inspirado en Ahora para eliminar elementos que coincidan con un predicado.

#include <iostream>
#include <iterator>
#include <list>
#include <string>
#include <algorithm>
#include <functional>

using namespace std;

class CPred : public unary_function<string, bool>
{
public:
        CPred(const string& arString)
                :mString(arString)
        {
        }

        bool operator()(const string& arString) const
        {
                return (arString.find(mString) == std::string::npos);
        }
private:
        string mString;
};

int main()
{
        list<string> Strings;

        Strings.push_back("213");
        Strings.push_back("145");
        Strings.push_back("ABC");
        Strings.push_back("167");
        Strings.push_back("DEF");

        cout << "Original list" << endl;
        copy(Strings.begin(), Strings.end(),ostream_iterator<string>(cout,"/n"));

        CPred Pred("1");

        // Linear. Exactly last - first applications of pred, and at most (last - first)/2 swaps. 
        list<string>::iterator end1 =
        partition(Strings.begin(), Strings.end(), Pred);

        list<string> NotMatching;

        // This function is constant time. 
        NotMatching.splice(NotMatching.begin(),Strings, Strings.begin(), end1); 

        cout << "Elements matching with 1" << endl;
        copy(Strings.begin(), Strings.end(), ostream_iterator<string>(cout,"/n"));

        cout << "Elements not matching with 1" << endl;
        copy(NotMatching.begin(), NotMatching.end(), ostream_iterator<string>(cout,"/n"));

        return 0;
}