Den 05-10-2017 kl. 22:42 skrev Ion Gaztañaga via Boost:
On 05/10/2017 19:02, Thorsten Ottosen via Boost wrote:
I understand the idea to avoid zero initialization for buffers, but what's the use case for types with non-trivial constructors? The documentation shows a socket example, and that's covered ith default_init_t.
Well, I don't know if my compiler is wrong, but vc 2017 says:
class IntClass { int i; public: IntClass() : i(0) {} IntClass( int i ) : i( i ) {} };
is trivially copyable (hence we can copy arrays of it as fast as arrays of ints). But it will be initialized with zero if I use default_init_t, right?
Right.
But I agree we don't need two overloads, the existing one just has to work in terms of trivially copyable. We can also put a static assertion in there to lock it down to such types for now.
If reserve is not an alias for reserve_back, the I think we must remove it.
reserve() means that a container won't reallocate if size() < capacity(). Where memory is reserved is irrelevant for the user.
I was thinking along generic code along the line
template< class BacKInsertionContiguousContainer > void foo( BacKInsertionContiguousContainer& cont ) { cont.reserve( source.size() ); for( ... ) cont.push_back( ... );
}
why should that not work with both devector and vector?
It would work, but it would not be as efficient as vector.
It may be. But I guess my concern was to make it compile. Sure, if a call to reserve is conditioned on d.capacity() - d.size(), it can behave differently. Reserve maybe easier to do something about. We may need to tweak the definition of reserve_back/reserve_front a little. Let's say we have x x 1 1 x so front_free_capacity is 2, back free capacity is 1 ans size is 2. with d.reserve( d.size() + 3 ); devector uses the expression n = new_capacity - size() so we get n = 5 - 2 = 3 and we get x x 1 1 x x x . A vector 1 1 x does the same. So is your concern that users use capacity to determine what/if to reserve?
This is tricky. I think the best is to treat both ends independently. If you start moving things around, you can break the O(1) amortized guarantee by interleaving push_front/push_back.
What do you mean by "treat both ends independtly"?
I mean that buffer extensions at either end should never affect each other. That is, a push_back can never remove free capacity from the front, a push_front can never remove free capacity from the back.
Ok. I still have no clear idea which allocation strategy would be the "natural" one. I've found this blog with a similar discussion and alternatives:
http://larshagencpp.github.io/blog/2016/05/22/devector
also linked from the blog post:
Certainly a good analysis.
Moving elements just one step when one side is full and the other side has capacity has bad quadratic behavior while current capacity is being exhausted and we continue inserting in the same side. Moving elements to the middle of the buffer seems a simple operation that reduces this to something closer to O(NlogN). In any case, I will always bad insertion sequence that hurts our strategy, so optimizing the common case seems the way to go.
I'm ok with inserts in the middle to move stuff around since it already has O(n) worst case behavior. For push_back/push_front I don't know. It would have to be really simple to be worth the effort IMO. Say, only when other_size_free_capacity >= size(). The simple thing would be to grow independently, and then the user calls shrink to fit when done if he cares about it. BTW: Before the review some people complained that the container could not work as deque when you repeatedly pop from one end and push another. Something to ponder ... kind regards Thorsten