c++ - 基于堆栈缓冲区的STL分配器？

Question

我想知道是否有一个符合C++标准库要求的allocator，它使用生活在堆栈中的(固定大小的)缓冲区，是否可行。

以某种方式，尽管在其他地方可能已经隐式回答了这个问题，但似乎还没有以这种方式问过这个问题。

基本上，就我的搜索而言，似乎应该可以创建使用固定大小缓冲区的分配器。现在，乍看之下，这应该意味着还应该有一个使用固定大小的缓冲区的“分配器”，该缓冲区在栈上“存在”，但确实确实没有广泛的实现。

让我举一个例子说明我的意思:

{ ...
  char buf[512];
  typedef ...hmm?... local_allocator; // should use buf
  typedef std::basic_string<char, std::char_traits<char>, local_allocator> lstring;
  lstring str; // string object of max. 512 char
}

这将如何实现？

answer to this other question(感谢R. Martinho Fernandes)从 Chrome 源链接到基于堆栈的分配器: http://src.chromium.org/viewvc/chrome/trunk/src/base/stack_container.h

但是，此类似乎异常特殊，尤其是因为此 StackAllocator没有默认的ctor －而且我在想 every allocator class needs a default ctor。

Answer 1

创建完全符合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首先从堆栈中分配一个连续的块，然后分配第二个堆栈块，然后释放第一个块，则即使每当 vector 将其容量增加到小于该值时，都会发生undefined行为。 stack_size。这就是为什么您需要提前保留堆栈大小的原因。 (但请参阅以下有关Howard Hinnant实现的说明。)

这带给我们一个问题...

您真正想要堆栈分配器有什么？

您实际上是否想要一个通用分配器，该分配器将允许您以不同的顺序分配和释放各种大小的内存块(例如 malloc)，除了它是从预分配的堆栈缓冲区中提取而不是调用 sbrk之外？如果是这样，那么您基本上是在谈论实现一个通用分配器，该分配器以某种方式维护一个内存块的空闲列表，只有用户才能为其提供一个预先存在的堆栈缓冲区。这是一个更加复杂的项目。 (如果空间用完了怎么办？抛出 std::bad_alloc？退回到堆上？)

上面的实现假定您想要一个分配器，该分配器将仅使用LIFO分配模式，并且如果空间不足，将使用另一个分配器。这对于 std::vector效果很好，它将始终使用可以预先保留的单个连续缓冲区。当 std::vector需要较大的缓冲区时，它将分配较大的缓冲区，复制(或移动)较小缓冲区中的元素，然后取消分配较小的缓冲区。当 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

同样，这对于vector来说也可以正常工作-但您需要问自己，您打算对堆栈分配器执行什么操作。如果您想要一个恰好从堆栈缓冲区中提取的通用内存分配器，那么您正在谈论的是一个更加复杂的项目。但是，一个简单的堆栈分配器仅递增和递减堆栈指针就可用于一组有限的用例。请注意，对于非POD类型，您将需要使用 std::aligned_storage<T, alignof(T)>创建实际的堆栈缓冲区。

我还要注意，与 Howard Hinnant's implementation不同，上述实现未明确检查调用 deallocate()时传入的指针是分配的最后一个块。如果传入的指针不是由LIFO排序的释放，则Hinnant的实现将完全不执行任何操作。这将使您无需预先保留就可以使用 std::vector，因为分配器基本上将忽略 vector 尝试取消分配初始缓冲区的尝试。但这也使分配器的语义有些模糊，并且依赖于行为，该行为与 std::vector已知的工作方式特别相关。我的感觉是，我们也可以简单地说，将未通过 上次调用返回的未传递给 deallocate()的任何指针传递给 allocate()，将导致未定义的行为，并将其留在那。

*最后-以下警告:似乎是否已通过标准定义了检查指针是否在堆栈缓冲区边界内的函数，即 debatable。比较来自不同 new / malloc'd缓冲区的两个指针的顺序可以说是实现定义的行为(即使使用 std::less)，这也许使得编写符合标准的堆栈分配器实现成为不可能，该实现依赖于堆分配。 (但是实际上，除非您在MS-DOS上运行80286，否则这并不重要。)

**最后(现在是真的)，还值得注意的是，堆栈分配器中的“堆栈”一词是重载的，既指内存源(固定大小的堆栈数组)又指分配方法(LIFO增量) /减量堆栈指针)。当大多数程序员说他们想要堆栈分配器时，他们在考虑前一种含义而不必考虑后者的语义，以及这些语义如何限制将这种分配器与标准容器一起使用。