基于堆栈缓冲的STL分配器？

Question

我想知道是否可行的C++标准库兼容allocator使用(固定大小)缓冲区,它存在于堆栈中.

不知怎的,似乎这个问题在SO上还没有被问过这个问题,尽管它可能已经在其他地方被暗示过了.

所以基本上,它似乎是,只要我去搜索,它应该能够创建一个使用固定大小的缓冲区的分配.现在,乍一看,这应该意味着它应该也有可能有一个使用固定大小的缓冲区,堆栈上的"生活"的分配,但它确实出现,这周围也没有普遍执行等.

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

{ ...
  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
}

这怎么可以实现？

---

这个问题的答案(感谢R. Martinho Fernandes)链接到来自铬源的基于堆栈的分配器:http://src.chromium.org/viewvc/chrome/trunk/src/base/stack_container.h

然而,这个类似乎非常特殊,特别是因为StackAllocator 它没有默认的ctor - 而且我认为每个分配器类都需要一个默认的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将导致未定义的行为,如果它首先分配从堆的单个连续块,然后分配第二堆叠块,然后将释放的第一个块,这将发生在每次矢量增加它的容量到仍然比小的值的时间stack_size.这就是您需要提前预留堆栈大小的原因.(但请参阅下面有关Howard Hinnant实施的说明.)

这带给我们的问题......

你真的想从堆栈分配器那里得到什么？

你真的想要一个通用的分配器,它允许你以不同的顺序分配和释放各种大小的内存块(比如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(),传入的指针是分配的最后一个块.如果传入的指针不是LIFO排序的释放,Hinnant的实现将不执行任何操作.这将使您能够std::vector提前使用,因为分配器将基本上忽略向量尝试释放初始缓冲区.但这也模糊了分配器的语义,并依赖于std::vector已知工作方式非常明确的行为.我的感觉是,我们不妨简单地说,传递任何指向deallocate()它不是通过返回的最后一次通话,以allocate()将导致不确定的行为,并留在这一点.

*最后 - 以下警告:检查指针是否在堆栈缓冲区边界内的函数是否是标准定义的行为似乎是有争议的.顺序 - 比较来自不同new/ malloc'd缓冲区的两个指针可以说是实现定义的行为(即使有std::less),这可能使得编写符合标准的堆栈分配器实现回到堆分配上是不可能的.(但实际上,除非你在MS-DOS上运行80286,否则无关紧要.)

**最后(现在真的),值得注意的是,堆栈分配器中的 "堆栈"这个词有点过载,以引用内存源(固定大小的堆栈数组)和分配方法(LIFO增量) /减少堆栈指针).当大多数程序员说他们想要一个堆栈分配器时,他们在考虑前者的意义而不必考虑后者的语义,以及这些语义如何限制这种分配器与标准容器的使用.

Answer 2

显然,有一个符合堆栈分配器从一个霍华德Hinnant(欣南特).

它的工作原理是使用固定大小的缓冲区(通过引用的arena对象),如果请求的空间太大,则会回落到堆中.

这个分配器没有默认的ctor,因为霍华德说:

我用一个完全符合C++ 11标准的新分配器更新了这篇文章.

我要说分配器不需要默认的ctor.

Answer 3

从 c++17 开始，这实际上很简单。完全归功于最愚蠢的分配器的作者，因为这就是它的基础。

最愚蠢的分配器是单调凹凸分配器，它将char[]资源作为其底层存储。在原始版本中，它char[]通过 放置在堆上mmap，但将其更改为指向char[]堆栈上的 a 很简单。

template<std::size_t Size=256>                                                                                                                               
class bumping_memory_resource {                                                                                                                              
  public:                                                                                                                                                    
  char buffer[Size];                                                                                                                                         
  char* _ptr;                                                                                                                                                
                                                                                                                                                             
  explicit bumping_memory_resource()                                                                                                                         
    : _ptr(&buffer[0]) {}                                                                                                                                    
                                                                                                                                                             
  void* allocate(std::size_t size) noexcept {                                                                                                                
    auto ret = _ptr;                                                                                                                                         
    _ptr += size;                                                                                                                                            
    return ret;                                                                                                                                              
  }                                                                                                                                                          
                                                                                                                                                             
  void deallocate(void*) noexcept {}                                                                                                                         
};                                                                                                                                                           

这会Size在创建时在堆栈上分配字节，默认值256。

template <typename T, typename Resource=bumping_memory_resource<256>>                                                                                        
class bumping_allocator {                                                                                                                                    
  Resource* _res;                                                                                                                                            
                                                                                                                                                             
  public:                                                                                                                                                    
  using value_type = T;                                                                                                                                      
                                                                                                                                                             
  explicit bumping_allocator(Resource& res)                                                                                                                  
    : _res(&res) {}                                                                                                                                          
                                                                                                                                                             
  bumping_allocator(const bumping_allocator&) = default;                                                                                                     
  template <typename U>                                                                                                                                      
  bumping_allocator(const bumping_allocator<U,Resource>& other)                                                                                              
    : bumping_allocator(other.resource()) {}                                                                                                                 
                                                                                                                                                             
  Resource& resource() const { return *_res; }                                                                                                               
                                                                                                                                                             
  T*   allocate(std::size_t n) { return static_cast<T*>(_res->allocate(sizeof(T) * n)); }                                                                    
  void deallocate(T* ptr, std::size_t) { _res->deallocate(ptr); }                                                                                            
                                                                                                                                                             
  friend bool operator==(const bumping_allocator& lhs, const bumping_allocator& rhs) {                                                                       
    return lhs._res == rhs._res;                                                                                                                             
  }                                                                                                                                                          
                                                                                                                                                             
  friend bool operator!=(const bumping_allocator& lhs, const bumping_allocator& rhs) {                                                                       
    return lhs._res != rhs._res;                                                                                                                             
  }                                                                                                                                                          
};                                                                                                                                                           

这是实际的分配器。请注意，向资源管理器添加重置是很简单的，这样您就可以再次从该区域的开头开始创建一个新的分配器。还可以实现环形缓冲区，但具有所有常见的风险。

至于你什么时候可能想要这样的东西：我在嵌入式系统中使用它。嵌入式系统通常对堆碎片反应不佳，因此能够使用不在堆上进行的动态分配有时会很方便。