c++ - 具有固定插入次数的 Map 的内存分配

标签 c++ memory stl map allocation

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

我运行了 GMan 的代码并得到了以下输出。 GetMem 从对“new”的调用中打印出来，而 FreeMem 从对 delete 的调用中打印出来。 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

最佳答案

分配测试响应

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

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

(注意，这些不是分配运算符的完全正确替换，仅供演示。)

运行运行时大小的示例程序会得到以下输出:

Allocating 40 bytes.
Allocating 40 bytes.
Allocating 40 bytes.
Allocating 40 bytes.
Allocating 40 bytes.
Allocating 40 bytes.
Allocating 40 bytes.
Deallocating.
Deallocating.
Allocating 120 bytes.
Deallocating.
Allocating 20 bytes.
Deallocating.
Allocating 40 bytes.
Deallocating.
Deallocating.
Deallocating.
Inserting: [0,0]
Inserting: [1,2]
Inserting: [2,4]
Inserting: [3,6]
Inserting: [4,8]
Deallocating.
Deallocating.
Deallocating.
bad allocation

注意一旦插入开始就没有分配。您应该没有 内存分配。您如何生成输出？

分配器

您需要的是一个新的分配器。这是我现在做的东西，所以它相对未经测试，但我觉得不错。

它创建一个 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;
    }
}

如果没有更多剩余插槽，运行时版本可能会分配更多空间，这很有用。但我把它留给你。 (不要调整 vector 的大小!您可能会丢失整个缓冲区。您可能需要 list 的 vector 。)

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

关于c++ - 具有固定插入次数的 Map 的内存分配，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2528317/

上一篇：c++ - 它应该在命名空间中吗？

下一篇：c++ - GCC、Unicode 和 __FUNCTION__

相关文章：

c++ - 交叉依赖而不向前声明所有使用的功能？

c++ - 如何在循环中使用 cin.ignore

c++ - 在 C++ 中定义可以容纳六个值的最小可能数据类型

c++ - 带有指针容器的自动类型推导

c++ - reinterpret_cast 从原始内存中获取的指针重新分配是否会导致 UB？

c++ - 在初始化期间将成员地址发送给父类安全吗？

c++ - 如何从内存中读取，就像使用 iostream 从文件中读取一样？

jquery - 将 Bootstrap 与 jQuery 一起使用会导致大量内存使用

C++ STL 101 : Overload function causes build error

c++ - 如何使用 STL 对字符串进行不区分大小写的二分搜索

©2024 IT工具网  联系我们