[boost] Interest in StaticVector - fixed capacity vector

78 views
Skip to first unread message

Andrew Hundt

unread,
Oct 9, 2011, 1:59:51 PM10/9/11
to bo...@lists.boost.org
On Sun, Aug 14, 2011 at 5:55 AM, Andrew Hundt <ath...@gmail.com> wrote:

> I've implemented a small companion class to boost.array that functions
> like a stack allocated vector with fixed capacity. The motivation for this
> class came when I was using boost.array in an interprocess library, when I
> realized that I actually desired an adjustable size boost.array, without the
> complexity of the vector class in the interprocess library. The result is
> StaticVector, which is boost.array directly modified with a size in front of
> the array, and added facilities to match std::vector.
>
> The Implementation is available at:
> https://github.com/ahundt/Boost.StaticVector
>
> Sample Code:
> StaticVector<std::size_t,3> three;
> three.push_back(5);
> three.push_back(2); // size: 2 capacity: 3
> three.push_back(3);
>
> three.push_back(1); // throws std::out_of_range exception indicating the
> capacity has been exceeded
>
> So here is the big question:
> Is there any interest in the class?
>
> Cheers!
> Andrew Hundt
>
>
On Mon, Aug 15, 2011 at 5:20 PM, Nevin Liber <ne...@eviloverlord.com> wrote:

> On 15 August 2011 16:05, Andrew Hundt <ath...@gmail.com> wrote:
>
> > Good point. I've modified elems to be a char array, and I now
> > reinterpret_cast to the class T as necessary. Elements should only be
> > constructed when they are added now.
> >
>
> What are you doing about alignment? Take a look at Synyhesizing Types with
> Specific Alignments in the Type Traits library for a start.
> --
> Nevin ":-)" Liber <mailto:ne...@eviloverlord.com> (847) 691-1404
>

Phil Endecott wrote:

> In the case of StativVector<char,N> where N<256, you should consider using
> uint8_t to store the size - and similar variations. Boost.Integer makes it
> possible to select a suitable type.

Sorry for the duplicate email, but my other email seemed to get lost in the
shuffle. I know its been a while since I sent my first emails regarding
StaticVector, but I have fixed some of the issues others pointed out.

- I added a benchmark based on a move benchmark found on C++Next, that shows
StaticVector outperforming vector by about 30%, which seems reasonable since
there is no dynamic allocation.
- I believe I've resolved the StaticVector alignment using type_traits'
aligned_storage, as suggested by Nevin Liber.
- I've also added the use of Boost.Integer to select the smallest possible
type to track the size of the vector given its capacity, as suggested by
Phil Endecott.

The Implementation is available at:
https://github.com/ahundt/Boost.StaticVector

Anyone still have additional thoughts or interest in this?

Cheers!
Andrew Hundt

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Peter Myerscough-Jackopson

unread,
Oct 10, 2011, 6:47:14 AM10/10/11
to bo...@lists.boost.org
Andrew Hundt <athundt <at> gmail.com> writes:

>
> On Sun, Aug 14, 2011 at 5:55 AM, Andrew Hundt <athundt <at> gmail.com> wrote:
>
<snip>


> > three.push_back(2); // size: 2 capacity: 3
> > three.push_back(3);
> >
> > three.push_back(1); // throws std::out_of_range exception indicating the
> > capacity has been exceeded

Is there any chance that the error behaviour code be configurable. StaticVector
looks ideal for embedded environments, BUT commonly exceptions are disabled in
such an environment. It would be nice to have asserts instead of exceptions
available in all cases, so that a programmer can check for room on a push_back
prior to calling it. A specific StaticVector macro would suffice for those that
need it.

(There may also need to be changes for the template specialization of <T,0> as
well, with respect to throwing exceptions.)

As an aside the exceptions should/could be thrown using the
BOOST_THROW_EXCEPTION macro, to support the other boost specific exception
behaviour support. (At least it is something like that.)

Yours,

Peter

Nigel Stewart

unread,
Oct 10, 2011, 1:04:32 PM10/10/11
to bo...@lists.boost.org
> Is there any chance that the error behaviour code be configurable.
StaticVector
> looks ideal for embedded environments, BUT commonly exceptions are
disabled in
> such an environment.

Yes indeed. That would be desirable, as an option.

- Nigel

Matt Calabrese

unread,
Oct 10, 2011, 1:18:39 PM10/10/11
to bo...@lists.boost.org
On Sun, Oct 9, 2011 at 1:59 PM, Andrew Hundt <ath...@gmail.com> wrote:

> On Sun, Aug 14, 2011 at 5:55 AM, Andrew Hundt <ath...@gmail.com> wrote:
>
> > I've implemented a small companion class to boost.array that functions
> > like a stack allocated vector with fixed capacity. The motivation for
> this
> > class came when I was using boost.array in an interprocess library, when
> I
> > realized that I actually desired an adjustable size boost.array, without
> the
> > complexity of the vector class in the interprocess library. The result is
> > StaticVector, which is boost.array directly modified with a size in front
> of
> > the array, and added facilities to match std::vector.
> >
> > The Implementation is available at:
> > https://github.com/ahundt/Boost.StaticVector


I believe there is interest -- in fact, there's already such a library in
the review queue. It's Thorsten Ottosen's AutoBuffer library.

--
-Matt Calabrese

Jeffrey Lee Hellrung, Jr.

unread,
Oct 10, 2011, 4:02:59 PM10/10/11
to bo...@lists.boost.org
On Mon, Oct 10, 2011 at 10:18 AM, Matt Calabrese <riv...@gmail.com> wrote:

> On Sun, Oct 9, 2011 at 1:59 PM, Andrew Hundt <ath...@gmail.com> wrote:
>
> > On Sun, Aug 14, 2011 at 5:55 AM, Andrew Hundt <ath...@gmail.com> wrote:
> >
> > > I've implemented a small companion class to boost.array that functions
> > > like a stack allocated vector with fixed capacity. The motivation for
> > this
> > > class came when I was using boost.array in an interprocess library,
> when
> > I
> > > realized that I actually desired an adjustable size boost.array,
> without
> > the
> > > complexity of the vector class in the interprocess library. The result
> is
> > > StaticVector, which is boost.array directly modified with a size in
> front
> > of
> > > the array, and added facilities to match std::vector.
> > >
> > > The Implementation is available at:
> > > https://github.com/ahundt/Boost.StaticVector
>
>
> I believe there is interest -- in fact, there's already such a library in
> the review queue. It's Thorsten Ottosen's AutoBuffer library.
>

I had thought that was slightly different. I may be misremembering, but I
had thought StaticVector has a statically-determined maximum size, while
AutoBuffer is something like a variant< StaticVector, std::vector >...

- Jeff

Andrew Hundt

unread,
Oct 10, 2011, 4:53:35 PM10/10/11
to bo...@lists.boost.org
>
> > I believe there is interest -- in fact, there's already such a library in
> > the review queue. It's Thorsten Ottosen's AutoBuffer library.
> >
>
>
It appears there is only malloc allocation available in AutoBuffer now, not
the in-object allocation I use. While I'm trying to maintain the simplicity
of boost.array with size tracking, that may not be others' goal. I would be
happy to try adding the allocation style of StaticVector as an additional
allocator in AutoBuffer. Unfortunately, I am not sure how I could add the
functionality I'm looking for to AutoBuffer myself. Is there a resource I
could use to learn what I need to allocate the memory block inside the
AutoBuffer object itself without pointers to externally allocated memory? It
would be greatly appreciated.


> I had thought that was slightly different. I may be misremembering, but I
> had thought StaticVector has a statically-determined maximum size, while
> AutoBuffer is something like a variant< StaticVector, std::vector >...


I happen to be using it in an embedded environment myself, but I can use
exceptions. Is there some good example code somewhere that I can use as a
style guide for implementing a no exceptions option?

Cheers!
Andrew Hundt

Marshall Clow

unread,
Oct 10, 2011, 6:36:19 PM10/10/11
to bo...@lists.boost.org
On Oct 10, 2011, at 3:47 AM, Peter Myerscough-Jackopson wrote:

> Andrew Hundt <athundt <at> gmail.com> writes:
>
>>
>> On Sun, Aug 14, 2011 at 5:55 AM, Andrew Hundt <athundt <at> gmail.com> wrote:
>>
> <snip>
>>> three.push_back(2); // size: 2 capacity: 3
>>> three.push_back(3);
>>>
>>> three.push_back(1); // throws std::out_of_range exception indicating the
>>> capacity has been exceeded
>
> Is there any chance that the error behaviour code be configurable. StaticVector
> looks ideal for embedded environments, BUT commonly exceptions are disabled in
> such an environment. It would be nice to have asserts instead of exceptions
> available in all cases, so that a programmer can check for room on a push_back
> prior to calling it. A specific StaticVector macro would suffice for those that
> need it.

IMHO, That's the whole point of using BOOST_THROW_EXCEPTION(x) instead of a naked "throw x"

If exceptions are disabled, then BOOST_THROW_EXCEPTION just calls exit().

-- Marshall

Marshall Clow Idio Software <mailto:mclow...@gmail.com>

A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait).
-- Yu Suzuki

Andrew Hundt

unread,
Oct 10, 2011, 7:04:36 PM10/10/11
to bo...@lists.boost.org
After looking through AutoBuffer carefully, I have determined that while
StaticVector and AutoBuffer are similar, each has different goals:
*
StaticVector goal:*
A subset of std::vector that closely matches Boost.Array with additional
size tracking, with a fixed capacity defined at compile time.

*AutoBuffer goal:*
A superset of std::vector with a higher performance stack based buffer
that falls back on dynamic allocation when that stack is exhausted.


I have found several cases where AutoBuffer fails to meet the goals tackled
by StaticVector:

1) Memory Size - AutoBuffer cannot handle large 64 bit sizes right now,
although this simple to fix.

2) Object Size - AutoBuffer stores a size, capacity, and a pointer to itself
(or an allocated buffer) making the object size significantly greater for
small buffers. In the smallest reasonable case of an AutoBuffer containing 2
chars, the size would be around 19 bytes, compared to around 3 bytes for
StaticVector. However, I may be counting incorrectly depending on factors
such as alignment.

3) Performance - I expect StaticVector to be at least slightly faster. This
is because StaticVector does not have to determine if data is on the stack
or the heap, and there is one fewer pointer dereference.

4) Allocation - I personally have a specific requirement where I have to
place objects in exactly the right location in memory to work with a legacy
interprocess allocator. This makes the Allocators currently in AutoBuffer an
unacceptable option. I could meet this goal using AutoBuffer with an
allocator that simply throws an exception (bad_alloc?) or returns an error
any time an allocation is attempted, but why have this overhead when it
isn't necessary?

StaticVector has clear limitations due to its fixed capacity. However,
StaticVector seems to target a specific set of goals that are exclusive to
the current implementation of AutoBuffer. While some goals can be worked
around within AutoBuffer, others cannot because the end goal of AutoBuffer
differs from the end goal of StaticVector. Does this seem like a fair
assessment?

*
*
Cheers!
Andrew Hundt

Andrew Hundt

unread,
Oct 10, 2011, 7:20:53 PM10/10/11
to bo...@lists.boost.org
>
>
> > Is there any chance that the error behaviour code be configurable.
> StaticVector
> > looks ideal for embedded environments, BUT commonly exceptions are
> disabled in
> > such an environment. It would be nice to have asserts instead of
> exceptions
> > available in all cases, so that a programmer can check for room on a
> push_back
> > prior to calling it. A specific StaticVector macro would suffice for
> those that
> > need it.
>
> IMHO, That's the whole point of using BOOST_THROW_EXCEPTION(x) instead of a
> naked "throw x"
>
> If exceptions are disabled, then BOOST_THROW_EXCEPTION just calls exit().
>
> -- Marshall
>
> Marshall Clow Idio Software <mailto:mclow...@gmail.com>
>
>
I have updated StaticVector to use the BOOST_THROW_EXCEPTION macro, so it
can now be built with exceptions disabled.

Cheers!
Andrew Hundt

Matt Calabrese

unread,
Oct 10, 2011, 7:27:01 PM10/10/11
to bo...@lists.boost.org
On Mon, Oct 10, 2011 at 7:04 PM, Andrew Hundt <ath...@gmail.com> wrote:

> After looking through AutoBuffer carefully, I have determined that while
> StaticVector and AutoBuffer are similar, each has different goals:


Sorry, you're correct. I mis-remembered.

--
-Matt Calabrese

Peter Myerscough-Jackopson

unread,
Oct 11, 2011, 4:48:23 AM10/11/11
to bo...@lists.boost.org

BOOST_THROW_EXCEPTION can be set to call a user defined function
boost_throw_exception, I am unaware of BOOST_THROW_EXCEPTION calling
exit(). The real issue is that even setting BOOST_NO_EXCEPTION and
BOOST_EXCEPTION_DISABLE, the user of a library is still required to
defined the boost_throw_exception function EVEN if the user checks that
calls are valid, i.e. the user performs their own capacitycheck and
rangecheck prior to calling. This means that you cannot compile up a
library including StaticVector without exceptions without defining
boost_throw_exception, even though because you check conditions prior to
calling functions. This pollutes the library unnecessarily, and means
users of a library that uses StaticVector have to provide a function
that is not used (boost_throw_exception) or that if they have defined it
for their own needs then it is somewhat concerning that an imported
library may appear to want to call it. Both of these are bad, and the
same issue exists inside boost::function. To resolve this it would be
useful to have an extension to the interface in some form to allow a
pushing and popping action to occur without a range/capacity check
function that can throw, but I would like to propose that an assert is
called instead. To maintain safety the checking functions could return
success/failure, and the calling functions maintain the object's state
invariants based upon the return code.

Alternatively the push/pop functions could also return bool signifying
success/failure.

In looking at this I also note that there is a StaticVector( Iter begin,
Iter end ) that calls capacitycheck(). This then potentially throws, is
this truly desirable in a constructor? I see in a number of places where
the StaticVector is essentially copying from another unknown storage
class that could be larger than the StatcVector that it also could
throw, did you consider merely copying all that could be copied? i.e.
the first N objects are copied. I can't think if that would be better or
worse? It would certainly circumvent the need for checking/throwing in
some places.

Yours,

Peter

Ps. As an aside the capacity check function could be static.

Andrew Hundt

unread,
Oct 11, 2011, 12:22:40 PM10/11/11
to bo...@lists.boost.org
>
>
> BOOST_THROW_EXCEPTION can be set to call a user defined function
> boost_throw_exception, I am unaware of BOOST_THROW_EXCEPTION calling
> exit(). The real issue is that even setting BOOST_NO_EXCEPTION and
> BOOST_EXCEPTION_DISABLE, the user of a library is still required to
> defined the boost_throw_exception function EVEN if the user checks that
> calls are valid, i.e. the user performs their own capacitycheck and
> rangecheck prior to calling.


I can understand the desire to reduce the constant calls to capacitycheck, I
need to give this some thought. This seems like a design choices that is
common enough to have a convention. Is anyone aware of one?


> This means that you cannot compile up a
> library including StaticVector without exceptions without defining
> boost_throw_exception, even though because you check conditions prior to
> calling functions. This pollutes the library unnecessarily, and means
> users of a library that uses StaticVector have to provide a function
> that is not used (boost_throw_exception) or that if they have defined it
> for their own needs then it is somewhat concerning that an imported
> library may appear to want to call it. Both of these are bad, and the
> same issue exists inside boost::function.


Calls to boost::throw_exception also exists in boost.array. I'm not sure
defining boost::throw_exception is an overly onerous requirement for when
exceptions are disabled, and it seems to be a somewhat widely used
convention within boost.


> To resolve this it would be
> useful to have an extension to the interface in some form to allow a
> pushing and popping action to occur without a range/capacity check
> function that can throw, but I would like to propose that an assert is
> called instead.


Since my goal is to provide a mix of the functionality in boost.array and
std::vector, I have matched their interface whenever possible. I don't find
it unreasonable to call BOOST_THROW_EXCEPTION, because it is done in
boost.array. Actually, they call boost::throw_exception, but my
understanding is that the end effect is comparable.


> To maintain safety the checking functions could return
> success/failure, and the calling functions maintain the object's state
> invariants based upon the return code.
>
> Alternatively the push/pop functions could also return bool signifying
> success/failure.
>

The definition of push_back for std::vector is:

void push_back ( const T& x );

which is why I chose to go with the same interface.


>
> In looking at this I also note that there is a StaticVector( Iter begin,
> Iter end ) that calls capacitycheck(). This then potentially throws, is
> this truly desirable in a constructor? I see in a number of places where
> the StaticVector is essentially copying from another unknown storage
> class that could be larger than the StatcVector that it also could
> throw, did you consider merely copying all that could be copied? i.e.
> the first N objects are copied. I can't think if that would be better or
> worse?


Am I correct that insert(pos,first,last) can achieve that purpose? Nasty,
difficult to find bugs would occur if someone makes an error and only the
first N objects are copied silently when they expect all objects to be
copied. Scott Meyers' wonderful Effective C++ third edition, Item 18 "make
interfaces easy to use correctly and hard to use incorrectly" provides a
good explanation of this type of choice.


> Ps. As an aside the capacity check function could be static.
>
>

You are correct, capacitycheck should be static. Thanks for finding that.


Thanks for the time and consideration you have given the implementation.

Cheers!
Andrew Hundt

Emil Dotchevski

unread,
Oct 11, 2011, 2:30:20 PM10/11/11
to bo...@lists.boost.org
On Tue, Oct 11, 2011 at 1:48 AM, Peter Myerscough-Jackopson
<peter.myersco...@macltd.com> wrote:

>>-----Original Message-----
> BOOST_THROW_EXCEPTION can be set to call a user defined function
> boost_throw_exception, I am unaware of BOOST_THROW_EXCEPTION calling
> exit().

BOOST_THROW_EXCEPTION should not be messed with, it is not designed to
be a customization point.

By design, (Boost) libraries use BOOST_THROW_EXCEPTION to enforce
postconditions. The only way to avoid throwing an exception in such
cases is to #define BOOST_NO_EXCEPTIONS and provide a user-defined
boost::throw_exception, which is not allowed to return.

Emil Dotchevski
Reverge Studios, Inc.
http://www.revergestudios.com/reblog/index.php?n=ReCode

Eelis van der Weegen

unread,
Oct 11, 2011, 12:41:06 PM10/11/11
to bo...@lists.boost.org
On 2011-10-09 19:59, Andrew Hundt wrote:
> Anyone still have additional thoughts or interest in this?

I think this type of container is very useful, and would love to see one
in Boost. Should you decide to submit your library for review, I will
definitely review it. :)

Eelis

Andrew Hundt

unread,
Oct 11, 2011, 3:41:07 PM10/11/11
to bo...@lists.boost.org
On Tue, Oct 11, 2011 at 12:41 PM, Eelis van der Weegen <ee...@eelis.net>wrote:

> On 2011-10-09 19:59, Andrew Hundt wrote:
>
>> Anyone still have additional thoughts or interest in this?
>>
>
> I think this type of container is very useful, and would love to see one in
> Boost. Should you decide to submit your library for review, I will
> definitely review it. :)
>
> Eelis
>
>

Great, thank you! I'm looking at the submission process page at:

http://www.boost.org/development/submissions.html

It appears I am currently at the "determine interest" stage. What must I do
to make a preliminary submission?

Cheers!
Andrew Hundt

Stewart, Robert

unread,
Oct 11, 2011, 4:03:13 PM10/11/11
to bo...@lists.boost.org
Andrew Hundt wrote:
>
> I'm looking at the submission process page at:
>
> http://www.boost.org/development/submissions.html
>
> It appears I am currently at the "determine interest" stage.
> What must I do to make a preliminary submission?

You've already done that since you've made code available. You're really moving into the Refinement step now.

_____
Rob Stewart robert....@sig.com
Software Engineer using std::disclaimer;
Dev Tools & Components
Susquehanna International Group, LLP http://www.sig.com


________________________________

IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

Christian Holmquist

unread,
Oct 11, 2011, 7:55:42 PM10/11/11
to bo...@lists.boost.org
On 11 October 2011 14:41, Andrew Hundt <ath...@gmail.com> wrote:

> On Tue, Oct 11, 2011 at 12:41 PM, Eelis van der Weegen <ee...@eelis.net
> >wrote:
>
> > On 2011-10-09 19:59, Andrew Hundt wrote:
> >
> >> Anyone still have additional thoughts or interest in this?
> >>
> >
> > I think this type of container is very useful, and would love to see one
> in
> > Boost. Should you decide to submit your library for review, I will
> > definitely review it. :)
> >
> > Eelis
> >
> >
> Great, thank you! I'm looking at the submission process page at:
>
>

I second that. I've been using boost::array<> with a sentinel value to
indicate end, which is both ugly and requires length to be 1 longer than
needed.
boost::container::static_vector seems like a good addition, maybe it can be
reviewed for inclusion in upcoming Boost.Container.

FWIW, I think that static_vector should throw std::bad_alloc if it runs out
of space, to mimic an out of memory situation for ordinary containers.
(Consider an algorithm that needs temporary storage, and user passes a
static_vector as tmp storage policy. The algorithm might be designed to
handle std::bad_alloc in some way).

- Christian

Jeffrey Lee Hellrung, Jr.

unread,
Oct 11, 2011, 8:11:02 PM10/11/11
to bo...@lists.boost.org
On Tue, Oct 11, 2011 at 4:55 PM, Christian Holmquist
<c.hol...@gmail.com>wrote:

> On 11 October 2011 14:41, Andrew Hundt <ath...@gmail.com> wrote:
>
> > On Tue, Oct 11, 2011 at 12:41 PM, Eelis van der Weegen <ee...@eelis.net
> > >wrote:
> >
> > > On 2011-10-09 19:59, Andrew Hundt wrote:
> > >
> > >> Anyone still have additional thoughts or interest in this?
> > >>
> > >
> > > I think this type of container is very useful, and would love to see
> one
> > in
> > > Boost. Should you decide to submit your library for review, I will
> > > definitely review it. :)
> > >
> > > Eelis
> > >
> > >
> > Great, thank you! I'm looking at the submission process page at:
> >
> >
> I second that. I've been using boost::array<> with a sentinel value to
> indicate end, which is both ugly and requires length to be 1 longer than
> needed.
> boost::container::static_vector seems like a good addition, maybe it can be
> reviewed for inclusion in upcoming Boost.Container.
>
> FWIW, I think that static_vector should throw std::bad_alloc if it runs out
> of space, to mimic an out of memory situation for ordinary containers.
> (Consider an algorithm that needs temporary storage, and user passes a
> static_vector as tmp storage policy. The algorithm might be designed to
> handle std::bad_alloc in some way).
>

I'm presently against any throwing behavior related to resizing of a
StaticVector/static_vector, since one can usually easily check the relevant
preconditions themselves. Just assert. For those who want defined behavior
in resize overflow (or underflow) situations, I'd say derive or wrap. Some
kind of policy template parameter could be possible, but right now it feels
like that's an unnecessary complication on an otherwise relatively simple
data structure.

That's not to say I can't be dissuaded from this opinion.

- Jeff

Marshall Clow

unread,
Oct 11, 2011, 8:19:05 PM10/11/11
to bo...@lists.boost.org

If you are checking all the preconditions yourself, why do you care if it throws or not?
[ That sounds glib - but it's a serious question. ]

Why do you care if it ASSERTs, calls abort (), throws, or gets your cat pregnant?

-- Marshall

Marshall Clow Idio Software <mailto:mclow...@gmail.com>

A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait).
-- Yu Suzuki


Matt Calabrese

unread,
Oct 11, 2011, 8:21:29 PM10/11/11
to bo...@lists.boost.org
On Tue, Oct 11, 2011 at 8:11 PM, Jeffrey Lee Hellrung, Jr. <
jeffrey....@gmail.com> wrote:

> I'm presently against any throwing behavior related to resizing of a
> StaticVector/static_vector, since one can usually easily check the relevant
> preconditions themselves. Just assert. For those who want defined
> behavior
> in resize overflow (or underflow) situations, I'd say derive or wrap. Some
> kind of policy template parameter could be possible, but right now it feels
> like that's an unnecessary complication on an otherwise relatively simple
> data structure.
>
> That's not to say I can't be dissuaded from this opinion.


My stance is that push_back, for instance, should throw if it goes beyond
capacity. This is primarily for consistency with other containers. I would
say, if it proves useful, to have a non-throwing version by a different name
in addition to push_back that has undefined behavior when going beyond the
capacity. This would be similar to how vectors have both the operator []
overload and the "at" member function.

--
-Matt Calabrese

Christian Holmquist

unread,
Oct 11, 2011, 8:25:27 PM10/11/11
to bo...@lists.boost.org
On 11 October 2011 19:11, Jeffrey Lee Hellrung, Jr. <
jeffrey....@gmail.com> wrote:

It's not always you know that you're dealing with a static_vector, but just
some code that expects push_back() to work or throw.


> in resize overflow (or underflow) situations, I'd say derive or wrap. Some
> kind of policy template parameter could be possible, but right now it feels
> like that's an unnecessary complication on an otherwise relatively simple
> data structure.
>

A lot of things get simplified when ignoring correctness.

- Christian

Nathan Ridge

unread,
Oct 11, 2011, 9:01:33 PM10/11/11
to Boost Developers Mailing List

> If you are checking all the preconditions yourself, why do you care if it throws or not?
> [ That sounds glib - but it's a serious question. ]
>
> Why do you care if it ASSERTs, calls abort (), throws, or gets your cat pregnant?

You care because if it throws, it is incurring the runtime cost of checking
whether the precondition has been met. If you also check the precondition
yourself, then this runtime cost is being incurred twice, for no reason.

The design choice between throwing and undefined behaviour (in release
builds, where asserts become no-ops) boils down to the choice of who
should check the precondition: the callee, or the caller. Tradition has
favoured the caller checking the precondition whenever possible, because
the caller has more information and can sometimes check more efficiently
(e.g. by eliding the check altogether in cases where it already knows the
precondition is met). Note that vector::push_back() throwing on out-of-memory
is *not* a counterexample to this - unlike exceeding the capacity of a
StaticVector, running out of memory is not a condition that can be checked
beforehand by the caller.

Regards,
Nate

Nevin Liber

unread,
Oct 12, 2011, 2:50:04 AM10/12/11
to bo...@lists.boost.org
On 11 October 2011 20:01, Nathan Ridge <zerat...@hotmail.com> wrote:
>
>> If you are checking all the preconditions yourself, why do you care if it throws or not?
>> [ That sounds glib - but it's a serious question. ]
>>
>> Why do you care if it ASSERTs, calls abort (), throws, or gets your cat pregnant?
>
> You care because if it throws, it is incurring the runtime cost of checking
> whether the precondition has been met.

So does the assert. The "complication" is there (performance is a
different issue) unless you make it undefined behavior AND ignore it.

> The design choice between throwing and undefined behaviour (in release
> builds, where asserts become no-ops) boils down to the choice of who
> should check the precondition: the callee, or the caller. Tradition has
> favoured the caller checking the precondition whenever possible, because
> the caller has more information and can sometimes check more efficiently
> (e.g. by eliding the check altogether in cases where it already knows the
> precondition is met).

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).

> Note that vector::push_back() throwing on out-of-memory
> is *not* a counterexample to this - unlike exceeding the capacity of a
> StaticVector, running out of memory is not a condition that can be checked
> beforehand by the caller.

Sure it is. You can duplicate the functionality of exponential growth
by calling size(), capacity() and reserve() before doing push_back().

I'd really like to see the interface be as close to C++11 std::vector
as possible (other than vector<bool>).


--
 Nevin ":-)" Liber  <mailto:ne...@eviloverlord.com(847) 691-1404

_______________________________________________

Andrew Hundt

unread,
Oct 12, 2011, 5:32:01 AM10/12/11
to bo...@lists.boost.org
On Tue, Oct 11, 2011 at 7:55 PM, Christian Holmquist
<c.hol...@gmail.com>wrote:

> On 11 October 2011 14:41, Andrew Hundt <ath...@gmail.com> wrote:


I'm fairly certain that throwing bad_alloc causes a number of show stopping
problems. For example, one may choose to catch the bad_alloc, then free some
extra memory that is being kept around before trying to call push_back
again. Of course the second push_back would also throw bad_alloc, so nothing
good would be accomplished.

Cheers!
Andrew Hundt

Andrew Hundt

unread,
Oct 12, 2011, 5:43:27 AM10/12/11
to bo...@lists.boost.org
> 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).
>
>
Thanks for finding the bug! I added it to my list.


>
> I'd really like to see the interface be as close to C++11 std::vector
> as possible (other than vector<bool>).


This is definitely one of my goals.

Perhaps it would be reasonable to add an unchecked_push_back like the one in
AutoBuffer. That way, both those that want and do not want extra checks can
be happy.

I am trying to tackle one bug that I simply haven't been able to understand.
My test program benchStaticVector calls a function that adds some random
std::set<std::size_t> to a StaticVector, then returns it to a local variable
and lets it go out of scope. It seems the destructor is being called on the
return, but for some reason the copy isn't happening correctly. Then, when
the local variable goes out of scope free gets called on uninitialized
memory. Does anyone know what type of problem might be the cause of this?
Perhaps I am missing some should-be-obvious function from my implementation?

Thanks for all the great comments!

Cheers!
Andrew Hundt

Stewart, Robert

unread,
Oct 12, 2011, 6:37:19 AM10/12/11
to bo...@lists.boost.org
Christian Holmquist wrote:
>
> boost::container::static_vector seems like a good addition,
> maybe it can be reviewed for inclusion in upcoming
> Boost.Containers.

That certainly would be the simplest way to add it to Boost and seems like the right place for it. You just need to see if Ion is interested.

_____
Rob Stewart robert....@sig.com
Software Engineer using std::disclaimer;
Dev Tools & Components
Susquehanna International Group, LLP http://www.sig.com


________________________________

IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

_______________________________________________

Stewart, Robert

unread,
Oct 12, 2011, 6:38:59 AM10/12/11
to bo...@lists.boost.org
Nevin Liber wrote:
> On 11 October 2011 20:01, Nathan Ridge
> <zerat...@hotmail.com> wrote:
>
> >> If you are checking all the preconditions yourself, why do
> >> you care if it throws or not?
> >> [ That sounds glib - but it's a serious question. ]
> >>
> >> Why do you care if it ASSERTs, calls abort (), throws, or
> >> gets your cat pregnant?
> >
> > You care because if it throws, it is incurring the runtime
> > cost of checking whether the precondition has been met.
>
> So does the assert. The "complication" is there (performance
> is a different issue) unless you make it undefined behavior AND
> ignore it.

He did call out the runtime cost, so he was addressing performance which you set aside.

> > The design choice between throwing and undefined behaviour
> > (in release builds, where asserts become no-ops) boils down
> > to the choice of who should check the precondition: the
> > callee, or the caller. Tradition has favoured the caller
> > checking the precondition whenever possible, because the
> > caller has more information and can sometimes check more
> > efficiently (e.g. by eliding the check altogether in cases
> > where it already knows the precondition is met).
>
> 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.

That can be handled by dispatching on iterator category. When the iterators are random access, computing the input range size is O(1), so the insert can be as efficient as possible. Otherwise, a checking copy operation can be used.

Generally, making it undefined behavior when exceeding capacity is the more efficient approach. One can always wrap such a class to create one that checks. The reverse is not true.

> > Note that vector::push_back() throwing on out-of-memory
> > is *not* a counterexample to this - unlike exceeding the
> > capacity of a StaticVector, running out of memory is not a
> > condition that can be checked beforehand by the caller.
>
> Sure it is. You can duplicate the functionality of exponential
> growth by calling size(), capacity() and reserve() before doing
> push_back().

This really comes down to whether static_vector is considered something more akin to std::array or std::vector.

> I'd really like to see the interface be as close to C++11
> std::vector as possible (other than vector<bool>).

Interface is one thing. That doesn't address the idea of throwing exceptions when exceeding capacity. Many wanting to use static_vector in embedded environments don't want exceptions. The rest of us find them useful. Still, BOOST_THROW_EXCEPTION provides a means to configure that, but it affects all Boost code; localizing the effect may be desirable. Matt called for a differently named container as a means to provide the no-exception behavior. I think a policy class, defaulted to the throwing behavior, is the better approach, despite Jeff's thinking it an unnecessary complication.

_____
Rob Stewart robert....@sig.com
Software Engineer using std::disclaimer;
Dev Tools & Components
Susquehanna International Group, LLP http://www.sig.com

________________________________

IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

_______________________________________________

Olaf van der Spek

unread,
Oct 12, 2011, 7:39:06 AM10/12/11
to bo...@lists.boost.org
On Wed, Oct 12, 2011 at 12:38 PM, Stewart, Robert
<Robert....@sig.com> wrote:
>> I'd really like to see the interface be as close to C++11
>> std::vector as possible (other than vector<bool>).
>
> Interface is one thing.  That doesn't address the idea of throwing exceptions when exceeding capacity.  Many wanting to use static_vector in embedded environments don't want exceptions.  The rest of us find them useful.  Still, BOOST_THROW_EXCEPTION provides a means to configure that, but it affects all Boost code; localizing the effect may be desirable.  Matt called for a differently named container as a means to provide the no-exception behavior.  I think a policy class, defaulted to the throwing behavior, is the better approach, despite Jeff's thinking it an unnecessary complication.

Is it a logic error or a runtime error? IMO exceeding the capacity
here is a logic error and should be handled with an assert by default.
Isn't it comparable to doing a pop_back() on an empty vector?

Olaf

Stewart, Robert

unread,
Oct 12, 2011, 8:19:11 AM10/12/11
to bo...@lists.boost.org
Olaf van der Spek wrote:
> On Wed, Oct 12, 2011 at 12:38 PM, Stewart, Robert
> <Robert....@sig.com> wrote:
> >> I'd really like to see the interface be as close to C++11
> >> std::vector as possible (other than vector<bool>).
> >
> > Interface is one thing. That doesn't address the idea of
> > throwing exceptions when exceeding capacity. Many wanting to
> > use static_vector in embedded environments don't want
> > exceptions. The rest of us find them useful. Still,
> > BOOST_THROW_EXCEPTION provides a means to configure that, but
> > it affects all Boost code; localizing the effect may be
> > desirable. Matt called for a differently named container as
> > a means to provide the no-exception behavior. I think a
> > policy class, defaulted to the throwing behavior, is the
> > better approach, despite Jeff's thinking it an unnecessary
> > complication.
>
> Is it a logic error or a runtime error? IMO exceeding the
> capacity here is a logic error and should be handled with an
> assert by default.
> Isn't it comparable to doing a pop_back() on an empty vector?

It depends upon whether static_vector is modeled like std::vector or std::array and whether we're referring to the subscript operator or push_back(). For the subscript operator, it's a logic error in both std::vector and std::array. For push_back, it's a runtime error (std::bad_alloc) because a vector grows. std::array doesn't have push_back(), of course, but static_vector manages size and capacity separately, so it will. Therefore, it isn't a logic error if you follow std::vector's example.

_____
Rob Stewart robert....@sig.com
Software Engineer using std::disclaimer;
Dev Tools & Components
Susquehanna International Group, LLP http://www.sig.com


________________________________

IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

_______________________________________________

Matt Calabrese

unread,
Oct 12, 2011, 10:37:01 AM10/12/11
to bo...@lists.boost.org
On Wed, Oct 12, 2011 at 6:38 AM, Stewart, Robert <Robert....@sig.com>wrote:

> Matt called for a differently named container as a means to provide the
> no-exception behavior. I think a policy class, defaulted to the throwing
> behavior, is the better approach, despite Jeff's thinking it an unnecessary
> complication.
>

To be clear, I wasn't suggesting two containers, I was suggesting a single
container with something like "push_back" and "unchecked_push_back", similar
to how std::vector has both operator[] and "at" member functions. I don't
think we have to (or even should) make a decision one-way or the other for
the entire type, just like vector doesn't make that decision about
bounds-checking for a given instantiation. Let the user decide on a
case-by-case basis via the member function that they call since it's a
fine-grained trade-off that doesn't have to be made by the type. I'm not
sure how many people share the following view, but I am personally grateful
that the STL does not have two templates "vector" and
"bounds_checked_vector" or a single template with a policy. It's simply not
necessary since the presence of both operator[] and at() covers the issue.

As for having "push_back" and "unchecked_push_back" rather than "push_back"
and "checked_push_back" -- the former approach avoids introducing additional
preconditions to a very common standard container member function name. One
advantage of this in practice is that it makes it easy for users to do
drop-in replacements of std::vector with boost::static_vector without any
subtle introductions of undefined behavior. Another is that it makes it
easier for readers of the code to know the preconditions of the function
without having to look to see if the type uses a "checked_capacity" policy
when instantiating the template or not. If a user can guarantee that a
push_back or resize will not go beyond capacity, they may then go and use a
separately named function and anyone reading the code will immediately see
that choice at the call-site. Reusing the name push_back but with extra
preconditions makes it more difficult for someone to understand what is
going on from the function name since you then have two different kinds of
push_back.

To be clear, I do agree that in most cases a user would often prefer the
unchecked version (just as how in practice, a user may often be able to use
operator[] rather than at()), I only disagree on the name of that function.
Perhaps unchecked_push_back is a nasty name, but that can be changed.

--
-Matt Calabrese

Olaf van der Spek

unread,
Oct 12, 2011, 12:03:28 PM10/12/11
to bo...@lists.boost.org
On Wed, Oct 12, 2011 at 4:37 PM, Matt Calabrese <riv...@gmail.com> wrote:
> To be clear, I do agree that in most cases a user would often prefer the
> unchecked version (just as how in practice, a user may often be able to use
> operator[] rather than at()), I only disagree on the name of that function.
> Perhaps unchecked_push_back is a nasty name, but that can be changed.

What about algorithms that call push_back, like back_inserter?
Will you provide them as well?

Olaf

Andrew Hundt

unread,
Oct 12, 2011, 1:20:46 PM10/12/11
to bo...@lists.boost.org
What about algorithms that call push_back, like back_inserter?
> Will you provide them as well?
>
> Olaf


I think back_inserter should work until you reach the capacity.

Cheers!
Andrew Hundt

Nathan Ridge

unread,
Oct 12, 2011, 1:21:09 PM10/12/11
to Boost Developers Mailing List

> >> If you are checking all the preconditions yourself, why do you care if it throws or not?
> >> [ That sounds glib - but it's a serious question. ]
> >>
> >> Why do you care if it ASSERTs, calls abort (), throws, or gets your cat pregnant?
> >
> > You care because if it throws, it is incurring the runtime cost of checking
> > whether the precondition has been met.
>
> So does the assert. The "complication" is there (performance is a
> different issue) unless you make it undefined behavior AND ignore it.

An assert does not incur a runtime cost in release builds. It's just a tool
to help catch programming mistakes in debug builds. From an interface
perspective, it's just as if the function assumes the precondition is met
and invokes undefined behaviour otherwise.

> > Note that vector::push_back() throwing on out-of-memory
> > is *not* a counterexample to this - unlike exceeding the capacity of a
> > StaticVector, running out of memory is not a condition that can be checked
> > beforehand by the caller.
>
> Sure it is. You can duplicate the functionality of exponential growth
> by calling size(), capacity() and reserve() before doing push_back().

Fine, "condition that can be checked beforehand by the caller" is not a
sufficiently precise criterion for what should throw and what should assert.

A more precise criterion is to assert when failing to meet a precondition is
a programming/logic error, and throw when it's something beyond the
programmer's control. (Hacks aside, that usually corresponds to conditions
that can be checked beforehand by the caller, and ones that cannot, but this
more precise criterion captures the essence better.)

My point is, exceeding a capacity bound known at compile time clearly falls
into the former category, while running out of memory falls into the latter.

Regards,
Nate

Nathan Ridge

unread,
Oct 12, 2011, 1:30:48 PM10/12/11
to Boost Developers Mailing List

> > I'm presently against any throwing behavior related to resizing of a
> > StaticVector/static_vector, since one can usually easily check the relevant
> > preconditions themselves. Just assert. For those who want defined
> > behavior
> >
> It's not always you know that you're dealing with a static_vector, but just
> some code that expects push_back() to work or throw.

Consider a generic algorithm that takes a "push_back-able" type and inserts
elements into it using push_back(), and expects the push_back() to work to throw.

When you invoke this algorithm, you either know in advance how
many elements it will add, or you don't.

If you do, then when calling this algorithm *with a static_vector*, you need
to check beforehand whether there is enough space in the static_vector.
I think that's a reasonable requirement, given that you know, at the call site,
that you're dealing with a static_vector.

If you don't, then calling the algorithm with a static_vector is a conceptual
error in the first place, because you are passing a container with a fixed
capacity to an algorithm that expects to be able to add a variable number
of elements to it.

Regards,
Nate

Christian Holmquist

unread,
Oct 12, 2011, 6:36:12 PM10/12/11
to bo...@lists.boost.org

I realize the validity of your point, and I don't disagree in general.
But I often look through the eyes of code maintenance for very large
projects, and if
I encounter a line like:
m_Somethings.push_back(...);
I don't consider that a possible source of undefined behaviour.
It's too easy for a maintenance programmer to add another line exactly the
same, without realizing he's broken the preconditions.

If that code would read
m_Somethings.unchecked_push_back(...) it's at least less likely that someone
would add another such line without further investigation.

Either way, some people want an unchecked version and others want a checked
version, both are useful, admittedly.. Question is if we should have
1) push_back() & unchecked_push_back()
or
2) push_back() & checked_push_back().

- christian

Howard Hinnant

unread,
Oct 12, 2011, 6:52:15 PM10/12/11
to bo...@lists.boost.org
On Oct 9, 2011, at 1:59 PM, Andrew Hundt wrote:

> On Sun, Aug 14, 2011 at 5:55 AM, Andrew Hundt <ath...@gmail.com> wrote:
>
>> I've implemented a small companion class to boost.array that functions
>> like a stack allocated vector with fixed capacity. The motivation for this
>> class came when I was using boost.array in an interprocess library, when I
>> realized that I actually desired an adjustable size boost.array, without the
>> complexity of the vector class in the interprocess library. The result is
>> StaticVector, which is boost.array directly modified with a size in front of
>> the array, and added facilities to match std::vector.
>>
>> The Implementation is available at:
>> https://github.com/ahundt/Boost.StaticVector
>>
>> Sample Code:
>> StaticVector<std::size_t,3> three;
>> three.push_back(5);


>> three.push_back(2); // size: 2 capacity: 3
>> three.push_back(3);
>>
>> three.push_back(1); // throws std::out_of_range exception indicating the
>> capacity has been exceeded
>>

>> So here is the big question:
>> Is there any interest in the class?
>>
>> Cheers!
>> Andrew Hundt
>

Fwiw, one can create allocators that allocate off the stack and then turn any container into a static_container. Here's an example vector, list and set: http://home.roadrunner.com/~hinnant/stack_alloc.html

This particular implementation will spill to heap if the static buffer is overrun. But you could easily build another allocator that had another behavior. Just doing an allocator and res-using existing allocator-aware containers (e.g. std::vector) seems like a win to me.

Howard

Andrew Hundt

unread,
Oct 12, 2011, 7:08:51 PM10/12/11
to bo...@lists.boost.org
>
>
> 1) push_back() & unchecked_push_back()
> or
> 2) push_back() & checked_push_back().


If it was between 1 and 2, I would still find option (1) to be the best,
because it keeps things closer to std::vector. However, one alternative
would be to choose another name for the unchecked version. Its not like
vec.at() or vec[N] really say much about how they check things. Even so, the
lack of naming expressiveness in one function hardly justifies keeping
others cryptic. Nonetheless, perhaps there are other options that work:

3) push_back() & put_back()
4) push_back() & set_back()

I like option 3 much better than 4, since set is already so heavily used,
and better than 2 for the reasons above. I'm undecided between 1 and 3.

Cheers!
Andrew Hundt

Stephan T. Lavavej

unread,
Oct 12, 2011, 7:26:26 PM10/12/11
to bo...@lists.boost.org
[Howard Hinnant]

> Fwiw, one can create allocators that allocate off the stack and then turn any container into a static_container.
> Here's an example vector, list and set: http://home.roadrunner.com/~hinnant/stack_alloc.html

> This particular implementation will spill to heap if the static buffer is overrun. But you could easily build
> another allocator that had another behavior. Just doing an allocator and res-using existing allocator-aware
> containers (e.g. std::vector) seems like a win to me.

C++03 forbids "internal storage" allocators (when an allocator returns memory from "inside itself").

C++03 20.1.5 [lib.allocator.requirements]'s tables say (they don't copy/paste well, so I have to type them in by hand - these are only the relevant portions):

Variable # Definition
T, U # any type
X # an Allocator class for type T
Y # the corresponding Allocator class for type U
a, a1, a2 # values of type X&
b # a value of type Y

expression # return type # assertion/note pre/post-condition
a1 == a2 # bool # returns true iff storage allocated from each can be deallocated via the other
X a(b); # # post: Y(a) == b

Here's why this rules out "internal storage" allocators.

1. I start with Y b; which is MyAlloc<U> b;
2. I construct X a(b); which is MyAlloc<T> a(b);
3. I construct Y c(a), giving it a name for clarity. That's MyAlloc<U> c(a).

b is the original MyAlloc<U>. c is the doubly-rebound MyAlloc<U>. They're required to compare equal, which means that storage allocated from one can be deallocated from the other and vice versa.

This is possible for stateless allocators (e.g. if you just call malloc/free), or stateful allocators that store things like heap handles (the heap handle is passed along by the rebinding constructor). It is impossible for "internal storage" allocators, because b and c will have separate internal storage.

Also, consider how "internal storage" allocators affect moving and swapping containers.

Taking advantage of C++03's requirements, VC11 contains optimizations that will break "internal storage" allocators, even in the absence of moving/swapping. It avoids storing stateless allocators completely, and stores only one copy of a stateful allocator - rebinding it on the fly whenever it needs to allocate a secret node type, a super secret proxy type, etc. C++03's requirements guarantee that as long as the container keeps at least one copy of a stateful allocator around, regardless of the type that it's for, it can be rebound to any other type and service allocations for that type (i.e. keeping one copy around will keep all allocations around, regardless of their type).

C++03 has no objection to allocators returning memory that happens to live on the stack, as long as it is "separate" from the allocator itself and its lifetime is sufficient.

STL

Andrew Hundt

unread,
Oct 12, 2011, 9:23:11 PM10/12/11
to bo...@lists.boost.org
>
>
> > The design choice between throwing and undefined behaviour (in release
> > builds, where asserts become no-ops) boils down to the choice of who
> > should check the precondition: the callee, or the caller. Tradition has
> > favoured the caller checking the precondition whenever possible, because
> > the caller has more information and can sometimes check more efficiently
> > (e.g. by eliding the check altogether in cases where it already knows the
> > precondition is met).
>
> 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?

On this topic, what is the difference between
boost::random_access_traversal_tag and std::random_access_iterator_tag, and
should I implement both?

Cheers!
Andrew Hundt

Nathan Ridge

unread,
Oct 12, 2011, 11:35:50 PM10/12/11
to Boost Developers Mailing List

> > 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

Stewart, Robert

unread,
Oct 13, 2011, 7:02:41 AM10/13/11
to bo...@lists.boost.org
Nathan Ridge wrote:
>
> > > 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).
> > >
> > 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?

_____
Rob Stewart robert....@sig.com
Software Engineer using std::disclaimer;
Dev Tools & Components
Susquehanna International Group, LLP http://www.sig.com

________________________________

IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

_______________________________________________

Andrew Hundt

unread,
Oct 13, 2011, 10:38:28 AM10/13/11
to bo...@lists.boost.org
>> 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.

What is the reasoning for not both?

Cheers!
Andrew Hundt

Thijs (M.A.) van den Berg

unread,
Oct 13, 2011, 10:42:34 AM10/13/11
to bo...@lists.boost.org
I found some a references via google about a quadrature project (numerical integration).
http://hugoduncan.org/boostable/doc/html/index.html

I can't find any trace in the sandbox... Does anybody know the status of this project?

Andrew Hundt

unread,
Oct 13, 2011, 10:54:55 AM10/13/11
to bo...@lists.boost.org
>>
>> 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?
>

I agree that optimizing for the success case is the better choice when
evaluating the length is not O(1). Since StaticVector forces the user
to choose exactly what size it will be at compile time, it can only be
reasonable to assume that they will choose a size that will succeed.
That would make any failure case in which the capacity is exceeded an
extremely exceptional situation which should be evaluated as lazily as
possible. Furthermore, if there is a significant chance that the
capacity will be exceeded, it can be checked by the user before
calling a function in StaticVector. This is similar to the reason why
it is desirable to make an unchecked_push_back style function
available.

Cheers!
Andrew Hundt

Thomas Klimpel

unread,
Oct 13, 2011, 11:07:39 AM10/13/11
to bo...@lists.boost.org
Thijs (M.A.) van den Berg wrote:
> I found some a references via google about a quadrature project
> (numerical integration).
> http://hugoduncan.org/boostable/doc/html/index.html
>
> I can't find any trace in the sandbox...

How about <https://github.com/boost-vault/Math-Numerics/blob/master/quadrature.tgz>?

> Does anybody know the status of this project?

No idea.

Regards,
Thomas

Dave Abrahams

unread,
Oct 13, 2011, 12:32:36 PM10/13/11
to bo...@lists.boost.org

on Wed Oct 12 2011, Olaf van der Spek <ml-AT-vdspek.org> wrote:

> On Wed, Oct 12, 2011 at 12:38 PM, Stewart, Robert
> <Robert....@sig.com> wrote:
>>> I'd really like to see the interface be as close to C++11
>
>>> std::vector as possible (other than vector<bool>).
>>
>> Interface is one thing.  That doesn't address the idea of throwing
>> exceptions when exceeding capacity.  Many wanting to use
>> static_vector in embedded environments don't want exceptions.  The
>> rest of us find them useful.  Still, BOOST_THROW_EXCEPTION provides
>> a means to configure that, but it affects all Boost code; localizing
>> the effect may be desirable.  Matt called for a differently named
>> container as a means to provide the no-exception behavior.  I think
>> a policy class, defaulted to the throwing behavior, is the better
>> approach, despite Jeff's thinking it an unnecessary complication.
>
> Is it a logic error or a runtime error? IMO exceeding the capacity
> here is a logic error and should be handled with an assert by default.
> Isn't it comparable to doing a pop_back() on an empty vector?

Indeed; I object to handling something that is almost certainly going to
be a programming error with a defined behavior of throwing an exception
(yes, I think std::vector::at is a mistake), for several reasons:

- It limits your ability to detect bugs: once you make the behavior
defined, you don't know whether a programming error has been committed
anymore.

- It responds by unwinding, which can destroy valuable debugging
information

- It does way more than absolutely necessary, which, in a program whose
invariants may be broken, may prevent emergency measures from
completing successfully.

That said, I am not a security guy, and I understand those people who
want to eliminate avoidable, open-ended, undefined behavior whenver
possible. Therefore I think that it might make sense to establish a
BOOST_SEMISECURE mode, and to encourage library authors are
free/encouraged to say something like:

If <some requirement> is not satisfied, the behavior is undefined.

In BOOST_SEMISECURE mode the library will (or may) check <some
requirement> using BOOST_ASSERT.

The point being that

a. We can unambiguously mark some usage as incorrect
b. Those who don't want it don't have to pay for the check
c. The behavior of check failures can be tuned.

--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

Andrew Hundt

unread,
Oct 13, 2011, 2:20:35 PM10/13/11
to bo...@lists.boost.org

This makes me curious. If logic errors should only be caught with an
assert in the case of defining a specific macro definition, is there
still a case where one should use std::logic_error and family? If not,
does that amount to de facto deprecation?

Nathan Ridge

unread,
Oct 13, 2011, 3:23:08 PM10/13/11
to Boost Developers Mailing List

> > > 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

Nathan Ridge

unread,
Oct 13, 2011, 3:38:06 PM10/13/11
to Boost Developers Mailing List

> >> 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.
>
> What is the reasoning for not both?

Because they're pretty much the same thing.

Your tag dispatching logic will be something like this:

if (boost::iterator_traversal<Iterator>::type is boost::random_access_traversal_tag)
call the random access version
else
call the input iterator version

Of course it won't look like that, the choice will be made at compile time
via template specialization, but that's the logic.

You can also have the logic:

if (std::iterator_traits<Iterator>::iterator_category is std::random_access_iterator_tag)
call the random access version
else
call the input iterator version

But it wouldn't make sense to do something like:

if (boost::iterator_traversal<Iterator>::type is boost::random_access_traversal_tag)

call the random access version
else if (std::iterator_traits<Iterator>::iterator_category is std::random_access_iterator_tag)
call the random access version
else

call the input iterator version


because the first case covers all the random access iterators already.

Hope that makes sense... or maybe I'm misunderstanding what you mean by
"implement both"?

Regards,
Nate

Nathan Ridge

unread,
Oct 13, 2011, 3:39:31 PM10/13/11
to Boost Developers Mailing List

> This makes me curious. If logic errors should only be caught with an
> assert in the case of defining a specific macro definition, is there
> still a case where one should use std::logic_error and family? If not,
> does that amount to de facto deprecation?

Perhaps std::logic_error should be used for errors in the user's logic,
not the programmer's logic?

Regards,
Nate

Thijs (M.A.) van den Berg

unread,
Oct 13, 2011, 4:04:22 PM10/13/11
to bo...@lists.boost.org

> Thijs (M.A.) van den Berg wrote:
>> I found some a references via google about a quadrature project
>> (numerical integration).
>> http://hugoduncan.org/boostable/doc/html/index.html
>>
>> I can't find any trace in the sandbox...
>
> How about <https://github.com/boost-vault/Math-Numerics/blob/master/quadrature.tgz>?
>
>> Does anybody know the status of this project?
>
> No idea.
>

Thanks for the pointer. I've send the author an email, let's see why it's apparently on hold?

Ion Gaztañaga

unread,
Oct 13, 2011, 4:46:14 PM10/13/11
to bo...@lists.boost.org
El 12/10/2011 12:37, Stewart, Robert escribió:
> Christian Holmquist wrote:
>>
>> boost::container::static_vector seems like a good addition,
>> maybe it can be reviewed for inclusion in upcoming
>> Boost.Containers.
>
> That certainly would be the simplest way to add it to Boost and seems like the right place for it. You just need to see if Ion is interested.

It's interesting but we need some consensus on several issues (If swap
is O(N), should it be provided?, unchecked functions? what to do when
there is no room for more elemnets?) and the implementation should
support movable types and other goodies from boost.Container.

One of the extensions I was thinking for Boost.Container was a fixed
capacity vector, and the solution I planned was reusing
boost::container::vector code, maybe with some extensions supporting a
pseudo-allocator. boost::container:: vector could treat this
pseudo-allocator specially and avoid storing a m_capacity or m_pointer
member to save some words. Then allocate() could implement the policy
(assert, throw, or just ignore).

There are more issues. Do we want to support some kind of StaticVector
compatible with shared memory? then we need to specify pointer and
const_pointer as those define the pointer type stored in iterators...

Anyway, I think that we could implement an approach similar to Howard's
stack_alloc quite easily, and get most benefits with a bit of size overhead.

Ion

Lars Viklund

unread,
Oct 13, 2011, 4:59:30 PM10/13/11
to bo...@lists.boost.org
On Thu, Oct 13, 2011 at 10:04:22PM +0200, Thijs (M.A.) van den Berg wrote:
>
> > Thijs (M.A.) van den Berg wrote:
> >> I found some a references via google about a quadrature project
> >> (numerical integration).
> >> http://hugoduncan.org/boostable/doc/html/index.html
> >>
> >> I can't find any trace in the sandbox...
> >
> > How about <https://github.com/boost-vault/Math-Numerics/blob/master/quadrature.tgz>?
> >
> >> Does anybody know the status of this project?
> >
> > No idea.
> >
>
> Thanks for the pointer. I've send the author an email, let's see why it's apparently on hold?

When posting to the Boost lists (or any mailing list at all), if you
have a new thread of conversation, please send it as a new message to
the list instead of replying to an existing message.

Replying to an existing message will put your new message in the thread
hierarchy of an existing thread instead of top-level.

People like I who read some threads with Mark-Thread-As-Read will never
see it.

--
Lars Viklund | z...@acc.umu.se

Ion Gaztañaga

unread,
Oct 13, 2011, 5:13:16 PM10/13/11
to bo...@lists.boost.org
El 13/10/2011 1:26, Stephan T. Lavavej escribió:
> C++03 forbids "internal storage" allocators (when an allocator returns memory from "inside itself").

AFAIK, C++11 also requires:

X a(b); Shall not exit via an exception.
post: Y(a) == b, a == X(b)

Best,

Ion

Stephan T. Lavavej

unread,
Oct 13, 2011, 6:44:26 PM10/13/11
to bo...@lists.boost.org
[STL]

> C++03 forbids "internal storage" allocators (when an allocator returns memory from "inside itself").

[Ion Gaztañaga]


> AFAIK, C++11 also requires:
> X a(b); Shall not exit via an exception.
> post: Y(a) == b, a == X(b)

Yep, thanks for looking that up. I recycled an old mail from my archives where I cited C++03. :->

STL

Andrew Hundt

unread,
Oct 13, 2011, 7:08:49 PM10/13/11
to bo...@lists.boost.org
2011/10/13 Ion Gaztañaga <igazt...@gmail.com>:

> It's interesting but we need some consensus on several issues

IMO, here are the most interesting and consensus worthy choices so far

> If swap is O(N), should it be provided?

Yes, I am fairly certain std::array provides a linear swap, and
boost.array definitely provides it, so StaticVector should too.

> unchecked functions?

They should definitely be provided.

> what to do when there is no room for more elements?

After comments by Nate Ridge, Dave Abrahams, and others, I have become
convinced that push_back should be unchecked and exceeding the bounds
should be undefined, with an option to turn on checking.

I haven't been convinced how the option should be defined, though I've
seen several options:
1) locally defined option
2) defined generally for boost
3) combination of 1 and 2, since they are not mutually exclusive
4) policy based.

> and the implementation should support movable
> types and other goodies from boost.Container.
> One of the extensions I was thinking for Boost.Container was a fixed
> capacity vector, and the solution I planned was reusing
> boost::container::vector code, maybe with some extensions supporting a
> pseudo-allocator. boost::container:: vector could treat this
> pseudo-allocator specially and avoid storing a m_capacity or m_pointer
> member to save some words. Then allocate() could implement the policy
> (assert, throw, or just ignore).
>

Interesting. So this stack allocated pseudo-allocator would look and
act (partially) like an allocator, but not fit the definition of one
due to the C++03 and C++11 rules against them.

Is this suggesting that boost::container::vector be directly modified
to support both fixed capacity as well, or just mixing some of the
shared code in?

> There are more issues. Do we want to support some kind of StaticVector
> compatible with shared memory? then we need to specify pointer and
> const_pointer as those define the pointer type stored in iterators...
>
> Anyway, I think that we could implement an approach similar to Howard's
> stack_alloc quite easily, and get most benefits with a bit of size overhead.

so considering the other posts that internal storage allocators are
forbidden, how would this work?

Well that may mark the end of my StaticVector work, but that is how
these things go. At the very least there has been productive
discussion. Although, perhaps the size overhead advantage of
StaticVector would allow room for it considering to the difference it
could make for embedded systems.

Nevin Liber

unread,
Oct 13, 2011, 10:36:44 PM10/13/11
to bo...@lists.boost.org
On 13 October 2011 18:08, Andrew Hundt <ath...@gmail.com> wrote:
> After comments by Nate Ridge, Dave Abrahams, and others, I have become
> convinced that push_back should be unchecked and exceeding the bounds
> should be undefined, with an option to turn on checking.


While I really disagree with this (as there are both use cases for it
and, more importantly, it is no longer a drop in replacement for
vector because your push_back will now behave differently), don't just
do it for push_back; do it for all the insert methods as well.
--
 Nevin ":-)" Liber  <mailto:ne...@eviloverlord.com(847) 691-1404

Andrew Hundt

unread,
Oct 13, 2011, 10:56:17 PM10/13/11
to bo...@lists.boost.org
On Thu, Oct 13, 2011 at 10:36 PM, Nevin Liber <ne...@eviloverlord.com> wrote:
> On 13 October 2011 18:08, Andrew Hundt <ath...@gmail.com> wrote:
>> After comments by Nate Ridge, Dave Abrahams, and others, I have become
>> convinced that push_back should be unchecked and exceeding the bounds
>> should be undefined, with an option to turn on checking.
>
>
> While I really disagree with this (as there are both use cases for it
> and, more importantly, it is no longer a drop in replacement for
> vector because your push_back will now behave differently),

While I wish it could be a drop in replacement, I think it would be
unreasonable to throw bad_alloc, since no allocations even happen at
all. Thus, it couldn't be a truly drop in replacement anyway.

Additionally, I found that since the behavior of accessing
vector.begin()-1 is undefined, that makes an undeniably compelling
argument that the correct behavior for accessing StaticVector.end()+1
should also be undefined.

> don't just do it for push_back; do it for all the insert methods as well.

that is the plan

Cheers!
Andrew Hundt