快捷導(dǎo)航

C++ Boost MultiIndex使用詳細(xì)介紹

更新時間：2022年11月08日 10:22:22 作者：無水先生

Boost是為C++語言標(biāo)準(zhǔn)庫提供擴展的一些C++程序庫的總稱。Boost庫是一個可移植、提供源代碼的C++庫，作為標(biāo)準(zhǔn)庫的后備，是C++標(biāo)準(zhǔn)化進(jìn)程的開發(fā)引擎之一，是為C++語言標(biāo)準(zhǔn)庫提供擴展的一些C++程序庫的總稱

一、關(guān)于BOOST的容器

容器是 C++ 中最有用的數(shù)據(jù)結(jié)構(gòu)之一。標(biāo)準(zhǔn)庫提供了許多容器，而 Boost 庫提供的更多。

Boost.MultiIndex 更進(jìn)一步：這個庫中的容器可以同時支持來自其他容器的多個接口。來自 Boost.MultiIndex 的容器就像合并的容器，并提供了與它們合并的所有容器的優(yōu)點。
Boost.Bimap 基于 Boost.MultiIndex。它提供了一個類似于 std::unordered_map 的容器，不同之處在于可以從兩側(cè)查找元素。因此，根據(jù)訪問容器的方式，任何一方都可能是關(guān)鍵。當(dāng)一側(cè)是關(guān)鍵時，另一側(cè)是價值。
Boost.Array 和 Boost.Unordered 定義了類 boost::array、boost::unordered_set 和 boost::unordered_map，它們是使用 C++11 添加到標(biāo)準(zhǔn)庫中的。
Boost.CircularBuffer 提供了一個容器，其最重要的屬性是當(dāng)一個值被添加到一個完整的循環(huán)緩沖區(qū)時，它將覆蓋緩沖區(qū)中的第一個元素。
Boost.Heap 提供了優(yōu)先級隊列的變體——類似于 std::priority_queue 的類。
Boost.Intrusive 允許您創(chuàng)建與標(biāo)準(zhǔn)庫中的容器不同的容器，這些容器既不復(fù)制也不移動對象。但是，要將對象添加到侵入性列表中，對象的類型必須滿足某些要求。
Boost.MultiArray 試圖簡化多維數(shù)組的使用。例如，可以將多維數(shù)組的一部分視為單獨的數(shù)組。
Boost.Container 是一個庫，它定義了與標(biāo)準(zhǔn)庫相同的容器。例如，如果您需要在多個平臺上支持一個程序，并且您希望避免由標(biāo)準(zhǔn)庫中特定于實現(xiàn)的差異引起的問題，則使用 Boost.Container 是有意義的。

二、Boost.MultiIndex

Boost.MultiIndex 使得定義支持任意數(shù)量接口的容器成為可能。雖然 std::vector 提供了一個支持直接訪問具有索引的元素的接口，而 std::set 提供了一個對元素進(jìn)行排序的接口，但 Boost.MultiIndex 允許您定義支持這兩個接口的容器。這樣的容器可用于使用索引并以排序方式訪問元素。

如果元素需要以不同的方式訪問并且通常需要存儲在多個容器中，則可以使用 Boost.MultiIndex。不必將元素同時存儲在向量和集合中，然后連續(xù)同步容器，您可以使用 Boost.MultiIndex 定義一個容器，該容器提供向量接口和集合接口。

如果您需要訪問基于多個不同屬性的元素，Boost.MultiIndex 也很有意義。在示例 12.1 中，通過名稱和腿數(shù)查找動物。如果沒有 Boost.MultiIndex，則需要兩個散列容器——一個按名稱查找動物，另一個按腿數(shù)查找它們。

示例 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 時，第一步是定義一個新容器。你必須決定你的新容器應(yīng)該支持哪些接口以及它應(yīng)該訪問哪些元素屬性。在 boost/multi_index_container.hpp 中定義的類 boost::multi_index::multi_index_container 用于每個容器定義。這是一個至少需要兩個參數(shù)的類模板。第一個參數(shù)是容器應(yīng)存儲的元素類型——在示例 12.1 中，這是一個名為動物的用戶定義類。第二個參數(shù)用于表示容器應(yīng)提供的不同索引。基于 Boost.MultiIndex 的容器的主要優(yōu)勢在于您可以通過不同的接口訪問元素。定義新容器時，可以指定接口的數(shù)量和類型。示例 12.1 中的容器需要支持按名稱或腿數(shù)搜索動物，因此定義了兩個接口。 Boost.MultiIndex 調(diào)用這些接口索引——這就是庫名稱的來源。

接口是在類 boost::multi_index::indexed_by 的幫助下定義的。每個接口都作為模板參數(shù)傳遞。示例 12.1 中使用了 boost::multi_index::hashed_non_unique 類型的兩個接口，在 boost/multi_index/hashed_index.hpp 中定義。使用這些接口使容器的行為類似于 std::unordered_set 并使用哈希值查找值。

類 boost::multi_index::hashed_non_unique 也是一個模板，它的唯一參數(shù)是計算哈希值的類。因為容器的兩個接口都需要查找動物，一個接口計算名稱的哈希值，而另一個接口計算腿數(shù)。

Boost.MultiIndex 提供了在 boost/multi_index/member.hpp 中定義的幫助類模板 boost::multi_index::member 來訪問成員變量。如示例 12.1 所示，已指定幾個參數(shù)以讓 boost::multi_index::member 知道應(yīng)該訪問動物的哪個成員變量以及成員變量的類型。

??? 盡管animal_multi 的定義起初看起來很復(fù)雜，但該類的工作方式就像一張地圖。動物的名字和腿數(shù)可以看作是一個鍵/值對。容器animal_multi 優(yōu)于std::unordered_map 之類的地圖的優(yōu)點是可以通過名稱或腿數(shù)查找動物。 animal_multi 支持兩種接口，一種基于名稱，一種基于腿數(shù)。接口確定哪個成員變量是鍵，哪個成員變量是值。

要訪問 MultiIndex 容器，您需要選擇一個接口。如果您使用 insert() 或 count() 直接訪問對象動物，則使用第一個接口。在示例 12.1 中，這是成員變量名稱的哈希容器。如果您需要不同的界面，則必須明確選擇它。

接口連續(xù)編號，從第一個接口的索引 0 開始。要訪問第二個接口（如示例 12.1 所示），請調(diào)用成員函數(shù) get() 并將所需接口的索引作為模板參數(shù)傳入。 ???

get() 的返回值看起來很復(fù)雜。它訪問一個名為 nth_index 的 MultiIndex 容器類，它又是一個模板。要使用的接口的索引必須指定為模板參數(shù)。該索引必須與傳遞給 get() 的索引相同。最后一步是訪問名為 type of nth_index 的類型定義。 type 的值表示對應(yīng)接口的類型。以下示例使用關(guān)鍵字 auto 來簡化代碼。

盡管您不需要知道接口的細(xì)節(jié)，因為它們是自動從 nth_index 和 type 派生的，您仍然應(yīng)該了解訪問的是哪種接口。由于接口在容器定義中是連續(xù)編號的，因此可以很容易地回答這個問題，因為索引同時傳遞給 get() 和 nth_index。因此，legs_index 是一個通過腿查找動物的哈希接口。

因為名字、腿等數(shù)據(jù)可以作為MultiIndex容器的key，所以不能隨意改變。如果在通過名稱查找動物后腿的數(shù)量發(fā)生了變化，則使用腿作為鍵的接口將不知道這種變化，也不知道需要計算新的哈希值。

就像 std::unordered_map 類型的容器中的鍵無法修改一樣，存儲在 MultiIndex 容器中的數(shù)據(jù)也無法修改。嚴(yán)格來說，存儲在 MultiIndex 容器中的所有數(shù)據(jù)都是常量。這包括不被任何接口使用的成員變量。即使沒有接口訪問腿，腿也不能改變。

為了避免必須從 MultiIndex 容器中刪除元素并插入新元素，Boost.MultiIndex 提供了成員函數(shù)來直接更改值。因為這些成員函數(shù)是在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 提供的每個接口都提供了成員函數(shù) modify()，它直接在容器上運行。要修改的對象是通過作為第一個參數(shù)傳遞給 modify() 的迭代器來標(biāo)識的。第二個參數(shù)是一個函數(shù)或函數(shù)對象，它的唯一參數(shù)是存儲在容器中的類型的對象。函數(shù)或函數(shù)對象可以隨心所欲地改變元素。示例 12.2 說明了如何使用成員函數(shù) 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 作為第二個接口。這意味著不能將兩條腿數(shù)相同的動物存儲在容器中，因為哈希值相同。

該示例嘗試存儲與已存儲的貓具有相同腿數(shù)的狗。因為這違反了第二個接口具有唯一哈希值的要求，所以狗不會被存儲在容器中。因此，當(dāng)搜索有四只腿的動物時，程序會顯示 1，因為只有貓被存儲和計數(shù)。

示例 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 接口，對象會自動排序。此接口要求您在定義容器時指定排序標(biāo)準(zhǔn)。示例 12.4 使用輔助類 boost::multi_index::member 按腿數(shù)對動物類型的對象進(jìn)行排序。

boost::multi_index::ordered_non_unique 提供了特殊的成員函數(shù)來查找排序值中的特定范圍。程序使用lower_bound() 和upper_bound() 搜索至少有4 條但不超過8 條腿的動物。因為它們需要對元素進(jìn)行排序，所以其他接口不提供這些成員函數(shù)。

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

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

現(xiàn)在我們已經(jīng)介紹了 Boost.MultiIndex 的四個接口，本章的其余部分將重點介紹鍵提取器。已經(jīng)引入了一個關(guān)鍵提取器：boost::multi_index::member，它在 boost/multi_index/member.hpp 中定義。這個幫助類被稱為鍵提取器，因為它允許您指定類的哪個成員變量應(yīng)該用作接口的鍵。

示例 12.5 引入了另外兩個密鑰提取器。

示例 12.5。密鑰提取器身份和 const_mem_fun

?:multi_index::hashed_unique 作為第二個接口。這意味著不能將兩條腿數(shù)相同的動物存儲在容器中，因為哈希值相同。

該示例嘗試存儲與已存儲的貓具有相同腿數(shù)的狗。因為這違反了第二個接口具有唯一哈希值的要求，所以狗不會被存儲在容器中。因此，當(dāng)搜索有四只腿的動物時，程序會顯示 1，因為只有貓被存儲和計數(shù)。

示例 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< 實現(xiàn)的。

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

Boost.MultiIndex 提供了另外兩個鍵提取器：boost::multi_index::global_fun 和 boost::multi_index::composite_key。前者可用于獨立或靜態(tài)成員函數(shù)，后者允許您設(shè)計一個由其他幾個密鑰提取器組成的密鑰提取器。

練習(xí)

使用 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";
}

到此這篇關(guān)于C++ Boost MultiIndex使用詳細(xì)介紹的文章就介紹到這了,更多相關(guān)C++ Boost MultiIndex內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: