Boost C++ 库

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

Boost.MultiIndex 教程: 基础

Boost.MultiIndex 教程

索引类型

简介

我们通过研究两个典型的用例来介绍 Boost.MultiIndex 的主要概念。

单个集合上的多个排序

STL 集合和多重集合是可变长度的容器，其中的元素根据给定的比较谓词有效地排序。当程序员希望有效地排序和查找遵循不同排序标准的元素时，这些容器类在功能上有所欠缺。例如，考虑以下情况：

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

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

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

ID 对于每个员工都是唯一的这一事实反映在 operator< 的定义方式中，因此存储 employee 的自然数据结构只是一个 std::set<employee>。现在，如果希望按字母顺序列出所有员工的列表，可用的解决方案可能在存储空间、复杂性或易维护性方面存在缺点

将员工集合复制到向量或类似的容器中，并根据依赖于 employee::name 的比较仿函数对其进行排序。
维护辅助数据结构，该结构包含指向集合元素的指针，并按名称进行适当排序。

在这些方案中，可能是第二个方案会被大多数关注效率的程序员所采用，但这给保持两个结构同步带来了烦人的负担。如果代码还需要是异常安全的，则这种构造很容易变得难以维护。

Boost.MultiIndex 具有 有序索引，它可以根据特定的键对元素进行排序，旨在帮助需要多个排序标准的元素序列的程序员。我们通过定义由多个有序索引组成的 multi_index_container 实例化来实现这一点：每个索引单独来看，其行为很像有序的 std::set（或 std::multiset），而整个数据结构的整体完整性得到了保留。因此，我们的示例问题可以使用 Boost.MultiIndex 解决，如下所示：

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

// define a multiply indexed set with indices by id and name
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> >
  > 
> employee_set;

void print_out_by_name(const employee_set& es)
{
  // get a view to index #1 (name)
  const employee_set::nth_index<1>::type& name_index=es.get<1>();
  // use name_index as a regular std::set
  std::copy(
    name_index.begin(),name_index.end(),
    std::ostream_iterator<employee>(std::cout));
}

与 STL 关联容器的情况一样，multi_index_container 传递的是索引规范（indexed_by）的列表，每个规范都会引起相应的索引。索引通过 get<N>() 访问，其中 N 的范围在 0 到比较谓词的数量减 1 之间。索引 #0 的功能可以直接从 multi_index_container 对象访问，而无需使用 get<0>()：例如，es.begin() 等效于 es.get<0>().begin()。

请注意，get 返回的是索引的引用，而不是索引对象。索引不能从它们所属的容器中构造为单独的对象，因此以下代码

// Wrong: we forgot the & after employee_set::nth_index<1>::type
const employee_set::nth_index<1>::type name_index=es.get<1>();

无法编译，因为它试图构造索引对象 name_index。这是用户代码中常见的错误来源。

具有快速查找的双向列表

本案例研究允许我们介绍所谓的 序列索引，以及它们如何与有序索引交互以构建强大的容器。假设我们有一个解析成单词的文本，并存储在如下所示的列表中：

typedef std::list<std::string> text_container;

std::string text=
  "Alice was beginning to get very tired of sitting by her sister on the "
  "bank, and of having nothing to do: once or twice she had peeped into the "
  "book her sister was reading, but it had no pictures or conversations in "
  "it, 'and what is the use of a book,' thought Alice 'without pictures or "
  "conversation?'";

// feed the text into the list
text_container tc;
boost::tokenizer<boost::char_separator<char> > tok
  (text,boost::char_separator<char>(" \t\n.,;:!?'\"-"));
std::copy(tok.begin(),tok.end(),std::back_inserter(tc));

如果我们想计算给定单词在文本中出现的次数，我们将求助于 std::count

std::size_t occurrences(const std::string& word)
{
  return std::count(tc.begin(),tc.end(),word);
}

但是，occurrences 的这种实现以线性时间执行，这对于大量文本来说可能是不可接受的。同样，诸如删除选定单词之类的其他操作在 std::list 上执行的成本也太高了

void delete_word(const std::string& word)
{
  tc.remove(word); // scans the entire list looking for word
}

当性能成为关注点时，我们将需要一个额外的数据结构来索引 tc 中的元素，大概是按字母顺序排列。Boost.MultiIndex 正是通过序列索引和有序索引的组合来实现这一点的

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

// define a multi_index_container with a list-like index and an ordered index
typedef multi_index_container<
  std::string,
  indexed_by<
    sequenced<>, // list-like index
    ordered_non_unique<identity<std::string> > // words by alphabetical order
  >
> text_container;

std::string text=...

// feed the text into the list
text_container tc;
boost::tokenizer<boost::char_separator<char> > tok
  (text,boost::char_separator<char>(" \t\n.,;:!?'\"-"));
std::copy(tok.begin(),tok.end(),std::back_inserter(tc));

到目前为止，用 multi_index_container 替换 std::list 并没有显示出任何优势。将文本插入容器的代码没有改变，因为序列索引提供了类似于 std::list 的接口（无需通过 get<0>() 显式访问此索引，因为 multi_index_container 继承了索引 #0 的功能）。但是，指定额外的有序索引允许我们以更有效的方式实现 occurrences 和 delete_word

std::size_t occurrences(const std::string& word)
{
  // get a view to index #1
  text_container::nth_index<1>::type& sorted_index=tc.get<1>();

  // use sorted_index as a regular std::set
  return sorted_index.count(word);
}

void delete_word(const std::string& word)
{
  // get a view to index #1
  text_container::nth_index<1>::type& sorted_index=tc.get<1>();

  // use sorted_index as a regular std::set
  sorted_index.erase(word);
}

现在，occurrences 和 delete_word 具有对数复杂度。程序员可以使用索引 #0 像使用 std::list 一样访问文本，并在需要对数查找时使用索引 #1。

索引规范

multi_index_container 实例化的索引通过 indexed_by 构造来指定。例如，实例化

typedef multi_index_container<
  employee,
  indexed_by<
    ordered_unique<identity<employee> >,
    ordered_non_unique<member<employee,std::string,&employee::name> >
  > 
> employee_set;

由一个唯一有序索引和一个非唯一有序索引组成，而在

typedef multi_index_container<
  std::string,
  indexed_by<
    sequenced<>,
    ordered_non_unique<identity<std::string> >
  >
> text_container;

我们指定了两个索引，第一个是序列类型，第二个是非唯一的有序索引。一般来说，我们可以指定任意数量的索引：indexed_by 的每个参数都称为 索引说明符。根据要指定的索引类型，相应的说明符将需要额外的信息：例如，说明符 ordered_unique 和 ordered_non_unique 提供了键提取器和可选的比较谓词，它们共同指示将如何执行元素的排序。

可以声明 multi_index_container 实例化，而无需提供 indexed_by 部分：在这种情况下，将采用默认索引值，以便生成的类型等效于常规的 std::set。具体来说，实例化

multi_index_container<(element)>

等效于

multi_index_container<
  (element),
  indexed_by<
    ordered_unique<identity<(element)> >
  >
>

标记

为了检索给定 multi_index_container 的索引（的引用），程序员必须提供其序号，这很麻烦且不具有自描述性。可选地，可以为索引分配标签（C++ 类型），这些标签充当更方便的助记符。如果提供标签，则必须将其作为相应索引说明符的第一个参数传递。以下是包含标签的 employee_set 的修订版本

// tags 
struct name{};

typedef multi_index_container<
  employee,
  indexed_by<
    ordered_unique<identity<employee> >,
    ordered_non_unique<tag<name>,member<employee,std::string,&employee::name> >
  >
> employee_set;

标签必须在 tag 构造中传递。任何类型都可以用作索引的标签，尽管通常会选择描述与其关联的索引的名称。标记机制允许我们编写如下表达式：

typedef employee_set::index<name>::type employee_set_by_name;
employee_set_by_name::iterator it=es.get<name>().begin();

如果未为索引提供标签（如前一个示例中的索引 #0 的情况），则只能通过编号访问该索引。请注意，存在两个不同的 typedef nth_index 和 index，分别用于按编号和按标签引用索引；例如，

employee_set::nth_index<1>::type 是索引 #1 的类型，
employee_set::index<name>::type 是标记为 name 的索引的类型（在本例中是相同的索引 #1。）

另一方面，get() 被重载以服务于两种访问方式

employee_set::index<name>::type& name_index=es.get<name>();
employee_set::nth_index<1>::type& name_index2=es.get<1>(); // same index

此外，tag 类模板接受一个索引的多个标签，我们可以互换使用这些标签：例如，前一个示例中索引 #1 的规范可以重写为包含两个不同的标签 name 和 by_name

// tags
struct name{};
struct by_name{};

typedef multi_index_container<
  ...
    ordered_non_unique<
      tag<name,by_name>,
      member<employee,std::string,&employee::name>
    >
  ...
> employee_set;

迭代器访问

multi_index_container 的每个索引都使用自己的迭代器类型，这些类型与其他索引的迭代器类型不同。按照 STL 容器的规则，这些迭代器被定义为索引的嵌套类型

employee_set::nth_index<1>::type::iterator it=
  es.get<1>().find("Judy Smith");

这种表达式可以通过用户定义的 typedef 使其更具可读性

typedef employee_set::nth_index<1>::type employee_set_by_name;
employee_set_by_name::iterator it=
  es.get<1>().find("Judy Smith");

每个索引提供的迭代器都是常量，也就是说，它们指向的元素不能直接修改。这遵循有序索引的 std::set 接口，但对于其他类型（如序列索引）可能会令人惊讶，序列索引以 std::list 为模型，其中不会发生这种限制。这种看似奇怪的行为是由 multi_index_container 的工作方式决定的；如果允许随意修改元素，我们可能会在 multi_index_container 的有序索引中引入不一致性，而容器不会收到通知。元素修改应通过任何索引上的更新操作正确完成。

索引类型

目前，Boost.MultiIndex 提供以下索引类型

有序索引像 std::set 一样对元素进行排序，并提供类似的接口。有唯一和非唯一变体：前者不允许重复，而后者允许重复（如 std::multiset。）
排序索引是有序索引的一种变体，它提供了额外的功能，用于基于元素的秩（它们在索引中占据的数字位置）查询和访问元素。
序列索引以 std::list 的语义和接口为模型：它们像在双向列表中一样排列元素。
哈希索引通过哈希技术提供对元素的快速访问，方式类似于无序关联容器 std::unordered_set（如果不允许重复）和 std::unordered_multiset（如果允许重复）。
随机访问索引提供类似于序列索引的接口，此外还具有随机访问迭代器和对元素的位置访问。

简介中的示例练习了有序索引和序列索引，它们是最常用的；其他类型的索引在教程的索引类型部分介绍。

有序索引

有序索引根据指定的键和关联的比较谓词对 multi_index_container 中的元素进行排序。这些索引可以看作是标准容器 std::set 的类似物，实际上它们确实复制了它的接口，尽管由于 Boost.MultiIndex 的一般约束，存在一些细微的差异。

唯一和非唯一变体

有序索引分为唯一索引和非唯一索引，前者禁止两个元素具有相同的键值，后者允许重复。再次考虑以下定义：

typedef multi_index_container<
  employee,
  indexed_by<
    ordered_unique<identity<employee> >,
    ordered_non_unique<member<employee,std::string,&employee::name> >
  > 
> employee_set;

在此 multi_index_container 实例化中，第一个索引应被视为唯一的（因为 ID 是每个员工独有的），因此使用 ordered_unique 声明，而第二个索引是非唯一的（因为可能存在两个同名的 John Smith 在同一家公司被聘用），这通过使用 ordered_non_unique 来指定。

有序索引在唯一和非唯一方面的分类对允许插入给定 multi_index_container 的元素产生影响；简而言之，唯一有序索引模仿 std::set 的行为，而非唯一有序索引类似于 std::multiset。例如，employee_set 可以保存对象 employee(0,"George Brown") 和 employee(1,"George Brown")，但不会接受插入 ID 与先前插入的员工的 ID 重合的 employee 对象。

可以指定多个唯一索引。例如，如果我们扩充 employee 以包含社会安全号码的额外成员，这可以合理地视为唯一的，则以下内容捕获了此设计

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> >,
    
    // sort by less<int> on ssnumber
    ordered_unique<member<employee,int,&employee::ssnumber> >
  >
> employee_set;

规范

indexed_by 中的有序索引说明符必须符合以下语法之一

(ordered_unique | ordered_non_unique)
  <[(tag)[,(key extractor)[,(comparison predicate)]]]>

(ordered_unique | ordered_non_unique)
  <[(key extractor)[,(comparison predicate)]]>

如果标签与索引关联，则使用第一个可选参数。现在，我们继续简要讨论有序索引说明符的其余参数。

键提取

有序索引规范中的第一个模板参数（如果提供了标签，则为第二个参数）提供了键提取谓词。此谓词接受一个完整元素（在我们的示例中，是对 employee 对象的引用），并返回用于排序的信息片段。在大多数情况下，会出现以下两种情况之一

整个元素充当键，就像 employee_set 中的第一个索引的情况一样。预定义的 identity 谓词可以在此处用作键提取器；identity 将作为键返回与作为参数传递的同一对象。
比较在元素的特定数据成员上执行；这与关系数据库中表列上的索引规范密切相关。Boost.MultiIndex 提供了 member，它返回作为键的元素成员，该成员由给定的指针指定。

例如，再次考虑 employee_set 的定义。第一个索引的定义

ordered_unique<identity<employee> >

通过 identity 指定 element 对象本身充当此索引的键。另一方面，在第二个索引中

ordered_non_unique<member<employee,std::string,&employee::name> >

我们使用 member 来提取 employee 对象的 name 部分。然后此索引的键类型为 std::string。

除了 identity 和 member 之外，Boost.MultiIndex 还提供了其他几个预定义的键提取器以及组合它们的强大方法。键提取器也可以由用户定义。有关此主题的更详细说明，请查阅教程的键提取部分。

比较谓词

有序索引规范的最后一部分是关联的比较谓词，它必须以小于方式对键进行排序。这些比较谓词与 STL 容器（如 std::set）使用的比较谓词没有区别。默认情况下（即，如果未提供比较谓词），键类型为 key_type 的索引按 std::less<key_type> 对元素进行排序。如果需要其他比较标准，则可以在索引声明中将其指定为附加参数

// define a multiply indexed set with indices by id and by name
// in reverse alphabetical order
typedef multi_index_container<
  employee,
  indexed_by<
    ordered_unique<identity<employee> >, // as usual
    ordered_non_unique<
      member<employee,std::string,&employee::name>,
      std::greater<std::string>  // default would be std::less<std::string>
    >
  >
> employee_set;

特殊查找操作

给定的有序索引允许基于其键类型而不是整个元素进行查找。例如，要在 employee_set 中查找 Veronica Cruz，可以编写

employee_set es;
...
typedef employee_set::index<name>::type employee_set_by_name;
employee_set_by_name::iterator it=es.get<name>().find("Veronica Cruz");

此外，Boost.MultiIndex 提供了接受与索引的 key_type 不同的搜索键的查找操作，当 key_type 对象创建成本很高时，这是一个特别有用的工具。有序 STL 容器未能提供此功能，这通常会导致不优雅的变通方法：例如，考虑确定 ID 范围在 [0,100] 内的员工的问题。鉴于 employee_set 索引 #0 的键是 employee 本身，在第一种方法中，人们会编写以下代码

employee_set::iterator p0=es.lower_bound(employee(0,""));
employee_set::iterator p1=es.upper_bound(employee(100,""));

但是请注意，std::less<employee> 实际上只依赖于员工的 ID，因此避免仅仅为了获取 ID 而创建完整的 employee 对象会更方便。Boost.MultiIndex 允许这样做：定义适当的比较谓词

struct comp_id
{
  // compare an ID and an employee
  bool operator()(int x,const employee& e2)const{return x<e2.id;}

  // compare an employee and an ID
  bool operator()(const employee& e1,int x)const{return e1.id<x;}
};

现在将搜索编写为

employee_set::iterator p0=es.lower_bound(0,comp_id());
employee_set::iterator p1=es.upper_bound(100,comp_id());

在这里，我们不仅传递了 ID 而不是 employee 对象：还传递了备用的比较谓词。一般来说，有序索引的查找操作被重载以接受 兼容的排序标准。参考资料中给出了此上下文中兼容性的有些繁琐的定义，但粗略地说，我们说比较谓词 C1 与 C2 兼容，如果任何由 C2 排序的序列也相对于 C1 排序。以下示例显示了兼容谓词的更有趣的用法

// sorting by name's initial
struct comp_initial
{
  bool operator()(char ch,const std::string& s)const{
    if(s.empty())return false;
    return ch<s[0];
  }

  bool operator()(const std::string& s,char ch)const{
    if(s.empty())return true;
    return s[0]<ch;
  }
};

// obtain first employee whose name begins with 'J' (ordered by name)
typedef employee_set::index<name>::type employee_set_by_name;
employee_set_by_name& name_index=es.get<name>(); 
employee_set_by_name::const_iterator it=
  name_index.lower_bound('J',comp_initial());

范围检索

范围搜索，即查找给定间隔中的所有元素，是一种非常频繁的操作，可以使用标准 lower_bound 和 upper_bound 来完成，尽管方式很繁琐。例如，以下代码检索间隔 [100,200] 中 multi_index_container<double> 的元素

typedef multi_index_container<double> double_set;
// note: default template parameters resolve to
// multi_index_container<double,indexed_by<unique<identity<double> > > >.

double_set s;
...
double_set::iterator it0=s.lower_bound(100.0);
double_set::iterator it1=s.upper_bound(200.0);
// range [it0,it1) contains the elements in [100,200]

当考虑严格不等式时，需要对代码进行细微的更改。要检索大于 100 且小于 200 的元素，必须将代码重写为

double_set::iterator it0=s.upper_bound(100.0);
double_set::iterator it1=s.lower_bound(200.0);
// range [it0,it1) contains the elements in (100,200)

为了增加这种复杂性，细心的程序员必须考虑到搜索间隔的下限和上限是兼容的：例如，如果下限是 200，上限是 100，则上述代码生成的迭代器 it0 和 it1 将反向排序，如果尝试从 it0 到 it1 的遍历，可能会导致灾难性后果。所有这些细节都使范围搜索成为一项乏味且容易出错的任务。

range 成员函数，通常与 Boost.Lambda 表达式结合使用，可以极大地帮助缓解这种情况

using namespace boost::lambda;

typedef multi_index_container<double> double_set;
double_set s;
...
std::pair<double_set::iterator,double_set::iterator> p=
  s.range(100.0<=_1,_1<=200); // 100<= x <=200
...
p=s.range(100.0<_1,_1<200);   // 100<  x < 200
...
p=s.range(100.0<=_1,_1<200);  // 100<= x < 200

range 只是接受指定搜索间隔下限和上限的谓词。有关传递给 range 的允许谓词的详细说明，请查阅参考资料。

可以使用特殊的 unbounded 标记省略一个或两个边界

p=s.range(100.0<=_1,unbounded); // 100 <= x
p=s.range(unbounded,_1<200.0);  //   x <  200
p=s.range(unbounded,unbounded); // equiv. to std::make_pair(s.begin(),s.end())

更新

replace 成员函数执行给定元素的就地替换，如下例所示

typedef index<employee_set,name>::type employee_set_by_name;
employee_set_by_name& name_index=es.get<name>();

employee_set_by_name::iterator it=name_index.find("Anna Jones");
employee anna=*it;
anna.name="Anna Smith";      // she just got married to Calvin Smith
name_index.replace(it,anna); // update her record

replace 以如下方式执行此替换

如果更改的元素相对于所有索引保持其原始顺序，则复杂度为常数时间；否则为对数时间。
迭代器和引用的有效性得到保留。
该操作是强异常安全的，即，如果抛出某些异常（由系统或用户数据类型引起），则 multi_index_container 保持不变。

replace 是标准 STL 容器未提供的强大操作，并且在需要强异常安全性的情况下特别方便。

细心的读者可能已经注意到，replace 的便利性是有代价的：即，整个元素必须复制两次才能进行更新（检索时和在 replace 内部）。如果元素复制成本很高，那么仅仅修改对象的一小部分可能会带来相当大的计算成本。为了应对这种情况，Boost.MultiIndex 提供了一种称为 modify 的替代更新机制

struct change_name
{
  change_name(const std::string& new_name):new_name(new_name){}

  void operator()(employee& e)
  {
    e.name=new_name;
  }

private:
  std::string new_name;
};
...
typedef employee_set::index<name>::type employee_set_by_name;
employee_set_by_name& name_index=es.get<name>();

employee_set_by_name::iterator it=name_index.find("Anna Jones");
name_index.modify(it,change_name("Anna Smith"));

modify 接受一个仿函数（或指向函数的指针），该仿函数传递对要更改的元素的引用，从而消除了对伪造副本的需求。与 replace 一样，modify 也保留了 multi_index_container 所有索引的内部排序。但是，modify 的语义与 replace 并不完全等效。考虑一下，如果由于修改元素而发生冲突会发生什么情况，即，修改后的元素在某些唯一有序索引方面与其他元素发生冲突。在 replace 的情况下，原始值保持不变，并且方法返回而不更改容器，但是 modify 无法承担这种方法，因为修改仿函数没有留下元素先前值的痕迹。因此，完整性约束导致以下策略：当在调用 modify 的过程中发生冲突时，元素将被擦除，并且该方法返回 false。modify 还有另一个版本，它接受回滚仿函数，以便在发生冲突时撤消更改

struct change_id
{
  change_id(int new_id):new_id(new_id){}

  void operator()(employee& e)
  {
    e.id=new_id;
  }

private:
  int new_id;
};
...
employee_set::iterator it=...

int old_id=it->id; // keep the original id

// try to modify the id, restore it in case of collisions
es.modify(it,change_id(321),change_id(old_id));

在示例中，当修改导致与其他元素冲突时，调用 change_id(old_id) 以恢复原始条件。程序员必须根据具体情况考虑 replace、modify 和带有回滚的 modify 之间行为的差异，以确定最佳的更新机制。

**不同更新机制的行为。**
更新函数	如果发生冲突...
`replace(it,x)`	替换不会发生。
`modify(it,mod)`	元素被擦除。
`modify(it,mod,back)`	`back` 用于恢复原始条件。（如果 `back` 抛出异常，则元素将被擦除。）

还提供了基于键的 modify 版本，名为 modify_key。在这种情况下，修改仿函数被传递对元素的 key_type 部分的引用，而不是整个对象。

struct change_str
{
  change_str(const std::string& new_str):new_str(new_str){}

  // note this is passed a string, not an employee
  void operator()(std::string& str)
  {
    str=new_str;
  }

private:
  std::string new_str;
};
...
typedef employee_set::index<name>::type employee_set_by_name;
employee_set_by_name& name_index=es.get<name>();

employee_set_by_name::iterator it=name_index.find("Anna Jones");
name_index.modify_key(it,change_str("Anna Smith"));

与 modify 类似，modify_key 也有带回滚和不带回滚的版本。modify 和 modify_key 特别适合与 Boost.Lambda 结合使用，以定义修改仿函数

using namespace boost::lambda;

typedef employee_set::index<name>::type employee_set_by_name;
employee_set_by_name& name_index=es.get<name>();

employee_set_by_name::iterator it=name_index.find("Anna Jones");
name_index.modify_key(it,_1="Anna Smith");

modify_key 要求键提取器是称为读/写的特殊类型：通常情况下是这样，但并非总是如此。

序列索引

与有序索引不同，序列索引不对元素施加固定的顺序：相反，这些元素可以像 std::list 允许的那样排列在序列中的任何位置。因此，序列索引的接口是根据 std::list 的接口设计的；标准容器中提供的几乎每个操作都在此处复制，偶尔会更改语法和/或语义以应对 Boost.MultiIndex 施加的约束。上面评论的一个重要区别是，序列索引迭代器指向的值被视为常量

multi_index_container<
  int,
  indexed_by<sequenced<> >
> s;            // list-like container

s.push_front(0);
*(s.begin())=1; // ERROR: the element cannot be changed

但是，与任何其他类型的索引一样，仍然可以通过更新操作进行元素修改。

考虑具有两个或多个索引的 multi_index_container，其中一个是序列类型。如果通过另一个索引插入元素，则该元素将自动附加到序列索引的末尾。一个例子将有助于阐明这一点

multi_index_container<
  int,
  indexed_by<
    sequenced<>,           // sequenced type
    ordered_unique<identity<int> > // another index
  >
> s;

s.get<1>().insert(1); // insert 1 through index #1
s.get<1>().insert(0); // insert 0 through index #1

// list elements through sequenced index #0
std::copy(s.begin(),s.end(),std::ostream_iterator<int>(std::cout));

// result: 1 0

因此，当不通过序列索引进行插入时，序列索引的行为是保留插入顺序。

规范

序列索引使用 sequenced 构造指定

sequenced<[(tag)]>

标签参数是可选的。

列表操作

如前所述，序列索引模仿 std::list 的接口，并且其中大多数原始操作也在此处提供。但是，这些操作的语义和复杂度并不总是与标准容器的语义和复杂度一致。差异主要源于以下事实：不能保证成功插入序列索引，因为 multi_index_container 的其他索引可能会禁止插入。有关更多详细信息，请查阅参考资料。

更新

与有序索引类似，序列索引提供 replace 和 modify 操作，它们具有相同的功能。但是，没有类似的 modify_key，因为序列索引不是基于键的。

迭代器投影

给定同一 multi_index_container 上的索引 i1 和 i2，project 可用于从 i1-迭代器检索 i2-迭代器，它们都指向容器的同一元素。此功能允许程序员在执行复杂操作时在同一 multi_index_container 的不同索引之间移动

typedef employee_set::index<name>::type employee_set_by_name;
employee_set_by_name& name_index=es.get<name>();

// list employees by ID starting from Robert Brown's ID

employee_set_by_name::iterator it1=name_index.find("Robert Brown");

// obtain an iterator of index #0 from it1
employee_set::iterator it2=es.project<0>(it1); 

std::copy(it2,es.end(),std::ostream_iterator<employee>(std::cout));

一个稍微更有趣的例子

text_container tc;

// get a view to index #1 (ordered index on the words)
text_container::nth_index<1>::type& sorted_index=tc.get<1>();

// prepend "older" to all occurrences of "sister"

text_container::nth_index<1>::type::iterator it1=
  sorted_index.lower_bound("sister");
  
while(it1!=sorted_index.end()&&*it1=="sister"){
  // convert to an iterator to the sequenced index
  text_container::iterator it2=tc.project<0>(it1);

  tc.insert(it2,"older");
  ++it1;
}

如果提供，project 也可以与标签一起使用。

复杂度和异常安全性

multi_index_container 提供与等效 STL 容器相同的复杂性和异常安全保证。即使对于 replace 和 modify 操作，迭代器和引用的有效性也得到保留。

实际上，multi_index_container 的适当实例化可以模拟 std::set、std::multiset 和（在更多限制下）std::list，如技术部分所示。这些模拟与原始 STL 容器几乎一样高效；有关复杂性保证的更多信息，请查阅参考资料，有关效率的实际测量，请查阅性能部分。

Boost.MultiIndex 教程

索引类型

修订于 2021 年 8 月 16 日

Boost.MultiIndex 教程: 基础

目录