[boost] Interest in StaticVector - fixed capacity vector
Andrew Hundt
> 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
>
> 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
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
> 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.
> 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
> > I believe there is interest -- in fact, there's already such a library in
> > the review queue. It's Thorsten Ottosen's AutoBuffer library.
> >
>
>
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
> 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
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
>
> > 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>
>
>
can now be built with exceptions disabled.
Cheers!
Andrew Hundt
Matt Calabrese
> 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
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
>
> 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
<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
> 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
> 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
>
> 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
> 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.
<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
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
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
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
> 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
>
>> 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
<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
> 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'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
>
> boost::container::static_vector seems like a good addition,
> maybe it can be reviewed for inclusion in upcoming
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
> 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
<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
> 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
> 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
> 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
> Will you provide them as well?
>
> Olaf
I think back_inserter should work until you reach the capacity.
Cheers!
Andrew Hundt
Nathan Ridge
> >> 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
> > 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
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