c++ - std::map 的时间复杂度是多少

Question

std::map 的时间复杂度是多少？在最坏的情况下它会退化吗？还是由执行决定，我们不知道？

Answer 1

查找与 log(N) 成正比。在典型情况下(作为红黑树实现)比较次数最多可达两倍 Log₂N。

插入通常也与 Log₂N 成正比——但是当您插入一些已经有序的项目时有一个特殊规定¹。在这种情况下，您可以为将要进行插入的位置指定一个“提示”。当该提示正确时，每次插入都是(分摊)O(1) 而不是 O(Log N)，因此按排序顺序插入一系列项目是线性的而不是 N log(N)。您指定的提示是指向要插入的项目之后位置的迭代器。

例如，如果您在一个文件中有一些按排序顺序排列的项目，并且您想要将它们插入到 map 中，您可以指定 your_map.end() 作为“提示” ，构建 map 的复杂度为 O(N)，而不是 O(N Log N)。

---

<子>1. 从技术上讲，这适用于您插入项目的任何时候，而不仅仅是在您按顺序插入它们时——但到目前为止，您有合理“提示”可用的最常见情况是在您按顺序插入项目时。