Allocator Usage with STL Unordered Set

[simoatze]

I have a set that will contain at most 25000 elements. Now if I use the std::unordered_set, every time I insert a new element (which is of type MyStruct), malloc will be called so it will actually affect significantly the performance. Also, when I reach 25000 elements, I want to clear the set and fill it up again.

I always need the same amount of memory and there should be no need to allocate and deallocate all the time.

If I understood correctly, I could use an allocator to allocate in advance the amount of memory I need to store these 25000 elements and instead of deallocating the memory I could just make the same memory available again.

I have been trying to use a custom allocator found online, but as soon as I clear the set and try to insert new elements I get “bad_alloc” error. So believe that as soon as I call "clear" the memory is completely deallocated, right?

Is there a way to work around this problem?

Thanks.
Best,
Simone

[mbozzi]

There's no need for a custom allocator in this case.
http://en.cppreference.com/w/cpp/container/unordered_set/reserve

[Cubbi]

unordered_set, like other node-based hash tables, actually uses two allocators (both obtained by rebinding from the allocator you supply as the template parameter)

One allocator is used to allocate the nodes (in gnu libstdc++ they have type std::__detail::_Hash_node<T, false>, in llvm libc++ std::__1::__hash_node<T, void *>). It is always called to allocate/deallocate just one node at a time, once per single-value insert.

The other to allocate buckets (in gnu libstdc++, a bucket is a pointer of type std::__detail::_Hash_node_base*, in llvm libc++, pointer of type std::__1::__hash_node_base<std::__1::__hash_node<T, void *> *> *). This second allocator is called to allocate the entire bucket array, once per resize.

The call to unordered_set::reserve allocates the bucket arrays, it makes the call to the second allocator, but does not pre-allocate any nodes. They can indeed benefit greatly from a monotonic pool allocator (same as any other node-based container really), since all nodes have fixed size.

So believe that as soon as I call "clear" the memory is completely deallocated, right?

When you call clear, the first allocator is called for every node in the set. The second allocator is not called (capacity does not change)

Sounds like the allocator you found online has bugs

[JLBorges]

Cubbi, could something like this be done?

1. Extract all the the node handles from the set and move them into a vector.
2. Modify the keys of the node to reflect the new values
3. Reinsert the modified node handles into the unordered_set

Would this be efficient?

[Cubbi]

efficient key change in sets was part of the motivation for C++17's node handle API, so I would think yes, at least as efficient as it gets (hash/equality will still be called)

[JLBorges]

Thank you!