[container] New segmented_vector container
Hi, I'd like to share the addition of a new (mostly refactored) sequence container to Boost.Container: segmented_vector. https://www.boost.org/doc/libs/develop/doc/html/doxygen/boost_container_head... What it is --------- segmented_vector is the single-ended counterpart of boost::container::deque, a sequence container that supports random access to elements, constant-time insertion and removal at the end, and linear-time insertion and removal in the middle. It uses the same segmented (block-based) storage as deque but only allows growth at the back: it provides push_back, pop_back, emplace_back, and the like, but does not provide push_front, pop_front, or emplace_front. "seque" was not an appropriate name as this container is not a "queue" (tipically a FIFO queue), but I'm open to renaming the container if a better name is proposed ;-) The initial idea was to add a "single_ended" option to "deque" but that would be too confusing. Implementation notes ------------------- segmented_vector is implemented on top of the same internal machinery as deque (with a single-ended policy optimization), so it shares the same allocation and indexing logic. sizeof(segmented_vector) is 3 words, reduced to 2 words in 64 bit machines if stored_size<uint32_t> option is used. Features ------- - Random-access iterators and the usual sequence interface (size, operator[], at, iterators, etc.). - Amortized O(1) push_back, pop_back, emplace_back; O(n) insert/erase in the middle. - Segmented storage: elements live in fixed-size segments (blocks) instead of one contiguous buffer. New segments are allocated as needed when the container grows, so there is no single large reallocation or bulk move of elements as with std::vector. This can reduce peak memory and improve performance when elements are expensive to move or when growth is large. - Iterator and reference stability: inserting or erasing at the end does *not* invalidate iterators or references/pointers to existing elements. Insertions and erasures in the middle invalidate iterators and references in the same way as for deque. Options ------------------- It supports the same options as deque (stored_size, block-size), I'm experimenting with a "reservable" option that allows "capacity/reserve" support both for segmented_vector and deque. Best, Ion
Ion Gaztañaga wrote:
Hi,
I'd like to share the addition of a new (mostly refactored) sequence container to Boost.Container: segmented_vector.
https://www.boost.org/doc/libs/develop/doc/html/doxygen/boost_container _header_reference/classboost_1_1container_1_1segmented__vector.html
What it is --------- segmented_vector is the single-ended counterpart of boost::container::deque, a sequence container that supports random access to elements, constant-time insertion and removal at the end, and linear-time insertion and removal in the middle. It uses the same segmented (block-based) storage as deque but only allows growth at the back: it provides push_back, pop_back, emplace_back, and the like, but does not provide push_front, pop_front, or emplace_front.
"seque" was not an appropriate name as this container is not a "queue" (tipically a FIFO queue), but I'm open to renaming the container if a better name is proposed ;-)
The initial idea was to add a "single_ended" option to "deque" but that would be too confusing.
Implementation notes ------------------- segmented_vector is implemented on top of the same internal machinery as deque (with a single-ended policy optimization), so it shares the same allocation and indexing logic. sizeof(segmented_vector) is 3 words, reduced to 2 words in 64 bit machines if stored_size<uint32_t> option is used.
Features ------- - Random-access iterators and the usual sequence interface (size, operator[], at, iterators, etc.). - Amortized O(1) push_back, pop_back, emplace_back; O(n) insert/erase in the middle. - Segmented storage: elements live in fixed-size segments (blocks) instead of one contiguous buffer. New segments are allocated as needed when the container grows, so there is no single large reallocation or bulk move of elements as with std::vector. This can reduce peak memory and improve performance when elements are expensive to move or when growth is large. - Iterator and reference stability: inserting or erasing at the end does *not* invalidate iterators or references/pointers to existing elements. Insertions and erasures in the middle invalidate iterators and references in the same way as for deque.
Options -------------------
It supports the same options as deque (stored_size, block-size), I'm experimenting with a "reservable" option that allows "capacity/reserve" support both for segmented_vector and deque.
I read all that three times and I still don't understand what makes this better than just using a deque.
El 04/02/2026 a las 14:42, Peter Dimov via Boost escribió:
I read all that three times and I still don't understand what makes this better than just using a deque.
Probably because it's written to be read 10 times without saying much... In the current implementation: smaller sizeof(), slightly better performance (due to fewer checks, not handling the "front" case), and better memory usage (deque uses a "move-to-middle" strategy when resizing the index). In the future I hope I can improve the difference for back-insertion only cases... Best, Ion
Ion Gaztañaga wrote:
El 04/02/2026 a las 14:42, Peter Dimov via Boost escribió:
I read all that three times and I still don't understand what makes this better than just using a deque.
Probably because it's written to be read 10 times without saying much...
In the current implementation: smaller sizeof(), slightly better performance (due to fewer checks, not handling the "front" case), and better memory usage (deque uses a "move-to-middle" strategy when resizing the index).
Thanks. Speaking of move to middle, on an entirely unrelated note, do we have an implementation of move-to-middle vector-based deque?
El 04/02/2026 a las 18:06, Peter Dimov via Boost escribió:
Ion Gaztañaga wrote:
El 04/02/2026 a las 14:42, Peter Dimov via Boost escribió:
I read all that three times and I still don't understand what makes this better than just using a deque.
Probably because it's written to be read 10 times without saying much...
In the current implementation: smaller sizeof(), slightly better performance (due to fewer checks, not handling the "front" case), and better memory usage (deque uses a "move-to-middle" strategy when resizing the index).
Thanks.
Speaking of move to middle, on an entirely unrelated note, do we have an implementation of move-to-middle vector-based deque?
Yeah: devector https://www.boost.org/doc/libs/latest/doc/html/container/non_standard_contai... Ion
On 4 Feb 2026 16:18, Ion Gaztañaga via Boost wrote:
Hi,
I'd like to share the addition of a new (mostly refactored) sequence container to Boost.Container: segmented_vector.
https://www.boost.org/doc/libs/develop/doc/html/doxygen/ boost_container_header_reference/ classboost_1_1container_1_1segmented__vector.html
What it is --------- segmented_vector is the single-ended counterpart of boost::container::deque, a sequence container that supports random access to elements, constant-time insertion and removal at the end, and linear-time insertion and removal in the middle. It uses the same segmented (block-based) storage as deque but only allows growth at the back: it provides push_back, pop_back, emplace_back, and the like, but does not provide push_front, pop_front, or emplace_front.
"seque" was not an appropriate name as this container is not a "queue" (tipically a FIFO queue), but I'm open to renaming the container if a better name is proposed ;-)
Well, since it is better suited for stacks, "staque" then? :) More seriously though, segmented_vector seems fine.
The initial idea was to add a "single_ended" option to "deque" but that would be too confusing.
Implementation notes ------------------- segmented_vector is implemented on top of the same internal machinery as deque (with a single-ended policy optimization), so it shares the same allocation and indexing logic. sizeof(segmented_vector) is 3 words, reduced to 2 words in 64 bit machines if stored_size<uint32_t> option is used.
And what is sizeof(deque), for comparison?
Features ------- - Random-access iterators and the usual sequence interface (size, operator[], at, iterators, etc.). - Amortized O(1) push_back, pop_back, emplace_back; O(n) insert/erase in the middle. - Segmented storage: elements live in fixed-size segments (blocks) instead of one contiguous buffer. New segments are allocated as needed when the container grows, so there is no single large reallocation or bulk move of elements as with std::vector. This can reduce peak memory and improve performance when elements are expensive to move or when growth is large. - Iterator and reference stability: inserting or erasing at the end does *not* invalidate iterators or references/pointers to existing elements. Insertions and erasures in the middle invalidate iterators and references in the same way as for deque.
Options -------------------
It supports the same options as deque (stored_size, block-size), I'm experimenting with a "reservable" option that allows "capacity/reserve" support both for segmented_vector and deque.
Ability to reserve storage would be appreciated. Also, customizable size of a segment would be very desirable. Preferably, in the number of elements. Deque already supports block_bytes and block_size options, it seems reasonable to expect them supported in segmented_vector as well.
On 4 Feb 2026 19:26, Andrey Semashev wrote:
On 4 Feb 2026 16:18, Ion Gaztañaga via Boost wrote:
Hi,
I'd like to share the addition of a new (mostly refactored) sequence container to Boost.Container: segmented_vector.
https://www.boost.org/doc/libs/develop/doc/html/doxygen/ boost_container_header_reference/ classboost_1_1container_1_1segmented__vector.html
What it is --------- segmented_vector is the single-ended counterpart of boost::container::deque, a sequence container that supports random access to elements, constant-time insertion and removal at the end, and linear-time insertion and removal in the middle. It uses the same segmented (block-based) storage as deque but only allows growth at the back: it provides push_back, pop_back, emplace_back, and the like, but does not provide push_front, pop_front, or emplace_front.
"seque" was not an appropriate name as this container is not a "queue" (tipically a FIFO queue), but I'm open to renaming the container if a better name is proposed ;-)
Well, since it is better suited for stacks, "staque" then? :) More seriously though, segmented_vector seems fine.
The initial idea was to add a "single_ended" option to "deque" but that would be too confusing.
Implementation notes ------------------- segmented_vector is implemented on top of the same internal machinery as deque (with a single-ended policy optimization), so it shares the same allocation and indexing logic. sizeof(segmented_vector) is 3 words, reduced to 2 words in 64 bit machines if stored_size<uint32_t> option is used.
And what is sizeof(deque), for comparison?
Features ------- - Random-access iterators and the usual sequence interface (size, operator[], at, iterators, etc.). - Amortized O(1) push_back, pop_back, emplace_back; O(n) insert/erase in the middle. - Segmented storage: elements live in fixed-size segments (blocks) instead of one contiguous buffer. New segments are allocated as needed when the container grows, so there is no single large reallocation or bulk move of elements as with std::vector. This can reduce peak memory and improve performance when elements are expensive to move or when growth is large. - Iterator and reference stability: inserting or erasing at the end does *not* invalidate iterators or references/pointers to existing elements. Insertions and erasures in the middle invalidate iterators and references in the same way as for deque.
Options -------------------
It supports the same options as deque (stored_size, block-size), I'm experimenting with a "reservable" option that allows "capacity/reserve" support both for segmented_vector and deque.
Ability to reserve storage would be appreciated.
Also, customizable size of a segment would be very desirable. Preferably, in the number of elements. Deque already supports block_bytes and block_size options, it seems reasonable to expect them supported in segmented_vector as well.
Sorry, I somehow missed that you already said that all deque's options are supported.
El 04/02/2026 a las 17:28, Andrey Semashev via Boost escribió:
On 4 Feb 2026 19:26, Andrey Semashev wrote:
And what is sizeof(deque), for comparison?
In the current implementation (since Boost 1.90, previously was 10 words) deque is 4 words (1 pointer + 3 sizes). segmented_vector is 3 words (1 pointer + 2 sizes). If using a "stored_size" option with a 32 bit unsigned in a 64 bit system, then deque would be 3 words and segmented_vector would be 2 words. Best, Ion
Andrey Semashev wrote:
On 4 Feb 2026 16:18, Ion Gaztañaga via Boost wrote:
Hi,
I'd like to share the addition of a new (mostly refactored) sequence container to Boost.Container: segmented_vector.
https://www.boost.org/doc/libs/develop/doc/html/doxygen/ boost_container_header_reference/ classboost_1_1container_1_1segmented__vector.html
What it is --------- segmented_vector is the single-ended counterpart of boost::container::deque, a sequence container that supports random access to elements, constant-time insertion and removal at the end, and linear-time insertion and removal in the middle. It uses the same segmented (block-based) storage as deque but only allows growth at the back: it provides push_back, pop_back, emplace_back, and the like, but does not provide push_front, pop_front, or emplace_front.
"seque" was not an appropriate name as this container is not a "queue" (tipically a FIFO queue), but I'm open to renaming the container if a better name is proposed ;-)
Well, since it is better suited for stacks, "staque" then? :)
I like staque. :-)
More seriously though, segmented_vector seems fine.
It doesn't quite sound fine to me, because it's not a vector. The defining characteristic of vector is that it's contiguous.
No dia 4 de fev. de 2026, às 18:11, Peter Dimov via Boost <boost@lists.boost.org> escreveu:
Andrey Semashev wrote:
On 4 Feb 2026 16:18, Ion Gaztañaga via Boost wrote: Hi,
[…]
"seque" was not an appropriate name as this container is not a "queue" (tipically a FIFO queue), but I'm open to renaming the container if a better name is proposed ;-)
Well, since it is better suited for stacks, "staque" then? :)
I like staque. :-)
Klick-klack https://en.wikipedia.org/wiki/Jacob%27s_ladder_(toy) Joaquín M López Muñoz
El 04/02/2026 a las 18:08, Peter Dimov via Boost escribió:
"seque" was not an appropriate name as this container is not a "queue" (tipically a FIFO queue), but I'm open to renaming the container if a better name is proposed ;-)
Well, since it is better suited for stacks, "staque" then? :)
I like staque. :-)
More seriously though, segmented_vector seems fine.
It doesn't quite sound fine to me, because it's not a vector. The defining characteristic of vector is that it's contiguous.
There are examples out there calling "vector" to things that are not contiguous, like "stationary_vector" (https://github.com/mehrdadn/libvital/blob/master/doc/cpp/vital/container/sta...) or EASTL's segmented_vector (https://github.com/electronicarts/EASTL/blob/master/include/EASTL/segmented_...) Another name that's been proposed for a similar data structure is "segtor". Best, Ion
El 08/02/2026 a las 6:06, Nigel Stewart via Boost escribió:
I like staque. :-)
Seque? ("See queue") Single-ended deque.
The problem is that it's not a queue... A single-ended queue would be a FIFO, like the std::queue adapter. After some thoughts, in order to follow Peter's advice on not calling "xxx_vector" something that it's not contiguous in memory and since I don't like "staque", I've renamed it to "segtor" (contraction for "segmented vector"). At least is short! I haven't found that name used in github, I think the name came from experiments that Matthew Bentley was doing (although if I remember correctly his approach was using geometrically increasing segments, something I hope I can add in the future). Let's see if everyone hates it, so that it will become a memorable name... Best, Ion
On 2/8/26 13:45, Nigel Stewart via Boost wrote:
I like staque. :-) Seque? ("See queue") Single-ended deque. The problem is that it's not a queue...
I think it is a queue. A LIFO (last in, first out) one. But I do think this is a bit "cute". A LIFO data structure is a stack, not a queue.
-- Rainer Deyke - rainerd@eldwood.com
participants (6)
-
Andrey Semashev -
Ion Gaztañaga -
Joaquín M López Muñoz -
Nigel Stewart -
Peter Dimov -
Rainer Deyke