Sådan fjernes elementer fra en container i C ++

Sådan fjernes elementer fra containeren er et almindeligt C ++ interviewspørgsmål, så du kan optjene nogle brownie-point, hvis du læser denne side omhyggeligt.

Slet – fjern idiomet er en C ++ teknik til at fjerne elementer, der opfylder et bestemt kriterium fra en container. Det er dog muligt at eliminere elementer med traditionel håndskrevet sløjfe, men slet-fjern idiomet har flere fordele.

Sammenligning

// Using a hand-written loop std::vector v = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; for (auto iter = v.cbegin(); iter < v.cend(); /*iter++*/) { if (is_odd(*iter)) { iter = v.erase(iter); } else { ++iter; } } // Using the erase–remove idiom std::vector v = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; v.erase(std::remove_if(v.begin(), v.end(), is_odd), v.end());

Som du kan se, kræver koden med håndskrevet sløjfe lidt mere at skrive, men den har også et præstationsproblem. Hvert eraseopkald skal flytte alle elementerne fremad efter den slettede, for at undgå "huller" i samlingen. At ringe eraseflere gange til den samme container genererer masser af omkostninger ved at flytte elementerne.

På den anden side er koden med slet – fjern idiomet ikke kun mere udtryksfuldt, men det er også mere effektivt. For det første bruger du remove_if/removetil at flytte alle elementer, der ikke passer til fjernelseskriterierne, til fronten af ​​intervallet og holde elementernes relative rækkefølge. Så efter opkald sletter remove_if/removeet enkelt opkald med erasealle resterende elementer i slutningen af ​​intervallet.

Eksempel

#include  // the general-purpose vector container #include  // cout #include  // remove and remove_if bool is_odd(int i) { return (i % 2) != 0; } void print(const std::vector &vec) { for (const auto& i : vec) std::cout << i << ' '; std::cout << std::endl; } int main() { // initializes a vector that holds the numbers from 1-10. std::vector v = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; print(v); // removes all elements with the value 5 v.erase(std::remove(v.begin(), v.end(), 5), v.end()); print(v); // removes all odd numbers v.erase(std::remove_if(v.begin(), v.end(), is_odd), v.end()); print(v); // removes multiples of 4 using lambda v.erase(std::remove_if(v.begin(), v.end(), [](int n) { return (n % 4) == 0; }), v.end()); print(v); return 0; } /* Output: 1 2 3 4 5 6 7 8 9 10 1 2 3 4 6 7 8 9 10 2 4 6 8 10 2 6 10 */

Kilder

"Slet – fjern idiom" Wikipedia: The Free Encyclopedia. Wikimedia Foundation, Inc. en.wikipedia.org/wiki/Erase-remove_idiom

Meyers, Scott (2001). Effektiv STL: 50 specifikke måder at forbedre din brug af standardskabelonbiblioteket. Addison-Wesley.