stați pe un std :: vector vs std :: inserați

Am un std :: vector sortat de dimensiuni relativ mici (de la 5 la 20 de elemente). Am folosit std :: vector deoarece datele sunt continue, deci am viteza din cauza memoriei cache. Într-un anumit punct trebuie să elimină un element din acest vector .

Am o îndoială: care este cea mai rapidă modalitate de a elimina această valoare între cele două opțiuni de mai jos?

  1. setați acel element la 0 și apelați sort pentru a reordona: aceasta are complexitate, dar elementele se află pe aceeași linie de cache.
  2. apelați delete care va copia (sau memcpy cine știe?) toate elementele după ea de 1 loc (trebuie să investighez spatele ștergerii).

Știți care este mai rapid?

Cred că aceeași abordare ar putea fi gândită și la introducerea unui element nou fără a se atinge capacitatea maximă a vectorului.

Salutari

AFG

0
... și tipul elementului containerului contează prea.
adăugat autor dirkgently, sursa
faci ipoteze despre linii de cache și așa mai departe, dar cred că e mai bine să o profilați în condiții realiste.
adăugat autor juanchopanza, sursa
de ce nu folosiți ceva care se potrivește acestui model, ca o hartă ordonată? se ocupă de aceste lucruri în mod automat, iar la aceste mărimi, deasupra capului arborelui inferior este neglijabilă.
adăugat autor Not_a_Golfer, sursa
De ce nu măsurați și aflați?
adăugat autor Oliver Charlesworth, sursa
De asemenea, nu reușesc să văd cum sortarea (care implică copierea) ar putea fi mai rapidă decât copierea.
adăugat autor Oliver Charlesworth, sursa

1 răspunsuri

Dacă nu vă interesează ordinea elementelor, este posibil să înlocuiți elementul cu cel din urmă.

void Remove( std::vector &vec, iterator i ) {
    iterator last = vec.end()-1;
    if (i != last)
        std::swap( *i, *last );
    vec.erase( last );
}

Menționați stabilirea elementului la 0. Dacă aceasta înseamnă că aveți indicii, atunci este posibil să nu aveți nevoie de swap:

void Remove( std::vector &vec, iterator i ) {
    vec[i] = vec.back();
    vec.erase( vec.end()-1 );
}

Dacă vă interesează ordinea, atunci cea de-a doua opțiune de a utiliza utilizarea ștergerii() o va păstra și va face o cantitate minimă de lucru. Este aproape sigur că va fi mai rapid decât recurgerea.

0
adăugat