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

Question

在我写自己之前,我会问你们所有人.

我正在寻找一个几乎完全像STL向量的C++类,但是将数据存储到堆栈中的数组中.某种类型的STL分配器类也可以工作,但我试图避免任何类型的堆,甚至是静态分配的每线程堆(尽管其中一个是我的第二选择).堆栈效率更高.

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

对于我自己要写的东西,我在考虑这样的事情:

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

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

stack_vector<match_item, 256> matches;

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

更新

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

我之所以没想过这样做的原因是我总是忽略了STL集合构造函数的allocator对象参数.我已经使用了几次模板参数来做静态池,但是我从未见过代码或编写任何实际使用过对象参数的代码.我学到了新东西.很酷!

代码有点乱,由于某种原因,GCC强迫我将分配器声明为实际项而不是将其构造为vector的allocator参数.它来自这样的事情:

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,我尝试使用它.但它不会从vector继承或定义相同的方法,因此它不是替代品.我不想使用向量重写所有代码,所以我放弃了它.

Answer 1

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

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

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

用法是这样的:

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和array之间的混合:就像vector一样,它是一个具有连续存储的序列容器,可以改变大小,以及静态分配,低开销和固定容量的数组.static_vector基于Adam Wulkiewicz和Andrew Hundt的高性能varray类.

static_vector中的元素数量可以动态变化到固定容量,因为元素与数组类似地存储在对象本身内.

Answer 3

您可能想要查看的一些选项:

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

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

请注意,我自己使用的实现不是STLSoft,而是一个从中大量借用的实现.

"Lazy Programmer"发布了一个alloca()用于存储的容器实现的帖子.我不是这种技术的粉丝,但我会让你自己决定它是否是你想要的:

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

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

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

Answer 4

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

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

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

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

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

#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 5

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

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