On 04/10/2017 11:45, Thorsten Ottosen via Boost wrote:
It's like just having small_vector without having vector, most libraries have two classes for these two use cases. Different classes also ease that a type erasured base class can be defined independent from the static storage size (Boost.Container calls it small_vector_base, LLVM calls it SmallVectorBase) I think we should have a devector, and add small_devector and static_devector containers if there is demand.
Can they share some of the implementation, or are we left with a double (or triple) implementation effort?
They can obviously share implementation. That's the case with vector/small_vector/static_vector.
2) Defaulting size_type to unsigned int is arbitrary and against existing practice.
We didn't do that as an arbitrary decision.
Yes, sorry, "arbitrary" sounds too strong.
According to the usual STL rules, size_type shall come from the allocator, which knows what type can represent the number of elements that can be allocated.
I have no problems with STL rules, but it as you point out, even Boost.Container deviates from several of those.
Yes, but only when they are "clearly bad rules (TM)" ;-)
3) reserve_only_tag: I would rename it as “reserve_only_t” (similarly to std::allocator_arg_t and Boost.Container’s “default_init_t”). The front and back capacity version should be enough as I think devector should not show preference for back insertion (if a user wants only a back capacity, then it would use a vector and not a devector).
So you would prefer it to divide the buffer in two approximately equal chucks? Or that one has to specify each chunk size explicitly each time (so full symmetry, and the one-sided constructor gone)?
Good questions. Maybe the first, but that would apply also to "reserve".
4) unsafe_uninitialized_tag: I don’t like these non-safe constructors, which are the cases?. With reserve-only constructors + unsafe emplace back a user can achieve nearly the same performance. For POD types (like the socket example mentioned in the documentation), I would suggest something like Boost.Container’s “default_init_t”. Instead of “unsafe_uninitialized_resize_front” I suggest resize_front(size_type, default_init_t)
I didn't know about these default_init_t when we started in 2015. They have a good design IMO. But unfortunately they don't get rid of double initialization for non-trivial types. So maybe both
resize_front( size_type, default_init_t ) resize_front( size_type, uninitialized_t )
would be an idea.
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.
5) reserve() / resize(): I think they have no sensible meaning in the container (capacity() could be useful, depending on the reallocation strategy). We should not treat back insertion as the “default” insertion. IMHO the API of devector should be symmetrical.
Symmetry is good, but what about generic code?
Generic code can't rely on reserve, only vector implements it in the STL. But if reserve() and resize() are unbiased to back insertion maybe they could make sense. reserve() allocates a new buffer if capacity() is not enough and moves existing elements to the middle. Resize could do the same and fill with elements on both ends. I somewhat have the idea that in a devector both front and back insertions should be common, so a back-biased approach should be avoided. Not sure if real usage follows this pattern.
8) Regarding "move_if_noexcept", Boost.Container does not use it as it consider a pessimized design for a situation (throwing moves) that will occur nearly never [snip] devector itself would be copied if small_buffer_size is used, etc.).
only when it stores elements with a non-noexcept move though.
Right.
9) Minor comment 2: IMHO I think iterators would be better as classes instead of pointers, a user can always use data() to make sure pointers are returned. Many times unwanted overload resolutions can happen if pointers are used, so I prefer the type safety offered by a class-based iterator. It can also offer checked iterators in the future.
I think you have a way to turn these into pointers again in Boost.Container, By defining some preprocessor symbol, right? Having pointers matters when interfacing with other types, because this is the only case where the iterators are seen as contiguous.
I would much rather see that in debug mode the iterator type is a class and in release mode it is a pointer compared to having extra preprocessor symbols.
That could have surprising compilation errors when switching modes. For debug iterators, I find interesting the libc++ approach (but I don't know how it performs) to maintain binary compatibility between checked and non-checked iterators using a global database store containers and iterators.
3) stable_insert: I can’t see the usefulness of this operation. A batch_deque is a sequence, but the user cares about the insertion point but does not care if additional elements are created somewhere? I fail to see a real use case.
A deque is a sequence, sure, but also a container with reference stability. I'm curious, when you use Boost.Intrusive, where do store the elements?
vector if object count or maximum object count is known and all elements are going to be destroyed at the same time. Deque if the number of elements are not known (but they are destroyed at the same time). If elements are destroyed in any order, then you need a pool, a list or some kind of free list backed with a deque or similar. stable_insert can maintain stability with a middle insertion but there is no equivalent operation for erasures. I just can't imagine a use case that tan take advantage of stable_insert (it needs more or less a positional insertion, but not absolute, instead of front/back insertion) but it will surely exist. Additional note: stable_insert also constructs a temporary batch_deque which is not passed the stored allocator so that objects are created in the same memory type of already stored objects. The temporary container should be avoided, maybe new segments could be back/front allocated and initialized then then just reinserted in their final positions in the map.
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"? Best, Ion