On 16/10/2017 19:18, Thorsten Ottosen via Boost wrote:
1) devector is initialized with equal free capacity for both ends.
I assume that implies reserve() does the very same?
Yes.
2) If a xxx (xxx = left or right) insertion is needed and xxx_free_capacity >= the number of items to be inserted, a xxx insertion is done (minimizes moves). 3) Otherwise if a xxx (xxx = left or right) insertion is needed and xxx_free_capacity < N, the sequence containing new plus old elements should be placed in the middle of the buffer. (Note: This step should be limited if amortized constant time is desired for push_xxx insertions)
There might be some corner cases here. Suppose we have front_free_capacity() == 3, back_free_capacity() == 0 and is about to insert to the right half. Does it then make sense to place elements in the middle?
We are optimizing the general case, we don't know where the user is going to insert the next element. Putting data in the middle seems the choice that minimizes worst-case scenarios. What if the next insertion is in the left half (say, via flat_map)? In any case if we want some kind of cache, we could just move new elements to the side where free elements were available in the old buffer with some kind of logic, like moving data more to left if right free capacity was exhausted.
I think the RF factor obtains an amortized constant time for one side insertion if that property is considered useful.
I think that is a must.
Ok. That's what's used in the alternative implementation in: http://larshagencpp.github.io/blog/2016/05/22/devector using a reallocation factor of 0.8. push_back benchmarks seem quite inline with vector and deque. But it uses some statistics based approach to relocate the buffer so that the push_back case is optimized instead of a random insertion scenario.
For a FIFO, I think a deque that reuses free segment capacity on one side and transfers it to the other side before allocating new memory would be the best choice. Currently boost::container::deque does not do this, but pull requests are welcome ;-)
Or maybe just boost::circular_buffer (is this not the optimal way to handle that case?). No one is saying that devector has to solve every problem.
You are right, circular_buffer should be container to use.
I do want to focus on simple properties from a user's perspective. Some cases to consider:
# case 1: push_back from empty state # case 2: push_back from unknown state # case 3: insert from empty state # case 4: insert from unknown state
How do these properties work for a devector? If I understand your strategy, we get the following:
I think all of them work.
# case 1: push_back from empty state ------------------------------------
devector<int> v; v.reserve( N );
This does not guarantee N pushes without exceptions or without reallocation. To get that guarantee we have to write
If I'm not mistaken, you get the same guarantee. The difference is that elements are "relocated" (moved), but there is no "reallocation" (new buffer allocation). They are first moved when N/2 elements are push_backed and left/right_free_capacity() is zero, then after push_backing additional N/2 elements, etc (the number of relocations (moves) steps depend on the "relocation factor"). Since push_back requires nothrow move constructible to avoid exceptions, moving elements is not a problem, because all of them will be noexcept. If I understand it correctly, it's more or less the same strategy used in: http://larshagencpp.github.io/blog/2016/05/22/devector Best, Ion