在实践中曾经有个需求： 系统会陆续生产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);
}

输出：

7
foo 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);
    }
#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<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