Re: "Fixing" the O(1) splice / O(1) size std::list problem?
"Howard Hinnant" <howard.hinnant@gmail.com> wrote in message
news:howard.hinnant-6EA91E.11483014022007@news-server.twcny.rr.com...
In article <xu-dnXYddKAjzU_YnZ2dnUVZ_qarnZ2d@giganews.com>,
"P.J. Plauger" <pjp@dinkumware.com> wrote:
"Ion Gazta=F1aga" <igaztanaga@gmail.com> wrote in message
news:1171398208.102218.231120@j27g2000cwj.googlegroups.com...
Due to user requests, I reimplemented the list using O(1) size and
O(N) splice but adding the new splice function. I've experimented the
advantage of this new splice when reimplementing "merge" for the list
container, which is typically based on splice(). "merge" can use the
new splice function to achieve the same complexity as the old "merge"
based on non constant-time lists. In many other algorithms I had, it
was possible to know the distance between the nodes, so I had no
performance loss.
But merge splices *entire* lists, so it can know both how many
elements it moves and where the head node lies. As I've pointed
out before, this is one of several overloads of splice that can
(and should) be performed in constant time. It's only when you
splice just part of a list into another that you need to know
the length of what you're moving -- and you *should* know that
it's a safe splice in the bargain. Both operations can be done
at once, in O(N) time.
I can well imagine list::merge taking advantage of
splice-some-from-other. It might look like (untested code follows):
.....
[pjp] At a quick glance, I'd say that your code does just what
our implementation does. The difference is that the "partial
splice with count" function is internal to list, and only gets
called after the iterators have been laundered to avoid granny
knots. Exposing such a function to the outside world, and requiring
that it operate in constant time, is a different kettle of fish,
however. It *forbids* the container from taking the time to ensure
that operations are safe.
I still haven't seen a compelling use case for O(1) "partial
splice", with or without a promised element count.
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]