Boost C++ 库

...世界上最受推崇和设计最精湛的 C++ 库项目之一。 — Herb Sutter 和 Andrei Alexandrescu, C++ 编码标准

Boost.MultiIndex 教程：索引类型

basics
基础
Boost.MultiIndex tutorial
Boost.MultiIndex 教程
key estraction
键提取

目录

分类

Boost.MultiIndex 提供了八种不同的索引类型，如下表所示进行分类。 有序 和 序列索引是最常用的，已经在基础部分解释过了；其余的索引类型可以看作是前者的变体，在功能或性能方面提供一些额外的优势。

Boost.MultiIndex 索引。
类型 说明符
  基于键     有序     ordered_unique  
  ordered_non_unique  
  ranked_unique  
  ranked_non_unique  
  哈希     hashed_unique  
  hashed_non_unique  
  非基于键     序列  
  随机访问  

基于键的索引，其中有序索引是常见的例子，它基于某些被称为元素键的信息提供元素的有效查找：有一整套 键提取 实用工具类，允许指定此类键。快速查找对这些索引施加了内部管理的顺序，用户不允许修改；另一方面，非基于键的索引可以自由重排，但代价是缺乏查找功能。 序列索引，以 std::list 的接口为模型，是非基于键索引的通常示例。

排名索引

假设我们有一个数字的 std::multiset，我们想输出高于 75% 百分位数 的值

typedef std::multiset<int> int_multiset;

void output_above_75th_percentile(const int_multiset& s)
{
  int_multiset::const_iterator it=s.begin();
  std::advance(it,s.size()*3/4); // linear on s.size();

  std::copy(it,s.end(),std::ostream_iterator<int>(std::cout,"\n"));
}

此代码的问题在于，获取所需子序列的开头涉及容器的线性遍历。排名索引提供了更快地执行此操作的机制

typedef multi_index_container<
  int,
  indexed_by<
    ranked_non_unique<identity<int> >
  >
> int_multiset;

void output_above_75th_percentile(const int_multiset& s)
{
  int_multiset::const_iterator it=s.nth(s.size()*3/4); // logarithmic
  std::copy(it,s.end(),std::ostream_iterator<int>(std::cout,"\n"));
}

nth(n) 返回一个指向元素的迭代器，该元素的排名，即它与索引开头的距离为 n，并且在对数时间内有效地执行此操作。相反，rank(it) 在对数时间内计算由 it 指向的元素的排名，如果 it==end()，则计算 size()。

int_multiset::iterator  it=s.insert(10).first;
int_multiset::size_type r=s.rank(it); // rank of 10;

排名索引提供与有序索引相同的接口，外加几个与排名相关的操作。此额外功能的代价是内存消耗更高，这是因为一些内部的额外数据（每个元素一个字），并且在插入和删除时的执行时间稍长——特别是，删除元素所需的时间与 log(n) 成正比，其中 n 是索引中的元素数量，而对于有序索引，此时间是恒定的。 参考 详细描述了这些索引。

规范

排名索引的规范与 有序索引 完全相同，只不过使用的是 ranked_unique 和 ranked_non_unique。

(ranked_unique | ranked_non_unique)
  <[(tag)[,(key extractor)[,(comparison predicate)]]]>

(ranked_unique | ranked_non_unique)
  <[(key extractor)[,(comparison predicate)]]>

排名操作

除了 nth 和 rank 之外，排名索引还提供成员函数

它们的行为与其正常的 查找 和 范围检索 对应项（find、lower_bound 等）相同，但返回的是排名而不是迭代器。

void percentile(int n,const int_multiset& s)
{
  std::cout<<n<<" lies in the "<<
    s.upper_bound_rank(n)*100.0/s.size()<<" percentile\n";
}

您可能会认为 upper_bound_rank(n) 只是 rank(upper_bound(n)) 的简写：但实际上，您应该更喜欢直接使用 *_rank 操作，因为它们比替代的公式运行得更快。

哈希索引

哈希索引构成了对有序索引的权衡：如果使用正确，它们可以提供更快的元素查找，但代价是丢失了排序信息。 让我们重新审视我们的 employee_set 示例：假设添加了一个用于存储社会安全号码的字段，并且要求按此号码进行查找的速度尽可能快。 可以使用哈希索引而不是通常的有序索引

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/member.hpp>

struct employee
{
  int         id;
  std::string name;
  int         ssnumber;

  employee(int id,const std::string& name,int ssnumber):
    id(id),name(name),ssnumber(ssnumber){}

  bool operator<(const employee& e)const{return id<e.id;}
};

typedef multi_index_container<
  employee,
  indexed_by<
    // sort by employee::operator<
    ordered_unique<identity<employee> >,
    
    // sort by less<string> on name
    ordered_non_unique<member<employee,std::string,&employee::name> >,
    
    // hashed on ssnumber
    hashed_unique<member<employee,int,&employee::ssnumber> >
  >
> employee_set

请注意，哈希索引不保证元素的任何特定顺序：例如，我们无法有效地查询 SSN 大于给定数字的员工。 通常，在确定是否优先选择哈希索引而不是有序索引时，必须考虑这些限制。

哈希索引复制了 std::unordered_set 和 std::unordered_multiset 的接口，只有在 multi_index_container 的一般约束要求时才会有细微的差异，并提供额外的有用功能，如元素的就地更新。 有关哈希索引接口的完整规范，请查看 参考 和 示例 8 和 示例 9 的实际应用。

唯一和非唯一变体

与有序索引一样，哈希索引具有唯一和非唯一变体，分别使用说明符 hashed_unique 和 hashed_non_unique 选择。 在后一种情况下，具有等效键的元素将保持在一起，并且可以通过 equal_range 成员函数共同检索。

规范

哈希索引说明符有两种替代语法，具体取决于是否提供了 标签

(hashed_unique | hashed_non_unique)
  <[(tag)[,(key extractor)[,(hash function)[,(equality predicate)]]]]>

(hashed_unique | hashed_non_unique)
  <[(key extractor)[,(hash function)[,(equality predicate)]]]>

键提取器参数的工作方式与 有序索引 完全相同； 查找、插入等基于提取器返回的键而不是整个元素。

哈希函数是这种类型的索引快速查找功能的核心：哈希器只是一个一元函数对象，对于任何给定的键返回一个 std::size_t 值。 一般来说，不可能将每个键都映射到不同的哈希值，因为键的空间可能大于允许的哈希代码的数量：好的哈希器使得冲突的概率（两个具有相同哈希值的不同键）尽可能接近于零。这是一个统计属性，具体取决于给定应用程序中键的典型分布，因此不可能有一个在每个可能场景中都具有出色结果的通用哈希函数； 此参数的默认值使用 Boost.Hash，它通常提供足够好的结果。

相等谓词用于确定是否将两个键视为相同。 默认值 std::equal_to<KeyFromValue::result_type> 在大多数情况下正是所需要的，因此您很少需要提供自己的谓词。 请注意，哈希索引要求两个等效键具有相同的哈希值，这实际上大大减少了选择相等谓词的自由度。

查找

哈希索引的查找接口由成员函数 find、count、contains 和 equal_range 组成。 请注意，不提供 lower_bound 和 upper_bound，因为这种类型的索引中没有键的内在顺序。

与有序索引一样，这些成员函数将键作为其搜索参数，而不是整个对象。 请记住，有序索引查找操作进一步增强为接受兼容键，这大致可以看作是“子键”。 对于哈希索引，也支持 兼容键 的概念，尽管它的用处非常有限：基本上，兼容键是一个与 key_type 值的本机对象完全等效的对象，尽管可能具有不同的内部表示

// US SSN numbering scheme
struct ssn
{
  ssn(int area_no,int group_no,int serial_no):
    area_no(area_no),group_no(group_no),serial_no(serial_no)
  {}

  int to_int()const
  {
    return serial_no+10000*group_no+1000000*area_no;
  }

private:
  int area_no;
  int group_no;
  int serial_no;
};

// interoperability with SSNs in raw int form

struct ssn_equal
{
  bool operator()(const ssn& x,int y)const
  {
    return x.to_int()==y;
  }

  bool operator()(int x,const ssn& y)const
  {
    return x==y.to_int();
  }
};

struct ssn_hash
{
  std::size_t operator()(const ssn& x)const
  {
    return boost::hash<int>()(x.to_int());
  }

  std::size_t operator()(int x)const
  {
    return boost::hash<int>()(x);
  }
};

typedef employee_set::nth_index<2>::type employee_set_by_ssn;

employee_set         es;
employee_set_by_ssn& ssn_index=es.get<2>();
...
// find an employee by ssn
employee e=*(ssn_index.find(ssn(12,1005,20678),ssn_hash(),ssn_equal()));

在该示例中，我们提供了一个哈希仿函数 ssn_hash 和一个相等谓词 ssn_equal，允许 ssn 对象与存储为 employee_set 中的 SSN 的原始 int 之间互操作。

到目前为止，在哈希索引的上下文中，兼容键最有用的应用在于它们允许无缝使用 复合键。

更新

哈希索引具有 replace、modify 和 modify_key 成员函数，其功能与有序索引相同。

关于迭代器有效性和异常安全性的保证

由于 Boost.MultiIndex 框架施加的内部约束，哈希索引在迭代器有效性和异常安全性方面提供的保证实际上比 C++ 标准对无序关联容器的要求更强

一般来说，这些更强的保证对用户的便利性有利，特别是那些涉及迭代器稳定性的保证。 然而，为了换取这些便利，可能会导致（希望最小的）性能下降。

随机访问索引

随机访问索引提供与 序列索引 相同的功能，其额外的优点是它们的迭代器是随机访问的，并且提供了 operator[] 和 at() 用于基于它们在索引中的位置访问元素。 让我们使用随机访问而不是序列索引来重写先前 示例 中使用的容器

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/identity.hpp>

// text container with fast lookup based on a random access index
typedef multi_index_container<
  std::string,
  indexed_by<
    random_access<>,
    ordered_non_unique<identity<std::string> >
  >
> text_container;

// global text container object
text_container tc;

随机访问功能允许我们有效地编写如下代码

void print_page(std::size_t page_num)
{
  static const std::size_t words_per_page=50;

  std::size_t pos0=std::min(tc.size(),page_num*words_per_page);
  std::size_t pos1=std::min(tc.size(),pos0+words_per_page);

  // note random access iterators can be added offsets 
  std::copy(
    tc.begin()+pos0,tc.begin()+pos1,
    std::ostream_iterator<std::string>(std::cout));
}

void print_random_word()
{
  std::cout<<tc[rand()%tc.size()];
}

这种额外的灵活性是有代价的：在索引末尾以外的位置插入和删除具有线性复杂度，而对于序列索引，这些操作是恒定时间的。 这种情况让人想起 std::list 和 std::vector 之间复杂度行为的差异：但是，在随机访问索引的情况下，插入和删除永远不会产生任何元素复制，因此尽管与序列索引相比存在理论上的缺点，但这些操作的实际性能是可以接受的。

在示例部分的示例 10 和 示例 11 中，展示了随机访问索引的实际应用。

规范

随机访问索引使用 random_access 构造指定，其中 标签 参数和往常一样是可选的。

random_access<[(tag)]>

接口

序列索引提供的所有公共函数，随机访问索引也同样提供，因此后者可以作为前者的直接替代（除了上面解释的复杂度边界之外）。此外，随机访问索引还具有 operator[] 和 at()，用于按位置访问元素，以及成员函数 capacity 和 reserve，它们以类似于 std::vector 中同名功能的方式控制内部重新分配。请查看 参考文档 获取详细信息。

与 std::vector 的比较

人们很容易将随机访问索引视为 Boost.MultiIndex 中使用的 std::vector 的类似物，但这种比喻可能会产生误导，因为这两种构造虽然在许多方面相似，但在语义上却存在重要差异。随机访问索引的一个优点是它们的迭代器以及对其元素的引用是稳定的，也就是说，在任何插入或删除操作后它们仍然有效。另一方面，随机访问索引相对于 std::vector 有几个缺点。

后一个缺点可以通过这些索引提供的重新排列接口部分地补救。

总的来说，将随机访问索引视为序列索引的变体，提供随机访问语义，而不是坚持 std::vector 的类比，更有启发意义。

索引重排

按照设计，索引元素是不可变的，即迭代器只允许对它们进行 const 访问，并且只能通过提供的更新接口（replace、modify 和 modify_key）修改元素。设置此限制是为了不破坏基于键的索引的内部不变量（例如，有序索引中的升序遍历），但在非基于键的索引中会产生重要的限制。

typedef multi_index_container<
  int,
  indexed_by<
    random_access<>,
    ordered_unique<identity<int> >
  >
> container;	

container    c;
std::mt19937 rng;
...
// compiler error: assignment to read-only objects
std::shuffle(c.begin(),c.end(),rng);

前面示例中不幸的是，std::shuffle 执行的操作可能与 multi_index_container 的不变量兼容，因为它的结果可以通过随机访问索引中元素的排列来描述，而无需实际修改元素本身。C++ 标准库中还有许多这样的兼容算法的示例，例如所有排序和分区函数。

序列索引和随机访问索引提供了一种利用此类外部算法的方法。为了引入此功能，我们需要一个初步概念：索引的视图被定义为索引元素上的某个迭代器范围 [first,last)，使得其所有元素都恰好包含在该范围内一次。继续我们的示例，我们可以在从容器获得的临时视图上应用 std::shuffle。

// note that the elements of the view are not copies of the elements
// in c, but references to them
std::vector<boost::reference_wrapper<const int> > v;
BOOST_FOREACH(const int& i,c)v.push_back(boost::cref(i));

// this compiles OK, as reference_wrappers are swappable
std::shuffle(v.begin(),v.end(),rng);

v 的元素是多索引容器中实际元素的 reference_wrapper（来自 Boost.Ref）。这些对象仍然不允许修改被引用的实体，但它们是可交换的，这是 std::shuffle 唯一的要求。一旦我们将所需的重新排列存储在视图中，我们就可以将其传递给容器，使用：

c.rearrange(v.begin());

rearrange 接受一个输入迭代器，表示外部视图的开始（并且不需要结束迭代器，因为视图的长度与索引的长度相同），并在内部重新定位索引的元素，使其遍历顺序与视图匹配。尽管有一些规避方法，rearrange 允许将各种算法应用于非基于键的索引。请注意，视图概念非常通用，与上面显示的特定实现示例没有任何关系。例如，multi_index_container 的索引实际上是其非基于键的索引的视图。

// rearrange as index #1 (ascending order)
c.rearrange(c.get<1>().begin());

// rearrange in descending order
c.rearrange(c.get<1>().rbegin());

对视图的唯一重要要求是它们必须是自由的，即它们不受基础索引重新定位的影响：因此，rearrange 不接受以下情况：

// undefined behavior: [rbegin(),rend()) is not free with respect
// to the base index
c.rearrange(c.rbegin());

视图概念在 参考文档 中详细定义。请参阅示例部分中的 示例 11 以演示 rearrange 的用法。

iterator_to

Boost.MultiIndex 的所有索引都提供一个名为 iterator_to 的成员函数，该函数返回指向容器给定元素的迭代器。

multi_index_container<
  int,
  indexed_by<sequenced<> >
> c;
...
// convoluted way to do c.pop_back()
c.erase(c.iterator_to(c.back())); 

// The following, though similar to the previous code,
// does not work: iterator_to accepts a reference to
// the element in the container, not a copy.
int x=c.back();
c.erase(c.iterator_to(x)); // run-time failure ensues

iterator_to 提供了一种从指向元素的指针检索元素迭代器的方法，从而在许多情况下使迭代器和指针在元素指向的目的上可以互换（遍历则不行）。尽管如此，iterator_to 的目的不是提倡将指针用作真实迭代器的替代品：后者是专门为处理容器的元素而设计的，不仅受益于容器接口的迭代器方向，而且还能够在编译和运行时暴露出比原始指针更多的编程错误。因此，iterator_to 旨在用于不适合或不希望通过迭代器访问的场景。

节点处理操作

使用直接节点操作，元素可以在 multi_index_container 之间传递，而无需实际复制它们。

// move an employee to the retiree archive
void move_to_retirement(int ssnumber,employee_set& es,employee_set& archive)
{
  // assume employee_set has an index on SS number(not shown before)
  // extract the employee with given SS number to a node handle
  employee_set_by_ssn::node_type node=es.get<ssn>().extract(ssnumber);

  if(!node.empty()){ // employee found
    // re-insert into archive (note the use of std::move)
    archive.insert(std::move(node));
  }
}

在示例中，内部节点按原样从 es 传输到 archive，这比从源中擦除并在目标中重新创建更有效。node_type 是一个仅移动的类，用于传递节点，其接口遵循 C++ 关联容器（集合容器版本）的 同名类型 的接口。Boost.MultiIndex 为所有索引类型（包括序列索引）提供节点提取和插入操作（相比之下，std::list 没有此类功能）。

multi_index_container<
  int,
  indexed_by<
    sequenced<>,
    ordered_unique<identity<int> >
  >
> src;

multi_index_container<
  int,
  indexed_by<
    sequenced<>,
    ordered_non_unique<identity<int>, std::greater<int> >
  >
> dst;

...

// transfer even numbers from src to dst
for(auto first=src.begin(),last=src.end();first!=last;){
  if(*first%2==0) dst.insert(dst.end(),src.extract(first++));
  else            ++first;
}

请注意，src 和 dst 是不同的类型，但传输是可能的。如果两个 multi_index_container 具有相同的元素和分配器类型，并且它们的各自索引一一匹配，而不考虑它们是唯一的还是非唯一的，或者它们的特定配置参数（它们都是有序的，或者都是序列的，等等），则它们是节点兼容的（即，它们使用相同的 node_type）。

或者，可以使用 merge（基于键的索引）和 splice（非基于键的索引）在两个容器之间进行直接节点传输，而无需保留中间的 node_type。

// move older employees to retirement
void move_to_retirement_by_age(
  int max_age,employee_set& es,employee_set& archive)
{
  // assume employee_set has an index on age (not shown before)
  employee_set_by_age& ea=es.get<age>();

  // archive employees with age>max_age
  archive.merge(ea,ea.upper_bound(max_age),ea.end());
}

...

// transfer even numbers from src to dst
for(auto first=src.begin(),last=src.end();first!=last;){
  if(*first%2==0) dst.splice(dst.end(),src,first++);
  else            ++first;
}

有用于传输单个元素、两个迭代器之间的范围和整个容器的 merge/splice 的重载：有关更多详细信息，请参阅例如 有序索引 和 序列索引 的参考文档（其余索引提供一个或另一个接口）。请注意，序列索引和随机访问索引也都有一个名为 merge 的操作，但它遵循 std::list::merge 的规范，后者具有略有不同的行为（要求源和目标按相同的标准排序）。这是一个相当令人困惑的命名问题，Boost.MultiIndex 只是从 C++ 标准继承的。

有序索引节点压缩

有序索引和排名索引是通过称为红黑树的数据结构实现的。红黑树的节点包含指向父节点和两个子节点的指针，以及一个称为节点颜色的 1 位字段（因此结构得名）。由于对齐问题，在大多数架构上，颜色字段占用一个完整的字，即在 32 位系统中占用 4 个字节，在 64 位环境中占用 8 个字节。可以通过将颜色位嵌入到节点指针之一中来避免这种空间浪费，前提是并非指针表示的所有位都包含有用的信息：这正是许多架构的情况，在这些架构中，此类节点与偶数地址对齐，这意味着地址的最低有效位必须始终为零。

Boost.MultiIndex 有序索引和排名索引在适用时实现这种类型的节点压缩。与 STL 容器 std::set 的常见实现相比，节点压缩可以将标头开销减少 25%（在典型的 32 位架构上从 16 字节减少到 12 字节，在 64 位系统上从 32 字节减少到 24 字节）。对于中等大小的容器，这种优化的性能影响已被验证为可忽略不计，而具有许多元素（数十万或更多）的容器使用这种优化会执行得更快，这很可能是由于 L1 和 L2 缓存效应。

可以通过全局设置宏 BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES 来禁用节点压缩。

basics
基础
Boost.MultiIndex tutorial
Boost.MultiIndex 教程
key estraction
键提取


修订于 2021 年 8 月 16 日

© 版权所有 2003-2021 Joaquín M López Muñoz。在 Boost 软件许可证 1.0 版下分发。（请参阅随附文件 LICENSE_1_0.txt 或复制 https://boost.ac.cn/LICENSE_1_0.txt）