# Non\-standard containers in C\+\+

Container is an object which stores a collection of related objects \(or elements\)\. The container manages the storage space that is allocated for its elements\. 

![0989_Non_standard_containers/image1.png](https://import.viva64.com/docx/blog/0989_Non_standard_containers/image1.png)

The C\+\+ standard library includes a variety of containers\. Moreover, there is a number of Open Source containers that cover much more use cases\. I'm going to describe the arrangement of the most curious non\-[STL](https://en.cppreference.com/w/cpp/container) containers and their differences from the standard containers\.

![0989_Non_standard_containers/image2.png](https://import.viva64.com/docx/blog/0989_Non_standard_containers/image2.png)

Containers can be roughly divided into two categories – sequence and associative, since these two kinds of containers are too different\. In this article we will only discuss sequence containers\. And who knows, maybe one day I'll write an article about associative containers as well\.\.\.


> We published and translated this article with the copyright holder's permission\\\. The author is Evgeny Shulgin \\\(\[mizaronplatz@gmail\\\.com\]\(mailto:mizaronplatz@gmail\.com\)\\\)\\\. The article was originally published on \[Habr\]\(https://habr\.com/en/post/664044/\)\\\.

## Memory management 

An element requires a storage space where the values of its data members are located\. In standard applications, memory is taken from the stack or the heap\. It would be good to revise some basic concepts to understand this article better\.

Stack allocation is an increment of the stack pointer to a hard\-coded value\. Heap allocation may be a system call, some custom allocators with complex logic \(like tcmalloc, jemalloc\) may also be used, or memory pools – a lot is going on "under the hood"\.



You can see from the infographics below that these two types of allocation differ greatly in performance:

![0989_Non_standard_containers/image3.png](https://import.viva64.com/docx/blog/0989_Non_standard_containers/image3.png)

Stack allocation takes a few CPU operations, heap allocation may take thousands, depending on the allocator\. That is why you can significantly increase heap allocation performance\. You can read more about other allocators on [Habr \[RU\]](https://habr.com/en/post/505632/)\. 

## STL implementations for non\-standard containers 

The C\+\+ standard only covers the container interface and imposes some requirements for performance, gives some guarantees, and so on\.

STL has several implementations\. The same containers in different implementations do not usually differ that much from each other\. Currently, there are three the most popular STL implementations by Clang, GCC, and Microsoft\.

It's hard enough to read their implementations, since the same code should compile to all standards\. That's why implementations are usually a hodgepodge of \#ifdef's and some freaky code\.

```cpp
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
allocator() _NOEXCEPT = default;
```

The code for non\-standard containers is normally more readable\. Many libraries compile to a specific standard and/or can change the interface \(which is not possible in STL\)\.

## std::array 

The [std::array<T, N\>](https://en.cppreference.com/w/cpp/container/array) is the basic container\. Its semantics is no different from the usual _T\[N\] _array\. The elements are located on the stack\. You can neither insert nor erase elements — their number is exactly _N\._

The distinctive feature of the _std::array_ \(or more precisely, of the _T\[N\]_ array\) is that all its elements are initialized immediately and ready for use\.

![0989_Non_standard_containers/image4.png](https://import.viva64.com/docx/blog/0989_Non_standard_containers/image4.png)

Figure 1\. The _std::array<T, 8\>_

All containers perform two stages: "get memory for an element" and "initialize the element in that memory"\. The second stage may occur much later than the first\. But in _std::array _all _N_ elements are initialized immediately\.

According to the C\+\+ rules, elements in the array are initialized "from left to right" and destructed "[from right to left](https://godbolt.org/z/1hqd7vrKP)"\.

A brief note: the constructor/destructor of an element may perform no action at all \(may not change the memory, may not call any other methods, and so on\)\. This type of constructor/destructor is called trivial\. If _T_ has a trivial constructor and destructor, then nothing but memory allocation for _std::array<T, N\>_ [happens](https://godbolt.org/z/EjWd3c5M4)\. 

## std::vector 

The [_std::vector<T\>_](https://en.cppreference.com/w/cpp/container/vector) allocates memory for elements in the heap\. Three pointers to elements are on the stack: the pointer to the first element \(_begin_\), one past the last element \(_end_\), and one past the last unused memory area \(_end\_cap_\)\.



![0989_Non_standard_containers/image5.png](https://import.viva64.com/docx/blog/0989_Non_standard_containers/image5.png)

Figure 2\. The _std::vector<T\>_, _size_ \= 5, _capacity_ \= 8

An element is created in pre\-allocated memory via the [placement new](https://www.geeksforgeeks.org/placement-new-operator-cpp/) operator\. Since C\+\+11 with the introduction of [perfect forwarding](https://habr.com/en/post/242639/), a new element for a vector can be constructed in\-place \(using the _emplace_/_emplace\_back_ [member function](https://en.cppreference.com/w/cpp/container/vector/emplace_back)\) without any redundant copy/move constructor calls\.

![0989_Non_standard_containers/image6.png](https://import.viva64.com/docx/blog/0989_Non_standard_containers/image6.png)

Figure 3\. After inserting an element; _size_ \= 6, _capacity_ \= 8; _end_ is changed

The vector contains the _\.size\(\)_ member function, which stands for the number of existing elements; and the _\.capacity\(\)_ member function, which denotes the number of elements that can be held in currently allocated storage\.

An empty vector does not allocate anything \(_begin \= end \= end\_cap \= nullptr_\), so it has _size_ and _capacity_ equal to 0\.

When inserting a new element, if it does not "fit" into the memory, the memory is reallocated for _max\(1, 2 \* capacity\)_ elements\. Old elements are moved into the new memory\. The size of the vector grows in the sequence of **0, 1, 2, 4, 8, 16, \.\.\., 2N**\.

![0989_Non_standard_containers/image7.png](https://import.viva64.com/docx/blog/0989_Non_standard_containers/image7.png)

Figure 4\. _size_ \= _capacity_ \= 8, before inserting an element the reallocation is needed

![0989_Non_standard_containers/image8.png](https://import.viva64.com/docx/blog/0989_Non_standard_containers/image8.png)

Figure 5\. _capacity_ grows from 8 to 16

We need to move elements from the old memory into the new memory, and then free the old memory\. We can move elements in different ways, I'll describe the most convenient ones later in this article\. Now we'll look at the custom _std::vector_ implementation\.

## folly::fbvector, the improved std::vector

Folly is an open\-source C\+\+ library with a variety of useful things\. Folly has its own vector implementation – _folly::fbvector_, and the [documentation](https://github.com/facebook/folly/blob/main/folly/docs/FBVector.md) for it\.

The key difference from _std::vector_ is that the capacity grows not by **2** times, but by **1\.5** times\. The documentation explains in detail why this growth factor is more cache\-friendly\.

Moreover, this container cooperates with the jemalloc allocator \(if it's enabled\) and allocates memory for it\.

Another optimization is related to moving objects from the old memory to the new memory during vector reallocation\. For the CPU, any object is just a set of bytes\. If these bytes are moved, the object will still be usable in most cases\. Objects of this kind can be referred as **relocatable**\.

Here's an example of **non\-relocatable** object, since one data member points to another:

```cpp
class Ew
{
  char buffer[1024];
  char * pointerInsideBuffer;
public:
  Ew() : pointerInsideBuffer(buffer) {}
  ....
};
```

Folly treats objects of custom classes as **non\-relocatable** by default\. To specify that the custom _Widget_ class is **relocatable**, you need to write this:

```cpp
// at global namespace level
namespace folly
{
  struct IsRelocatable<Widget> : boost::true_type {};
}
```

I promised to tell you how to choose the relocation strategy, these are the options for _folly::fbvector_:

* If the type is _IsRelocatable_: **memcpy** is used for the memory occupied by objects\. 
* If the type has a noexcept move constructor: **move** is used for every object\. 
* If the type doesn't have a copy constructor: **move** is used for every object\. 
* By default: **copy** is used for every object\.

Some more information on the first point: memcpy is the fastest way to copy bytes to another memory area, and the implementation of this feature contains environment optimizations\.

As for the second point: why are the move constructors required to be noexcept? It's necessary to provide "strong exception guarantee"\.  Let's look at the code fragment:

```cpp
// using std::vector or folly::fbvector
void TryAddWidget(std::vector<Widget>& widgets)
{ 
  // execute some code...
  Widget w;
  try
  {
    widgets.push_back(std::move(w));
  }
  catch (...)
  {
    // caught an exception...
    // expect the widgets to remain usable
  }
}
```

"Strong exception guarantee" is required for keeping the vector in its consistent state\. In this case, the state of the vector is rolled back to the state just before the object inserting\.

If move constructor throws an exception, we have a risk to break up the original vector\. For example, we reallocate memory and exception occurred during the move:

![0989_Non_standard_containers/image9.png](https://import.viva64.com/docx/blog/0989_Non_standard_containers/image9.png)

Figure 6\. An exception is thrown when we move the fifth object

In general, objects should not be used after the move\. Since some of the objects have been moved to the new memory, you must move them back to the old memory\. And if you catch another exception again, the program execution is fully broken\.

Noexcept move constructors have no problems of this kind\. C\+\+ has rules on which classes can have [implicitly\-defined default constructors](https://en.cppreference.com/w/cpp/language/default_constructor), if possible, they should be noexcept\.

Many C\+\+ style guides do not allow exceptions at all \(for instance, [Google C\+\+ Style Guide](https://google.github.io/styleguide/cppguide.html#Exceptions)\), so this class of problems does not exist there\.

Some more information on the third point: if the class has no copy constructor \(which is relevant for the [_std::unique\_ptr_](https://en.cppreference.com/w/cpp/memory/unique_ptr) class\), then the move constructor is called whether there is noexcept specifier or not\. The call may break up the consistency of the vector \(no exception guarantee\), but this is unlikely, since there are quite few such classes\.

As for the last point: if all the previous points are not met, then we copy an object as usual\.

To implement such logic, special utilities from the standard library are used, for example, [_std::move\_if\_noexcept_](https://en.cppreference.com/w/cpp/utility/move_if_noexcept)\.

The _std::vector_ has the same logic for moving objects as _folly::fbvector_, except for the first point\. The _std::vector_ implementation treats the objects of _Widget_ class as **relocatable**, if [_std::is\_trivially\_move\_constructible<Widget\>::value \=\= true_](https://en.cppreference.com/w/cpp/types/is_move_constructible), and this cannot be changed\.

## std::deque

The [_std::deque_](https://en.cppreference.com/w/cpp/container/deque) \(double\-ended queue\) is a container that allows fast insertion of objects at both its beginning and its end\. While the _std::vector_ uses a single piece of memory, the _std::deque_ splits memory into equal chunks\.

![0989_Non_standard_containers/image10.png](https://import.viva64.com/docx/blog/0989_Non_standard_containers/image10.png)

Figure 7\. The _std::deque<T\>_, _start_ \= 3, _size_ \= 15 in the image

Pointers to the chunks are in a container similar to the vector \(with small differences in details\)\.

The object reference is obtained through 2 dereferences \(instead of 1 for the _std::vector_\)\.

If you fail to insert an object in the beginning/end, a new memory chunk is allocated first\. At worst, the pointer container reallocation to the chunks may be needed, so in this case there are two allocations\.

The advantage of the container is that when we're inserting new objects in the beginning/end, no references/pointers are invalidated\.

The disadvantage is the memory overhead, which is more noticeable if there are few objects in the container\. The _std::deque<T\>_ with a single object allocates a rather large chunk \(4096 bytes in the STL implementation by Clang\)\.

## Invalidation of iterators and pointers 

In fact, I've not written anything about iterator and pointer invalidation in detail yet\.

Even though the subject is already familiar to experienced C\+\+ developers, we should talk about it precisely in the context of non\-standard containers\.

An iterator of the _container<T\>_ is a sort of a ''light'' object, that should be similar to the _T\*_ pointer\. Every container has its own iterator\. The _iter\+\+ _call advances the pointer to the next element inside the container, while the _\*iter_ call gets the reference on the element pointed to\. That's the main purpose of iterators, which are needed a lot, for example, for [range\-for](https://en.cppreference.com/w/cpp/language/range-for)\.

The most primitive iterator of the _std::array<T\>_ is the _T\*_ pointer itself\.

The_ std::deque<T\>_ has a more complex iterator, consisting of two pointers: the pointer to the current chunk and the pointer to the current object of the chunk\. The _iter\+\+_ call safely updates these pointers and the _\*iter_ call returns the current object of the chunk\. Thus, iterators provide ''seamless'' traversal through the container elements\.

Iterators and pointers may become invalidated, which means they may no longer point to the object\. Usually people create all sorts of large tables where they analyze corner cases and many other things to describe the conditions for the invalidation\.

It's always better not to cram these tables, but to read the source code of the iterator's and the container's classes\. The insight into the question will come by itself\. For example, if you don't understand the inner workings of the _std::vector_ and the _std::deque_ containers, then it's more challenging to understand why, after the _push\_back_ call, an object reference in the first container may "expire", while in the second container it remains valid\.

While describing the inner structure of non\-standard containers I don't go into details on the conditions for the invalidation, since a lot is explained by the inner workings of the container\.

## std::forward\_list 

The [_std::forward\_list_](https://en.cppreference.com/w/cpp/container/forward_list) is a singly linked list, the easiest implementation of the linked list\. The list consists of a collection of nodes\. The node of the list is the object itself and the reference to the next node in the sequence \(the pointer is _nullptr_, if the object is the last in the sequence\)\. Memory is allocated independently for every node, _sizeof\(T\) \+ sizeof\(void\*\)_ bytes\.

![0989_Non_standard_containers/image11.png](https://import.viva64.com/docx/blog/0989_Non_standard_containers/image11.png)

Figure 8\. The _std::forward\_list<T\>_ consists of three objects, the root node on the stack

The container supports fast insertion and removal of elements from anywhere, since we only need to change the _next\_ptr_ for the left node\. However, the "fast insertion" refers specifically to the "algorithmic complexity"\. Memory allocation for the new node may be not so fast\.

![0989_Non_standard_containers/image12.png](https://import.viva64.com/docx/blog/0989_Non_standard_containers/image12.png)

Figure 9\. Inserting a new object into middle positions

You can't get the _N_\-th object quickly\. Firstly, you need to traverse from the root node to the _next\_ptr_ _N_ times\. Also, the list size can only be obtained by traversing all _next\_ptr_'s until we see _nullptr_\. The container doesn't even have the _\.size\(\)_ member function\.

Among non\-STL containers there are some other implementations of a singly linked lists, in which the _\.size\(\)_ member function is implemented for _**O\(1\)**_, for the overhead as a storing _size_ variable on the stack\.

Iterators and pointers to an object in this container are never invalidated unless the object is deleted\. Thus, the _std::forward\_list_ provides the strongest guaranties among all containers\.

## Std::list

The [_std::list_](https://en.cppreference.com/w/cpp/container/list) is a more complex implementation of the linked list\. It has all the same properties as the _std::forward\_list_, but the nodes can also reference to the previous nodes, moreover, the container supports fast insertion of elements into the end of the list\.

![0989_Non_standard_containers/image13.png](https://import.viva64.com/docx/blog/0989_Non_standard_containers/image13.png)

Figure 10\. The _std::list<T\>_, _size_ \= 3

Fun fact: since C\+\+11, the _\.size\(\)_ member function must have a [constant complexity](https://en.cppreference.com/w/cpp/container/list/size)\. A variable where the list size is written is supported for this purpose\. Until C\+\+11, the _\.size\(\)_ member function  implementation could have a linear complexity, traversing all nodes\.

## Adapter containers 

Some containers do not have a tricky internal arrangement, their distinctive functionality is based on the other container's functionality\. There are three STL containers of this kind: _std::stack_, _std::queue_, _std::priority\_queue_, and you can choose a "real'' container for each of them\.

```cpp
Template <class T,
          class Container = std::deque<T>>
class stack;

template <class T,
          class Container = std::deque<T>>
class queue;

template <class T,
          class Container = std::vector<T>,
          class Compare = std::less<typename Container::value_type>>
class priority_queue;
```

In most cases an interface of an adapter container simply redirects the member function call, such as in the _std::stack_:

```cpp
bool empty()     const      { return c.empty(); }
size_type size() const      { return c.size(); }
reference top()             { return c.back(); }
void push(const value_type &__v) { c.push_back(__v); }
void pop() { c.pop_back(); }
```

## Bit containers – std::bitset, std::vector<bool\>, boost::dynamic\_bitset

Bit containers are needed to manage a sequence of _N_ bits\. Which means that these containers store only bits\. 

An object cannot "weigh" less than 1 byte, but one byte holds as much as [_CHAR\_BIT_](https://en.cppreference.com/w/cpp/types/climits) bits \(usually _CHAR\_BIT \= 8_\)\. That is why a special container for bits is 8 times more efficient in terms of memory management\.

Physically, such containers contain several numbers, usually, of the _size\_t_ type \(their size is 64 bits on a 64\-bit machine\)\.

Just as with "standard" containers, data can either be on the stack or on the heap\.

![0989_Non_standard_containers/image14.png](https://import.viva64.com/docx/blog/0989_Non_standard_containers/image14.png)

Figure 11\. The _std::bitset<512\>_ on a 64\-bit machine \(8 _size\_t_ numbers are enough\)

For the [_std::bitset<N\>_,](https://en.cppreference.com/w/cpp/utility/bitset) which is on the stack, you need to know the number of bits "in advance"\. Initially, all bits are filled with zeros\. The container has several approaches to manage bits \(all bits or a specific bit\)\.

Group operations like the [_\.count\(\)_](https://en.cppreference.com/w/cpp/utility/bitset/count) are much faster compared to the ones in the common _for_ loop\. Processor produces bit operations on a number in a single instruction, which is at least 64 times faster than if they were done in a loop\.

Bit operations done via the _operator\[\]_ are supported in a special way:

```cpp
std::bitset<512> b;
b[128] = 1; // or b[128] = true
```

The_ operator\[\]\(size\_t pos_\) is overloaded so that its call returns the "light" _std::bitset::reference_ object, which contains a pointer to the number and the bitmask\. At the same time, the object has the _operator\=\(bool x\)_ overloaded\. The operator writes to the required bit\.

As you may have already noticed, C\+\+ uses many such tricks with the proxy objects \(iterators, bit references\) to make it convenient for users to work with objects\.

The_ std::vector<bool\>_ is a similar class that allocates data on the heap \(where the number of bits can be set in run\-time\)\. Many developers don't like this class, some consider it to be a [bad design in C\+\+ \[RU\]](http://alenacpp.blogspot.com/2005/06/vector.html)\. For example, those who try to use it as a conforming container instead of the "_std::bitset_ on a heap", find it impossible to use direct pointers to an object \(you cannot point to an individual bit\)\. But, if you have problems of this kind, you can always use _std::vector<char\>_, _std::vector<int\>_, _std::deque<bool\>_\.

![0989_Non_standard_containers/image15.png](https://import.viva64.com/docx/blog/0989_Non_standard_containers/image15.png)

Figure 12\. The _std::vector<bool\>_ or the _boost::dynamic\_bitset_

The_ std::vector<bool\>_ is extremely poor in the bit operations available\. The container lacks basic group bit operations, which, as I mentioned above, the processor produces much more effectively\.

There is a more advanced analog of _std::vector<bool\>_ in Boost – [_boost::dynamic\_bitset_](https://www.boost.org/doc/libs/1_79_0/libs/dynamic_bitset/dynamic_bitset.html)\. It has a fast implementation of every bitset operation imaginable\. This container has a wide range of uses\.

"Non\-standard" containers are great since they can be easily patched\. A few years ago, I patched _boost::dynamic\_bitset_ to make bit counting faster and add new member functions to control the [bit](https://github.com/boostorg/dynamic_bitset/commits?author=Izaron) sequence\.

## Static vector 

The previously discussed _std::array<T, N\>_ has a property of initializing all _N_ objects at once\. If you don't need this property and want to manage memory for _N_ objects, you can use the [boost::static\_vector](https://www.boost.org/doc/libs/1_79_0/doc/html/boost/container/static_vector.html)\.

![0989_Non_standard_containers/image16.png](https://import.viva64.com/docx/blog/0989_Non_standard_containers/image16.png)

Figure 13\. The _boost::static\_vector<T, 8\>_

This container behaves just as the usual _std::vector_, but its memory is allocated on the stack for _N_ objects\.

How do you allocate raw memory on the stack without an existing object? Until C\+\+23, you could do it through [_std::aligned\_storage_](https://en.cppreference.com/w/cpp/types/aligned_storage) with a high risk to make a mistake and to shoot yourself in the foot\. Since C\+\+23, you can do it more easily:

```cpp
alignas(T) std::byte buff[sizeof(T)];
```

and then create objects in _buff_ using the placement new\.

An exception is thrown when you try to insert _N\+1_ object into the _boost::static\_vector_\. You can write code and run it through [godbolt](https://godbolt.org/z/o3Y4MhjYe), which supports Boost\. To enhance the performance greatly you can set the template not to throw an exception, so the program just [crashes](https://godbolt.org/z/9GTa8rhsn)\.

## Small vector

The [_boost::small\_vector_](https://www.boost.org/doc/libs/1_79_0/doc/html/boost/container/small_vector.html) is some kind of a hybrid of the _boost::static\_vector_ and the _std::vector_\. It statically allocates memory for N objects, but in case of overflow it allocates memory on the heap\.

![0989_Non_standard_containers/image17.png](https://import.viva64.com/docx/blog/0989_Non_standard_containers/image17.png)

Figure 14\. The _boost::small\_vec<T, 8\>_ with 13 objects

In the image _N_ objects are on the stack and _size \- N_ objects are on the heap\. In some implementations all _size_ objects are allocated on the heap to ensure that the objects are in a contiguous storage area \(when _size \> N_\)\.

You can effectively use this container if a number of elements that can be held is not likely to be greater than a predicted one\.

The authors of this container say that they took inspiration from SmallVector in [LLVM](https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h)\. That's no surprise – the containers described in this article were reinvented numerous times\.

Boost has its own reinvented ~~wheel~~ implementation of STL containers with various features\. For example, you can set [growth factor](https://www.boost.org/doc/libs/1_79_0/doc/html/boost/container/growth_factor.html) of a vector or set the block size for a deque\.

## Devector

The_ boost::devector_ is a hybrid of the _std::vector_ and the _std::deque_\. This container allows fast insertion at both its beginning and its end, just like the deque\. But this container still keeps the vector features, such as the contiguous storage area and the conditions for the invalidation of iterators/pointers\.

![0989_Non_standard_containers/image18.png](https://import.viva64.com/docx/blog/0989_Non_standard_containers/image18.png)

Figure 15\. The _boost::devector<T\>_, _size_ \= 5, _front\_capacity_ \= 1, _back\_capacity_ \= 2

When the vector is reallocated, we select in which direction the vector should be expanded \(right or left\), depending on which limit was exceeded\.

If _sizeof\(std::vector\) \=\= 3 \* sizeof\(T\*\)_, then the devector requires an additional pointer\. Therefore _sizeof\(boost::devector\) \=\= 4 \* sizeof\(T\*\)_\.

## Stable vector 

The [_boost::stable\_vector_](https://www.boost.org/doc/libs/1_79_0/doc/html/boost/container/stable_vector.html) is a hybrid of the _std::vector_ and the _std::list_\.

The_ std::vector_ has a disadvantage – references and iterators are easily invalidated\. This happens when a vector is reallocated, or when an object is erased/inserted closer to the beginning\.

Containers can be divided into "stable" and "unstable" types\. "Stable" containers keep references and iterators to the object valid until the object is erased from the container\. The _std::list_ is a perfect example of a "stable" container\. While the _std::vector_ is "unstable" container\.

If you cancel the linear arrangement requirement for the _std::vector_, you can implement a "stable" analogue of a vector:

![0989_Non_standard_containers/image19.png](https://import.viva64.com/docx/blog/0989_Non_standard_containers/image19.png)

Figure 16\. The _boost::stable\_vector<T\>_, contains 5 objects

Where the _std::vector_ has objects, the _boost::stable\_vector_ has an array of references to _node_ instead\.

A **node** contains _value_ – the object, and _up_ – the back reference to the certain position in the array with the value pointing to the _node_\.

Just as for the _std::list_, the **node** for each object is allocated separately\.

The iterator to an object is a reference to a **node**\. 

References and iterators to an object are valid until the object is erased in the container\. Inserting/erasing an object that is "closer" to the beginning of the vector will rewrite the pointer _up_, but neither the reference \(to _value_\) nor the iterator \(**node\***\) will change\. Reallocation of the array of references to nodes does not invalidate references/iterators to an object \(the container fixes the _up_ value during the reallocation\)\.

Now look at how the iterator works on the oversimplified pseudocode\. For example, there is a vector with pointers to the nodes \(as in the picture\):

```cpp
template <typename T>
struct node;

template <typename T>
std::vector<node<T>*> node_ptrs;
```

The node contains two values: the reference to the certain position in the node reference array; and the object itself\.

```cpp
template <typename T>
struct node
{
  node<T>** up;
  T value;
};
```

The iterator works with a reference to the node:

```cpp
template <typename T>
class stable_vector_iterator
{
public:
  using self = stable_vector_iterator;

  self& operator++()
  {
    p = *(p->up + 1);
    return *this;
  }

  T& operator*()
  {
    return p->value;
  }

private:
    node<T> *p;
};
```

To get the reference to the ''next'' node, you have to follow _up_ to the array location where the current reference is, move to the next location, and dereference the resulting value\.

Algorithmic complexity of the _boost::stable\_vector_ member functions is exactly the same as the corresponding _std::vector_ member functions\. In particular, unlike the _std::list_, an object can be obtained by any index for _**O\(1\)**_\.

## Circular buffer 

There is an article on [Wikipedia](https://en.wikipedia.org/wiki/Circular_buffer) about the circular buffer\. In C\+\+, it can be implemented as a fixed\-size container \(on the stack or on the heap\)\. An object is created at the beginning of the array when the array is out of bounds\.

![0989_Non_standard_containers/image20.png](https://import.viva64.com/docx/blog/0989_Non_standard_containers/image20.png)

Figure 17\. Circular buffer with the memory on the stack for 8 objects; _start_ \= 5, _size_ \= 5

Circular buffer can also be implemented as a usual vector\. The container's advantage is the fast insertion/removal at its beginning\. The disadvantage is a strict memory limit of _N_ objects\. And that's all\. There is nothing else special about this container\.

Circular buffer is implemented in Boost as well: [_boost::circular\_buffer_](https://www.boost.org/doc/libs/1_79_0/doc/html/boost/circular_buffer.html)\. 

## Colony

Container _colony_ is a hybrid of the _std::deque_ and the _std::list_\. This container was proposed to the C\+\+ standard library, but hasn't yet been adopted\. Here is a document with the detailed description of this [container](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0447r9.html)\.

In many projects, objects more often do not "own" other objects, but only refer to them\. For example, in video games entity objects may refer to \(rather than contain\) shared resources like sprites, sounds and so on\.

Those shared resources are usually located in containers\. The container should stay stable regardless of its resource changes \(insertion/erasure\)\. Unfortunately, the _std::vector_ is not stable, while the _std::list_ is not okay with cache and decreases performance, especially during iteration\.

Colony is quite fast and "stable" container\. The objects it contains are allocated into chunks, as in the _std::deque_\. In the _std::deque_ objects are allocated closely to each other, while the colony may have 'skips' \(erased elements\) in the chunks\. The overall view of the colony changed several times over the past years, but schematically it looks like this: 

![0989_Non_standard_containers/image21.png](https://import.viva64.com/docx/blog/0989_Non_standard_containers/image21.png)

Figure 18\. The _colony<T\>_

When an object is erased from the colony, the objects to its right will not move to its place\. Thus, pointers to an object stay valid\.

Colony has the skipfield structure, which encodes information about 'skips'\. 'Skips' are reused – when a new object is inserted, it is written in the leftmost 'skip'\. The skipfield is also required in order to skip over erased elements during iteration\.

In addition to stability, the container has these guarantees for basic operations:

* insertion \(one object\): **O\(1\)**;
* insertion \(_N_ objects\): **O\(N\)**;
* erasure \(one object\): **O\(1\)**;
* erasure \(_N_ objects\) **O\(N\)** for non\-trivially\-destructible elements, and **O\(logN\)** for trivially\-destructible elements;
* _std::find_: **O\(N\)**; you need to iterate over the container to find an object;
* Random access \(operator _\[\]_\): **O\(N\)**; due to "skips" it is impossible to access a random object beyond **O\(1\)**\.

This container is the best option if you need a structure that allows fast insertion/erasure of objects and to keep the references valid\. At the same time, this container is faster than the _std::list_\. However, it is not possible to quickly obtain an object by an arbitrary index, the container is not built for that\.

See the container's implementation on [github](https://github.com/mattreecebentley/plf_colony)\. 

## How to choose the most suitable container? 

Now that we've discussed both standard and non\-standard containers, we can examine a practical case\.

For example, you're developing the display of fast food ads on a website\. You need to display the top 5 most relevant meals\. They depend on the user's region, the meals that are available in the nearest fast food joint, promotions, current local time, etc\.

Requests come to the service API\. Suppose that all data that determines the top meals is represented by C\+\+ classes/structures\.

Let's imagine an API class that defines one of the nearest fast food joints to the user\. It contains the distance to a user \(the longer, the less important\), occupancy, the meals available, promos, and the history of user's visits\.

```cpp
struct Restaurant
{
  double Distance;                 // distance
  double Occupancy;                // occupancy
  std::vector<Meal*> Meals;        // meals available
  std::vector<Promo*> Promos;      // promos
  std::vector<Visit> VisitHistory; // the history of visits
};
```

Some data is "owned" by the object \(like visit history\), and some data is just referenced because it is common to all users\.

Here we have a problem – suppose we have the _std::vector<Meal\> Meals_ objects somewhere in the program\. If we create _Restaurant_\-es and then add some new dish, we can get a vector reallocation, and then all _Meal\*_ references will become dangling\.

You can turn objects into a smart pointer \(_std::vector<std::shared\_ptr<Meal\>\> Meals_\), but that's clumsy and even not for free\.

But you can solve multiple issues at once – **all API classes must be made [non\-copyable](https://www.boost.org/doc/libs/master/libs/core/doc/html/core/noncopyable.html#core.noncopyable.header_boost_core_noncopyable_hp)\. And non\-movable\.** What are the advantages:

* objects cannot be accidentally passed by value, copied or moved;
* pointers to objects are valid until a container with an object is deleted\.

The C\+\+ compiler will not allow the container to be used as the _std::vector_, which can potentially invalidate references\. But it will compile a safe container such as the _std::list_\. If the containers are non\-standard, then, for example, the _stable\_vector_ or the _colony_ will be compiled\.