池分配器与免费列表的更多问题

Question

在std :: map中，这会在构造第一个对象时导致错误。我检查了调试器，我发现free_list :: init（）正确地创建了连续的内存地址。我知道这个分配器不能用于向量或其他相关容器，但它只能用于结节容器。

我从这里获得了一个运行时错误实用程序（在VC12中），第158行：

_Container_proxy *_Parent_proxy = _Parent->_Myproxy;

检查调试器，似乎_Parent从未初始化，导致0xC0000005运行时错误。为什么或如何没有初始化以及为什么在构造第一个对象时发生这种情况（在std :: map执行3次单独分配之后），我不知道。

我想使用std :: map和std :: list以及其他结节容器，并不担心它是否可以在std :: vector等中执行。

#include <algorithm>

class free_list {
public:
    free_list() {}

    free_list(free_list&& other)
        : m_next(other.m_next) {
        other.m_next = nullptr;
    }

    free_list(void* data, std::size_t num_elements, std::size_t element_size) {
        init(data, num_elements, element_size);
    }

    free_list& operator=(free_list&& other) {
        m_next = other.m_next;
        other.m_next = nullptr;
    }

    void init(void* data, std::size_t num_elements, std::size_t element_size) {
        union building {
            void* as_void;
            char* as_char;
            free_list* as_self;
        };

        building b;

        b.as_void = data;
        m_next = b.as_self;
        b.as_char += element_size;

        free_list* runner = m_next;
        for (std::size_t s = 1; s < num_elements; ++s) {
            runner->m_next = b.as_self;
            runner = runner->m_next;
            b.as_char += element_size;
        }
        runner->m_next = nullptr;
    }

    free_list* obtain() {
        if (m_next == nullptr) {
            return nullptr;
        }
        free_list* head = m_next;
        m_next = head->m_next;
        return head;
    }

    void give_back(free_list* ptr) {
        ptr->m_next = m_next;
        m_next = ptr;
    }

    free_list* m_next;

};

template<class T>
class pool_alloc {
    typedef pool_alloc<T> myt;

public:
    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;
    typedef T value_type;
    typedef T& reference;
    typedef const T& const_reference;
    typedef T* pointer;
    typedef const T* const_pointer;

    typedef std::false_type propagate_on_container_copy_assignment;
    typedef std::true_type propagate_on_container_move_assignment;
    typedef std::true_type propagate_on_container_swap;

    template<class U> struct rebind {
        typedef pool_alloc<U> other;
    };

    ~pool_alloc() {
        destroy();
    }
    pool_alloc() : data(nullptr), fl(), capacity(4096) {
    }
    pool_alloc(size_type capacity) : data(nullptr), fl(), capacity(capacity) {}

    pool_alloc(const myt& other)
        : data(nullptr), fl(), capacity(other.capacity) {}

    pool_alloc(myt&& other)
        : data(other.data), fl(std::move(other.fl)), capacity(other.capacity) {
        other.data = nullptr;
    }

    template<class U>
    pool_alloc(const pool_alloc<U>& other) 
        : data(nullptr), fl(), capacity(other.max_size()) {}

    myt& operator=(const myt& other) {
        destroy();
        capacity = other.capacity;
    }

    myt& operator=(myt&& other) {
        destroy();
        data = other.data;
        other.data = nullptr;
        capacity = other.capacity;
        fl = std::move(other.fl);
    }

    static pointer address(reference ref) {
        return &ref;
    }

    static const_pointer address(const_reference ref) {
        return &ref;
    }

    size_type max_size() const {
        return capacity;
    }

    pointer allocate(size_type) {
        if (data == nullptr) create();
        return reinterpret_cast<pointer>(fl.obtain());
    }

    void deallocate(pointer ptr, size_type) {
        fl.give_back(reinterpret_cast<free_list*>(ptr));
    }

    template<class... Args>
    static void construct(pointer ptr, Args&&... args) {
        ::new (ptr) T(std::forward<Args>(args)...);
    }

    static void destroy(pointer ptr) {
        ptr->~T();
    }

    bool operator==(const myt& other) const {
        return reinterpret_cast<char*>(data) ==
            reinterpret_cast<char*>(other.data);
    }

    bool operator!=(const myt& other) const {
        return !operator==(other);
    }

private:

    void create() {
        data = ::operator new(capacity * sizeof(value_type));
        fl.init(data, capacity, sizeof(value_type));
    }

    void destroy() {
        ::operator delete(data);
        data = nullptr;
    }

    void* data;
    free_list fl;
    size_type capacity;

};

template<>
class pool_alloc < void > {
public:
    template <class U> struct rebind { typedef pool_alloc<U> other; };

    typedef void* pointer;
    typedef const void* const_pointer;
    typedef void value_type;
};

构造std :: pair时出现问题（在第214行的MSVC12实用程序中）：

    template<class _Other1,
        class _Other2,
        class = typename enable_if<is_convertible<_Other1, _Ty1>::value
            && is_convertible<_Other2, _Ty2>::value,
            void>::type>
        pair(_Other1&& _Val1, _Other2&& _Val2)
            _NOEXCEPT_OP((is_nothrow_constructible<_Ty1, _Other1&&>::value
                && is_nothrow_constructible<_Ty2, _Other2&&>::value))
        : first(_STD forward<_Other1>(_Val1)),
                second(_STD forward<_Other2>(_Val2))
        {   // construct from moved values
        }

即使在单步执行后，也会发生运行时错误，与上述_Parent未初始化时相同。

Answer 1

我通过广泛的调试能够回答我自己的问题。显然，VC12的std :: map实现至少有时会抛出一个_Alnod（永久分配器，它在映射的生命周期内保持在范围内，用于分配和释放映射中的节点，我期望的是什么实际上调用allocate（）和deallocate（））作为_Alproxy，一个临时分配器，使用allocate（）创建一些名为_Mproxy（或类似的东西）的对象。但是，问题是VC12的实现然后让_Alproxy超出范围，同时仍然期望指向分配的对象的指针保持有效，所以很明显我必须使用:: operator new和:: operator delete on像_Mproxy这样的对象：使用内存池然后超出范围，而指向其中的位置的指针仍然是导致崩溃的原因。

我提出了我认为可以称为脏技巧的测试，这是在复制构造或将分配器复制分配给另一个分配器类型时执行的测试：

template<class U>
pool_alloc(const pool_alloc<U>& other)
    : data(nullptr), fl(), capacity(other.max_size()), use_data(true) {
    if (sizeof(T) < sizeof(U)) use_data = false;
}

我将bool成员use_data添加到allocator类，如果为true则表示使用内存池，如果为false则表示使用:: operator new和:: operator delete。默认情况下，这是真的。当分配器被转换为另一个分配器类型，其模板参数的大小小于源分配器的大小时，就产生了它的价值问题;在这种情况下，use_data设置为false。因为这个_Mproxy对象或它所调用的任何东西都相当小，所以即使使用带有char的std :: set作为元素类型，这个修复似乎也能工作。

我已经在32位VC12和GCC 4.8.1中使用带有char类型的std :: set进行了测试，并且发现它在两种情况下都有效。在两种情况下分配和取消分配节点时，都使用内存池。

这是完整的源代码：

#include <algorithm>

class free_list {
public:

    free_list() {}

    free_list(free_list&& other)
        : m_next(other.m_next) {
        other.m_next = nullptr;
    }

    free_list(void* data, std::size_t num_elements, std::size_t element_size) {
        init(data, num_elements, element_size);
    }

    free_list& operator=(free_list&& other) {
        if (this != &other) {
            m_next = other.m_next;
            other.m_next = nullptr;
        }
        return *this;
    }

    void init(void* data, std::size_t num_elements, std::size_t element_size) {
        union building {
            void* as_void;
            char* as_char;
            free_list* as_self;
        };

        building b;

        b.as_void = data;
        m_next = b.as_self;
        b.as_char += element_size;

        free_list* runner = m_next;
        for (std::size_t s = 1; s < num_elements; ++s) {
            runner->m_next = b.as_self;
            runner = runner->m_next;
            b.as_char += element_size;
        }
        runner->m_next = nullptr;
    }

    free_list* obtain() {
        if (m_next == nullptr) {
            return nullptr;
        }
        free_list* head = m_next;
        m_next = head->m_next;
        return head;
    }

    void give_back(free_list* ptr) {
        ptr->m_next = m_next;
        m_next = ptr;
    }

    free_list* m_next;

};

template<class T>
class pool_alloc {
    typedef pool_alloc<T> myt;

public:
    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;
    typedef T value_type;
    typedef T& reference;
    typedef const T& const_reference;
    typedef T* pointer;
    typedef const T* const_pointer;

    typedef std::false_type propagate_on_container_copy_assignment;
    typedef std::true_type propagate_on_container_move_assignment;
    typedef std::true_type propagate_on_container_swap;

    myt select_on_container_copy_construction() const {
        return *this;
    }

    template<class U> struct rebind {
        typedef pool_alloc<U> other;
    };

    ~pool_alloc() {
        clear();
    }
    pool_alloc() : data(nullptr), fl(), capacity(4096), use_data(true) {}

    pool_alloc(size_type capacity) : data(nullptr), fl(), 
        capacity(capacity), use_data(true) {}

    pool_alloc(const myt& other)
        : data(nullptr), fl(), capacity(other.capacity), 
            use_data(other.use_data) {}

    pool_alloc(myt&& other)
        : data(other.data), fl(std::move(other.fl)), capacity(other.capacity),
            use_data(other.use_data) {
        other.data = nullptr;
    }

    template<class U>
    pool_alloc(const pool_alloc<U>& other) 
        : data(nullptr), fl(), capacity(other.max_size()), use_data(true) {
        if (sizeof(T) < sizeof(U)) use_data = false;
    }


    myt& operator=(const myt& other) {
        if (*this != other) {
            clear();
            capacity = other.capacity;
            use_data = other.use_data;
        }
    }

    myt& operator=(myt&& other) {
        if (*this != other) {
            clear();
            data = other.data;
            other.data = nullptr;
            capacity = other.capacity;
            use_data = other.use_data;
            fl = std::move(other.fl);
        }
        return *this;
    }

    template<class U>
    myt& operator=(const pool_alloc<U>& other) {
        if (this != reinterpret_cast<myt*>(&other)) {
            capacity = other.max_size();
            if (sizeof(T) < sizeof(U))
                use_data = false;
            else
                use_data = true;
        }
        return *this;
    }

    static pointer address(reference ref) {
        return &ref;
    }

    static const_pointer address(const_reference ref) {
        return &ref;
    }

    size_type max_size() const {
        return capacity;
    }

    pointer allocate(size_type) {
        if (use_data) {
            if (data == nullptr) create();
            return reinterpret_cast<pointer>(fl.obtain());
        } else {
            return reinterpret_cast<pointer>(::operator new(sizeof(T)));
        }
    }

    void deallocate(pointer ptr, size_type) {
        if (use_data) {
            fl.give_back(reinterpret_cast<free_list*>(ptr));
        } else {
            ::operator delete(reinterpret_cast<void*>(ptr));
        }
    }

    template<class... Args>
    static void construct(pointer ptr, Args&&... args) {
        ::new ((void*)ptr) value_type(std::forward<Args>(args)...);
    }

    static void destroy(pointer ptr) {
        ptr->~value_type();
    }

    bool operator==(const myt& other) const {
        return reinterpret_cast<char*>(data) ==
            reinterpret_cast<char*>(other.data);
    }

    bool operator!=(const myt& other) const {
        return !operator==(other);
    }

private:

    void create() {
        size_type size = sizeof(value_type) < sizeof(free_list*) ? 
            sizeof(free_list*) : sizeof(value_type);
        data = ::operator new(capacity * size);
        fl.init(data, capacity, size);
    }

    void clear() {
        ::operator delete(data);
        data = nullptr;
    }

    void* data;
    free_list fl;
    size_type capacity;
    bool use_data;
};

template<>
class pool_alloc < void > {
public:
    template <class U> struct rebind { typedef pool_alloc<U> other; };

    typedef void* pointer;
    typedef const void* const_pointer;
    typedef void value_type;
};

template<class Container, class Alloc>
void change_capacity(Container& c, typename Alloc::size_type new_capacity) {
    Container temp(c, Alloc(new_capacity));
    c = std::move(temp);
}

由于分配器不是自动增长的（不知道如何制作这样的东西），我添加了change_capacity（）函数。