Warum vermeidet „std::sort' „std::swap' für kleine Datensätze?

std::sorts Vermeidung von std::swap mit kleinen Datensätzen

In diesem Codeausschnitt wird ein Array benutzerdefinierter Objekte erstellt und übergeben an std::sort.

<code class="cpp">std::vector<my_space::A> vec(n);
for (int i = 0; i < n; ++i) {
  vec[i].a = -i;
}

std::sort(vec.begin(), vec.end());

Die benutzerdefinierte Swap-Funktion in my_space ist definiert als:

<code class="cpp">namespace my_space
{
struct A
{
  double a;
  double* b;
};

void swap(A& lhs, A& rhs)
{
  std::cerr << "My swap.\n";
  std::swap(lhs.a, rhs.a);
  std::swap(lhs.b, rhs.b);
}
}  

Bei der Ausführung wird das folgende Phänomen beobachtet: wenn n auf 20 gesetzt ist , die benutzerdefinierte Swap-Funktion wird aufgerufen und das Array wird erfolgreich sortiert. Wenn n jedoch auf 4 gesetzt ist, wird das Array sortiert, ohne die benutzerdefinierte Swap-Funktion aufzurufen.

Dieses Verhalten ist darauf zurückzuführen, dass std::sort die Einfügungssortierung für kleine Bereiche verwendet. In der stdlibc-Implementierung von GCC wird aus Leistungsgründen die Einfügungssortierung verwendet. Folgendes passiert intern:

<code class="cpp">typename iterator_traits<RandomAccessIterator>::value_type
  __val = _GLIBCXX_MOVE(*__i);
_GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
*__first = _GLIBCXX_MOVE(__val);</code>

Dieser Vorgang ahmt n Swaps in einer schnellen Aktion nach. Daher wird die benutzerdefinierte Swap-Funktion nicht aufgerufen.

Es ist bemerkenswert, dass _GLIBCXX_MOVE std::move nur dann aufruft, wenn GXX_EXPERIMENTAL_CXX0X definiert ist. Andernfalls werden die Werte standardmäßig kopiert.

Das obige ist der detaillierte Inhalt vonWarum vermeidet „std::sort' „std::swap' für kleine Datensätze?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!