The complexity is a lie.

The complexity is a lie.
http://www.cplusplus.com/reference/list/list/size/

Comments

  1. Jörg Barfurth5 June 2014 at 01:42

    Why do you think so? And are you talking about the C++11 case?

    ReplyDelete
  2. Lars Clausen5 June 2014 at 04:40

    Yes. Apparently having a constant-time size function (and the structure changes that implied) broke so much binary compatibility that at least GCC has decided to revert to the linear-time size function. Some of my colleagues just got bit by that. I leave it as an exercise for the reader to implement both size() and splice() in constant time.

    ReplyDelete
  3. Jörg Barfurth5 June 2014 at 05:16

    C++03 required ABI breakage for some implementors. So does C++11. If compatibility is more important, vendors must not claim that their implementation (fully) conforms to the standard.

    So what you are saying is not that the complexity claim in the standard is a lie. But that a specific implementation is still at pre-C++11 for this.

    Full-list and single-element splice are easily done in constant time, even when tracking size. Range splice is specified to be up to linear in the size of the range. Apparently the C++11 committee decided to favor constant size over constant splice.

    ReplyDelete

Post a Comment

Popular posts from this blog

#Security weirdness of the day: I followed a link to #Instagram, and it told me they'd noticed an unusual login. Now I hardly ever log in to Instagram, so I imagine any login would be tagged as unusual. But this login - which blocked me from viewing a public post until I answered whether it was me or not - was from two months ago. I have no idea if I logged in then. I might have, for whatever reason, but who remembers where they log in for several months? Not I. The follow-up page had me change my password, without any other kind of challenge. I got a mail afterwards, but seriously, that's some weird shit.
Read more

If only the sun flares in my photos were this impressive.

Image
If only the sun flares in my photos were this impressive. Originally shared by Astronomy Picture of the Day (APoD) A Solar Filament Erupts Image Credit: NASA 's GSFC, SDO AIA Team https://apod.nasa.gov/apod/ap180916.html What's happened to our Sun? Nothing very unusual -- it just threw a filament. Toward the middle of 2012, a long standing solar filament suddenly erupted into space producing an energetic Coronal Mass Ejection (CME). The filament had been held up for days by the Sun's ever changing magnetic field and the timing of the eruption was unexpected. Watched closely by the Sun-orbiting Solar Dynamics Observatory, the resulting explosion shot electrons and ions into the Solar System, some of which arrived at Earth three days later and impacted Earth's magnetosphere, causing visible aurorae. Loops of plasma surrounding an active region can be seen above the erupting filament in the featured ultraviolet image. Although the Sun is now in a relatively inactive state ...
Read more