Boost.MultiIndex 指南: 基礎

Boost.MultiIndex 指南

Boost.MultiIndex 指南

Index types索引的類型

Contents目錄

• Introduction簡介
  • Multiple sorts on a single set單個集合上的多種排序
  • A bidirectional list with fast lookup可快速查找的雙向鏈表
• Index specification索引的規格
• Tagging標誌
• Iterator access迭代器訪問
• Index types索引的類型
  • Ordered indices有序索引
    • Unique and non-unique variants唯一與非唯一索引的區別
    • Specification規範
    • Key extraction鍵提取
    • Comparison predicates比較謂詞
    • Special lookup operations特殊的查找操作
    • Retrieval of ranges範圍的獲取
    • Updating更新
  • Sequenced indices序列索引
    • Specification規範
    • List operations鏈表操作
    • Updating更新
• Projection of iterators迭代器投影
• Complexity and exception safety複雜度與異常安全性

Introduction簡介

我們通過研究兩個典型用例來介紹Boost.MultiIndex的主要概念。

Multiple sorts on a single set單個集合上的多種排序

STL的set和multiset都是可變長度的容器，其中的元素按照一個給定的比較謂詞高效地進行了排序。當程序員希望按不同的排序標準進行排序或查找時，這些容器類就無法滿足了。考慮以下例子：

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< ，因此保存employees的最自然的數據結構就是 std::set<employee>。現在，如果有人希望按字母順序打印出所有員工的列表，可行的解決方法可能會在存儲空間、時間複雜度或易維護性中的某個方面存在弱點：

• 將 employee set 拷貝到一個 vector 或類似的結構中，再使用比較employee::name的函數對像來進行排序。
• 維護一個次級數據結構，其中保存了指向這些元素的指針，並按name來排序。

Boost.MultiIndex 提供了 ordered indices有序索引, 可以通過另一鍵值對元素進行排序，是專門為了需要多種排序方法的容器的程序員而設計的。方法如下，定義一個 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>

// 定義一個按id和name進行索引和多索引set
typedef multi_index_container<
  employee,
  indexed_by<
    // 以 employee::operator< 排序
    ordered_unique<identity<employee> >,
    
    // 以 less<string> 在name上排序
    ordered_non_unique<member<employee,std::string,&employee::name> >
  > 
> employee_set;

void print_out_by_name(const employee_set& es)
{
  // 取得一個對索引#1(name)的視圖
  const employee_set::nth_index<1>::type& name_index=es.get<1>();
  // 像一個普通的std::set那樣使用name_index
  std::copy(
    name_index.begin(),name_index.end(),
    std::ostream_iterator<employee>(std::cout));
}
  

與STL關聯式容器中的單一比較謂詞不同，multi_index_container 要傳入一個索引方法的typelist (indexed_by)，其中每一項對應一個索引。通過 get<N>() 來訪問對應的索引，N 的取值為從0到比較謂詞數量減一。#0索引可以直接從 multi_index_container 對像訪問，無需使用 get<0>()，例如：es.begin() 等同於 es.get<0>().begin()。

注意，get 返回一個索引的引用，而不是索引的對象。索引不能在它們所屬的容器之外獨立構造，以下代碼：

// 錯誤：忘記了employee_set::nth_index<1>::type後面的&
const employee_set::nth_index<1>::type name_index=es.get<1>();
  

不能通過編譯，因為它試圖構造一個索引對像 name_index. 這是用戶代碼中的常見錯誤。

A bidirectional list with fast lookup可快速查找的雙向列表

這個例子中將介紹 sequenced indices序列索引, 以及它們如何與有序索引相合以構造強大的容器。假定我們要將一個文本分解為單詞並保存在一個列表中，如下：

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?'";

// 將文本放入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); // 掃瞄整個列表來查找單詞
}
  

如果性能是你必須關心的，我們就需要一個額外的數據結構來按字母順序索引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>

// 定義一個具有類-list的索引以及有序索引的 multi_index_container
typedef multi_index_container<
  std::string,
  indexed_by<
    sequenced<>, // 類-list索引
    ordered_non_unique<identity<std::string> > // 按字母序排列單詞
  >
> text_container;

std::string text=...

// 將文本放入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)
{
  // 取得索引#1的視圖
  text_container::nth_index<1>::type& sorted_index=tc.get<1>();

  // 像一個普通的std::set那樣使用sorted_index
  return sorted_index.count(word);
}

void delete_word(const std::string& word)
{
  // 取得索引#1的視圖
  text_container::nth_index<1>::type& sorted_index=tc.get<1>();

  // 像一個普通的std::set那樣使用sorted_index
  sorted_index.erase(word);
}
  

現在，occurrences 和 delete_word 具有了對數時間複雜度。程序員可以使用索引#0來象 std::list 那樣訪問文本，也可以在需要對數查找時使用索引#1。

Index specification索引的規格

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;
  

其索引由一個 unique ordered index 和一個 non-unique ordered index組成，而以下代碼：

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

則指定兩個索引，第一個是 sequenced type, 第二個是非唯一 ordered index。通常，我們可以指定任意數量的索引：indexed_by中的每一個參數被稱為一個 index specifier索引說明。不同的索引類型在指定時，需要給出不同的信息，例如：ordered_unique 和 ordered_non_unique 的說明要提供一個 key extractor鍵提取器 和一個可選的 comparison predicate比較謂詞，以指明如何進行元素的排序。

multi_index_container 的實例化也可以沒有 indexed_by 部分，這種情況下將使用缺省的索引值，其結果等同於普通的std::set。以下實例化：

multi_index_container<(element)>
  

等同於

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

Tagging標誌

為了從給定的multi_index_container中取出一個索引(的引用)，程序員必須提供索引的序號，這一點有些麻煩，而且不具有自述性。作為可選項，索引可以被賦予一個標記tags (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)類型。

employee_set::index<name>::type& name_index=es.get<name>();
employee_set::nth_index<1>::type& name_index2=es.get<1>(); // 同一個索引
  

另外，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;
  

Iterator access迭代器訪問

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");
  

另外，multi_index_container 為索引的迭代器提供了一個簡短的定義

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

以上表達式的另一個寫法是使用 tags:

employee_set::index_iterator<name>::type it=
  es.get<name>().find("Judy Smith");         // 也可以用get<1> 
  

Index types索引的類型

當前，Boost.MultiIndex 提供以下索引類型：

• 有序索引Ordered indices，像std::set一樣對元素進行排序並提供類似的接口。有唯一和非唯一兩種：前者不允許重複值，後者則允許(如std::multiset)。 
• 序列索引Sequenced indices，參照std::list的接口和語義，像雙向列表一樣操縱元素。
• 散列索引Hashed indices，通過散列技術提供對元素的快速訪問，類似於其它提供者的非標準hash_set。最近，非排序關聯式容器unordered associative containers 已被標準委員會提議作為TR1加入C++標準庫中。散列索引近似於該提議。
• 隨機訪問索引Random access indices，提供一個類似於序列索引的接口，但增加了隨機訪問迭代器的特性，可以按位置訪問元素。

Ordered indices有序索引

有序索引依照給定的鍵和相應的比較謂詞對 multi_index_container 中的元素進行排序。這些索引看起來就像標準容器 std::set, 實際上它們就是複製了std::set的接口，雖然由於Boost.MultiIndex的通用約束而有一點點不同。

Unique and non-unique variants唯一與非唯一的區別

有序索引可分為唯一的（禁止兩個元素具有相同鍵值），和非唯一的（允許鍵值重複）。再看一次以下定義：

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 Smiths的)，以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<
    // 按 employee::operator< 排序
    ordered_unique<identity<employee> >,
    
    // 對name按 less<string> 排序
    ordered_non_unique<member<employee,std::string,&employee::name> >,
    
    // 對ssnumber按 less<int> 排序
    ordered_unique<member<employee,int,&employee::ssnumber> >
  >
> employee_set;
  

Specification規範

indexed_by中的有序索引說明必須符合以下語法：

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

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

如果索引具有 tags，則使用第一個可選參數。現在我們來簡單討論一下有序索引說明中的其它參數。 

Key extraction鍵提取

有序索引說明中的第一個模板參數(或者第二個，如果使用了標記)提供了一個鍵提取key extraction 謂詞。該謂詞接受一個完整的元素(在這個例子中，就是一個employee對象的引用)，返回執行排序的那部分信息。多數情況下，會是以下兩種情況之一：

• 整個元素本身就是關鍵字，正如employee_set的第一個索引那樣。這時預定義的 identity 謂詞可以用作鍵提取器；identity 將傳入的整個對象作為關鍵字返回。
• 僅對元素中的部分數據成員執行比較；類似於關係數據庫中指定表中的某一列作為索引。Boost.MultiIndex 提供了 member，它將元素中某個成員作為關鍵字返回，該成員以指針形式給定。

ordered_unique<identity<employee> >
  

通過 identity 指定整個 element 對像本身作為這個索引的關鍵字。而對於第二個索引：

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

我們用 member 來取得 employee對象的 name 部分。這個索引的關鍵字類型為std::string。

除了 identity 和 member 以外，Boost.MultiIndex 還提供了幾個預定義的鍵提供器以及把它們結合起來使用的強大方法。鍵提取器也可 以由用戶來定義。有關這個話題的更為詳細的說明，請參考本指南的 key extraction 鍵提取一節 .

Comparison predicates比較謂詞

有序索引說明的最後一部分是關聯的比較謂詞comparison predicate，其負責對鍵值進行“小於”比較。這些比較謂詞與STL容器std::set如所使用的沒有什麼不同。缺省地(即沒有指定比較謂詞)，類型為 key_type 的鍵使用 std::less<key_type> 進行比較。如果需要指定其它比較方法，則要在索引聲明中作為一個額外的參數進行指定：

// 定義一個多索引set，按id的順序以及按name的逆序排序
typedef multi_index_container<
  employee,
  indexed_by<
    ordered_unique<identity<employee> >, // 如常
    ordered_non_unique<
      member<employee,std::string,&employee::name>,
      std::greater<std::string>  // 缺省值是std::less<std::string>
    >
  >
> employee_set;
  

Special lookup operations特殊的查找操作

對於一個有序索引，可以基於其關鍵字類型進行查找，而不是基於整個元素。例如，在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
{
  // 比較一個ID和一個employee
  bool operator()(int x,const employee& e2)const{return x<e2.id;}

  // 比較一個employee和一個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對像來傳遞，還要傳入一個比較謂詞。通常，有序索引的查找操作都被重載以接受 compatible sorting criteria兼容排序標準。這裡的“兼容”性的定義有點複雜，在“參考”一節有詳細說明，大約上講，比較謂詞C1兼容於C2，是指對於C2是有序的任意序列，對於C1也同樣有序。下面示例了比較謂詞的一個有趣的用法：

// 按name的首字母排序
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;
  }
};

// 取得name以'J'開頭的第一個員工(以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());
  

Retrieval of ranges範圍的獲取

範圍查找即查找給定區間內的所有元素，是很常用的操作，標準的 lower_bound 和 upper_bound 常用於此。例如，以下代碼取得multi_index_container<double>中位於區間[100,200]的所有元素：

typedef multi_index_container<double> double_set;
// 注意: 缺省模板參數等同於
// 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);
// 範圍 [it0,it1) 包含了[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); // 等同於 std::make_pair(s.begin(),s.end())
  

Updating更新

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";      // 她剛嫁給了 Calvin Smith
name_index.replace(it,anna); // 更新相應的記錄
  

replace 有以下優點：

• 如果被更新的元素對於所有索引均保持原有順序，則操作為常數時間複雜度；否則為對數時間複雜度。
• 所有迭代器與引用的有效性均得到保證。
• 該操作是強異常安全的，即如果有任何異常(無論是系統或用戶的數據類型產生的)拋出， multi_index_container 保持不變。

仔細的讀者可能注意到了 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，它接受一個 rollback 函數對象，用於在發生衝突時取消所作的改變：

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; // 保持原有 id

// 嘗試修改 id, 當發生衝突時恢復它
es.modify(it,change_id(321),change_id(old_id));
  

在這個例子中，當修改數據導致某些元素的衝突時，change_id(old_id) 將被調用以恢復到原來的情形。程序員必須考慮 replace, modify 和帶回滾的 modify 間的差異，根據具體情況決定最佳的更新機制。

modify有一個專為關鍵字設計的版本，名為 modify_key。對於該函數，傳入的函數對像應接受元素的key_value部分的引用，而不是整個對象的引用。

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 要求鍵提取器是一種稱為 read/write 的特殊類型：通常這可以滿足，但並不總是如此。

Sequenced indices序列索引

與有序索引不同，序列索引不影響元素的順序：元素可以被放在序列中的任何位置，正如 std::list 所允許的那樣。序列索引的接口是參照std::list設計的；幾乎標準容器中的每一個操作都被複製了，只是由於Boost.MultiIndex的某些約束而在語法和/或語義上有少許的修改。特別地，序列索引與std::list不同的一個重要限制是，multi_index_container 中的元素不能通過迭代器來改寫：

multi_index_container<
  int,
  indexed_by<sequenced<> >
> s;            // 類-list容器

s.push_front(0);
*(s.begin())=1; // ERROR: 元素不能被修改
  

也就是說，序列索引(實際上所有類型的索引都是)的迭代器指向的是一個常量元素。這一限制可能會讓人驚訝，但它的確是 multi_index_container 的要求；如果元素可以用這種方式修改，我們將可能會對multi_index_container中的其它索引帶來不一致。元素的更新必須通過 update operations更新操作 完成。

考慮一個帶有兩個或以上索引的 multi_index_container，其中一個索引是序列索引。如果通過其它索引插入了一個元素，則該元素將被插入到該序列索引的尾部。以下例子可以說明這一點：

multi_index_container<
  int,
  indexed_by<
    sequenced<>,           // 序列索引
    ordered_unique<identity<int> > // 其它索引
  >
> s;

s.get<1>().insert(1); // 通過索引#1插入1
s.get<1>().insert(0); // 通過索引#1插入0

// 通過索引#0列出元素
std::copy(s.begin(),s.end(),std::ostream_iterator<int>(std::cout));

// 結果: 1 0
  

可見，不通過序列索引進行插入時，序列索引將保持元素的插入順序。

Specification規範

序列索引用sequenced結構來指定：

sequenced<[(tag)]>
  

tag 參數是可選的。

List operations列表操作

與前所說，序列索引參照了std::list的接口，大部分原有的操作都有提供。但是這些操作的語義和複雜度則不完全與標準容器相同。其中最主要的差異是，序列索引的插入操作並不保證一定成功，由於有可能被 multi_index_container 中的其它索引所禁止。更多的細節請查閱 reference參考。

Updating更新

與有序索引一樣，序列索引提供了相同功能的 replace 和 modify 操作。但是沒有 modify_key，由於序列索引沒有關鍵字。

Projection of iterators迭代器投影

給定一個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>();

// 按ID從Robert Brown的ID開始列出員工

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

// 從it1獲得索引#0的迭代器
employee_set::iterator it2=es.project<0>(it1); 

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

再看看一個更有趣的例子：

text_container tc;

// 取得索引#1(對單詞的有序索引)的視圖
text_container::nth_index<1>::type& sorted_index=tc.get<1>();

// 在所有"sister"前加上"older"

text_container::nth_index_iterator<1>::type it1=
  sorted_index.lower_bound("sister");
  
while(it1!=sorted_index.end()&&*it1=="sister"){
  // 將迭代器轉換為序列索引
  text_container::iterator it2=tc.project<0>(it1);

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

如果索引帶有 tags，project 也可以與標記一起使用。

Complexity and exception safety複雜度與異常安全性

multi_index_container 提供了與STL容器相同的時間複雜度與異常安全性保證。對於插入、替換和更新操作，迭代器與引用的有效性均可得到保證。

multi_index_container 的某些實例化事實上可以模擬 std::set, std::multiset 和 (帶有限制的) std::list，這些將在 techniques技巧 一節看到。這些模擬與原有的STL容器效率相近；有關複雜度保證的信息請查閱 reference參考 一節，有關效率的實際測試請查閱 performance性能 一節。

Boost.MultiIndex 指南

Boost.MultiIndex 指南

Index types索引的類型

Revised July 17th 2007

© Copyright 2003-2007 Joaquín M López Muñoz. Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)