Boost.MultiIndex Examples

性能

測試

Contents目錄

Example 1: 基本用法
Example 2: 以成員函數為關鍵字
Example 3: 用 ctor_args_list 構造 multi_index_containers
Example 4: 雙向 map
Example 5: 序列索引
Example 6: 複雜查詢和外鍵
Example 7: 組合鍵
Example 8: 散列索引
Example 9: 序列化與 MRU 列表
Example 10: 隨機訪問索引
Example 11: 索引重排
Example 12: 使用 Boost.Interprocess 分配器

Example 1: 基本用法

源程序請見 source code.

這是一個展示Boost.MultiIndex多索引功能的基礎例程，以employee記錄集合為例。

Example 2: 以函數為關鍵字

源程序請見 source code.

通常一個索引是以元素的某個成員變量作為關鍵字的，但是鍵提取器也可以被定義為以某個成員函數或全局函數的返回值作為關鍵字。這一點與一些關係數據庫引擎所支持的計算關鍵字概念類似。這個例子展示了如何使用預定義的 const_mem_fun 和 global_fun 鍵提取器來處理這種情況。

基於函數的關鍵字實際上並不常見，更多的是以成員函數的返回值作為中間值的情況。這意味著不能將 modify_key 用於這類鍵提取器，這是非常合理的強制要求。

Example 3: 用`ctor_args_list`構造 `multi_index_container`

源程序請見 source code.

我們給出了使用multi_index_container::ctor_arg_list的真實例子，在指南一節中有相關的定義和說明。這個程序組合了一組基於模算術的數字，x 與 y 等價當且僅當 (x%n)==(y%n)，n為固定數。

這個例子展示了如何用multi_index_container構造一個雙向map。雙向map即是一個元素類型為std::pair<const FromType,const ToType>的容器，要求沒有兩個元素的first 或 second 相同(std::map 僅保證 first 的唯一性)。基於兩個鍵的快速查找都已支持。這個程序模擬了一個小型的西班牙語-英詞詞典，提供兩個語言的單詞在線查找。

Example 5: 序列索引

源程序請見 source code.

一個序列索引與一個ordered_non_unique類型的索引可以組成一個支持快速查找的類-list結構。本例執行了一些指定文本的操作，如單詞計數和刪除選定單詞。

Example 6: 複雜查詢與外鍵

源程序請見 source code.

這個程序舉例說明了一些對複雜數據結構使用multi_index_container的高級技術。考慮一個存有汽車信息的 car_model 類。開始，car_model 可能會這樣定義：

struct car_model
{
  std::string model;
  std::string manufacturer;
  int         price;
};

具有關係數據庫知識的讀者可以輕易指出這個定義的一個缺點：manufacturer 成員對於所有相同廠家的汽車而言都是重複的。這非常浪費空間，而且當某個廠家改名時會很麻煩。參照關係數據庫設計中常用的方法，正確的設計應該是將廠家信息保存在另一個 multi_index_container 中，並在 car_model 中保存其指針：

struct car_manufacturer
{
  std::string name;
};

struct car_model
{
  std::string       model;
  car_manufacturer* manufacturer;
  int               price;
};

雖然Boost.MultiIndex中預定義了許多鍵提取器，以處理包括指針在內的多種情形(參見指南一節中的 Boost.MultiIndex 鍵提取器的高級特性)，但是這個例子的情況過於複雜，必須自行定義一個適當的鍵提取器。以下工具用於疊加兩個鍵提取器：

template<class KeyExtractor1,class KeyExtractor2>
struct key_from_key
{
public:
  typedef typename KeyExtractor1::result_type result_type;

  key_from_key(
    const KeyExtractor1& key1_=KeyExtractor1(),
    const KeyExtractor2& key2_=KeyExtractor2()):
    key1(key1_),key2(key2_)
  {}

  template<typename Arg>
  result_type operator()(Arg& arg)const
  {
    return key1(key2(arg));
  }

private:
  KeyExtractor1 key1;
  KeyExtractor2 key2;
};

這樣，從一個car_model得到其相關car_manufacturer的 name 域，可以這樣寫：

key_from_key<
  member<car_manufacturer,const std::string,&car_manufacturer::name>,
  member<car_model,const car_manufacturer *,car_model::manufacturer>
>

本程序請用戶輸入一個廠家名以及價格範圍，返回滿足要求的汽車型號。這是一個無法在單個操作完成的複雜查詢。大致上，執行該查詢的過程如下：

用equal_range以指定廠家名選出一些元素，
將這些元素放入一個以價格排序的 multi_index_container，
用lower_bound 和 upper_bound按價格進行選擇；

或者是：

用lower_bound 和 upper_bound按價格範圍選出一些元素，
將這些元素放入一個以廠家名排序的 multi_index_container，
用equal_range找出指定廠家的元素。

這個例子中使用的一個有趣技術是，構造一個中間的 multi_index_container。為了避免對像拷貝，用multi_index_container所定義的視圖類型應以car_mode指針作為元素，而不是以實際對像作為元素。這些視圖要補充適當的提領鍵提取器。

Example 7: 組合鍵

源程序請見 source code.

Boost.MultiIndex 為 composite_key 的構造提供了靈活的工具，以非平凡的排序標準來創建索引。該程序簡單地模擬了一個文件系統以及類-Unix的shell。一個文件項用以下結構表示：

struct file_entry
{
  std::string       name;
  unsigned          size;
  bool              is_dir; // true if the entry is a directory
  const file_entry* dir;    // directory this entry belongs in
};

文件項被保存在一個以兩個組合鍵為索引的 multi_index_container 中：

首先以目錄排序的原因是，文件所在位置依賴於shell命令如ls的當前目錄。我們僅模擬了三個shell命令：

cd [.|..|<directory>]
ls [-s] (-s 以文件大小順序輸入)
mkdir <directory>

當用戶在命令提示符處鍵入回車，程序將退出。

讀者可以嘗試為本程序增加更多的功能，如：

實現其它命令，如 cp；
處理絕對路徑；
在程序的多次運行間，用序列化serialization來保存和恢復文件系統的狀態。

Example 8: 散列索引

源程序請見 source code.

在需要快速查找且不關心排序信息時，散列索引可以替代有序索引。本例模擬了一個單詞計數器，使用散列索引來檢查重複的項。請與example 5的單詞計數算法進行比較。

Example 9: 序列化與 MRU 列表

源程序請見 source code.

序列化功能的一個主要用途是，允許程序員在多次執行之間保存用戶的上下文。本例程請用戶輸入一些單詞，並記錄下十個最近輸入的單詞，無論這些單詞是在本次或以前的會話中所輸入的。這個被序列化的數據結構，通常被稱為 MRU (最近使用)列表，具有一些有趣的特點：MRU列表的行為類似於普通的FIFO隊列，除了一點，即當插入一個已有項時，不會出現兩次，而只是將該項移到列表的前端。你可以在許多程序的類似於"最近打開文件"的菜單中見到這樣的特性。這個數據結構是由帶一個序列索引和一個hashed_unique類型索引的 multi_index_container 來實現的。

Example 10: 隨機訪問索引

源程序請見 source code.

本例繼續 example 5 中的文本容器例子，示範如何用隨機訪問索引來替換序列索引，實現通過位置來高效訪問，以及計算給定元素在容器中的偏移值。

Example 11: 索引重排

源程序請見 source code.

有一種說法，一副撲克牌要洗七次才能最好地混合。這一說法來自於數學家 Persi Diaconis 在 riffle shuffling 方面的工作: 這種洗牌的方法是將一副牌分兩同樣大小的兩份，然後將兩份牌一張隔一張地合併。重複這一過程七次，統計表明這時牌的分佈最接近於隨機排列。對 "隨機性" 的評估可以通過計算 rising sequences上升序列 來測算: 考慮序列 1,2, ... , n 的一個排列, 上升序列是指連續的最長子序列 m, m+1, ... , m+r，其滿足升序的條件。例如，排列 125364789 由兩個上升序列 1234 和 56789 組成, 可以將序列顯示為125364789. n 個元素的隨機排列中的上升序列平均數量為 (n+1)/2: 作為比照，一副排好的牌在一次 riffle shuffle 後，不可能超過兩個上升序列。隨著洗牌的次數增加，上升序列的平均數量接近於 (n+1)/2, 對於52張撲克牌來說，七次洗牌後的結果最為接近。Brad Mann 的論文 "How many times should you shuffle a deck of cards?" 提供了這個題目的嚴格討論。

這個例子程序對52張牌在重複洗牌後的上升序列平均數量進行評估，以完全隨機排列來估算。用以下容器來模擬一副牌：

multi_index_container<
  int,
  indexed_by<
    random_access<>,
    random_access<> 
  >
>

其中第一個索引保存牌的當前排列，第二個索引用於記住開始的位置。這種表示可以以線性時間實現一個高效的上升序列算法。rearrange 用於將洗牌操作應用於一個外部數據結構。

Example 12: 使用 Boost.Interprocess 分配器

源程序請見 source code.

Boost.MultiIndex 支持特殊的分配器，如由 Boost.Interprocess 所提供的分配器，這樣 multi_index_containers 可以被存放在共享內存中。本例示範了一個小型圖書數據庫的前端，該數據庫以一個保存在 Boost.Interprocess 內存映射文件中的 multi_index_container 來實現。讀者可以驗證一下，程序的多個實例可以同時正常工作，並可以立即看到由其它實例執行的數據庫修改。

性能

測試

Revised July 16th 2007