Boost C++ Libraries

This useful, fully STL-compliant stable container designed by Joaquín M. López Muñoz is an hybrid between vector and list, providing most of the features of vector except element contiguity.

Extremely convenient as they are, vectors have a limitation that many novice C++ programmers frequently stumble upon: iterators and references to an element of an vector are invalidated when a preceding element is erased or when the vector expands and needs to migrate its internal storage to a wider memory region (i.e. when the required size exceeds the vector's capacity). We say then that vectors are unstable: by contrast, stable containers are those for which references and iterators to a given element remain valid as long as the element is not erased: examples of stable containers within the C++ standard library are list and the standard associative containers (set, map, etc.).

Sometimes stability is too precious a feature to live without, but one particular property of vectors, element contiguity, makes it impossible to add stability to this container. So, provided we sacrifice element contiguity, how much can a stable design approach the behavior of vector (random access iterators, amortized constant time end insertion/deletion, minimal memory overhead, etc.)? The following image describes the layout of a possible data structure upon which to base the design of a stable vector:

Each element is stored in its own separate node. All the nodes are referenced from a contiguous array of pointers, but also every node contains an "up" pointer referring back to the associated array cell. This up pointer is the key element to implementing stability and random accessibility:

Iterators point to the nodes rather than to the pointer array. This ensures stability, as it is only the pointer array that needs to be shifted or relocated upon insertion or deletion. Random access operations can be implemented by using the pointer array as a convenient intermediate zone. For instance, if the iterator it holds a node pointer it.p and we want to advance it by n positions, we simply do:

it.p = *(it.p->up+n);

That is, we go "up" to the pointer array, add n there and then go "down" to the resulting node.

General properties. stable_vector satisfies all the requirements of a container, a reversible container and a sequence and provides all the optional operations present in vector. Like vector, iterators are random access. stable_vector does not provide element contiguity; in exchange for this absence, the container is stable, i.e. references and iterators to an element of a stable_vector remain valid as long as the element is not erased, and an iterator that has been assigned the return value of end() always remain valid until the destruction of the associated stable_vector.

Operation complexity. The big-O complexities of stable_vector operations match exactly those of vector. In general, insertion/deletion is constant time at the end of the sequence and linear elsewhere. Unlike vector, stable_vector does not internally perform any value_type destruction, copy/move construction/assignment operations other than those exactly corresponding to the insertion of new elements or deletion of stored elements, which can sometimes compensate in terms of performance for the extra burden of doing more pointer manipulation and an additional allocation per element.

Exception safety. (according to Abrahams' terminology) As stable_vector does not internally copy/move elements around, some operations provide stronger exception safety guarantees than in vector:

Memory overhead. The C++ standard does not specify requirements on memory consumption, but virtually any implementation of vector has the same behavior with respect to memory usage: the memory allocated by a vector v with n elements of type T is

m_v = c∙e,

where c is v.capacity() and e is sizeof(T). c can be as low as n if the user has explicitly reserved the exact capacity required; otherwise, the average value c for a growing vector oscillates between 1.25∙n and 1.5∙n for typical resizing policies. For stable_vector, the memory usage is

m_sv = (c + 1)p + (n + 1)(e + p),

where p is the size of a pointer. We have c + 1 and n + 1 rather than c and n because a dummy node is needed at the end of the sequence. If we call f the capacity to size ratio c/n and assume that n is large enough, we have that

m_sv/m_v ≃ (fp + e + p)/fe.

So, stable_vector uses less memory than vector only when e > p and the capacity to size ratio exceeds a given threshold:

m_sv < m_v <-> f > (e + p)/(e - p). (provided e > p)

This threshold approaches typical values of f below 1.5 when e > 5p; in a 32-bit architecture, when e > 20 bytes.

Summary. stable_vector is a drop-in replacement for vector providing stability of references and iterators, in exchange for missing element contiguity and also some performance and memory overhead. When the element objects are expensive to move around, the performance overhead can turn into a net performance gain for stable_vector if many middle insertions or deletions are performed or if resizing is very frequent. Similarly, if the elements are large there are situations when the memory used by stable_vector can actually be less than required by vector.

Note: Text and explanations taken from Joaquín's blog

Using sorted vectors instead of tree-based associative containers is a well-known technique in C++ world. Matt Austern's classic article Why You Shouldn't Use set, and What You Should Use Instead (C++ Report 12:4, April 2000) was enlightening:

“Red-black trees aren't the only way to organize data that permits lookup in logarithmic time. One of the basic algorithms of computer science is binary search, which works by successively dividing a range in half. Binary search is log N and it doesn't require any fancy data structures, just a sorted collection of elements. (...) You can use whatever data structure is convenient, so long as it provides STL iterator; usually it's easiest to use a C array, or a vector.”

“Both std::lower_bound and set::find take time proportional to log N, but the constants of proportionality are very different. Using g++ (...) it takes X seconds to perform a million lookups in a sorted vector<double> of a million elements, and almost twice as long (...) using a set. Moreover, the set uses almost three times as much memory (48 million bytes) as the vector (16.8 million).”

“Using a sorted vector instead of a set gives you faster lookup and much faster iteration, but at the cost of slower insertion. Insertion into a set, using set::insert, is proportional to log N, but insertion into a sorted vector, (...) , is proportional to N. Whenever you insert something into a vector, vector::insert has to make room by shifting all of the elements that follow it. On average, if you're equally likely to insert a new element anywhere, you'll be shifting N/2 elements.”

“It may sometimes be convenient to bundle all of this together into a small container adaptor. This class does not satisfy the requirements of a Standard Associative Container, since the complexity of insert is O(N) rather than O(log N), but otherwise it is almost a drop-in replacement for set.”

Following Matt Austern's indications, Andrei Alexandrescu's Modern C++ Design showed AssocVector, a std::map drop-in replacement designed in his Loki library:

“It seems as if we're better off with a sorted vector. The disadvantages of a sorted vector are linear-time insertions and linear-time deletions (...). In exchange, a vector offers about twice the lookup speed and a much smaller working set (...). Loki saves the trouble of maintaining a sorted vector by hand by defining an AssocVector class template. AssocVector is a drop-in replacement for std::map (it supports the same set of member functions), implemented on top of std::vector. AssocVector differs from a map in the behavior of its erase functions (AssocVector::erase invalidates all iterators into the object) and in the complexity guarantees of insert and erase (linear as opposed to constant). ”

Boost.Container flat_map, flat_set, flat_multimap and flat_multiset containers are ordered, vector-like container based, associative containers following Austern's and Alexandrescu's guidelines. These ordered vector-like containers have also benefited with the addition of move semantics, speeding up insertion and erasure times considerably. Flat associative containers have the following attributes:

Differences with the standard std::flat_map/std::flat_set. C++23 added std::flat_map, std::flat_set, std::flat_multimap and std::flat_multiset, based on the same sorted-vector idea. There are, however, several notable differences with Boost.Container's long-standing implementation (available since 2004 and usable from C++03 onwards):

The following example shows the most common operations, the single-sequence storage and the extract_sequence/adopt_sequence idiom:

#include <boost/container/flat_map.hpp>
#include <boost/move/utility_core.hpp>   //boost::move

//Make sure assertions are active
#ifdef NDEBUG
#undef NDEBUG
#endif
#include <cassert>

int main ()
{
   using namespace boost::container;

   typedef flat_map<int, int> map_t;

   map_t m;

   //Like vector, we can reserve storage to avoid reallocations while filling.
   m.reserve(8);

   //Insertions keep the underlying vector sorted by key. They are O(N)
   //because the elements after the insertion point must be shifted.
   m[30] = 3;
   m[10] = 1;
   m[20] = 2;
   assert(m.size() == 3);

   //Iteration is in key order and over contiguous memory, using random-access
   //iterators, so it is much faster than a node-based std::map.
   {
      map_t::const_iterator it = m.begin();
      assert(it->first == 10 && it->second == 1); ++it;
      assert(it->first == 20 && it->second == 2); ++it;
      assert(it->first == 30 && it->second == 3);
   }

   //Lookup uses binary search: O(log N).
   map_t::iterator f = m.find(20);
   assert(f != m.end() && f->second == 2);

   //All values live in a single underlying sequence of value_type, which is
   //std::pair<Key, T> (an array of structs). This is a key difference with the
   //C++23 std::flat_map, a container *adaptor* that keeps keys and mapped
   //values in two separate, parallel containers (a structure of arrays).
   const map_t::value_type *raw = &*m.begin();
   assert(raw[0].first == 10 && raw[2].first == 30);

   //The underlying sorted vector can be moved out with extract_sequence() and
   //moved back in with adopt_sequence(). Because the extracted sequence is
   //already ordered and free of duplicates, we can re-adopt it in O(1) using
   //the ordered_unique_range_t overload.
   map_t::sequence_type seq = m.extract_sequence();
   assert(m.empty());
   m.adopt_sequence(ordered_unique_range_t(), boost::move(seq));
   assert(m.size() == 3 && m.find(30) != m.end());

   return 0;
}

devector ("double-ended vector") is a hybrid of the standard vector and deque containers, originally written by Benedek Thaler. It offers cheap (amortized constant time) insertion at both the front and back ends, while also providing the regular features of vector, in particular contiguous underlying storage and random access to elements.

What is it for? devector is the natural choice whenever a program needs a growable sequence that is frequently modified at both ends but still requires the elements to live in a single contiguous block of memory. Double-ended queues (work queues, sliding windows, ring-buffer-like patterns) and parsers or builders that both prepend and append data are typical examples where a plain vector would force expensive shifts at the front and a deque would give up contiguity.

Relationship with other containers. Like vector, devector keeps all its elements in a single contiguous buffer, so it offers random access, data()-based interoperability with C APIs and cache-friendly traversal; in fact, devector's available methods are a superset of those of vector with similar behaviour, barring a couple of iterator invalidation guarantees that differ. Unlike vector, it can reserve free capacity before the first element as well as after the last one, which makes front insertion as cheap as back insertion instead of a linear-time operation. Like deque, it provides amortized constant-time growth at both ends, but unlike deque it does not use a segmented layout: the price for contiguity is that growing past the reserved capacity relocates elements, so iterators and references are invalidated more often than in a deque. In short, devector sits between vector and deque, trading some of deque's iterator-stability guarantees for vector-like contiguous storage with efficient two-ended growth.

The static size overhead for boost's devector is one extra size_t per container: Usually sizeof(devector) == 4*sizeof(T*).

There are different strategies when elements are to be inserted at one extreme of the container and there is no room for additional elements at that extreme. One simple strategy would be to reallocate a bigger buffer and move all elements to the new memory. However, this would lead to unbounded memory waste when elements are inserted predominantly on one extreme (e.g. pushed at one extreme and popped from the other, like a LIFO pattern).

To avoid unbounded memory waste, Boost.Container's devector uses a different strategy:

However, this strategy has also some downsides:

The following example illustrates the most common operations: efficient insertion and removal at both ends, random access over contiguous storage and the per-end reserve_front/reserve_back capacity hints:

#include <boost/container/devector.hpp>

#include <cstddef>

//Make sure assertions are active
#ifdef NDEBUG
#undef NDEBUG
#endif
#include <cassert>

int main ()
{
   using namespace boost::container;

   devector<int> dv;

   //Unlike vector, a devector can grow cheaply (amortized constant time)
   //at *both* ends, while keeping all elements in contiguous memory.
   dv.push_back(2);              // {2}
   dv.push_back(3);              // {2, 3}
   dv.push_front(1);            // {1, 2, 3}
   dv.push_front(0);            // {0, 1, 2, 3}

   assert(dv.size() == 4);
   assert(dv.front() == 0);
   assert(dv.back()  == 3);

   //Random access and contiguous storage, just like vector.
   assert(dv[0] == 0 && dv[3] == 3);
   const int *p = dv.data();
   for(std::size_t i = 0, n = dv.size(); i != n; ++i)
      assert(p[i] == (int)i);

   //We can ask for free capacity at each end independently, so that the
   //following insertions at that end do not trigger a reallocation.
   dv.reserve_front(dv.size() + 4);
   dv.reserve_back(dv.size() + 4);

   //emplace variants construct the element in place at either end.
   dv.emplace_front(-1);        // {-1, 0, 1, 2, 3}
   dv.emplace_back(4);          // {-1, 0, 1, 2, 3, 4}
   assert(dv.front() == -1);
   assert(dv.back()  == 4);

   //Removal at both ends is constant time and never reallocates.
   dv.pop_front();              // {0, 1, 2, 3, 4}
   dv.pop_back();               // {0, 1, 2, 3}
   assert(dv.size() == 4);
   assert(dv.front() == 0);
   assert(dv.back()  == 3);

   return 0;
}

When the standard template library was designed, it contained a singly linked list called slist. Unfortunately, this container was not standardized and remained as an extension for many standard library implementations until C++11 introduced forward_list, which is a bit different from the the original SGI slist. According to SGI STL documentation:

“An slist is a singly linked list: a list where each element is linked to the next element, but not to the previous element. That is, it is a Sequence that supports forward but not backward traversal, and (amortized) constant time insertion and removal of elements. Slists, like lists, have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed. The ordering of iterators may be changed (that is, slist<T>::iterator might have a different predecessor or successor after a list operation than it did before), but the iterators themselves will not be invalidated or made to point to different elements unless that invalidation or mutation is explicit.”

“The main difference between slist and list is that list's iterators are bidirectional iterators, while slist's iterators are forward iterators. This means that slist is less versatile than list; frequently, however, bidirectional iterators are unnecessary. You should usually use slist unless you actually need the extra functionality of list, because singly linked lists are smaller and faster than double linked lists.”

“Important performance note: like every other Sequence, slist defines the member functions insert and erase. Using these member functions carelessly, however, can result in disastrously slow programs. The problem is that insert's first argument is an iterator pos, and that it inserts the new element(s) before pos. This means that insert must find the iterator just before pos; this is a constant-time operation for list, since list has bidirectional iterators, but for slist it must find that iterator by traversing the list from the beginning up to pos. In other words: insert and erase are slow operations anywhere but near the beginning of the slist.”

“Slist provides the member functions insert_after and erase_after, which are constant time operations: you should always use insert_after and erase_after whenever possible. If you find that insert_after and erase_after aren't adequate for your needs, and that you often need to use insert and erase in the middle of the list, then you should probably use list instead of slist.”

Boost.Container updates the classic slist container with and implements it a bit differently than the standard C++ forward_list. forward_list has no size() method, so it's been designed to allow (or in practice, encourage) implementations without tracking list size with every insertion/erasure, allowing constant-time splice_after(iterator, forward_list &, iterator, iterator)-based list merging. On the other hand slist offers constant-time size() for those that don't care about linear-time splice_after(iterator, [classref boost::container::slist slist] &, iterator, iterator) size() and offers an additional splice_after(iterator, [classref boost::container::slist slist] &, iterator, iterator, size_type) method that can speed up slist merging when the programmer already knows the size. slist and forward_list are therefore complementary.

Differences with the standard std::forward_list. Both slist and the C++11 std::forward_list are singly linked lists with forward iterators, push_front, and the constant-time _after operations (insert_after, erase_after, splice_after), so most code looks the same with either. The relevant differences are:

The following example illustrates the most common operations, in particular the constant-time _after family (insert_after/erase_after), the use of before_begin() and the size-aware splice_after:

#include <boost/container/slist.hpp>

//Make sure assertions are active
#ifdef NDEBUG
#undef NDEBUG
#endif
#include <cassert>

int main ()
{
   using namespace boost::container;

   typedef slist<int> slist_t;

   slist_t l;

   //A singly linked list offers constant-time insertion/removal at the front.
   l.push_front(3);
   l.push_front(2);
   l.push_front(1);                       // {1, 2, 3}

   //Unlike std::forward_list, Boost.Container slist keeps track of its length,
   //so size() is a constant-time operation.
   assert(l.size() == 3);
   assert(l.front() == 1);

   //The efficient way to insert into a singly linked list is *after* a known
   //position (constant time). insert_after/erase_after avoid the linear scan
   //that plain insert/erase would need to locate the previous node.
   slist_t::iterator it = l.begin();      // -> 1
   ++it;                                   // -> 2
   l.insert_after(it, 20);                // {1, 2, 20, 3}
   assert(l.size() == 4);

   //erase_after removes the element following the iterator in constant time.
   l.erase_after(it);                     // removes 20 -> {1, 2, 3}
   assert(l.size() == 3);

   //before_begin() denotes the position just before the first element, so
   //inserting after it is equivalent to push_front.
   l.insert_after(l.before_begin(), 0);   // {0, 1, 2, 3}
   assert(l.front() == 0);

   //slist provides a size-aware splice_after overload that merges a range from
   //another list in constant time when the number of elements is known.
   slist_t other;
   other.push_front(6);
   other.push_front(5);                   // {5, 6}

   slist_t::iterator before_last = other.begin();
   ++before_last;                          // points to the last element (6)
   //Move the whole 'other' list to the front of 'l' in O(1).
   l.splice_after(l.before_begin(), other,
                  other.before_begin(), before_last, other.size());
   assert(other.empty());                  // {5, 6, 0, 1, 2, 3}

   //Forward, in-order traversal.
   const int expected[] = { 5, 6, 0, 1, 2, 3 };
   int i = 0;
   for(slist_t::const_iterator b = l.begin(), e = l.end(); b != e; ++b, ++i)
      assert(*b == expected[i]);
   assert(l.size() == 6);

   return 0;
}

static_vector is an hybrid between vector and array: like vector, it's a sequence container with contiguous storage that can change in size, along with the static allocation, low overhead, and fixed capacity of array. static_vector is based on Adam Wulkiewicz and Andrew Hundt's high-performance varray class.

What is it for?. static_vector stores its elements inside the container object itself, so it never performs dynamic memory allocation. This makes it ideal whenever heap allocation is undesirable or unavailable but a variable-length, vector-like interface is still convenient: embedded and realtime systems, hot code paths where allocation latency matters, fixed-size buffers, and the internal implementation of other classes are typical examples.

Relationship with other containers. The number of elements in a static_vector may vary dynamically up to a fixed capacity because elements are stored within the object itself, similarly to an array. However, objects are initialized as they are inserted into static_vector unlike C arrays or std::array, which must construct all elements on instantiation. The behavior of static_vector enables the use of statically allocated elements in cases with complex object lifetime requirements that would otherwise not be trivially possible. The key difference with small_vector is that small_vector falls back to dynamic storage once its in-place buffer is exhausted, while static_vector's capacity is a hard, compile-time bound that is never exceeded.

General properties. Some relevant properties are:

Error handling. By default (throw_on_overflow<true>) trying to insert beyond the fixed capacity throws bad_alloc (or calls throw_bad_alloc() when exceptions are disabled) instead of allocating more memory. Out-of-bounds access through at() throws out_of_range. If throw_on_overflow<false> is configured, inserting beyond capacity is undefined behavior, trading the safety check for minimum overhead.

Differences with the standard std::inplace_vector. C++26 added std::inplace_vector, a dynamically-resizable, fixed-capacity sequence container that stores its elements inside the object, i.e. the same idea pioneered by static_vector. The most relevant differences are:

The following example illustrates the most common operations and the fixed-capacity behavior:

#include <boost/container/static_vector.hpp>

#include <exception>

//Make sure assertions are active
#ifdef NDEBUG
#undef NDEBUG
#endif
#include <cassert>

int main ()
{
   using namespace boost::container;

   //A static_vector<int> that can hold at most 5 elements. All the storage
   //lives inside the object itself, so creating it performs no dynamic
   //allocation and the capacity is fixed at compile time.
   static_vector<int, 5> sv;

   assert(sv.empty());
   assert(sv.capacity() == 5);   //fixed capacity, known at compile time
   assert(sv.max_size() == 5);

   //Elements are inserted just like with a vector (constant time at the end).
   //Unlike std::array, elements are constructed only as they are inserted.
   for(int i = 0; i < 5; ++i)
      sv.push_back(i);

   assert(sv.size() == 5);
   assert(sv.size() == sv.capacity());   //the container is now full

   //Contiguous storage and random access, just like vector/array.
   assert(sv[0] == 0 && sv[4] == 4);
   assert(sv.data()[2] == 2);

   #ifndef BOOST_NO_EXCEPTIONS
   //By default (throw_on_overflow<true>) inserting beyond the fixed capacity
   //throws instead of allocating more memory.
   bool overflowed = false;
   try {
      sv.push_back(5);   //capacity already reached
   }
   catch(const std::exception &) {
      overflowed = true;
   }
   assert(overflowed);
   #endif

   //Removal at the end is constant time and never reallocates.
   sv.pop_back();
   assert(sv.size() == 4);

   return 0;
}

Customization. As with the other Boost.Container vector-like containers, static_vector can be tuned through static_vector_options (the overflow-checking policy described above and the integral type used to store the size). See the Configurable static vector section for examples.

small_vector is a vector-like container optimized for the case when it holds few elements. It embeds some preallocated, in-place storage for a number N of elements, which allows it to avoid any dynamic memory allocation as long as the actual number of elements does not exceed that preallocated threshold. small_vector is inspired by LLVM's SmallVector container.

What is it for?. Many programs create a large amount of short-lived sequences that, the overwhelming majority of the time, contain just a handful of elements. Using a plain vector in those scenarios means paying for a heap allocation (and the matching deallocation) on construction/growth even when only one or two elements are stored, which can dominate the cost and hurt cache locality. small_vector addresses this by carrying a small buffer inside the container object itself: while size() <= N no allocation takes place and the elements live next to the container, which is both faster and more cache-friendly. Typical uses are temporary working sets, the implementation details of other data structures, parser/AST node children, small option lists, etc.

Relationship with other containers. Unlike static_vector, whose capacity is a fixed compile-time bound, small_vector's capacity can grow beyond the initial preallocated N: when the preallocated buffer is exhausted it transparently switches to dynamically allocated storage, behaving from then on like an ordinary vector. In other words, static_vector never allocates (and throws if the fixed capacity is exceeded), whereas small_vector only allocates once it outgrows its in-place buffer. small_vector derives from vector and inherits all of its member functions, so it supports every standard feature such as emplacement, the full set of insertion/erasure operations, stateful allocators, and so on.

General properties. small_vector provides contiguous storage and random access iterators, just like vector. Insertion and removal are amortized constant time at the end and linear elsewhere. As with vector, iterators and references are invalidated by reallocation; note that, in addition, the very first growth past N (and any later shrink/transition between in-place and heap storage) moves the elements, so pointers, references and iterators are invalidated at those points even though the same logical element count is preserved.

Memory considerations. Because the in-place buffer is part of the object, sizeof(small_vector<T, N>) grows with N (roughly the size of an empty vector plus storage for N objects of type T). Choosing N is therefore a trade-off: a larger N avoids more allocations but makes the container object bigger (which matters when many of them are stored, moved around or kept on the stack). A good rule of thumb is to set N to the most common maximum size of the sequence so the common case stays allocation-free while the rare larger case still works by falling back to the heap.

small_vector_base: decoupling code from the preallocated count. The preallocated element count N is part of small_vector's type, so small_vector<T, 4> and small_vector<T, 64> are distinct, unrelated types. This is inconvenient for functions that just want to operate on "a small vector of T" regardless of how much in-place storage it happens to carry, as they would otherwise need to be turned into templates parameterized on N. To solve this, every small_vector<T, N, Allocator, Options> publicly derives from, and is implicitly convertible to, small_vector_base<T, Allocator, Options>, a base type that does not depend on N. Functions that read or modify a small vector can take a (const) reference to small_vector_base and accept any small_vector<T, N>:

#include <boost/container/small_vector.hpp>

#include <cstddef>

//Make sure assertions are active
#ifdef NDEBUG
#undef NDEBUG
#endif
#include <cassert>

using namespace boost::container;

//small_vector_base<T> erases the preallocated element count "N" from the type,
//so the following non-template functions accept any small_vector<int, N>.

//Reads any small_vector<int, N> (taken by const reference to the base).
int sum(const small_vector_base<int> &sv)
{
   int res = 0;
   for(std::size_t i = 0, n = sv.size(); i != n; ++i)
      res += sv[i];
   return res;
}

//Modifies any small_vector<int, N> (taken by reference to the base).
void push_range(small_vector_base<int> &sv, int first, int last)
{
   for(int i = first; i < last; ++i)
      sv.push_back(i);
}

int main ()
{
   //Two small_vectors with different in-place capacities (N = 4 and N = 64)...
   small_vector<int, 4>  sv_small;
   small_vector<int, 64> sv_big;

   //...both implicitly convert to small_vector_base<int>, so the very same
   //non-template functions can operate on either of them.
   push_range(sv_small, 0, 5);   //grows beyond its 4 preallocated elements
   push_range(sv_big,   0, 5);   //stays within its 64 preallocated elements

   //The behaviour is identical regardless of the preallocated capacity N.
   assert(sum(sv_small) == (0+1+2+3+4));
   assert(sum(sv_small) == sum(sv_big));

   return 0;
}

small_vector_base inherits all of vector's member functions as well, so the called code can use the full container interface. It is non-copyable and non-destructible on its own (it is meant to be used only through a derived small_vector object, typically as a function parameter), which keeps client interfaces free of the N template argument while preserving the small-buffer optimization of the concrete object passed in.

Customization. As with the other Boost.Container vector-like containers, small_vector can be tuned through small_vector_options (alignment of the in-place storage, growth factor, the integral type used to store the size/capacity, etc.). See the Configurable small vector section for examples.

segtor is 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. In that sense it is the single-ended counterpart of deque.

Unlike a single contiguous buffer, segmented storage avoids reallocating and moving all elements when the container grows: new blocks are allocated as needed. This can reduce peak memory and improve performance when elements are expensive to move or when growth is large. 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.

The container can be configured via segtor_options to control block size and other parameters.