如何计算包含最大 N 个元素的 std::multiset 的最大分配数？

Question

我将 6 个对象推送到 std::multimap，但我在控制台中看到分配器有 8 个输出。为什么？总是N+2吗？如何计算N个元素的最大分配数？

我想在分配器中使用静态数组，return 指向它元素的指针用于数据局部性。

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 中引入），而不是自己制作或简单地实现一个支持最多所需元素数量的简单多重集。

如何计算包含最大 N 个元素的 std::multiset 的最大分配数？

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

c++

std

hashmap

red-black-tree

multiset