определенно возможно создать полностью соответствующий C ++ 11 / C ++ 14 распределитель стека *.Но вам необходимо рассмотреть некоторые из возможных последствий реализации и семантики распределения стека и того, как они взаимодействуют со стандартными контейнерами.
Здесь приведен полностью соответствующий C ++ 11 / C ++ 14 распределитель стека (также размещен на хосте).на моем github ):
#include <functional>
#include <memory>
template <class T, std::size_t N, class Allocator = std::allocator<T>>
class stack_allocator
{
public:
typedef typename std::allocator_traits<Allocator>::value_type value_type;
typedef typename std::allocator_traits<Allocator>::pointer pointer;
typedef typename std::allocator_traits<Allocator>::const_pointer const_pointer;
typedef typename Allocator::reference reference;
typedef typename Allocator::const_reference const_reference;
typedef typename std::allocator_traits<Allocator>::size_type size_type;
typedef typename std::allocator_traits<Allocator>::difference_type difference_type;
typedef typename std::allocator_traits<Allocator>::const_void_pointer const_void_pointer;
typedef Allocator allocator_type;
public:
explicit stack_allocator(const allocator_type& alloc = allocator_type())
: m_allocator(alloc), m_begin(nullptr), m_end(nullptr), m_stack_pointer(nullptr)
{ }
explicit stack_allocator(pointer buffer, const allocator_type& alloc = allocator_type())
: m_allocator(alloc), m_begin(buffer), m_end(buffer + N),
m_stack_pointer(buffer)
{ }
template <class U>
stack_allocator(const stack_allocator<U, N, Allocator>& other)
: m_allocator(other.m_allocator), m_begin(other.m_begin), m_end(other.m_end),
m_stack_pointer(other.m_stack_pointer)
{ }
constexpr static size_type capacity()
{
return N;
}
pointer allocate(size_type n, const_void_pointer hint = const_void_pointer())
{
if (n <= size_type(std::distance(m_stack_pointer, m_end)))
{
pointer result = m_stack_pointer;
m_stack_pointer += n;
return result;
}
return m_allocator.allocate(n, hint);
}
void deallocate(pointer p, size_type n)
{
if (pointer_to_internal_buffer(p))
{
m_stack_pointer -= n;
}
else m_allocator.deallocate(p, n);
}
size_type max_size() const noexcept
{
return m_allocator.max_size();
}
template <class U, class... Args>
void construct(U* p, Args&&... args)
{
m_allocator.construct(p, std::forward<Args>(args)...);
}
template <class U>
void destroy(U* p)
{
m_allocator.destroy(p);
}
pointer address(reference x) const noexcept
{
if (pointer_to_internal_buffer(std::addressof(x)))
{
return std::addressof(x);
}
return m_allocator.address(x);
}
const_pointer address(const_reference x) const noexcept
{
if (pointer_to_internal_buffer(std::addressof(x)))
{
return std::addressof(x);
}
return m_allocator.address(x);
}
template <class U>
struct rebind { typedef stack_allocator<U, N, allocator_type> other; };
pointer buffer() const noexcept
{
return m_begin;
}
private:
bool pointer_to_internal_buffer(const_pointer p) const
{
return (!(std::less<const_pointer>()(p, m_begin)) && (std::less<const_pointer>()(p, m_end)));
}
allocator_type m_allocator;
pointer m_begin;
pointer m_end;
pointer m_stack_pointer;
};
template <class T1, std::size_t N, class Allocator, class T2>
bool operator == (const stack_allocator<T1, N, Allocator>& lhs,
const stack_allocator<T2, N, Allocator>& rhs) noexcept
{
return lhs.buffer() == rhs.buffer();
}
template <class T1, std::size_t N, class Allocator, class T2>
bool operator != (const stack_allocator<T1, N, Allocator>& lhs,
const stack_allocator<T2, N, Allocator>& rhs) noexcept
{
return !(lhs == rhs);
}
Этот распределитель использует предоставленный пользователем буфер фиксированного размера в качестве начального источника памяти, а затем возвращается к вторичному распределителю (std::allocator<T> по умолчанию), когда ему не хватает места.
На что следует обратить внимание:
Прежде чем вы просто начнете использовать распределитель стеков, вам необходимо рассмотреть шаблоны распределения.Во-первых, при использовании буфера памяти в стеке необходимо учитывать, что именно это означает для выделения и освобождения памяти.
Самый простой метод (и метод, использованный выше) - это простоувеличить указатель стека для выделения и уменьшить его для освобождения.Обратите внимание, что строго ограничивает возможности использования распределителя на практике.Он будет нормально работать, скажем, для std::vector (который выделит один непрерывный блок памяти), если используется правильно, но не будет работать, скажем, для std::map, который будет выделять и освобождать объекты узлов в различном порядке.
Если ваш распределитель стека просто увеличивает и уменьшает указатель стека, то вы получите неопределенное поведение, если ваши выделения и освобождения не в порядке LIFO.Даже std::vector вызовет неопределенное поведение, если сначала выделит один непрерывный блок из стека, затем выделит второй блок стека, а затем освободит первый блок, что будет происходить каждый раз, когда вектор увеличивает свою емкость до значения, которое все ещеменьше чем stack_size.Вот почему вам нужно заранее зарезервировать размер стека.(Но см. Примечание ниже относительно реализации Говарда Хиннанта.)
Что приводит нас к вопросу ...
Что вы действительно хотите от распределителя стека?
Действительно ли вам нужен распределитель общего назначения, который позволит вам выделять и освобождать блоки памяти разных размеров в различном порядке (например, malloc), за исключением того, что он извлекается из предварительно выделенного стекового буфера вместозвонить sbrk?Если это так, вы в основном говорите о реализации распределителя общего назначения, который каким-то образом поддерживает свободный список блоков памяти, только пользователь может предоставить ему уже существующий буфер стека.Это гораздо более сложный проект.(И что он должен делать, если ему не хватает места? Бросить std::bad_alloc? Откатиться в кучу?)
Вышеприведенная реализация предполагает, что вам нужен распределитель, который будет просто использовать шаблоны распределения LIFO и использовать другойраспределитель, если ему не хватает места.Это прекрасно работает для std::vector, который всегда будет использовать один непрерывный буфер, который можно зарезервировать заранее.Когда std::vector требуется больший буфер, он выделит больший буфер, скопирует (или переместит) элементы в меньший буфер, а затем освободит меньший буфер.Когда вектор запрашивает больший буфер, вышеприведенная реализация stack_allocator просто возвращается к вторичному распределителю (который по умолчанию равен std::allocator)
Так, например:
const static std::size_t stack_size = 4;
int buffer[stack_size];
typedef stack_allocator<int, stack_size> allocator_type;
std::vector<int, allocator_type> vec((allocator_type(buffer))); // double parenthesis here for "most vexing parse" nonsense
vec.reserve(stack_size); // attempt to reserve space for 4 elements
std::cout << vec.capacity() << std::endl;
vec.push_back(10);
vec.push_back(20);
vec.push_back(30);
vec.push_back(40);
// Assert that the vector is actually using our stack
//
assert(
std::equal(
vec.begin(),
vec.end(),
buffer,
[](const int& v1, const int& v2) {
return &v1 == &v2;
}
)
);
// Output some values in the stack, we see it is the same values we
// inserted in our vector.
//
std::cout << buffer[0] << std::endl;
std::cout << buffer[1] << std::endl;
std::cout << buffer[2] << std::endl;
std::cout << buffer[3] << std::endl;
// Attempt to push back some more values. Since our stack allocator only has
// room for 4 elements, we cannot satisfy the request for an 8 element buffer.
// So, the allocator quietly falls back on using std::allocator.
//
// Alternatively, you could modify the stack_allocator implementation
// to throw std::bad_alloc
//
vec.push_back(50);
vec.push_back(60);
vec.push_back(70);
vec.push_back(80);
// Assert that we are no longer using the stack buffer
//
assert(
!std::equal(
vec.begin(),
vec.end(),
buffer,
[](const int& v1, const int& v2) {
return &v1 == &v2;
}
)
);
// Print out all the values in our vector just to make sure
// everything is sane.
//
for (auto v : vec) std::cout << v << ", ";
std::cout << std::endl;
См .: http://ideone.com/YhMZxt
Опять же, это хорошо работает для вектора - но вы должны спросить себя, что именно вы собираетесь делать с распределителем стека.Если вам нужен распределитель памяти общего назначения, который просто получается из стекового буфера, вы говорите о гораздо более сложном проекте.Однако простой распределитель стека, который просто увеличивает и уменьшает указатель стека, будет работать для ограниченного набора вариантов использования.Обратите внимание, что для типов, отличных от POD, вам нужно использовать std::aligned_storage<T, alignof(T)> для создания фактического стекового буфера.
Я бы также отметил, что в отличие от реализации Говарда Хиннанта, вышеприведенная реализация явно не проверяет, что при вызове deallocate() переданный указатель является последним выделенным блоком. Реализация Hinnant просто ничего не сделает, если переданный указатель не является LIFO-упорядоченным освобождением. Это позволит вам использовать std::vector без предварительного резервирования, поскольку распределитель будет в основном игнорировать попытку вектора освободить начальный буфер. Но это также немного размывает семантику распределителя и зависит от поведения, которое довольно специфично связано с тем, как, как известно, работает std::vector. Я чувствую, что мы можем просто сказать, что передача любого указателя на deallocate(), который не был , возвращенный через последний вызов на allocate(), приведет к неопределенному поведению и оставит это при этом.
* Наконец - следующее предостережение: это, кажется, спорно или нет функции, которая проверяет, является ли указатель в пределах буфера стека даже определить поведение стандарта. Сравнение порядка двух указателей из разных буферов new / malloc, возможно, является поведением, определяемым реализацией (даже с std::less), которое, возможно, делает невозможным написание реализации распределителя стека, соответствующей стандартам, которая использует распределение кучи , (Но на практике это не имеет значения, если вы не используете 80286 в MS-DOS.)
** Наконец (действительно сейчас), также стоит отметить, что слово "стек" в распределителе стека является своего рода перегруженным, чтобы ссылаться как на источник памяти ( стековый массив фиксированного размера) и метод выделения (указатель стека приращения / уменьшения LIFO). Когда большинство программистов говорят, что им нужен распределитель стека, они думают о первом значении, не обязательно учитывая семантику последнего, и о том, как эта семантика ограничивает использование такого распределителя со стандартными контейнерами.