Port a benchmark to D?

Steven Schveighoffer schveiguy at yahoo.com
Mon Jun 6 06:37:42 PDT 2011


On Fri, 03 Jun 2011 17:30:54 -0400, Timon Gehr <timon.gehr at gmx.ch> wrote:

> Jonathan M Davis wrote:
>> On 2011-06-03 14:08, Timon Gehr wrote:
>> > Andrei Alexandrescu wrote:
>> > > I noticed that the C++ code uses std::list without there being any  
>> need
>> > > for a linked list structure. See for example the data structure  
>> used in
>> > > FindSet. It's a list, but it's just appended too and then used for  
>> one
>> > > iteration.
>> > >
>> > > Andrei
>> >
>> > Yes, but the list in FindSet is unnecessary anyways. If I start  
>> changing
>> > the original implementation, the first thing I will do is to remove  
>> that.
>> >
>> > First however, I will port the code as closely as possible. Is there  
>> any
>> > associative version of RedBlackTree (I realize it could be made  
>> associative
>> > quite easily), or should I just use built-in hash maps?
>>
>> You give RedBlackTree a different predicate if you want to treat it as  
>> a map.
>> It defaults to "a < b" with allowDuplicates as false, which makes it a
>> multiset.

This makes it a set, not a multiset.  allowDuplicates set to true would  
make it a multiset.


> Yes, thats what I had in mind, but I thought it is strange that there is  
> no
> boilerplate map in std.container.

I think the goal is to eventually have these higher-level types based on  
the implementation types, but I'm uncertain how they will look or where  
they will go.  Almost certainly, there will be a template based on a  
set-like template for defining a map (e.g. map!(RedBlackTree, int, int) ).

If you want a cookie-cutter map type that uses the exact same  
implementation as RedBlackTree, with a custom allocator that helps with  
performance for long-lasting containers, dcollections provides such a type  
(TreeMap).  If you do end up using it, I recommend the latest trunk, I've  
made some critical bug fixes (I need to release soon...).

-Steve


More information about the Digitalmars-d mailing list