应该std :: list :: size在C ++ 11有常量的复杂性吗? [英] Should std::list::size have constant complexity in C++11?
问题描述
我使用 gcc 4.8.1 ,经过几个小时的调试,一个可怕的神秘性能问题,我发现 std :: list :: size
实际上实现为对 std :: distance
的调用。
I am using gcc 4.8.1 and after hours of debugging a horrible mysterious performance issue I found out that the std::list::size
is actually implemented as a call to std::distance
.
/** Returns the number of elements in the %list. */
size_type
size() const _GLIBCXX_NOEXCEPT
{ return std::distance(begin(), end()); }
这让我很惊讶,因为参考文档说复杂性std :: list :: size应该是常数,复杂度 std :: distance
是 std :: list :: iterator
的线性。
This surprised me, since the reference says that the complexity of std::list::size should be constant and the complexity of std::distance
is linear for std::list::iterator
.
我真的很困惑, gcc对C ++ 11的功能有很好的支持,我没有理由为什么他们不会实现这一个。
I am really confused, since I think gcc has excellent support for C++11 features and I see no reason why they would not implement this one.
这是参考或gcc中的错误吗?
Is this an error in the reference or in gcc?
在后一种情况下:
有什么原因会导致这样的基本C ++ 11功能太长?
is there any reason why such a fundamental C++11 feature would be missing for so long?
是否有第三种可能性,例如:
Is there a third possibility e.g.:
Could I have gcc 4.8.1 but some older version of the standard library?
推荐答案
这不是一个错误,您可以在这里阅读:
This is not exactly a bug and you can read about it here:
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561
这更像是与旧版本的gcc的兼容性。
看起来他们真的不想添加额外的数据成员。
It's more of a case of compatibility with older versions of gcc. Looks like they really don't want to add an additional "data member".
引用:
这个补丁使得c ++ 98和c ++ 11代码不兼容,并导致了
对于发行版的严重问题。
This patch made c++98 and c++11 code incompatible and is causing serious problems for distros.
其中补丁
是他们为gcc 4.7(它是O(1))实现的修复。
Where the patch
is the fix they implemented for gcc 4.7 (it was O(1) in it).
另一个引言:
维持ABI兼容性已被决定为更重要
当前版本
maintaining ABI compatibility has been decided to be more important for the current releases
这篇关于应该std :: list :: size在C ++ 11有常量的复杂性吗?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!