Как рассчитать распределение максимального числа для std :: multiset, содержащего максимум N элементов?

Question

Я поместил 6 объектов в std :: multimap, но я вижу 8 выводов из распределителя в консоли. Почему? Это всегда N + 2? Как рассчитать максимальное количество выделений для N элементов?

Я хочу использовать статический массив внутри распределителя и возвращать указатели на него элементов для локальности данных.

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();
}

Answer 1

Я не верю, что было указано, как идет реализация для мультимножества, набора и т. Д. Номер, который вы ищете, может быть разным для разных платформ / версий STL / или неожиданно увеличиваться при общем количестве выделений. .

Я советую вам использовать полиморфный распределитель (представленный в C ++ 17) вместо создания собственного или просто реализовать простой мультимножество, поддерживающее до нужного количества элементов.