
Hi, I've been working lately on a new deque implementation for Boost.Container. The original uses the classic SGI STL-based data structure, that is quite bulky. The new implementation is already on develop and ready to be merged to master for Boost 1.90 The new implementation will try to be faster than std implementations (I probably need to work more on that with benchmarks), but more importantly, can allow some additional features. Some changes: - sizeof(deque) was 10 words, now is 4 words. Probably the lightest implementation around. - sizeof(deque::iterator) was 4 words, now is is 2 words (similar to libc++ and MSVC).) - Several internal algorithms were reimplemented to take advantage of the segmented nature of deque. - Defaults were slightly changed, 64 bit platforms now use 1024 byte blocks by default instead of the SGI classic 512 byte blocks (still far from libc++'s 4K blocks). - The new implementation eases further deque-like variations and optimizations in the future. Some planned features - Add a "stored_size_type" option so that the sizeof deque can be further decreased (probably down to 3 words) for those in 64 bit platforms that don't need more than 4G elements in deque. - Add a single-ended variation ("seque" might be confusing name because the data structure would not longer be a queue, but a segment-based sequence with random-access). Some people use deque to have a random-access container that avoids vector-like reallocations and guarantees stable pointers and references when inserting on the back. A double-ended container is sometimes sub-optimal for those use cases. - Add options (or maybe different containers or aliases reusing parts of the implementation) that can offer "reserve/capacity"-like features, so that a programmer can pre-allocate all the blocks that's going to use avoiding allocation performance penalties on hot code. I'll update the "Draft Development Plan for Boost.Container" (https://docs.google.com/document/d/1VdMTheFUczC946dP3VKPseOoUq3sVKjU73oMvK8F...) with these proposals. Of course, I'm open to new proposals/features. If any booster is eager to test the new deque implementation or wants to suggest a benchmark/use-case that could be useful for Boost.Container users, please let me know! If anyone detects a bug in the new implementation please notify it and I'll try to solve it ASAP. Best, Ion