c++ - 容器复杂性

Question

因此我有一个std::set<int>和std::list<int>。
我想让我的容器分类。
对于集合，我将具有类似于插入元素O(nlogn)的复杂性。 对于列表，我将具有复杂性，例如插入元素 +调用。 在这两种情况下，复杂性都是，但在 的情况下还有额外的操作。我有一些固定的时间来重新平衡。n
O(n)nO(nlogn)list::sort
O(nlogn)O(n)std::listset

问题来了，哪个容器运行得更快？

Answer 1

由于您想要一个 ' const ' 排序容器，我建议std::vector哪个是缓存友好的。

初始化期间：

• push_back所有元素O(n)。
• std::sort向量O(n log n)。
• std::unique如果您想删除重复项（就像std::set这样）。O(n).

所以初始化是O(n log n).

要检查元素是否存在，请使用std::binary_searchtoO(log n)代替O(n).