views:

271

answers:

3

It says here that

The unbounded array is similar to a std::vector in that in can grow in size beyond any fixed bound. However unbounded_array is aimed at optimal performance. Therefore unbounded_array does not model a Sequence like std::vector does.

What does this mean?

A: 

As I understood it from the linked documentation, it is all about allocation strategy. std::vector afaik postpones allocation until necessary and than might allocate some reasonable chunk of meory, unbounded_array seams to allocate more memory early and therefore it might allocate less often. But this is only a gues from the statement in documentation, that it allocates more memory than might be needed and that the allocation is more expensive.

Gabriel Ščerbák
std::vector's allocation strategy is not defined with the exception of the `std::vector<t>::reserve` member. Implementations are free to initialize blocks of unused memory as they see fit.
Billy ONeal
@Billy ONeal than there is no place to compare them and to claim that unbounded_array is optimal... imho boost guys are comparing it to some implementation
Gabriel Ščerbák
@Gabriel Ščerbák: That one statement makes a -1 answer into a +1 answer. Change your answer to include that and I'll change my vote.
Billy ONeal
@Billy ONeal I am not so much into the upvote to claim Boost developers might not be right:)
Gabriel Ščerbák
@Gabriel Ščerbák: You sure had a correct answer for someone who didn't want to claim Boost developers were wrong :)
Billy ONeal
@Billy ONeal I am glad you pointed out that in the end I was sort of right, it is nice to recall what was I using four years ago:)
Gabriel Ščerbák
+10  A: 

It appears to lack insert and erase methods. As these may be "slow," ie their performance depends on size() in the vector implementation, they were omitted to prevent the programmer from shooting himself in the foot.

insert and erase are required by the standard for a container to be called a Sequence, so unlike vector, unbounded_array is not a sequence.

No efficiency is gained by failing to be a sequence, per se.

However, it is more efficient in its memory allocation scheme, by avoiding a concept of vector::capacity and always having the allocated block exactly the size of the content. This makes the unbounded_array object smaller and makes the block on the heap exactly as big as it needs to be.

Potatoswatter
Kinds seems like there must be something else for them to make this claim though.
Michael Dorgan
+1, very reasonable answer.
Maulrus
Would not say so:When resized unbounded_array will reallocate it's storage even if the new size requirement is smaller.
Gabriel Ščerbák
@Gabriel: I think it's tailored to algorithms that don't do much shrinking. (Or growing, for that matter.)
Potatoswatter
@Michael: If you include memory consumption in your analysis of a container's performance, the claim is perfectly justified. Over the containers recommended operations, the runtime performance is the same as a vector's, but the memory consumption is up to 50% less. Its an extremely poorly written description, though. They make no attempt to justify the container's existence at all.
Dennis Zickefoose
@Potatoswatter but than this would be obsolete "...and always having the allocated block exactly the size of the content.", right?
Gabriel Ščerbák
Looking over the documentation some more, I take back that statement. The initialization could be notably less efficient than a vector.
Dennis Zickefoose
@Dennis: the lack of an iterator range constructor is particularly odd, but this is part of Boost Linear Algebra, so I suppose it's not intended for use with constructors at all.
Potatoswatter
+1 for pointing out the differences in capacity and potential memory block size differences with a vector storing the same number of elements. unbounded_array is really more of an implementation detail, however, it should not be considered for general purpose usage (at least not without some modifications).
+12  A: 

As a Boost developer myself, I can tell you that it's perfectly fine to question the statements in the documentation ;-)

From reading those docs, and from reading the source code (see storage.hpp) I can say that it's somewhat correct given some assumptions about the implementation of std::vector at the time that code was written. That code dates to 2000 initially, and perhaps as late as 2002. Which means at the time many STD implementations did not do a good job of optimizing destruction and construction of objects in containers. The claim about the non-resizing is easily refuted by using an initially large capacity vector. The claim about speed, I think, comes entirely from the fact that the unbounded_array has special code for eliding dtors & ctors when the stored objects have trivial implementations of them. Hence it can avoid calling them when it has to rearrange things, or when it's copying elements. Compared to really recent STD implementations it's not going to be faster, as new STD implementation tend to take advantage of things like move semantics to do even more optimizations.

GrafikRobot
Are there any prospects for updating boost.ublas? It would be nice to have matrix implementations you can call `reserve()` on and other things that `unbounded_array` lacks. Sometimes ublas feels like the forgotten step-child of boost.
Inverse
I think you can instantiate the matrix template types so that they are built on top of vector instead of unbounded_array.
Neil G