Этот полезный, полностью совместимый с STL стабильный контейнер, разработанный Joaquín M. López Muñoz— гибрид между<vector>и<list>, обеспечивающий большинство признаков<vector>, за исключениемСвязность элементов.

Чрезвычайно удобные<vector>s имеют ограничение, на которое часто натыкаются многие начинающие программисты на C++: итераторы и ссылки на элемент<vector>недействительны, когда предыдущий элемент стирается или когда вектор расширяется и нуждается в миграции своего внутреннего хранилища в более широкую область памяти (т.е. когда требуемый размер превышает емкость вектора). Тогда мы говорим, что<vector>s нестабильны: напротив, стабильные контейнеры — это те, для которых ссылки и итераторы на данный элемент остаются действительными до тех пор, пока элемент не стерт: примеры стабильных контейнеров в стандартной библиотеке C++ являются<list>и стандартными ассоциативными контейнерами<set>,<map>и т. д.

Иногда стабильность является слишком ценной особенностью, чтобы жить без нее, но одно конкретное свойство<vector>s, связанность элементов, делает невозможным добавление стабильности в этот контейнер. Итак, при условии, что мы жертвуем смежностью элементов, насколько стабильный дизайн может подходить к поведению<vector>(случайные итераторы доступа, амортизированная постоянная вставка / удаление окончания времени, минимальные накладные расходы на память и т. д.)? На следующем изображении описывается схема возможной структуры данных, на которой основывается конструкция стабильного вектора:

Каждый элемент хранится в своем отдельном узле. Все узлы ссылаются на смежный массив указателей, но также каждый узел содержит указатель «вверх», ссылающийся на связанную ячейку массива. Этот указатель является ключевым элементом для реализации стабильности и случайной доступности:

Итераторы указывают на узлы, а не на массив указателей. Это обеспечивает стабильность, поскольку при вставке или удалении необходимо перемещать или перемещать только указательный массив. Операции случайного доступа могут быть реализованы с использованием массива указателей в качестве удобной промежуточной зоны. Например, если итератор содержит указатель узла<it.p>и мы хотим продвинуть его по n позиций, мы просто делаем:

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

То есть мы идем «вверх» к массиву указателей, добавляем туда n и затем идем «вниз» к полученному узлу.

Общие свойства.<stable_vector>удовлетворяют всем требованиям контейнера, обратимого контейнера и последовательности и обеспечивают все необязательные операции, присутствующие в векторе. Как и вектор, итераторы являются случайным доступом.<stable_vector>не обеспечивает смежность элементов; в обмен на это отсутствие контейнер стабилен, то есть ссылки и итераторы на элемент<stable_vector>остаются действительными до тех пор, пока элемент не стерт, а итератор, которому было присвоено обратное значение конца(), всегда остаются действительными до разрушения связанного<stable_vector>.

Сложность операции. Сложности операций с большими О<stable_vector>точно соответствуют векторным. В целом, вставка/удаление является постоянным временем в конце последовательности и линейным в другом месте. В отличие от вектора,<stable_vector>не выполняет внутренне никаких операций разрушения типа значения, копирования / перемещения конструкции / назначения, кроме тех, которые точно соответствуют вставке новых элементов или удалению сохраненных элементов, что иногда может компенсировать с точки зрения производительности дополнительное бремя выполнения большего количества манипуляций с указателями и дополнительного распределения на элемент.

Безопасность исключения. (по терминологии Абрахама) Поскольку<stable_vector>не копирует/не перемещает элементы внутри, некоторые операции обеспечивают более сильные гарантии безопасности исключения, чем в векторе:

Накладная память. Стандарт C++ не определяет требования к потреблению памяти, но практически любая реализация<vector>имеет такое же поведение по отношению к использованию памяти: память, выделенная a<vector>v с n элементами типа T, является

m_v= c∙e,

где c<v.capacity()>и e<sizeof(T)>. c может быть таким же низким, как n, если пользователь явно зарезервировал требуемую емкость; в противном случае среднее значение c для растущего<vector>колеблется между 1,25∙n и 1,5∙n для типичных политик изменения размера.<stable_vector>Использование памяти

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

где p - размер указателя. У нас есть c + 1 и n + 1, а не c и n, потому что в конце последовательности нужен фиктивный узел. Если мы назовем f отношением мощности к размеру c/n и предположим, что n достаточно велико, мы получим

m_sv/m_v& #8771; (fp + e + p)/fe.

Таким образом,<stable_vector>использует меньше памяти, чем<vector>, только когда e >p и отношение емкости к размеру превышает заданный порог:

m_sv< m_v<->f >(e + p)/(e - p) (при условии e >p)

Этот порог приближается к типичным значениям f ниже 1,5, когда e >5p; в 32-битной архитектуре, когда e >20 байт.

Краткое изложение.<stable_vector>является заменой для<vector>, обеспечивающей стабильность ссылок и итераторов, в обмен на недостающую смежность элементов, а также некоторые накладные расходы на производительность и память. Когда объекты элементов дороги для перемещения, накладные расходы на производительность могут превратиться в чистый прирост производительности для<stable_vector>, если выполняется много средних вставок или удалений или если очень часто происходит изменение размера. Аналогично, если элементы велики, бывают ситуации, когда память, используемая<stable_vector>, на самом деле может быть меньше, чем требуется вектором.

Примечание: Текст и пояснения взяты изJoaquín's blog

Использование отсортированных векторов вместо древесных ассоциативных контейнеров является хорошо известной техникой в мире C++. Классическая статья Мэтта ОстернаWhy You Shouldn't Use Set, and What You Should Use Instead(C++ Report 12:4, April 2000)

& #8220;Красно-черные деревья — не единственный способ организовать данные, позволяющие искать в логарифмическое время. Одним из основных алгоритмов информатики является двоичный поиск, который работает путем последовательного деления диапазона пополам. Бинарный поиск - это log N, и он не требует каких-либо причудливых структур данных, просто отсортированный набор элементов. (...) Вы можете использовать любую удобную структуру данных, если она обеспечивает итератор STL; обычно проще всего использовать массив C или вектор.& #8221;

& #8220;Оба std::lower_bound и set::find требуют времени, пропорционального log N, но константы пропорциональности очень разные. Использование g++ (...) X секунд для выполнения миллиона поисковых запросов в сортированном вектореиз миллиона элементов и почти в два раза длиннее (...) с использованием набора. Более того, в наборе используется почти в три раза больше памяти (48 млн байт), чем в векторе (16,8 млн).& #8221;

& #8220;Использование сортированного вектора вместо набора дает вам более быстрый поиск и гораздо более быструю итерацию, но за счет более медленной вставки. Вставка в набор, используя множество::вставка, пропорциональна журналу N, но вставка в сортированный вектор, (...), пропорциональна N. Всякий раз, когда вы вставляете что-то в вектор, вектор: вставка должна освободить место, сместив все элементы, которые следуют за ней. В среднем, если вы с одинаковой вероятностью вставите новый элемент в любом месте, вы будете перемещать элементы N/2.& #8221;

& #8220;Иногда может быть удобно связать все это вместе в небольшой адаптер контейнера. Этот класс не удовлетворяет требованиям стандартного ассоциативного контейнера, так как сложность вставки составляет O(N), а не O(log N), но в противном случае это почти замена набора.& #8221;

Следуя указаниям Мэтта Остерна, современный дизайн С++Андрея Александрескупоказал<AssocVector>, замену<std::map>, разработанную в его библиотекеЛоки:

& #8220;Кажется, что нам лучше иметь сортированный вектор. Недостатками сортированного вектора являются линейно-временные вставки и линейно-временные делеции (...). Взамен вектор предлагает примерно вдвое большую скорость поиска и гораздо меньший рабочий набор. Локи избавляет от проблем с поддержанием сортированного вектора вручную, определяя шаблон класса AssocVector. AssocVector - это замена std::map (он поддерживает тот же набор функций-членов), реализованный поверх std::vector. AssocVector отличается от карты поведением своих функций стирания (AssocVector::erase делает недействительными все итераторы в объект) и гарантиями сложности вставки и стирания (линейный, а не постоянный).& #8221;

Boost.Container<flat_[multi]map/set>контейнеры упорядоченно-векторные на основе ассоциативных контейнеров на основе принципов Остерна и Александреску. В последнее время эти упорядоченные векторные контейнеры также получили пользу от добавления<movesemantics>к C++, что значительно ускорило время вставки и стирания. Плоские ассоциативные контейнеры имеют следующие атрибуты:

Когда была разработана стандартная библиотека шаблонов, она содержала единый связанный список под названием<slist>. К сожалению, этот контейнер не был стандартизирован и оставался расширением для многих стандартных реализаций библиотеки, пока не был представлен C++11<forward_list>, который немного отличается от оригинального SGI<slist>. Согласнодокументации SGI STL:

& #8220;<slist>представляет собой единый список: список, в котором каждый элемент связан со следующим элементом, но не с предыдущим элементом. То есть это последовательность, которая поддерживает прямое, но не обратное прохождение, и (амортизированное) постоянное вставление времени и удаление элементов. Списки, как и списки, имеют важное свойство, что вставка и сплайсинг не делают недействительными итераторы для списка элементов, и что даже удаление недействительными только итераторы, которые указывают на элементы, которые удаляются. Упорядочение итераторов может быть изменено (т.е. у итератора может быть другой предшественник или преемник после операции списка, чем это было раньше), но сами итераторы не будут признаны недействительными или сделаны с указанием на различные элементы, если эта недействительность или мутация не явна.& #8221;

& #8220;Основное различие между<slist>и списком заключается в том, что итераторы списка являются двунаправленными итераторами, в то время как итераторы списка являются передовыми итераторами. Это означает, что<slist>менее универсален, чем список; однако часто двунаправленные итераторы не нужны. Обычно вы должны использовать<slist>, если вам не нужна дополнительная функциональность списка, потому что списки, связанные по отдельности, меньше и быстрее, чем двойные списки.& #8221;

& #8220;Важное примечание: как и любая другая последовательность,<slist>определяет вставку и стирание функций-членов. Однако небрежное использование этих функций может привести к катастрофически медленным программам. Проблема в том, что первый аргумент вставки - это итератор pos, и что он вставляет новый элемент(ы) перед pos. Это означает, что вставка должна найти итератор непосредственно перед pos; это операция с постоянным временем для списка, поскольку список имеет двунаправленные итераторы, но для<slist>он должен найти этот итератор, пересекая список от начала до pos. Другими словами, вставка и стирание являются медленными операциями в любом месте, кроме начала списка.& #8221;

& #8220;Slist предоставляет функции вставки_после и удаления_после, которые являются операциями с постоянным временем: вы всегда должны использовать вставку_после и стирать_после, когда это возможно. Если вы обнаружите, что вставка_после и удаление_после не соответствуют вашим потребностям, и что вам часто нужно использовать вставку и удаление в середине списка, то вам, вероятно, следует использовать список вместо списка.& #8221;

Boost.Containerобновляет классический контейнер<slist>с функциями C++11, такими как семантика перемещения и вставка размещения, и реализует его немного иначе, чем стандартный C++<forward_list>.<forward_list>не имеет метода<size()>, поэтому он был разработан для того, чтобы разрешать (или на практике поощрять) реализации без размера списка отслеживания с каждой вставкой / стиранием, позволяя слияние списка на основе постоянного времени<splice_after(iterator,forward_list&, iterator, iterator)>. С другой стороны,<slist>предлагает постоянное время<size()>для тех, кто не заботится о линейном времени<splice_after(iterator,slist&, iterator, iterator)><size()>и предлагает дополнительный<splice_after(iterator,slist&,iterator,iterator,size_type)>метод, который может ускорить<slist>слияние, когда программист уже знает размер.<slist>и<forward_list>являются взаимодополняющими.

<static_vector>является гибридом между<vector>и<array>: как<vector>, это контейнер последовательностей с непрерывным хранилищем, который может изменяться в размере, наряду со статическим распределением, низкими накладными расходами и фиксированной емкостью<array>.<static_vector>основан на высокопроизводительном классе Адама Вулькевича и Эндрю Хундтаvarray.

Число элементов в<static_vector>может динамически изменяться до фиксированной емкости, поскольку элементы хранятся внутри самого объекта аналогично массиву. Однако объекты инициализируются, когда они вставляются в<static_vector>, в отличие от массивов C или<std::array>, которые должны конструировать все элементы при инстанциации. Поведение<static_vector>позволяет использовать статически выделенные элементы в случаях со сложными требованиями к сроку службы объекта, которые в противном случае были бы тривиально невозможны. Некоторые другие свойства:

<static_vector>хорошо подходит для использования в буфере, внутренней реализации других классов или в случаях использования, когда существует фиксированное ограничение на количество элементов, которые должны храниться. Встроенные приложения и приложения в режиме реального времени, в которых распределение может быть либо недоступным, либо приемлемым, являются конкретным случаем, когда<static_vector>может быть полезным.

<small_vector>представляет собой векторный контейнер, оптимизированный для случая, когда он содержит мало элементов. Он содержит некоторые предварительно выделенные элементы на месте, что позволяет избежать использования динамического распределения памяти, когда фактическое количество элементов ниже этого предварительно выделенного порога.<small_vector>вдохновлен контейнеромLLVM<SmallVector>. В отличие от<static_vector>,<small_vector>емкость может вырастать за пределы первоначальной предварительно выделенной емкости.

<small_vector<T,N,Allocator>>является конвертируемым в<small_vector_base<T, Allocator>>, тип, который не зависит от предварительно выделенного количества элементов, позволяя клиентскому коду, который не должен быть шаблонизирован на этом аргументе N.<small_vector>наследует все функции<vector>, поэтому он поддерживает все стандартные функции, такие как размещение, государственные распределители и т. Д.