[Bug libstdc++/49561] [C++0x] std::list::size complexity

["blelbach at cct dot lsu.edu" <gcc-bugzilla at gcc dot gnu dot org>]

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

--- Comment #14 from Bryce Lelbach (wash) <blelbach at cct dot lsu.edu> 2012-07-03 03:35:31 UTC ---
(In reply to comment #13)
> Patch reverted, thus in C++11 mode size() is back to O(n) but std::list can
> interoperate with the C++98 version of it.

Why has this been reverted? If std::list<>::size() is not O(1), then GCC's
C++11 standard library is not compliant with the C++11 international standard.
I have personally spoken with multiple members of the standard body and
confirmed that this behavior is REQUIRED by the C++11 standard.

Please re-apply this patch for C++11 mode, or state somewhere in the GCC docs
that GCC is not compliant with the C++11 standard. In the C++03 and C++98
standards, it was highly suggested that compiler vendors implement
std::list<>::size() as O(1).

I understand this is a breaking change, but honestly, the C++ standard has been
suggesting the O(1) implementation for over a decade, and the GCC standard
library developers have chosen to implement different behavior. You've had many
years of warning about this.

(In reply to comment #10)
> I can confirm it was just luck, really.

^ Paolo, this is correct. I think it's a really, really bad idea for any
particular vendor to cherrypick elements of an ISO standard to implement. If
you feel that the C++11 standard is wrong to require an O(1) implementation,
please file a standard defect (I'm afraid you can expect me to fight it).
Otherwise, I'd like to ask that you please reconsider applying this patch.