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

["redi at gcc dot gnu.org" <gcc-bugzilla at gcc dot gnu dot org>]

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

--- Comment #16 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-07-03 08:31:18 UTC ---
(In reply to comment #14)
> (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.

Yes, we're well aware of that, thanks.

This patch made c++98 and c++11 code incompatible and is causing serious
problems for distros.

You've lived with O(n) size for 15 years, you can live with it for a while
longer until libstdc++'s ABI changes.

> 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.

You seem to think we were taken by surprise, that has nothing to do with it.
GCC has maintained ABI compatibility since version 3.4, including between c++98
and c++11 mode in most cases. This change broke that and caused a lot of
problems in real systems (not just "you don't implement the standard!") and has
been reverted until the entire library ABI gets updated at a later date.

> (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.

Calm down. Noone thinks it's wrong, but maintaining ABI compatibility has been
decided to be more important for the current releases. See the mailing lists
for more information.