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

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

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

二、Boost.MultiIndex

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

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

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

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

類 boost::multi_index::hashed_non_unique 也是一個(gè)模板，它的唯一參數(shù)是計(jì)算哈希值的類。因?yàn)槿萜鞯膬蓚€(gè)接口都需要查找動(dòng)物，一個(gè)接口計(jì)算名稱的哈希值，而另一個(gè)接口計(jì)算腿數(shù)。

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

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

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

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

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

盡管您不需要知道接口的細(xì)節(jié)，因?yàn)樗鼈兪亲詣?dòng)從 nth_index 和 type 派生的，您仍然應(yīng)該了解訪問(wèn)的是哪種接口。由于接口在容器定義中是連續(xù)編號(hào)的，因此可以很容易地回答這個(gè)問(wèn)題，因?yàn)樗饕瑫r(shí)傳遞給 get() 和 nth_index。因此，legs_index 是一個(gè)通過(guò)腿查找動(dòng)物的哈希接口。

因?yàn)槊帧⑼鹊葦?shù)據(jù)可以作為MultiIndex容器的key，所以不能隨意改變。如果在通過(guò)名稱查找動(dòng)物后腿的數(shù)量發(fā)生了變化，則使用腿作為鍵的接口將不知道這種變化，也不知道需要計(jì)算新的哈希值。

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

為了避免必須從 MultiIndex 容器中刪除元素并插入新元素，Boost.MultiIndex 提供了成員函數(shù)來(lái)直接更改值。因?yàn)檫@些成員函數(shù)是在MultiIndex容器本身上操作的，并且因?yàn)槿萜髦械脑貨](méi)有被直接修改，所以所有的接口都會(huì)得到通知，可以計(jì)算出新的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 提供的每個(gè)接口都提供了成員函數(shù) modify()，它直接在容器上運(yùn)行。要修改的對(duì)象是通過(guò)作為第一個(gè)參數(shù)傳遞給 modify() 的迭代器來(lái)標(biāo)識(shí)的。第二個(gè)參數(shù)是一個(gè)函數(shù)或函數(shù)對(duì)象，它的唯一參數(shù)是存儲(chǔ)在容器中的類型的對(duì)象。函數(shù)或函數(shù)對(duì)象可以隨心所欲地改變?cè)?。示?12.2 說(shuō)明了如何使用成員函數(shù) modify() 來(lái)更改元素。

到目前為止，只引入了一個(gè)接口：boost::multi_index::hashed_non_unique，它計(jì)算一個(gè)不必唯一的哈希值。為了保證沒(méi)有值被存儲(chǔ)兩次，請(qǐng)使用 boost::multi_index::hashed_unique。請(qǐng)注意，如果值不滿足特定容器的所有接口的要求，則無(wú)法存儲(chǔ)值。如果一個(gè)接口不允許您多次存儲(chǔ)值，那么另一個(gè)接口是否允許它并不重要。

示例 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 作為第二個(gè)接口。這意味著不能將兩條腿數(shù)相同的動(dòng)物存儲(chǔ)在容器中，因?yàn)楣Ｖ迪嗤?/p>

該示例嘗試存儲(chǔ)與已存儲(chǔ)的貓具有相同腿數(shù)的狗。因?yàn)檫@違反了第二個(gè)接口具有唯一哈希值的要求，所以狗不會(huì)被存儲(chǔ)在容器中。因此，當(dāng)搜索有四只腿的動(dòng)物時(shí)，程序會(huì)顯示 1，因?yàn)橹挥胸埍淮鎯?chǔ)和計(jì)數(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 的最后三個(gè)接口：boost::multi_index::sequenced、boost::multi_index::ordered_non_unique 和 boost::multi_index::random_access。

接口 boost::multi_index::sequenced 允許您將 MultiIndex 容器視為類型為 std::list 的列表。元素按給定的順序存儲(chǔ)。

使用 boost::multi_index::ordered_non_unique 接口，對(duì)象會(huì)自動(dòng)排序。此接口要求您在定義容器時(shí)指定排序標(biāo)準(zhǔn)。示例 12.4 使用輔助類 boost::multi_index::member 按腿數(shù)對(duì)動(dòng)物類型的對(duì)象進(jìn)行排序。

boost::multi_index::ordered_non_unique 提供了特殊的成員函數(shù)來(lái)查找排序值中的特定范圍。程序使用lower_bound() 和upper_bound() 搜索至少有4 條但不超過(guò)8 條腿的動(dòng)物。因?yàn)樗鼈冃枰獙?duì)元素進(jìn)行排序，所以其他接口不提供這些成員函數(shù)。

最后引入的接口是 boost::multi_index::random_access，它允許您將 MultiIndex 容器視為 std::vector 類型的向量。兩個(gè)最突出的成員函數(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 的四個(gè)接口，本章的其余部分將重點(diǎn)介紹鍵提取器。已經(jīng)引入了一個(gè)關(guān)鍵提取器：boost::multi_index::member，它在 boost/multi_index/member.hpp 中定義。這個(gè)幫助類被稱為鍵提取器，因?yàn)樗试S您指定類的哪個(gè)成員變量應(yīng)該用作接口的鍵。

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

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

?:multi_index::hashed_unique 作為第二個(gè)接口。這意味著不能將兩條腿數(shù)相同的動(dòng)物存儲(chǔ)在容器中，因?yàn)楣Ｖ迪嗤?/p>

該示例嘗試存儲(chǔ)與已存儲(chǔ)的貓具有相同腿數(shù)的狗。因?yàn)檫@違反了第二個(gè)接口具有唯一哈希值的要求，所以狗不會(huì)被存儲(chǔ)在容器中。因此，當(dāng)搜索有四只腿的動(dòng)物時(shí)，程序會(huì)顯示 1，因?yàn)橹挥胸埍淮鎯?chǔ)和計(jì)數(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 使用存儲(chǔ)在容器中的元素作為鍵。這要求動(dòng)物類是可排序的，因?yàn)閯?dòng)物類型的對(duì)象將用作接口 boost::multi_index::ordered_unique 的鍵。在示例 12.5 中，這是通過(guò)重載的 operator< 實(shí)現(xiàn)的。

頭文件 boost/multi_index/mem_fun.hpp 定義了兩個(gè)鍵提取器——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 提供了另外兩個(gè)鍵提取器：boost::multi_index::global_fun 和 boost::multi_index::composite_key。前者可用于獨(dú)立或靜態(tài)成員函數(shù)，后者允許您設(shè)計(jì)一個(gè)由其他幾個(gè)密鑰提取器組成的密鑰提取器。

練習(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)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論