对分配测试的反应
将此添加到我在下面给出的任何一个示例中：
#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]
释放。
解除分配。
解除分配。
分配不当
请注意，一旦插入开始，就没有分配。您应该没有内存分配。你是如何产生你的输出的？
分配器
你需要的是一个新的分配器。这是我现在制作的东西，所以它相对未经测试，但对我来说看起来不错。
它创建一个空闲列表并使用它来分配内存。分配器的构造需要 O(N)，但分配和释放都是 O(1)。（非常快！）此外，一旦构建完成，就不会再进行内存分配了。尽管 freelists 具有平均位置，但它可能会超过您通常使用默认分配器从地图中获得的内容。
这里是：
#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;
}
}
如果没有更多剩余插槽，运行时版本可能会分配更多空间，这可能很有用。但我把它留给你。（不要调整向量的大小！您可能会丢失整个缓冲区。您list可能需要一个向量。）
请注意，如果您可以使用 Boost，他们的Pool library中有这样的分配器。也就是说，他们的分配器会跟踪您请求内存的顺序，以确保逆向构造破坏顺序。这将分配和释放转换为 O(N)。（在我看来，这是一个糟糕的选择。）我实际上编写了自己的分配器boost::pool<>来解决这个问题。