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