Robert Jacques wrote:
> On Thu, 04 Mar 2010 18:22:55 -0500, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> [snip]
> 
> I like this idea. I've gotten used to using template constraints and ranges when coding which matches this strategy naturally. A lot of the capabilities seem to match ranges, but why did you use different names for some of them?
> removeBack : popBack
> removeFront: popFront
> pushBack   : put
> pushFront  : putFront?
> 

It's intentional. You don't want to use a container as a range by mistake.

Andrei

Sandwich wrote:
> /*Me ends lurking*/
> 
> As far as allocators go, you may want to take a look at how eastl handles them:
> 
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html#eastl_allocator
> 
> /*Resumes Lurking*/

Thanks. Wonder how many other knowledgeable lurkers are out there :o).

Andrei

On 05/03/2010 00:22, Andrei Alexandrescu wrote:
> I want to bring to STL's design are (a) a better categorization of
> containers, (b) of course replace iterators with ranges, (c) either
> eliminate allocators or make them work.

I would like to see : collection update events. The C# C5 library is (afaik) the only container library which implements this very useful feature. (example a database informs connected users about relevant changes to force update the GUI, no need to pull just in case every 5 seconds)

Beside, Implementing update events could be a good reason to give std.pattern a new try...

http://www.itu.dk/research/c5/

> Please speak up - the future of D depends, in small part, on
> this too.
> Andrei

I think it is a big win for the D2 community to have a container library. I.E. porting C++ will be more comfortable.
Bjoern

On 3/5/10 10:44, BLS wrote:
> On 05/03/2010 00:22, Andrei Alexandrescu wrote:
>> I want to bring to STL's design are (a) a better categorization of
>> containers, (b) of course replace iterators with ranges, (c) either
>> eliminate allocators or make them work.
>
> I would like to see : collection update events. The C# C5 library is
> (afaik) the only container library which implements this very useful
> feature. (example a database informs connected users about relevant
> changes to force update the GUI, no need to pull just in case every 5
> seconds)

That looks really nice to have.

> Beside, Implementing update events could be a good reason to give
> std.pattern a new try...
>
> http://www.itu.dk/research/c5/
>
>> Please speak up - the future of D depends, in small part, on
>> this too.
>> Andrei
>
> I think it is a big win for the D2 community to have a container
> library. I.E. porting C++ will be more comfortable.
> Bjoern
>

== Quote from Jacob Carlborg (doob@me.com)'s article
> On 3/5/10 10:44, BLS wrote:
> > On 05/03/2010 00:22, Andrei Alexandrescu wrote:
> >> I want to bring to STL's design are (a) a better categorization of
> >> containers, (b) of course replace iterators with ranges, (c) either
> >> eliminate allocators or make them work.
> >
> > I would like to see : collection update events. The C# C5 library is (afaik) the only container library which implements this very useful feature. (example a database informs connected users about relevant changes to force update the GUI, no need to pull just in case every 5 seconds)
> That looks really nice to have.

It's a nice touch. I hope at least to allow that kind of customization from the outside.

Andrei

On Thu, 04 Mar 2010 18:22:55 -0500, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

>
> Needless to say, I'd be very curious to hear other opinions in this matter. Please speak up - the future of D depends, in small part, on this too.

As you know, you and I disagree on some aspects of containers.  However, I think our philosophies are converging.

Having built a container library, I can tell you the one and only reason I made it have an interface hierarchy -- Tango.  Tango had a container library, which was based on ancient Doug Lea collections, with some added features.  Because I intended dcollections to replace Tango's collections, I tried to encompass the same feature set that it had.  One of those features was the ability to use interfaces without knowing the implementation.  Since then, Tango has replaced their container collection with something different, and guess what -- no more interface hierarchy.  They have a single interface ICollection, and all containers implement that interface.  No Map interface, or List interface or anything.

However, although I think generic containers can avoid *requiring* an interface, if you design your classes well, slapping on an interface costs almost nothing.  It depends on whether you wish to use classes or structs to implement containers.  I still think classes are better, because modifying one aspect of a class is easy to do.  If someone wants to make a new type of HashMap that does everything my HashMap does, except changes one little bit, it's really easy.  With the advent of alias this, it's also possible to do something similar with structs, but not as straightforward, and not without recompiling.  Also, passing containers around by value by default is one of the aspects of STL that I think sucks.  When working with STL, I almost never passed around a container by value, I always used a reference, because passing by value can incur large hidden-allocation costs.

I'll go over a quick set of points that are pro-interface.  First, using an interface hides the implementation.  It may not be possible to have your code on display for the compiler to use.  Using an interface is a perfectly acceptable way to hide proprietary code that you cannot legally divulge.  This is probably the weakest of the points, but I put it out there.  Second, D is a statically compiled language, but with the (hopefully soon) evolution to dynamic linking, using an interface is ideal.  If you for instance wish to pass a map to or from a plugin library, using an interface is probably the best way to do it.  Interfaces are less susceptible to implementation changes/differences.  Third, code that uses an interface is compiled once per interface.  Code that uses duck typing is compiled once per set of arguments.  While this might not seem like much, it can reduce the footprint of generated code.  Using duck typing, you may have two almost identical generated functions that differ only by the function addresses used.  Finally, interfaces simplify understanding.  Once you have used an interface, you know "oh yeah, this is a map, so I can use it like a map."  You can strive to build a container library that follows those principles, even making assertions that force the compiler to prove those principles, but it's not as easy for a person to understand as it is to look at interface documentation and know what it does.  This becomes important when using libraries that use special implementations of containers.  Like for instance a database result or an XML tree.

Interfaces in other languages can be viewed as advantageous in other ways, but D has advanced compile-time interfaces so far that those don't really matter in D.  For example, declaring that a function requires a map container can be done with duck typing via conditional compilation.

At the same time, just like I think ranges don't fit every model (*cough* I/O), interfaces aren't the answer to every aspect of containers.  I don't think ranges fit well with interfaces, because iterating interface ranges prevents inlining -- the major draw of ranges in the first place -- and ranges are so much more useful with value semantics.  I also think functions that can be tuned to each implementation should be.  For this reason, dcollections containers provide a lot of functionality that is not included in the interfaces, simply because the functions are so specific to the implementation, it would be the only class that implemented that interface.  For example, all the functions that return cursors (and soon ranges) are not interface functions.  This doesn't make them useless via interfaces, but you cannot use every aspect of the container via an interface.  An interface is like a common denominator, and I think it should be useful for some purposes.  If nobody will ever use the interface as a parameter to a function, then there is no point in declaring the interface (I realize that I have created such interfaces in dcollections and I plan to correct that -- one nice benefit of the contemplation triggered by this discussion).

I am working on updating dcollections as we post, and I think I have come up with a nifty way to do ranges that will both retain the usefulness of the cursor, and provide a common way to plug the collections into std.algorithm.

Good luck with your containers, I still hold out hope that dcollections can be integrated in Phobos, but I probably need to get it working in order to have any chance of competing :)

-Steve

On 2010-03-05 01:53:32 -0500, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> said:

> Robert Jacques wrote:
>> On Thu, 04 Mar 2010 18:22:55 -0500, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>> [snip]
>> 
>> I like this idea. I've gotten used to using template constraints and ranges when coding which matches this strategy naturally. A lot of the capabilities seem to match ranges, but why did you use different names for some of them?
>> removeBack : popBack
>> removeFront: popFront
>> pushBack   : put
>> pushFront  : putFront?
> 
> It's intentional. You don't want to use a container as a range by mistake.

I agree that "put" has different semantics than "push" so the name should be different, but what's the difference in semantics between "remove" and "pop"? Both remove an element from the subject (range or container). I think they should share the same name.

You say you don't want to mix ranges with containers. But a container somewhat has the same semantics as an input stream: if you remove/pop something form it, it's no longer there for anyone. You decided to implement input streams as ranges, but at the same time you avoid reusing the same interface for containers; isn't that a little contradictory?

Why couldn't a container have the same interface as a range, only with the added ability to push elements into it?

-- 
Michel Fortin
michel.fortin@michelf.com
http://michelf.com/

> Why couldn't a container have the same interface as a range, only with the added ability to push elements into it?
> 

Probably because it would become way too easy to accidentally use the container as a range, which in many cases would end up emptying it when passing it to one of the std algorithms.

- Jonathan M Davis

Steven Schveighoffer wrote:
> On Thu, 04 Mar 2010 18:22:55 -0500, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> 
>>
>> Needless to say, I'd be very curious to hear other opinions in this matter. Please speak up - the future of D depends, in small part, on this too.
> 
> As you know, you and I disagree on some aspects of containers.  However, I think our philosophies are converging.
[snip]

To summarize my understanding of your points:

(a) When you only want to tweak a container's behavior in small ways, inheritance is great.

(b) Pass by reference is more natural for containers than pass by value.

(c) Proprietary code hiding is better with interfaces.

(d) Dynamically-linked code works best with interfaces.

(e) Interface-based code requires less recompilation and may save on generated code.

(f) Interfaces simplify understanding.

At the same time, you argue that ranges aren't fit as interfaces because:

(a) Inlinining is difficult/impossible

(b) Value semantics is more natural for ranges

(c) I didn't understand this because you changed the subject from ranges back to containers:

> I also think functions that can be tuned to each implementation should be.  For this reason, dcollections containers provide a lot of functionality that is not included in the interfaces, simply because the functions are so specific to the implementation, it would be the only class that implemented that interface.  For example, all the functions that return cursors (and soon ranges) are not interface functions.  This doesn't make them useless via interfaces, but you cannot use every aspect of the container via an interface.  An interface is like a common denominator, and I think it should be useful for some purposes.  If nobody will ever use the interface as a parameter to a function, then there is no point in declaring the interface (I realize that I have created such interfaces in dcollections and I plan to correct that -- one nice benefit of the contemplation triggered by this discussion).

One other thing I'm worried about, and was an absolute pain in my preliminary tests of container implementations, is this issue of "iterators/ranges/cursors are not part of the container interface". It is absolutely fundamental that you can get an abstract range from an abstract container because most of what you can do to a container you must do with ranges. Otherwise the duplication of functionality is horrid. This failure alone is a reason to abandon the container hierarchy design.

> I am working on updating dcollections as we post, and I think I have come up with a nifty way to do ranges that will both retain the usefulness of the cursor, and provide a common way to plug the collections into std.algorithm.
> 
> Good luck with your containers, I still hold out hope that dcollections can be integrated in Phobos, but I probably need to get it working in order to have any chance of competing :)

Good luck to you too. As I specified in my private message - if you undo the fundamental mistake of making find()/contains() part of the container (and of course all other disastrous mistakes of that kind), then I'm sure dcollections will be a very solid library.


Andrei

On 2010-03-05 11:32:27 -0500, Jonathan M Davis <jmdavisProg@gmail.com> said:

>> Why couldn't a container have the same interface as a range, only with
>> the added ability to push elements into it?
> 
> Probably because it would become way too easy to accidentally use the
> container as a range, which in many cases would end up emptying it when
> passing it to one of the std algorithms.

Yes, I understand that.

My point is that the problem already exists with ranges: by exposing a stream as a range, you'll empty the stream when iterating over it. If that's acceptable for streams, why is it not for containers?

And perhaps you actually want to empty the container as you iterate over it. If you use your container as a queue, that's what you'll expect. In fact, a stream is just like a queue, and you want algorithms to work on streams don't you?

-- 
Michel Fortin
michel.fortin@michelf.com
http://michelf.com/