C++的Boost?MultiIndex如何使用

今天小編給大家分享一下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 定義了兩個鍵提取器&mdash;&mdash;boost::multi_index::const_mem_fun 和 boost::multi_index::mem_fun&mdash;&mdash;它們使用成員函數的返回值作為鍵。在示例 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 << " legs\n";
    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 << " legs\n";
    auto animals_without_tail = animals.find_by_tail(false);
    for (auto a : animals_without_tail)
        std::cout << a.name << " has no tail\n";
}

以上就是“C++的Boost MultiIndex如何使用”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。