在本章中，我们将介绍:
- 在序列容器中存储一些元素
- 在序列容器中存储最多 N 个元素
- 以超快的方式比较字符串
- 使用无序集和映射
- 制作地图，其中值也是一个关键
- 使用多索引容器
- 获得单一链表和内存池的好处
- 使用平面关联容器
本章专门介绍 Boost 容器以及与它们直接相关的东西。它提供了关于可以在日常编程中使用的 Boost 类的信息，这将使您的代码更快，新应用的开发更容易。
容器的不同不仅在于功能，还在于它的一些成员的效率(复杂性)。关于复杂性的知识对于编写快速应用至关重要。本章不仅仅向您介绍一些新的容器，它还为您提供了何时以及何时不使用特定类型的容器或其方法的提示。
那么，让我们开始吧！
在过去的二十年里，C++ 程序员使用std::vector作为默认的序列容器。它是一个快速的容器，不做大量的分配，以一种对 CPU 缓存友好的方式存储元素，并且因为容器像函数一样连续存储元素std::vector::data()允许与纯 C 函数交互操作。
但是，我们想要更多！有些情况下，我们确实知道要存储在向量中的典型元素数，我们需要通过完全消除这种情况下的内存分配来提高向量的性能。
想象一下，我们正在编写一个处理银行交易的高性能系统。事务是一系列操作，如果其中至少一个操作失败，这些操作必须全部成功或失败。我们知道 99%的事务包含 8 个或更少的操作，并希望加快速度:
#include <vector>
class operation;
template <class T>
void execute_operations(const T&);
bool has_operation();
operation get_operation();
void process_transaction_1() {
std::vector<operation> ops;
ops.reserve(8); // TODO: Memory allocation. Not good!
while (has_operation()) {
ops.push_back(get_operation());
}
execute_operations(ops);
// ...
}这个食谱只需要标准库和 C++ 的基础知识。
这将是本书最简单的任务，感谢Boost.Container图书馆:
- 包括适当的标题:
#include <boost/container/small_vector.hpp>- 将
std::vector替换为boost::container::small_vector并放弃reserve()呼叫:
void process_transaction_2() {
boost::container::small_vector<operation, 8> ops;
while (has_operation()) {
ops.push_back(get_operation());
}
execute_operations(ops);
// ...
}boost::container::small_vector的第二个模板参数是要在堆栈上预分配的元素计数。所以如果很多时候我们要在向量中存储 8 个或者更少的元素，我们只需要把8作为第二个模板参数。
如果我们必须在容器中存储 8 个以上的元素，那么small_vector的行为与std::vector完全一样，并动态分配一大块内存来存储 8 个以上的元素。就像std::vector一样，small_vector是一个带有随机访问迭代器的序列容器，它一致地存储元素。
总而言之，boost::container::small_vector是一个行为与std::vector完全相同的容器，但是允许为编译时指定数量的元素避免内存分配。
使用small_vector的一个缺点是我们的元素计数假设泄漏到接受small_vector作为参数的函数签名中。因此，如果我们有三个分别专用于4、8和16元素的函数，并且所有这些函数都使用前面示例中的execute_operations处理事务，那么我们将得到execute_operations函数的多个实例化:
void execute_operations(
const boost::container::small_vector<operation, 4>&);
void execute_operations(
const boost::container::small_vector<operation, 8>&);
void execute_operations(
const boost::container::small_vector<operation, 16>&);那可不好！现在，我们的可执行文件中有多个函数，它们做完全相同的事情，并且由几乎完全相同的机器代码组成。这导致了更大的二进制文件，更长的可执行文件启动时间，更长的编译和链接时间。一些编译器可能会消除冗余，但可能性很低。
不过，解决办法很简单。boost::container::small_vector来源于独立于预分配元素计数的boost::container::small_vector_base类型:
void execute_operations(
const boost::container::small_vector_base<operation>& ops
);就这样！现在，我们可以在任何boost::container::small_vector上使用新的execute_operations函数，而没有膨胀二进制大小的风险。
C++ 17 没有small_vector这样的类。有人提议将small_vector纳入将于 2020 年左右推出的下一个 C++ 标准。
- http://boost.org/libs/container 图书馆有许多有趣课程的完整参考文献
small_vector来自 LLVM 项目的 Boost 您可以在始发地http://llvm . org/docs/programmersmanual . html # llvm-ADT-small vector-h阅读关于集装箱的信息
这里有一个问题:如果我们知道序列从来没有超过 N 元素和 N 不大，我们应该用什么容器从函数返回序列。例如，我们必须如何编写最多返回五个事件的get_events()函数:
#include <vector>
std::vector<event> get_events();std::vector<event>分配内存，所以之前的代码不是一个好的解决方案。
#include <boost/array.hpp>
boost::array<event, 5> get_events();boost::array<event, 5>不分配内存，而是构造所有的五行。少于五个元素没办法返回。
#include <boost/container/small_vector.hpp>
boost::container::small_vector<event, 5> get_events();boost::container::small_vector<event, 5>不为五个或更少的元素分配内存，允许我们返回五个以下的元素。但是，解决方案并不完美，因为从函数接口来看，它从不返回超过五个元素并不明显。
这个食谱只需要标准库和 C++ 的基础知识。
Boost.Container有一个容器可以完美满足我们的需求:
#include <boost/container/static_vector.hpp>
boost::container::static_vector<event, 5> get_events();boost::container::static_vector<T, N>是一个不分配内存的容器，只能容纳编译时指定数量的元素。想象一下boost::container::small_vector<T, N>不能动态分配内存，任何存储超过 N 个元素的尝试都会导致std::bad_alloc异常:
#include <cassert>
int main () {
boost::container::static_vector<event, 5> ev = get_events();
assert(ev.size() == 5);
boost::container::static_vector<int, 2> ints;
ints.push_back(1);
ints.push_back(2);
try {
// The following line always throws:
ints.push_back(3);
} catch (const std::bad_alloc& ) {
// ...
}
}就像Boost.Container库的所有容器一样，static_vector支持移动语义并使用 Boost 模拟右值引用。如果编译器不支持右值，请移动库。
如果用户插入一个元素，并且无法将新值放入已经分配的内存中，则std::vector会分配更大的内存块。在这种情况下，std::vector将元素从旧位置移动到新位置，如果这些元素不是行移动可构造的。否则，std::vector将元素复制到新的位置，然后为旧位置的每个元素调用析构函数。
正因为如此，行为std::vector对于许多成员函数来说具有不变的复杂性。static_vector从不分配内存，因此它不必将元素从旧位置移动或复制到新位置。正因为如此，对于std::vector而言具有摊销的 O(1) 复杂度的操作对于boost::container::static_vector而言具有真正的 O(1)复杂度。这对于一些实时应用来说可能很方便；不过，要小心例外！
Some people still prefer to pass output parameters by reference instead of returning them: void get_events(static_vector<event, 5>& result_out). They think that this way, there's a guarantee that no copying of result happens. Don't do that, it makes things worse! C++ compilers have a whole bunch of optimizations, such as Return Value Optimization (RVO) and Named Return Value Optimization (NRVO); different platforms have agreements nailed down in ABI that code with retun something; does not result in an unnecessary copy and so forth. No copying happens already. However, when you pass a value, the reference compiler just does not see where the value came from and may assume that it aliases some other value in the scope. This may significantly degrade performance.
C++ 17 没有static_vector类，目前也没有计划将其加入 C++ 20。
Boost.Container的官方文档有一个详细的参考部分，描述了boost::container::static_vector类的所有成员函数。参考http://boost.org/libs/container.
操纵字符串是一项常见的任务。在这里，我们将看到如何使用一些简单的技巧快速完成字符串比较操作。这个配方是下一个配方的蹦床，这里描述的技术将用于实现恒定的时间复杂度搜索。
因此，我们需要创建一个能够快速比较字符串是否相等的类。我们将制作一个模板函数来测量比较的速度:
#include <string>
template <class T>
std::size_t test_default() {
// Constants
const std::size_t ii_max = 200000;
const std::string s(
"Long long long string that "
"will be used in tests to compare "
"speed of equality comparisons."
);
// Making some data, that will be
// used in comparisons.
const T data1[] = {
T(s),
T(s + s),
T(s + ". Whooohooo"),
T(std::string(""))
};
const T data2[] = {
T(s),
T(s + s),
T(s + ". Whooohooo"),
T(std::string(""))
};
const std::size_t data_dimensions = sizeof(data1) / sizeof(data1[0]);
std::size_t matches = 0u;
for (std::size_t ii = 0; ii < ii_max; ++ ii) {
for (std::size_t i = 0; i < data_dimensions; ++ i) {
for (std::size_t j = 0; j < data_dimensions; ++ j) {
if (data1[i] == data2[j]) {
++ matches;
}
}
}
}
return matches;
}这个食谱只需要标准库和 C++ 的基础知识。
我们将使std::string成为我们自己类中的一个公共字段，并将所有的比较代码添加到我们的类中，而不需要编写助手方法来处理存储的std::string，如下步骤所示:
- 为此，我们需要以下标题:
#include <boost/functional/hash.hpp>- 现在，我们可以创建我们的
fast comparison_类:
struct string_hash_fast {
typedef std::size_t comp_type;
const comp_type comparison_;
const std::string str_;
explicit string_hash_fast(const std::string& s)
: comparison_(
boost::hash<std::string>()(s)
)
, str_(s)
{}
};- 不要忘记定义
equality comparisons操作符:
inline bool operator == (
const string_hash_fast& s1, const string_hash_fast& s2)
{
return s1.comparison_ == s2.comparison_ && s1.str_ == s2.str_;
}
inline bool operator != (
const string_hash_fast& s1, const string_hash_fast& s2)
{
return !(s1 == s2);
}- 就这样！现在，我们可以使用以下代码运行测试并查看结果:
#include <iostream>
#include <iostream>
#include <cassert>
int main(int argc, char* argv[]) {
if (argc < 2) {
assert(
test_default<string_hash_fast>()
==
test_default<std::string>()
);
return 0;
}
switch (argv[1][0]) {
case 'h':
std::cout << "HASH matched: "
<< test_default<string_hash_fast>();
break;
case 's':
std::cout << "STD matched: "
<< test_default<std::string>();
break;
default:
return 2;
}
}字符串的比较很慢，因为如果字符串长度相等，我们需要逐个比较字符串的所有字符。相反，我们用整数的比较代替字符串的比较。这是通过hash函数实现的，该函数对字符串进行短固定长度的表示。
我们来谈谈苹果的hash值。想象一下，你有两个带标签的苹果，如下图所示，你希望检查这两个苹果的品种是否相同。比较这些苹果最简单的方法是通过标签进行比较。否则，您将失去大量时间来根据颜色、大小、形状和其他参数比较苹果。哈希类似于反映对象价值的标签。
现在，让我们一步一步来。
在步骤 1 中，我们包括了包含hash函数定义的头文件。在步骤 2 中，我们声明了新的string类，它包含str_，这是字符串的原始值，comparison_，这是计算出的hash值。注意结构:
boost::hash<std::string>()(s) 这里，boost::hash<std::string>是一个结构，一个功能对象，就像std::negate<>一样。这就是为什么我们需要第一个括号——我们构造这个函数对象。内有s的第二个括号是对std::size_t operator()(const std::string& s)的调用，它计算hash值。
现在，看看第三步，我们在这里定义operator==:
return s1.comparison_ == s2.comparison_ && s1.str_ == s2.str_; 额外注意表达式的第二部分。哈希操作会丢失信息，这意味着可能有多个字符串产生完全相同的hash值。这意味着如果哈希值不匹配，可以 100%保证字符串不匹配；否则，我们需要使用传统方法比较字符串。
是时候比较一下数字了。如果我们使用默认的比较方法来测量执行时间，它会给我们 819 毫秒；然而，我们的散列比较工作快了将近两倍，并且在 475 毫秒内完成。
C++ 11 有hash功能对象；您可以在std::名称空间的<functional>标题中找到它。Boost 和标准库中的哈希算法快速可靠。它不分配额外的内存，也没有虚拟功能。
您可以为自己的类型专门散列。在 Boost 中，这是通过在自定义类型的名称空间中专门化hash_value函数来完成的:
// Must be in the namespace of string_hash_fast class.
inline std::size_t hash_value(const string_hash_fast& v) {
return v.comparison_;
}这与std::hash的标准库专门化不同，标准库专门化要求您对std::命名空间中的hash<>结构进行模板专门化。
Boost 中的哈希是为所有基本类型(如int、float、double和char)定义的，为数组定义的，也为所有标准库容器定义的，包括std::array、std::tuple和std::type_index。一些库也提供散列专门化，例如Boost.Variant库可以散列任何boost::variant类。
- 阅读本章中的使用无序集和映射方法，了解更多关于散列函数用法的信息。
Boost.Functional/Hash的官方文档会告诉你如何组合多个哈希，并提供更多例子；在http://boost.org/libs/functional/hash阅读。
在前面的配方中，我们看到了如何使用哈希优化字符串比较。读完之后，可能会出现以下问题:我们能否制作一个容器来缓存散列值，以便更快地进行比较？
答案是肯定的，我们可以做得更多。我们可以实现几乎恒定的元素搜索、插入和移除时间。
需要 C++ 和 STL 容器的基本知识。阅读之前的食谱也会有所帮助。
这将是所有食谱中最简单的:
- 如果你想使用地图，你只需要包含
<boost/unordered_map.hpp>标题。如果我们希望使用器械包，请包含<boost/unordered_set.hpp>标题。 - 现在，您可以自由使用
boost::unordered_map代替std::map、boost::unordered_set代替std::set:
#include <boost/unordered_set.hpp>
#include <string>
#include <cassert>
void example() {
boost::unordered_set<std::string> strings;
strings.insert("This");
strings.insert("is");
strings.insert("an");
strings.insert("example");
assert(strings.find("is") != strings.cend());
}无序容器存储值并记住每个值的散列。现在，如果您希望在其中找到一个值，他们将计算该值的散列，并在容器中搜索该散列。在找到散列之后，容器检查找到的值和搜索到的值是否相等。然后，返回值或容器末尾的迭代器。
因为容器可能会搜索恒定宽度的整数哈希值，所以它可能会使用一些仅适用于整数的优化和算法。当传统的std::set和std::map提供更差的复杂度 O(log(N))，其中 N 是容器中的元素数量时，这些算法保证了恒定的搜索复杂度 O(1)。这就导致了一种情况，传统的std::set或std::map中的元素越多，它的工作速度就越慢。然而，无序容器的性能不依赖于元素数量。
如此出色的表现从来都不是免费的。在无序容器中，值是无序的(你并不惊讶，是吗？).这意味着我们将是容器的元素，从begin()到end()将是输出，如下所示:
template <class T>
void output_example() {
T strings;
strings.insert("CZ");
strings.insert("CD");
strings.insert("A");
strings.insert("B");
std::copy(
strings.begin(),
strings.end(),
std::ostream_iterator<std::string>(std::cout, " ")
);
}我们将得到std::set和boost::unordered_set的以下输出:
boost::unordered_set<std::string> : B A CD CZ
std::set<std::string> : A B CD CZ那么，性能相差多少？通常，这取决于实施质量。我有以下数字:
For 100 elements:
Boost: map is 1.69954 slower than unordered map
Std: map is 1.54316 slower than unordered map
For 1000 elements:
Boost: map is 4.13714 slower than unordered map
Std: map is 2.12495 slower than unordered map
For 10000 elements:
Boost: map is 2.04475 slower than unordered map
Std: map is 2.23285 slower than unordered map
For 100000 elements:
Boost: map is 1.67128 slower than unordered map
Std: map is 1.68169 slower than unordered map使用以下代码块测量性能:
T map;
for (std::size_t ii = 0; ii < ii_max; ++ ii) {
map[s + boost::lexical_cast<std::string>(ii)] = ii;
}
// Asserting.
for (std::size_t ii = 0; ii < ii_max; ++ ii) {
assert(map[s + boost::lexical_cast<std::string>(ii)] == ii);
}The code contains a lot of string constructions, so it is not 100% correct to measure the speedup using this test. It is here to show that unordered containers are usually faster than ordered ones.
有时，当我们需要在无序容器中使用用户定义的类型时，可能会出现一个任务:
struct my_type {
int val1_;
std::string val2_;
}; 为此，我们需要为该类型编写一个比较运算符:
inline bool operator == (const my_type& v1, const my_type& v2) {
return v1.val1_ == v2.val1_ && v1.val2_ == v2.val2_;
} 我们还需要专门化该类型的散列函数。如果类型由多个字段组成，我们通常只需要将参与equality comparisons的所有字段的哈希值进行组合即可:
std::size_t hash_value(const my_type& v) {
std::size_t ret = 0u;
boost::hash_combine(ret, v.val1_);
boost::hash_combine(ret, v.val2_);
return ret;
} It is highly recommended to combine hashes using the boost::hash_combine function.
容器也有多版本，在<boost/unordered_set.hpp>头中定义boost::unordered_multiset，在<boost/unordered_map.hpp>头中定义boost::unordered_multimap。就像标准库一样，容器的多版本能够存储多个相等的键值。
所有无序容器都允许您指定自己的散列函数，而不是默认的boost::hash。它们也允许你专门化你自己的相等比较函子，而不是默认的std::equal_to。
C++ 11 拥有 Boost 库的所有无序容器。您可以在标题中找到它们:<unordered_set>和<unordered_map>，在std::命名空间中，而不是boost::。Boost 和标准库版本的性能可能不同，但必须以相同的方式工作。然而，Boost 的无序容器即使在 C++ 03/C++ 98 编译器上也是可用的，并且利用了Boost.Move的右值引用仿真，所以即使在 C++ 11 之前的编译器上，您也可以将这些容器用于只移动类。
C++ 11 没有hash_combine函数，所以你得自己写:
template <class T>
inline void hash_combine(std::size_t& seed, const T& v)
{
std::hash<T> hasher;
seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
} 或者直接用boost::hash_combine。
自 Boost 1.64 以来，Boost 中的无序容器具有 C++ 17 的提取和插入节点的功能。
- 食谱使用 C++ 11 移动仿真在第 1 章、开始编写你的应用，了解更多关于
Boost.Move的右值参考仿真的细节 - 更多关于无序集装箱的信息可在官方网站http://boost.org/libs/unordered获得
- 有关组合散列和计算范围散列的更多信息，请访问http://boost.org/libs/functional/hash
一年中有几次，我们需要可以存储和索引一对值的东西。此外，我们需要使用第二个获得配对的第一部分，并使用第一个获得第二部分。迷茫？我给你举个例子。我们创建了一个词汇班。当用户将值放入其中时，类必须返回标识符，当用户将标识符放入其中时，类必须返回值。
更实际的是，用户将登录名放在我们的词汇表中，并希望从中获得唯一的标识符。他们还希望获得标识符的所有登录信息。
让我们看看如何使用 Boost 实现它。
本食谱需要标准库和模板的基本知识。
这个食谱是关于Boost.Bimap库的能力的。让我们看看如何使用它来实现这个任务:
- 我们需要以下内容:
#include <iostream>
#include <boost/bimap.hpp>
#include <boost/bimap/multiset_of.hpp>- 现在，我们准备制作我们的词汇结构:
int main() {
typedef boost::bimap<
std::string,
boost::bimaps::multiset_of<std::size_t>
> name_id_type;
name_id_type name_id;- 可以使用以下语法填充:
// Inserting keys <-> values
name_id.insert(name_id_type::value_type(
"John Snow", 1
));
name_id.insert(name_id_type::value_type(
"Vasya Pupkin", 2
));
name_id.insert(name_id_type::value_type(
"Antony Polukhin", 3
));
// Same person as "Antony Polukhin"
name_id.insert(name_id_type::value_type(
"Anton Polukhin", 3
));- 我们可以像处理地图一样处理它的左边部分:
std::cout << "Left:\n";
typedef name_id_type::left_const_iterator left_const_iterator;
const left_const_iterator lend = name_id.left.end();
for (left_const_iterator it = name_id.left.begin();
it!= lend;
++ it)
{
std::cout << it->first << " <=> " << it->second << '\n';
}- 右边部分和左边几乎一样:
std::cout << "\nRight:\n";
typedef name_id_type::right_const_iterator right_const_iterator;
const right_const_iterator rend = name_id.right.end();
for (right_const_iterator it = name_id.right.begin();
it!= rend;
++ it)
{
std::cout << it->first << " <=> " << it->second << '\n';
}- 我们还需要确保词汇中有这样一个人:
assert(
name_id.find(name_id_type::value_type(
"Anton Polukhin", 3
)) != name_id.end()
);
} /* end of main() */就是这样，现在如果我们把所有的代码(除了 includes)放在int main()里面，我们会得到如下输出:
Left:
Anton Polukhin <=> 3
Antony Polukhin <=> 3
John Snow <=> 1
Vasya Pupkin <=> 2
Right:
1 <=> John Snow
2 <=> Vasya Pupkin
3 <=> Antony Polukhin
3 <=> Anton Polukhin在步骤 2 中，我们定义了bimap类型:
typedef boost::bimap<
std::string,
boost::bimaps::multiset_of<std::size_t>
> name_id_type; 第一个模板参数告诉第一个键必须有类型std::string，应该作为std::set工作。第二个模板参数告诉第二个键必须有类型std::size_t。多个第一键可以有一个第二键值，就像std::multimap一样。
我们可以使用来自boost::bimaps::命名空间的类来指定bimap的底层行为。我们可以使用哈希映射作为第一个键的基础类型:
#include <boost/bimap/unordered_set_of.hpp>
#include <boost/bimap/unordered_multiset_of.hpp>
typedef boost::bimap<
boost::bimaps::unordered_set_of<std::string>,
boost::bimaps::unordered_multiset_of<std::size_t>
> hash_name_id_type; 当我们不指定键的行为而只指定其类型时，Boost.Bimap使用boost::bimaps::set_of作为默认行为。就像在我们的示例中一样，我们可以尝试使用标准库来表达以下代码:
#include <boost/bimap/set_of.hpp>
typedef boost::bimap<
boost::bimaps::set_of<std::string>,
boost::bimaps::multiset_of<std::size_t>
> name_id_type; 使用标准库，它看起来像是以下两个变量的组合:
std::map<std::string, std::size_t> key1; // == name_id.left
std::multimap<std::size_t, std::string> key2; // == name_id.right从前面的评论中我们可以看到，对name_id.left(在第 4 步中)的调用返回了对某个界面接近std::map<std::string, std::size_t>的东西的引用。从第 5 步调用name_id.right会返回一个界面接近std::multimap<std::size_t, std::string>的东西。
在第 6 步中，我们使用一个整体bimap，搜索一对密钥并确保它们在容器中。
可惜 C++ 17 没有什么接近Boost.Bimap的东西。以下是其他一些坏消息:
Boost.Bimap不支持右值引用，在某些编译器上，会显示大量的警告。请参考您的编译器文档，以获取有关抑制特定警告的信息。
好消息是Boost.Bimap通常比两个标准库容器使用更少的内存，并且搜索速度和标准库容器一样快。它内部没有虚函数调用，而是使用动态分配。
- 下一个食谱使用多索引容器，将会给你更多关于多索引的信息，以及关于可以代替
Boost.Bimap使用的 Boost 库的信息 - 阅读官方文档，了解更多关于 http://boost.org/libs/bimap 的示例和信息
在前面的食谱中，我们制作了某种词汇，当我们需要与人合作时，这很好。但是，如果我们需要更高级的索引呢？让我们做一个程序来索引人:
struct person {
std::size_t id_;
std::string name_;
unsigned int height_;
unsigned int weight_;
person(std::size_t id, const std::string& name,
unsigned int height, unsigned int weight)
: id_(id)
, name_(name)
, height_(height)
, weight_(weight)
{}
};
inline bool operator < (const person& p1, const person& p2) {
return p1.name_ < p2.name_;
}我们将需要很多索引，例如，姓名、身份证、身高和体重。
需要关于标准库容器和无序地图的基本知识。
所有的索引都可以由一个单独的Boost.Multiindex容器来构建和管理。
- 为此，我们需要大量的包括:
#include <iostream>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/member.hpp>- 最难的是构造
multi-index类型:
void example_main() {
typedef boost::multi_index::multi_index_container<
person,
boost::multi_index::indexed_by<
// names are unique
boost::multi_index::ordered_unique<
boost::multi_index::identity<person>
>,
// IDs are not unique, but we do not need them ordered
boost::multi_index::hashed_non_unique<
boost::multi_index::member<
person, std::size_t, &person::id_
>
>,
// Height may not be unique, but must be sorted
boost::multi_index::ordered_non_unique<
boost::multi_index::member<
person, unsigned int, &person::height_
>
>,
// Weight may not be unique, but must be sorted
boost::multi_index::ordered_non_unique<
boost::multi_index::member<
person, unsigned int, &person::weight_
>
>
> // closing for `boost::multi_index::indexed_by<`
> indexes_t;- 现在，我们可以在我们的
multi-index中插入值:
indexes_t persons;
// Inserting values:
persons.insert(person(1, "John Snow", 185, 80));
persons.insert(person(2, "Vasya Pupkin", 165, 60));
persons.insert(person(3, "Antony Polukhin", 183, 70));
// Same person as "Antony Polukhin".
persons.insert(person(3, "Anton Polukhin", 182, 70));- 让我们构造一个函数来打印索引内容:
template <std::size_t IndexNo, class Indexes>
void print(const Indexes& persons) {
std::cout << IndexNo << ":\n";
typedef typename Indexes::template nth_index<
IndexNo
>::type::const_iterator const_iterator_t;
for (const_iterator_t it = persons.template get<IndexNo>().begin(),
iend = persons.template get<IndexNo>().end();
it != iend;
++ it)
{
const person& v = *it;
std::cout
<< v.name_ << ", "
<< v.id_ << ", "
<< v.height_ << ", "
<< v.weight_ << '\n'
;
}
std::cout << '\n';
} - 按如下方式打印所有索引:
print<0>(persons);
print<1>(persons);
print<2>(persons);
print<3>(persons);- 也可以使用之前配方中的一些代码:
assert(persons.get<1>().find(2)->name_ == "Vasya Pupkin");
assert(
persons.find(person(
77, "Anton Polukhin", 0, 0
)) != persons.end()
);
// Won't compile:
//assert(persons.get<0>().find("John Snow")->id_ == 1);现在，如果我们运行我们的示例，它将输出索引的内容:
0:
Anton Polukhin, 3, 182, 70
Antony Polukhin, 3, 183, 70
John Snow, 1, 185, 80
Vasya Pupkin, 2, 165, 60
1:
John Snow, 1, 185, 80
Vasya Pupkin, 2, 165, 60
Anton Polukhin, 3, 182, 70
Antony Polukhin, 3, 183, 70
2:
Vasya Pupkin, 2, 165, 60
Anton Polukhin, 3, 182, 70
Antony Polukhin, 3, 183, 70
John Snow, 1, 185, 80
3:
Vasya Pupkin, 2, 165, 60
Antony Polukhin, 3, 183, 70
Anton Polukhin, 3, 182, 70
John Snow, 1, 185, 80这里最难的是使用boost::multi_index::multi_index_container构造多指标类型。第一个模板参数是我们要索引的类。在我们的情况下，就是person。第二个参数是类型boost::multi_index::indexed_by，所有的索引都必须描述为该类的模板参数。
现在，让我们看看第一个索引描述:
boost::multi_index::ordered_unique<
boost::multi_index::identity<person>
> boost::multi_index::ordered_unique类的用法意味着索引必须像std::set一样工作，并且拥有它的所有成员。boost::multi_index::identity<person>类意味着索引必须使用person类的operator <进行排序。
下表显示了Boost.MultiIndex类型和 STL 容器之间的关系:
| Boost.MultiIndex类型 | STL 容器 |
| boost::multi_index::ordered_unique | std::set |
| boost::multi_index::ordered_non_unique | std::multiset |
| boost::multi_index::hashed_unique | std::unordered_set |
| boost::multi_index::hashed_non_unique | std::unordered_mutiset |
| boost::multi_index::sequenced | std::list |
看看第二个指数:
boost::multi_index::hashed_non_unique<
boost::multi_index::member<
person, std::size_t, &person::id_
>
> boost::multi_index::hashed_non_unique类型意味着索引的工作方式类似于std::set，boost::multi_index::member<person, std::size_t, &person::id_>意味着索引必须将哈希函数仅应用于人员结构的单个成员字段，而不是person::id_。
剩下的指数现在不会有麻烦了；所以让我们来看看print函数中索引的用法。获取特定索引的迭代器类型是使用以下代码完成的:
typedef typename Indexes::template nth_index<
IndexNo
>::type::const_iterator const_iterator_t; 这看起来有点过于复杂，因为Indexes是一个模板参数。如果我们能在indexes_t的范围内编写这段代码，这个例子会更简单:
typedef indexes_t::nth_index<0>::type::const_iterator const_iterator_t;nth_index成员元函数使用从零开始的索引数。在我们的例子中，索引 1 是标识的索引，索引 2 是高度的索引，以此类推。
现在，我们来看看如何使用const_iterator_t:
for (const_iterator_t it = persons.template get<IndexNo>().begin(),
iend = persons.template get<IndexNo>().end();
it != iend;
++ it)
{
const person& v = *it;
// ... 这也可以简化为indexes_t在范围内:
for (const_iterator_t it = persons.get<0>().begin(),
iend = persons.get<0>().end();
it != iend;
++ it)
{
const person& v = *it;
// ... 函数get<indexNo>()返回索引。我们可以像使用 STL 容器一样使用该索引。
C++ 17 没有多索引库。Boost.MultiIndex是一个不使用虚函数的快速库。Boost.MultiIndex的官方文档包含性能和内存使用度量，表明该库在大多数情况下比基于标准库的手写代码使用更少的内存。不幸的是，boost::multi_index::multi_index_container不支持 C++ 11 特性，也没有使用Boost.Move的右值引用仿真。
Boost.MultiIndex的官方文档包含教程、性能度量、示例和其他Boost.Multiindex库对有用特性的描述。在http://boost.org/libs/multi_index.阅读
如今，当我们需要非关联和非有序的容器时，我们通常会使用std::vector。这是安德烈·亚历山德雷斯库和赫伯萨特在 C++ 编码标准一书中推荐的。即使是那些没有读过书的用户，通常也会使用std::vector。为什么呢？嗯，std::list比std::vector更慢，使用的资源也更多。std::deque容器与std::vector非常接近，但不连续存储数值。
如果我们需要一个容器，其中擦除和插入元素不会使迭代器无效，那么我们被迫选择一个缓慢的std::list。
但是等等，我们可能会用 Boost 组装一个更好的解决方案！
理解引言部分需要对标准库容器有很好的了解。之后，只需要 C++ 和标准库容器的基础知识。
在这个食谱中，我们将同时使用两个 Boost 库:Boost.Pool和一个来自Boost.Container的链表。
- 我们需要以下标题:
#include <boost/pool/pool_alloc.hpp>
#include <boost/container/slist.hpp>
#include <cassert>- 现在，我们需要描述列表的类型。这可以按照下面的代码来完成:
typedef boost::fast_pool_allocator<int> allocator_t;
typedef boost::container::slist<int, allocator_t> slist_t;- 我们可以像使用
std::list一样使用单个链表:
template <class ListT>
void test_lists() {
typedef ListT list_t;
// Inserting 1000000 zeros.
list_t list(1000000, 0);
for (int i = 0; i < 1000; ++ i) {
list.insert(list.begin(), i);
}
// Searching for some value.
typedef typename list_t::iterator iterator;
iterator it = std::find(list.begin(), list.end(), 777);
assert(it != list.end());
// Erasing some values.
for (int i = 0; i < 100; ++ i) {
list.pop_front();
}
// Iterator is still valid and points to the same value.
assert(it != list.end());
assert(*it == 777);
// Inserting more values
for (int i = -100; i < 10; ++ i) {
list.insert(list.begin(), i);
}
// Iterator is still valid and points to the same value
assert(it != list.end());
assert(*it == 777);
}
void test_slist() {
test_lists<slist_t>();
}
void test_list() {
test_lists<std::list<int> >();
}- 一些特定于列表的功能:
void list_specific(slist_t& list, slist_t::iterator it) {
typedef slist_t::iterator iterator;
// Erasing element 776
assert( *(++ iterator(it)) == 776);
assert(*it == 777);
list.erase_after(it);
assert(*it == 777);
assert( *(++ iterator(it)) == 775);- 必须使用以下代码释放内存:
// Freeing memory: slist rebinds allocator_t and allocates
// nodes of the slist, not just ints.
boost::singleton_pool<
boost::fast_pool_allocator_tag,
sizeof(slist_t::stored_allocator_type::value_type)
>::release_memory();
} // end of list_specific function当我们使用std::list时，我们可能会注意到速度变慢，因为列表的每个节点都需要单独分配。这意味着通常当我们在std::list中插入 10 个元素时，容器会调用new 10 次。此外，分配的节点通常随机位于内存中，这不利于 CPU 缓存。
这就是为什么我们从Boost.Pool开始使用 Boost ::fast_pool_allocator<int>。这个分配器试图分配更大的内存块，以便在稍后的阶段，无需多次调用new，就可以构建多个节点。
Boost.Pool库有一个缺点——它使用内存来满足内部需求。通常，每个元素使用额外的sizeof(void*)。为了解决这个问题，我们使用了一个来自Boost.Containers的链接列表。
boost::container::slist类更紧凑，但是它的迭代器只能向前迭代。步骤 3 对于那些了解标准图书馆容器的读者来说很简单，所以我们转到步骤 4 来看看一些boost::container::slist的具体特性。由于单个链表迭代器只能向前迭代，传统的插入和删除算法需要线性时间 O(N)。这是因为当我们擦除或插入时，必须修改列表的前一个元素。为了解决这个问题，单一链表有两种方法erase_after和insert_after，它们的工作时间都是 O(1)。这些方法在迭代器的当前位置之后插入或删除元素。
However, erasing and inserting values at the beginning of a single linked lists makes no big difference.
仔细看看下面的代码:
boost::singleton_pool<
boost::fast_pool_allocator_tag,
sizeof(slist_t::stored_allocator_type::value_type)
>::release_memory();之所以需要，是因为boost::fast_pool_allocator不释放内存，所以一定要手工做。在范围出口第二章资源管理中的在范围出口做某事的方法可能有助于释放Boost.Pool。
让我们看看执行时间，感受一下不同之处:
$ TIME="Runtime=%E RAM=%MKB" time ./07_slist_and_pool l
std::list: Runtime=0:00.08 RAM=34224KB
$ TIME="Runtime=%E RAM=%MKB" time ./07_slist_and_pool s
slist_t: Runtime=0:00.04 RAM=19640KB我们可以看到，slist_t使用了一半的内存，比std::list类快了一倍。
Boost.Container库实际上有一个现成的解决方案，叫做boost::container::stable_vector。后者允许随机访问元素，具有随机访问迭代器，但是具有std::list的大部分性能和内存使用缺点。
C++ 11 有std::forward_list，非常接近boost::containers::slist。它也有*_after法，但没有size()法。C++ 11 和 Boost 版本的单链表性能相同，都没有虚函数。然而，Boosts 版本也可以在 C++ 03 编译器上使用，甚至通过Boost.Move支持右值引用仿真。
boost::fast_pool_allocator不在 C++ 17 中。不过 C++ 17 有更好的解决方案！标题<memory_resource>包含使用多态分配器的有用内容，在这里你可以找到std::pmr::synchronized_pool_resource、std::pmr::unsynchronized_pool_resource和std::pmr::monotonic_buffer_resource。用这些进行实验，以获得更好的性能。
Guessing why boost::fast_pool_allocator does not free the memory by itself? That's because C++ 03 has no stateful allocators, so the containers are not copying and storing allocators. That makes it impossible to implement a boost::fast_pool_allocator function that deallocates memory by itself.
Boost.Pool的官方文档包含更多使用内存池的例子和类。跟随链接http://boost.org/libs/pool阅读。- 使用平面联想容器食谱将从
Boost.Container开始给你介绍更多的课程。您也可以在http://boost.org/libs/container阅读Boost.Container的官方文档，自行研究该图书馆或获取其课程的完整参考文档。 - Vector vs List ，C++ 编程语言的发明者比雅尼·斯特劳斯特鲁普的其他有趣话题可以在http://channel 9 . msdn . com/Events/going native/going native-2012/Keynote-Bjarne-Stroustrup-CPP 11-Style网站找到。
读完前面的食谱，有些读者可能会开始到处使用快速池分配器；尤其是对于std::set和std::map。好吧，我不会阻止你这么做，但至少让我们看看一个替代方案:平面关联容器。这些容器在传统向量容器的基础上实现，并存储有序的值。
需要标准库关联容器的基本知识。
扁平容器是Boost.Container库的一部分。在之前的食谱中，我们已经看到了如何使用它的一些容器。在本食谱中，我们将使用一个flat_set关联容器:
- 我们只需要包含一个头文件:
#include <boost/container/flat_set.hpp>- 之后，我们可以自由构建扁平容器并进行实验:
#include <algorithm>
#include <cassert>
int main() {
boost::container::flat_set<int> set;- 为元素保留空间:
set.reserve(4096);- 填充容器:
for (int i = 0; i < 4000; ++ i) {
set.insert(i);
}- 现在，我们可以像使用
std::set一样使用它:
// 5.1
assert(set.lower_bound(500) - set.lower_bound(100) == 400);
// 5.2
set.erase(0);
// 5.3
set.erase(5000);
// 5.4
assert(std::lower_bound(set.cbegin(), set.cend(), 900000) == set.cend());
// 5.5
assert(
set.lower_bound(100) + 400
==
set.find(500)
);
} // end of main() function步骤 1 和 2 简单，但是步骤 3 需要注意。这是使用平面关联容器和std::vector时最重要的步骤之一。
boost::container::flat_set类存储其在向量中排序的值，这意味着任何不在容器末端的元素的插入或删除都需要线性时间 O(N)，就像std::vector的情况一样。这是必然的罪恶。但为此，我们获得了每个元素少三倍的内存使用，更多的处理器缓存友好存储，以及随机访问迭代器。看看第 5 步、5.1，在这里我们得到了调用lower_bound成员函数返回的两个迭代器之间的距离。用平集求距离需要常数时间 O(1)，而对std::set的迭代器进行同样的运算需要线性时间 O(N)。在5.1的情况下，使用std::set获取距离将比获取平置集装箱的距离慢 400 倍。
回到第三步。如果不保留内存，元素的插入有时会变得更慢，内存效率也会降低。std::vector类分配所需的内存块，然后在该块上就地构造元素。当我们在没有保留内存的情况下插入一些元素时，有可能在预分配的内存块上没有剩余的可用空间，因此std::vector分配了更大的内存块。之后，std::vector将元素从第一个块复制或移动到第二个块，删除第一个块的元素，并释放第一个块。只有在那之后，插入才会发生。在插入过程中，这种复制和释放可能会发生多次，大大降低了速度。
If you know the count of elements that std::vector or any flat container must store, reserve the space for those elements before insertion. This speeds up the program in most cases!
第四步很简单，我们在这里插入元素。请注意，我们正在插入有序元素。这不是必需的，但建议加快插入速度。在std::vector的末尾插入元素比在中间或开头便宜得多。
在第五步中，5.2和5.3除了执行速度不同，没有太大区别。擦除元素的规则与插入元素的规则基本相同。解释见上一段。
May be I'm telling you simple things about containers, but I saw some very popular products that use features of C++ 11, have insane amount of optimizations and lame usage of standard library containers, especially std::vector.
在第 5 步中，5.4向您展示了std::lower_bound函数使用boost::container::flat_set比使用std::set更快，因为随机访问迭代器。
在第 5 步中，5.5也向您展示了随机访问迭代器的好处。
We did not use the std::find function here. This is because that function takes liner time O(N), while the member find functions take logarithmic time O(log(N)).
我们什么时候应该使用扁平容器，什么时候应该使用普通容器？好吧，这取决于你，但这里有一个不同于Boost.Container官方文档的列表，将帮助你做出决定:
- 比标准关联容器更快的查找
- 比标准关联容器快得多的迭代
- 小对象的内存消耗更少(如果使用
shrink_to_fit，则大对象的内存消耗更少) - 提高缓存性能(数据存储在连续内存中)
- 非稳定迭代器(迭代器在插入和删除元素时无效)
- 不能存储不可复制和不可移动的值类型
- 与标准关联容器相比，异常安全性较弱(复制/移动构造函数在擦除和插入中转移值时会引发异常)
- 与标准关联容器(特别是不可移动的类型)相比，插入和擦除速度更慢
不幸的是，C++ 17 没有平面容器。Boost 的平面容器速度快，有很多优化，不使用虚函数。来自Boost.Containers的类通过Boost.Move支持右值引用仿真，所以你甚至可以在 C++ 03 编译器上自由使用它们。
- 有关
Boost.Container的更多信息，请参考获取单链表和内存池的好处配方。 - 在第一章、中使用 C++ 11 移动仿真开始编写你的应用的食谱将为你提供 C++ 03 兼容编译器上仿真值引用的基础知识。
Boost.Container的官方文档中包含了很多关于Boost.Container的有用信息，以及每个类的完整参考。在http://boost.org/libs/container.阅读