c++ - std::list 或 std::multimap

Question

嘿，我现在有一个我制作的结构列表，每次我添加一个新对象时，我都会使用 std::list 排序方法对这个列表进行排序。我想知道什么会更快，为此使用 std::multimap 或 std::list，因为我每帧都在迭代整个列表(我正在制作游戏)。

我想听听你的意见，对于这次事件我应该用什么。

Answer 1

std::multimap 可能会更快，因为每次插入的时间复杂度为 O(log n)，而列表的插入和排序时间为 O(n log n)。

根据您的使用模式，使用排序的vector 可能会更好。如果您一次插入一大堆项目然后进行一堆读取——即读取和写入不是交错的——那么使用 vector、std 将获得更好的性能::sort 和 std::binary_search。