[Containers] How about a list with O(1) splice?
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.
On Oct 5, 2011, at 11:28 AM, Phil Endecott wrote:
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...]
I'd be happy to compile such a list, if people want to contribute... -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki
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.
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
on Wed Oct 05 2011, "Vicente J. Botet Escriba" <vicente.botet-AT-wanadoo.fr> wrote:
I think that it is better to have the freedom to choose the implementation more adapted to each context.
I think the amount of interface and documentation complication needed to achieve that isn't worth the gains over a "usually O(1) size implementation." If you really want the next size() to be O(1) after a splice all you need to do is... call size(). -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Dave Abrahams wrote:
on Wed Oct 05 2011, "Vicente J. Botet Escriba" <vicente.botet-AT-wanadoo.fr> wrote:
I think that it is better to have the freedom to choose the implementation more adapted to each context.
I think the amount of interface and documentation complication needed to achieve that isn't worth the gains over a "usually O(1) size implementation." If you really want the next size() to be O(1) after a splice all you need to do is... call size().
How the call to size() make later call to size() O(1)? Vicente -- View this message in context: http://boost.2283326.n4.nabble.com/Containers-How-about-a-list-with-O-1-spli... Sent from the Boost - Dev mailing list archive at Nabble.com.
Vicente Botet wrote:
Dave Abrahams wrote:
on Wed Oct 05 2011, "Vicente J. Botet Escriba" <vicente.botet-AT-wanadoo.fr> wrote:
I think that it is better to have the freedom to choose the implementation more adapted to each context.
I think the amount of interface and documentation complication needed to achieve that isn't worth the gains over a "usually O(1) size implementation." If you really want the next size() to be O(1) after a splice all you need to do is... call size().
How the call to size() make later call to size() O(1)?
I think he was referring to your amortized constant time size(). The first call notices the dirty flag and computes the size in linear time. The second, and subsequent calls, will be constant time. _____ Rob Stewart robert.stewart@sig.com Software Engineer using std::disclaimer; Dev Tools & Components Susquehanna International Group, LLP http://www.sig.com ________________________________ IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
Ion Gazta?aga 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...
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.
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?) 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. Or, as Ion suggests, it could not have size() at all - that would work. Ion, is there any chance of adding something like this to Boost.Container? Regards, Phil.
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
on Thu Oct 06 2011, Ion Gaztañaga <igaztanaga-AT-gmail.com> wrote:
//! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator //! are not equal.
Are you sure you want to make this defined behavior? -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Thu, Oct 6, 2011 at 7:15 PM, Dave Abrahams <dave@boostpro.com> wrote:
on Thu Oct 06 2011, Ion Gaztañaga <igaztanaga-AT-gmail.com> wrote:
//! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator //! are not equal.
Are you sure you want to make this defined behavior?
Wouldn't it be a logic_error? An assert seems more appropriate.
on Thu Oct 06 2011, Olaf van der Spek <ml-AT-vdspek.org> wrote:
On Thu, Oct 6, 2011 at 7:15 PM, Dave Abrahams <dave@boostpro.com> wrote:
on Thu Oct 06 2011, Ion Gaztañaga <igaztanaga-AT-gmail.com> wrote:
//! <b>Throws</b>: std::runtime_error if this' allocator and x's allocator //! are not equal.
Are you sure you want to make this defined behavior?
Wouldn't it be a logic_error? An assert seems more appropriate.
That's my point. IMO we shouldn't throw in response to conditions that are almost certainly programming errors. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Thu, Oct 6, 2011 at 8:50 PM, Dave Abrahams <dave@boostpro.com> wrote:
Wouldn't it be a logic_error? An assert seems more appropriate.
That's my point. IMO we shouldn't throw in response to conditions that are almost certainly programming errors.
assert() works only in NDEBUG builds. What options besides throwing does one have? Olaf
on Thu Oct 06 2011, Olaf van der Spek <ml-AT-vdspek.org> wrote:
On Thu, Oct 6, 2011 at 8:50 PM, Dave Abrahams <dave@boostpro.com> wrote:
Wouldn't it be a logic_error? An assert seems more appropriate.
That's my point. IMO we shouldn't throw in response to conditions that are almost certainly programming errors.
assert() works only in NDEBUG builds. What options besides throwing does one have?
BOOST_ASSERT(). -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Thu, Oct 6, 2011 at 9:44 PM, Dave Abrahams <dave@boostpro.com> wrote:
on Thu Oct 06 2011, Olaf van der Spek <ml-AT-vdspek.org> wrote:
On Thu, Oct 6, 2011 at 8:50 PM, Dave Abrahams <dave@boostpro.com> wrote:
Wouldn't it be a logic_error? An assert seems more appropriate.
That's my point. IMO we shouldn't throw in response to conditions that are almost certainly programming errors.
assert() works only in NDEBUG builds. What options besides throwing does one have?
BOOST_ASSERT().
That's a no-op when NDEBUG is defined, just like assert(). Olaf
on Thu Oct 06 2011, Olaf van der Spek <ml-AT-vdspek.org> wrote:
On Thu, Oct 6, 2011 at 9:44 PM, Dave Abrahams <dave@boostpro.com> wrote:
on Thu Oct 06 2011, Olaf van der Spek <ml-AT-vdspek.org> wrote:
On Thu, Oct 6, 2011 at 8:50 PM, Dave Abrahams <dave@boostpro.com> wrote:
Wouldn't it be a logic_error? An assert seems more appropriate.
That's my point. IMO we shouldn't throw in response to conditions that are almost certainly programming errors.
assert() works only in NDEBUG builds. What options besides throwing does one have?
BOOST_ASSERT().
That's a no-op when NDEBUG is defined, just like assert().
And that's a problem because...? I repeat: undefined behavior is called for here. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Fri, Oct 7, 2011 at 12:08 AM, Dave Abrahams <dave@boostpro.com> wrote:
That's a no-op when NDEBUG is defined, just like assert().
And that's a problem because...?
I repeat: undefined behavior is called for here.
Sometimes you'd like certain assert checks to be done at run-time too.
El 06/10/2011 19:15, Dave Abrahams escribió:
on Thu Oct 06 2011, Ion Gaztañaga<igaztanaga-AT-gmail.com> wrote:
//!<b>Throws</b>: std::runtime_error if this' allocator and x's allocator //! are not equal.
Are you sure you want to make this defined behavior?
I was just reproducing existing practice of some implementations (*), but I agree that we could just require it as a precondition and use assert. (*) http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1599.html
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. Ion
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
participants (8)
-
Dave Abrahams -
Ion Gaztañaga -
Marshall Clow -
Olaf van der Spek -
Phil Endecott -
Stewart, Robert -
Vicente Botet -
Vicente J. Botet Escriba