edit: ich vergleiche konkretstd::vector'slinear Suchoperationen zumstd::map binär Suchoperationen, weil Herbs Behauptung damit zu tun zu haben schien. Ich weiß, dass die Verwendung einer binären Suche die Leistung von O (N) nach O (log N) verschiebt, aber das würde Herbs Behauptung nicht auf die Probe stellen

Bjarne Stroustrup und Herb Sutter haben kürzlich darüber gesprochen, wie großartigstd::vector ist in Situationen, die man erwarten würdestd::list aufgrund der Kosten von Cache-Fehlern beim Durchlaufen von verknüpften Listen verwendet werden. (sehenhttp://channel9.msdn.com/Events/Build/2014/2-661 bei der 48-Minuten-Marke)

Herb machte jedoch eine weitere Aussage, dass Operationen an einem geordneten Vektor sogar noch schneller waren alsstd::map, (sehenhttp://i.imgur.com/zX07TZR.png entnommen aus der 51: 30-Marke des obigen Channel9-Videos), die ich schwer zu ergründen fand. Deshalb habe ich einen kleinen Test erstellt, um dies zu demonstrieren und hatte Schwierigkeiten, die folgenden Ergebnisse zu reproduzieren:https://ideone.com/MN7DYK

Dies ist der Testcode:

template <typename C>
void test(std::string name, std::vector<int> shuffledInputValues, C & c)
{
   // fill container 'c' with values from 'shuffledInputValues' then erase them all
   {
      std::cout << "testing " << name << "..." << std::endl;
      timer t;

      for (auto val : shuffledInputValues) insert(c, val);
      for (auto val : shuffledInputValues) remove(c, val);
  }
}

// output:
// testing vector...99.189ms
// testing deque...120.848ms
// testing set...4.077ms

Beachten Sie, wie diestd::vector führt eine Größenordnung langsamer alsstd::set . Natürlich ist dies das Ergebnis, das ich erwartet habe, aber ich bin verwirrt über die Behauptung, die Herb zu machen versuchte.

Was mache ich falsch? Oder verstehe ich Herbs Behauptung falsch?

Hinweise zu meiner Test-App:

Es müssen lineare Operationen verwendet werden. Der Sinn der Übung besteht darin, die CPU-Cache-Magie zu demonstrieren. Dies sind die Einschränkungen, die Herb und Bjarne für die Übung auferlegt habenIch habe für meine Vektoriteration kein trickreiches Loop-Unraveling versucht, aber ich glaube, dass die Iteration die Leistung sowieso nicht stark beeinträchtigtIch habe die Schleife auf 10K-Elemente beschränkt, da Ideone bei größeren Sets eine Zeitüberschreitung aufweist, aber das Erhöhen der Größe ändert nichts an den Ergebnissen

bearbeiten: siehehttps://ideone.com/916fVd für ein modifiziertes Beispiel, das nur die Leistung von Suchvorgängen vergleicht. Die lineare Suche weist die gleiche Leistung auf.