Thread overview
Type sequence concatenation / associative array implementation
6 days ago
Marcel
6 days ago
user1234
6 days ago
H. S. Teoh
6 days ago
Paul Backus
6 days ago
Hello!
I have two questions:

1- How can I concatenate two type sequences?

2- How is the builtin associative array implemented? I think I read somewhere it's implemented like C++'s std::unordered_map but with BSTs instead of DLists for handling collisions: is this correct?
6 days ago
On Wednesday, 12 February 2020 at 20:58:49 UTC, Marcel wrote:
> Hello!
> I have two questions:
>
> 1- How can I concatenate two type sequences?

alias Concatenated = AliasSeq!(TList1, TList2);

or maybe

alias Concatenated = AliasSeq!(TList1[0..$], TList2[0..$]);

since I don't remember if they nest or not.

> 2- How is the builtin associative array implemented? I think I read somewhere it's implemented like C++'s std::unordered_map but with BSTs instead of DLists for handling collisions: is this correct?

see druntime source.


6 days ago
On Wed, Feb 12, 2020 at 09:05:22PM +0000, user1234 via Digitalmars-d-learn wrote:
> On Wednesday, 12 February 2020 at 20:58:49 UTC, Marcel wrote:
> > Hello!
> > I have two questions:
> > 
> > 1- How can I concatenate two type sequences?
> 
> alias Concatenated = AliasSeq!(TList1, TList2);
[...]

This is correct. They always auto-expand, and thus do not nest.


T

-- 
Let X be the set not defined by this sentence...
6 days ago
On Wednesday, 12 February 2020 at 20:58:49 UTC, Marcel wrote:
> 2- How is the builtin associative array implemented? I think I read somewhere it's implemented like C++'s std::unordered_map but with BSTs instead of DLists for handling collisions: is this correct?

It's an open-addressed hash table. If you want to see all the details, the source is here:

https://github.com/dlang/druntime/blob/v2.090.1/src/rt/aaA.d
5 days ago
On 2/12/20 5:47 PM, Paul Backus wrote:
> On Wednesday, 12 February 2020 at 20:58:49 UTC, Marcel wrote:
>> 2- How is the builtin associative array implemented? I think I read somewhere it's implemented like C++'s std::unordered_map but with BSTs instead of DLists for handling collisions: is this correct?
> 
> It's an open-addressed hash table. If you want to see all the details, the source is here:
> 
> https://github.com/dlang/druntime/blob/v2.090.1/src/rt/aaA.d

For some background, collisions used to be handled via a BST, which required all AA keys to provide opCmp in addition to opEquals and toHash.

It was changed some time ago (maybe like 8 years ago? Can't remember) to be open addressed hash, thus removing the requirement for opCmp.

This is probably why you read something about the old implementation using BST.

-Steve