Vector like container which can reuse space?

[DexterMorgan]

Unoptimized problem: I work on a table (vector of vectors).
vector< vector<double> >

Optimization: If the current set of vectors is v1...vn (so each vk is a vector of double), my problem is such that I will only work on the last M of the vectors, the earlier vectors are irrelevant. I would like to reuse space to make the algorithm scalable, so I want to delete the vectors that can be forgotten. I read in a new vector, I delete the oldest vector.

The problem is that naive deletion of vectors is expensive. There must be a simple way to do this since this is a special and simple kind of deletion.

Any suggestions?

[Disch]

Maybe use a deque instead of a vector?

deque's allow for quick erasure of elements at both ends. So you can use it as a continuous stream: You can push elements to the end of it, while popping them off of the front. And still allow fast random access.

[JLBorges]

Use a ring buffer (with move assignment). Boost has an implementation.

#include <iostream>
#include <vector>
#include <boost/circular_buffer.hpp>

int main()
{
    std::size_t M = 5 ;

    // http://www.boost.org/doc/libs/1_57_0/doc/html/circular_buffer.html
    boost::circular_buffer< std::vector<double> > ring_buffer(M) ; // keeps the last 'M' vectors

    double v = 0.1 ;
    std::size_t n = 2 ;
    for( std::size_t i = 0 ; i < M*3 ; ++i )
    {
        std::vector<double> next( n, v ) ;
        double incr = 0 ;
        for( double& d : next ) { d += incr ; incr += 0.1 ; }
        ring_buffer.push_back( std::move(next) ) ;

        if( i > (M-2) )
        {
            for( const auto& vec : ring_buffer )
            {
                std::cout << "[ " ;
                for( double d : vec ) std::cout << d << ' ' ;
                std::cout << "]   " ;
            }
            std::cout << '\n' ;
        }

        if( i%2 ) ++n ;
        v += 0.1 ;
    }
}

http://coliru.stacked-crooked.com/a/470fb1f1542f62ec