STL и большинство других контейнеров инициализируют новые элементы в общих операциях, таких как<vector::resize(size_typen)>или<explicit vector::vector(size_typen)>.

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

Boost.Containerпредлагает два новых участника для<vector>,<static_vector>и<stable_vector>:<explicitcontainer::container(size_typen,default_init_t)>и<explicit container::resize(size_typen,default_init_t)>, где новые элементы построены с использованиеминициализации по умолчанию.

При заполнении ассоциативных контейнеров может быть достигнут большой прирост производительности, если входной диапазон, который должен быть вставлен, гарантирован пользователем для заказа в соответствии с предикатом. Это может произойти при вставке значений от<set>до<multiset>или между различными ассоциативными семействами контейнеров<[multi]set/map>против<flat_[multi]set/map>.

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

<set>,<multiset>,<map>и<multimap>ассоциативные контейнеры реализуются в виде двоичных поисковых деревьев, которые предлагают необходимые гарантии сложности и стабильности, требуемые стандартом C++ для ассоциативных контейнеров.

Boost.Containerпредлагает возможность настроить во время компиляции некоторые параметры реализации дерева двоичного поиска. Эта конфигурация передается в качестве последнего параметра шаблона и определяется с использованием класса полезности<tree_assoc_options>.

Можно настроить следующие параметры:

Смотрите следующий пример, чтобы увидеть, как<tree_assoc_options>можно использовать для настройки этих контейнеров:

#include <boost/container/set.hpp>
#include <cassert>
int main ()
{
   using namespace boost::container;
   //First define several options
   //
   //This option specifies an AVL tree based associative container
   typedef tree_assoc_options< tree_type<avl_tree> >::type AVLTree;
   //This option specifies an AVL tree based associative container
   //disabling node size optimization.
   typedef tree_assoc_options< tree_type<avl_tree>
                             , optimize_size<false> >::type AVLTreeNoSizeOpt;
   //This option specifies an Splay tree based associative container
   typedef tree_assoc_options< tree_type<splay_tree> >::type SplayTree;
   //Now define new tree-based associative containers
   //
   //AVLTree based set container
   typedef set<int, std::less<int>, std::allocator<int>, AVLTree> AvlSet;
   //AVLTree based set container without size optimization
   typedef set<int, std::less<int>, std::allocator<int>, AVLTreeNoSizeOpt> AvlSetNoSizeOpt;
   //Splay tree based multiset container
   typedef multiset<int, std::less<int>, std::allocator<int>, SplayTree> SplayMultiset;
   //Use them
   //
   AvlSet avl_set;
   avl_set.insert(0);
   assert(avl_set.find(0) != avl_set.end());
   AvlSetNoSizeOpt avl_set_no_szopt;
   avl_set_no_szopt.insert(1);
   avl_set_no_szopt.insert(1);
   assert(avl_set_no_szopt.count(1) == 1);
   SplayMultiset splay_mset;
   splay_mset.insert(2);
   splay_mset.insert(2);
   assert(splay_mset.count(2) == 2);
   return 0;
}

В первом стандарте C++<list::size()>не требовалось постоянное время, и это вызвало некоторые споры в сообществе C++. Говард ХиннантНа листе размеромбумаги:

C++11 определенно требовал<size()>быть O(1), поэтому сплайс диапазона стал O(N). Тем не менее, статья Говарда Хиннана предложила новую<splice>перегрузку, чтобы даже реализации O(1)<list:size()>могли достичь сплайса диапазона O(1), когда размер диапазона был известен абоненту:

Эта новая сплайс-подпись позволяет клиенту пройти расстояние входного диапазона. Эта информация часто доступна на сайте звонков. Если он проходит, то операция происходит постоянно, даже при размере O(1).

Boost.Containerреализует эту перегрузку для<list>и модифицированную версию для<slist>(как<slist::size()>также<O(1)>).

Многие программисты C++ когда-либо задавались вопросом, где хороший старый реаллок вписывается в C++. И это хороший вопрос. Можем ли мы улучшить производительность<vector>, используя механизмы расширения памяти, чтобы избежать слишком большого количества копий? Но<vector>не единственный контейнер, который мог бы извлечь выгоду из улучшенного интерфейса распределителя: мы могли бы воспользоваться вставкой нескольких элементов в<list>, используя механизм распределения лопастей, который мог бы амортизировать затраты (замкиmutex, поиск свободной памяти ...), которые не могут быть амортизированы при использовании стратегий распределения одного узла.

Эти улучшения требуют расширения интерфейса распределителя STL и использования нового распределителя общего назначения, поскольку новые и удаленные не предлагают возможности расширения и разрыва.

Используйте их, просто указав новый распределитель в соответствующем шаблоне аргумента вашего любимого контейнера:

#include <boost/container/vector.hpp>
#include <boost/container/flat_set.hpp>
#include <boost/container/list.hpp>
#include <boost/container/set.hpp>
//"allocator" is a general purpose allocator that can reallocate
//memory, something useful for vector and flat associative containers
#include <boost/container/allocator.hpp>
//"adaptive_pool" is a node allocator, specially suited for
//node-based containers
#include <boost/container/adaptive_pool.hpp>
int main ()
{
   using namespace boost::container;
   //A vector that can reallocate memory to implement faster insertions
   vector<int, allocator<int> > extended_alloc_vector;
   //A flat set that can reallocate memory to implement faster insertions
   flat_set<int, std::less<int>, allocator<int> > extended_alloc_flat_set;
   //A list that can manages nodes to implement faster
   //range insertions and deletions
   list<int, adaptive_pool<int> > extended_alloc_list;
   //A set that can recycle nodes to implement faster
   //range insertions and deletions
   set<int, std::less<int>, adaptive_pool<int> > extended_alloc_set;
   //Now user them as always
   extended_alloc_vector.push_back(0);
   extended_alloc_flat_set.insert(0);
   extended_alloc_list.push_back(0);
   extended_alloc_set.insert(0);
   //...
   return 0;
}

ДокументC++ Расширения для библиотечных основ (окончательный проект: N4480)включают классы, которые обеспечивают стирание типа распределителя и полиморфизм среды выполнения. Как объясняет автор предложения Пабло Гальперн в статье (N3916 Polymorphic Memory Resources (r2)):

“Существенным препятствием для эффективного управления памятью на C++ была неспособность использовать распределители в негенерических контекстах. В больших программных системах большая часть прикладной программы состоит из негенерического процедурного или объектно-ориентированного кода, который компилируется один раз и связывается много раз.& #8221;

& #8220;Распределители в C++, однако, исторически полагались исключительно на полиморфизм времени компиляции, и поэтому не подходили для использования в типах лексики, которые передаются через интерфейсы между отдельно компилируемыми модулями, поскольку тип распределителя обязательно влияет на тип объекта, который его использует. Это предложение основано на улучшениях, сделанных для распределителей в C++11, и описывает набор средств для ресурсов полиморфной памяти во время выполнения, которые взаимодействуют с существующими полиморфными распределителями во время компиляции.& #8221;

Boost.Containerреализует практически все классы предложения под пространством имен<boost::container::pmr>. Есть две группы,

Boost.Containerбиблиотека полиморфных ресурсов используется из контейнеров C++03 и предлагает некоторые альтернативные утилиты, если необходимые функции C++11Библиотечные основыспецификации отсутствуют.

Давайте рассмотрим пример использования, приведенный вN3916, и посмотрим, как он может быть реализован с использованиемBoost.Container:Предположим, что мы обрабатываем серию списков покупок, где список покупок представляет собой контейнер строк, и храним их в коллекции (списке) списков покупок. Каждый обрабатываемый список покупок использует ограниченное количество памяти, которое необходимо в течение короткого периода времени, в то время как сбор списков покупок использует неограниченное количество памяти и будет существовать в течение более длительного периода времени. Для эффективности мы можем использовать более эффективный по времени распределитель памяти на основе конечного буфера для временных списков покупок.

Давайте посмотрим, как<ShoppingList>можно определить для поддержки полиморфного ресурса памяти, который может выделять память из различных базовых механизмов. Наиболее важными деталями являются:

Примечание:В компиляторах C++03 требуется, чтобы программист специализировался как<true><constructible_with_allocator_suffix>или<constructible_with_allocator_prefix>, так как в C++03 нет способа автоматического обнаружения выбранной опции во время компиляции. Если специализация не выполняется,Boost.Containerпредполагает вариант суффикса.

//ShoppingList.hpp
#include <boost/container/pmr/vector.hpp>
#include <boost/container/pmr/string.hpp>
class ShoppingList
{
   // A vector of strings using polymorphic allocators. Every element
   // of the vector will use the same allocator as the vector itself.
   boost::container::pmr::vector_of
      <boost::container::pmr::string>::type m_strvec;
   //Alternatively in compilers that support template aliases:
   //    boost::container::pmr::vector<boost::container::pmr::string> m_strvec;
   public:
   // This makes uses_allocator<ShoppingList, memory_resource*>::value true
   typedef boost::container::pmr::memory_resource* allocator_type;
   // If the allocator is not specified, "m_strvec" uses pmr::get_default_resource().
   explicit ShoppingList(allocator_type alloc = 0)
      : m_strvec(alloc) {}
   // Copy constructor. As allocator is not specified,
   // "m_strvec" uses pmr::get_default_resource().
   ShoppingList(const ShoppingList& other)
      : m_strvec(other.m_strvec) {}
   // Copy construct using the given memory_resource.
   ShoppingList(const ShoppingList& other, allocator_type a)
      : m_strvec(other.m_strvec, a) {}
   allocator_type get_allocator() const
   { return m_strvec.get_allocator().resource(); }
   void add_item(const char *item)
   { m_strvec.emplace_back(item); }
   //...
};

Однако этот эффективный по времени распределитель не подходит для более долгой коллекции списков покупок. Этот пример показывает, как эти временные списки покупок с использованием эффективного по времени распределителя можно использовать для заполнения долгоживущей коллекции списков покупок, используя распределитель общего назначения, что было бы досадно трудно без полиморфных распределителей.

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

#include "ShoppingList.hpp"
#include <cassert>
#include <boost/container/pmr/list.hpp>
#include <boost/container/pmr/monotonic_buffer_resource.hpp>
void processShoppingList(const ShoppingList&)
{  /**/   }
int main()
{
   using namespace boost::container;
   //All memory needed by folder and its contained objects will
   //be allocated from the default memory resource (usually new/delete) 
   pmr::list_of<ShoppingList>::type folder; // Default allocator resource
   //Alternatively in compilers that support template aliases:
   //    boost::container::pmr::list<ShoppingList> folder;
   {
      char buffer[1024];
      pmr::monotonic_buffer_resource buf_rsrc(&buffer, 1024);
      //All memory needed by temporaryShoppingList will be allocated
      //from the local buffer (speeds up "processShoppingList")
      ShoppingList temporaryShoppingList(&buf_rsrc);
      assert(&buf_rsrc == temporaryShoppingList.get_allocator());
      //list nodes, and strings "salt" and "pepper" will be allocated
      //in the stack thanks to "monotonic_buffer_resource".
      temporaryShoppingList.add_item("salt");
      temporaryShoppingList.add_item("pepper");
      //...
      //All modifications and additions to "temporaryShoppingList"
      //will use memory from "buffer" until it's exhausted.
      processShoppingList(temporaryShoppingList);
      //Processing done, now insert it in "folder",
      //which uses the default memory resource
      folder.push_back(temporaryShoppingList);
      assert(pmr::get_default_resource() == folder.back().get_allocator());
      //temporaryShoppingList, buf_rsrc, and buffer go out of scope
   }
   return 0;
}

Обратите внимание, что списки покупок в<folder>используют ресурс распределителя по умолчанию, тогда как список покупок<temporaryShoppingList>использует недолговечный, но очень быстрый<buf_rsrc>. Несмотря на использование различных распределителей, вы можете вставить<temporaryShoppingList>в папку, потому что они имеют одинаковый<ShoppingList>тип. Кроме того, хотя<ShoppingList>использует память_ресурс напрямую,<pmr::list>,<pmr::vector>и<pmr::string>все используют<polymorphic_allocator>.

Ресурс, переданный конструктору<ShoppingList>, распространяется на вектор и каждую строку внутри этого<ShoppingList>. Аналогичным образом, ресурс, используемый для построения<folder>, распространяется на конструкторов Списков покупок, которые вставляются в список (и на строки в них<ShoppingLists>). Шаблон<polymorphic_allocator>предназначен для того, чтобы быть почти взаимозаменяемым с указателем на<memory_resource>, таким образом создавая мостмежду стилем распределителя шаблона-политики и стилем распределителя полиморфного базового класса.

Этот пример на самом деле показывает, насколько легко использоватьBoost.Containerдля написания классов, способных вычислять типы, даже в компиляторах C++03.