On Mon, 24 May 2010 11:45:44 -0400, Andrei Alexandrescu
<[email protected]> wrote:
On 05/24/2010 10:23 AM, Steven Schveighoffer wrote:
On Mon, 24 May 2010 10:10:51 -0400, Andrei Alexandrescu
<[email protected]> 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.
I get what you are saying. What I meant was it's moot if you are not
using interfaces. If you don't know what the underlying type is, then you
have to do a runtime check.
I agree it's awkward, and I could have not included length as a member of
Iterator, in which case it would be on all the container types and
NO_LENGTH_SUPPORT would not exist. All containers are meant to have a
valid length, it is only with non-container Iterators that length can be
NO_LENGTH_SUPPORT.
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?
O(n) with n being the number of elements added
Is add expected to put things in a specific place? How does slist
implement back()?
slist does not fit the List interface.
A pointer to the end element would be required for both appending and
back().
-Steve
