https://issues.dlang.org/show_bug.cgi?id=2504: reserve for associative arrays

Jon Degenhardt via Digitalmars-d digitalmars-d at puremagic.com
Sat Nov 5 20:28:20 PDT 2016


On Sunday, 6 November 2016 at 02:12:12 UTC, Alexandru Caciulescu 
wrote:
> On Friday, 4 November 2016 at 09:37:39 UTC, Shachar Shemesh 
> wrote:
>> On 03/11/16 23:00, Yuxuan Shui wrote:
>>> On Wednesday, 2 November 2016 at 03:36:42 UTC, Andrei 
>>> Alexandrescu wrote:
>>>> [snip]
>>>>
>>>> * The implementation cannot use Phobos' allocator because 
>>>> it's in
>>>> druntime.
>>>
>>> How about let the user provide the memory block when they 
>>> calls reserve()?
>>>
>>
>> I think that's just a halfhearted attempt at introducing STL's 
>> allocators.
>
> I see this topic started a clash of opinions regarding the 
> future of AAs. After Andrei suggested a free-list 
> implementation I had a good idea of how to proceed but now I am 
> not so sure since this discussion isn't converging to a single 
> idea/implementation.
>
To make a concrete proposal - For near-term, against current AAs, 
add a 'reserve()' function that pre-allocates the bucket array, 
but not the memory for elements. This would be consistent with 
the current implementation. It looks like it could be done via a 
call to the 'resize()' function. It would be similar to the 
'rehash()' function (see _aaRehash() in aaA.d). Memory allocation 
and management for inserted elements is unchanged, it continues 
to operate as current. This approach would be similar to how the 
C++ std::unordered_map::reserve() function works.

This still permits a longer term approach adding template-based 
hash tables in the future, with various options for memory 
management, etc.

I think this suggestion is consistent with Steve Schveighoffer's 
suggestion earlier in the thread.

--Jon


More information about the Digitalmars-d mailing list