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

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

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

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

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

1. 标准文档定义

std::allocator - cppreference.com

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

成员类型

成员函数

非成员函数

注解

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

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

示例

#include <iostream>#include <memory>#include <string> int main(){    // int 的默认分配器    std::allocator<int> alloc1;     // 演示少见的直接使用成员    static_assert(std::is_same_v<int, decltype(alloc1)::value_type>);    int* p1 = alloc1.allocate(1);  // 一个 int 的空间    alloc1.deallocate(p1, 1);      // 而它没了     // 这些都可以通过特征使用，所以不需要直接使用    using traits_t1 = std::allocator_traits<decltype(alloc1)>; // 匹配的特征    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<std::string> alloc2;    // 匹配的特征    using traits_t2 = std::allocator_traits<decltype(alloc2)>;     // 用 string 的特征重绑定产生同一类型    traits_t2::rebind_alloc<std::string> 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);}

输出：

7foo bar

构造函数

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

参数

2. 探索

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

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

allocator() noexcept;

allocator( const allocator& other ) noexcept;

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

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

value_type T

size_type std::size_t

difference_type std::ptrdiff_t

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

allocate

deallocate

address（非必要）

max_size（非必要）

construct（非必要）

destroy（非必要）

2.2 自定义allocator 示例

• 内部使用std::allocator方式

#include <iostream>#include <vector>template <typename _Ty>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 <class _Other>    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 <class _Objty, class... _Types>    void construct(_Objty* const _Ptr, _Types&&... _Args) {        return alloc.construct<_Objty, _Types ...>(_Ptr, std::forward<_Types>(_Args) ... );    }    template <class _Uty>    void destroy(_Uty* const _Ptr) {        alloc.destroy<_Uty>(_Ptr);    }    size_t max_size() const noexcept {        return alloc.max_size();    }    template <class _Other>    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);    }#endifprivate:    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<A>> vec;    for (int i = 0; i < 100; i++) {        vec.emplace_back(i);    }    auto alloc = vec.get_allocator();    auto x = alloc.allocate(1);    //alloc.construct(x, 999);    new (x) A(999);    x->~A();    alloc.deallocate(x, 1);    return 0;}

• 继承 std::allocator 方式

#include <iostream>#include <vector>#include <map>template <typename _Ty>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<A>> vec;    for (int i = 0; i < 100; i++) {        vec.emplace_back(i);    }    //vec.get_allocator(); linux出错    std::map<int, int, std::less<int>, Allocator2<std::pair<const int, int>>> map;    map.insert({1, 1});    //map.get_allocator(); linux出错        return 0;}

• 不使用std::allocator方式

#include <iostream>#include <vector>#include <map>template <typename _Ty>class Allocator3 {public:    //成员类型    using value_type = _Ty;    //构造函数    constexpr Allocator3() noexcept {}    constexpr Allocator3(const Allocator3& x) noexcept = default;    template <class _Other>    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<A>> vec;    for (int i = 0; i < 100; i++) {        vec.emplace_back(i);    }    vec.get_allocator().Show();    std::map<int, int, std::less<int>, Allocator3<std::pair<const int, int>>> map;    map.insert({ 1, 1 });    map.get_allocator().Show();    return 0;}

3. 总结

通过上面的学习， 对allocator有了一定的了解， 以后碰上了， 不至于一头雾水。

有兴趣可以测试下 std::unordered_map 与 std::map 空间占比。

c++ 疑难杂症(3) 模板特化

c++ 疑难杂症(2) std::move

c++ 疑难杂症(6) std::map

c++ 疑难杂症(5) std::pair

c++ 疑难杂症(7) std::tuple

c++ 疑难杂症(1) std::thread

c++ 疑难杂症(9) std::array

c++ 疑难杂症(4) std:vector

c++ 疑难杂症(8) std::multimap

c++ 疑难杂症(11) std::forward_list

c++ 疑难杂症(10) std::initializer_list

c++ 疑难杂症(12) unordered_map