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.
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 :) 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.
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 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.
I don't know of a word for "hierarchy with interfaces as root and inner
nodes and classes as leaf nodes" so I just call that class hierarchy.
I view them as classes with interfaces tacked on because the
implementations are similar :)
-Steve
