寻找类似C ++ STL的vector类，但是使用栈存储

在我写我自己之前，我会问你们所有人。

我正在寻找一个几乎完全像STL向量的C ++类，但将数据存储到堆栈中的一个数组中。 某种types的STL分配器类也可以工作，但我试图避免任何堆，甚至静态分配每个线程堆（虽然其中之一是我的第二select）。 堆栈效率更高。

对于使用vector的当前代码来说，它几乎是一个代替。

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

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

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

 stack_vector<match_item, 256> matches; 

我以为它会抛出std :: bad_alloc，如果它运行的空间，尽pipe这不应该发生。

更新

使用Chromium的stack_container.h很好用！

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

该代码有点混乱，由于某些原因，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); 

对此：

 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 ); 

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

我注意到stack_container.h有一个StackVector定义，我试着用它。 但它不会从向量inheritance或定义相同的方法，所以它不是一个插入replace。 我不想用vector重写所有的代码，所以我放弃了。

Answer 1

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

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

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

用法如下所示：

 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; 

Answer 2

看来， boost :: static_vector是你正在寻找。 从文档：

static_vector是vector和数组的混合体：类似vector，它是一个连续存储的序列容器，可以随着静态分配，低开销和数组的固定容量而变化。 static_vector基于Adam Wulkiewicz和Andrew Hundt的高性能varray类。

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

Answer 3

你可能想看一些选项：

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

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

请注意，我自己使用的实现不是STLSoft的，而是一个实实在在的借鉴。

“懒惰的程序员”做了一个实现使用alloca()存储的容器的职位。 我不是这种技术的粉丝，但我会让你自己决定，如果这是你想要的：

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

然后是boost::array ，它没有前两个的dynamic大小调整行为，但是比使用内置数组获得迭代器指针更多的是vector接口（例如，你得到了begin() ， end() ， size()等）：

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

Answer 4

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

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

Answer 5

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

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

对于下面的一个愚蠢的testing – 只有2推，v [0] v [1]，2 pop，在一个平台上，mac ppc，gcc-4.2 -O3只。 （我不知道苹果是否优化了他们的stl。）

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

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

 #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 ); } 

Answer 6

tr1 :: array部分匹配你的描述。 它缺lesspush ___ back（）等东西，但是可能值得以此为出发点。 包装它并添加一个索引到“后退”以支持push_back（）等应该相当容易。

Answer 7

你为什么要把它放在栈上呢？ 如果你有一个alloca（）的实现，你可以使用它来代替malloc（），但是你使用静态分配数组的想法会更好：在大多数体系结构上它的速度一样快，你的风险堆栈腐败搞砸了。

Answer 8

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

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

Answer 9

有这个提升。 它叫做small_vector

small_vector是一个向量优化的容器，当它包含很less的元素时。 它包含一些预分配的元素，当元素的实际数量低于预先分配的阈值时，可以避免使用dynamic存储分配。 small_vector灵感来自LLVM的SmallVector容器。 与static_vector不同的是，small_vector的容量可以超出最初的预分配容量。

small_vector可转换为small_vector_base，这是一种独立于预分配元素数的types，允许客户端代码不需要在该N参数上进行模板化。 small_vectorinheritance所有向量的成员函数，所以它支持所有的标准function，如安置，有状态的分配器等。