Re: [boost] Interest in StaticVector - fixed capacity vector

Subject: Re: [boost] Interest in StaticVector - fixed capacity vector
From: Nathan Ridge (zeratul976_at_[hidden])
Date: 2011-10-13 15:23:08

> > > I assume I want to simply check the distance between two
> > > random access iterators and return immediately if the size is
> > > too big. Then, if it isn't random access I should just start
> > > copying and check if I've run out of space on each element
> > > that is added. Is this correct?
> >
> > Basically, yes. You may also want to have a version for
> > forward iterators - if you're allowed to traverse the range
> > more than once, then it is usually more efficient to traverse
> > it once to find out the length, throw (or whatever) if the
> > length is too big, and otherwise traverse it a second time to
> > actually insert the elements. (This is not always more
> > efficient - for example, if your iterators are
> > transform_iterators, and the transformation function they are
> > calling is expensive, it's not - but I believe several STL
> > implementations assume it is and do it this way).
> 
> Why would you optimize the failure case?

On second thought, you probably shouldn't :)

I revisited the STL functions I was referring to that discriminated
between forward iterators and input iterators in this way, and
realized they were the likes of vector::insert(first, last), which
may potentially have to reallocate its storage to be large enough
to store the existing elements plus the new ones. In such a case,
knowing how many elements you have in advance is a big gain,
even if it means iterating through the range a second time,
because otherwise you may end up reallocating multiple times.

For static_vector, doing this really would just be optimizing
the failure case, so it shouldn't  be done. Random access iterator
and input iterator versions are sufficient.

Regards,
Nate