Re: "Fixing" the O(1) splice / O(1) size std::list problem?
"Ion Gazta?aga" <igaztanaga@gmail.com> wrote in message
news:1171398208.102218.231120@j27g2000cwj.googlegroups.com...
Howard Hinnant wrote:
[snip]
Imho the current status quo is the worst possible outcome.
The best would be one of:
1. Require O(1) size().
2. Remove list::size().
An O(n) size() is nothing but a trap waiting to catch the next
programmer, expert or not. Not having it at all would be far higher
quality than having it, and having it be O(n). If list::size() didn't
exist, and you needed that information, std::distance(l.begin(),
l.end()) is neither difficult, nor error prone.
In my experience implementing containers (for Boost.Interprocess) I
started modifying the SGI STL implementation (which has O(N) size and
O(1) splice), I think that option 1 is the correct, because:
1. Every other STL container (deque, vector, map/set...) in every
implementation I know has constant-time size(). Users expect O(1)
size.
2. The standard avoids defining inefficient functions, like operator[]
for lists, which would be also O(N)
3. The new splice function you propose (the one that takes the
distance) can make many O(N) splice operations O(1).
4. I think that usually size() is called many more times than
splice().
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.
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 ]