c++内置的效率

Question

我是C++的新手，有更多的C语言经验。

我正在编写一个使用string类的程序，并开始怀疑"length()“方法的效率。

我意识到我对这个问题没有一个好的答案，所以我想知道这个问题和类似问题的答案是否存在于某个地方。虽然我更有能力确定我自己的代码的运行时，但当涉及到提供的代码时，我感到有点困惑，所以我发现我不能准确地判断我的程序的效率。

是否有包含所提供代码的运行时信息的c++文档(在线或"man“格式)？

编辑:我通常对此感兴趣，而不仅仅是string::length。

Answer 1

目前，所有STL容器的size()时间复杂度都被低估了。有一个open C++ defect report可以解决这个问题。

目前的ISO标准规定C++容器应该具有恒定复杂性的size()：

21.3lib.basic.string/2

类模板basic_string符合序列的要求，如(23.1.1)所述。此外，由于basic_string支持的迭代器是随机访问迭代器(24.1.5)，因此basic_string符合(23.1)中指定的可逆容器的要求。

23.1lib.tainer.requirements/5

注释表达式：a.size()

• Complexity：( A)

那些标记为‘’(注A)‘’的条目应该具有恒定的复杂度

然而，在标准术语中，“应该”不是一个有约束力的要求；实际上，上面的规定也适用于std::list，但在实践中，一些实现(特别是g++)具有O(N) std::list::size()。

唯一可以保证的是字符串的(end() - begin())是(可能分期) O(1)。这是因为字符串迭代器保证是随机访问的，而随机访问迭代器保证具有恒定的时间operator-。

作为一个更实际的问题，对于所有现有的C++实现，以下是成立的：

• std::string::size() is O(1)
• std::vector::size() is O(1)

它们相当明显，因为字符串和向量都是最有效地实现为具有单独存储大小的连续数组:连续是因为它在满足所有其他复杂性要求的同时提供了最快的元素访问，而存储大小是因为容器要求end()是恒定时间。

Answer 2

我看到的所有实现都是O(1)。

您要查找的文档是C++标准--我相信C++03是目前最新的标准。它不是在线的，也不是人工格式的，它是商业销售的。这里有一个可以找到它的地方的列表，以及最近的价格，here。