www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Associative arrays

reply TheFlyingFiddle <kurtyan student.chalmers.se> writes:
I have a few questions about the pseudo built in associative 
arrays.

1. Is it possible to have the built in associative array use a 
custom allocator from std.experimental.allocator to service it's 
allocation needs?

2. A while ago I read on the newsgroup a while back that there 
was a plan to make it possible for a user to swap out the 
standard associative array implementation by modifying druntime 
and or implementing some linker functions. Have this been done 
yet? And if so what must I do to swap the implementation?
Nov 08 2015
parent reply Rikki Cattermole <alphaglosined gmail.com> writes:
On 09/11/15 4:57 PM, TheFlyingFiddle wrote:

 I have a few questions about the pseudo built in associative arrays.

 1. Is it possible to have the built in associative array use a custom
 allocator from std.experimental.allocator to service it's allocation needs?


Nope.


 2. A while ago I read on the newsgroup a while back that there was a
 plan to make it possible for a user to swap out the standard associative
 array implementation by modifying druntime and or implementing some
 linker functions. Have this been done yet? And if so what must I do to
 swap the implementation?


As far as I'm aware, you are stuck using e.g. structs to emulate AA 
behavior.
I have a VERY basic implementation here: 
https://github.com/rikkimax/alphaPhobos/blob/master/source/std/experimental/internal/containers/map.d
Feel free to steal.
Nov 08 2015
parent reply rsw0x <anonymous anonymous.com> writes:
On Monday, 9 November 2015 at 04:29:30 UTC, Rikki Cattermole 
wrote:

 On 09/11/15 4:57 PM, TheFlyingFiddle wrote:

 [...]


 Nope.


 [...]


 As far as I'm aware, you are stuck using e.g. structs to 
 emulate AA behavior.
 I have a VERY basic implementation here: 
 https://github.com/rikkimax/alphaPhobos/blob/master/source/std/experimental/internal/containers/map.d
 Feel free to steal.


Fwiw, EMSI provides high quality containers backed by 
std.experimental.allocator.
https://github.com/economicmodeling/containers
Nov 08 2015
next sibling parent TheFlyingFiddle <kurtyan student.chalmers.se> writes:
On Monday, 9 November 2015 at 04:52:37 UTC, rsw0x wrote:

 On Monday, 9 November 2015 at 04:29:30 UTC, Rikki Cattermole 
 wrote:

 On 09/11/15 4:57 PM, TheFlyingFiddle wrote:

 [...]


 Nope.


 [...]


 As far as I'm aware, you are stuck using e.g. structs to 
 emulate AA behavior.
 I have a VERY basic implementation here: 
 https://github.com/rikkimax/alphaPhobos/blob/master/source/std/experimental/internal/containers/map.d
 Feel free to steal.


 Fwiw, EMSI provides high quality containers backed by 
 std.experimental.allocator.
 https://github.com/economicmodeling/containers


Thanks for the suggestions. I also made a hashmap using 
allocators some time ago that I use in-place of the built in 
hashmap for most of my purposes. The syntax of a custom hash map 
is somewhat lacking in comparison to the built in one however and 
I was hoping that I could either make the built in work with 
allocators or replace it with my own implementation.

In addition to this I am building a pointer patching binary 
serializer and I hoped that I could make it work with the built 
in aa without requiring to many gc allocations.

The economicmodeling one seems interesting ill try it out and see 
if it's better then the one I am currently using.
Nov 09 2015
prev sibling parent reply TheFlyingFiddle <kurtyan student.chalmers.se> writes:
On Monday, 9 November 2015 at 04:52:37 UTC, rsw0x wrote:

 On Monday, 9 November 2015 at 04:29:30 UTC, Rikki Cattermole 
 wrote:
 Fwiw, EMSI provides high quality containers backed by 
 std.experimental.allocator.
 https://github.com/economicmodeling/containers


I have a question regarding the implementation of the 
economicmodeling hashmap. Why must buckets be a power of two? Is 
it to be able to use the: hash & (buckets.length - 1) for index 
calculations or is there some other reason?
Nov 09 2015
next sibling parent rsw0x <anonymous anonymous.com> writes:
On Monday, 9 November 2015 at 21:33:09 UTC, TheFlyingFiddle wrote:

 On Monday, 9 November 2015 at 04:52:37 UTC, rsw0x wrote:

 On Monday, 9 November 2015 at 04:29:30 UTC, Rikki Cattermole 
 wrote:
 Fwiw, EMSI provides high quality containers backed by 
 std.experimental.allocator.
 https://github.com/economicmodeling/containers


 I have a question regarding the implementation of the 
 economicmodeling hashmap. Why must buckets be a power of two? 
 Is it to be able to use the: hash & (buckets.length - 1) for 
 index calculations or is there some other reason?


I have no idea, sorry.
Schott wrote them AFAIK, he might be able to respond if he sees 
this.
Nov 09 2015
prev sibling parent reply Brian Schott <briancschott gmail.com> writes:
On Monday, 9 November 2015 at 21:33:09 UTC, TheFlyingFiddle wrote:

 On Monday, 9 November 2015 at 04:52:37 UTC, rsw0x wrote:

 On Monday, 9 November 2015 at 04:29:30 UTC, Rikki Cattermole 
 wrote:
 Fwiw, EMSI provides high quality containers backed by 
 std.experimental.allocator.
 https://github.com/economicmodeling/containers


 I have a question regarding the implementation of the 
 economicmodeling hashmap. Why must buckets be a power of two? 
 Is it to be able to use the: hash & (buckets.length - 1) for 
 index calculations or is there some other reason?


Yes. It's a hack that gives you a modulus without having to do a 
modulus. It only works on powers of two.
Nov 09 2015
parent Brian Schott <briancschott gmail.com> writes:
On Tuesday, 10 November 2015 at 01:29:11 UTC, Brian Schott wrote:

 Yes. It's a hack that gives you a modulus without having to do 
 a modulus. It only works on powers of two.


http://graphics.stanford.edu/~seander/bithacks.html#ModulusDivisionEasy
Nov 09 2015