绝对有可能创建一个完全符合 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>
默认情况下)。
需要考虑的事项:
在您继续使用堆栈分配器之前,您需要考虑您的分配模式。首先,在堆栈上使用内存缓冲区时,您需要考虑分配和释放内存的确切含义。
最简单的方法(以及上面使用的方法)是简单地为分配增加一个堆栈指针,并为解除分配而减少它。请注意,这严重限制了您在实践中如何使用分配器。如果使用正确,它将适用于例如an std::vector
(它将分配一个连续的内存块),但不适用于 an std::map
,它将以不同的顺序分配和取消分配节点对象。
如果您的堆栈分配器只是增加和减少堆栈指针,那么如果您的分配和解除分配不是 LIFO 顺序,您将获得未定义的行为。如果它首先从堆栈中分配一个连续的块,然后分配第二个堆栈块,然后释放第一个块,那么即使 anstd::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
没有提前保留的情况下使用 an,因为分配器基本上会忽略向量释放初始缓冲区的尝试。但这也稍微模糊了分配器的语义,并且依赖于非常具体地绑定到std::vector
已知工作方式的行为。我的感觉是,我们不妨简单地说,传递任何未deallocate()
通过最后一次调用将allocate()
导致未定义的行为并保持不变。
*最后 - 以下警告:检查指针是否在堆栈缓冲区边界内的函数是否是标准定义的行为似乎是有争议的。对来自不同new
/ malloc
'd 缓冲区的两个指针进行顺序比较可以说是实现定义的行为(即使使用std::less
),这可能使得编写符合标准的堆栈分配器实现依赖于堆分配是不可能的。(但实际上这无关紧要,除非您在 MS-DOS 上运行 80286。)
** 最后(真的是现在),还值得注意的是,堆栈分配器中的“堆栈”一词有点重载,既指内存源(一个固定大小的栈数组),又指分配方法(一个 LIFO 增量/递减堆栈指针)。当大多数程序员说他们想要一个堆栈分配器时,他们考虑的是前者的含义,而不必考虑后者的语义,以及这些语义如何限制这种分配器与标准容器的使用。