c++ - std::dequeまたはstd::list

Question

私は使用push_front()してpush_back()いるだけです。insert()したがって、またはを使用する他の費用は発生しませんremove()。

私は、両方のコンテナーがO(1)これらの関数のそれぞれに複雑さを提供していることを知っています。dequelist

しかし、もしあれば、どちらの時間が他の時間よりも短いかを知りたいのです。

Answer 1

あなたの質問に答える方法がわからない。自分で簡単に作成できるベンチマークプログラムを作成してほしいと思われます。だから、それをする代わりに、私はこれを述べるだけです：

• を使用するlistと、プッシュするすべてのアイテムにメモリ割り当てが発生します。
• を使用するdequeと、大きなブロックが一度に割り当てられます。

通常、メモリの割り当てが遅いことを考えると、dequeリストよりもパフォーマンスが優れていると思います。

一度に多くのアイテムをプッシュまたはポップする場合、キャッシュの局所性が機能するため、これは特に当てはまります。

もちろん、メモリプールを使用するアロケータをリストに書き込むこともできます。そうすれば、パフォーマンスが向上する可能性があります。

したがって、これらの仮説を念頭に置いて、離れてそれを測定します。結果について話し合いたい場合は、それが質問をするときです。

Answer 2

パフォーマンスに関しては、「推測」することはお勧めできません（または、インターネットで質問することは、推測よりもわずかに優れていますが、多少だけです）。この場合は、ループを実行するだけで、常に2つのオプションを測定するのが最善です。 、およびpush_backまたはpush_frontを現実的にするのに十分なもの[より現実的にして、コードのほとんどのことを実行し、時間を測定するのに十分な時間持続するのに十分な回数ループで実行することをお勧めします-多くの場合、list/にバジリオンの値を追加して、deque「スワップアウトする必要がある場合、非常に遅くなる」ことを見つけるよりも現実的です]。