on Wed Oct 05 2011, Ion Gaztañaga <igaztanaga-AT-gmail.com> wrote:
El 05/10/2011 20:28, Phil Endecott escribió:
In another thread, Stephan T. Lavavej wrote:
Two-list partial-splice is now linear time. FDIS 23.3.5.5 [list.ops]/14: "Complexity: Constant time if &x == this; otherwise, linear time."
Is there an opportunity here for Boost.Containers to provide a std::list replacement that keeps the old O(1) splice and O(N) size? I can imagine a lot of demand for this once people discover that their old splicing code is trashed by a std library upgrade...
IMHO this O(1) splice list should not have size() at all, just like forward_list.
Exactly. There's room for a list with a cached size that's normally O(1) except after a splice, but let's find out that someone needs it before we go there. -- Dave Abrahams BoostPro Computing http://www.boostpro.com