Als ich letztes Jahr zum ersten Mal in das Unternehmen eintrat, gab es LRUCache in der Basisbibliothek des Unternehmens und seine Implementierung verwendete std::list. Aber die Funktion, die std::list berechnet, verwendet direkt die size()-Methode in stl. Dadurch blieb die Leistung während des Stresstests hier hängen.
Heute hat ein Kollege eine weitere Warteschlangenimplementierung in der Basisbibliothek gefunden, die ebenfalls std::list verwendet. Die size()-Methode wurde auch beim Abrufen der Anzahl der Elemente verwendet.
Leider stellt die Basisbibliothek des Unternehmens nur Header-Dateien bereit, und es ist unmöglich, einzeln zu überprüfen, ob diese Grube an anderen Stellen vorhanden ist.
Werfen wir einen Blick auf die Implementierung der size()-Methode in stl:
size_type
size() const
{ return std::distance(begin(), end()); }Die obige Code-G-Version ist 4.2.1
Offensichtlich die Komplexität ist O(N ). Wenn die Liste viele Elemente enthält, ist die Berechnung sehr langsam. Daher müssen Sie bei der Verwendung von std::list daran denken, selbst eine Zählung zu führen.
