How to callculate max number allocations for std::multiset containing maximum N elements?

user_747709 0
Viewed 57

I pushed 6 objects to std::multimap but I see 8 outputs from allocator in console. Why? Is it always N+2? How to calculate max number of allocations for N elements?

I want to use static array inside allocator and return pointers to it elements for data locality.

template <class T>
struct Mallocator {
  typedef T value_type;
  Mallocator() = default;
  template <class U> constexpr Mallocator(const Mallocator<U>&) noexcept {}
  T* allocate(std::size_t n) {
    if (n > std::numeric_limits<std::size_t>::max() / sizeof(T)) throw std::bad_alloc();
    if (auto p = static_cast<T*>(std::malloc(n * sizeof(T)))) { std::cout << "allocate" << std::endl; return p; }
    throw std::bad_alloc();
  }
  void deallocate(T* p, std::size_t) noexcept { std::cout << "free" << std::endl;  std::free(p); }
};
template <class T, class U>
bool operator==(const Mallocator<T>&, const Mallocator<U>&) { return true; }
template <class T, class U>
bool operator!=(const Mallocator<T>&, const Mallocator<U>&) { return false; }

int main()
{
  std::multiset<int, std::less<int>, Mallocator<int>> hashMap;

  hashMap.insert(1);
  hashMap.insert(2);
  hashMap.insert(3);
  hashMap.insert(4);
  hashMap.insert(5);
  hashMap.insert(6);

  _getch();
}
multiset red-black-tree std hashmap c++
1 Answers

I don't believe it was specified how the implementation goes for the multiset, set, etc. The number you are looking for might be different numbers for different platforms / versions of STL / or increase unexpectedly with the total number of allocations.

I advise you to use the polymorphic allocator (introduced in C++17) instead of making your own or simply implement a simple multiset that supports up to the desired number of elements.

user_108036710
Related