list - Big O リストの複雑さ 8 バイト対 16 バイト

Question

次のリンクで：

http://www.baptiste-wicht.com/2012/12/cpp-benchmark-vector-list-deque/

彼が並べ替えを比較しているセクションまで下にスクロールすると、最初に 8 バイトのデータ型の結果が表示され、リスト、ベクター、および両端キューが比較されます。8 バイト (および 128 バイト) のデータ型の場合、リストは vector や deque よりもはるかに遅くなります。ただし、並べ替え比較の最後で 16 バイトのデータ型を使用すると、突然リストが高速になります。

8 バイトと 128 バイトではリストが遅くなり、その間の値 (つまり 16 バイト) ではどのように速くなるでしょうか??

編集: random_insert セクションで同じパターンに気付きました。List は、8 バイトおよび 32 バイトのデータ型では vector および deque よりも遅いですが、16 バイトでははるかに高速ですか?

Answer 1

16 バイト データ型は「単純な 16 バイト データ型」ではないことに注意してください。

自明ではないデータ型は 2 つの long で構成されており、非常に愚かな代入演算子と、いくつかの計算を行うだけのコピー コンストラクターがあります (まったく意味がありませんが、コストがかかります)。これは共通のコピー コンストラクターでも共通の代入演算子でもないと主張する人もいるかもしれませんが、ここで重要な点は、このベンチマークには十分なコストのかかる演算子であるということです。

したがって、これはリストを遅くする魔法の数である16バイトとは何の関係もありませんが、それはリストを遅くする重要な型での演算子のオーバーロードに関するものです。