我用谷歌搜索了很长时间，以便找出一个比较，显示所有 STL 容器在插入/推送擦除/弹出等方面的复杂性差异。我没有找到任何东西。也不是在我所有的 STL 书籍中。有什么提示吗？
我当然知道一些经验法则。但是定义在哪里？
问问题
24188 次
3 回答
3
尝试
http://www.sgi.com/tech/stl/complexity.html
http://www.sgi.com/tech/stl/table_of_contents.html
从complexity.html：
从根本上说，对于真实的计算机硬件而不是抽象的机器模型，很难准确地定义渐近算法复杂度的概念。因此，我们满足以下准则：
- 对于具有运行时间 O(f(n)) 的算法 A，必须有一个对应的算法 A' 在具有任意长指针和 size_t 类型的机器上是正确的，这样 A 和 A' 执行基本相同的操作序列在实际硬件上。（在简单的情况下，A 和 A' 将是相同的。在其他情况下，A 可能已经被简化，因为知道地址是有界的。）对于足够大尺寸 n 的输入，A' 必须花费最多时间 Cf(n)，其中 C 是一个常数，与 n 和地址大小无关。（指针、size_t 和 ptrdiff_t 操作被假定花费恒定时间，与它们的大小无关。）
- 所有容器或迭代器复杂性规范均指摊销复杂性。单个操作可能需要比指定时间更长的时间。但是在同一个容器或迭代器上任何足够长的操作序列将最多花费指定操作成本的相应总和。
- 算法指定最坏情况或平均情况的性能，并确定哪种情况。除非另有说明，否则平均值假定容器元素是从具有比容器大小更多的可能值的有限类型中选择的，并且容器元素是独立均匀分布的。
- 操作 f 的复杂性规范假定 f 调用的操作最多需要指定的运行时。但是，如果调用的操作不超过预期情况下指定的对数因子，则算法通常仍然适用。
如果操作比当前 STL 中的函数 F 假设的更昂贵，那么 F 最多会按增加的成本成比例地减慢。未来任何无法满足此属性的操作都会使其明确。
为了准确起见，假设 F 被指定为使用时间 f(m) 来进行大小为 m 的输入。F 使用操作 Gk，在输入大小 n 上具有指定的运行时间 gk(n)。如果在每个 Gk 比预期最多慢一个因子 h(n) 的上下文中使用 F，则 F 最多减慢一个因子 h(m)。这是因为当前的算法都没有将操作 Gk 应用于明显大于 m 的输入。
于 2009-06-26T13:20:22.093 回答
1
ISO C++ 标准在需要时定义了算法和容器访问方法的复杂性。在其他任何地方（如果没有明确说明），所有的赌注都没有了，库实现者可以自由地进行自己的实现。
例如，您可以假设地图和集合是使用红黑树实现的，但没有要求这样做。许多算法被重载或专门用于特定的迭代器类别（如随机访问迭代器），有时甚至可能被优化为从特殊硬件执行（如 XMM 注册并并行执行一些操作）。
有时，由于其他要求，您确实必须在逻辑上假设操作可能花费多少，例如 std::list 中的拼接必须具有 O(1) 复杂性 => 长度具有 O(n)。
我有来自 N. Josuttis C++ Standard Library - Tutorial And Reference的书 ，所有这些方面都在那里得到了很好的介绍。
最好的问候，
Ovanes
于 2009-06-26T14:22:46.943 回答
1
看看这份关于 STL、Boost 和阵列容器性能的报告
于 2013-09-18T11:14:48.817 回答