c++ - libreria - ¿La forma más eficiente de borrar/eliminar múltiples elementos std:: vector manteniendo el orden original?

sort algorithm c++

Question

Tengo un std::vector<int> y un segundo contenedor que contiene iteradores o índices (sin claves, quiero un acceso constante al elemento) a este vector para fines de eliminación. Supongamos que tengo un vector de 1000 elementos y quiero borrar 200 de ellos. El orden de los elementos no eliminados debe ser el mismo después de las operaciones de eliminación como antes.

Una cosa más que me perdí en la primera versión de mi pregunta: los valores son únicos . Son identidades.

¿Cómo lo haría de manera segura (en relación con las normas de STL) y de manera eficiente (la decisión de un vector será definitiva)?

Posibilidades o métodos que pensé:

• el idioma de borrado-eliminar (http://en.wikipedia.org/wiki/Erase-remove_idiom): originalmente para la eliminación de elementos que cumplen una condición (incluida la búsqueda lineal) pero creo que con rangos de tamaño 1 este método podría ser Solía ​​hacerlo con iteradores ya dados y una condición ficticia. Pregunta: ¿se conserva el orden original de los elementos y es más eficaz que el último método?
• recorra los índices y borre los elementos con el uso de vector.erase(vector.begin()+index+offset) mientras mantiene los índices eliminados en un contenedor para calcular el offset. Este desplazamiento podría determinarse para cada iteración de eliminación con el uso de un std::lower_bound n el contenedor de elementos ya eliminados. El problema: muchas búsquedas binarias para obtener el desplazamiento y muchas operaciones de movimiento debido a la eliminación de ubicación aleatoria.
• En este momento estoy haciendo lo siguiente: obtener todos los iteradores para que se eliminen los elementos. Clasifíquelos en orden descendente según la ubicación en el vector y vector.erase para la eliminación final con vector.erase . Ahora no estoy invalidando ningún iterador y no hay operaciones de reorganización vectorial excepto la eliminación en sí misma. El problema: mucha ordenación.

Entonces, ¿cómo abordaría esto? ¿Alguna idea nueva? ¿Alguna recomendación?

Gracias por tu contribución.

Sascha

Resultados de edición / actualización / propios: implementé el lenguaje de borrado-eliminar , que también fue mencionado por KennyTM, con un predicado basado en la búsqueda en un boost :: dynamic_bitset y es increíblemente rápido . Además, probé el método de movimiento y truncado de PigBen (también mencionado por Steve Jessop) que también está accediendo al conjunto de bits en su bucle while. Ambos parecen ser igualmente rápidos con mi tipo de datos. Intenté eliminar 100 de 1000 elementos (entradas sin firmar), hice 100 eliminaciones 1M veces y no hubo una diferencia significativa. Porque creo que el lenguaje de eliminación-eliminación basado en STL es un poco más "natural, estoy eligiendo este método (el argumento también fue mencionado por KennyTM).

Answer 1

¿Elementos de qué? Tal vez me estoy tomando en serio tu publicación, pero si tienes un vector de 1000 elementos, ¿por qué no marcar los que ya no son válidos y eliminar el borrado en primer lugar? Obviamente, estoy suponiendo que tus elementos no exigen mucha memoria.

Solo menciono esto porque parece que te preocupa la velocidad. ¡Si las sugerencias ya dadas no hacen el truco, tal vez esta idea vale la pena un pensamiento! En esencia, acelerar las cosas al no hacer la operación en primer lugar.

Answer 2

¿Qué hay de hacer un bucle a través del vector, y para cada elemento que necesita ser eliminado, copie el siguiente elemento que no necesita ser eliminado en esa posición. Luego, cuando llegues al final, trunca.

int last = 0;
for(int i=0; i<vec.size(); ++i, ++last)
{
   while(needs_to_be_removed(i))
      ++i;
   if(i >= vec.size()) break;

   vec[last] = vec[i];   
}

vec.resize(last);

Answer 3

En <algorithm> hay una función remove_if que comprime todos los valores no eliminados al frente manteniendo el orden. Esto funciona si esos 200 elementos pueden ser determinados puramente por los valores, no por el índice.

Este es esencialmente el lenguaje Erase-remove al que te has vinculado. se garantiza que remove_if realice comparaciones O (N) (y, como máximo, copias de O (N)), lo que sería más eficiente que la clasificación (O (N log N)), aunque su última opción no requiere realmente la clasificación si los índices se determinan a partir de los valores (solo escanee en la dirección invertida mientras se copia).

Sin embargo, usar remove_if (si puede) es mejor que las otras 2 opciones porque la implementación ya se ha escrito para usted, por lo que hay menos posibilidades de error lógico y transmite mejor qué hacer (no cómo ).

Answer 4

He escrito una función, basada en la respuesta de Benjamin Lindley https://.com/a/4115582/2835054 .

#include <iostream>
#include <algorithm>
#include <vector>

template <typename elementType, typename indexType>
void remove_multiple_elements_from_vector(std::vector<elementType> &vector,
std::vector<indexType> &indexes)
{
    // 1. indexType is any integer.
    // 2. elementType is any type.
    // 3. Indexes should be unique.
    // 4. The largest index inside indexes shouldn''t be larger than
    //    the largetst index in the vector.
    // 5. Indexes should be sorted in ascending order
    //    (it is done inside function).
    std::sort(indexes.begin(), indexes.end());
    indexType currentIndexInIndexesVector = 0;
    indexType last = 0;
    for(indexType i=0; i<vector.size(); ++i, ++last)
    {
       while(indexes[currentIndexInIndexesVector] == i)
       {
          ++i;
          ++currentIndexInIndexesVector;
       }
       if(i >= vector.size()) break;

       vector[last] = vector[i];   
    }

    vector.resize(last);
}


int main()
{
    std::vector<int> vector = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::vector<int> indexes = {0, 10, 5};

    for (auto &vectorElement : vector)
    {
        std::cout << vectorElement << " ";
    }    
    std::cout << "/n";

    remove_multiple_elements_from_vector<int, int>(vector, indexes);

    for (auto &vectorElement : vector)
    {
        std::cout << vectorElement << " ";
    }
}

Answer 5

Lo primero es no llamar a erase más veces de las necesarias, ya que para un vector baraja todos los elementos posteriores, lo que da a toda la operación un tiempo de ejecución en el peor de los casos Ω (n * m) (n el tamaño del vector , m el tamaño de la lista de índices a eliminar).

Creo que lo primero que intentaría sería similar a tu código actual:

• ordenar los índices
• crear un nuevo vector de tamaño n - m
• itere sobre el vector original, copiando elementos indexes[0] , omitiendo un elemento, luego copiando indexes[1] - indexes[0] - 1 elementos, omitiendo un elemento, y así sucesivamente.
• swap el vector original por el nuevo.

Es posible que pueda realizar el tercer paso con remove_copy_if y un predicado que contiene el estado (contando cuántos elementos ha copiado y qué tan lejos está a través de la lista ordenada de índices), pero por razones extremadamente tediosas y oscuras no está garantizado. Para trabajar (los predicados de algoritmo con estado mutable son problemáticos, parece ser el consenso de que el estándar no garantiza que se use la misma copia del predicado en todo el algoritmo). Así que realmente no aconsejo intentarlo, pero podría ayudar tener en cuenta que lo que estás escribiendo básicamente es una versión modificada de remove_copy_if .

Podría evitar el segundo paso utilizando un back_inserter lugar de prescribir el vector, aunque probablemente todavía reservará el espacio por adelantado.

[Editar: ahora que lo pienso, ¿por qué estoy copiando algo? En lugar de implementar un remove_copy_if modificado, implemente un remove_if modificado, y simplemente cópielo a un punto anterior en el vector. Luego erase / resize al final. No me preocuparía el tipo de índice O(m log m) hasta que se demuestre que es un problema, ya que es poco probable que sea significativamente más lento que la operación Ω (m) para leer todos los valores que se eliminarán y almacenarlos en algún tipo de contenedor. Luego, usar este contenedor en el predicado para remove_if puede o no ser O(1) . La clasificación podría resultar más rápida para valores plausibles de m .]

Answer 6

Puede copiar todos los elementos del vector a una lista a menos que el índice en su segundo contenedor, y luego volver a un vector. Incluso con su algoritmo de pasar del final del vector al frente, hay mucho trabajo detrás de la escena en su vector.

Haga de su segundo contenedor un mapa para que mantenga los índices ordenados automáticamente.

editar:

Para responder al comentario.

El costo de mantener un mapa es, en el peor de los casos, lo mismo que mantener otra estructura (lista o vector) y luego clasificarla. Si ya lo estás haciendo, podrías mantenerlo como un mapa. No tiene sentido quejarse de la sobrecarga de un mapa frente a la sobrecarga de ordenar una lista.

En cuanto al rendimiento de mi algoritmo sugerido, si m es el número de elementos que se eliminarán, y n es el número total de elementos, entonces se obtiene O (n - m).

Por supuesto, esto es sobre todo solo para humillar su intento de optimizar con un vector.

1 - No debería utilizar un vector si desea realizar eliminaciones de acceso aleatorio. Eso no es para lo que son buenos, use una lista si es posible. Y como parece que usted está mucho más interesado en el orden relativo que en el índice absoluto, me pregunto por qué se necesita un vector. Si dio todo el problema, probablemente haya una solución común que le permita usar la estructura de datos más eficiente para resolverlo.

2 - En lugar de mantener una segunda estructura de datos, marque los elementos que deben eliminarse directamente en su contenedor. Una forma trivial es, en cambio, usar un contenedor <T> usar un contenedor <std :: pair <T, char>> y usar el carácter para realizar un seguimiento del estado del elemento.

Si hace 1 y 2, elimina todas las copias por completo y obtiene una implementación mucho más eficiente.

Answer 7

Si tiene un conjunto de índices (por ejemplo, no ordenados) que desea borrar, puede usar esto:

template <typename Type>
void erase_indices(
        const std::unordered_set<size_t>& indices_to_erase,
        std::vector<Type>& vec) {
    std::vector<bool> erase_index(vec.size(), false);
    for (const size_t i: indices_to_erase) {
        erase_index[i] = true;
    }
    std::vector<bool>::const_iterator it_to_erase = erase_index.cbegin();
    typename std::vector<Type>::iterator it_erase_from = std::remove_if(
        vec.begin(), vec.end(),
        [&it_to_erase](const Type&) -> bool {
          return *it_to_erase++ == true;
        }
    );
    vec.erase(it_erase_from, vec.end());
}

Es la solución más rápida que se me ha ocurrido. Sin embargo, necesitas C ++ 11 . Ejemplo de uso para borrar elementos en el índice 2 y 5:

constexpr size_t num = 10u;
std::vector<int> vec(num);
std::iota(vec.begin(), vec.end(), 0);

std::unordered_set<size_t> indices_to_erase;
indices_to_erase.insert(2u);
indices_to_erase.insert(5u);

erase_indices(indices_to_erase, vec);

Antes de:

0 1 2 3 4 5 6 7 8 9

Después:

0 1 3 4 6 7 8 9

Edición: si desea ser más flexible con respecto al tipo de contenedor que contiene los índices para borrar:

template <typename Type, typename Container>
void erase_indices(
        const Container& indices_to_erase,
        std::vector<Type>& vec) {
    typedef typename Container::value_type IndexType;
    static_assert(std::is_same<IndexType, std::size_t>::value,
        "Indices to be erased have to be of type std::size_t");
    std::vector<bool> erase_index(vec.size(), false);
    for (const IndexType idx_erase: indices_to_erase) {
        erase_index[idx_erase] = true;
    }
    std::vector<bool>::const_iterator it_to_erase = erase_index.cbegin();
    typename std::vector<Type>::iterator it_erase_from = std::remove_if(
        vec.begin(), vec.end(),
        [&it_to_erase](const Type&) -> bool {
          return *it_to_erase++ == true;
        }
    );
    vec.erase(it_erase_from, vec.end());
}

Ahora puede usar cualquier tipo de contenedor de la Biblioteca de Contenedores para proporcionar los índices que se borrarán siempre que el value_type de ese contenedor sea std::size_t . El uso sigue siendo el mismo.