custom allocator for std::unordered_map

Question

I am trying to use my custom allocator for a std::unordered_map. The allocator already works for my own objects and also for std::vector, but when I try to use it in the same way for a std::unordered_map I get an error message from hashtable.h:

/usr/include/c++/11/bits/hashtable.h:204:21: error: static assertion failed: unordered container must have the same value_type as its allocator
  204 |       static_assert(is_same<typename _Alloc::value_type, _Value>{},

The class where I try to use my custom allocator:

class a {
  public:
  /**
   * @brief Creates a A managed by an shared ptr.
   */
  [[nodiscard]] static std::shared_ptr<a> create();

  /**
   * @brief Creates a B as part of A.
   * @tparam T The type of the b. (There are different Bs, but all inherit from the origin class B)
   * @param args Arguments to pass to b.
   * @return The b.
   */
  template<typename T, typename... Args>
  T* create_b(Args&&... args) {
    std::unique_ptr<T> b = std::make_unique<T>(std::forward<Args>(args)...);
    Bs_.push_back(std::move(b));
    return static_cast<T*>(Bs_.back().get());
  }

  /**
   * @brief Overloaded new operator to use the custom allocator.
   */
  void* operator new(std::size_t size)
  {
    tlsf_allocator allocator;
    return allocator.allocate<a>(size);
  }

  /**
   * @brief Overloaded delete operator to use the custom deallocator.
   */
  void operator delete(void* ptr)
  {
    tlsf_allocator allocator;
    allocator.deallocate<a>(static_cast<a*>(ptr), 1);
  }

  private:
  // CTOR is private to prevent constructing a class object without being managed by a shared_ptr.
  a();

  //std::unordered_map<const i_b*, c*, std::hash<const i_b*>, std::equal_to<const i_b*>> Bs_to_Cs_{};//working fine, but no custom allocator

  std::unordered_map<const i_b*, c*, std::hash<const i_b*>, std::equal_to<const i_b*>, tlsf_allocator::allocator_for<std::pair<const i_b*, c*>>> Bs_to_Cs_{}; // Error

  std::vector<std::unique_ptr<i_b>, tlsf_allocator::allocator_for<std::unique_ptr<i_b>>> Bs_{};//working fine, even with custom allocator
};

My custom allocator:

/**
 * @class tlsf_allocator
 * @brief A custom allocator class that uses TLSF (Two-Level Segregated Fit) for memory allocation.
 */
class tlsf_allocator {
  public:
  /**
   * @brief Allocates memory for 'n' elements of type 'T'.
   *
   * @tparam T The type of elements to allocate memory for.
   * @param n The number of elements to allocate memory for.
   * @return A pointer to the allocated memory block.
   *
   * This function allocates memory for 'n' elements of type 'T' using TLSF memory management.
   * It returns a pointer to the allocated memory block.
   */
  template<typename T>
  T* allocate(size_t n) {
    T* result = reinterpret_cast<T*>(tlsf_malloc(get_tlsf_pool(), sizeof(T) * n));
    if (result == nullptr) {
      throw std::bad_alloc();    // not enough memory to allocate new the object
    }
    return result;
  }

  /**
   * @brief Deallocates memory block at the given pointer.
   *
   * @tparam T The type of the memory block being deallocated.
   * @param ptr A pointer to the memory block to deallocate.
   * @param n The number of elements in the memory block (unused in this implementation), but required for
   * std::allocator_traits.
   *
   * This function deallocates the memory block at the given pointer using TLSF memory management.
   * The 'n' parameter is unused in this implementation but kept for compatibility with the allocator concept.
   */
  template<typename T>
  void deallocate(T* ptr, [[maybe_unused]] size_t n) {
    tlsf_free(get_tlsf_pool(), ptr);
  }

  /**
   * @struct allocator_for
   * @brief An allocator adaptor for providing the tlsf_allocator to STL containers.
   *
   * This allocator adaptor is used to provide the tlsf_allocator functionality to STL containers
   * like std::vector. It is used as a template parameter when declaring a container with the
   * desired element type. This allows the container's memory allocation and deallocation operations
   * to be managed by the tlsf_allocator.
   *
   * @tparam U The type of the elements that the allocator should allocate memory for.
   */
  template<typename U>
  struct allocator_for {
    /**
     * @brief Type alias for the element type managed by the allocator adaptor.
     *
     * This type alias defines the type of elements that the allocator adaptor manages.
     * It is used to provide information about the element type to the STL containers
     * that use this allocator.
     */
    using value_type = U;

    /**
     * @brief Default constructor.
     */
    allocator_for() noexcept = default;

    /**
     * @brief Copy constructor.
     *
     * @tparam V Another type.
     * @param other Another allocator_for instance.
     */
    template<typename V>
    explicit allocator_for([[maybe_unused]] const allocator_for<V>& other) noexcept {}

    /**
     * @brief Allocate memory for elements.
     *
     * @param n The number of elements to allocate memory for.
     * @return A pointer to the allocated memory block.
     */
    U* allocate(std::size_t n) {
      tlsf_allocator allocator;
      return reinterpret_cast<U*>(allocator.allocate<U>(n));
    }

    /**
     * @brief Deallocate memory for elements.
     *
     * @param p A pointer to the memory block to deallocate.
     * @param n The number of elements.
     */
    void deallocate(U* p, std::size_t n) noexcept {
      tlsf_allocator allocator;
      allocator.deallocate<U>(p, n);
    }
  };

  private:
  /**
   * @brief Gets the TLSF memory pool.
   *
   * @return A reference to the TLSF memory pool.
   *
   * This static function returns a reference to the TLSF memory pool used by the allocator.
   * It ensures that a single memory pool is shared among all instances of the allocator.
   */
  static tlsf_t& get_tlsf_pool();
};

I have looked at sample code. Each time pair<const key, value> is used, but it doesn't seem to work for me. As it looks my allocator appears to use a wrong value_type for the std::unordered_map somehow.

I also tried to write my own unordered_map class, which uses std::unordered_map internally, but redefines new and delete. I know that normally writing your own unordered_map class is not necessary to use a custom allocator for std::unordered_map, but since my first attempt failed i wanted to try this as a second approach. The error was the same, so I dropped this approach.

I am aware that using a custom allocator is a special case. I want to use this because I am running in an embedded environment and would like to use the tlsf memory allocation on static memory. Additionally I want all objects created by my custom allocator to be in the same tlsf_pool. Therefore I could not give the class tlsf_allocator a template<typename T>, because this caused the method static tlsf_t& get_tlsf_pool(); to return different memory areas. That was enough at this point to run my own classes over my custom allocator. But since I also wanted to allocate std::vector and std::unordered_map over my custom allocator, I wrote myself an allocator adaptor (struct allocator_for) for providing the tlsf_allocator to STL containers. This then also has the template parameter U and therefore can also have using value_type = U;.

This was enough to allocate the std::vector, but I failed with std::unordered_map.

Answer 1

Your key is const i_b*. The value_type must be a pair that contains const key as its first element. For your case that would be const i_b * const.

Answer 2

Allocators are provided to STL containers via template parameters, at compile time. By default, these parameters are set to STL allocators, particularly std::allocator.

The reason the STL allows allocators as template parameters is modularly, i.e. you can get the behavior of std::vector without a tight coupling to some allocation scheme. This includes a tight coupling to new.

First off, you do not need to override operator new. Defining and using custom allocators takes care of this. You shouldn't do both.

Before implementing a custom allocator, you must ask yourself, why? There are very few reasons to implement custom allocators. The most compelling is performance. std::allocator and the default implementation of new are incredibly general purpose. This is good for usability, but in some niche scenarios can hurt performance. For example, applications like game engines and web servers often utilize an arena or pool allocator. This is because they often allocate many small objects near the same time, and don't care too much about their lifetime. For general purpose allocators this is expensive, but arena allocators can perform multiple allocs and frees for very cheap, at the cost of deferred memory reclamation.

But suppose you DO want to implement a custom allocator. Coming from languages like Java, you might expect that an allocator must implement some Allocator interface. This is generally true for C++ as well, when using run-time polymorphism. But as stated above, allocators are provided via template parameters, at compile-time.

So you need a templated compile-time interface. In C++20, this was formalized as concept. This is fundamentally different from OOP style interfaces. How? Interfaces must be explicitly implemented, concepts are not. Classes that implicitly happen to meet the requirements of a concept are accepted. As such, to implement a custom allocator, you need not derive from any interface. Rather, you simply write a class that has the necessary methods, types, returns, etc expected by an allocator in the STL.

Please see the following link at cppreference: https://en.cppreference.com/w/cpp/named_req/Allocator

This is the named requirements (concept) for an allocator to be used in the STL. It even includes a MVP example that you can drop in and use. Cppreference is a FANTASTIC resource for STL type stuff. The STL and standard are... complicated. Cppreference is very detail oriented and accurate.

For your particular error, the error message lays it out quite nicely. The Allocator is for a given container is expected to have a value type equal to T.

template<typename T>
custom_allocator
{
  using value_type = T;
...
};

auto v = std::vector<int, custom_allocator<int>>();