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.lists@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

-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Marshall Clow Sent: 10 October 2011 23:36 To: boost@lists.boost.org Subject: Re: [boost] Interest in StaticVector - fixed capacity vector

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

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.

On Tue, Oct 11, 2011 at 1:48 AM, Peter Myerscough-Jackopson <peter.myerscough-jackopson@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

On Mon, Oct 10, 2011 at 10:18 AM, Matt Calabrese <rivorus@gmail.com> wrote:

On Sun, Oct 9, 2011 at 1:59 PM, Andrew Hundt <athundt@gmail.com> wrote:

...

On Sun, Aug 14, 2011 at 5:55 AM, Andrew Hundt <athundt@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

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 On Mon, Oct 10, 2011 at 4:53 PM, Andrew Hundt <athundt@gmail.com> wrote:

...

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

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.stewart@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.

On Tue, Oct 11, 2011 at 4:55 PM, Christian Holmquist <c.holmquist@gmail.com>wrote:

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

...

On Tue, Oct 11, 2011 at 12:41 PM, Eelis van der Weegen <eelis@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

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

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

On Wed, Oct 12, 2011 at 12:38 PM, Stewart, Robert <Robert.Stewart@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

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.Stewart@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

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

On Wed, Oct 12, 2011 at 6:38 AM, Stewart, Robert <Robert.Stewart@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

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

...

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 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.stewart@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.

...

...

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

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?

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?

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. Does anybody know the status of this project?

I would be interested in seeing progress here as well. I believe, however, that if anyone wants to undertake the creation of a comprehensive collection of quadrature algorithms, then flexibility to handle multiple-precision numbers. (Yes, I know that this would be difficult.) Boost already has some support for multiple-precision in Boost.Math. In addition, some *potential* new works such as Boost.Multiprecision and Boost.Big_Number (both in sandbox now) work toward formalization of the semantics of multiple-precision numbers. So new math algorithms might want to target compatibility with these new potential works. In addition, my examples 5 and 8 in Boost.Multiprecision exemplify rudimentary quadrature as well as Gauss-Laguerre quadrature for multiple-precision numbers. Perhaps this might help a potential quadrature algorithm author in some small way. Sincerely, Chris.

On Tue, Oct 11, 2011 at 8:11 PM, Jeffrey Lee Hellrung, Jr. < jeffrey.hellrung@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

...

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

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

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.stewart@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.

2011/10/13 Ion Gaztañaga <igaztanaga@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.

On Thu, Oct 13, 2011 at 10:36 PM, Nevin Liber <nevin@eviloverlord.com> wrote:

On 13 October 2011 18:08, Andrew Hundt <athundt@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

on Thu Oct 13 2011, Nevin Liber <nevin-AT-eviloverlord.com> wrote:

On 13 October 2011 18:08, Andrew Hundt <athundt@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

Use-cases, please! Let's not overlook anything important in this discussion.

and, more importantly, it is no longer a drop in replacement for vector because your push_back will now behave differently),

How could it ever be a "drop-in replacement for vector" when it comes to exceeding a reasonably low length bound? A vector is probably going to succeed to push_back past that bound, while this class definitely won't. Unless you plan to intentionally leverage this exception (in which case vector wasn't serving your needs, so your code needs more than a "drop-in-replacement" anyway), then it's *going* to change the behavior of your program if and when you cause it to be thrown. Maybe I'm missing something. -- Dave Abrahams BoostPro Computing http://www.boostpro.com

on Fri Oct 14 2011, Andrew Hundt <athundt-AT-gmail.com> wrote:

On Fri, Oct 14, 2011 at 6:32 AM, Dave Abrahams <dave@boostpro.com> wrote:

...

...

on Thu Oct 13 2011, Nevin Liber <nevin-AT-eviloverlord.com> wrote:

...

On 13 October 2011 18:08, Andrew Hundt <athundt@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

Use-cases, please!

use case for unchecked: copying point clouds, packets, geometry, or other sets of small objects with fixed size through an intermediate buffer that either has to be allocated frequently, where space is extremely limited, or where allocation is simply not an option.

I know those, of course. Another one you failed to mention: when you want to implement your own checking ;-)

use case for checked: copying user input where you have a fixed length limit anyway due to other limitations,

How do you use the exception in a correct program for this case?

or the type of data being input, or any other case where performance is not important and correctness/lack of errors is.

Is throwing an exception going to turn an incorrect program into a correct one?

...

How could it ever be a "drop-in replacement for vector" when it comes to exceeding a reasonably low length bound?  A vector is probably going to succeed to push_back past that bound, while this class definitely won't. Unless you plan to intentionally leverage this exception (in which case vector wasn't serving your needs, so your code needs more than a "drop-in-replacement" anyway), then it's *going* to change the behavior of your program if and when you cause it to be thrown.

Maybe I'm missing something.

- Perhaps one uses vector while prototyping on their nice quad core 64 bit machine, then they need to cut things down and set strict limits once the prototype works to get it on their cell phone, game console, or even smaller device like a router or radio chip.

Yeah... in that case they almost certainly don't want to pay for the check. But if they do want a check, how is an exception going to help them?

- On the completely opposite end of the spectrum, processing an extremely large dataset that has fixed size datums. One could again prototype with vectors, but now they need something a bit more constrained to optimize performance for their datacenter.

Again, how does the exception help? How do you use that?

- Yet another case is existing code that uses vectors, but have a constraint that makes a perfect case for switching to StaticVectors like the ones above.

These are all basically the same case AFAICT ;-) -- Dave Abrahams BoostPro Computing http://www.boostpro.com

on Fri Oct 14 2011, Andrew Hundt <athundt-AT-gmail.com> wrote:

...

...

use case for checked: copying user input where you have a fixed length limit anyway due to other limitations,

How do you use the exception in a correct program for this case?

ah, exceptions in a correct program! I don't believe I have ever seen a program that is both nontrivial and correct :-)

I cannot think of cases where given a correct program an exception should be thrown with a fixed capacity vector, aside from testing that the exceptions are thrown correctly :-). As far as I can think at the moment, if your program is correct you should never exceed the capacity of a fixed size vector.

...

...

or the type of data being input, or any other case where performance is not important and correctness/lack of errors is.

Is throwing an exception going to turn an incorrect program into a correct one?

If you catch that exception and do something reasonable, would it not?

No. "Reasonable" doesn't mean you fulfill your original intention/specification. You don't normally write specifications that say, "...unless the code is wrong, in which case I'll do something reasonable," nor do you code to perform an operation in two different ways in case one of them turns out to have coding errors, do you?

Perhaps this only makes the argument of making it "less wrong".

Is that like "less pregnant?" More precisely, it avoids some undefined behaviors, which has some security benefits. That's why I proposed the SEMISECURE mode.

...

...

...

How could it ever be a "drop-in replacement for vector" when it comes to exceeding a reasonably low length bound?  A vector is probably going to succeed to push_back past that bound, while this class definitely won't. Unless you plan to intentionally leverage this exception (in which case vector wasn't serving your needs, so your code needs more than a "drop-in-replacement" anyway), then it's *going* to change the behavior of your program if and when you cause it to be thrown.

Maybe I'm missing something.

- Perhaps one uses vector while prototyping on their nice quad core 64 bit machine, then they need to cut things down and set strict limits once the prototype works to get it on their cell phone, game console, or even smaller device like a router or radio chip.

Yeah... in that case they almost certainly don't want to pay for the check.  But if they do want a check, how is an exception going to help them?

Black box: If you have to use an existing algorithm or function that you cannot change or do not know exactly how the internals work, you can catch the exception and handle it in a reasonable way.

Too much hand-waving. What possible "reasonable way?" Are you going to try to achieve the same semantics in a different way? [And why "how the internals work" matters is beyond me].

Alternately, if you are creating the black box, you could do the same for the data they give you.

Ditto

Prototyping: I find exceptions helpful when they immediately kill my program when I do something wrong at the prototyping stage, as compared to random stack jumps into other places when I'm just allowed to try and access that memory. Much easier to find and fix quickly :-)

Thus a recommendation for a SEMISECURE mode where you can tune the response. The builtin assert() facility almost always kills your program at /least/ as usefully and quickly as an exception.

...

...

- On the completely opposite end of the spectrum, processing an extremely large dataset that has fixed size datums. One could again prototype with vectors, but now they need something a bit more constrained to optimize performance for their datacenter.

Again, how does the exception help?  How do you use that?

The execution of what?

Did I write "execution?" -- Dave Abrahams BoostPro Computing http://www.boostpro.com

on Fri Oct 14 2011, Andrew Hundt <athundt-AT-gmail.com> wrote:

...

...

...

Is throwing an exception going to turn an incorrect program into a

...

...

...

correct one?

If you catch that exception and do something reasonable, would it not?

No.  "Reasonable" doesn't mean you fulfill your original intention/specification.  You don't normally write specifications that say, "...unless the code is wrong, in which case I'll do something reasonable,"

I'm fairly certain that writing specifications this way is quite common.

I was asking about you, personally.

For instance, consider a program that catches exceptions and crashes, then generates and sends a bug report to the creators. Does that application not catch when the code is wrong, then do something reasonable?

Its specification doesn't say "do something reasonable;" it says "send a bug report to the creators."

Of course this is not correct behavior with respect to the original goal, but I would argue that is is correct behavior with respect to a secondary goal of finding incorrect behavior that prevents reaching the original goal.

Sure, but exceptions are a poor way to get that effect.

Furthermore, I don't believe I am being very original with this idea. Java has the ArrayOutOfBounds exception. Please, I beg you not to take this as the belief that Java is correct. I am simply unconvinced by your argument and I am playing devil's advocate by pointing out an example counter to the point you are making.

I don't know what to say. Java is a mostly-different story; they have no undefined behavior in the language, so they have to do something else. IMO using EH to deal with programming errors is usually a mistake, but it's one that's been repeated far and wide.

...

More precisely, it avoids some undefined behaviors, which has some security benefits.  That's why I proposed the SEMISECURE mode.

Why should the mode be SEMISECURE by default, and not a RELAXED_SECURITY mode for when you absolutely need the highest performance?

Everybody wants a different default; I'm not here to argue about that except that I'll say people get upset when they turn on all the optimizations and then pay for checks they weren't expecting.

also, what is the disadvantage of providing, push_back(), checked_push_back(), and unchecked_push_back(), where a policy or struct tag allows the checkedness (pardon my word frankenstein) to be decided at either the instantiation or the call site, respectively?

Creeping—nay, rampaging—complexity.

To draw an analogy, designing code to use RAII can sometimes incur a performance penalty with the benefit of preventing a failure to release a resource. Of course you can always "just free" that resource by hand, but changes in one portion of an application can have unforeseen consequences in another to those who are dealing with a small portion of a very large or complex system. Therefore it has become commonplace to pay a small penalty for the benefit of preventing problems. In this case, that problem is undefined behavior, and the penalty is the checks. Perhaps an out of bounds error does not meet the complexity level required for such a cost to be worthwhile, but if I am not mistaken myself, it is one of the most common mistakes made by anyone. However, this does not prevent one from making the other choice, and calling the unchecked version when they absolutely need the performance.

The core of what I am saying is that checks + exceptions make it easier to find, prevent, and/or report problems.

The checks are not the problem; the exceptions are. And they don't help with finding, preventing, or reporting problems.

There are a some items I would like to verify so I can clarify my understanding of your argument.

First, I believe that you are saying that code is already incorrect when it goes out of bounds,

Probably.

so you might as well just let it keep running with undefined behavior unless a special SEMISECURE flag is set.

No.

Furthermore, by the time you reach the point where I am proposing that an exception be thrown, the code is already incorrect, therefore the exception will never prevent an error, and thus the exception should not exist. Is this correct?

That's one way to look at it, but it's not what I said. The main problems are the ones I cited before in this thread (you can go back and look them up).

What are the metrics by which you define an exception as both incorrect and/or worse? What is lost by using an exception? Does it break a convention, reduce performance, break purity, or upend general happiness?

All answered already in my first posting in the thread. -- Dave Abrahams BoostPro Computing http://www.boostpro.com

On 14 October 2011 12:55, Dave Abrahams <dave@boostpro.com> wrote:

Is throwing an exception going to turn an incorrect program into a correct one?

I'm probably completely misunderstanding your point of view, or rather, what is your point of view? Not throwing the exception will turn a correct program into an incorrect one if that program relies on the exception. That's the case I'm most worried about, incorrect programs not so much. I find them difficult to reason about, but maybe that's just me..

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

- Christian

On 14 October 2011 16:07, Peter Dimov <pdimov@pdimov.com> wrote:

Christian Holmquist wrote:

...

On 14 October 2011 12:55, Dave Abrahams <dave@boostpro.com> wrote:

...

Is throwing an exception going to turn an incorrect program into a correct one?

I'm probably completely misunderstanding your point of view, or rather, what is your point of view?

He's saying that if a program does a push_back when the capacity has been reached, this program has a logic error, and throwing an exception will not make the error go away.

To me this is like saying that if any exception is thrown, the program has a logic error. It's not very helpful though. All code which does not deal with global OS data (such as the heap, files, etc) can be written as no throw, if enough details are exposed for the user. But I want code to throw so that I don't need to worry and check all details everywhere. How much juggling would I need to do to parse a comma separated text of integers into a static_vector? static_vector<int, 4> v; spirit::parse("1, 2, 3, 4, 5", int_ % ',', space, v); // undefined behaviour??? Sure, the above can be seen as having a 'logic error' because the grammar says parse N but the capacity can only handle N < 5. But the the code can never parse N anyways, because sooner or later even a std::vector runs out of memory space. I simply find it hard to accept that a predefined maximum capacity, being at compile time or runtime, should run into undefined behaviour if that capacity is exceeded. There's too much code in the world already that doesn't check limits.. STL containers has helped tremendously in this regard, I don't see why one would want to go in another direction. - Christian

on Fri Oct 14 2011, Christian Holmquist <c.holmquist-AT-gmail.com> wrote:

On 14 October 2011 16:07, Peter Dimov <pdimov@pdimov.com> wrote:

...

Christian Holmquist wrote:

...

On 14 October 2011 12:55, Dave Abrahams <dave@boostpro.com> wrote:

...

Is throwing an exception going to turn an incorrect program into a correct one?

I'm probably completely misunderstanding your point of view, or rather, what is your point of view?

He's saying that if a program does a push_back when the capacity has been reached, this program has a logic error, and throwing an exception will not make the error go away.

To me this is like saying that if any exception is thrown, the program has a logic error.

I don't see how anyone could draw that conclusion.

It's not very helpful though. All code which does not deal with global OS data (such as the heap, files, etc) can be written as no throw, if enough details are exposed for the user.

Only by reporting the error another way. There's no way for a user to check beforehand that there is going to be enough memory to complete any given job requiring a dynamic allocation. And if you consider memory "global OS data" then yes, the code that doesn't need to allocate resources and can always complete successfully in the absence of erroneous usage should be no-throw. On the other hand, /this/ problem is in the user's power to prevent, and I assert that in the vast majority of imaginable use cases the user will have tried to get prevention right (i.e. will have tried to choose the length to be sure everything fits).

But I want code to throw so that I don't need to worry and check all details everywhere.

If your code detects a programming error, you need to worry. Yes, it's true that once you say "I'm going to throw under these conditions" it's no longer certain that it's a programming error, but I assert that in this case it remains highly likely. But then the library is no longer allowed to treat it as an error and helpfully do the most appropriate thing for debugging purposes; it has to throw an exception, because it promised to. What's your program's response to that exception? In many programs when there's an exception it gets logged and it tries again later. By the time you catch the exception far from the call site, you no longer know for sure whether it was a programmer error or not, so you don't really have a choice. This is how bugs stay hidden. We mostly have a consistent practice in the C++ standard library and in Boost that we respond to programming errors with undefined behavior and *not* with a documented defined behavior, which has the effect of making it harder to detect bugs. [Now I'm proposing broadening that practice in Boost to help avoid undefined behavior.]

How much juggling would I need to do to parse a comma separated text of integers into a static_vector? static_vector<int, 4> v; spirit::parse("1, 2, 3, 4, 5", int_ % ',', space, v); // undefined behaviour???

Nobody likes "unefined behaviour???" But please allow me to replace that comment with: "// throws an exception???" It's just not the most appropriate response. For those who want checking, dropping into the debugger or dumping core or logging and terminating would be better, and those who don't will be annoyed to pay for unneeded checks when their code is correct. Why should the library be locked into providing what is almost always a suboptimal response?

Sure, the above can be seen as having a 'logic error' because the grammar says parse N but the capacity can only handle N < 5.

Um, yeah, and because you wrote the existence of 5 items right into the program at the call site. In most cases there's a better chance that it's not a logic error. If this isn't a logic error, it's a perverse way of writing "throw capacity_exceeded()" for which the programmer should receive fifty lashes with a wet noodle.

But the the code can never parse N anyways, because sooner or later even a std::vector runs out of memory space.

Oh, come now. By that reasoning, code using std::vector can never do anything with N.

I simply find it hard to accept that a predefined maximum capacity, being at compile time or runtime, should run into undefined behaviour if that capacity is exceeded. There's too much code in the world already that doesn't check limits. STL containers has helped tremendously in this regard,

Huh? Except for at(), STL containers aren't spec'd to check for misuse or out-of-bounds access. The ones that do check are doing so... **as an expression of undefined behavior**.

I don't see why one would want to go in another direction.

That's why I'm specifically proposing a mode that *does* do the checking. But we should *not* encode into the library spec that the response to a failed check is an exception in those cases where a failed check is most likely to represent a programming error. -- Dave Abrahams BoostPro Computing http://www.boostpro.com

on Sat Oct 15 2011, "Peter Dimov" <pdimov-AT-pdimov.com> wrote:

Dave Abrahams wrote:

...

Nobody likes "unefined behaviour???" But please allow me to replace

...

that comment with:

"// throws an exception???"

It's just not the most appropriate response. For those who want checking, dropping into the debugger or dumping core or logging and terminating would be better, and those who don't will be annoyed to pay for unneeded checks when their code is correct.

We (as in the authors of the example) fall in neither category of yours. We want the algorithm that does push_back to terminate when it reaches capacity. Which is exactly what it will do, without having to be rewritten.

This approach is not scalable or composable. If you have an algorithm of the form: for (...) v.push_back(whatever) then yeah, it works and you can get usable results. But as soon as your algorithm has another step after the for loop, you have to expect that the algorithm is terminated somewhere in the middle, and the results are either nil (if it gives the strong guarantee) or useless (if it gives the basic guarantee).

...

Why should the library be locked into providing what is almost always a suboptimal response?

It's your (and others') assertion that this is almost always a suboptimal response. You haven't backed it up.

If you think of this thing as a vector with a length bound, and you try to exceed the capacity, I claim it's probably a bug. IIUC, you claim it might just as well not be a bug. I'm not asking you to "back that up." I'm asking you to use your noggin and think about what happens most of the time in most of the code you see. If we say "prove it" to one another, there's going to be a stand-off, because you know as well as I do that nobody knows for certain.

Yes, it's trivial to argue that logic errors should not be exceptions, but why is push_back over capacity "almost always" a logic error?

Because for me it is like writing past the end of an array, and my intuition tells me that it will be like that for many other people. *Generally speaking*, in programming, if you ask for something with a fixed capacity you had better not exceed it if you want your program to acheieve the intended result. That's my experience. Yours may differ. Does it? If so, I'll loosen my conviction.

Heck... why is it a logic error at all, except in the trivial case in which you start with an empty static_vector<T, N> and do exactly N push_backs,

? That's not a logic error. You're not making sense to me. -- Dave Abrahams BoostPro Computing http://www.boostpro.com

on Sat Oct 15 2011, "Peter Dimov" <pdimov-AT-pdimov.com> wrote:

Dave Abrahams wrote:

...

on Sat Oct 15 2011, "Peter Dimov" <pdimov-AT-pdimov.com> wrote:

...

...

Yes, it's trivial to argue that logic errors should not be exceptions, but why is push_back over capacity "almost always" a logic error?

Because for me it is like writing past the end of an array, and my intuition tells me that it will be like that for many other people.

It's not. Writing past the end, meaning size(), of a static_vector is like writing past the end of an array. push_back into a static_vector is like push_back into a vector.

I guess I look at this static_vector as something I might use in place of an array when the element type was not default-constructible, in which case, it's a lot alike. Once you add the fixed size limit, I think vector::push_back is no longer the right analogue unless you commonly use algorithms that push_back into a vector, catch the exception, and continue. Otherwise the algorithm is going to throw, which generally means it's not going to fulfill its postconditions. I grant you that if you have a situation where you are happy to process only the first relatively-small, fixed, N elements of the data and you're willing to pay a massive performance penalty should you encounter N+1 elements, then this exception is well-suited to your job. I just don't recall ever running into such a case. Do you? In the standard library, the adaptive algorithms have to do something like this but implementations don't use vector to acquire the storage in practice... they use something that doesn't throw (e.g. malloc).

...

*Generally speaking*, in programming, if you ask for something with a fixed capacity you had better not exceed it if you want your program to achieve the intended result.

If you use static_vector<char,...> as you would a char[], then yes, I guess. It's not clear what you'd gain from it though, as the whole point of not using char[] is to eliminate the buffer overflows.

...

...

Heck... why is it a logic error at all, except in the trivial case in which you start with an empty static_vector<T, N> and do exactly N push_backs,

? That's not a logic error. You're not making sense to me.

Going over capacity would be a logic error in this case,

If you do exactly N push_backs, you're not going over capacity.

Anyway. Do you agree that the number of push_backs is typically a run time value?

Absolutely, 100% agreed. -- Dave Abrahams BoostPro Computing http://www.boostpro.com

On Sat, Oct 15, 2011 at 4:07 PM, Peter Dimov <pdimov@pdimov.com> wrote:

Dave Abrahams wrote:

...

...

Anyway. Do you agree that the number of push_backs is typically a run time value?

Absolutely, 100% agreed.

OK. So we sometimes have more elements than the static_vector can take, and this can't yet be a logic error because it's caused by input external to the program. What do we do?

[...] So, I figure it might add some fuel to the fire if I shared what one of my use cases has been for this sort of structure. I implemented a data structure called "bounded_vector" which is basically the same as the proposed "static_vector" with asserting when over-capacity (i.e., no throwing). My problem required storing a variable but compile-time-bounded number of not-necessarily-default-constructible-objects in an array. Specifically, I was storing some representation of the sub-simplex intersections between two d-dimensional simplices, where d was a compile-time constant (typically 2 or 3). The number of such intersections is bounded in terms of the dimension d, and this was a computational intensive part of the application, so avoiding heap access was desirable. To me, something like the above is a shoe-in use case for static_vector / bounded_vector: you have a variable but compile-time upper bound on the size, and, to boot, your value_type is not default constructible. I never thought of static_vector as a "drop-in replacement" for std::vector. As Dave alluded to in another message, wouldn't Thorsten's proposed AutoBuffer (which falls back to the heap when the immediate storage is exceeded) be more appropriate in cases where you want to optimize for small array sizes but also want to account for larger arrays? - Jeff

on Sat Oct 15 2011, Nathan Ridge <zeratul976-AT-hotmail.com> wrote:

After reading this thread again, it seems to me that the reason we can't reach an agreement is that different people are proposing two fundamentally different ways of using static_vector:

1) As a variant of [std|boost]::array where not all the elements are constructed/used at the same time, and which keeps track of how many elements are currently in use.

2) As a variant of std::vector which keeps its memory on the stack, and which is used, literally, as a drop-in replacement for std::vector, in the sense that the developer was using std::vector, but then identified that in non-exceptional situations the actual number of elements used is below a certain threshold, and the program could use the optimization of not allocating memory dynamically.

It's clear to me that for use (1), exceeding the bound of the static_vector is a logic error and therefore should be undefined behaviour, whereas for (2), exceeding the bound of the static_vector is not a logic error and therefore throwing an exception is reasonable.

My own previous arguments for not throwing were based on the assumption that the use case is (1), without giving (2) much thought.

But isn't use-case 2 much better served by a vector that degrades gracefully by falling back to using the heap? I just can't see how throwing serves anyone's purpose well. -- Dave Abrahams BoostPro Computing http://www.boostpro.com

...

After reading this thread again, it seems to me that the reason we can't reach an agreement is that different people are proposing two fundamentally different ways of using static_vector:

1) As a variant of [std|boost]::array where not all the elements are constructed/used at the same time, and which keeps track of how many elements are currently in use.

Can you please give some examples of such use?

For starters, any use of [std|boost]::array<T> where T is not default constructible and I do not wish to make it so just so I can use it in an array. Regards, Nate

on Sat Oct 15 2011, "Peter Dimov" <pdimov-AT-pdimov.com> wrote:

Nathan Ridge wrote:

...

My problem required storing a variable but compile-time-bounded number of not-necessarily-default-constructible-objects in an array. Specifically, I was storing some representation of the sub-simplex intersections between two d-dimensional simplices, where d was a compile-time constant (typically 2 or 3). The number of such intersections is bounded in terms of the dimension d, and this was a computational intensive part of the application, so avoiding heap access was desirable.

This is a good example. If the intended use case of this class is only when the size is compile time bounded, I agree that push_back/insert/resize should assert. If it's intended to have a wider use, though...

In the wider use-cases why isn't "fall back to the heap" the right thing to do? -- Dave Abrahams BoostPro Computing http://www.boostpro.com

Peter Dimov wrote:

Dave Abrahams wrote:

...

In the wider use-cases why isn't "fall back to the heap" the right thing to do?

I've no idea. To avoid denial of service, perhaps. Or perhaps the processing code after that is limited to a specific size anyway for performance reasons, so it makes no sense to collect more values.

Why stick to this container? Why close this funcionality inside? You are all of the time debating about one case which should be handled differently. One should provide an adaptor which would work for all: typedef std::vector<T> V; typedef static_vector<T, N> SV; // however I'd rather change the name for XXX_array bounded_buffer<V, N> bounded_vector; bounded_buffer<SV, N> bounded_XXX_array; bounded_buffer<std::list<T>, N> bounded_list; bounded_buffer<std::deque<T>, N> bounded_deque; Regards, Adam

Peter Dimov wrote:

Adam Wulkiewicz wrote:

...

Why stick to this container? Why close this funcionality inside? You are all of the time debating about one case which should be handled differently.

I don't think that "potential number of elements not bounded by a compile-time constant" can be reasonably classified as "one use case", although you could legitimately argue that it should be handled differently. That is, that people are holding it wrong. I kind of sense that you're a bit frustrated at my holding it wrong. I also predict that many others will hold it wrong. This could be their own fault, or it could be a design issue.

One use case is "inserting run-time number of elements to the container which should store compile-time number of elements finished by throwing an exception". A workaround of a problem which is "exiting from some routine's internals at some point of execution in possibly unknown place". This will work with some routines and don't with others which treat exceptions differently. And you're saying that only one specific conainer is intended for this task because other won't throw an exception in this case. Regards, Adam

on Sun Oct 16 2011, "Peter Dimov" <pdimov-AT-pdimov.com> wrote:

Dave Abrahams wrote:

...

In the wider use-cases why isn't "fall back to the heap" the right thing to do?

I've no idea. To avoid denial of service, perhaps. Or perhaps the processing code after that is limited to a specific size anyway for performance reasons, so it makes no sense to collect more values.

Seems like this is a low-level component upon which one might build containers with higher-level fallback behaviors (like throwing, or ASSERTing, or dynamic allocation). So, we're back to policies now? -- Dave Abrahams BoostPro Computing http://www.boostpro.com

So, you desperately want to optimize away an "if" check, but a copy operation on a typical class that cannot be default constructed is a-okay?

It's not like anyone has even bothered to ask for emplace_back, which would seem to me to be a far more important optimization opportunity if this were indeed a real-world use case...

Admittedly, I am in C++11-world and for this use case I was thinking of the move version of push_back(), or emplace_back() (yes, we do want these, and the fact that we haven't asked for them in this thread is simply because the recent discussion has been on a topic orthogonal to this, not because we don't want them). Regards, Nate

...

After reading this thread again, it seems to me that the reason we can't reach an agreement is that different people are proposing two fundamentally different ways of using static_vector:

1) As a variant of [std|boost]::array where not all the elements are constructed/used at the same time, and which keeps track of how many elements are currently in use.

Can you please give some examples of such use?

Another example would be the underlying data structure for a circular buffer whose maximum size is known at compile time. Regards, Nate

On Sat, Oct 15, 2011 at 5:16 PM, Nathan Ridge <zeratul976@hotmail.com> wrote:

After reading this thread again, it seems to me that the reason we can't reach an agreement is that different people are proposing two fundamentally different ways of using static_vector:

  1) As a variant of [std|boost]::array where not all the elements are       constructed/used at the same time, and which keeps track of       how many elements are currently in use.

  2) As a variant of std::vector which keeps its memory on the       stack, and which is used, literally, as a drop-in replacement       for std::vector, in the sense that the developer was using       std::vector, but then identified that in non-exceptional       situations the actual number of elements used is below a       certain threshold, and the program could use the       optimization of not allocating memory dynamically.

It's clear to me that for use (1), exceeding the bound of the static_vector is a logic error and therefore should be undefined behaviour, whereas for (2), exceeding the bound of the static_vector is not a logic error and therefore throwing an exception is reasonable.

My own previous arguments for not throwing were based on the assumption that the use case is (1), without giving (2) much thought.

It's been suggested (including by me) that we use a policy or other technique for accommodating both use cases within the same class. However, upon some reflection, I'd like to propose something more drastic:

Let's not have a class that serves two conceptually different purposes at all. It would confuse people, and lead to more buggy code, as developers conflate these two fundamentally different concepts in their head because they are both served by the same class.

Of course, both use cases are worthwhile and deserve having a class for them in boost, and one's push_back should assert and the other's should throw. We can call one capacity_array and the other stack_vector, or whatever better names we come up with - but let's not give them the same name, when they are very different beasts.

Now the implementor of these classes can implement them like this:

typedef boost::detail::static_vector<T, AssertPolicy> capacity_array; typedef boost::detail::static_vector<T, ThrowPolicy> stack_vector;

if they so choose - but the user doesn't need to know that, and should not have access to the underlying static_vector class, which does not correspond to any clear concept.

Regards, Nate

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

Nate seems to have provided the best analysis of the situation that I have seen in the thread.

But isn't use-case 2 much better served by a vector that degrades gracefully by falling back to using the heap? I just can't see how throwing serves anyone's purpose well.

As Dave Abrahams suggests, I agree that the best behavior for case (2) is falling back to the heap after exhausting the buffer, which conveniently fits the functionality provided by AutoBuffer. Therefore, I think StaticVector should focus on use case (1). I'll probably attempt to make StaticVector fulfill use case (1) with bounds checking performed using assert, in a way that makes it viable for use internally within AutoBuffer as well if the writer of that library desired to. The way I see things, if I implement StaticVector using assert, someone can inherit from my class and add exceptions if desired. I may be mistaken, but one could not do the same the other way around without any sacrifice, since some implementations of exceptions incur performance penalties. As for check/unchecked bounds, I'll start with push_back being checked, and provide unchecked_push_back + unchecked_insert. I know it is less popular than a policy based implementation but I feel like there will be reduced overhead for compiler implementations with less effective optimizations, though this is based only on others' comments earlier on in the thread. Since this is (for me at least) designed to also be useful for embedded applications which may have stricter requirements, I find this to be a sensible choice. Please rip my choices apart for me, so I can correct them now before I write more code :-) I have one additional question regarding the size. It was requested that I use boost::uint_value_t<N>::least, but I am concerned this would inhibit uses where one inherits from StaticVector to add functionality such as what is found in AutoBuffer. Should I stick to std::size_t, boost::uint_value_t<N>::least, or allow the size type to be set with a template parameter? Cheers! Andrew Hundt

Le 18/10/11 19:44, Andrew Hundt a écrit :

On Sat, Oct 15, 2011 at 5:16 PM, Nathan Ridge<zeratul976@hotmail.com> wrote:

...

After reading this thread again, it seems to me that the reason we can't reach an agreement is that different people are proposing two fundamentally different ways of using static_vector:

1) As a variant of [std|boost]::array where not all the elements are constructed/used at the same time, and which keeps track of how many elements are currently in use.

2) As a variant of std::vector which keeps its memory on the stack, and which is used, literally, as a drop-in replacement for std::vector, in the sense that the developer was using std::vector, but then identified that in non-exceptional situations the actual number of elements used is below a certain threshold, and the program could use the optimization of not allocating memory dynamically.

Nate seems to have provided the best analysis of the situation that I have seen in the thread.

...

But isn't use-case 2 much better served by a vector that degrades gracefully by falling back to using the heap? I just can't see how throwing serves anyone's purpose well. As Dave Abrahams suggests, I agree that the best behavior for case (2) is falling back to the heap after exhausting the buffer, which conveniently fits the functionality provided by AutoBuffer. Therefore, I think StaticVector should focus on use case (1). +1

I'll probably attempt to make StaticVector fulfill use case (1) with bounds checking performed using assert, in a way that makes it viable for use internally within AutoBuffer as well if the writer of that library desired to. The way I see things, if I implement StaticVector using assert, someone can inherit from my class and add exceptions if desired. I may be mistaken, but one could not do the same the other way around without any sacrifice, since some implementations of exceptions incur performance penalties. I don't see the advantage to use internally AutoBuffer here, but maybe I'm missing something evident.

As for check/unchecked bounds, I'll start with push_back being checked, and provide unchecked_push_back + unchecked_insert. I know it is less popular than a policy based implementation but I feel like there will be reduced overhead for compiler implementations with less effective optimizations, though this is based only on others' comments earlier on in the thread. Since this is (for me at least) designed to also be useful for embedded applications which may have stricter requirements, I find this to be a sensible choice. I will add that the push_back is checked only in debug mode as it will use assert. Then the unchecked version lost its utility on release mode. Please rip my choices apart for me, so I can correct them now before I write more code :-)

I have one additional question regarding the size. It was requested that I use boost::uint_value_t<N>::least, but I am concerned this would inhibit uses where one inherits from StaticVector to add functionality such as what is found in AutoBuffer. Should I stick to std::size_t, boost::uint_value_t<N>::least, or allow the size type to be set with a template parameter?

You can always add a size_type template parameter that is defaulted to boost::uint_value_t<N>::least. Best, Vicente

On 15 October 2011 08:27, Dave Abrahams <dave@boostpro.com> wrote:

...

But I want code to throw so that I don't need to worry and check all details everywhere.

If your code detects a programming error, you need to worry. Yes, it's true that once you say "I'm going to throw under these conditions" it's no longer certain that it's a programming error, but I assert that in this case it remains highly likely. But then the library is no longer allowed to treat it as an error and helpfully do the most appropriate thing for debugging purposes; it has to throw an exception, because it promised to.

It's by no means the most helpful and appropriate thing to, even for debugging purposes. If I want to catch exceptions when thrown, i instruct my environment to do so. But real world errors don't appear under a debugger, they appear on end users machines or on remote server sites and always in release builds. If something doesn't show up in an error log, it didn't happen... I realize I'm standing with another background than most others here, so I simply rest my case. It's been interesting anyways, hope I haven't disturbed too much =)

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

_______________________________________________

Cheers, - Christian

Dave Abrahams wrote:

on Fri Oct 14 2011, "Peter Dimov" <pdimov-AT-pdimov.com> wrote:

...

try { do some push_backs into a static_vector; we don't know how many } catch( out_of_capacity& ) { // ignore, what we gathered so far is good enough for gov't use }

Yes, it's possible, but highly unusual, for someone to use the class that way.

I'm not sure of that either. What makes you think so? What are the "proper" uses for it?

Adam Wulkiewicz wrote:

I'd rather use the following:

while ( sv.size() < sv.capacity() && keep_pushing ) // do a push_back into a static_vector

Yeah, if you get to rewrite all the functions that lead to the push_back. Like spirit::parse and everything it calls.

Adam Wulkiewicz wrote:

Yes and should I know what spirit::parse do if some exception is thrown inside? Maby it returns empty vector, whatever? Is it aware that some of the exceptions are ok? I don't know it and I do not want to know it.

Good point, although I suspect that it will do exactly what I expect it to do. It doesn't need to be aware of "what exceptions are OK" for that - all exceptions are (equally) OK.

Dave Abrahams wrote:

on Sat Oct 15 2011, "Peter Dimov" <pdimov-AT-pdimov.com> wrote:

...

What are the "proper" uses for it?

It sounds like you're asking me to prove something for which we both know there's no proof.

Not really. As I already said in the other message, doing more push_backs than a compile-time constant size is a logic error only when the number of push_backs is a compile-time constant as well. So, it follows that it is only proper to use static_vector when the number of push_backs is known at compile time. So I was wondering what some of these (nontrivial and variable size) uses are. As an example, a case in which 99.4% of the time the number of push_backs doesn't exceed capacity is a legitimate use, but it's not a logic error, and quite fits the mantra that "exceptions should be exceptional".

Dave Abrahams wrote:

If we can figure out how to get cars to bounce harmlessly out of collisions we could decide to make it legal to ignore stop signs and just count on the bounce to handle it. Should we?

Cars are cars, and static_vector::push_back is, well, static_vector::push_back. They have nothing in common. You can't mechanically apply the same rule to both. push_back throwing doesn't imply operator[] throwing, for example. Their uses are different. A throwing static_vector::push_back enables existing algorithms that use push_back or back_inserter to continue to work without their behavior becoming undefined. A throwing static_vector::operator[]... does not enable anything. :-)

On 13 October 2011 18:08, Andrew Hundt <athundt@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.

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

2) Please no. Global policies like BOOST_NO_THREADS and, as I think this discussion have shown, BOOST_THROW_EXCEPTION is not fine grained enough. There seems to be some consensus on the usefulness of undefined behaviour if exhausting the capacity of the vector, which is fine (even as default if stated clearly in the docs), as long as user can opt for an alternative that throws.

3) combination of 1 and 2, since they are not mutually exclusive 4) policy based.

4) seems like the best compromise. (how does 4 differ from 1?). - Christian

2011/10/14 Ion Gaztañaga <igaztanaga@gmail.com>: but we currently have no

push_back preconditions for push_back, insert, etc. and this can be a great source of mistakes.

I agree. And unlike at() vs. operator[], in this case we are moving enforcement of the class invariants from the class itself the caller, just to save an "if" check. I really don't want to see a policy controlling this; rather, have unchecked_push_back and unchecked_insert for those who need every ounce of performance at the expense of safety. --  Nevin ":-)" Liber  <mailto:nevin@eviloverlord.com>  (847) 691-1404

-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Andrew Hundt Sent: Friday, October 14, 2011 8:14 AM To: boost@lists.boost.org Subject: Re: [boost] Interest in StaticVector - fixed capacity vector

...

I really don't want to see a policy controlling this; rather, have unchecked_push_back and unchecked_insert for those who need every ounce of performance at the expense of safety.

I definitely see a lot of clarity in implementing it this way. I just wish there was a nicer name than unchecked_push_back.

If I were writing the code I would name it push_back_blindly. I have several _blindly functions in polygon. The generally mean that the caller assumes responsibility for maintaining the class invariant and that the class should skip the usual checks for performance reasons. Typically these are intended for use within the class itself, but I make them public instead of private because I trust that I can use them properly from within or without. I think unchecked_push_back is perfectly fine too. Regards, Luke

-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Andrew Hundt Sent: Friday, October 14, 2011 4:07 PM To: boost@lists.boost.org Subject: Re: [boost] Interest in StaticVector - fixed capacity vector

Side note: Can anyone think of a better name than unchecked_push_back?

push_back_unchecked ? Then it will appear in the sensible place in any alphabetical list of functions. Paul --- Paul A. Bristow, Prizet Farmhouse, Kendal LA8 8AB UK +44 1539 561830 07714330204 pbristow@hetp.u-net.com

I was thinking about that, but from what I've read on the list it seems people prefer clearer and more correct english in the function names whenever possible.

The one I keep coming across is: put_back()

Does that currently imply anything I'm not thinking of? It seems like something someone would look up if they haven't seen it, then use it correctly. It does not directly imply unchecked, but it does seem appropriate.

The names put_back() vs. push_back() suggest absolutely nothing about how these functions might be different. I'd much prefer a name that's descriptive, like unchecked_push_back, even if it's longer and clumsier. It seems the main options that have been proposed are: * push_back and unchecked_push_back * checked_push_back and push_back * just push_back, with behaviour controlled by a policy This might be overkill, but we can make everyone happy by having all three: * unchecked_push_back which does what it says; AND * checked_push_back which does what it says; AND * push_back which calls one or the other based on a policy That leaves just one thing to quibble about - the default value of the policy - but even that choice becomes less important, because those who feel strongly about the default behaviour of push_back being one or the other can just use the explicitly-named version instead. Regards, Nate

-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Andrew Hundt Sent: Friday, October 14, 2011 5:04 PM To: boost@lists.boost.org Subject: Re: [boost] Interest in StaticVector - fixed capacity vector

...

 * unchecked_push_back which does what it says; AND  * checked_push_back which does what it says; AND  * push_back which calls one or the other based on a policy

That leaves just one thing to quibble about - the default value of the policy - but even that choice becomes less important, because those who feel strongly about the default behaviour of push_back being one or the other can just use the explicitly-named version instead.

I love the sound of design-by-committee in the morning :-)

More seriously, I do think that makes sense since it allows the user to select the appropriate function for their design, but use the alternate one when necessary.

If this is what is finally settled on, I would prefer to default to a checked policy because then it will catch and prevent mistakes by default. If you have an exceptional reason for the performance, you can switch to the alternate function/policy.

I also prefer checked by default. But it is true that a policy solution will impose a run-time penalty? Can't it be a compile-time choice? Of course, there still remains opportunity for the design-by-committee members to discuss what the default should be ;-) Paul --- Paul A. Bristow, Prizet Farmhouse, Kendal LA8 8AB UK +44 1539 561830 07714330204 pbristow@hetp.u-net.com

Krzysztof Czainski:

+1 for policy based from me. I can imagine using different policy StaticVectors in the same app.

Andrew Hundt:

...

Side note: Can anyone think of a better name than unchecked_push_back?

2011/10/14 Paul A. Bristow <pbristow@hetp.u-net.com>:

push_back_unchecked ?

Then it will appear in the sensible place in any alphabetical list of functions.

I think having both checked, and unchecked versions is a good idea. I prefer the name push_back_unchecked for the same reason, as Andrew. However, I'd still like to have the option of choosing a policy for the "ckecked" versions, so I can pass different StaticVectors to the same algorithm in different contexts: a checking-one-way version of StaticVector, or a checking-another-way version, or maybe a not-checking version. This maybe sounds dangerous, but I would like that to be possible. Regards Kris

Le 14/10/11 17:06, Andrew Hundt a écrit :

Side note: Can anyone think of a better name than unchecked_push_back?

Hi, I know that people don't like tags too much, but tags could open the interface so, the choice of check policy can be deferred at a higher level. I would use the following overloads: void push_back( const T& x ); void push_back(no_check_t, const T& x); void push_back(check_t, const T& x ) { return push_back(x); } With this interface we can define an algorithm using push_back that is templated by the check policy template <typename CheckPolicy> void algo(...) { // use push_back(CheckPolicy(), x); } A user could use it also directly as push_back(no_check, x); Best, Vicente

Krzysztof Czainski wrote:

I program for embedded, and I've beed observing this discussion with interest.

+1 for policy based from me. I can imagine using different policy StaticVectors in the same app.

For sake of completeness, I'll note that Ion's idea of using a specially recognized allocator to effect the different behaviors in boost::containers::vector is in this vein. That is, being policy-based doesn't mean it has to be static_vector < class T , size_t N , class CapacityExhaustionPolicy

_____ Rob Stewart robert.stewart@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.

[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

[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