If I recall correctly, D has had templates for a number of months now.  Are D templates usable yet?  Is there standard container/collection library for D like the Standard Template Library for C++?  If so, what is currently available?  I'm looking for things like linked-lists, autosizing arrays like std::vector, binary-tree-based containers like std::set, and hash tables.

Thanks,

Craig

Craig Black wrote:
> If I recall correctly, D has had templates for a number of months now.  Are
> D templates usable yet?  Is there standard container/collection library for
> D like the Standard Template Library for C++?  If so, what is currently
> available?  I'm looking for things like linked-lists, autosizing arrays like
> std::vector, binary-tree-based containers like std::set, and hash tables.
> 
> Thanks,
> 
> Craig
> 
> 

Search the NG for DTL - Matthew Wilson is running his lib by Walter right now.  Should see it soon.

BA

Craig Black wrote:

> If I recall correctly, D has had templates for a number of months now.  Are D templates usable yet?

Yes. I've used them, for instance.

> Is there standard container/collection library for D like the Standard Template Library for C++?  If so, what is currently available?  I'm looking for things like linked-lists, autosizing arrays like std::vector,

How would this be an improvement over D's built-in dynamic arrays?

> binary-tree-based containers like std::set, and hash tables.

Any particular improvements you're looking for over D's built-in associative arrays?  But do see (if you haven't already) my version at
http://smjg.port5.com/pr/d/

Stewart.

-- 
My e-mail is valid but not my primary mailbox, aside from its being the unfortunate victim of intensive mail-bombing at the moment.  Please keep replies on the 'group where everyone may benefit.

> > Is there standard container/collection library for D like the Standard Template Library for C++?  If so, what is currently available?  I'm looking for things like linked-lists, autosizing arrays like std::vector,
>
> How would this be an improvement over D's built-in dynamic arrays?

D arrays optimized for adding single elements as std::vector is? std::vector is optimized so that it doesn't have to resize every time you add a single element. The last time I researched this a few months ago D arrays did not have this property.  Perhaps the situation has changed.  It's a really nice feature.

>
> > binary-tree-based containers like std::set, and hash tables.
>
> Any particular improvements you're looking for over D's built-in associative arrays?

Correct me if I'm wrong. Last I heard, D associative arrays work only with char[] type, so they lack the flexibility provided by a generic class.

>  But do see (if you haven't already) my version at
> http://smjg.port5.com/pr/d/

Cool!  Keep up the good work, Stewart!  Perhaps Walter will add an official template library to D so that we can all contribute to a common library.

Craig

Craig Black schrieb:

> D arrays optimized for adding single elements as std::vector is?
> std::vector is optimized so that it doesn't have to resize every time you
> add a single element. The last time I researched this a few months ago D
> arrays did not have this property.  Perhaps the situation has changed.  It's
> a really nice feature.

I recall there were plans to mark "ownership" of an array with a bit within the length field. Something like a simple reference counting. And if there is only one owner, the array can be resized using realloc, and is preallocated with power-of-2 size, IIRC. Burton was planning to make it in his experimental compiler, but he didn't. I don't know whether DMD has this feature or has it been considered at all. But for the future, it is an option.

-eye

Craig Black wrote:

>Correct me if I'm wrong. Last I heard, D associative arrays work only with
>char[] type, so they lack the flexibility provided by a generic class.
>  
>

This is wrong.  D's associative arrays can be used with class objects.

>> But do see (if you haven't already) my version at
>>http://smjg.port5.com/pr/d/
>>    
>>
>
>Cool!  Keep up the good work, Stewart!  Perhaps Walter will add an official
>template library to D so that we can all contribute to a common library.
>
>Craig
>
I think it will probably be Mathews DTL.

-- 
-Anderson: http://badmama.com.au/~anderson/

Craig Black wrote:

<snip>
>> How would this be an improvement over D's built-in dynamic arrays?
> 
> D arrays optimized for adding single elements as std::vector is?

Yes, implementation permitting.

> std::vector is optimized so that it doesn't have to resize every time you
> add a single element. The last time I researched this a few months ago D
> arrays did not have this property.

I don't think D arrays have any implementation specifics set in stone. Besides (possibly) the elements being contiguous in memory.  In which case, it's perfectly valid for an implementation to set aside some growing space.

IRHS you can already create some growing space yourself (again, this would be implementation dependent):

	int[] qwert;
	qwert.length = 100;
	qwert.length = 0;

<snip>
> Correct me if I'm wrong. Last I heard, D associative arrays work only with
> char[] type, so they lack the flexibility provided by a generic class.
<snip>

I've had no problem using it with an integer type.  This is indeed how my hash map template is implemented.

Besides, if D associative arrays were only supposed to work with char[], chances are the declaration syntax would have omitted the key type altogether.

Stewart.

-- 
My e-mail is valid but not my primary mailbox, aside from its being the unfortunate victim of intensive mail-bombing at the moment.  Please keep replies on the 'group where everyone may benefit.

Stewart Gordon wrote:

>> add a single element. The last time I researched this a few months ago D
>> arrays did not have this property.
>
> std::vector is optimized so that it doesn't have to resize every time you
>
> I don't think D arrays have any implementation specifics set in stone. Besides (possibly) the elements being contiguous in memory.  In which case, it's perfectly valid for an implementation to set aside some growing space.

Walter did mention something about the GC allocating double the required memory. 

There may be some good reasons for an vector class that allows you to provide your own allocator. Personally I'd have little use for such a thing (I always use the default allocator in C++).

-- 
-Anderson: http://badmama.com.au/~anderson/

> Walter did mention something about the GC allocating double the required memory.

I don't believe that std::vector just doubles the size.  If you observe the growth rate of std::vector as you add elements, it increases each time by a certain percentage, say 30% or so.  Personally this more conservative approach is more attractive to me.  It wastes less memory and still maintains decent performance.

> There may be some good reasons for an vector class that allows you to provide your own allocator. Personally I'd have little use for such a thing (I always use the default allocator in C++).

Yeah, me neither.  I'm sure the customizable allocator feature was useful for somebody, but I never got into it.  Too much work, requires a lot of research to find out the best allocation algorithm.  Better if someone else does this for me.

Craig

J Anderson wrote:

> Stewart Gordon wrote:
<snip>
>> I don't think D arrays have any implementation specifics set in stone. Besides (possibly) the elements being contiguous in memory.  In which case, it's perfectly valid for an implementation to set aside some growing space.
> 
> Walter did mention something about the GC allocating double the required memory.
<snip>

Can it reduce this factor if there isn't enough spare memory to double the capacity?  Further, can a GC pass reduce the growing capacity of an already allocated array?

Stewart.

-- 
My e-mail is valid but not my primary mailbox, aside from its being the unfortunate victim of intensive mail-bombing at the moment.  Please keep replies on the 'group where everyone may benefit.