GSoC-2011 project:: Containers

[Jonathan M Davis]

On 2011-03-30 09:18, Emil Madsen wrote:
> On 30 March 2011 10:38, Jonathan M Davis <jmdavisProg at gmx.com> wrote:
> > On 2011-03-30 01:18, Daniel Gibson wrote:
> > > Am 30.03.2011 01:55, schrieb Jonathan M Davis:
> > > > On 2011-03-29 14:50, dsimcha wrote:
> > > >> == Quote from Jonathan M Davis (jmdavisProg at gmx.com)'s article
> > > >> 
> > > >>> The fancier stuff would be nice, but we don't even have a
> > 
> > doubly-linked
> > 
> > > >>> list yet. We should get the simpler stuff sorted out before we get
> > > >>> particularly fancy, not to mention that it's usually the simple
> > > >>> stuff that gets heavily used.
> > > >> 
> > > >> For the most part I agree, but a doubly linked list might be **too**
> > > >> simple. Linked lists are so trivial to implement that I'd tend to
> > > >> roll my own that does exactly what I need with regard additional
> > > >> behavior
> > 
> > on
> > 
> > > >> insertion, etc. rather than wrapping a library solution to get these
> > > >> features.
> > > > 
> > > > A doubly-linked list is on the list of containers that every standard
> > > > library should have or it's likely to be considered lacking. I can
> > > > understand rolling your own for specific uses, but _I_ sure don't
> > > > want to be doing that if I don't have to. If I want a doubly-linked
> > > > list, I want to be able to just create a standard one and use it.
> > > > C++, C#, and Java all have doubly-linked lists in their standard
> > > > libraries.
> > > > 
> > > > If no one else ever implements a doubly-linked list for Phobos, I'll
> > > > probably do it eventually simply because it's one of the containers
> > 
> > that
> > 
> > > > is on the short list of containers that pretty much every standard
> > > > library has.
> > > > 
> > > > - Jonathan M Davis
> > > 
> > > It may be feasible to enhance the single-linked list to support both
> > > single- and double linking, via an additional template-parameter "bool
> > > doubly" or something like that and some static-ifs in the
> > > implementation. I once created a simple single/double-linked queue for
> > > D1 like that.
> > 
> > To what end though? I don't think that that would save you much. While
> > some of
> > the implementation would be the same, so much of it would be different,
> > that
> > you'd practically have two complete types defined in one template. At
> > that point, you might as well create a separate class/struct. It's just
> > simpler to
> > have them separate, and I don't see any real gain in combining them.
> > Having both is great, since there are times that you want one and times
> > when you want
> > the other, but having both SList and DList (or whatever it would be
> > called) as
> > separate types makes sense.
> > 
> > - Jonathan M Davis
> 
> Just a question that popped into my mind, how does D's std.container handle
> cyclic lists? using static if?

And how would it get a cyclic list? The only linked list of any kind at the 
moment is SList, which is a singly-linked list. It only has elements in it 
where you inserted them. There's no way to tell it to insert anything 
cyclically. Sure, a cyclical list container could be implemented, but none 
such exists at the moment. std.container is one of the newer modules in Phobos 
and is still pretty sparse.

- Jonathan M Davis