C++ Boost MultiIndex使用詳細介紹

一、關於BOOST的容器

容器是 C++ 中最有用的資料結構之一。標準庫提供了許多容器，而 Boost 庫提供的更多。

• Boost.MultiIndex 更進一步：這個庫中的容器可以同時支援來自其他容器的多個介面。來自 Boost.MultiIndex 的容器就像合併的容器，並提供了與它們合併的所有容器的優點。
• Boost.Bimap 基於 Boost.MultiIndex。它提供了一個類似於 std::unordered_map 的容器，不同之處在於可以從兩側查詢元素。因此，根據存取容器的方式，任何一方都可能是關鍵。當一側是關鍵時，另一側是價值。
• Boost.Array 和 Boost.Unordered 定義了類 boost::array、boost::unordered_set 和 boost::unordered_map，它們是使用 C++11 新增到標準庫中的。
• Boost.CircularBuffer 提供了一個容器，其最重要的屬性是當一個值被新增到一個完整的迴圈緩衝區時，它將覆蓋緩衝區中的第一個元素。
• Boost.Heap 提供了優先順序佇列的變體——類似於 std::priority_queue 的類。
• Boost.Intrusive 允許您建立與標準庫中的容器不同的容器，這些容器既不復制也不移動物件。但是，要將物件新增到侵入性列表中，物件的型別必須滿足某些要求。
• Boost.MultiArray 試圖簡化多維陣列的使用。例如，可以將多維陣列的一部分視為單獨的陣列。
• Boost.Container 是一個庫，它定義了與標準庫相同的容器。例如，如果您需要在多個平臺上支援一個程式，並且您希望避免由標準庫中特定於實現的差異引起的問題，則使用 Boost.Container 是有意義的。

二、Boost.MultiIndex

Boost.MultiIndex 使得定義支援任意數量介面的容器成為可能。雖然 std::vector 提供了一個支援直接存取具有索引的元素的介面，而 std::set 提供了一個對元素進行排序的介面，但 Boost.MultiIndex 允許您定義支援這兩個介面的容器。這樣的容器可用於使用索引並以排序方式存取元素。

如果元素需要以不同的方式存取並且通常需要儲存在多個容器中，則可以使用 Boost.MultiIndex。不必將元素同時儲存在向量和集合中，然後連續同步容器，您可以使用 Boost.MultiIndex 定義一個容器，該容器提供向量介面和集合介面。

如果您需要存取基於多個不同屬性的元素，Boost.MultiIndex 也很有意義。在範例 12.1 中，通過名稱和腿數查詢動物。如果沒有 Boost.MultiIndex，則需要兩個雜湊容器——一個按名稱查詢動物，另一個按腿數查詢它們。

範例 12.1。使用 boost::multi_index::multi_index_container

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <string>
#include <iostream>
using namespace boost::multi_index;
struct animal
{
  std::string name;
  int legs;
};
typedef multi_index_container<
  animal,
  indexed_by<
    hashed_non_unique<
      member<
        animal, std::string, &animal::name
      >
    >,
    hashed_non_unique<
      member<
        animal, int, &animal::legs
      >
    >
  >
> animal_multi;
int main()
{
  animal_multi animals;
  animals.insert({"cat", 4});
  animals.insert({"shark", 0});
  animals.insert({"spider", 8});
  std::cout << animals.count("cat") << 'n';
  const animal_multi::nth_index<1>::type &legs_index = animals.get<1>();
  std::cout << legs_index.count(8) << 'n';
}

​​​ 使用 Boost.MultiIndex 時，第一步是定義一個新容器。你必須決定你的新容器應該支援哪些介面以及它應該存取哪些元素屬性。 在 boost/multi_index_container.hpp 中定義的類 boost::multi_index::multi_index_container 用於每個容器定義。這是一個至少需要兩個引數的類別範本。第一個引數是容器應儲存的元素型別——在範例 12.1 中，這是一個名為動物的使用者定義類。第二個引數用於表示容器應提供的不同索引。 基於 Boost.MultiIndex 的容器的主要優勢在於您可以通過不同的介面存取元素。定義新容器時，可以指定介面的數量和型別。範例 12.1 中的容器需要支援按名稱或腿數搜尋動物，因此定義了兩個介面。 Boost.MultiIndex 呼叫這些介面索引——這就是庫名稱的來源。

介面是在類 boost::multi_index::indexed_by 的幫助下定義的。每個介面都作為模板引數傳遞。範例 12.1 中使用了 boost::multi_index::hashed_non_unique 型別的兩個介面，在 boost/multi_index/hashed_index.hpp 中定義。使用這些介面使容器的行為類似於 std::unordered_set 並使用雜湊值查詢值。

類 boost::multi_index::hashed_non_unique 也是一個模板，它的唯一引數是計算雜湊值的類。因為容器的兩個介面都需要查詢動物，一個介面計算名稱的雜湊值，而另一個介面計算腿數。

Boost.MultiIndex 提供了在 boost/multi_index/member.hpp 中定義的幫助類別範本 boost::multi_index::member 來存取成員變數。如範例 12.1 所示，已指定幾個引數以讓 boost::multi_index::member 知道應該存取動物的哪個成員變數以及成員變數的型別。

​​​ 儘管animal_multi 的定義起初看起來很複雜，但該類的工作方式就像一張地圖。動物的名字和腿數可以看作是一個鍵/值對。容器animal_multi 優於std::unordered_map 之類的地圖的優點是可以通過名稱或腿數查詢動物。 animal_multi 支援兩種介面，一種基於名稱，一種基於腿數。介面確定哪個成員變數是鍵，哪個成員變數是值。

要存取 MultiIndex 容器，您需要選擇一個介面。如果您使用 insert() 或 count() 直接存取物件動物，則使用第一個介面。在範例 12.1 中，這是成員變數名稱的雜湊容器。如果您需要不同的介面，則必須明確選擇它。

介面連續編號，從第一個介面的索引 0 開始。要存取第二個介面（如範例 12.1 所示），請呼叫成員函數 get() 並將所需介面的索引作為模板引數傳入。 ​​​

get() 的返回值看起來很複雜。它存取一個名為 nth_index 的 MultiIndex 容器類，它又是一個模板。要使用的介面的索引必須指定為模板引數。該索引必須與傳遞給 get() 的索引相同。最後一步是存取名為 type of nth_index 的型別定義。 type 的值表示對應介面的型別。以下範例使用關鍵字 auto 來簡化程式碼。

儘管您不需要知道介面的細節，因為它們是自動從 nth_index 和 type 派生的，您仍然應該瞭解存取的是哪種介面。由於介面在容器定義中是連續編號的，因此可以很容易地回答這個問題，因為索引同時傳遞給 get() 和 nth_index。因此，legs_index 是一個通過腿查詢動物的雜湊介面。

因為名字、腿等資料可以作為MultiIndex容器的key，所以不能隨意改變。如果在通過名稱查詢動物後腿的數量發生了變化，則使用腿作為鍵的介面將不知道這種變化，也不知道需要計算新的雜湊值。

就像 std::unordered_map 型別的容器中的鍵無法修改一樣，儲存在 MultiIndex 容器中的資料也無法修改。嚴格來說，儲存在 MultiIndex 容器中的所有資料都是常數。這包括不被任何介面使用的成員變數。即使沒有介面存取腿，腿也不能改變。

為了避免必須從 MultiIndex 容器中刪除元素並插入新元素，Boost.MultiIndex 提供了成員函數來直接更改值。因為這些成員函數是在MultiIndex容器本身上操作的，並且因為容器中的元素沒有被直接修改，所以所有的介面都會得到通知，可以計算出新的hash值。

範例 12.2。使用 modify() 更改 MultiIndex 容器中的元素

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <string>
#include <iostream>
using namespace boost::multi_index;
struct animal
{
  std::string name;
  int legs;
};
typedef multi_index_container<
  animal,
  indexed_by<
    hashed_non_unique<
      member<
        animal, std::string, &animal::name
      >
    >,
    hashed_non_unique<
      member<
        animal, int, &animal::legs
      >
    >
  >
> animal_multi;
int main()
{
  animal_multi animals;
  animals.insert({"cat", 4});
  animals.insert({"shark", 0});
  animals.insert({"spider", 8});
  auto &legs_index = animals.get<1>();
  auto it = legs_index.find(4);
  legs_index.modify(it, [](animal &a){ a.name = "dog"; });
  std::cout << animals.count("dog") << 'n';
}

Boost.MultiIndex 提供的每個介面都提供了成員函數 modify()，它直接在容器上執行。要修改的物件是通過作為第一個引數傳遞給 modify() 的迭代器來標識的。第二個引數是一個函數或函數物件，它的唯一引數是儲存在容器中的型別的物件。函數或函數物件可以隨心所欲地改變元素。範例 12.2 說明了如何使用成員函數 modify() 來更改元素。

到目前為止，只引入了一個介面：boost::multi_index::hashed_non_unique，它計算一個不必唯一的雜湊值。為了保證沒有值被儲存兩次，請使用 boost::multi_index::hashed_unique。請注意，如果值不滿足特定容器的所有介面的要求，則無法儲存值。如果一個介面不允許您多次儲存值，那麼另一個介面是否允許它並不重要。

範例 12.3。具有 boost::multi_index::hashed_unique 的 MultiIndex 容器

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <string>
#include <iostream>
using namespace boost::multi_index;
struct animal
{
  std::string name;
  int legs;
};
typedef multi_index_container<
  animal,
  indexed_by<
    hashed_non_unique<
      member<
        animal, std::string, &animal::name
      >
    >,
    hashed_unique<
      member<
        animal, int, &animal::legs
      >
    >
  >
> animal_multi;
int main()
{
  animal_multi animals;
  animals.insert({"cat", 4});
  animals.insert({"shark", 0});
  animals.insert({"dog", 4});
  auto &legs_index = animals.get<1>();
  std::cout << legs_index.count(4) << 'n';
}

範例 12.3 中的容器使用 boost::multi_index::hashed_unique 作為第二個介面。這意味著不能將兩條腿數相同的動物儲存在容器中，因為雜湊值相同。

該範例嘗試儲存與已儲存的貓具有相同腿數的狗。因為這違反了第二個介面具有唯一雜湊值的要求，所以狗不會被儲存在容器中。因此，當搜尋有四隻腿的動物時，程式會顯示 1，因為只有貓被儲存和計數。

範例 12.4。介面排序、ordered_non_unique 和 random_access

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/member.hpp>
#include <string>
#include <iostream>
using namespace boost::multi_index;
struct animal
{
  std::string name;
  int legs;
};
typedef multi_index_container<
  animal,
  indexed_by<
    sequenced<>,
    ordered_non_unique<
      member<
        animal, int, &animal::legs
      >
    >,
    random_access<>
  >
> animal_multi;
int main()
{
  animal_multi animals;
  animals.push_back({"cat", 4});
  animals.push_back({"shark", 0});
  animals.push_back({"spider", 8});
  auto &legs_index = animals.get<1>();
  auto it = legs_index.lower_bound(4);
  auto end = legs_index.upper_bound(8);
  for (; it != end; ++it)
    std::cout << it->name << 'n';
  const auto &rand_index = animals.get<2>();
  std::cout << rand_index[0].name << 'n';
}

Example12.4

範例 12.3 中的容器使用 boost：​

example2.4 介紹了 Boost.MultiIndex 的最後三個介面：boost::multi_index::sequenced、boost::multi_index::ordered_non_unique 和 boost::multi_index::random_access。

介面 boost::multi_index::sequenced 允許您將 MultiIndex 容器視為型別為 std::list 的列表。元素按給定的順序儲存。

使用 boost::multi_index::ordered_non_unique 介面，物件會自動排序。此介面要求您在定義容器時指定排序標準。範例 12.4 使用輔助類 boost::multi_index::member 按腿數對動物型別的物件進行排序。

boost::multi_index::ordered_non_unique 提供了特殊的成員函數來查詢排序值中的特定範圍。程式使用lower_bound() 和upper_bound() 搜尋至少有4 條但不超過8 條腿的動物。因為它們需要對元素進行排序，所以其他介面不提供這些成員函數。

最後引入的介面是 boost::multi_index::random_access，它允許您將 MultiIndex 容器視為 std::vector 型別的向量。兩個最突出的成員函數是 operator[] 和 at()。

boost::multi_index::random_access 包括 boost::multi_index::sequenced。使用 boost::multi_index::random_access，boost::multi_index::sequenced 的所有成員函數也都可用。

現在我們已經介紹了 Boost.MultiIndex 的四個介面，本章的其餘部分將重點介紹鍵提取器。已經引入了一個關鍵提取器：boost::multi_index::member，它在 boost/multi_index/member.hpp 中定義。這個幫助類被稱為鍵提取器，因為它允許您指定類的哪個成員變數應該用作介面的鍵。

範例 12.5 引入了另外兩個金鑰提取器。

範例 12.5。金鑰提取器身份和 const_mem_fun

​:multi_index::hashed_unique 作為第二個介面。這意味著不能將兩條腿數相同的動物儲存在容器中，因為雜湊值相同。

該範例嘗試儲存與已儲存的貓具有相同腿數的狗。因為這違反了第二個介面具有唯一雜湊值的要求，所以狗不會被儲存在容器中。因此，當搜尋有四隻腿的動物時，程式會顯示 1，因為只有貓被儲存和計數。

範例 12.4。介面排序、ordered_non_unique 和 random_access

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/mem_fun.hpp>
#include <string>
#include <utility>
#include <iostream>
using namespace boost::multi_index;
class animal
{
public:
  animal(std::string name, int legs) : name_{std::move(name)},
    legs_(legs) {}
  bool operator<(const animal &a) const { return legs_ < a.legs_; }
  const std::string &name() const { return name_; }
private:
  std::string name_;
  int legs_;
};
typedef multi_index_container<
  animal,
  indexed_by<
    ordered_unique<
      identity<animal>
    >,
    hashed_unique<
      const_mem_fun<
        animal, const std::string&, &animal::name
      >
    >
  >
> animal_multi;
int main()
{
  animal_multi animals;
  animals.emplace("cat", 4);
  animals.emplace("shark", 0);
  animals.emplace("spider", 8);
  std::cout << animals.begin()->name() << 'n';
  const auto &name_index = animals.get<1>();
  std::cout << name_index.count("shark") << 'n';
}

在 boost/multi_index/identity.hpp 中定義的鍵提取器 boost::multi_index::identity 使用儲存在容器中的元素作為鍵。這要求動物類是可排序的，因為動物型別的物件將用作介面 boost::multi_index::ordered_unique 的鍵。在範例 12.5 中，這是通過過載的 operator< 實現的。

標頭檔案 boost/multi_index/mem_fun.hpp 定義了兩個鍵提取器——boost::multi_index::const_mem_fun 和 boost::multi_index::mem_fun——它們使用成員函數的返回值作為鍵。在範例 12.5 中，name() 的返回值就是以這種方式使用的。 boost::multi_index::const_mem_fun 用於常數成員函數，而 boost::multi_index::mem_fun 用於非常數成員函數。

Boost.MultiIndex 提供了另外兩個鍵提取器：boost::multi_index::global_fun 和 boost::multi_index::composite_key。前者可用於獨立或靜態成員函數，後者允許您設計一個由其他幾個金鑰提取器組成的金鑰提取器。

練習

使用 Boost.MultiIndex 定義類animals_container：

#include <string>
#include <vector>
#include <iostream>
struct animal
{
    std::string name;
    int legs;
    bool has_tail;
};
class animals_container
{
public:
    void add(animal a)
    {
        // TODO: Implement this member function.
    }
    const animal *find_by_name(const std::string &name) const
    {
        // TODO: Implement this member function.
        return nullptr;
    }
    std::vector<animal> find_by_legs(int from, int to) const
    {
        // TODO: Implement this member function.
        return {};
    }
    std::vector<animal> find_by_tail(bool has_tail) const
    {
        // TODO: Implement this member function.
        return {};
    }
};
int main()
{
    animals_container animals;
    animals.add({ "cat", 4, true });
    animals.add({ "ant", 6, false });
    animals.add({ "spider", 8, false });
    animals.add({ "shark", 0, false });
    const animal *a = animals.find_by_name("cat");
    if (a)
        std::cout << "cat has " << a->legs << " legsn";
    auto animals_with_6_to_8_legs = animals.find_by_legs(6, 9);
    for (auto a : animals_with_6_to_8_legs)
        std::cout << a.name << " has " << a.legs << " legsn";
    auto animals_without_tail = animals.find_by_tail(false);
    for (auto a : animals_without_tail)
        std::cout << a.name << " has no tailn";
}

到此這篇關於C++ Boost MultiIndex使用詳細介紹的文章就介紹到這了,更多相關C++ Boost MultiIndex內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！