配賦テストへの対応
以下に示すサンプルのいずれかにこれを追加します。
#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) です。(非常に高速です!) また、一度構築されると、それ以上のメモリ割り当ては行われません。フリーリストには平均的な局所性がありますが、デフォルトのアロケーターを使用してマップから通常得られるものよりもおそらく優れています。
ここにあります：
#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 ライブラリにそのようなアロケータがあることに注意してください。つまり、それらのアロケーターは、メモリを要求する順序を追跡し、逆の構築破壊順序を保証します。これにより、割り当てと割り当て解除が O(N) に変わります。(私の意見ではひどい選択です。) 実際、私はこれを回避するために独自のアロケーターを書きboost::pool<>ました。