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?

> 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.

> 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?

> 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. 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.

>>>> OTish: What are your thoughts on a bimap implementation and a
>>>> child/sibling or general tree implementation as part of
>>>> dcollections?
>>>
>>> I haven't the slightest what a bimap is :) I am not an expert in
>>> collections or data structures, I just reimplement things I have
>>> understood. My implementations are basically copied from my
>>> algorithm book, and refined as much as I can do.
>>>
>>> That being said, if you have any implementation of a tree or hash, it
>>> should be easy to insert into dcollections. If you have ideas for
>>> other collection types (i.e. other than Map, Set, Multiset or List),
>>> then I can look into that if you point me at an implementation or
>>> have one of your own. I purposefully left out multi-map because I've
>>> never had a huge use for it, and it seemed like a awkward thing to
>>> create an interface for...
>>
>> Tries of various kinds come up again and again. I don't think
>> dcollections' current abstractions capture them, which further
>> supports my point that containers have too much personality to be
>> caught in the straitjacket of class hierarchies.
>
> I am not familiar with tries, and dcollections has no class hierarchy.

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.


Andrei

On Fri, 21 May 2010 13:42:14 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> On 05/19/2010 08:42 PM, Steven Schveighoffer wrote:
>> Andrei Alexandrescu Wrote:
>>
>>
>> I.e. there aren't many
>> kinds of HashMaps that derive from each other.  But the interfaces
>> are not detrimental to your ideas.  The only thing interfaces require
>> is that the entities implementing them are classes and not structs.
>> As long as you agree that classes are the right call, then interfaces
>> can co-exist with your other suggestions without interference.
>
> This brings back a discussion I had with Walter a while ago, with echoes in the newsgroup. Basically the conclusion was as follows: if a container never escapes the addresses of its elements, it can manage its own storage. That forces, however, the container to be a struct because copying references to a class container would break that encapsulation. I called those "perfectly encapsulated containers" and I think they are good candidates for manual memory management because they tend to deal in relatively large chunks.
>
> I noticed that your collections return things by value, so they are good candidates for perfect encapsulation.

Then you need reference counting, I don't think that is a good design.

>
>> Yes, if you want to define "this function needs something that is
>> both addable and purgeable, I don't have an interface for that.  But
>> a concept can certainly define that generically (which is what you
>> want anyways), or you could just say "I need a List" and get those
>> functions also.  It also does not force entities other than
>> dcollections objects to be classes, they could be structs and
>> implement the correct concepts.
>>
>> I myself don't really use the interface aspect of the classes, it is
>> mostly a carryover from the Java/Tango inspirations.
>
> I don't know Tango, but Java's containers are a terrible example to follow. Java's container library is a ill-advised design on top of an underpowered language, patched later with some half-understood seeming of genericity. I think Java containers are a huge disservice to the programming community because they foster bad design.

Java has some warts as you have rightfully pointed out in the past (i.e. O(n) lookup), but I have attempted to remove all those warts.  Dcollections I would hope does not suffer from the problems that Java's collections suffer from.

>
>> But I can see
>> one good reason to keep them -- binary interoperability.  For
>> example, it might be the case some day when D has good support with
>> dynamic libraries that a library exposes some piece of itself as a
>> Map or List interface.
>
> I need to disagree with that. I've done and I do a ton of binary interoperability stuff. You never expose a generic container interface! Interoperable objects always embody high-level logic that is specific to the application. They might use containers inside, but they invariably expose high-level, application-specific functionality.

It's done all the time in Java and .NET.  For example, A GUI listbox widget exposes its elements as an array of elements, which implement the List interface.  You don't ever see the implementation or need it.  Granted Java and .NET have less problems than C++ and D with binary compatibility, since the function tables are dynamic, but the potential is there for D to make binary compatibility possible with interfaces.

In the past I have built a C++ library that abstracted features of the OS.  My goal was to make it possible to dynamically load a module that abstracted things like setting the IP address of a network interface.  My modules used std::string instead of char * to lookup services to get objects that implement the interface.  Big mistake.  On a later version of the standard C++ runtime, the private implementation of std::string changed, so the dynamically loaded libraries crashed horribly.  No change in string's interface, just the private stuff changed, but because it's a template, the code that uses it necessarily has to be aware of it.  We ended up ditching the standard C++ library's version of string, and used STLPort so we could control the library.

I envision this same sort of problem would be likely with D collection objects that were not used via interfaces.

>
>> So my answer is -- go ahead and define these concepts and required
>> names, and you can ignore the interfaces if they don't interest you.
>> They do not subtract from the possibilities, and others may find good
>> use for them.
>>
>> Does that make sense?
>
> I understand I could ignore the interfaces and call it a day, but it seems that at this point we are both convinced they are not quite good at anything: you only put them in because you suffered the Stockholm syndrome with Java, and I hate them with a passion.

The reason I put them in is because they existed before, but thinking about what they would be useful for, D doesn't really support dynamic libraries all that well (recent advances have brought that closer).  But once it does, I think it will be much more important to keep compiled libraries compatible between versions of the standard library.  This is typically not possible with templates, I know C++ is horrible at it from personal experience.

So I'm not convinced it is not quite good at anything.  I think it's a solution to a problem that doesn't exist yet on D because D's linking features are stuck in 1995.

>
> Why would we keep in the standard library bad design with the advice that "if you don't like it ignore it"?

People have continuously used that argument against const and immutable.  Really that argument is fine, as long as you don't consider it bad design, which I don't :)

-Steve

On 05/24/2010 06:54 AM, Steven Schveighoffer wrote:
> I am not familiar with tries,

Missed that upon the first read. I suggest you look at tries and the following other structures as good examples that it's futile to fit collections into hierarchies.

http://en.wikipedia.org/wiki/Trie
http://linux.thai.net/~thep/datrie/datrie.html
http://en.wikipedia.org/wiki/Suffix_tree
http://en.wikipedia.org/wiki/Kd-tree

We'd want to implement in time those and many more in Phobos without worrying that some of their primitives won't fit the existing interfaces, and also without the unjustified effort of formalizing interfaces for each of them in thinking that another very, very similar container will come along.


Andrei

On Mon, 24 May 2010 10:10:51 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@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

On Mon, 24 May 2010 11:21:20 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> On 05/24/2010 06:54 AM, Steven Schveighoffer wrote:
>> I am not familiar with tries,
>
> Missed that upon the first read. I suggest you look at tries and the following other structures as good examples that it's futile to fit collections into hierarchies.
>
> http://en.wikipedia.org/wiki/Trie
> http://linux.thai.net/~thep/datrie/datrie.html
> http://en.wikipedia.org/wiki/Suffix_tree
> http://en.wikipedia.org/wiki/Kd-tree
>
> We'd want to implement in time those and many more in Phobos without worrying that some of their primitives won't fit the existing interfaces, and also without the unjustified effort of formalizing interfaces for each of them in thinking that another very, very similar container will come along.
>

From a cursory look, I don't see why tries would not be possible in dcollections.

I'd probably start with something like this:

class TrieMap(K, V) : Map!(K[], V)

The array brackets enforce the ability to use prefixes on the keys.

-Stvee

On Fri, 21 May 2010 22:56:54 -0400, Vladimir Panteleev <vladimir@thecybershadow.net> wrote:

> On Thu, 20 May 2010 04:42:35 +0300, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>
>> interfaces
>
> Does that imply that the most important methods are virtual?
>
> If so, say good-bye to inlining, and hello to an additional level of dereferencing.
>
> Without meaning any disrespect to all the work you did, allow me to say that I won't use a library that could be faster (without making usage too clumsy), but isn't. (I prefer my D programs to be as fast as reasonably possible - if I didn't care about speed, I'd use another language.) For the same reasons, I'd be disappointed if the library was admitted as-is into Phobos, since it doesn't live up to my personal ideal of what D should be.

With the future update that all the classes are final, then they are not virtual as long as you don't use the interfaces.

-Steve

On 05/24/2010 10:23 AM, Steven Schveighoffer wrote:
> On Mon, 24 May 2010 10:10:51 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail@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

On 05/24/2010 10:01 AM, Steven Schveighoffer wrote:
> On Fri, 21 May 2010 13:42:14 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org> wrote:
>
>> On 05/19/2010 08:42 PM, Steven Schveighoffer wrote:
>>> Andrei Alexandrescu Wrote:
>>>
>>>
>>> I.e. there aren't many kinds of HashMaps that derive from each
>>> other. But the interfaces are not detrimental to your ideas. The
>>> only thing interfaces require is that the entities implementing
>>> them are classes and not structs. As long as you agree that
>>> classes are the right call, then interfaces can co-exist with
>>> your other suggestions without interference.
>>
>> This brings back a discussion I had with Walter a while ago, with
>> echoes in the newsgroup. Basically the conclusion was as follows:
>> if a container never escapes the addresses of its elements, it can
>> manage its own storage. That forces, however, the container to be a
>> struct because copying references to a class container would break
>> that encapsulation. I called those "perfectly encapsulated
>> containers" and I think they are good candidates for manual memory
>> management because they tend to deal in relatively large chunks.
>>
>> I noticed that your collections return things by value, so they are
>>  good candidates for perfect encapsulation.
>
> Then you need reference counting, I don't think that is a good
> design.

Why?

I think refcounting for containers is perfect.

Refcounting small objects is bad because the counter overhead is large.
Also, small objects tend to be created and passed around a lot, so the
time overhead is significant.

In contrast, refcounting and containers are a perfect marriage. The
container is a relatively large conglomerate of objects so refcounting
that is bound to yield good benefits in terms of memory reclamation.

>>> Yes, if you want to define "this function needs something that
>>> is both addable and purgeable, I don't have an interface for
>>> that. But a concept can certainly define that generically (which
>>> is what you want anyways), or you could just say "I need a List"
>>> and get those functions also. It also does not force entities
>>> other than dcollections objects to be classes, they could be
>>> structs and implement the correct concepts.
>>>
>>> I myself don't really use the interface aspect of the classes, it
>>> is mostly a carryover from the Java/Tango inspirations.
>>
>> I don't know Tango, but Java's containers are a terrible example to
>>  follow. Java's container library is a ill-advised design on top of
>> an underpowered language, patched later with some half-understood
>> seeming of genericity. I think Java containers are a huge
>> disservice to the programming community because they foster bad
>> design.
>
> Java has some warts as you have rightfully pointed out in the past
> (i.e. O(n) lookup), but I have attempted to remove all those warts.
> Dcollections I would hope does not suffer from the problems that
> Java's collections suffer from.

That's great. But let me quote what you said: "I myself don't really use
the interface aspect of the classes, it is mostly a carryover from the
Java/Tango inspirations." I took that to mean you don't have a strong
justification for structuring dcollections as a hierarchy, and
furthermore that makes me hope it's possible you'd be willing to yank
that dinosaur brain.

>>> But I can see one good reason to keep them -- binary
>>> interoperability. For example, it might be the case some day when
>>> D has good support with dynamic libraries that a library exposes
>>> some piece of itself as a Map or List interface.
>>
>> I need to disagree with that. I've done and I do a ton of binary
>> interoperability stuff. You never expose a generic container
>> interface! Interoperable objects always embody high-level logic
>> that is specific to the application. They might use containers
>> inside, but they invariably expose high-level, application-specific
>> functionality.
>
> It's done all the time in Java and .NET. For example, A GUI listbox
> widget exposes its elements as an array of elements, which implement
> the List interface. You don't ever see the implementation or need it.
>  Granted Java and .NET have less problems than C++ and D with binary
>  compatibility, since the function tables are dynamic, but the
> potential is there for D to make binary compatibility possible with
> interfaces.

I see.

> In the past I have built a C++ library that abstracted features of
> the OS. My goal was to make it possible to dynamically load a module
> that abstracted things like setting the IP address of a network
> interface. My modules used std::string instead of char * to lookup
> services to get objects that implement the interface. Big mistake. On
> a later version of the standard C++ runtime, the private
> implementation of std::string changed, so the dynamically loaded
> libraries crashed horribly. No change in string's interface, just the
> private stuff changed, but because it's a template, the code that
> uses it necessarily has to be aware of it. We ended up ditching the
> standard C++ library's version of string, and used STLPort so we
> could control the library.
>
> I envision this same sort of problem would be likely with D
> collection objects that were not used via interfaces.

I see no problem retrofitting a no-interface container into a formal
interface if so needed.

>>> So my answer is -- go ahead and define these concepts and
>>> required names, and you can ignore the interfaces if they don't
>>> interest you. They do not subtract from the possibilities, and
>>> others may find good use for them.
>>>
>>> Does that make sense?
>>
>> I understand I could ignore the interfaces and call it a day, but
>> it seems that at this point we are both convinced they are not
>> quite good at anything: you only put them in because you suffered
>> the Stockholm syndrome with Java, and I hate them with a passion.
>
> The reason I put them in is because they existed before, but thinking
>  about what they would be useful for, D doesn't really support
> dynamic libraries all that well (recent advances have brought that
> closer). But once it does, I think it will be much more important to
> keep compiled libraries compatible between versions of the standard
> library. This is typically not possible with templates, I know C++ is
> horrible at it from personal experience. So I'm not convinced it is
> not quite good at anything. I think it's a solution to a problem that
> doesn't exist yet on D because D's linking features are stuck in
> 1995.

Clearly interfaces have their advantages. I just happen to think they
are much thinner than their disadvantages for this particular case.

>> Why would we keep in the standard library bad design with the
>> advice that "if you don't like it ignore it"?
>
> People have continuously used that argument against const and
> immutable. Really that argument is fine, as long as you don't
> consider it bad design, which I don't :)

Looks like we're heading straight to stalemate once again.

In the interest of time, it would be better to get to stalemate (or, hopefully, agreement) so we know whether dcollections will be integrated within Phobos or whether I should spend this and next weeks' evenings coding. To that end, please let me know whether it's worth that I spend time on putting together a list of proposed changes.


Andrei

On 05/24/2010 10:39 AM, Steven Schveighoffer wrote:
> On Mon, 24 May 2010 11:21:20 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org> wrote:
>
>> On 05/24/2010 06:54 AM, Steven Schveighoffer wrote:
>>> I am not familiar with tries,
>>
>> Missed that upon the first read. I suggest you look at tries and the
>> following other structures as good examples that it's futile to fit
>> collections into hierarchies.
>>
>> http://en.wikipedia.org/wiki/Trie
>> http://linux.thai.net/~thep/datrie/datrie.html
>> http://en.wikipedia.org/wiki/Suffix_tree
>> http://en.wikipedia.org/wiki/Kd-tree
>>
>> We'd want to implement in time those and many more in Phobos without
>> worrying that some of their primitives won't fit the existing
>> interfaces, and also without the unjustified effort of formalizing
>> interfaces for each of them in thinking that another very, very
>> similar container will come along.
>>
>
>  From a cursory look, I don't see why tries would not be possible in
> dcollections.
>
> I'd probably start with something like this:
>
> class TrieMap(K, V) : Map!(K[], V)
>
> The array brackets enforce the ability to use prefixes on the keys.

The key point of tries is that they have distributed storage. Thus, shoehorning them into the interface function

Iterator!(K[]) keys();

forces allocation and copying.


Andrei

On Mon, 24 May 2010 08:06:29 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
> On Thu, 20 May 2010 12:46:59 -0400, Robert Jacques <sandford@jhu.edu> wrote:
>
>> On Thu, 20 May 2010 06:34:42 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
[snip]
>>>
>>> I understand these points, but I'm already using interfaces to copy data between containers.  I don't have to, I could have used generic code, but this way, only one function is instantiated to copy data from all the other containers.  The problem with using generic code is that the compiler will needlessly duplicate functions that are identical.
>>
>> This sounds like a failure of design. Why aren't you using ranges to do this?
>
> Why are ranges necessarily better?  I'm using the container's opApply, which I'd probably still use even if there were no interfaces.  opApply allows much more possibilities in traversal than ranges which cannot use stack recursion without heap activity.

Ranges are not necessarily better and may have some minor amount of overhead over a well optimized opApply. Then again, the opposite may be true. The point is that if the difference between opApply and a range is more than trivial, you've probably had a failure of design occur. Honestly, I'm having trouble thinking of a container which allows stack recursion for transversal and doesn't have an efficient range/loop variant. For that matter, a range using heap activity is also a clear indication of a design failure.

>>
>>> Using interfaces is not as viral as you think.  My interfaces can be used in generic code, as long as the generic code uses functions in the interfaces.  If a library returns an interface, the author is saying "I don't want you using any functions outside this interface," so why is that a bad thing?
>>
>> Well, needlessly duplicated functions for one. :) More importantly, the example I gave was about third party libraries which I have no control over. So this solution explicitly doesn't work. And even if everyone used templates everywhere in order to be compatible with both interfaces and classes, isn't that a viral effect of having both?
>
> If a 3rd party library uses interfaces, it's probably for good reason.  They most likely want to remain binary compatible with other libs, and/or want to abstract the implementation of some custom container type.  If you don't like their requirements, don't use the library.
>
> -Steve

No, if a 3rd party library _needs_ to use interfaces it's probably for a good reason. The problem is, if they exist, people are going to use them even if they don't need them. Which therein lies the problem.