Boost C++ 库

对于支持右值引用的编译器以及那些使用 Boost.Move 进行右值引用仿真的 C++03 类型，Boost.Container 支持所有与移动语义相关的 C++11 功能：容器是可移动的，value_type 的要求与 C++11 容器的要求相同。

对于支持可变参数模板的编译器，Boost.Container 支持 C++11 中的原地插入（emplace 等）函数。对于不支持可变参数模板的编译器，Boost.Container 使用预处理器创建一组最多包含有限数量参数的重载。

C++03 不利于有状态分配器。为了使容器对象紧凑和简单，它不要求容器支持有状态分配器：分配器对象不需要存储在容器对象中。无法存储有状态分配器，例如持有指向内存池指针的分配器，用于分配内存。C++03 允许实现者假定同一类型的两个分配器总是相等（这意味着由一个分配器对象分配的内存可以由同一类型的另一个实例释放），并且在容器交换时分配器不会被交换。

C++11 通过 std::allocator_traits 进一步改进了有状态分配器的支持。std::allocator_traits 是容器和分配器之间的协议，分配器作者可以遵循 allocator_traits 的要求来自定义其行为（容器是否应在移动构造函数、交换等操作中传播它？）。Boost.Container 不仅支持 C++11 中的模型，还通过 boost::container::allocator_traits 将其回溯移植到 C++03，包括一些 C++17 的更改。该类提供了一些针对 C++03 编译器的解决方案，以实现与 std::allocator_traits 相同的分配器保证。

在 [Boost.Container] 容器中，如果可能，会保留一个分配器来构造 value_type。如果容器需要辅助分配器（例如 deque 或 stable_vector 使用的数组分配器），该分配器也会存储在容器中，并在容器构造时从用户提供的分配器进行初始化（即，在需要辅助内存时不会即时构造）。

C++11 通过引入 std::scoped_allocator_adaptor 类模板来改进有状态分配器。scoped_allocator_adaptor 使用一个外部分配器和零个或多个内部分配器进行实例化。

作用域分配器是一种机制，可以自动以受控方式将分配器的状态传播到容器的子对象。如果仅使用一种分配器类型进行实例化，则内部分配器将成为 scoped_allocator_adaptor 本身，从而为容器及其内部的每个元素使用相同的分配器资源，如果元素本身是容器，则递归地为每个元素的元素使用相同的分配器资源。如果使用多个分配器进行实例化，第一个分配器是容器使用的外部分配器，第二个分配器将传递给容器元素的构造函数，如果元素本身是容器，则第三个分配器将传递给元素的元素，依此类推。

Boost.Container 实现自己的 scoped_allocator_adaptor 类，并将其回溯移植到 C++03 编译器。由于 C++03 的限制，在这些编译器中，由 scoped_allocator_adaptor::construct 函数实现的分配器传播将基于 N2554：作用域分配器模型（Rev 2）提案 中提出的特征（constructible_with_allocator_suffix 和 constructible_with_allocator_prefix）。在符合 C++11 的编译器或支持 SFINAE 表达式的编译器中（当 BOOST_NO_SFINAE_EXPR 未定义时），将忽略特征，并使用 C++11 规则（is_constructible<T, Args..., inner_allocator_type>::value 和 is_constructible<T, allocator_arg_t, inner_allocator_type, Args...>::value）来检测分配器是否必须作为后缀或前缀分配器参数进行传播。

LWG Issue #233 纠正了 C++98 中的一个缺陷，并规定了如何将等效键插入关联容器。Boost.Container 实现 N1780 《关于 LWG 问题 233：关联容器中的插入提示》 中指定的 C++11 更改。

Boost.Container 支持在实现此功能的编译器中，从初始化列表中进行初始化、赋值和插入。

Boost.Container 实现 C++14 Null Forward Iterators，这意味着值初始化的迭代器可以与同一类型的其他值初始化的迭代器进行比较并相等。值初始化的迭代器行为就如同它们指向同一个空序列的末尾（示例来自 N3644）。

vector<int> v = { ... };
auto ni = vector<int>::iterator();
auto nd = vector<double>::iterator();
ni == ni; // True.
nd != nd; // False.
v.begin() == ni; // ??? (likely false in practice).
v.end() == ni;   // ??? (likely false in practice).
ni == nd; // Won't compile.

文档 C++ 库基础扩展（最终草案） 包含提供分配器类型擦除和运行时多态的类。正如 Pablo Halpern 在论文（N3916 多态内存资源（r2））中所解释的：

“C++ 中有效内存管理的一个重大障碍是无法在非泛型上下文中使用的分配器。在大型软件系统中，大部分应用程序由非泛型过程代码或面向对象代码组成，这些代码被编译一次并链接多次。”

“然而，C++ 中的分配器历来仅依赖于编译时多态，因此不适用于词汇类型，这些类型通过接口在独立编译的模块之间传递，因为分配器类型必然会影响使用它的对象的类型。本提案建立在 C++11 对分配器的改进之上，并描述了一套用于运行时多态内存资源的设施，这些资源可与现有的编译时多态分配器互操作。”

Fundamentals TS 的大多数实用程序已合并到 C++17 中，但 Boost.Container 为 C++03、C++11 和 C++14 编译器提供了它们。

Boost.Container 在 boost::container::pmr 命名空间下实现了提案中几乎所有的类。它们分为两类：

Boost.Container 的多态资源库可用于 C++03 容器，并在 Library Fundamentals 规范中需要 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 插入到 folder 中，因为它们具有相同的 ShoppingList 类型。此外，虽然 ShoppingList 直接使用 memory_resource，但 pmr::list、pmr::vector 和 pmr::string 都使用 polymorphic_allocator。

传递给 ShoppingList 构造函数的资源会传播到该 ShoppingList 中的向量和每个字符串。类似地，用于构造 folder 的资源会传播到插入到列表中的 ShoppingLists（以及那些 ShoppingLists 中的字符串）的构造函数。 polymorphic_allocator 模板设计得几乎可以与 memory_resource 指针互换使用，从而在模板策略式分配器和多态基类式分配器之间产生了桥梁。

此示例实际展示了即使在 C++03 编译器中，使用 Boost.Container 编写支持类型擦除分配器的类是多么容易。

Boost.Container 尚未提供 C++11 forward_list 容器，但它将在未来版本中提供。

vector 不支持 std::vector 在 insert、push_back、emplace、emplace_back、resize、reserve 或 shrink_to_fit 等函数中为可复制或无抛出移动类型提供的强异常保证。在 C++11 中，move_if_noexcept 用于在 C++03 异常安全保证与 C++11 移动语义相结合的情况下，保持 C++03 异常安全保证。这种强异常保证会降低可复制和抛出移动类型的插入性能，当使用上述成员在向量中插入这些类型时，会将移动操作降级为复制操作。

这种强异常保证也排除了使用某些类型的原地重分配的可能性，这些重分配可以进一步提高 vector 的插入性能。请参阅 扩展分配器 以了解有关这些优化的更多信息。

vector 始终使用移动构造函数/赋值来重新排列向量中的元素，并使用内存扩展机制（如果分配器支持），同时仅提供基本安全保证。它以牺牲异常保证来换取提高的性能。

几个容器操作使用通过 const 引用传递但在函数执行期间可能被修改的参数。LWG Issue 526（《标准中的函数修改参数是否未定义？》）讨论了这些问题。

//Given std::vector<int> v
v.insert(v.begin(), v[2]);
//v[2] can be changed by moving elements of vector

//Given std::list<int> l:
l.remove(*l.begin())
//The operation could delete the first element, and then continue trying to access it.

通过的决议 NAD（非缺陷）意味着之前的操作必须是明确定义的。这要求代码检测对已插入元素的引用，并在该情况下进行额外的复制，即使不使用对已插入对象的引用也会影响性能。请注意，接受右值引用或迭代器范围的等效函数需要容器中尚未插入的元素。

Boost.Container 优先考虑性能，尚未实现 NAD 决议：在可能修改参数的函数中，库要求使用非存储在容器中的元素的引用。使用对已插入元素的引用将导致未定义行为（尽管在调试模式下，可以通过 BOOST_ASSERT 通知这种前提条件违反）。

vector<bool> 的特化一直很成问题，并且有几次尝试从标准中弃用或删除它。Boost.Container 没有实现它，因为有更优越的 Boost.DynamicBitset 解决方案。有关 vector<bool> 的问题，请参阅以下论文：

引言

因此，boost::container::vector<bool>::iterator 返回真实的 bool 引用，并作为完全兼容的容器工作。如果您需要 boost::container::vector<bool> 的内存优化版本，请使用 Boost.DynamicBitset。

Boost.Container 使用 std::memset 并以零值初始化一些类型，因为在大多数平台上，这种初始化能够带来更好的性能并产生所需的值初始化。

遵循 C11 标准，Boost.Container 假定对于任何整数类型，所有位都为零的对象表示形式应为该类型的值零的表示形式。由于 _Bool/wchar_t/char16_t/char32_t 在 C 中也是整数类型，因此它将所有 C++ 整型视为可以通过 std::memset 进行初始化。

默认情况下，Boost.Container 也认为浮点类型可以使用 std::memset 进行初始化。大多数平台都兼容这种初始化，但如果这种初始化不理想，用户可以在包含库头文件之前定义 #define BOOST_CONTAINER_MEMZEROED_FLOATING_POINT_IS_NOT_ZERO。

默认情况下，它还认为指针类型（指针和指向函数的指针，不包括成员对象和成员函数指针）可以使用 std::memset 进行初始化。大多数平台都兼容这种初始化，但如果这种初始化不理想，用户可以在包含库头文件之前定义 #define BOOST_CONTAINER_MEMZEROED_POINTER_IS_NOT_ZERO。