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

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.

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.

Update

Using Chromium's stack_container.h works great!

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!

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:

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.

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::vector to give it your custom allocator which allocates from a stack-buffer. The chromium authors wrote an allocator just for this:

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.

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;

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

> 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.

Some options you may want to look at:

STLSoft by Matthew Wilson (author of Imperfect C++) has an auto_buffer template 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.

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.

"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:

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

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

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

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>

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

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

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

}

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.

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.

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.

Why do you want to put it on the stack particularly? 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.

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

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

Boost have this. Its called 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 Allocator>, 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.

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:

new_stack_vector(Type, name, size)

where Type is the type of element in the vector, name is the variable name of the vector, and size is the maximum number of elements to allow in the vector.

size can be variable and does not need to be a compile-time constant! :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.