在实践中曾经有个需求：系统会陆续生产32字节固定大小串，检查是否重复，不重复就添加，最大的数据量可达到500万条记录，不使用磁盘，在内存中处理。

尝试了纯内存的sqlite，占用内存太大了，放弃；

也尝试直接使用std::map/std::set，都因为内存占用太大了，放弃；

最后是从std::map里把红黑树给抠出来，使用整型及位域来减少节点变量大小，一次性分配多个节点的内存之类的，从而实现内存不超过230M，满足了业务需求。

当时，如果是对std::allocator有所了解，也许不用这么折腾了；现在来学习学习。

1. 标准文档定义

在标头定义
template< class t> struct allocator;
template<> struct allocator;	(C++17 中弃用) (C++20 中移除)

如果不提供用户指定的分配器，那么 std::allocator 类模板是所有标准库容器使用的默认分配器。默认分配器无状态，即给定分配器的任何实例都可交换、比较相等，且能由同一分配器类型的任何其他实例释放分配的内存。

对 void 的显式特化缺少成员类型定义（typedef）reference、const_reference、size_type 和 difference_type。此特化不声明成员函数。	(C++20 前)
默认分配器满足分配器完整性要求。	(C++17 起)

成员类型

类型	定义
value_type	T
pointer (C++17 中弃用) (C++20 中移除)	T*
const_pointer (C++17 中弃用) (C++20 中移除)	const T*
reference (C++17 中弃用) (C++20 中移除)	T&
const_reference (C++17 中弃用) (C++20 中移除)	const T&
size_type	std::size_t
difference_type	std::ptrdiff_t
propagate_on _container _move_assignment (C++11)	std::true_type
rebind (C++17 中弃用) (C++20 中移除)	template< class u> struct rebind { typedef allocator other; };
is_always_equal (C++11) (C++23 中弃用) (C++26 中移除)	std::true_type

成员函数

(构造函数)	创建新的分配器实例 (公开成员函数)
(析构函数)	析构分配器实例 (公开成员函数)
address(C++20 前)	获得对象的地址，即使重载了 operator& (公开成员函数)
allocate	分配未初始化的存储 (公开成员函数)
allocate_at_least(C++23)	分配与请求的大小至少一样大的未初始化存储 (公开成员函数)
deallocate	解分配存储 (公开成员函数)
max_size(C++20 前)	返回最大的受支持分配大小 (公开成员函数)
construct(C++20 前)	在分配的存储中构造对象 (公开成员函数)
destroy(C++20 前)	析构已分配存储中的对象 (公开成员函数)

非成员函数

operator==

operator!=(C++20 中移除)

比较两个分配器实例 (公开成员函数)

注解

成员模板 rebind 提供获得不同类型的分配器的方式。例如，std::list 在分配某个内部类型 Node 节点时会使用分配器A::rebind<Node>::other (C++11 前)std::allocator_traits::rebind_alloc<Node>，它在 A 是 std::allocator 时以 A::rebind<Node>::other (C++11 起) 实现。

成员类型 is_always_equal 由 LWG 问题 3170 弃用，因为它使得派生自 std::allocator 的定制分配器默认被当作始终相等。
std::allocator_traitsstd::allocator::is_always_equal 未被弃用，而它的成员常量 value 对任何 T 均为 true。

示例

#include 
#include 
#include 
 
int main()
{
    // int 的默认分配器
    std::allocator alloc1;
 
    // 演示少见的直接使用成员
    static_assert(std::is_same_v);
    int* p1 = alloc1.allocate(1);  // 一个 int 的空间
    alloc1.deallocate(p1, 1);      // 而它没了
 
    // 这些都可以通过特征使用，所以不需要直接使用
    using traits_t1 = std::allocator_traits; // 匹配的特征
    p1 = traits_t1::allocate(alloc1, 1);
    traits_t1::construct(alloc1, p1, 7);  // 构造 int
    std::cout << *p1 << '\n';
    traits_t1::deallocate(alloc1, p1, 1); // 解分配 int 的空间
 
    // string 的默认分配器
    std::allocator alloc2;
    // 匹配的特征
    using traits_t2 = std::allocator_traits;
 
    // 用 string 的特征重绑定产生同一类型
    traits_t2::rebind_alloc alloc_ = alloc2;
 
    std::string* p2 = traits_t2::allocate(alloc2, 2); // 2 个 string 的空间
 
    traits_t2::construct(alloc2, p2, "foo");
    traits_t2::construct(alloc2, p2 + 1, "bar");
 
    std::cout << p2[0] << ' ' << p2[1] << '\n';
 
    traits_t2::destroy(alloc2, p2 + 1);
    traits_t2::destroy(alloc2, p2);
    traits_t2::deallocate(alloc2, p2, 2);
}

输出：

7
foo bar

构造函数


allocator() throw();	(C++11 前)
allocator() noexcept;	(C++11 起) (C++20 前)
constexpr allocator() noexcept;	(C++20 起)

allocator( const allocator& other ) throw();	(C++11 前)
allocator( const allocator& other ) noexcept;	(C++11 起) (C++20 前)
constexpr allocator( const allocator& other ) noexcept;	(C++20 起)

template< class u> allocator( const allocator& other ) throw();	(C++11 前)
template< class u> allocator( const allocator& other ) noexcept;	(C++11 起) (C++20 前)
template< class u> constexpr allocator( const allocator& other ) noexcept;	(C++20 起)

构造默认分配器。因为默认分配器是无状态的，故构造函数无可见效应。

参数

other

用以构造的另一 allocator

2. 探索

2.1 自定义allocator 要求(c++11起， c++20前)

构造函数(参考上面的构造函数定义)

allocator() noexcept;

allocator( const allocator& other ) noexcept;

template< class u> allocator( const allocator& other ) noexcept;

定义的成员类型(参考上面的成员类型)

value_type T

size_type std::size_t

difference_type std::ptrdiff_t

定义成员函数(参考上面的成员类型)

2.2 自定义allocator 示例

内部使用std::allocator方式

#include 
#include 

template 
class Allocator1 {
public:
    //成员类型
    using value_type = _Ty;
    //using size_type = size_t;
    //using difference_type = ptrdiff_t;

    //构造函数
    constexpr Allocator1() noexcept {}
    constexpr Allocator1(const Allocator1&) noexcept = default;
    template 
    constexpr Allocator1(const Allocator1<_other>&) noexcept {}

    //成员函数
    _Ty* allocate(const size_t _Count) {
        return alloc.allocate(_Count);
    }

    void deallocate(_Ty* const _Ptr, const size_t _Count) {
        return alloc.deallocate(_Ptr, _Count);
    }
#if 0
//非必要实现
    template 
    void construct(_Objty* const _Ptr, _Types&&... _Args) {
        return alloc.construct<_objty, _types ...>(_Ptr, std::forward<_types>(_Args) ... );
    }

    template 
    void destroy(_Uty* const _Ptr) {
        alloc.destroy<_uty>(_Ptr);
    }

    size_t max_size() const noexcept {
        return alloc.max_size();
    }

    template 
    struct rebind {
        using other = Allocator1<_other>;
    };
    _Ty* address(_Ty& _Val) const noexcept {
        return alloc.address(_Val);
    }

    const _Ty* address(const _Ty& _Val) const noexcept {
        return alloc.address(_Val);
    }
#endif
private:
    std::allocator<_ty> alloc;
};

int main() {

    class A {
        int val = 0;
    public:
        A(int x) : val(x){
            std::cout << "A(" << val << ")" << std::endl;
        }
        ~A() {
            std::cout << "~A(" << val << ")" << std::endl;
        }
    };

    std::vector<A, Allocator1> vec;
    for (int i = 0; i < 100 i vec.emplace_backi auto alloc='vec.get_allocator();' auto x='alloc.allocate(1);' alloc.constructx 999 new x a999 x->~A();
    alloc.deallocate(x, 1);
    return 0;
}

继承 std::allocator 方式

#include 
#include 
#include 

template 
class Allocator2 : public std::allocator<_ty> {
//class Allocator2 : private std::allocator<_ty> {
public:      
    //使用父类构造函数
    using std::allocator<_ty>::allocator;
    using std::allocator<_ty>::value_type;

    //成员函数
    _Ty* allocate(const size_t _Count) {
        return std::allocator<_ty>::allocate(_Count);
    }

    void deallocate(_Ty* const _Ptr, const size_t _Count) {
        return std::allocator<_ty>::deallocate(_Ptr, _Count);
    }
};

int main() {

    class A {
        int val = 0;
    public:
        A(int x) : val(x) {
            std::cout << "A(" << val << ")" << std::endl;
        }
        ~A() {
            std::cout << "A(" << val << ")" << std::endl;
        }
    };

    std::vector<A, Allocator2> vec;
    for (int i = 0; i < 100; i++) {
        vec.emplace_back(i);
    }
    //vec.get_allocator(); linux出错

    std::map<int, int, std::less, Allocator2<std::pair>> map;
    map.insert({1, 1});
    //map.get_allocator(); linux出错
    
    return 0;
}

不使用std::allocator方式

#include 
#include 
#include 

template 
class Allocator3 {
public:
    //成员类型
    using value_type = _Ty;

    //构造函数
    constexpr Allocator3() noexcept {}
    constexpr Allocator3(const Allocator3& x) noexcept = default;
    template 
    constexpr Allocator3(const Allocator3<_other>& x) noexcept {
        totalSize = x.totalSize;
    }

    //成员函数
    _Ty* allocate(const size_t _Count) {
        size_t size = _Count * sizeof(_Ty);
        totalSize += size;
        return (_Ty*)std::malloc(size);
    }

    void deallocate(_Ty* const _Ptr, const size_t _Count) {
        std::free(_Ptr);
    }

    void Show() {
        std::cout << "分配大小: " << totalSize << std::endl;
    }

    size_t totalSize = 0;

};

int main() {

    class A {
        int val = 0;
    public:
        A(int x) : val(x) {
            std::cout << "A(" << val << ")" << std::endl;
        }
        ~A() {
            std::cout << "A(" << val << ")" << std::endl;
        }
    };

    std::vector<A, Allocator3> vec;
    for (int i = 0; i < 100; i++) {
        vec.emplace_back(i);
    }
    vec.get_allocator().Show();

    std::map<int, int, std::less, Allocator3<std::pair>> map;
    map.insert({ 1, 1 });
    map.get_allocator().Show();

    return 0;
}