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-12 23:35:50

> > And sometimes is less efficient. For instance, if you are populating
> > from StaticVector from list iterators (or any non-random access
> > iterators), it's an O(n) check ahead of time or a complicated wrapper
> > around a one-at-a-time insert. (Note: this is a bug in the current
> > implementation of StaticVector, as its iterator constructor currently
> > requires random access iterators).
> >
> >
> Does this mean that in any of the functions where I have two iterators, I
> should separately implement one for boost::single_pass_traversal_tag and
> another for boost::random_access_traversal_tag?
>
> 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).

> On this topic, what is the difference between
> boost::random_access_traversal_tag and std::random_access_iterator_tag,

Take a look at http://www.boost.org/doc/libs/1_47_0/libs/iterator/doc/new-iter-concepts.html

> and should I implement both?

One or the other, not both. I would image that for Boost libraries, the convention 
is to use the Boost concepts, but I'm no authority on this.

Regards,
Nate