Dear users and members of Boost, I'm happy to to announce that Benedek Thaler's Boost.DoubleEnded is /conditionally/ accepted into Boost provided that it can be integrated smoothly with Boost.Container. There are several other conditions, some major and some minor which I will outline below. For now, I would like to thank everyone that participated with reviews and comments. We didn't have that many reviews, but the reviewers did spend a lot of time both on review and the following discussions. Special thanks also goes to Benedek for his hard work. It is not too often that a GSOC code ends with something of this quality. Two of the world's expert C++ container developers used phrases like "solid" and "everything looks clean and beautiful" about the implementation, "tests look very good, corner cases and all", "The reference section is very good". Congratulations, Benedek. ============== A path forward ============== Ion has most kindly accepted the idea of merging the library into Boost.Container. This consists of A. taking selected elements from batch_deque and adding them to boost::container::deque. B. putting devector into boost.container after changes have been applied to code and documentation C. back-porting the devector code to C++03 (C) does not need to happen immediately, that is, we can have a release where devector is available in a C++11 version. Ion has also most kindly agreed to help with this process. I will help write a new introduction that focuses on the main principles of devector. We also have a number of benchmarks which we can gather and use for a small section of on that topic. I'll leave it to you and Ion to work out the details. ========================== Detailed comments devector ========================== Apart from the merging with Boost.Container, the most heard complaint was about the "fat", the non-essential parts if the interface, that could be removed. This includes -- Remove the direct support for small buffer optimization form devector. When the time comes, provide small_devector similar to the way we have vector/small_vector (there is no requirement that small_devector is provided). -- remove all of the following: - all constructors that uses reserve_only_tag, - all constructors that uses unsafe_uninitialized_tag, - void unsafe_uninitialized_resize_front(size_type); - void unsafe_uninitialized_resize_back(size_type); - unsafe_push_front(...); - unsafe_push_back(...); -- add instead - constructors that uses default_init_t like boost.container - resize versions that uses default_init_t - T& unchecked_emplace_back(...) noexcept(...) - T& unchecked_emplace_front(...) noexcept(...) At some point, I hope we can upgrade default_init_t to mean no construction for all trivially copyable types. There was a wish for more symmetry in devector and so functions that break symmetry or can appear ambiguous should be removed. This means we should remove: -- capacity() There is no need for front_capacity() and back_capacity(). We could remove reserve(), but then we can't use devector with a flat_set. Reserve() should not be an alias for reserve_back() though, but controlled by the policy. We could remove resize(), but even deque has it where it means resize_back(). I totally agree it would be ideal to remove all of reserve(),resize(),capacity(),clear(), but I see no easy way we can use devector with flat containers if we remove the first and the last. Unless we start deprecating stuff in boost::deque/boost::vector and provide new consistent alternatives, we will never get a 100% satisfactory solution. At the end of the day, we need to be pragmatic, so if deprecation is not on the table, this seems the best we can do. Since we don't want two allocations implied by calling reserve_back() and reserve_front(), you can add a mechanism for doing that. That is, you can provide -- reserve( new_capacity ); -- reserve_front( new_front_capacity ) -- reserve_back( new_back_capacity ) -- reserve( new_front_capacity, new_back_capacity ) or, since reserve() is such a weird beast, simply provide -- reserve( new_capacity ); // for flat containers -- anticipate_front( new_front_elements ) -- anticipate_back( new_back_elements ) -- anticipate( new_front_elements, new_back_elements ) to get rid of the funky -- container.reserve_front( container.size() + new_front_elements ) dance. There were suggestions for shrink_back/front_to_fit, but since we are trying to remove fat, I suggest that we wait for a use-case. There were also suggestions that clear() should be amended. As the growth (or resizing policy) mandates what clear does, we need a way to escape. The minimal change that allows that is to provide -- clear( front_free_capacity ) which gives full power to the user. You may provide clear_back() as clear(0) and clear_front() as clear(c.size()+c.front_free_capacity()+c.back_free_capacity()). Ideally, clear() would have been removed entirely like capacity()/resize(), but like reserve(), it just seems like impossible when we start using it with flat containers. Other minor comments: - drop strong exception safety guarantees and do it like boost.container - prefer to make iterator a type (should be easy with reuse from boost::container::vector - allocator should not be inherted from - make clear O(1) amortized gurantees depend on growth policy - consider calling growth policy for resizing policy - make sure SFINAE works properly with constructors - make the default growth factor 2 (as we heard from Sean Parent: no factor below 2 is empirically good) - consider renaming front_free_capacity to free_front_capacity. Rationale: "front_capacity" is a concept, noun, and "free" is the adjective. Ditto for back_free_capacity. - remove size_type from growth policy and take it from the allocator - make the allocator template argument the 2nd argument - fix remaning TODO in code - documentation should not sell devector as drop-in replacement for vector, but rather stress it is not - the allocator supports needs to be improved. I guess doing it the Boost.Container way ensures that (ask Daniel James for help) - exception-safety issues pointed out by Ion - postconditions of insert/erase needs to specify behavior to front_free_capacity/back_free_capcity - use of local containers should be avoided - rotate should be avoided - delegate range move operations to those defined in Boost.Container - make sure all functions excepting non-overlapping range uses memcpy (not just memmove). This includes: - range constructor - copy-constructor - copy-assignment - range-assignment - range insert - destructor should used std::has_trivial_destructor to avoid loop in that case to make sure all compilers optimize it away (similar for erase). There is one final puzzle and that is the growth policy. I hope we can finalize that by testing Joaquin's and Ion's suggestions over the coming weeks. ============================= Detailed comments batch_deque ============================= For deque, the comments were similar, although there was far less to discuss than for devector. All agreed that one should be able to control the segment size. - stable_insert was not needed. - segment iteration was good, but should be usable with range-based for loop. The segment iterator should return a segment type if possible, and the segment should have begin(),end(),size() members. - since boost::deque already has a resize with default_init_t, that should be sufficient to provide fast serialization load for trivial types. No need for - resize_front - resize_back - unsafe_uninitialized_resize_front - unsafe_uninitialized_resize_back - reserve - shrink_to_fit() - capacity() The following are still needed for optimal code (or code that can be known not to reallocate, or for better locality in deserialization, avoiding double initialization) - free_front_capacity; - free_back_capacity; - reserve_front - reserve_back - unchecked_emplace_front - unchecked_emplace_back Boost.Container's unit-tests should be extended with those from batch_deque where it makes sense. Since segmented iteration was somewhat faster, it should be use internally where it makes sense. In particular - copy-constructor - copy-assignment - destructor As for devector, all constructor/functions that iterate over non-overlapping ranges should use memcpy. destructor should use is_trivially_destructible to ensure it is optimized away (similar for erase). ====================== Serialization comments ====================== I suggest that the default versions just do what Boost.Serialization does, perhaps just replacing resize with resize with default_init_t. That ensures it works correctly for all archive types. It also needs to use make_nvp() so the output is identical to std::vector. We will then talk to Robert about how we can take advantage of the binary archive in a correct fashion. ====================== kind regards Thorsten, review manager