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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk