Sign in to follow this  
johnnyk

Where can i get a const capacity vector class?

Recommended Posts

I was a class like stl::vector, but with a const capacity, ie no memory allocations - its memory is stored on the stack like a c-array. I found Boost::Array, which gives me a const *size*, but doesnt have a concept of capacity. I need functions like 'push_back' and 'clear' for my purposes (which would assert if i went over the capacity) I'm about to go write my own wrapper for Boost::Array, but I figure there must be something like this already existing so I thought I'd ask first! Thanks, -John

Share this post


Link to post
Share on other sites
0) std::vector, not stl::vector.

1) You might be able to create an allocator policy for standard library containers that uses alloca(), but that way lies many many dragons.

2) boost::scoped_array has a constant capacity, but doesn't remember how many elements are "in use". However, it's appropriate (instead of boost::array) when the necessary size is not known at compile time. It is non-copyable, so it needs to be passed around by reference rather than by value (a limitation that doesn't apply to boost::array).

I would go ahead and make the wrapper, but think carefully about what it's based on. And for that matter, think about the motivations behind the apparent design goals. (Using std::vector is not "slow" if it's used properly. You might even do it from scratch, because boost::array and boost::scoped_array are actually both very simple.

Share this post


Link to post
Share on other sites
Write a custom allocator that grabs the memory you need at the outset, and for which future allocations will not do anything, or better yet, throw an exception, log an error, or otherwise make you aware that an attempt to grab more memory was made (because this would probably indicate a logic error on your part) -- you might optionally choose to allow the extra memory to be allocated in debug builds for the sake of tracking down other issues, provided you aren't passing out pointers to the things in the vector (which you probably shouldn't be doing anyways).

Share this post


Link to post
Share on other sites
Thanks guys, I went ahead and made a wrapper which was exceptionally easy. Then I realized what I was wrapping was already so small it was virtually unnecessary as well, and just implemented the whole thing as so:

//------------------------------------------------------------------------------
template <typename _Type, int iSize>
class varray
{
int m_iSize;
_Type m_array[iSize];

public:
varray() : m_iSize(0) {}
int size() const { return m_iSize; }
void push_back(const _Type &val) { m_array[m_iSize++] = val; }
void clear() { m_iSize = 0; }

const _Type &operator[](const int iIndex) const { return m_array[iIndex]; }
_Type &operator[](const int iIndex) { return m_array[iIndex]; }
};

Share this post


Link to post
Share on other sites
Interesting thing to note, even though I make about 1000 of these per frame, it made no difference in the performance stats in comparison with a regular std::vector. Guess dynamic memory allocations aren't as slow as i thought (I'm on a PC, maybe it will help more on a console)

Share this post


Link to post
Share on other sites
One difference with the vector is that it doesn't construct the objects until you insert them into the container. And array will need to construct x default objects even if you are not going to use them.

Share this post


Link to post
Share on other sites
Quote:
I'm about to go write my own wrapper for Boost::Array, but I figure there must be something like this already existing so I thought I'd ask first!

No such thing exists as far as I know.
Be careful when writing the wrapper, it is not-so-trivial. You will need to use PODs with the same alignment and sizes as your types, reinterpret_cast them to construct, destruct and use them. You will also need to have a "size" variable, of course.

The main advantage over std::vector with a custom allocator (outside of the wrapper being more space efficient) is that your wrapper will own its memory, which allocators do not allow. The allocator system has many issues anyway; it is being enhanced and clarified but won't allow that I think.

As you can see, this is not at all what your simple "wrapper" is. What you did is an array of constant size (which means all elements are default-constructed and destructed) where you do not consider elements outside of a given range.

Share this post


Link to post
Share on other sites
Quote:
Original post by johnnyk
Interesting thing to note, even though I make about 1000 of these per frame, it made no difference in the performance stats in comparison with a regular std::vector. Guess dynamic memory allocations aren't as slow as i thought (I'm on a PC, maybe it will help more on a console)
Indeed. This is why even Stroustrup says he doesn't use vectors reserve method any more.
If you really want it to be a constant capacity, just use a vector with reserve.

Share this post


Link to post
Share on other sites
Quote:
Original post by johnnyk
Interesting thing to note, even though I make about 1000 of these per frame, it made no difference in the performance stats in comparison with a regular std::vector. Guess dynamic memory allocations aren't as slow as i thought (I'm on a PC, maybe it will help more on a console)


Actually, dynamic memory allocations are many many times slower than those on the stack. Whether you see a performance difference in a program by eliminating them has to do with the percentage of the runtime they consume. For example, even if we suppose dynamic allocations are 1000000 times slower than stack ones, if they only consume 1% of the total runtime, the best performance boost you can get is 1%, and that is if you make them zero-time. This is what profiling is for, see what parts of the code eat up the largest parts of your program execution time and optimize them first. That way you avoid wasting too much time on optimizations that will yield insignificant performance benefits.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this