应该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屋！