On 05/24/2010 10:23 AM, Steven Schveighoffer wrote:
On Mon, 24 May 2010 10:10:51 -0400, Andrei Alexandrescu
<seewebsiteforem...@erdani.org> wrote:
On 05/24/2010 06:54 AM, Steven Schveighoffer wrote:
length is allowed to return NO_LENGTH_SUPPORT if O(1) length isn't
possible,
Do you agree that's an awkwardness?
Yes, at that point it's an optimization. The only place where I assume
length could be invalid is when working with the Iterator!V type, which
might not be a dcollections object.
That doesn't matter. Since you define NO_LENGTH_SUPPORT and you have
interfaces, the door is ajar forever. Client code can't write this:
auto total = cont1.length + cont2.length;
because that is incorrect code (that compiles, runs, and produces some
odd result).
So don't take it lightly. NO_LENGTH_SUPPORT means no length support.
Then pretending it's supported will only harm everyone.
but all dcollections define length.
I was hoping we're on the verge of agreeing to yank all interfaces and
let the collection roam free. If that's a possibility, then your
design isn't constrained to define length anymore unless in can.
I agree, removing all the interfaces would get rid of the need for
NO_LENGTH_SUPPORT. But all dcollections define a valid length, so that
point is kinda moot :)
Not moot because you have interfaces.
However, supporting non-length containers via
generic programming vs. interfaces would be much smoother.
In that case, you can do
coll.begin.empty to determine if the collection has any elements.
Then why not make length optional and define empty? From the above it
looks like an obviously better design.
But all dcollections are bi-directional anyways, there is no singly
linked list. That was a decision I made early on, because it allows more
assumptions about dcollections' containers. I think length-less singly
linked lists would be a good addition to phobos that are not part of the
collection hierarchy, they are almost on par with builtin arrays as
being so simple.
Do you see dcollections' inability to express slists as a problem?
I don't see them as unable to express slists. They would break the
design guidelines that I set for collections being iterable in both
directions, but an slist fits fine within the List interface.
What's the required complexity of concat? Is add expected to put things
in a specific place? How does slist implement back()?
slist does not fit the List interface.
And singly linked vs. doubly linked does not make any difference whether
O(1) length is possible or not. As you say, it's O(1) splicing or O(1)
length, regardless of single or double links.
I disagree with your assessment that length is a less used operation
than splicing. I think I have never used splicing with std::list. C++'s
default is O(1) length, and I followed that design.
I didn't assess that.
I felt like you did. Your statement was: "It works against splicing (an
important list primitive) and most of the time you don't need it so why
waste time updating it."
While you didn't specifically say it was used more, you mentioned the
importance of splicing, and the non-importance of length. I guess I
should have said, I disagree that splicing is more important than
caching length.
My main point was that if one defines an slist, in many cases one
defines it to be very small, simple, and cheap. Maintaining size will
come on the radar and would discourage the use of the abstraction in
favor of a hand-rolled implementation. This is failure to abstract.
All dcollections own their elements, it is not like an array, where
there can be multiple references to subsets of the data. An slist would
simply be an slist as you describe with a slightly bigger head. In other
words, the head node has the length cache and allocator, and object
monitor, and whatever else you need for the whole list. The nodes
themselves would be a simple element and pointer. But the elements are
never exposed except via ranges and cursors. The ranges and cursors
cannot affect the topology of the list, you need the head "owner" node
to do that.
I understand. The problem is when you many such lists or when you
manipulate a few intensively.
I look at it this way, dcollections are "good enough" for most uses, if
you need highly tailored data structures with specific uses in mind, you
can make those on your own.
For example, dcollections' LinkList can easily take the place of a
simple slist. It may not be as fast with your specific requirements in
mind, but it works. The benefit is, it works like all the other
collection types and it's easy to learn all of them together because
they all have certain properties.
That's what STL said about slists. Next thing you know... forward_list
is being standardized.
Andrei
