我花了很长时间在谷歌上搜索,想找到一个比较所有STL容器在插入/推送、删除/弹出等方面复杂性差异的比较。但是我没有找到任何信息,即使在我所有的STL书籍中也没有找到。有什么提示吗?
当然,我知道一些经验法则,但是哪里有明确定义呢?
我花了很长时间在谷歌上搜索,想找到一个比较所有STL容器在插入/推送、删除/弹出等方面复杂性差异的比较。但是我没有找到任何信息,即使在我所有的STL书籍中也没有找到。有什么提示吗?
当然,我知道一些经验法则,但是哪里有明确定义呢?
尝试使用
http://www.sgi.com/tech/stl/complexity.html
http://www.sgi.com/tech/stl/table_of_contents.html
来自 complexity.html:
从根本上说,对于实际计算机硬件而非抽象的机器模型,精确定义渐近算法复杂度的概念是困难的。因此,我们采用以下准则: 1. 对于一个运行时间为O(f(n))的算法A,必须有相应的算法A',在具有任意长指针和size_t类型的机器上正确执行,使得A和A'在实际硬件上执行基本相同的操作序列。(在简单情况下,A和A'将是相同的。在其他情况下,A可能已经被简化,知道地址是有界的。)对于足够大的输入大小n,A'最多需要Cf(n)的时间,其中C是常数,独立于n和地址大小。(假定指针、size_t和ptrdiff_t操作需要常数时间,与它们的大小无关。) 2. 所有容器或迭代器复杂度规格说明都是摊销复杂度。单个操作可能比规定的时间长。但是,在相同容器或迭代器上进行的任何足够长的操作序列将不会超过相应的规定操作成本之和。 3. 算法规定了最坏情况或平均情况性能,并标明哪种情况。除非另有说明,否则平均值假定容器元素是从具有比容器大小更多可能值的有限类型中选择的,并且容器元素是独立均匀分布的。 4. 操作f的复杂度规范假定由f调用的操作最多需要指定的运行时间。但是,如果在预期情况下调用的操作不超过规定的对数因子,则算法通常仍然适用。 5. 如果操作比当前STL中函数F所假定的更昂贵,则F最多会按比例增加成本。任何未能满足此属性的未来操作都将明确说明。为了使这一点明确,假设F被指定用于输入大小m的时间f(m)。F使用操作Gk,在输入大小n上具有指定的运行时间gk(n)。如果在每个Gk比预期慢至多一个因子h(n)的情况下使用F,则F最多会减速h(m)倍。这是因为当前的算法都不会将操作Gk应用于明显大于m的输入。ISO C++标准定义了算法和容器访问方法的复杂度,如果需要的话。在其他任何地方(如果没有明确说明),所有的赌注都是无效的,库实现者可以自由地进行自己的实现。
例如,您可以假设使用红黑树来实现映射和集合,但没有必要这样做。许多算法针对特定的迭代器类别(如随机访问迭代器)进行了重载或专门化,并且有时甚至可能被优化以从特殊硬件(如XMM寄存器)执行某些操作并行执行。
有时候,您真的必须逻辑上假设一个操作可能会花费多少成本,由于其他要求,比如std::list中的splice必须具有O(1)复杂度=>长度为O(n)。
我有N. Josuttis的书 C++ Standard Library - Tutorial And Reference 所有这些方面都在那里得到了很好的涵盖。
最好的问候,
Ovanes