boost multi index多索引容器

复制源：https://www.cnblogs.com/sssblog/p/11004572.html(纯英文）

注意：本文是机翻

Boost.MultiIndex makes it possible to define containers that support an arbitrary number of interfaces. While std::vector provides an interface that supports direct access to elements with an index and std::set provides an interface that sorts elements. Boost.MultiIndex lets you definde containers that support both interfaces. Such a container could be used to access elements using an index and in a sorted fashion.

Boost。MultiIndex使得定义支持任意数量接口的容器成为可能。std::vector提供了一个支持直接访问带有索引的元素的接口，std::set提供了一个对元素进行排序的接口。Boost。MultiIndex允许您定义支持这两个接口的容器。这样的容器可用于使用索引并以排序方式访问元素。

1.

#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") << std::endl;
  
  const animal_multi::nth_index<1>::type& legs_index = animals.get<1>();
  std::cout << legs_index.count(8) << std::endl;
  return 0;
}

When you use Boost.MultiIndex, the first step is to define a new container. You have to decide which interfaces your new container should support and which element properties it should access.

当你使用Boost。MultiIndex，第一步是定义一个新的容器。您必须决定新容器应该支持哪些接口，以及它应该访问哪些元素属性。

multi_index_container is a class template that requires at least two parameters. The first parameter is the type of elements the container should store. The second parameter is used to denote different indexes the container should provide.

Multi_index_container是一个类模板，它至少需要两个参数。第一个参数是容器应该存储的元素类型。第二个参数用于表示容器应该提供的不同索引。

The key advantage of containers based on Boost.MultiIndex is that you can access elements via different interfaces. When you define a new container, you can specify the number and type of interfaces.

基于Boost的容器的主要优势。MultiIndex就是可以通过不同的接口访问元素。在定义新容器时，可以指定接口的数量和类型。

The advantage of the container animal_multi over a map like std::unordered_map is that animals can be looked up by name or by number of legs. animal_multi supports two interfaces, one based on the name and one based on the number of legs.

容器animal_multi相对于std::unordered_map这样的映射的优点是，可以通过名称或腿的数量来查找动物。Animal_multi支持两个接口，一个基于名称，另一个基于腿的数量。

The interface determines which member variable is the key and which member variable is the value. Because data such as names and legs can be keys of the MultiIndex container, the cannot be arbitrarily changed.

接口确定哪个成员变量是键，哪个成员变量是值。因为名字和腿之类的数据可以是MultiIndex容器的键，所以不能随意更改。

If the number of legs is changed after an animal hase been looked up by name, an interface using legs as a key would be unaware of the change and would not know that a new hash value needs to be calculted.

如果在按名称查找动物之后，腿的数量发生了变化，那么使用腿作为键的接口将不知道这种变化，也不知道需要计算新的哈希值。

2. boost::multi_index::hashed_unique

#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) << std::endl;
  return 0;
}

输出：1

hashed_non_unique which calculates a hash value that does not have to be unique. In order to guarantee that no value is stored twice, use boost::multi_index::hashed_unique.

hashhed_non_unique计算一个不必唯一的哈希值。为了保证没有值被存储两次，使用boost::multi_index:: hashhed_unique。

If one interface does not allow you to store values multiple times, it does not matter whether another interface does allow it. The example tries to store a dog, which has the same number of legs as the already stored cat.

如果一个接口不允许多次存储值，那么另一个接口是否允许也无关紧要。这个例子试图存储一只狗，它和已经存储的猫有相同数量的腿。

Because this violates the requirement of having unique hash values for the second interface, the dog will not be stored in the container. Therefore, when searching for animals with four legs, the program displays 1, because only the cat was stored and counted.

因为这违反了对第二个接口具有唯一哈希值的要求，所以狗不会存储在容器中。因此，当搜索四条腿的动物时，程序显示1，因为只存储和计数了猫。

3. The interfaces sequenced, ordered_noe_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.insert({"cat", 4});
  animals.insert({"shark", 0});
  animals.insert({"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 << std::endl;
  }
  
  const auto& rand_index = animals.get<2>();
  std::cout << rand_index[0].name << std::endl;
  return 0;
}

The interface boost::multi_index::sequenced allows you to treat a MultiIndex container like a list of type std::list. Elements are stored in the given order.

接口boost::multi_index::sequence允许您像对待std::list类型的列表一样对待MultiIndex容器。元素按照给定的顺序存储。

With the interface boost::multi_index::ordered_non_unique, objects are automatically sorted. This interface requires that you specify a sorting criterion when defining the container. ordered_non_unique provides special member functions to find specific ranges within the sorted values. Using lower_bound() and upper_bound(), the program searches for animals that have at lease four and no more than eight legs.

boost::multi_index::ordered_non_unique接口，对象将自动排序。此接口要求您在定义容器时指定排序条件。Ordered_non_unique提供了特殊的成员函数来查找排序值中的特定范围。使用lower_bound()和upper_bound()，程序搜索至少有四条腿但不超过八条腿的动物。

boost::multi_index::random_access allows you to treat the MultiIndex container like a vector of type std::vector. The two most prominent member functions are operator[] and at().

boost::multi_index::random_access允许您将MultiIndex容器视为std::vector类型的vector。两个最突出的成员函数是operator[]和at()。

4. The key extractors identity and const_mem_fun

#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() << std::endl;

  const auto& name_index = animals.get<1>();
  std::cout << name_index.count("shark") << std::enl;
  return 0;
}

boost::multi_index::identity uses elements stored in the container as keys. This requires the class animal to be sortable because objects of type animal will be used as the key for the interface boost::multi_index::ordered_unique.

Boost::multi_index::identity使用存储在容器中的元素作为键。这要求类animal是可排序的，因为动物类型的对象将用作接口boost::multi_index::ordered_unique的键。

This is achieved through the overloaded operator<boost::multi_index::const_mem_fun and boost::multi_index::mem_fun that use the return value of a member function as a key.

这是通过重载操作符<boost::multi_index::const_mem_fun和boost::multi_index::mem_fun实现的，它们使用成员函数的返回值作为键。