c ++内置的效率

Question

我是C++的新手,拥有更多的C经验.

我正在编写一个将使用字符串类的程序,并开始怀疑"length()"方法的效率.

我意识到虽然我对这个问题没有一个好的答案,所以想知道这个和类似问题的答案是否存在于某个地方.虽然我能够确定自己代码的运行时间,但在提供代码方面我有点不知所措,所以我发现我无法准确判断程序的效率.

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

编辑:我一般对此感兴趣,而不仅仅是string :: length.

Answer 1

我见过的所有实现都是O(1).

您正在寻找的文档是C++标准 - 我相信C++ 03是目前最新的文档.它不是在线或以人工格式提供的,而是商业销售的.有找到了它的地方的清单,以及最近的价格,在这里.

Answer 2

目前,时间复杂度size()为所有的STL容器是尚未.有一个开放的C++缺陷报告.

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

21.3 [lib.basic.string]/2

类模板basic_string符合Sequence的要求,如(23.1.1)中所述.另外,因为basic_string支持的迭代器是随机访问迭代器(24.1.5),所以basic_string符合(23.1)中规定的可逆容器的要求.

23.1 [lib.container.requirements]/5

• 表达: a.size()
• 复杂性:(注A)

那些标有''(注释A)'的条目应该具有不变的复杂性

但是,"应该"不是标准用语中的约束性要求; 实际上,上述内容也适用std::list,但实际上一些实现(特别是g ++)具有O(N)std::list::size().

唯一可以保证的是,(end() - begin())字符串是(可能是摊销的)O(1).这是因为字符串迭代器保证是随机访问,并且随机访问迭代器保证具有恒定时间operator-.

作为一个更实际的问题,对于所有现有的C++实现,以下内容成立:

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

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