Распределитель STL на основе стека?

Ответ 1

По-видимому, является совместимым Stack Allocator из одного Говарда Хиннанта.

Он работает с использованием буфера фиксированного размера (через ссылочный объект arena) и возвращается в кучу, если запрашивается слишком много места.

Этот распределитель не имеет значения по умолчанию ctor, и поскольку Говард говорит:

Я обновил эту статью с помощью нового распределителя, который полностью соответствует С++ 11.

Я бы сказал, что для распределителя не обязательно иметь по умолчанию ctor.

Ответ 2

Определенно возможно создать полностью совместимый с С++ 11/С++ 14 распределитель стека *. Но вам нужно рассмотреть некоторые последствия для реализации и семантики распределения стека и как они взаимодействуют со стандартными контейнерами.

Здесь полный С++ 11/С++ 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, который будет распределять и освобождать объекты node в различном порядке,

Если ваш распределитель стека просто увеличивает и уменьшает указатель стека, вы получите поведение undefined, если ваши распределения и освобождения не находятся в порядке LIFO. Даже std::vector вызывает поведение undefined, если он сначала выделяет один единственный непрерывный блок из стека, затем выделяет второй стекный блок, а затем освобождает первый блок, который будет происходить каждый раз, когда вектор увеличивает его емкость до значения, которое все еще меньше, чем 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)> для создания фактического буфера стека.

Я бы также отметил, что в отличие от реализация Howard Hinnant, вышеприведенная реализация явно не проверяет, что при вызове deallocate() указатель, переданный в, является последним выделенным блоком. Реализация Hinnant просто ничего не сделает, если указатель прошел внутри, не является LIFO-упорядоченным освобождением. Это позволит вам использовать std::vector без резервирования заранее, потому что распределитель будет в основном игнорировать попытку вектора освобождения начального буфера. Но это также немного размывает семантику распределителя и полагается на поведение, которое довольно конкретно связано с тем, как известно, что std::vector работает. Я чувствую, что мы можем просто сказать, что передача любого указателя на deallocate(), который не был возвращен с помощью последнего вызова на allocate(), приведет к поведению undefined и оставьте его на этом,

* Наконец - следующее предостережение: кажется, что debatable независимо от того, определена ли функция, которая проверяет, находится ли указатель внутри границ стекового буфера поведение по стандарту. Сравнение двух двух указателей из разных буферов new/malloc 'd является, возможно, реализацией определенного поведения (даже с std::less), что, возможно, делает невозможным запись реализатора распределения колонок, совместимого со стандартами, которая возвращается к распределению кучи, (Но на практике это не имеет значения, если вы не используете 80286 на MS-DOS.)

** Наконец (действительно сейчас), также стоит отметить, что слово "стек" в распределителе стека перегружено, чтобы ссылаться как на источник памяти (массив стеков фиксированного размера), так и на метод распределения ( указатель стека указателя увеличения/уменьшения LIFO). Когда большинство программистов говорят, что им нужен распределитель стека, они думают о первом значении, не задумываясь о семантике последнего, и о том, как эти семантики ограничивают использование такого распределителя стандартными контейнерами.

Ответ 3

Распределитель STL на основе стека имеет такую ​​ограниченную полезность, что я сомневаюсь, что вы найдете много предшествующего уровня техники. Даже простой пример, который вы цитируете, быстро взрывается, если позже вы решите, что хотите скопировать или удлинить начальный lstring.

Для других STL-контейнеров, таких как ассоциативные (внутренние на основе дерева) или даже vector и deque, которые используют один или несколько непрерывных блоков ОЗУ, семантика использования памяти быстро становится неуправляемой в стеке почти любое использование в реальном мире.

Ответ 4

Это на самом деле чрезвычайно полезная практика и используется в совершенстве, например, в играх, совсем немного. Встраивание встроенной памяти в стек или в распределение структуры класса может иметь решающее значение для скорости и управления контейнером.

Чтобы ответить на ваш вопрос, это сводится к реализации контейнера stl. Если контейнер не только создает экземпляр, но также сохраняет ссылку на ваш распределитель в качестве члена, тогда вы можете пойти на создание фиксированной кучи, я обнаружил, что это не всегда так, поскольку оно не является частью спецификации. В противном случае это становится проблематичным. Одним из решений может быть упаковка контейнера, вектора, списка и т.д. Другим классом, который содержит хранилище. Затем вы можете использовать распределитель, чтобы извлечь из него. Это может потребовать много шаблонов (tm).

Ответ 5

Это действительно зависит от ваших требований, конечно, если вам нравится, вы можете создать распределитель, который работает только в стеке, но он будет очень ограниченным, поскольку один и тот же объект стека не доступен извне в программе, поскольку объект кучи будет.

Я думаю, эта статья объясняет, что распределители очень хорошо

http://www.codeguru.com/cpp/cpp/cpp_mfc/stl/article.php/c4079