STL fixed size vectors?

[poolisfun]

Hi,

I was wondering if there was any easy way to define a fixed size vector in C++.
Basically, I am trying to avoid the inefficiency of dynamic allocations without having to deal with handling memory on my own (because I know the maximum number of elements).

It would be ideal if I could do something like this:

vector<10,int> tenIntegers;

I could use boost::array, but this would complicate things...


Does anybody know of a way to force an STL vector (or even a string) to do this?

If not, I am kind of annoyed with the C++ committee people...

[Lindley]

std::tr1::array is what you're looking for. In the latest generation of compilers it may have been promoted to std::array, actually, but the TR1 version should work up to one generation back.

[poolisfun]

Thanks, but why is it not possible to use .push_back() with tr1::arrays? Like, do I need to manually keep track of the number of elements I store? Basically, I want to avoid dynamic allocation without giving up this flexibility.
This way array::size() will return a different value than array::max_size()...

Also, for a std::set with a fixed size of 3500 elements, is there anything I can do like 'set<int, 3500> setOf3500' ?

[Chris_F]

Thanks, but why is it not possible to use .push_back() with tr1::arrays? Like, do I need to manually keep track of the number of elements I store? Basically, I want to avoid dynamic allocation without giving up this flexibility.
This way array::size() will return a different value than array::max_size()...

Also, for a std::set with a fixed size of 3500 elements, is there anything I can do like 'set<int, 3500> setOf3500' ?

If it had push_back then it wouldn't be fixed size.

[nuzzle]

I want to avoid dynamic allocation without giving up this flexibility.

In that case you reserve space, like

std::vector<T> v;
v.reserve(1000); // set capacity

Now you can push_back 1000 T objects without reallocation of v.

You can check both the capacity and the actual number of objects by the use of v.capacity() and v.size() respectively.

[Lindley]

Thanks, but why is it not possible to use .push_back() with tr1::arrays? Like, do I need to manually keep track of the number of elements I store? Basically, I want to avoid dynamic allocation without giving up this flexibility.
This way array::size() will return a different value than array::max_size()...

Also, for a std::set with a fixed size of 3500 elements, is there anything I can do like 'set<int, 3500> setOf3500' ?

Well, there is a stack-based allocator that someone around here came up with.

Seems to me, however, that for your requirements it would be simplest to just use a vector which is .reserve()ed to the correct maximum size at the largest relevant scope, and passed into lower-level functions as a reference parameter. That's the usual way of doing what you seem to be looking for.

[kempofighter]

Hi,

I was wondering if there was any easy way to define a fixed size vector in C++.
Basically, I am trying to avoid the inefficiency of dynamic allocations without having to deal with handling memory on my own (because I know the maximum number of elements).

It would be ideal if I could do something like this:

vector<10,int> tenIntegers;

I could use boost::array, but this would complicate things...


Does anybody know of a way to force an STL vector (or even a string) to do this?

If not, I am kind of annoyed with the C++ committee people...

I do not understand why you are annoyed with anyone else. They gave you a powerful, flexible tool to use called the std::vector. They also gave you these things called classes which allow you to encapsulate a vector. If you really want to have a fixed size vector then make a wrapper class and use its interface to prevent the array from growing. Typically a vector is a building block used to design all of the parts of your program so it is reasonable that most vectors within a well designed program will be encapsulated by a class that owns it. That class can be coded to ensure that the vector is setup with memory reserved for some "fixed' number of elements. It is up to the owner of the vector to ensure that the size is tested against the capacity prior to inserting new data. The C++ people gave you everything that you need to build a well designed program. They also gave you things like exceptions that can be thrown if the user of the class tries to do something that is invalid.

[Lindley]

Well, I can understand wanting to avoid dynamic allocation, but the class encapsulation idea is a good one----just make it a tr1::array that's encapsulated rather than a vector, and add a member to say how many of its indexes are currently in use.

[poolisfun]

Well, I can understand wanting to avoid dynamic allocation, but the class encapsulation idea is a good one----just make it a tr1::array that's encapsulated rather than a vector, and add a member to say how many of its indexes are currently in use.

Sounds like a good idea thanks!

[JohnW@Wessex]

Well, there is a stack-based allocator that someone around here came up with.

That was me
But to be honest, I would go along with the other suggestions such as a vector with reserved capacity or a wrapped std::array. The stack allocator was specifically designed for fast and deterministic performance, but unless you are coding for a real-time platform, it doesn't give any real advantage over the standard allocator and has certain caveats to it's use.

[monarch_dodra]

Well, I can understand wanting to avoid dynamic allocation, but the class encapsulation idea is a good one----just make it a tr1::array that's encapsulated rather than a vector, and add a member to say how many of its indexes are currently in use.

I'd recommend something in the same flavor: wrapping a vector which is immediately reserved for max size. Then the interface can still push_back, however, you will stop pushing back once the vector is full. This will guarantee a fixed size container that never re-allocates.

But it depends if you want a "fixed size" vector, or a "max size" vector. There is a difference. This option gives both.

The difference from using a tr1 array, is that vectors use placement new and explicit destruction to create and destroy objects as they come and go, on previously allocated but un-initialized memory. This also means you will not pay for the construction of objects you never use.

Something like this:

template<typename T, typename alloc = std::allocator<T> >
class fixed_size_vector
{
public :
    fixed_size_vector(size_t size) : vect(),
                                     max_size(size)
    {
        vect.reserve(size);
    }

    push_back(const T& i)
    {
        if(vect.size()<max_size)
        {
            vect.push_back();
        }
    }

    //forward everything else
    operator[](size_t t)
    {
        return vect[t];
    }

    ...

private:
    std::vector<T, alloc> vect;
    size_t max_size;
};

The neat thing about this is that even if you are fixed size, you still have access to operations that could potentially change the size of your vector (push_back, insert etc), yet your implementation saves you and drops extra items.

Of course, you'll have to pay for some extra book keeping, and the implementation systematically checks against max_size, even if you now you haven't reached. But it's either that or a naked vector (or another proposed solution).

[dude_1967]

I have done most or all of the suggestions above --- and these are some good suggestions.

When writing in modern C++, I either use std::array<T, N> or std::tr1::array<T, N> preferably checking availability in the order shown.

If neither std::array nor std::tr1::array is available, I often write my own utility called something like util::array<T, N>. You can essentially get the code from boost. It is really simple and quite useful.

For tiny embedded systems without heaps but with rudimentary vector needs, I have at times written some implementations of a utility called something like util::fixed_size_vector<T, N>. But I don't wrap std::vector, I make a completely new implementation based on an array of memory. I have off-and-on implemented more or less of vector's standard member functions depending on the depth of the drop-in replacement needs. This kind of implementation is essentially an array with an end marker which simply lets elements fall off the edge instead of growing dynamically past the end of its memory. However, it lets the end user gain access to some of vector's functions which, within the memory constraints, behave as expected.

The advice about reserving size up front is always helpful.

I hope this helps in addition to the other good suggestions.

Sincerely, Chris.

[kempofighter]

The only thing that I can add is that a fixed size array is really not necessary. I think that some people were misunderstanding my earlier post.

// Now i have an array of 10 elements default initialized to 0.
// simply use operator[] to override the elements and don't insert or erase
// anything from it.  Why does it need to be fixed in size?
// this technique can work for std::deque as well.
std::vector<int> MyArray(10);

// here is an array of 0 elements with a capacity of 10.
// I can use insert / push_back up to 10 times
// std::deque does not have reserve() or capacity() members.
std::vector<int> MyArray; // empty
MyArray.reserve(10); // memory created for 10 elements

I'm not sure that you would want to create a wrapper for the sole purpose of making the vector object a fixed size array. When I said wrapper I meant that in OO programming you normally have a collection of classes and they might have vector instance as private / protected attribute. The instance is encapsulated so the public interfaces would enforce that a user of the class can't do anything that would cause the vector to grow beyond its original size. I'm not sure if there is a benefit in making something like a vector that has a fixed size.

[Lindley]

The only benefit would be in avoiding the heap allocation implicit in the use of a vector, since a fixed-size array could be placed entirely on the stack.

[poolisfun]

The only benefit would be in avoiding the heap allocation implicit in the use of a vector, since a fixed-size array could be placed entirely on the stack.

Yeah, that was my original intention. Now if only STL defined some way to reserve a certain amount of space in a vector via stack it would be easier...