www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - dlist for phobos

reply %u <ee ee.com> writes:
Are there plans for including a double linked list in phobos? Maybe
one backed by an array like .NET's List<T> or Java's ArrayList.

If so, when?

Thanks
Jan 26 2011
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, January 26, 2011 15:34:05 %u wrote:

 Are there plans for including a double linked list in phobos? Maybe
 one backed by an array like .NET's List<T> or Java's ArrayList.
 
 If so, when?


Array is the equivalent of Java's ArrayList. It's Java's LinkedList which is a 
doubly-linked list. You don't normally use arrays to implement linked lists. We 
do have a _singly_-linked list - SList - but not doubly-linked list at the 
moment. I'd be stunned if Andrei doesn't intend to add one at some point
though. 
However, std.container was slow in coming, and it's been slow in growing.

- Jonathan M Davis
Jan 26 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/26/11 6:20 PM, Jonathan M Davis wrote:

 On Wednesday, January 26, 2011 15:34:05 %u wrote:

 Are there plans for including a double linked list in phobos? Maybe
 one backed by an array like .NET's List<T>  or Java's ArrayList.

 If so, when?


 Array is the equivalent of Java's ArrayList. It's Java's LinkedList which is a
 doubly-linked list. You don't normally use arrays to implement linked lists. We
 do have a _singly_-linked list - SList - but not doubly-linked list at the
 moment. I'd be stunned if Andrei doesn't intend to add one at some point
though.
 However, std.container was slow in coming, and it's been slow in growing.

 - Jonathan M Davis


One big issue with std.container is that the absence of unified function 
call syntax forces the implementation to add a lot of aliases. I'm sort 
of stalling in hope that language improvements will prompt terser 
container implementations.

I'm also undecided on what to do about sealing, and again language 
improvements (preventing escapes of references) could lead to improved 
designs.

That being said, a doubly-linked list is an obvious candidate as the 
next significant container to put in std.container.


Andrei
Jan 26 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
Andrei:


 I'm also undecided on what to do about sealing, and again language 
 improvements (preventing escapes of references) could lead to improved 
 designs.


Language improvements need to be understood, desired, designed, and then
implemented and debugged, so what kind of syntax and semantics are you thinking
about?

Bye,
bearophile
Jan 27 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/27/11 3:25 AM, bearophile wrote:

 Andrei:


 I'm also undecided on what to do about sealing, and again language
 improvements (preventing escapes of references) could lead to improved
 designs.


 Language improvements need to be understood, desired, designed, and then
implemented and debugged, so what kind of syntax and semantics are you thinking
about?

 Bye,
 bearophile


ref returns should be guaranteed to never escape.

Andrei
Jan 27 2011
parent reply Tomek =?ISO-8859-2?Q?Sowi=F1ski?= <just ask.me> writes:
Andrei Alexandrescu napisa=B3:


 ref returns should be guaranteed to never escape.


Should meaning they're not guaranteed now? I'm curious in what scenarios th=
ey escape.

--=20
Tomek
Jan 27 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/27/11 4:48 PM, Tomek Sowi�ski wrote:

 Andrei Alexandrescu napisa�:


 ref returns should be guaranteed to never escape.


 Should meaning they're not guaranteed now? I'm curious in what scenarios they
escape.


Any function can take the address of a reference (either a ref parameter 
or the result of another function) and squirrel it away.

Andrei
Jan 27 2011
next sibling parent Tomek =?ISO-8859-2?Q?Sowi=F1ski?= <just ask.me> writes:
Andrei Alexandrescu napisa=B3:


 On 1/27/11 4:48 PM, Tomek Sowi=F1ski wrote:

 Andrei Alexandrescu napisa=B3:


 ref returns should be guaranteed to never escape.


 Should meaning they're not guaranteed now? I'm curious in what scenario=




s they escape.

=20
 Any function can take the address of a reference (either a ref parameter=


=20

 or the result of another function) and squirrel it away.


Jeez.. I must've had some brain-warp that I didn't think of &r.front :-)

But is just banning taking addresses of ref parameters and return values go=
ing to solve the problem? Sounds delusively simple...

--=20
Tomek
Jan 27 2011
prev sibling parent Michel Fortin <michel.fortin michelf.com> writes:
On 2011-01-27 17:52:27 -0500, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:


 On 1/27/11 4:48 PM, Tomek Sowiński wrote:

 Andrei Alexandrescu napisał:
 

 ref returns should be guaranteed to never escape.


 
 Should meaning they're not guaranteed now? I'm curious in what 
 scenarios they escape.


 
 Any function can take the address of a reference (either a ref 
 parameter or the result of another function) and squirrel it away.


Even in  safe mode? Being able to take the address of a ref in non-safe 
code seems normal to me.

That said, you don't need to take the address of anything to escape a ref:

	ref int test() {
		int i;
		return pass(i);
	}

	ref int pass(ref int i) {
		return i;
	}

Now, consider that instead of 'int i' you have a container with 
deterministic destruction:

	ref int test() {
		Container!int a;
		return a[0];
	}

Same problem.

-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Jan 27 2011
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 26 Jan 2011 18:34:05 -0500, %u <ee ee.com> wrote:


 Are there plans for including a double linked list in phobos? Maybe
 one backed by an array like .NET's List<T> or Java's ArrayList.

 If so, when?


http://www.dsource.org/projects/dcollections

LinkList there is doubly-linked.

Sorry, I don't have online docs yet for the d2 version... *kicks self*

-Steve
Jan 26 2011