72

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

我正在寻找一个几乎完全像 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 集合构造函数的分配器对象参数。我曾多次使用模板参数来做静态池，但我从未见过代码或编写过任何实际使用对象参数的代码。我学到了一些新东西。很酷！

代码有点混乱，出于某种原因，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，我尝试使用它。但它没有从 vector 继承或定义相同的方法，因此它不是一个直接替代品。我不想使用向量重写所有代码，所以我放弃了它。

4

10 回答 10

50

您不必编写全新的容器类。您可以坚持使用您的 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;
于 2008-12-09T22:27:00.920 回答
24

看来boost::static_vector是您正在搜索的内容。从文档中：

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

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

于 2014-01-16T13:23:13.270 回答
12

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

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

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

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

alloca()“The Lazy Programmer”为实现用于存储的容器做了一篇文章。我不是这种技术的粉丝，但如果它是你想要的，我会让你自己决定：

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

于 2008-12-10T01:18:56.987 回答
6

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

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

对于下面的一个愚蠢的测试——只有 2 push，v[0] v[1]，2 pop，在一个平台上，mac ppc，gcc-4.2 -O3 而已。（我不知道苹果是否优化了他们的 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 );

}
于 2009-07-29T11:20:15.903 回答
5

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

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

于 2008-12-09T22:18:30.813 回答
3

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

于 2008-12-09T22:39:40.613 回答
2

为什么特别想入栈？如果你有一个 alloca() 的实现，你可以使用它而不是 malloc() 来构建一个类分配器，但是你使用静态分配数组的想法更好：它在大多数架构上都一样快，而你不需要你搞砸的风险堆栈腐败。

于 2008-12-09T22:25:10.660 回答
2

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

不过，如果我使用它，我更喜欢增强版。

于 2014-05-13T20:00:24.230 回答
1

Boost有这个。它称为small_vector

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

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

于 2016-04-21T08:50:48.023 回答
1

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

new_stack_vector(Type, name, size)

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

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

例子：

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

...就这样！

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

于 2018-03-07T13:27:26.493 回答