Search for a C ++ STL-like vector class, but using stack storage

Question

Before I write my own, I will ask all of you.

I am looking for a C ++ class that is almost exactly like an STL vector, but stores data in an array on the stack. Some class of STL allocator will work, but I try to avoid any heap, even static distributed cumulus (though one of them is my second choice). The stack is more efficient.

It should be almost a replacement for the current code that uses the vector.

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

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

Or the class may contain buffer space inside. Then it will look like this:

 stack_vector<match_item, 256> matches; 

I thought he would throw std :: bad_alloc if he runs out of free space, although this should not happen.

Update

Using Chromium stack_container.h works great!

The reason I didn’t think I was doing it myself was because I always ignored the allocator object parameter for the STL collection constructors. I used the template parameter several times to create static pools, but I never saw the code or wrote any that actually used the object parameter. I learned something new. Very cool!

The code is a bit messy and for some reason GCC made me declare the allocator as the actual element, rather than constructing it into a vector allocator parameter. It came 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); 

For 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 it when I announce a new one. But it works the way I wanted.

I noticed that stack_container.h has StackVector installed and I tried to use it. But it does not inherit from the vector or does not define the same methods, so it was not a replacement. I did not want to rewrite all the code using a vector, so I abandoned it.

Answer 1

You do not need to write a completely new container class. You can stick with your STL containers, but change the second parameter, for example std::vector , to provide it with its own dispenser that allocates from the stack buffer. Chrome authors wrote a dispenser 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 a container and call container.reserve(buffer_size); . If you overflow this size, the distributor will automatically get the elements from the heap (since it is derived from std::allocator , in this case it just uses the means of the standard distributor). I have not tried it, but it seems like google, so I think it is worth a try.

Usage looks 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; 

Answer 2

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

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

The number of elements in static_vector can dynamically vary to a fixed capacity, because the elements are stored inside the object itself like an array.

Answer 3

Some options you can see:

STLSoft by Matthew Wilson (author of Imperfect C ++) has an auto_buffer template class that pushes the default array auto_buffer stack, but if it is larger than the stack allocation, it will grab memory from the heap. I like this class - if you know that the size of your container is usually limited by a rather low limit, then you get the speed of a local array allocated by the stack. However, for corner cases, when you need more memory, all this works fine.

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

Please note that the implementation that I use myself is not STLSoft, but an implementation that depends heavily on it.

The "lazy programmer" made a message to implement a container that uses alloca() for storage. I am not a fan of this technique, but I will let you decide for yourself if this is what you want:

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

Then there is boost::array , which has no dynamic behavior of the size of the first two, but gives you more of a vector interface than just using pointers as iterators that you get with inline arrays (that is, you get begin() , end() , size() , etc.):

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

Answer 4

You can use your own allocator for std :: vector and distribute stack based pieces of your storage similar to your example. The allocator class is the second part of the template.

Edit: I have never tried this, and looking at the documentation, I also believe that you cannot write your own dispenser. I still look at him.

Answer 5

If speed matters, I see the runtime

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

for one stupid test below - only 2 clicks, v [0] v [1], 2 pop, on the same platform, only mac ppc, gcc-4.2-O3. (I don't know if Apple optimized their stl.)

Do not accept any timings that you did not fake yourself. And of course, each usage pattern is different. However, factors> 2 surprise me.

(If mems, memory accesses, are the dominant factor at runtime, what are all the extra members in different 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 ); } 

Answer 6

tr1 :: array partially matches your description. There are no such things as push ___ back (), etc., but it might be worth a look at the starting point. Wrapping and adding an index to the back to support push_back (), etc. It should be pretty simple.

Answer 7

Why do you want to put it on the stack? If you have an alloca () implementation, you can reassign the allocator class using this instead of malloc (), but your idea of ​​using a statically allocated array is even better: it works just as quickly on most architectures, and you don't use stack corruption with risk you will lose.

Answer 8

Perhaps you are using Qt. Then you can go to QVarLengthArray ( docs ). It sits mainly between std::vector and std::array , allocating statically for a certain amount and, if necessary, returns to the distribution of the heap.

I would prefer the boost version if I used it.

Answer 9

Increase it. It is called small_vector

small_vector is a vector container optimized for the case when it contains several elements. It contains some pre-allocated items in place, which avoids the use of dynamic storage when the actual number of items is below a predetermined threshold. small_vector is inspired by the LLVM SmallVector container. Unlike static_vector, the capacity of small_vector can grow beyond the original pre-allocated capacity.

small_vector is converted to small_vector_base, a type that does not depend on a pre-distributed element counting, allowing client code that does not need to be planned on this N. small_vector inherits all member functions of the vector, so it supports all standard functions, such as placement, etc.