寻找类似 C++ STL 的向量类但使用堆栈存储

Looking for C++ STL-like vector class but using stack storage

提问by Zan Lynx

Before I write my own I will ask all y'all.

在我自己写之前，我会问大家。

I'm looking for a C++ class that is almost exactly like a STL vector but stores data into an array on the stack. Some kind of STL allocator class would work also, but I am trying to avoid any kind of heap, even static allocated per-thread heaps (although one of those is my second choice). The stack is just more efficient.

我正在寻找一个 C++ 类，它几乎与 STL 向量完全一样，但将数据存储到堆栈上的数组中。某种 STL 分配器类也可以工作，但我试图避免任何类型的堆，甚至是静态分配的每线程堆（尽管其中一个是我的第二选择）。堆栈只是更有效。

It needs to be almost a drop in replacement for current code that uses a vector.

它几乎需要替代使用向量的当前代码。

For what I was about to write myself I was thinking of something like this:

对于我要自己写的东西，我在想这样的事情：

char buffer[4096];
stack_vector<match_item> matches(buffer, sizeof(buffer));

Or the class could have buffer space allocated internally. Then it would look like:

或者该类可以在内部分配缓冲区空间。然后它看起来像：

stack_vector<match_item, 256> matches;

I was thinking it would throw std::bad_alloc if it runs out of space, although that should not ever happen.

我认为如果空间不足，它会抛出 std::bad_alloc ，尽管这不应该发生。

Update

更新

Using Chromium's stack_container.h works great!

使用 Chromium 的 stack_container.h 效果很好！

The reason I hadn't thought of doing it this way myself is that I have always overlooked the allocator object parameter to the STL collection constructors. I have used the template parameter a few times to do static pools but I'd never seen code or written any that actually used the object parameter. I learned something new. Very cool!

我自己没有想到这样做的原因是我一直忽略了 STL 集合构造函数的分配器对象参数。我曾多次使用模板参数来做静态池，但我从未见过代码或编写任何实际使用对象参数的代码。我学到了一些新东西。很酷！

The code is a bit messy and for some reason GCC forced me to declare the allocator as an actual item instead of constructing it into vector's allocator parameter. It went from something like this:

代码有点乱，出于某种原因，GCC 迫使我将分配器声明为实际项目，而不是将其构造为向量的分配器参数。它来自这样的事情：

typedef std::pair< const char *, const char * > comp_list_item;
typedef std::vector< comp_list_item > comp_list_type;

comp_list_type match_list;
match_list.reserve(32);

To this:

对此：

static const size_t comp_list_alloc_size = 128;
typedef std::pair< const char *, const char * > comp_list_item;
typedef StackAllocator< comp_list_item, comp_list_alloc_size > comp_list_alloc_type;
typedef std::vector< comp_list_item, comp_list_alloc_type > comp_list_type;

comp_list_alloc_type::Source match_list_buffer;
comp_list_alloc_type match_list_alloc( &match_list_buffer );
comp_list_type match_list( match_list_alloc );
match_list.reserve( comp_list_alloc_size );

And I have to repeat that whenever I declare a new one. But it works just like I wanted.

每当我宣布一个新的时，我都必须重复这一点。但它就像我想要的那样工作。

I noticed that stack_container.h has a StackVector defined and I tried using it. But it doesn't inherit from vector or define the same methods so it wasn't a drop-in replacement. I didn't want to rewrite all the code using the vector so I gave up on it.

我注意到 stack_container.h 定义了一个 StackVector，我尝试使用它。但它没有从 vector 继承或定义相同的方法，所以它不是一个简单的替代品。我不想使用向量重写所有代码，所以我放弃了它。

采纳答案by Johannes Schaub - litb

You don't have to write a completely new container class. You can stick with your STL containers, but change the second parameter of for example std::vectorto give it your custom allocator which allocates from a stack-buffer. The chromium authors wrote an allocator just for this:

您不必编写全新的容器类。您可以坚持使用 STL 容器，但更改例如的第二个参数以为std::vector其提供从堆栈缓冲区分配的自定义分配器。铬的作者为此编写了一个分配器：

https://chromium.googlesource.com/chromium/chromium/+/master/base/stack_container.h

https://chromium.googlesource.com/chromium/chromium/+/master/base/stack_container.h

It works by allocating a buffer where you say how big it is. You create the container and call container.reserve(buffer_size);. If you overflow that size, the allocator will automatically get elements from the heap (since it is derived from std::allocator, it will in that case just use the facilities of the standard allocator). I haven't tried it, but it looks like it's from google so i think it's worth a try.

它的工作原理是在你说它有多大的地方分配一个缓冲区。您创建容器并调用container.reserve(buffer_size);. 如果超出该大小，分配器将自动从堆中获取元素（因为它派生自std::allocator，在这种情况下它将只使用标准分配器的功能）。我还没有尝试过，但它看起来像是来自谷歌，所以我认为值得一试。

Usage is like this:

用法是这样的：

StackVector<int, 128> s;
s->push_back(42); // overloaded operator->
s->push_back(43);

// to get the real std::vector. 
StackVector<int, 128>::ContainerType & v = s.container();
std::cout << v[0] << " " << v[1] << std::endl;

回答by Yury

It seems that boost::static_vectoris what you are searching. From the documentation:

似乎boost::static_vector是您正在搜索的内容。从文档：

static_vector is an hybrid between vector and array: like vector, it's a sequence container with contiguous storage that can change in size, along with the static allocation, low overhead, and fixed capacity of array. static_vector is based on Adam Wulkiewicz and Andrew Hundt's high-performance varray class.

The number of elements in a static_vector may vary dynamically up to a fixed capacity because elements are stored within the object itself similarly to an array.

static_vector 是vector 和array 的混合体：与vector 一样，它是一个序列容器，具有连续的存储空间，可以改变大小，以及静态分配、低开销和固定容量的数组。static_vector 基于 Adam Wulkiewicz 和 Andrew Hundt 的高性能 varray 类。

static_vector 中的元素数量可能会动态变化，直到固定容量，因为元素存储在对象本身中，类似于数组。

回答by Michael Burr

Some options you may want to look at:

您可能想查看的一些选项：

STLSoft by Matthew Wilson (author of Imperfect C++) has an auto_buffertemplate class that puts a default array on the stack but if it grows larger than the stack allocation will grab the memory from the heap. I like this class - if you know that your container sizes are generally going to be bounded by a rather low limit, then you get the speed of a local, stack allocated array. However, for the corner cases where you need more memory, it all still works properly.

Matthew Wilson（Imperfect C++ 的作者）的 STLSoft 有一个auto_buffer模板类，该类将默认数组放在堆栈上，但如果它增长到大于堆栈分配，将从堆中获取内存。我喜欢这个类 - 如果您知道您的容器大小通常会受到一个相当低的限制，那么您将获得本地堆栈分配数组的速度。但是，对于需要更多内存的极端情况，它仍然可以正常工作。

http://www.stlsoft.org/doc-1.9/classstlsoft_1_1auto__buffer.html

http://www.stlsoft.org/doc-1.9/classstlsoft_1_1auto__buffer.html

Note that the implementation I use myself is not STLSoft's, but an implementation that borrows heavily from it.

请注意，我自己使用的实现不是 STLSoft 的，而是大量借用它的实现。

"The Lazy Programmer" did a post for an implementation of a container that uses alloca()for the storage. I'm not a fan of this technique, but I'll let you decide for yourself if it's what you want:

“懒惰的程序员”为alloca()用于存储的容器的实现做了一个帖子。我不喜欢这种技术，但我会让你自己决定它是否是你想要的：

http://tlzprgmr.wordpress.com/2008/04/02/c-how-to-create-variable-length-arrays-on-the-stack/

http://tlzprgmr.wordpress.com/2008/04/02/c-how-to-create-variable-length-arrays-on-the-stack/

Then there's boost::arraywhich has none of the dynamic sizing behavior of the first two, but gives you more of the vectorinterface than just using pointers as iterators that you get with built-in arrays (ie., you get begin(), end(), size(), etc.):

再有就是boost::array它有没有动态调整大小的前两个行为，但给你更多的vector接口比只用指针作为迭代器，你用得到内置阵列（即，你得到的。begin()，end()，size()等）：

http://www.boost.org/doc/libs/1_37_0/doc/html/boost/array.html

http://www.boost.org/doc/libs/1_37_0/doc/html/boost/array.html

回答by denis

If speed matters, I see run times

如果速度很重要，我会看到运行时间

• 4 ns int[10], fixed size on the stack
• 40 ns <vector>
• 1300 ns <stlsoft/containers/pod_vector.hpp>

• 4 ns int[10]，堆栈上的固定大小
• 40 纳秒 <vector>
• 1300 纳秒 <stlsoft/containers/pod_vector.hpp>

for one stupid test below -- just 2 push, v[0] v[1], 2 pop, on one platform, mac ppc, gcc-4.2 -O3 only. (I have no idea if Apple have optimized their stl.)

对于下面的一个愚蠢的测试——只有 2 次推送，v[0] v[1]，2 次弹出，在一个平台上，mac ppc，gcc-4.2 -O3。（我不知道 Apple 是否优化了他们的 stl。）

Don't accept any timings you haven't faked yourself. And of course every usage pattern is different. Nonetheless factors > 2 surprise me.

不要接受任何你没有伪造自己的时间。当然，每种使用模式都是不同的。尽管如此，> 2 的因素让我感到惊讶。

(If mems, memory accesses, are the dominant factor in runtimes, what are all the extra mems in the various implementations ?)

（如果内存、内存访问是运行时的主要因素，那么各种实现中的所有额外内存是什么？）

#include <stlsoft/containers/pod_vector.hpp>
#include <stdio.h>
using namespace std;

int main( int argc, char* argv[] )
{
        // times for 2 push, v[0] v[1], 2 pop, mac g4 ppc gcc-4.2 -O3 --
    // Vecint10 v;  // stack int[10]: 4 ns
    vector<int> v;  // 40 ns
    // stlsoft::pod_vector<int> v;  // 1300 ns
    // stlsoft::pod_vector<int, std::allocator<int>, 64> v;

    int n = (argv[1] ? atoi( argv[1] ) : 10) * 1000000;
    int sum = 0;

    while( --n >= 0 ){
        v.push_back( n );
        v.push_back( n );
        sum += v[0] + v[1];
        v.pop_back();
        v.pop_back();
    }
    printf( "sum: %d\n", sum );

}

回答by Mark Ransom

You can use your own allocator for std::vector and have it allocate chunks of your stack-based storage, similar to your example. The allocator class is the second part of the template.

您可以将自己的分配器用于 std::vector 并让它分配基于堆栈的存储块，类似于您的示例。分配器类是模板的第二部分。

Edit: I've never tried this, and looking at the documentation further leads me to believe you can't write your own allocator. I'm still looking into it.

编辑：我从来没有尝试过这个，查看文档进一步让我相信你不能编写自己的分配器。我还在研究它。

回答by Boojum

tr1::array partially matches your description. It lacks things like push___back(), etc., but it might be worth taking a look at as a starting point. Wrapping it and adding an index to the "back" to support push_back(), etc. should be fairly easy.

tr1::array 部分符合您的描述。它缺少 push___back() 等内容，但作为起点可能值得一看。包装它并向“back”添加索引以支持 push_back() 等应该相当容易。

回答by Charlie Martin

Why do you want to put it on the stackparticularly? If you have an implementation of alloca(), you could buld a class allocator using that instead of malloc(), but your idea of using a statically allocated array is even better: it's just as fast on most architectures, and you don't risk stack corruption of you mess up.

你为什么特别想把它放在堆栈上？如果您有 alloca() 的实现，您可以使用它而不是 malloc() 构建一个类分配器，但是您使用静态分配数组的想法甚至更好：它在大多数架构上都一样快，而您没有风险堆栈损坏你搞砸了。

回答by Sebastian Graf

It may be the case that you are using Qt. Then You might want to go for QVarLengthArray(docs). It sits basically between std::vectorand std::array, allocating statically for a certain amount and falling back to heap allocation if necessary.

可能是您使用 Qt 的情况。那么你可能想要QVarLengthArray（docs）。它基本上位于std::vector和之间std::array，静态分配一定数量，并在必要时回退到堆分配。

I'd prefer the boost version if I was using it though.

如果我使用它，我更喜欢 boost 版本。

回答by fandyushin

Boost have this. Its called small_vector

Boost有这个。它叫做small_vector

small_vector is a vector-like container optimized for the case when it contains few elements. It contains some preallocated elements in-place, which allows it to avoid the use of dynamic storage allocation when the actual number of elements is below that preallocated threshold. small_vector is inspired by LLVM's SmallVector container. Unlike static_vector, small_vector's capacity can grow beyond the initial preallocated capacity.

small_vector is convertible to small_vector_base, a type that is independent from the preallocated element count, allowing client code that does not need to be templated on that N argument. small_vector inherits all vector's member functions so it supports all standard features like emplacement, stateful allocators, etc.

small_vector 是一个类似矢量的容器，针对包含很少元素的情况进行了优化。它包含一些就地预分配元素，当实际元素数量低于预分配阈值时，它可以避免使用动态存储分配。small_vector 的灵感来自 LLVM 的 SmallVector 容器。与 static_vector 不同，small_vector 的容量可以增长到超出初始预分配容量。

small_vector 可转换为 small_vector_base，这是一种独立于预分配元素计数的类型，允许客户端代码不需要在该 N 参数上进行模板化。small_vector 继承了 vector 的所有成员函数，因此它支持所有标准功能，如定位、有状态分配器等。

回答by MathuSum Mut

If you would like to allocate on the stack but do not want to pre-define a maximum size at compile-time, you can use StackVector, a small implementation that can be used like this:

如果您想在堆栈上分配但不想在编译时预定义最大大小，您可以使用StackVector，这是一个可以像这样使用的小实现：

new_stack_vector(Type, name, size)

where Typeis the type of element in the vector, nameis the variable name of the vector, and sizeis the maximum number of elements to allow in the vector.

其中Type是向量中元素的类型，name是向量的变量名称， 是向量size中允许的最大元素数。

sizecan be variable and does not need to be a compile-time constant! :D

size可以是变量，不需要是编译时常量！:D

Example:

例子：

new_stack_vector(int, vec, 100); //like vector<int> vec; vec.reserve(100); but on the stack :)
vec.push_back(10); //added "10" as the first item in the vector

...and that's all!

...就这样！

Disclaimer: Never use very large array sizes on the stack in general. Like you should not use int var[9999999], you should similarly not use new_stack_vector(int, vec, 9999999)! Use responsibly.

免责声明：通常不要在堆栈上使用非常大的数组大小。就像你不应该使用int var[9999999]，你同样不应该使用new_stack_vector(int, vec, 9999999)！负责任地使用。