std :: list :: size在C++ 11中应该具有恒定的复杂性吗？

Question

我正在使用gcc 4.8.1并经过数小时的调试后发现一个可怕的神秘性能问题,我发现它std::list::size实际上是作为一个调用实现的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.

我真的很困惑,因为我认为gcc对C++ 11功能有很好的支持,我认为他们没有理由不实现这个功能.

这是引用中还是gcc中的错误？

在后一种情况下:

有这么一个基本的C++ 11功能会缺少这么久的原因吗？

还有第三种可能性,例如:

我可以使用gcc 4.8.1但是标准库的某些旧版本？

Answer 1

这不是一个错误,你可以在这里阅读:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

它更像是与旧版gcc兼容的情况.看起来他们真的不想添加额外的"数据成员".

引用:

这个补丁使得c ++ 98和c ++ 11代码不兼容,并且对于发行版造成严重问题.

这patch是他们为gcc 4.7实现的修复(它是O(1)).

另一个引用:

保持ABI兼容性已被确定为当前版本更重要