C++ Boost MultiIndex使用详细介绍
无水先生 人气:0一、关于BOOST的容器
容器是 C++ 中最有用的数据结构之一。标准库提供了许多容器，而 Boost 库提供的更多。
- Boost.MultiIndex 更进一步：这个库中的容器可以同时支持来自其他容器的多个接口。来自 Boost.MultiIndex 的容器就像合并的容器，并提供了与它们合并的所有容器的优点。
- Boost.Bimap 基于 Boost.MultiIndex。它提供了一个类似于 std::unordered_map 的容器，不同之处在于可以从两侧查找元素。因此，根据访问容器的方式，任何一方都可能是关键。当一侧是关键时，另一侧是价值。
- Boost.Array 和 Boost.Unordered 定义了类 boost::array、boost::unordered_set 和 boost::unordered_map，它们是使用 C++11 添加到标准库中的。
- Boost.CircularBuffer 提供了一个容器，其最重要的属性是当一个值被添加到一个完整的循环缓冲区时，它将覆盖缓冲区中的第一个元素。
- Boost.Heap 提供了优先级队列的变体——类似于 std::priority_queue 的类。
- Boost.Intrusive 允许您创建与标准库中的容器不同的容器，这些容器既不复制也不移动对象。但是，要将对象添加到侵入性列表中，对象的类型必须满足某些要求。
- Boost.MultiArray 试图简化多维数组的使用。例如，可以将多维数组的一部分视为单独的数组。
- Boost.Container 是一个库，它定义了与标准库相同的容器。例如，如果您需要在多个平台上支持一个程序，并且您希望避免由标准库中特定于实现的差异引起的问题，则使用 Boost.Container 是有意义的。
二、Boost.MultiIndex
Boost.MultiIndex 使得定义支持任意数量接口的容器成为可能。虽然 std::vector 提供了一个支持直接访问具有索引的元素的接口，而 std::set 提供了一个对元素进行排序的接口，但 Boost.MultiIndex 允许您定义支持这两个接口的容器。这样的容器可用于使用索引并以排序方式访问元素。
如果元素需要以不同的方式访问并且通常需要存储在多个容器中，则可以使用 Boost.MultiIndex。不必将元素同时存储在向量和集合中，然后连续同步容器，您可以使用 Boost.MultiIndex 定义一个容器，该容器提供向量接口和集合接口。
如果您需要访问基于多个不同属性的元素，Boost.MultiIndex 也很有意义。在示例 12.1 中，通过名称和腿数查找动物。如果没有 Boost.MultiIndex，则需要两个散列容器——一个按名称查找动物，另一个按腿数查找它们。
示例 12.1。使用 boost::multi_index::multi_index_container
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <string>
#include <iostream>
using namespace boost::multi_index;
struct animal
{
std::string name;
int legs;
};
typedef multi_index_container<
animal,
indexed_by<
hashed_non_unique<
member<
animal, std::string, &animal::name
>
>,
hashed_non_unique<
member<
animal, int, &animal::legs
>
>
>
> animal_multi;
int main()
{
animal_multi animals;
animals.insert({"cat", 4});
animals.insert({"shark", 0});
animals.insert({"spider", 8});
std::cout << animals.count("cat") << '\n';
const animal_multi::nth_index<1>::type &legs_index = animals.get<1>();
std::cout << legs_index.count(8) << '\n';
} 使用 Boost.MultiIndex 时，第一步是定义一个新容器。你必须决定你的新容器应该支持哪些接口以及它应该访问哪些元素属性。 在 boost/multi_index_container.hpp 中定义的类 boost::multi_index::multi_index_container 用于每个容器定义。这是一个至少需要两个参数的类模板。第一个参数是容器应存储的元素类型——在示例 12.1 中，这是一个名为动物的用户定义类。第二个参数用于表示容器应提供的不同索引。 基于 Boost.MultiIndex 的容器的主要优势在于您可以通过不同的接口访问元素。定义新容器时，可以指定接口的数量和类型。示例 12.1 中的容器需要支持按名称或腿数搜索动物，因此定义了两个接口。 Boost.MultiIndex 调用这些接口索引——这就是库名称的来源。
接口是在类 boost::multi_index::indexed_by 的帮助下定义的。每个接口都作为模板参数传递。示例 12.1 中使用了 boost::multi_index::hashed_non_unique 类型的两个接口，在 boost/multi_index/hashed_index.hpp 中定义。使用这些接口使容器的行为类似于 std::unordered_set 并使用哈希值查找值。
类 boost::multi_index::hashed_non_unique 也是一个模板，它的唯一参数是计算哈希值的类。因为容器的两个接口都需要查找动物，一个接口计算名称的哈希值，而另一个接口计算腿数。
Boost.MultiIndex 提供了在 boost/multi_index/member.hpp 中定义的帮助类模板 boost::multi_index::member 来访问成员变量。如示例 12.1 所示，已指定几个参数以让 boost::multi_index::member 知道应该访问动物的哪个成员变量以及成员变量的类型。
尽管animal_multi 的定义起初看起来很复杂，但该类的工作方式就像一张地图。动物的名字和腿数可以看作是一个键/值对。容器animal_multi 优于std::unordered_map 之类的地图的优点是可以通过名称或腿数查找动物。 animal_multi 支持两种接口，一种基于名称，一种基于腿数。接口确定哪个成员变量是键，哪个成员变量是值。
要访问 MultiIndex 容器，您需要选择一个接口。如果您使用 insert() 或 count() 直接访问对象动物，则使用第一个接口。在示例 12.1 中，这是成员变量名称的哈希容器。如果您需要不同的界面，则必须明确选择它。
接口连续编号，从第一个接口的索引 0 开始。要访问第二个接口（如示例 12.1 所示），请调用成员函数 get() 并将所需接口的索引作为模板参数传入。
get() 的返回值看起来很复杂。它访问一个名为 nth_index 的 MultiIndex 容器类，它又是一个模板。要使用的接口的索引必须指定为模板参数。该索引必须与传递给 get() 的索引相同。最后一步是访问名为 type of nth_index 的类型定义。 type 的值表示对应接口的类型。以下示例使用关键字 auto 来简化代码。
尽管您不需要知道接口的细节，因为它们是自动从 nth_index 和 type 派生的，您仍然应该了解访问的是哪种接口。由于接口在容器定义中是连续编号的，因此可以很容易地回答这个问题，因为索引同时传递给 get() 和 nth_index。因此，legs_index 是一个通过腿查找动物的哈希接口。
因为名字、腿等数据可以作为MultiIndex容器的key，所以不能随意改变。如果在通过名称查找动物后腿的数量发生了变化，则使用腿作为键的接口将不知道这种变化，也不知道需要计算新的哈希值。
就像 std::unordered_map 类型的容器中的键无法修改一样，存储在 MultiIndex 容器中的数据也无法修改。严格来说，存储在 MultiIndex 容器中的所有数据都是常量。这包括不被任何接口使用的成员变量。即使没有接口访问腿，腿也不能改变。
为了避免必须从 MultiIndex 容器中删除元素并插入新元素，Boost.MultiIndex 提供了成员函数来直接更改值。因为这些成员函数是在MultiIndex容器本身上操作的，并且因为容器中的元素没有被直接修改，所以所有的接口都会得到通知，可以计算出新的hash值。
示例 12.2。使用 modify() 更改 MultiIndex 容器中的元素
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <string>
#include <iostream>
using namespace boost::multi_index;
struct animal
{
std::string name;
int legs;
};
typedef multi_index_container<
animal,
indexed_by<
hashed_non_unique<
member<
animal, std::string, &animal::name
>
>,
hashed_non_unique<
member<
animal, int, &animal::legs
>
>
>
> animal_multi;
int main()
{
animal_multi animals;
animals.insert({"cat", 4});
animals.insert({"shark", 0});
animals.insert({"spider", 8});
auto &legs_index = animals.get<1>();
auto it = legs_index.find(4);
legs_index.modify(it, [](animal &a){ a.name = "dog"; });
std::cout << animals.count("dog") << '\n';
}Boost.MultiIndex 提供的每个接口都提供了成员函数 modify()，它直接在容器上运行。要修改的对象是通过作为第一个参数传递给 modify() 的迭代器来标识的。第二个参数是一个函数或函数对象，它的唯一参数是存储在容器中的类型的对象。函数或函数对象可以随心所欲地改变元素。示例 12.2 说明了如何使用成员函数 modify() 来更改元素。
到目前为止，只引入了一个接口：boost::multi_index::hashed_non_unique，它计算一个不必唯一的哈希值。为了保证没有值被存储两次，请使用 boost::multi_index::hashed_unique。请注意，如果值不满足特定容器的所有接口的要求，则无法存储值。如果一个接口不允许您多次存储值，那么另一个接口是否允许它并不重要。
示例 12.3。具有 boost::multi_index::hashed_unique 的 MultiIndex 容器
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <string>
#include <iostream>
using namespace boost::multi_index;
struct animal
{
std::string name;
int legs;
};
typedef multi_index_container<
animal,
indexed_by<
hashed_non_unique<
member<
animal, std::string, &animal::name
>
>,
hashed_unique<
member<
animal, int, &animal::legs
>
>
>
> animal_multi;
int main()
{
animal_multi animals;
animals.insert({"cat", 4});
animals.insert({"shark", 0});
animals.insert({"dog", 4});
auto &legs_index = animals.get<1>();
std::cout << legs_index.count(4) << '\n';
}示例 12.3 中的容器使用 boost::multi_index::hashed_unique 作为第二个接口。这意味着不能将两条腿数相同的动物存储在容器中，因为哈希值相同。
该示例尝试存储与已存储的猫具有相同腿数的狗。因为这违反了第二个接口具有唯一哈希值的要求，所以狗不会被存储在容器中。因此，当搜索有四只腿的动物时，程序会显示 1，因为只有猫被存储和计数。
示例 12.4。接口排序、ordered_non_unique 和 random_access
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/member.hpp>
#include <string>
#include <iostream>
using namespace boost::multi_index;
struct animal
{
std::string name;
int legs;
};
typedef multi_index_container<
animal,
indexed_by<
sequenced<>,
ordered_non_unique<
member<
animal, int, &animal::legs
>
>,
random_access<>
>
> animal_multi;
int main()
{
animal_multi animals;
animals.push_back({"cat", 4});
animals.push_back({"shark", 0});
animals.push_back({"spider", 8});
auto &legs_index = animals.get<1>();
auto it = legs_index.lower_bound(4);
auto end = legs_index.upper_bound(8);
for (; it != end; ++it)
std::cout << it->name << '\n';
const auto &rand_index = animals.get<2>();
std::cout << rand_index[0].name << '\n';
}示例 12.3 中的容器使用 boost：
example2.4 介绍了 Boost.MultiIndex 的最后三个接口：boost::multi_index::sequenced、boost::multi_index::ordered_non_unique 和 boost::multi_index::random_access。
接口 boost::multi_index::sequenced 允许您将 MultiIndex 容器视为类型为 std::list 的列表。元素按给定的顺序存储。
使用 boost::multi_index::ordered_non_unique 接口，对象会自动排序。此接口要求您在定义容器时指定排序标准。示例 12.4 使用辅助类 boost::multi_index::member 按腿数对动物类型的对象进行排序。
boost::multi_index::ordered_non_unique 提供了特殊的成员函数来查找排序值中的特定范围。程序使用lower_bound() 和upper_bound() 搜索至少有4 条但不超过8 条腿的动物。因为它们需要对元素进行排序，所以其他接口不提供这些成员函数。
最后引入的接口是 boost::multi_index::random_access，它允许您将 MultiIndex 容器视为 std::vector 类型的向量。两个最突出的成员函数是 operator[] 和 at()。
boost::multi_index::random_access 包括 boost::multi_index::sequenced。使用 boost::multi_index::random_access，boost::multi_index::sequenced 的所有成员函数也都可用。
现在我们已经介绍了 Boost.MultiIndex 的四个接口，本章的其余部分将重点介绍键提取器。已经引入了一个关键提取器：boost::multi_index::member，它在 boost/multi_index/member.hpp 中定义。这个帮助类被称为键提取器，因为它允许您指定类的哪个成员变量应该用作接口的键。
示例 12.5 引入了另外两个密钥提取器。
示例 12.5。密钥提取器身份和 const_mem_fun
:multi_index::hashed_unique 作为第二个接口。这意味着不能将两条腿数相同的动物存储在容器中，因为哈希值相同。
该示例尝试存储与已存储的猫具有相同腿数的狗。因为这违反了第二个接口具有唯一哈希值的要求，所以狗不会被存储在容器中。因此，当搜索有四只腿的动物时，程序会显示 1，因为只有猫被存储和计数。
示例 12.4。接口排序、ordered_non_unique 和 random_access
#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/mem_fun.hpp>
#include <string>
#include <utility>
#include <iostream>
using namespace boost::multi_index;
class animal
{
public:
animal(std::string name, int legs) : name_{std::move(name)},
legs_(legs) {}
bool operator<(const animal &a) const { return legs_ < a.legs_; }
const std::string &name() const { return name_; }
private:
std::string name_;
int legs_;
};
typedef multi_index_container<
animal,
indexed_by<
ordered_unique<
identity<animal>
>,
hashed_unique<
const_mem_fun<
animal, const std::string&, &animal::name
>
>
>
> animal_multi;
int main()
{
animal_multi animals;
animals.emplace("cat", 4);
animals.emplace("shark", 0);
animals.emplace("spider", 8);
std::cout << animals.begin()->name() << '\n';
const auto &name_index = animals.get<1>();
std::cout << name_index.count("shark") << '\n';
}在 boost/multi_index/identity.hpp 中定义的键提取器 boost::multi_index::identity 使用存储在容器中的元素作为键。这要求动物类是可排序的，因为动物类型的对象将用作接口 boost::multi_index::ordered_unique 的键。在示例 12.5 中，这是通过重载的 operator< 实现的。
头文件 boost/multi_index/mem_fun.hpp 定义了两个键提取器——boost::multi_index::const_mem_fun 和 boost::multi_index::mem_fun——它们使用成员函数的返回值作为键。在示例 12.5 中，name() 的返回值就是以这种方式使用的。 boost::multi_index::const_mem_fun 用于常量成员函数，而 boost::multi_index::mem_fun 用于非常量成员函数。
Boost.MultiIndex 提供了另外两个键提取器：boost::multi_index::global_fun 和 boost::multi_index::composite_key。前者可用于独立或静态成员函数，后者允许您设计一个由其他几个密钥提取器组成的密钥提取器。
练习
使用 Boost.MultiIndex 定义类animals_container：
#include <string>
#include <vector>
#include <iostream>
struct animal
{
std::string name;
int legs;
bool has_tail;
};
class animals_container
{
public:
void add(animal a)
{
// TODO: Implement this member function.
}
const animal *find_by_name(const std::string &name) const
{
// TODO: Implement this member function.
return nullptr;
}
std::vector<animal> find_by_legs(int from, int to) const
{
// TODO: Implement this member function.
return {};
}
std::vector<animal> find_by_tail(bool has_tail) const
{
// TODO: Implement this member function.
return {};
}
};
int main()
{
animals_container animals;
animals.add({ "cat", 4, true });
animals.add({ "ant", 6, false });
animals.add({ "spider", 8, false });
animals.add({ "shark", 0, false });
const animal *a = animals.find_by_name("cat");
if (a)
std::cout << "cat has " << a->legs << " legs\n";
auto animals_with_6_to_8_legs = animals.find_by_legs(6, 9);
for (auto a : animals_with_6_to_8_legs)
std::cout << a.name << " has " << a.legs << " legs\n";
auto animals_without_tail = animals.find_by_tail(false);
for (auto a : animals_without_tail)
std::cout << a.name << " has no tail\n";
}加载全部内容