Boost.MultiIndex 教程：索引类型

基础知识

Boost.MultiIndex 教程

键提取

目录

• 分类
• 排序索引
  • 规范
  • 排序操作
• 哈希索引
  • 唯一和非唯一变体
  • 规范
  • 查找
  • 更新
  • 迭代器有效性和异常安全性的保证
• 随机访问索引
  • 规范
  • 接口
  • 与 std::vector 的比较
• 索引重排
• iterator_to
• 节点处理操作
• 有序索引节点压缩

分类

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

基于键的索引（其中有序索引是常见的示例）基于称为元素键的某些信息提供元素的有效查找：有一个广泛的键提取实用程序类套件，允许指定此类键。快速查找对这些索引施加了内部管理的顺序，用户不允许修改；另一方面，非基于键的索引可以自由地重新排列，但代价是缺乏查找功能。序列索引以 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_rank,
• lower_bound_rank,
• upper_bound_rank,
• equal_range_rank 和
• range_rank

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++ 标准对无序关联容器的要求更强

• 在插入或重新哈希期间，迭代器有效性在任何情况下都得到保留：当执行重新哈希（隐式或显式）时，C++ 无序关联容器可能会使迭代器无效。
• 通过迭代器删除元素或元素范围永远不会抛出异常，因为实际上不会调用内部哈希函数和相等谓词对象。
• rehash 无条件地提供强异常安全保证。仅当内部哈希函数和相等谓词对象不抛出异常时，标准才保证无序关联容器的强异常安全保证。有点令人惊讶的后果是，如果重新哈希期间抛出异常，则符合标准的 std::unordered_set 可能会删除元素！

随机访问索引

随机访问索引提供与序列索引相同类型的功能，但额外的优势是它们的迭代器是随机访问的，并且提供了 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 的比较

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

• 它们不提供内存连续性，这是 std::vector 的一个属性，通过该属性，元素存储在单个内存块中彼此相邻。
• 与 Boost.MultiIndex 中通常的情况一样，随机访问索引的元素是不可变的，并且只能通过成员函数 replace 和 modify 进行修改。这排除了许多变异算法的使用，尽管这些算法仍然适用于 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 的元素是（来自 Boost.Ref 的）reference_wrapper，指向 multi-index 容器中的实际元素。这些对象仍然不允许修改引用的实体，但是它们是可交换的，这是 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());

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

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 旨在用于通过迭代器访问不合适或不可取的场景

• 与基于指针或引用的现有 API 的互操作性。
• 基于指针的接口的发布（例如，在设计 C 兼容库时）。
• 用指针代替迭代器的公开可以充当类型擦除屏障，有效地将代码用户与正在使用的特定容器的实现细节分离。类似的技术（例如著名的 Pimpl 惯用法）用于大型项目中，以减少依赖性和构建时间。
• 自引用上下文，其中元素作用于其所有者容器，并且没有指向自身的迭代器可用。

节点处理操作

使用直接节点操作，可以在 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 来禁用节点压缩。

基础知识

Boost.MultiIndex 教程

键提取

修订于 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 复制）