Thread overview | |||||||
---|---|---|---|---|---|---|---|
|
February 12, 2020 Type sequence concatenation / associative array implementation | ||||
---|---|---|---|---|
| ||||
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? |
February 12, 2020 Re: Type sequence concatenation / associative array implementation | ||||
---|---|---|---|---|
| ||||
Posted in reply to Marcel | 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. |
February 12, 2020 Re: Type sequence concatenation / associative array implementation | ||||
---|---|---|---|---|
| ||||
Posted in reply to user1234 | 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... |
February 12, 2020 Re: Type sequence concatenation / associative array implementation | ||||
---|---|---|---|---|
| ||||
Posted in reply to Marcel | 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 |
February 13, 2020 Re: Type sequence concatenation / associative array implementation | ||||
---|---|---|---|---|
| ||||
Posted in reply to Paul Backus | 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
|
Copyright © 1999-2021 by the D Language Foundation