www.digitalmars.com         C & C++   DMDScript  

D - Template Library

reply "Craig Black" <cblack ara.com> writes:
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
Mar 29 2004
next sibling parent Brad Anderson <brad sankaty.dot.com> writes:
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
Mar 29 2004
prev sibling parent reply Stewart Gordon <smjg_1998 yahoo.com> writes:
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.
Mar 30 2004
parent reply "Craig Black" <cblack ara.com> writes:
 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
Apr 01 2004
next sibling parent Ilya Minkov <minkov cs.tum.edu> writes:
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
Apr 01 2004
prev sibling next sibling parent J Anderson <REMOVEanderson badmama.com.au> writes:
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/
Apr 01 2004
prev sibling parent reply Stewart Gordon <smjg_1998 yahoo.com> writes:
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.
Apr 01 2004
parent reply J Anderson <REMOVEanderson badmama.com.au> writes:
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/
Apr 01 2004
next sibling parent reply "Craig Black" <cblack ara.com> writes:
 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
Apr 01 2004
parent J Anderson <REMOVEanderson badmama.com.au> writes:
Craig Black wrote:


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




BTW: I can't remember exactly what big W said so take that with a grain 
of salt.

There's also a capacity thing in gcx.d that get's the capacity of a 
pointer but I don't think this is accessible.


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.
  


Maybe but I think it depends on the application.  If you know your 
application though you can almost always write a better scheme manually.

I don't think D should do this directly (D needs to keep to the metal). 
I think it should be done as part of the library (as you've suggested).  
But it seems more like a boost thing then an std thing.  I guess the lib 
would come with a range of pre-defined allocators that can be plugged in.

-- 
-Anderson: http://badmama.com.au/~anderson/
Apr 02 2004
prev sibling parent Stewart Gordon <smjg_1998 yahoo.com> writes:
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.
Apr 02 2004