c++ - repetidos - Cómo eliminar elementos de un std:: vector dada una lista de índices

encontrar la posicion de un numero en un arreglo

Question

Tengo un vector de elementos, y un vector de índices que se deben eliminar de los items :

std::vector<T> items;
std::vector<size_t> indicesToDelete;

items.push_back(a);
items.push_back(b);
items.push_back(c);
items.push_back(d);
items.push_back(e);

indicesToDelete.push_back(3);
indicesToDelete.push_back(0);
indicesToDelete.push_back(1);

// given these 2 data structures, I want to remove items so it contains
// only c and e (deleting indices 3, 0, and 1)
// ???

¿Cuál es la mejor manera de realizar la eliminación, sabiendo que con cada eliminación, afecta a todos los demás índices en indicesToDelete ?

Un par de ideas serían:

1. Copie items a un nuevo vector, un elemento a la vez, omitiendo si el índice está en indicesToDelete
2. Iterar items y para cada eliminación, disminuir todos los elementos en indicesToDelete que tienen un índice mayor.
3. Ordene indicesToDelete primero, luego iterar indicesToDelete y, para cada eliminación, incremente una indexCorrection que se resta de los índices subsiguientes.

Todos parecen estar pensando demasiado en una tarea aparentemente trivial. ¿Alguna idea mejor?

Editar Aquí está la solución, básicamente una variación de # 1 pero usando iteradores para definir bloques para copiar al resultado.

template<typename T>
inline std::vector<T> erase_indices(const std::vector<T>& data, std::vector<size_t>& indicesToDelete/* can''t assume copy elision, don''t pass-by-value */)
{
    if(indicesToDelete.empty())
        return data;

    std::vector<T> ret;
    ret.reserve(data.size() - indicesToDelete.size());

    std::sort(indicesToDelete.begin(), indicesToDelete.end());

    // new we can assume there is at least 1 element to delete. copy blocks at a time.
    std::vector<T>::const_iterator itBlockBegin = data.begin();
    for(std::vector<size_t>::const_iterator it = indicesToDelete.begin(); it != indicesToDelete.end(); ++ it)
    {
        std::vector<T>::const_iterator itBlockEnd = data.begin() + *it;
        if(itBlockBegin != itBlockEnd)
        {
            std::copy(itBlockBegin, itBlockEnd, std::back_inserter(ret));
        }
        itBlockBegin = itBlockEnd + 1;
    }

    // copy last block.
    if(itBlockBegin != data.end())
    {
        std::copy(itBlockBegin, data.end(), std::back_inserter(ret));
    }

    return ret;
}

Answer 1

Aquí está mi solución para este problema que mantiene el orden de los "artículos" originales:

1. cree una "máscara vectorial" e inicialice (rellene) con valores "falsos".
2. cambie los valores de máscara a "verdadero" para todos los índices que desee eliminar.
3. recorra todos los miembros de "enmascarar" y borre de ambos vectores "elementos" y "enmascare" los elementos con valores "verdaderos".

Aquí está el ejemplo del código:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<unsigned int> items(12);
    vector<unsigned int> indicesToDelete(3);
    indicesToDelete[0] = 3;
    indicesToDelete[1] = 0;
    indicesToDelete[2] = 1;
    for(int i=0; i<12; i++) items[i] = i;

    for(int i=0; i<items.size(); i++)
      cout << "items[" << i << "] = " << items[i] << endl;

    // removing indeces
    vector<bool> mask(items.size());
    vector<bool>::iterator mask_it;
    vector<unsigned int>::iterator items_it;
    for(size_t i = 0; i < mask.size(); i++)
      mask[i] = false;
    for(size_t i = 0; i < indicesToDelete.size(); i++)
      mask[indicesToDelete[i]] = true;        

    mask_it = mask.begin();
    items_it = items.begin();
    while(mask_it != mask.end()){
      if(*mask_it){
        items_it = items.erase(items_it);
        mask_it = mask.erase(mask_it);
      }
      else{
        mask_it++;
        items_it++;
      }
    }

    for(int i=0; i<items.size(); i++)
      cout << "items[" << i << "] = " << items[i] << endl;

    return 0;
}

Esta no es una implementación rápida para usar con grandes conjuntos de datos. El método "erase ()" toma tiempo para reorganizar el vector después de eliminar el elemento.

Answer 2

Básicamente, la clave del problema es recordar que si elimina el objeto en el índice i y no usa un marcador de posición de lápida, el vector debe hacer una copia de todos los objetos después de i . Esto se aplica a todas las posibilidades que sugirió, excepto para el #1 . Copiar a una nueva lista hace una copia sin importar cuántos borre, por lo que es la respuesta más rápida.
Y como dijo David Rodríguez, la clasificación de la lista de índices a eliminar permite algunas optimizaciones menores, pero solo vale la pena si está eliminando más de 10-20 (por favor haga el perfil primero).

Answer 3

Dado que la discusión se ha transformado de alguna manera en una pregunta relacionada con el rendimiento, escribí el siguiente código. Utiliza remove_if y vector::erase , que deberían mover los elementos un número mínimo de veces. Hay un poco de sobrecarga, pero para casos grandes, esto debería ser bueno.

Sin embargo, si no te importa el orden relativo de los elementos, entonces esto no será tan rápido.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <set>

using std::vector;
using std::string;
using std::remove_if;
using std::cout;
using std::endl;
using std::set;

struct predicate {
    public:
        predicate(const vector<string>::iterator & begin, const vector<size_t> & indices) {
            m_begin = begin;
            m_indices.insert(indices.begin(), indices.end());
        }

        bool operator()(string & value) {
            const int index = distance(&m_begin[0], &value);
            set<size_t>::iterator target = m_indices.find(index);
            return target != m_indices.end();
        }

    private:
        vector<string>::iterator m_begin;
        set<size_t> m_indices;
};

int main() {
    vector<string> items;
    items.push_back("zeroth");
    items.push_back("first");
    items.push_back("second");
    items.push_back("third");
    items.push_back("fourth");
    items.push_back("fifth");

    vector<size_t> indicesToDelete;
    indicesToDelete.push_back(3);
    indicesToDelete.push_back(0);
    indicesToDelete.push_back(1);

    vector<string>::iterator pos = remove_if(items.begin(), items.end(), predicate(items.begin(), indicesToDelete));
    items.erase(pos, items.end());

    for (int i=0; i< items.size(); ++i)
        cout << items[i] << endl;
}

La salida para esto sería:

second
fourth
fifth

Hay una pequeña sobrecarga de rendimiento que aún se puede reducir. En remove_if (al menos en gcc), el predicado se copia por valor para cada elemento del vector. Esto significa que posiblemente estamos haciendo el constructor de copia en el conjunto m_indices cada vez. Si el compilador no puede deshacerse de esto, entonces recomendaría pasar los índices como un conjunto y almacenarlo como una referencia constante.

Podríamos hacer eso de la siguiente manera:

struct predicate {
    public:
        predicate(const vector<string>::iterator & begin, const set<size_t> & indices) : m_begin(begin), m_indices(indices) {
        }

        bool operator()(string & value) {
            const int index = distance(&m_begin[0], &value);
            set<size_t>::iterator target = m_indices.find(index);
            return target != m_indices.end();
        }

    private:
        const vector<string>::iterator & m_begin;
        const set<size_t> & m_indices;
};

int main() {
    vector<string> items;
    items.push_back("zeroth");
    items.push_back("first");
    items.push_back("second");
    items.push_back("third");
    items.push_back("fourth");
    items.push_back("fifth");

    set<size_t> indicesToDelete;
    indicesToDelete.insert(3);
    indicesToDelete.insert(0);
    indicesToDelete.insert(1);

    vector<string>::iterator pos = remove_if(items.begin(), items.end(), predicate(items.begin(), indicesToDelete));
    items.erase(pos, items.end());

    for (int i=0; i< items.size(); ++i)
        cout << items[i] << endl;
}

Answer 4

Depende de los números que estés borrando.

Si está eliminando muchos elementos, puede tener sentido copiar los elementos que no se eliminan en un nuevo vector y luego reemplazar el vector antiguo con el nuevo vector (después de ordenar indicesToDelete ). De esa manera, evitará comprimir el vector después de cada eliminación, que es una operación O (n), posiblemente realizando todo el proceso O (n ^ 2).

Si está eliminando algunos elementos, tal vez haga la eliminación en orden de índice inverso (suponiendo que los índices estén ordenados), entonces no necesita ajustarlos a medida que se eliminan los elementos.

Answer 5

Incluso podría ser la opción 4:

Si está eliminando algunos elementos de un gran número, y sabe que nunca habrá una alta densidad de elementos eliminados:

Reemplace cada uno de los elementos en los índices que deben eliminarse con valores de "lápida", lo que indica que no hay nada válido en esos índices, y asegúrese de que cada vez que acceda a un artículo, verifique una piedra sepulcral.

Answer 6

Me gustaría 1/3, es decir: ordenar el vector de índices, crear dos iteradores en el vector de datos, uno para leer y otro para escribir. Inicialice el iterador de escritura en el primer elemento que se eliminará, y el iterador de lectura en uno más allá de aquel. Luego, en cada paso del bucle, incremente los iteradores al siguiente valor (escritura) y al siguiente valor que no se omitirá (lectura) y copie / mueva los elementos. Al final del bucle, erase llamada para descartar los elementos más allá del último escrito en la posición.

Por cierto, este es el enfoque implementado en los algoritmos remove / remove_if de la STL con la diferencia de que mantiene la condición en un vector ordenado separado.

Answer 7

std::sort() indicesToDelete en orden descendente y luego borra de los item s en un bucle normal for . No hay necesidad de ajustar los índices entonces.