Cancellazione di elementi in stl :: vector utilizzando gli indici

Question

Ho uno stl::vector<int> e ho bisogno di rimuovere tutti gli elementi con indici specifici (il vettore di solito ha un'elevata dimensionalità). Mi piacerebbe sapere, che è il modo più efficiente per fare un'operazione del genere avendo in mente che l'ordine del vettore originale dovrebbe essere preservato.

Sebbene, ho trovato post correlati su questo problema, alcuni di loro avevano bisogno di rimuovere uno single element o multiple elements dove il remove-erase idiom sembrava essere una buona soluzione. Nel mio caso, tuttavia, ho bisogno di cancellare più elementi e dal momento che sto usando gli indici invece dei valori diretti, non è possibile applicare remove-erase idiom, giusto? Di seguito il mio codice e vorrei sapere se è possibile fare di meglio in termini di efficienza?

bool find_element(const vector<int> & vMyVect, int nElem){ 
    return (std::find(vMyVect.begin(), vMyVect.end(), nElem)!=vMyVect.end()) ? true : false; 
} 

void remove_elements(){ 

    srand (time(NULL)); 

    int nSize = 20; 
    std::vector<int> vMyValues; 
    for(int i = 0; i < nSize; ++i){ 
      vMyValues.push_back(i); 
    } 

    int nRandIdx; 
    std::vector<int> vMyIndexes; 
    for(int i = 0; i < 6; ++i){ 
     nRandIdx = rand() % nSize; 
     vMyIndexes.push_back(nRandIdx); 
    } 

    std::vector<int> vMyResult; 
    for(int i=0; i < (int)vMyValues.size(); i++){ 
     if(!find_element(vMyIndexes,i)){ 
      vMyResult.push_back(vMyValues[i]); 
     } 
    } 
} 

Answer 1

penso che potrebbe essere più efficiente, se appena appena sorta vostri indici e quindi eliminare quegli elementi dal vostro vettore dal più alto al più basso. L'eliminazione dell'indice più alto in un elenco non invaliderà gli indici inferiori che si desidera eliminare, poiché solo gli elementi superiori a quelli eliminati modificano l'indice.

Se è davvero più efficiente dipenderà dalla velocità di smistamento. Un altro professionista di questa soluzione è che non hai bisogno di una copia del tuo vettore di valore, puoi lavorare direttamente sul vettore originale. codice dovrebbe essere simile a questa:

... fill up the vectors ... 

sort (vMyIndexes.begin(), vMyIndexes.end()); 

for(int i=vMyIndexes.size() - 1; i >= 0; i--){ 
    vMyValues.erase(vMyValues.begin() + vMyIndexes[i]) 
} 

Answer 2

per evitare di spostare gli stessi elementi molte volte, siamo in grado di spostarli da catene tra gli indici cancellati

// fill vMyIndexes, take care about duplicated values 
vMyIndexes.push_back(-1); // to handle range from 0 to the first index to remove 
vMyIndexes.push_back(vMyValues.size()); // to handle range from the last index to remove and to the end of values 
std::sort(vMyIndexes.begin(), vMyIndexes.end()); 
std::vector<int>::iterator last = vMyValues.begin(); 
for (size_t i = 1; i != vMyIndexes.size(); ++i) { 
    size_t range_begin = vMyIndexes[i - 1] + 1; 
    size_t range_end = vMyIndexes[i]; 
    std::copy(vMyValues.begin() + range_begin, vMyValues.begin() + range_end, last); 
    last += range_end - range_begin; 
} 
vMyValues.erase(last, vMyValues.end()); 

P.S. corretto un bug, grazie a Steve Jessop che ha cercato pazientemente di mostrarmelo

Answer 3

Se si vuole assicurare che ogni elemento venga spostato una sola volta, si può semplicemente scorrere attraverso ogni elemento, copiare quelli che devono rimanere in un nuovo, secondo contenitore, non copiare quelli che desideri rimuovere e quindi eliminare il vecchio contenitore e sostituirlo con quello nuovo :)

Answer 4

Quello che puoi fare è dividere il vettore (in realtà un qualsiasi contenitore non associativo) in due gruppi, uno corrispondente agli indici da cancellare e uno contenente il resto.

template<typename Cont, typename It> 
auto ToggleIndices(Cont &cont, It beg, It end) -> decltype(std::end(cont)) 
{ 
    int helpIndx(0); 
    return std::stable_partition(std::begin(cont), std::end(cont), 
     [&](typename Cont::value_type const& val) -> bool { 
      return std::find(beg, end, helpIndx++) != end; 
    }); 
} 

è possibile eliminare da (o fino a) il punto di divisione per cancellare (mantenere solo) gli elementi corrispondenti a indici

std::vector<int> v; 
v.push_back(0); 
v.push_back(1); 
v.push_back(2); 
v.push_back(3); 
v.push_back(4); 
v.push_back(5); 

int ar[] = { 2, 0, 4 }; 
v.erase(ToggleIndices(v, std::begin(ar), std::end(ar)), v.end()); 

• Se il 'tenere solo index' operazione non è necessaria è possibile utilizzare remove_if insted di stable_partition (O (n) vs O (nlogn) complessità)
• Per funzionare per i vettori C come contenitori, la funzione lambda deve essere [&] (decrittata pe (* (std :: begin (cont))) const & val) -> bool {return std :: find (beg, end, helpIndx ++)! = end; } ma poi il.cancellare() metodo non è un'opzione

Answer 5

Erase-rimuovere più elementi in determinati indici

C++ 11 Versione utilizzando std :: mossa (vedi linea commentata-out per C++ 98-versione):

template <class ForwardIt, class SortedIndicesForwardIt> 
inline ForwardIt remove_at(
    ForwardIt first, 
    ForwardIt last, 
    SortedIndicesForwardIt indices_fist, 
    SortedIndicesForwardIt indices_last) 
{ 
    // flag elements to keep 
    typedef typename std::vector<bool> Flags; 
    Flags is_keep(
     static_cast<Flags::size_type>(std::distance(first, last)), true); 
    for(; indices_fist != indices_last; ++indices_fist) 
     is_keep[static_cast<Flags::size_type>(*indices_fist)] = false; 
    // move kept elements to beginning 
    typedef typename Flags::const_iterator FlagsIt; 
    ForwardIt dest = first; 
    for(FlagsIt keepIt = is_keep.begin(); first != last; ++first, ++keepIt) 
     if(*keepIt) 
      *dest++ = std::move(*first); // *dest++ = *first; //<= c++98 
    return dest; 
} 

esempio di utilizzo:

std::vector<int> vec = /*...*/; 
std::vector<size_t> indices = /*...*/; 

std::sort(indices.begin(), indices.end()); 
vec.erase(
    remove_at(vec.begin(), vec.end(), indices.begin(), indices.end()), 
    vec.end() 
); 

Note:

• indici devono essere filtrate
• bandiere ciascun elemento (tenuti o rimosso) usando un vettore temporaneo di bools
• Live example