Re: [boost] Stack-based vector container

Subject: Re: [boost] Stack-based vector container
From: Gregory Crosswhite (gcross_at_[hidden])
Date: 2010-12-28 18:22:52

On 12/28/10 6:17 PM, Michael Caisse wrote:
> On 12/28/2010 03:03 PM, Gregory Crosswhite wrote:
>> Hey everyone,
>>
>> In the course of my work as a computational scientist I have written 
>> a container that emulates std::vector, but which is backed by an 
>> array whose size is fixed at compile time.  Concretely, the class 
>> looks something like the following:
>>
>>     template<typename T,unsigned int buffer_size> class static_vector {
>>         ...
>>         protected:
>>             T data[buffer_size];
>>             T* end_ptr;
>>             size_t current_size;
>>     }
>>
>> where in the [...] there are methods that emulate (at this time, 
>> partially) the interface of std::vector, save that the size of the 
>> static_vector is not allowed to grow beyond the buffer_size.
>>
>> The advantage of using a static_vector over vector is performance.  
>> In my code I have performed benchmarks that show up to a 30% 
>> performance boost of static_vector over vector;  the benefit occurs 
>> most stongly when working with lots of arrays of small objects, so 
>> that the use of dynamic memory rather than stack memory appears to 
>> add significant overhead to the computation.  (Note that I when 
>> running these benchmarks I would use std::vector::reserve() to 
>> pre-allocate the array so that std::vector would not perform multiple 
>> allocations as the container grew, so that should not have been a 
>> source of overhead.)
>>
>> It seems to me that it would be useful to have this functionality 
>> generally available as a library, and in particular it might be a 
>> good fit for the boost family of libraries.  Is there any interest 
>> out there for having such a library in boost?  If so, I would be 
>> happy to do the work of taking what I have and fleshing it out so 
>> that it can function as a drop-in replacement for vector, which means 
>> modeling the Random Access Container and Back Insertion Sequence 
>> concepts as well as adding capacity() and reserve(size_t) (no-op) 
>> methods.
>>
>> Thoughts?
>>
>
> How is this different than boost::array?
> <http://www.boost.org/doc/libs/1_45_0/doc/html/array.html>
>

boost:array has a number of elements that is fixed at compile time.  By 
contrast, my proposed static_vector could grow and shrink as long as the 
number of elements is kept below the buffer_size.

Cheers,
Greg