3

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.

stefaanv
  • 14,072
  • 2
  • 31
  • 53

6 Answers6

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.

David Rodríguez - dribeas
  • 204,818
  • 23
  • 294
  • 489
  • Private inheritance is well and good, but the container interface is inconveniently large. See the list of requirements, and optional requirements, and then `vector` adds more… – Potatoswatter Aug 25 '10 at 12:12
  • The user requirements seem lesser: fill entries, remove, iterate. You can implement a non-standard container that only offers what is required en probably less than 50 lines (including all the appropriate typedefs). – David Rodríguez - dribeas Aug 25 '10 at 13:19
  • Note: this sketch is already 47 lines, and it is quite bare. Contrast the restrictions of this class with the single requirement to call `reserve` after constructing an object as in my solution. – Potatoswatter Aug 25 '10 at 20:31
  • @Potatoswatter: The sketch goes beyond the requirements established in the question. Using a limited allocator is wrong as the way that containers grow is undefined. Note also that simply constructing a vector (without actually inserting elements into it) may already trigger an allocation. There is no way of controlling the capacity *before* the vector is created, and there is no guarantee that once it is created it is not too late already. – David Rodríguez - dribeas Aug 25 '10 at 23:03
  • @David: OP didn't attempt to describe all his requirements… it is cleaner to use an STL class and not worry about the feature set. Although the allocation schedule is implementation defined, it is somewhat brain-dead to request an allocation greater than `Allocator::max_size`, as `reserve` is already required to check its argument against `max_size`. And it takes a rather pessimistic implementation to allocate memory for an empty vector. By the same logic, *any* vector is allowed to crash right off the bat. – Potatoswatter Aug 25 '10 at 23:54
  • @David: thanks, I went for the private composition, but in the end, it is similar to your code. – stefaanv Aug 26 '10 at 06:55
3

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.

Hemant
  • 726
  • 6
  • 17
  • So the question has moved to: what is the best way to customize a vector to impose an upper limit? Is inheritance a good idea in this case? – stefaanv Aug 25 '10 at 07:46
  • 1
    @Hemant: How? Do you have any code snippet to illustrate your point? You may want to look at http://stackoverflow.com/questions/922248/is-there-any-real-risk-to-deriving-from-the-c-stl-containers – Chubsdad Aug 25 '10 at 07:46
  • The STL containers are not designed to be derived from. You can tell this because their destructors are not virtual. – Martin York Aug 25 '10 at 07:51
  • @stefaanv: No inheritance allowed. Customization is exactly the approach that I am taking. – Potatoswatter Aug 25 '10 at 07:57
  • 1
    @stefaanv: Not only is it not encouraged, it's a rather bad idea for containers. You have to duplicate all the constructors, including two which alias each other in a tricky way. – Potatoswatter Aug 25 '10 at 08:00
  • 2
    People often overstate the problems with deriving from STL containers. You don't need a virtual destructor if you're not adding data members, and unless the ownership of the derived containers themselves (as distinct from their elements) is complex then there are no issues with accidental destruction via base pointer anyway. 95% of the time you're making this kind of design decision, it's obvious that it's safe. You often don't need all the constructor's either. If you're providing a library with a drop-in vector for arbitrary client usage you should worry more :-). – Tony Delroy Aug 25 '10 at 08:10
  • @Potatoswatter: thanks, so tempting as it seems for a small customization, I won't inherit. I didn't know that reason. However, I'm still not clear whether the customization that you show will work for me, but I'll try to it. – stefaanv Aug 25 '10 at 08:10
  • One other point on the above - the derivation issue is one of robust maintainability, and doing the obvious - despite imperfect corner cases - benefits greatly from simplicity and clarity. The issues are well understood. Hacking up some alternative is typically more error prone and can reduce productivity and robustness. – Tony Delroy Aug 25 '10 at 08:14
2

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.
}
Potatoswatter
  • 134,909
  • 25
  • 265
  • 421
  • 5
    The way vectors grow their capacity is distinct from their in-use size (for example, a single push_back may trigger a request to double capacity) seems to prevent this approach: you're putting a cap on capacity, but that may be hit before size() reaches the intended limit. – Tony Delroy Aug 25 '10 at 07:31
  • @Tony: fair nuff, although `reserve` could solve that problem, or simply making the limit double the upper bound. – Potatoswatter Aug 25 '10 at 07:33
  • The Standard doesn't guarantee it'll double each time... e.g. may allocate a memory page of objects the first time or two, then double afterwards. reserve() is a pretty strong request not to pad out the allocation though.... – Tony Delroy Aug 25 '10 at 07:45
  • @Tony: Yep, although most implementations double or less. Actually, `max_size` provides enough information to `vector` that a good implementation shouldn't need to exceed it. `vector` could and should catch the `bad_alloc` and retry the allocation with `max_size`. However, GNU doesn't do this, it only uses `max_size` if the size *overflows*, which is kind of bizarre. As with everything allocator-related, the standard is discombobulated on the issue. – Potatoswatter Aug 25 '10 at 07:46
  • @Potatoswatter: I like the allocator-idea, but in my case the limit needs to be the size of the current array, so I have no choice. Is an allocator that owns a fixed array an option? – stefaanv Aug 25 '10 at 07:49
  • @stefaanv: Allocators can't own things, so no. But you can call `reserve(vector_max)` or generate the arrays in a factory function which calls `reserve(vector_max)`; this will reliably set a hard limit. – Potatoswatter Aug 25 '10 at 07:55
  • Oops, I spoke too soon about GNU. GCC 4.2.1 only uses `max_size` when multiplying the capacity by 2 results in arithmetic overflow; GCC 4.5 uses checks against `max_size` every time and should work flawlessly with this allocator. – Potatoswatter Aug 25 '10 at 08:27
2

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.

sbi
  • 219,715
  • 46
  • 258
  • 445
  • It probably would be the best thing, because it would give a complete container, but taking over code, even with liberal licenses requires approvals, so I'm going for the own implementation starting from a vector. – stefaanv Aug 26 '10 at 06:59
  • @stefaanv: Uh oh, corporate headaches. IANAL, but would it be a problem to incorporate _your_ code in your company's? Because if not, that code's license is liberal enough for you to rip the code out of that header and put it into your own header, with whatever copyright you'd like to use. You'd then only face the supposedly smaller hurdle of getting your own code approved. That somewhat beats a bureaucratic system with its own weapons. `:)` – sbi Aug 26 '10 at 09:43
  • thanks for the tip, but for the moment, I'm happy with my implementation (similar to dribeas suggestion) – stefaanv Aug 26 '10 at 11:04
1

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.

dirkgently
  • 108,024
  • 16
  • 131
  • 187
1

Take a look at boost::array

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

dimba
  • 26,717
  • 34
  • 141
  • 196