How should a size-limited stl-like container be implemented?

Question

While refactoring, I wanted to change an array where entries are added to an std::vector, but for compatibility (persistency, downgrading,...), it still needs to have an upper limit.
What is the best way (elegant, stl-like, limited extra code) to have an stl-like container which is limited in size, so you know that inserting an entry fails?

Edit:
To clarify: I would like an stl-like container, that starts empty, that you can fill with entries and possibly remove entries and that iterate over the filled-in entries, but that doesn't allow to put in more than e.g. 50 entries, so almost like a sequential contrainer, but with an upper-limit.

Answer 1

You can create a custom allocator (e.g. derived from std::allocator) that refuses to allocate an array larger than a given size.

Note that you need to call reserve( vector_max ) on the resulting object before adding things to it. I'm filing a defect against the C++ standard, as the requirement should be unnecessary (and it is, on recent versions of GCC).

template< typename T, size_t N >
struct limited_alloc : std::allocator< T > {
    size_t max_size() const { return N; }
    typename std::allocator<T>::pointer allocate( size_t n ) {
        if ( n < N ) return std::allocator<T>::allocate( n );
        throw std::length_error( "array too large" );
    }

    limited_alloc() {} // silly cruft for standard requirements:
    template< typename T2 >
    limited_alloc( limited_alloc<T2,N> const & ) {}
    template< typename T2 >
    struct rebind { typedef limited_alloc<T2,N> other; };
};

enum { vector_max = 40 };

template< typename T >
struct limited_vector {
    typedef std::vector< T, limited_alloc< T, vector_max > > type;
};

void f() {
    limited_vector< int >::type x;
    x.reserve( vector_max );
    x.assign( vector_max + 1, 3 ); // throws.
}

Answer 2

Customize the vector class to impose an upper limit. Probably, you can have a new api exposed which will check the size against the upper limit and return false if exceeds otherwise call the regular insertion method.

Answer 3

Take a look at Boost.Array

As replacement for ordinary arrays, the STL provides class std::vector. However, std::vector<> provides the semantics of dynamic arrays. Thus, it manages data to be able to change the number of elements. This results in some overhead in case only arrays with static size are needed.

Answer 4

Take a look at boost::array

Edit: for add/delete boost::optional can be used as a element type of boost::array.

Answer 5

A simple solution would be encapsulating a vector inside your own limited size container. You could use private composition or private inheritance --note that private inheritance models implemented in terms of and does not have some of the shortcomings of public inheritance.

EDIT: Sketch of the solution with private inheritance

template <typename T, unsigned int N>
class fixed_vector : std::vector<T>
{
    typedef std::vector<T> vector_type;
public:
    typedef typename vector_type::reference reference;
    typedef typename vector_type::const_reference const_reference;
    typedef typename vector_type::iterator iterator;
    typedef typename vector_type::const_iterator const_iterator;
    typedef typename vector_type::value_type value_type;
    typedef typename vector_type::size_type size_type;

    fixed_vector() : vector_type() {}
    fixed_vector( size_type size, value_type const & value = value_type() )
       : vector_type(size,value)
    {}      

    void push_back( value_type v ) {
        ensure_can_grow();
        vector_type::push_back( v );
    }
    iterator insert( iterator position, value_type const & v ) {
        ensure_can_grow();
        vector_type::insert( position, v );
    }
    void reserve( size_type size ) {
        if ( size > N ) throw std::invalid_argument();
        vector_type::reserve( size );
    }
    size_type capacity() const {
        // In case the default implementation acquires by default 
        // more than N elements, or the vector grows to a higher capacity
        return std::min( vector_type::capacity(), N );
    }
    // provide other insert methods if required, with the same pattern
    using vector_type::begin;
    using vector_type::end;
    using vector_type::operator[];
    using vector_type::erase;
    using vector_type::size;
    using vector_type::empty;
private:
    void ensure_can_grow() const {
        // probably a different exception would make sense here: 
        if ( this->size() == N ) throw std::bad_alloc();
    }
};

There is quite a bit of hand-waving there... std::vector take more arguments that could be added to the façade. If you need any of the other methods or typedefs, you can just bring them into scope with a using declaration, redefine the typedef, or implement the adaptor with your particular test.

Also, in this implementation the size is a compile time constant, but it would be really simple to modify it into a constructor parameter.

Answer 6

Have a look at this static_vector implementation which I found a while ago. I think it does exactly what you want.

It's distributed under the very liberal boost license, so you're allowed to do just about anything with it.