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 和比较谓词的数量减一之间。索引 #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 与先前插入的员工相同的 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 对象：还传递了一个替代的比较谓词。通常，有序索引的查找操作被重载以接受 *兼容的排序标准*。参考中给出了此上下文中兼容性的有点繁琐的定义，但粗略地说，如果按 C2 排序的任何序列也相对于 C1 排序，我们就说比较谓词 C1 与 C2 兼容。以下显示了兼容谓词的更有趣的用法

// 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 容器相同的复杂性和异常安全保证。即使对于替换和修改操作，迭代器和引用的有效性在插入时也会得到保留。

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

Boost.MultiIndex 教程

索引类型

修订于 2021 年 8 月 16 日

Boost.MultiIndex 教程：基础

目录