Le 05/10/11 21:42, Ion Gaztañaga a écrit :
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...
[OT: does anyone know of a list of "C++1x nasties" like this? It's easy to find lists of new features, but harder to find lists of misfeatures...]
Regards, Phil.
In Boost.Container you can avoid this problem if you know the distance between the arguments of a range splice:
void splice(const_iterator p, ThisType &x, const_iterator first, const_iterator last, size_type n)
This splice is constant-time and I've found many times you already know the the distance between first and last.
Hi, long time ago I implemented a library Boost.ConstantTimeSize. Here follows an extract of the motivation. *An hybrid approach* In a http://www.thescripts.com/forum/thread720757.html "A solution for a fast std::list::size() *and* a fast std::list::splice()" - Juha Nieminen present an hybrid solution. " ... I was thinking: What if size() was an O(n) operation only *after* a splice() operation has been performed (and only the first time size() is called after that), but O(1) otherwise? In other words, keep a size variable in the list class and update it as necessary, and additionally keep a flag which tells if this size variable is valid. As long as the flag tells that it's valid, list::size() can return the value of the variable. Only if the flag says it's invalid, then the O(n) counting will be performed, updating the variable, after which the flag can be set to valid. A splice() operation would set the flag to invalid in both lists. This way splice() will always be O(1), and size() will be O(n) only once after a splice(), but O(1) otherwise. You will get speed benefits in all cases except if you alternatively call splice() and size() repeatedly (in which case you just get the same behavior as in most current list implementations, so it's not like the result would be worse). " This discusion will continue forever if we don't want a take in account all the requirements. There is not a best solution, there are bests solution each one on a different context. The question is, do we require only one solution that can not satisfy every body or should allow the user to ask for the better respect to its context. I think that it is better to have the freedom to choose the implementation more adapted to each context. * linear_time: size has linear time complexity -> splice shall be implemented in constant time in the worst case * constant_time: size in constant time in the worst case -> splice has linear time complexity * quasy_constant_time: size in constant time in most of the cases -> splice can have constant time in most of the cases Ion, does Boost.Containers provides these possibilities. If not, do you think it is worth including something like the quasy-constant-time in Boost.Containers? Best, Vicente