El 06/10/2011 12:42, Phil Endecott escribió:
Ion Gazta?aga wrote: Well that's another interesting possibility. But to be clear, the current boost::containter::list has O(1) size and O(N) splice. (In fact, the docs don't even mention constant splice when splicing to itself - is that a doc issue?)
Trunk container::list (http://svn.boost.org/svn/boost/trunk/boost/container/list.hpp) contains this code: //! <b>Requires</b>: p must point to an element contained //! by this list. first and last must point to elements contained in list x. //! n == std::distance(first, last) //! //! <b>Effects</b>: Transfers the range pointed by first and last from list x to this list, //! before the the element pointed by p. No destructors or copy constructors are called. //! //! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator //! are not equal. //! //! <b>Complexity</b>: Constant. //! //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this //! list. Iterators of this list and all the references are not invalidated. void splice(const_iterator p, ThisType &x, const_iterator first, const_iterator last, size_type n); This was inspired in Howard Hinnant's "on list size" paper: http://home.roadrunner.com/~hinnant/On_list_size.html
Fundamentally, if you have a list that doesn't store its own size you can have O(N) size and O(1) splice. Given such an implementation it's straightforward to add a wrapper that tracks the size, changing the complexities to O(1) size and O(N) splice. In contrast, if you start with an implementation that stores the size it is impossible to write a wrapper that will give you back O(1) splice. This is why I believe the default implementation should have been the O(N) size one.
As Vicente mentions, it is also possible to write a wrapper that keeps a flag and gives you either O(1) size OR O(1) splice but not both at runtime. Personally I don't much like that idea, but it also requires an underlying implementation that has O(N) size and O(1) splice.
Yes, but you need a mutable member or non-const size() function and that might conflict with multithreading read-only (usually const) accesses, say in shared memory. My choice would be to write a new class without any size() member. It is not a top priority addition to Boost.Container, but patches are welcome ;-) Ion