Ответ на тест распределения
Добавьте это к любому из приведенных ниже примеров:
#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 байт.
Deallocating.
Deallocating.
Выделение 120 байт.
Deallocating.
Выделение 20 байтов.
Deallocating.
Выделение 40 байт.
Deallocating.
Deallocating.
Deallocating.
Вставка: [0,0]
Вставка: [1,2]
Вставка: [2,4]
Вставка: [3,6]
Вставка: [4,8]
Deallocating.
Deallocating.
Deallocating.
плохое распределение
Обратите внимание, что после начала вставки выделений нет. Вы должны получить no выделений памяти. Как вы генерируете свою продукцию?
Распределители
Вам нужен новый распределитель. Вот кое-что, что я сделал сейчас, так что это относительно непроверено, но мне это нравится.
Создает 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;
}
}
Версия во время выполнения могла бы выделить больше места, если больше нет оставшихся слотов, что может быть полезно. Но я оставляю это тебе. (Не изменяйте размер вектора! Возможно, вы потеряете весь свой буфер. Вероятно, вам понадобится list векторов.)
Обратите внимание: если вы можете использовать Boost, у них есть такой распределитель в их библиотеке Pool . Тем не менее, их распределитель отслеживает порядок, в котором вы запрашиваете память, чтобы обеспечить обратный порядок уничтожения построения. Это превращает распределения и освобождения в O (N). (На мой взгляд, ужасный выбор.) Я действительно написал свой собственный распределитель около boost::pool<>, чтобы обойти это.