Thorsten Ottosen wrote:

Dmitry Vinogradov skrev:

...

Boost.Array offers constant size container with preallocated buffer, Boost.Optional provides from zero to one element. There are no STL container with preallocated buffer and it seems custom allocator does not help to do this with existing containers.

Does any container exist to offer functionality like Boost.Array but allowing to store from 0 to N elements? Is there any interest in such container?

PS. It's similar to fixed_string but as a generic container.

Please see

http://www.cs.aau.dk/~nesotto/boost/auto_buffer.zip

http://www.cs.aau.dk/~nesotto/boost/trunk/libs/auto_buffer/doc/html/

Thanks! That's it.

Please see

http://www.cs.aau.dk/~nesotto/boost/auto_buffer.zip

http://www.cs.aau.dk/~nesotto/boost/trunk/libs/auto_buffer/doc/html/

Is there a review scheduled for this? Cheers, Anteru

Thorsten Ottosen wrote On Monday, May 18, 2009 9:05 AM

Dmitry Vinogradov skrev:

...

Does any container exist to offer functionality like Boost.Array but allowing to store from 0 to N elements? Is there any interest in such container?

PS. It's similar to fixed_string but as a generic container.

Please see

http://www.cs.aau.dk/~nesotto/boost/auto_buffer.zip

http://www.cs.aau.dk/~nesotto/boost/trunk/libs/auto_buffer/doc/html/

auto_buffer looks really useful, Thorsten, but I'd like to pick at it a little. boost::default_grow_policy is troubling. First, s/grow/growth/ in the name. Did you mean to that policy as appropriate for all of Boost? You put it in the boost namespace. Third, new_capacity() ought to be "reserve" because that more clearly associates it with auto_buffer<>::reserve() and the well understood behavior of, for example, std::vector<>::reserve(). auto_buffer's "StackBufferPolicy" template parameter should be named "SizingPolicy" because it has to do with computing the buffer's size. The "GrowPolicy" template parameter should be named "GrowthPolicy." The auto_buffer nested value "N" is confusing as it will change based upon the SizingPolicy, but won't match that policy's "value" if using boost::store_n_bytes, and it isn't the number of elements in, or capacity of, the auto_buffer, particularly when memory is allocated from the allocator. Renaming it to "stack_capacity" should work, though. Is there a compile time assertion for N > 0 for store_n_objects? How about that store_n_bytes<N>::value >= sizeof(T)? Those will help to diagnose misuse. There should be a debug build assertion that GrowthPolicy::reserve(n) returns a value >= n to help diagnose mistakes. "optimized_const_reference" would be better named "by_value_type" or something. For small types, optimized_const_reference isn't a reference at all, so the name is misleading. Better to name it for the usage rather than the type. What's the point of push_back() with no argument? What's the motivation for that versus making the caller explicitly default construct a T and pass that to push_back(by_value_type)? Are you simply optimizing the copying? If so, isn't it better to mimic vector and gain the optimization with move semantics? Shouldn't pop_back_n() be an algorithm rather than a member function? Is there really efficiency to be gained by making it a member and is there a good use case for that? Rather than reserve_precisely(), which should be named "reserve_exactly" if retained, why not just document reserve() as allocating what GrowthPolicy::reserve() returns and leave the behavior to the policy? That leaves room for reserve() allocating exactly what's requested, or rounding up according to some computation, as the policy dictates. The remarks for the uninitialized_*() functions use the phrase, "depending on the application," but that doesn't explain when the user is responsible to initialize or destroy the n elements. Change the remarks to note that if T is POD, the user need not initialize/destroy the affected elements, whereas not doing so for non-POD types results in undefined behavior. The unchecked_*() functions deserve remarks that explain the danger in their use and that the precondition is not checked. If you don't already, though, you should check the precondition in debug builds to help clients use these dangerous functions correctly. The description of should_shrink(), on the default_grow_policy class, mentions shrink_to_fit() which is not mentioned elsewhere in the documentation. I find shrink_to_fit() in Boost.Interprocess, but nowhere else. Did you forget something? shrink_to_stack() might be a useful addition. You probably inferred the purpose: to shrink the size to what will fit on the stack and move the contents to the stack from allocator-supplied memory, if used. That seems the logical converse of dynamically growing beyond the stack allocation, though I admit I can't think of a motivating use case beyond simply trying to keep memory consumption low in a long running function. There are numerous things to fix in the docs, plus more to add, of course, but I don't want to address those points now. I think I can find some time to help you flesh out the docs so you can submit auto_buffer for review, if you're interested. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; 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.

Thorsten Ottosen wrote:

...

The "GrowPolicy" template parameter should be named "GrowthPolicy."

Really?

"Grow" is a verb; "Growth" is a noun. "GrowthPolicy" just sounds better.

...

"optimized_const_reference" would be better named "by_value_type" or something.

...

For small types, optimized_const_reference isn't a reference at all, so the name is misleading.

...

Better to name it for the usage rather than the type.

But then for large types, "by_value_type" is not a value type, but a reference. What about parameter_type or param_type?

boost::call_traits uses param_type. I haven't looked at the code, so I'm not sure what you're using it for or if you'd just be able to use call_traits. --Jeffrey Bosboom

Thorsten Ottosen wrote On Tuesday, May 19, 2009 2:17 PM

Stewart, Robert skrev:

...

Third, new_capacity() ought to be "reserve" because that

more clearly associates it with auto_buffer<>::reserve() and the well understood behavior of, for example, std::vector<>::reserve().

Well, the function of the policy does not reserve anything itself, it just calculates the new capacity. Hence the name.

I understand your thinking. How about "grow?" It is suggestive of the purpose but less wordy. Is the signature actually sufficient? What if the requested size exceeds the adjustment new_capacity() would make? IOW, what if the requested size is greater than four times the old capacity? Would this be better? template <class Size> static Size grow(Size _old, Size _size); This means supplying the old capacity and desired size such that the result should be at least _size.

...

auto_buffer's "StackBufferPolicy" template parameter should be named "SizingPolicy" because it has to do with computing the buffer's size.

But it doesn't has much to do with the size of the container in general. So that name does not sound too good either.

That's why I didn't suggest "SizePolicy." Seriously. The policy still has to do with a size computation. "StackSizePolicy" is probably better.

...

The "GrowPolicy" template parameter should be named "GrowthPolicy."

Really?

Yes, "growth" is a noun.

...

The auto_buffer nested value "N" is confusing as it will change based upon the SizingPolicy,

...

but won't match that policy's "value" if using boost::store_n_bytes, and it isn't the number of elements in, or capacity of, the auto_buffer, particularly when memory is allocated from the allocator.

...

Renaming it to "stack_capacity" should work, though.

I'll think about it. I need a short name for the docs, and N seems both short and good to me. N is also documented.

"N" suggests number of elements to me.

...

Is there a compile time assertion for N > 0 for store_n_objects?

No, you are allowed to specify an empty stack buffer.

Why would anyone bother to create one that won't fit on the stack? Why not just use vector? Are you thinking of generic code that sometimes will succeed in using the stack and other times not? I suppose that's a good justification, but it would be worth documenting that N == 0 is permissible and why.

...

How about that store_n_bytes<N>::value >= sizeof(T)? Those will help to diagnose misuse.

This might be ok to have if 0 < N < sizeof(T).

I suppose this can occur for the same reason as above but it should be documented. Otherwise, there's no sense in allowing it.

...

"optimized_const_reference" would be better named "by_value_type" or something.

...

For small types, optimized_const_reference isn't a reference at all, so the name is misleading.

...

Better to name it for the usage rather than the type.

But then for large types, "by_value_type" is not a value type, but a reference. What about parameter_type or param_type?

Yeah, it doesn't work well for the other case. "Parameter" suggests only the input side of things. boost::call_traits does something similar, but that only has to do with calling functions. It would be odd to return a call_traits type. How about "fast_value_type?"

...

What's the point of push_back() with no argument?

...

What's the motivation for that versus making the caller explicitly default construct a T and pass that to push_back(by_value_type)?

...

Are you simply optimizing the copying? If so, isn't it better to mimic vector and gain the optimization with move semantics?

I guess it should be rename emplace(), like in vector.

That name strikes me as odd, but it will become the norm, so yes, you should use it.

...

Shouldn't pop_back_n() be an algorithm rather than a member function?

...

Is there really efficiency to be gained by making it a member and is there a good use case for that?

Yes, it is more efficient since for PODs it only adjust the size. Calling erase() would be slightly less efficient.

The documentation should note that the function is particularly efficient for PODs.

...

Rather than reserve_precisely(), which should be named "reserve_exactly" if retained,

...

why not just document reserve() as allocating what GrowthPolicy::reserve() returns and leave the behavior to the policy?

...

That leaves room for reserve() allocating exactly what's requested, or rounding up according to some computation, as the policy dictates.

reserve() is used several places when the buffer needs to grow. If this was to allocate precisely what was requested, then we would e.g. allocate just one extra element.

But I guess I could factor the code so it was as you suggested. I will make this a review question. This will require a small change in GrowPolicy so you can see what is requested.

I think the "see what is requested" is the change I suggested above.

...

The unchecked_*() functions deserve remarks that explain the danger in their use and that the precondition is not checked.

You didn't comment on the addition of remarks for these functions, so I'm re-raising this point.

...

shrink_to_stack() might be a useful addition.

shrink_to_fit() can already place the content on the stack.

OK. I assume that shrink_to_fit() takes an argument, so that shrink_to_stack() would be shorthand for a.shrink_to_fit(a.stack_capacity).

...

There are numerous things to fix in the docs, plus more to add, of course, but I don't want to address those points now.

...

I think I can find some time to help you flesh out the docs so you can submit auto_buffer for review, if you're interested.

It's already in the review queue. But I need a review manager :-)

I guess you'd rather I chose to be review manager than to help on the docs. I'll do it then. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; 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.

Thorsten Ottosen wrote On Tuesday, May 19, 2009 4:41 PM

Stewart, Robert skrev:

...

Thorsten Ottosen wrote On Tuesday, May 19, 2009 2:17 PM

...

Stewart, Robert skrev:

...

Is the signature actually sufficient? What if the requested size exceeds the adjustment new_capacity() would make?

...

IOW, what if the requested size is greater than four times the old capacity? Would this be better?

template <class Size> static Size grow(Size _old, Size _size);

This means supplying the old capacity and desired size such that the result should be at least _size.

In that case the exact requested size is allocated. The interface you show provides some extra flexibility, but I don't know if it is useful. Perhaps.

I haven't looked at your implementation of reserve(), but I was expecting that it would simply ask the policy for the new size and allocate it. Apparently, you're making decisions in reserve() over and above those made by new_capacity(). I think that will be surprising to those writing the policy.

...

...

...

The "GrowPolicy" template parameter should be named "GrowthPolicy." Really?

Yes, "growth" is a noun.

How about ResizingPolicy? The policy is also used in shrink_to_fit().

Good

...

...

...

The auto_buffer nested value "N" is confusing as it will change based upon the SizingPolicy, but won't match that policy's "value" if using boost::store_n_bytes, and it isn't the number of elements in, or capacity of, the auto_buffer, particularly when memory is allocated from the allocator. Renaming it to "stack_capacity" should work, though. I'll think about it. I need a short name for the docs, and N seems both short and good to me. N is also documented.

"N" suggests number of elements to me.

Right. And that is what it is.

Isn't it just the number of elements that will fit within the stack allocation? When the buffer switches to allocator-supplied memory, N is no longer likely to be the number of elements -- which is why you provide size().

...

Why would anyone bother to create one that won't fit on the stack? Why not just use vector?

Because auto_buffer provides additional functionality not found in std::vector.

...

Are you thinking of generic code that sometimes will succeed in using the stack and other times not?

I don't know what you mean by this, but I'm happy if there is yet another reason to use the class.

I meant a function template that creates an auto_buffer<T,store_n_bytes<N>> where sizeof(T) may be greater than N, depending upon T.

...

...

...

How about that store_n_bytes<N>::value >= sizeof(T)? Those will help to diagnose misuse. This might be ok to have if 0 < N < sizeof(T).

I suppose this can occur for the same reason as above but it should be documented. Otherwise, there's no sense in allowing it.

OTOH, I would hate to put a static assertion in there if it sometimes complicates the use when the user actually don't mind this.

It may be worth mentioning the relationship between N and sizeof(T) when using store_n_bytes as it can lead to not using the stack space.

...

...

...

For small types, optimized_const_reference isn't a reference at all, so the name is misleading. Better to name it for the usage rather than the type. But then for large types, "by_value_type" is not a value type, but a reference. What about parameter_type or param_type?

Yeah, it doesn't work well for the other case. "Parameter" suggests only the input side of things. boost::call_traits does something similar, but that only has to do with calling functions. It would be odd to return a call_traits type. How about "fast_value_type?"

It's a candidate, but again, sometimes it is a reference :-)

It is being used as a value. You're returning a T, but you're using a reference to const to avoid copying. "fast_value_type" refers to the usage rather than the type.

...

...

...

Rather than reserve_precisely(), which should be named "reserve_exactly" if retained, why not just document reserve() as allocating what GrowthPolicy::reserve() returns and leave the behavior to the policy? That leaves room for reserve() allocating exactly what's requested, or rounding up according to some computation, as the policy dictates. reserve() is used several places when the buffer needs to grow. If this was to allocate precisely what was requested, then we would e.g. allocate just one extra element.

But I guess I could factor the code so it was as you suggested. I will make this a review question. This will require a small change in GrowPolicy so you can see what is requested.

I think the "see what is requested" is the change I suggested above.

Not quite. reserve_precisely() allows you to do extractly that, not matter what GrowPolicy you have installed. The user knows that the new buffer should be exactly what he asks for, no matter what the policy thinks.

OK, but if you remove reserve_precisely(), as I suggested, then you're left with reserve() and it will behave as dictated by the policy. Whenever I use reserve(), I only want that many elements, not at least that many, but I understand that when auto_buffer grows implicitly, it wants to allocate something extra to get amortized constant time for the increase. Thus, in my mind, reserve() does exactly what the caller asks, but auto_buffer itself uses a private member function that calls new_capacity() and moves the data to a new allocation.

...

...

...

The unchecked_*() functions deserve remarks that explain the danger in their use and that the precondition is not checked.

You didn't comment on the addition of remarks for these functions, so I'm re-raising this point.

The precondition is checked with BOOST_ASSERT(). As for remarks, yeah, but how many other functions in Boost have a remark saying that you should not violate the preconditions?

OK, but you can still document the danger.

...

...

...

shrink_to_stack() might be a useful addition. shrink_to_fit() can already place the content on the stack.

OK. I assume that shrink_to_fit() takes an argument, so that shrink_to_stack() would be shorthand for a.shrink_to_fit(a.stack_capacity).

No, shrink_to_fit() never erases elements from the container (logically). resize() does, but this is on my todo list. resize() would probably not move elements to the stack.

Then shrink_to_stack() would be a nice addition for which shrink_to_fit() is not a replacement. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; 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.

Ross Levine skrev:

What would be REALLY nice, is if there was an auto_vector and an auto_set and an auto_map, etc. If anyone has looked into EASTL, they have various fixed_ containers that work this way. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html#Functiona...

I think this is a great idea, personally.

Seems like a lot of work too. I wonder if not the majority of the use cases falls into local objects. In that case, we should be able to use a special stack_based_allocator with existing containers. -Thorsten

Thorsten Ottosen wrote:

Dmitry Vinogradov skrev:

...

Boost.Array offers constant size container with preallocated buffer, Boost.Optional provides from zero to one element. There are no STL container with preallocated buffer and it seems custom allocator does not help to do this with existing containers.

Does any container exist to offer functionality like Boost.Array but allowing to store from 0 to N elements? Is there any interest in such container?

PS. It's similar to fixed_string but as a generic container.

Please see

http://www.cs.aau.dk/~nesotto/boost/auto_buffer.zip

http://www.cs.aau.dk/~nesotto/boost/trunk/libs/auto_buffer/doc/html/

BTW, it would be nice to have an auto_buffer::assign(InputIt First, InputIt Last) member function like std::vector::assign().

OvermindDL1 wrote:

...

Thorsten Ottosen wrote:

...

Dmitry Vinogradov skrev:

...

Boost.Array offers constant size container with preallocated buffer, Boost.Optional provides from zero to one element. There are no STL container with preallocated buffer and it seems custom allocator does not help to do this with existing containers.

Does any container exist to offer functionality like Boost.Array but allowing to store from 0 to N elements? Is there any interest in such container?

PS. It's similar to fixed_string but as a generic container. Please see

http://www.cs.aau.dk/~nesotto/boost/auto_buffer.zip

http://www.cs.aau.dk/~nesotto/boost/trunk/libs/auto_buffer/doc/html/

I am curious. Would it not be possible to implement a class that handles memory allocations of the standard STL style and just pass an instance of that allocator (after allocated on the stack of course) to the stl::vector template parameter, or does std::vector require a class type? I have not read the standard in this area, and from above I guess the C++0x is more clear on this?

Writing custom allocator can help to solve problem, but preformance will fall. Std::vector does not have GrowPolicy template parameter, so there is no way to tell it about pre-allocated buffer size. Every time vector think it needs to grow, it does reallocation by copying data from previous location to a new one. It's not nessesary when a new size() is less than size of buffer. Then if std::vector will grow by twiceing its size from 32 (for example) to 64 to store 50 objects, it will force the allocator to use heap - but imagine that the buffer buffer size is 60, so heap allocating is not required at all!

Dmitry Vinogradov wrote:

Thorsten Ottosen wrote:

...

Dmitry Vinogradov skrev:

...

Boost.Array offers constant size container with preallocated buffer, Boost.Optional provides from zero to one element. There are no STL container with preallocated buffer and it seems custom allocator does not help to do this with existing containers.

Does any container exist to offer functionality like Boost.Array but allowing to store from 0 to N elements? Is there any interest in such container?

PS. It's similar to fixed_string but as a generic container.

Please see

http://www.cs.aau.dk/~nesotto/boost/auto_buffer.zip

http://www.cs.aau.dk/~nesotto/boost/trunk/libs/auto_buffer/doc/html/

BTW, it would be nice to have an auto_buffer::assign(InputIt First, InputIt Last) member function like std::vector::assign().

+ resize()

Thorsten Ottosen wrote:

Dmitry Vinogradov skrev:

...

Boost.Array offers constant size container with preallocated buffer, Boost.Optional provides from zero to one element. There are no STL container with preallocated buffer and it seems custom allocator does not help to do this with existing containers.

Does any container exist to offer functionality like Boost.Array but allowing to store from 0 to N elements? Is there any interest in such container?

PS. It's similar to fixed_string but as a generic container.

Please see

http://www.cs.aau.dk/~nesotto/boost/auto_buffer.zip

http://www.cs.aau.dk/~nesotto/boost/trunk/libs/auto_buffer/doc/html/

By the way, you can use boost::serialization::array to serialize contained data. http://www.boost.org/doc/libs/1_39_0/libs/serialization/doc/wrappers.html#ar... And, is it really needed to serialize capacity? (named "count"?!) I think it's unnecessary thing. Boost.Serialization library does not serialize capacity for standard containers.