C++20中为std::map实现自定义分配器：rebind_alloc与节点分配问题

一、正确设置rebind_alloc #

你当前的rebind_alloc写法存在循环依赖问题，std::allocator_traits<Allocator2<T>>::rebind_alloc<U>本身就依赖分配器自身的rebind机制，不需要间接引用它。正确的写法是直接将rebind_alloc<U>定义为Allocator2<U>：

template<typename U>
using rebind_alloc = Allocator2<U>;

如果需要兼容C++03标准，也可以用传统的rebind结构体写法：

template<typename U>
struct rebind {
    using other = Allocator2<U>;
};

C++11及以后更推荐用模板别名rebind_alloc，写法更简洁直观。

二、修复std::map的比较函数 #

你的PointCmp不符合std::map要求的严格弱序规则，当前return lhs == rhs的逻辑会让map认为所有插入元素都相等，只会保留第一个元素，自然看不到后续的节点分配操作。必须修正为严格弱序比较：

struct PointCmp {
    bool operator()(const int& lhs, const int& rhs) const {
        return lhs < rhs; // 符合map要求的严格弱序
    }
};

三、验证节点分配操作 #

修正后，map会通过rebind_alloc将你传入的Allocator2<std::pair<const int, int>>转换为内部节点类型的分配器（比如Allocator2<std::_Rb_tree_node<std::pair<const int, int>>>），此时allocate函数会被调用，你会看到输出Alloc 1（每个map节点单独分配，n=1）。

如果想更清晰地看到分配的类型，可在allocate函数中添加类型信息输出：

T* allocate(size_type n, const void* hint = 0)
{
    std::cout << "Alloc " << n << " elements of type: " << typeid(T).name() << std::endl;
    return static_cast<T*>(malloc(n*sizeof(T)));
}

这样就能明确看到分配的是map内部的节点类型，而非std::pair<const int, int>。

完整修正后的代码示例 #

#include <iostream>
#include <map>
#include <memory>
#include <limits>
#include <typeinfo>

template <class T>
class Allocator2
{
public:
    using value_type = T;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using propagate_on_container_move_assignment = std::true_type;

    // 正确的rebind_alloc定义
    template<typename U>
    using rebind_alloc = Allocator2<U>;

    T* allocate(size_type n, const void* hint = 0)
    {
        std::cout << "Alloc " << n << " elements of type: " << typeid(T).name() << std::endl;
        return static_cast<T*>(malloc(n*sizeof(T)));
    }

    void deallocate(T* p, size_type n) { free(p); }
    size_type max_size() const { return size_type(std::numeric_limits<unsigned int>::max() / sizeof(T)); }
    
    template<typename... Args>
    void construct(T* p, Args&&... args) {
        std::construct_at(p, std::forward<Args>(args)...);
    }
    
    void destroy(T* p) { std::destroy_at(p); }
};

template<class T, class U>
bool operator==(const Allocator2<T>&, const Allocator2<U>&) noexcept { return true; }

template<class T, class U>
bool operator!=(const Allocator2<T>&, const Allocator2<U>&) noexcept { return false; }

struct PointCmp {
    bool operator()(const int& lhs, const int& rhs) const {
        return lhs < rhs; // 修正为严格弱序
    }
};

template <typename T>
void Print(T t)
{
    std::cout << __PRETTY_FUNCTION__ << std::endl;
}

int main()
{
    using valueType = std::map<int, int>::value_type;
    Print(valueType{});
    std::map<int, int, PointCmp, Allocator2<valueType>> m;

    for (unsigned int n = 0; n < 10; n++) // 用10个元素测试即可
    {
        std::cout << "Now set " << n << std::endl;
        m[n] = n;
    }
}

运行代码后，每次插入元素都会触发allocate函数的输出，清晰显示map节点的分配操作。

内容的提问来源于stack exchange，提问作者Klaus