具有固定插入次数的映射的内存分配

Question

我想将 n 个元素插入到预先知道 n 的映射中。我不想在每次插入时分配内存。我想要一开始就分配所有内存。有办法做到这一点吗？如果是这样，怎么办？编写某种内存分配器会有帮助吗？

我运行 GMan 的代码并得到以下输出。 GetMem 是从调用“new”时打印的，FreeMem 是从调用删除时打印的。 size 是请求的字节数，ptr 是返回的指针。显然，分配/释放是在插入期间进行的。你如何解释这一点？

GetMem 大小 40，指针 0x8420008
GetMem 大小 40，指针 0x8420038
GetMem 大小 120，指针 0x8420068
GetMem 大小 120，指针 0x84200e8
FreeMem 指针 0x8420068
FreeMem 指针 0x8420038
FreeMem 指针 0x8420008
插入：[0,0]
GetMem 大小 40，指针 0x8420008
FreeMem 指针 0x8420008
插入：[1,2]
GetMem 大小 40，指针 0x8420008
FreeMem 指针 0x8420008
插入：[2,4]
GetMem 大小 40，指针 0x8420008
FreeMem 指针 0x8420008
插入：[3,6]
GetMem 大小 40，指针 0x8420008
FreeMem 指针 0x8420008
插入：[4,8]
GetMem 大小 40，指针 0x8420008
FreeMem 指针 0x8420008
插入：[5,10]
GetMem 大小 40，指针 0x8420008
FreeMem 指针 0x8420008
GetMem 大小 40，指针 0x8420008
FreeMem 指针 0x8420008
GetMem 大小 40，指针 0x8420008
FreeMem 指针 0x8420008
GetMem 大小 40，指针 0x8420008
FreeMem 指针 0x8420008
GetMem 大小 40，指针 0x8420008
FreeMem 指针 0x8420008
FreeMem 指针 0x84200e8
St9bad_alloc

Answer 1

对分配测试的响应

将此添加到我在下面给出的任一示例中：（

#include <cstdlib>

void* allocate(size_t pAmount)
{
    std::cout << "Allocating " << pAmount << " bytes." << std::endl;

    return std::malloc(pAmount);
}

void deallocate(void* pPtr)
{
    std::cout << "Deallocating." << std::endl;

    std::free(pPtr);
}

void* operator new(size_t pAmount) // throw(std::bad_alloc)
{
    return allocate(pAmount);
}

void *operator new[](size_t pAmount) // throw(std::bad_alloc)
{
    return allocate(pAmount);
}

void *operator new(size_t pAmount, const std::nothrow_t&) throw()
{
    return allocate(pAmount);
}

void *operator new[](size_t pAmount, const std::nothrow_t&) throw()
{
    return allocate(pAmount);
}

void operator delete(void* pMemory) throw()
{
    deallocate(pMemory);
}

void operator delete[](void* pMemory) throw()
{
    deallocate(pMemory);
}

void operator delete(void* pMemory, const std::nothrow_t&) throw()
{
    deallocate(pMemory);
}

void operator delete[](void* pMemory, const std::nothrow_t&) throw()
{
    deallocate(pMemory);
}

注意，这些不是分配运算符的完全正确替换，并且用于演示。）

运行运行时大小的示例程序会给出以下输出：

分配 40 字节。
分配40字节。
分配40字节。
分配40字节。
分配40字节。
分配40字节。
分配40字节。
解除分配。
解除分配。
分配120字节。
解除分配。
分配20个字节。
解除分配。
分配40字节。
解除分配。
解除分配。
解除分配。
插入：[0,0]
插入：[1,2]
插入：[2,4]
插入：[3,6]
插入：[4,8]
解除分配。
解除分配。
解除分配。
分配不当

请注意，一旦开始插入，就不会再进行分配。您应该没有获得内存分配。您如何生成输出？

---

分配器

您需要的是一个新的分配器。这是我现在制作的东西，所以它相对未经测试，但对我来说看起来不错。

它创建一个 freelist 并使用它来释放内存。分配器的构造需要 O(N)，但分配和释放都是 O(1)。 （非常快！）此外，一旦构建完成，就不再进行内存分配。尽管空闲列表具有平均局部性，但它可能会击败您通常使用默认分配器从映射中获得的结果。

在这里：

#include <cassert>
#include <exception>
#include <limits>
#include <vector>

// gets rid of "unused parameter" warnings
#define USE(x) (void)(x)

template <typename T, size_t N>
class freelist_allocator
{
public: 
    // types
    typedef T value_type;
    typedef const T const_value_type;
    
    typedef value_type& reference;
    typedef const_value_type& const_reference;
    
    typedef value_type* pointer;
    typedef const_value_type* const_pointer;

    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;

    // ensure it can hold both a pointer and T
    struct block_type
    {
        char data[sizeof(T) > sizeof(void*) ?
                    sizeof(T) : sizeof(void*)];
    };

    typedef std::vector<block_type> buffer_type;

    // constants
    static const size_t Elements = N;

    // rebind
    template<typename U, size_t M = Elements>
    struct rebind
    {
        typedef freelist_allocator<U, M> other;
    };

    // constructor
    freelist_allocator(void) :
    mBuffer(Elements),
    mNext(0)
    {
        build_list();
    }

    freelist_allocator(const freelist_allocator&) :
    mBuffer(Elements),
    mNext(0)
    {
        build_list();
    }

    template<typename U, size_t M>
    freelist_allocator(const freelist_allocator<U, M>&) :
    mBuffer(Elements),
    mNext(0)
    {
        build_list();
    }

    // address
    pointer address(reference r)
    {
        return &r;
    }

    const_pointer address(const_reference r)
    {
        return &r;
    }

    // memory
    pointer allocate(size_type pCount, const void* = 0)
    {
        USE(pCount); // pCount unused when assert is disabled in release
        assert(pCount == 1 && "freelist_allocator is noncontiguous");

        // end of list
        if (!mNext)
            throw std::bad_alloc();

        // remove from list
        void* memory = mNext;
        mNext = data_as_ptr(*mNext);

        return static_cast<pointer>(memory);
    }

    void deallocate(pointer pPtr, size_type)
    {
        // get back our block
        block_type* b = reinterpret_cast<block_type*>(pPtr);

        // reinsert to list
        data_as_ptr(*b) = mNext;
        mNext = b;
    }

    // size
    size_type max_size(void) const
    {
        static const size_t MaxSize = 
                    std::numeric_limits<size_type>::max();
        return MaxSize / sizeof(value_type);
    }

    // construction / destruction
    void construct(pointer pPtr, const T& pT)
    {
        new (pPtr) T(pT);
    }

    void destroy(pointer pPtr)
    {
        USE(pPtr); // trivial destructor skips next line
        pPtr->~value_type();
    }   

private:
    // utility
    block_type*& data_as_ptr(block_type& pBlock)
    {
        return reinterpret_cast<block_type*&>(pBlock.data);
    }

    void build_list(void)
    {
        // build list
        for (size_t i = 1; i < mBuffer.size(); ++i)
        {
            data_as_ptr(mBuffer[i - 1]) = &mBuffer[i];
        }

        mNext = &mBuffer[0];
    }

    // members
    buffer_type mBuffer;
    block_type* mNext;
};

// equality
template<typename T, size_t N>
bool operator==(freelist_allocator<T, N> const&,
                freelist_allocator<T, N> const&)
{
    return false;
}

template<typename T, size_t N>
bool operator!=(freelist_allocator<T, N> const& pX,
                freelist_allocator<T, N> const& pY)
{
    return !(pX == pY);
}

#undef USE

并使用：

#include <iostream>
#include <map>
#include <string>

static const size_t MaxElements = 5;

typedef std::pair<int, int> pair_type;
typedef freelist_allocator<pair_type, MaxElements> allocator_type;
typedef std::map<int, int,
                    std::less<int>, allocator_type> map_type;

void do_insert(int pX, int pY, map_type& pMap)
{
    std::cout << "Inserting: [" << pX << ","
        << pY << "]" << std::endl;

    pMap.insert(std::make_pair(pX, pY));
}

int main(void)
{   
    try
    {
        map_type m;

        // just keep inserting
        for (int i = 0; i <= std::numeric_limits<int>::max() / 2; ++i)
        {
            // will throw at MaxElements insertions
            do_insert(i, i * 2, m);
        }
    }
    catch (const std::exception& e)
    {
        std::cerr << e.what() << std::endl;
    }
}

现在我已经将大小设置为编译时常量，但是您想要运行时版本，请告诉我，我会写下来。这是一个在运行时获取大小的版本：

#include <cassert>
#include <exception>
#include <limits>
#include <vector>

// gets rid of "unused parameter" warnings
#define USE(x) (void)(x)

template <typename T>
class freelist_allocator
{
public: 
    // types
    typedef T value_type;
    typedef const T const_value_type;
    
    typedef value_type& reference;
    typedef const_value_type& const_reference;
    
    typedef value_type* pointer;
    typedef const_value_type* const_pointer;

    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;

    // ensure it can hold both a pointer and T
    struct block_type
    {
        char data[sizeof(T) > sizeof(void*) ?
                    sizeof(T) : sizeof(void*)];
    };

    typedef std::vector<block_type> buffer_type;

    // rebind
    template<typename U>
    struct rebind
    {
        typedef freelist_allocator<U> other;
    };

    // constructor
    freelist_allocator(size_t pElements) :
    mBuffer(pElements),
    mNext(0)
    {
        build_list();
    }

    freelist_allocator(const freelist_allocator& pRhs) :
    mBuffer(pRhs.size()),
    mNext(0)
    {
        build_list();
    }

    template<typename U>
    freelist_allocator(const freelist_allocator<U>& pRhs) :
    mBuffer(pRhs.size()),
    mNext(0)
    {
        build_list();
    }

    // address
    pointer address(reference r)
    {
        return &r;
    }

    const_pointer address(const_reference r)
    {
        return &r;
    }

    // memory
    pointer allocate(size_type pCount, const void* = 0)
    {
        USE(pCount); // pCount unused when assert is disabled in release
        assert(pCount == 1 && "freelist_allocator is noncontiguous");

        // end of list
        if (!mNext)
            throw std::bad_alloc();

        // remove from list
        void* memory = mNext;
        mNext = data_as_ptr(*mNext);

        return static_cast<pointer>(memory);
    }

    void deallocate(pointer pPtr, size_type)
    {
        // get back our block
        block_type* b = reinterpret_cast<block_type*>(pPtr);

        // reinsert to list
        data_as_ptr(*b) = mNext;
        mNext = b;
    }

    // size
    size_type max_size(void) const
    {
        static const size_t MaxSize = 
                    std::numeric_limits<size_type>::max();
        return MaxSize / sizeof(value_type);
    }

    size_t size(void) const
    {
        return mBuffer.size();
    }

    // construction / destruction
    void construct(pointer pPtr, const T& pT)
    {
        new (pPtr) T(pT);
    }

    void destroy(pointer pPtr)
    {
        USE(pPtr); // trivial destructor skips next line
        pPtr->~value_type();
    }   

private:
    // utility
    block_type*& data_as_ptr(block_type& pBlock)
    {
        return reinterpret_cast<block_type*&>(pBlock.data);
    }

    void build_list(void)
    {
        // build list
        for (size_t i = 1; i < mBuffer.size(); ++i)
        {
            data_as_ptr(mBuffer[i - 1]) = &mBuffer[i];
        }

        mNext = &mBuffer[0];
    }

    // members
    buffer_type mBuffer;
    block_type* mNext;
};

// equality
template<typename T>
bool operator==(freelist_allocator<T> const&,
                freelist_allocator<T> const&)
{
    return false;
}

template<typename T, size_t N>
bool operator!=(freelist_allocator<T> const& pX,
                freelist_allocator<T> const& pY)
{
    return !(pX == pY);
}

#undef USE

用途：

#include <iostream>
#include <map>
#include <string>

static const size_t MaxElements = 5;

template <typename Key, typename Value>
struct map_types // helpful
{
    typedef std::pair<Key, Value> pair_type;
    typedef freelist_allocator<pair_type> allocator_type;
    typedef std::less<Key> predicate_type;
    typedef std::map<Key, Value,
                    predicate_type, allocator_type> map_type;
};

template <typename Key, typename Value, typename Map>
void do_insert(const Key& pX, const Value& pY, Map& pMap)
{
    std::cout << "Inserting: [" << pX << ","
                << pY << "]" << std::endl;

    pMap.insert(std::make_pair(pX, pY));
}

int main(void)
{   
    try
    {
        typedef map_types<int, int> map_types;

        // double parenthesis to avoid vexing parse
        map_types::map_type m((map_types::predicate_type()),
                            map_types::allocator_type(MaxElements));

        // just keep inserting
        for (int i = 0; i <= std::numeric_limits<int>::max() / 2; ++i)
        {
            do_insert(i, i * 2, m);
        }
    }
    catch (const std::exception& e)
    {
        std::cerr << e.what() << std::endl;
    }
}

如果没有更多剩余插槽，运行时版本可能会分配更多空间，这可能很有用。但我把这个留给你。 （不要调整向量的大小！你可能会丢失整个缓冲区。你可能需要一个向量的列表。）

请注意，如果你可以使用Boost，他们的内存中有这样一个分配器池库。也就是说，它们的分配器会跟踪您请求内存的顺序，以确保反向构造销毁顺序。这将分配和释放变为 O(N)。 （在我看来，这是一个糟糕的选择。）实际上，我围绕 boost::pool 编写了自己的分配器来解决这个问题。

Answer 2

使用哈希表。 unordered_map 可能不合适，因为它允许单独分配每个对象，并使用桶的“封闭寻址”而不是一个平坦的内存块。

请参阅 http://en.wikipedia.org/wiki/Hash_table#Open_addressing 了解您应该考虑的结构类型的描述。实现具有恒定访问时间和恒定插入时间的关联容器并不太困难。

不过，对删除的支持可能有点混乱，您需要在哈希表中分配相当大的空白空间，也许是您实际使用的空间的两倍，以保持地址空间整洁。

Answer 3

map 不需要像 vector 那样的方式。由于 map 在内部实现为树，因此插入很便宜（您不需要移动整个块）。另一方面，对于超过当前保留边界的向量插入，需要移动所有先前分配的元素。

也就是说，如果分配性能对您来说非常重要，您可以编写一个自定义分配器，例如从预分配的缓冲区进行分配。如果您正确实现此功能，它将比 map 使用的默认 new 更快。然而，我怀疑你是否必须走这么远。

Answer 4

std::map 不提供任何内置支持来执行此操作。但是，如果元素数量足够小，那么您可以创建成对的 std::vector 并使用 vector::reserve 方法来保留所需的空间。