C++内置的效率[关闭]

目前,时间的复杂性 size() 对于 全部的 STL容器未指定。有一个 open C++ defect report 为此。

目前的ISO C++标准称STL容器 应该 有 尺寸() 具有恒定的复杂性:

21.3[库基本字符串]/2

类模板基本_字符串符合序列的要求,如(23.1.1)所述。此外,由于basic_string支持的迭代器是随机访问迭代器(24.1.5),因此basic_string符合可逆容器的要求,如(23.1)所述。

23.1[库容器要求]/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() 保持时间不变。

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

你正在寻找的文档是C++标准——我相信C++ 03是目前最新的。它不在网上或以男人的形式提供,它是商业销售。这里有一个能找到它的地方的清单,还有最近的价格, here .