C++ Boost Intrusive庫範例精講

一、說明

Boost.Intrusive 是一個特別適合在高效能程式中使用的庫。該庫提供了建立侵入式容器的工具。這些容器替換了標準庫中的已知容器。它們的缺點是它們不能像 std::list 或 std::set 那樣容易使用。但它們有以下優點：

• 侵入式容器不會動態分配記憶體。對 push_back() 的呼叫不會導致使用 new 進行動態分配。這是侵入式容器可以提高效能的一個原因。
• 侵入式容器不會動態分配記憶體。對 push_bacIntrusive 容器的呼叫儲存原始物件，而不是副本。畢竟，它們不會動態分配記憶體。這帶來了另一個優勢：諸如 push_back() 之類的成員函數不會丟擲異常，因為它們既不分配記憶體也不復制物件。k() 不會導致使用 new 進行動態分配。這是侵入式容器可以提高效能的一個原因。

這些優勢通過更復雜的程式碼得到了回報，因為必須滿足先決條件才能將物件儲存在侵入式容器中。您不能將任意型別的物件儲存在侵入式容器中。例如，您不能將 std::string 型別的字串放入侵入式容器中；相反，您必須使用標準庫中的容器。

二、範例

範例 18.1 準備了一個類動物，以允許將此類物件儲存在侵入式列表中。

範例 18.1。使用 boost::intrusive::list

#include <boost/intrusive/list.hpp>
#include <string>
#include <utility>
#include <iostream>
using namespace boost::intrusive;
struct animal : public list_base_hook<>
{
  std::string name;
  int legs;
  animal(std::string n, int l) : name{std::move(n)}, legs{l} {}
};
int main()
{
  animal a1{"cat", 4};
  animal a2{"shark", 0};
  animal a3{"spider", 8};
  typedef list<animal> animal_list;
  animal_list animals;
  animals.push_back(a1);
  animals.push_back(a2);
  animals.push_back(a3);
  a1.name = "dog";
  for (const animal &a : animals)
    std::cout << a.name << 'n';
}

在列表中，總是從另一個元素存取一個元素，通常使用指標。如果侵入式列表要在沒有動態記憶體分配的情況下儲存動物型別的物件，則指標必須存在於某處以連線元素。

要將動物型別的物件儲存在侵入式列表中，該類必須提供侵入式列表所需的變數以連線元素。 Boost.Intrusive 提供了勾點——從這些類中繼承了所需的變數。要允許將動物型別的物件儲存在侵入列表中，動物必須從類 boost::intrusive::list_base_hook 派生。

勾點可以忽略實現細節。但是，可以安全地假設 boost::intrusive::list_base_hook 至少提供了兩個指標，因為 boost::intrusive::list 是一個雙向連結串列。多虧了基礎類別 boost::intrusive::list_base_hook，animal 定義了這兩個指標以允許連線這種型別的物件。

請注意 boost::intrusive::list_base_hook 是一個帶有預設模板引數的模板。因此，不需要顯式傳遞任何型別。

Boost.Intrusive 提供類 boost::intrusive::list 來建立一個侵入式列表。此類在 boost/intrusive/list.hpp 中定義，並像 std::list 一樣使用。可以使用 push_back() 新增元素，也可以迭代元素。

重要的是要了解侵入式容器不儲存副本；他們儲存原始物件。範例 18.1 將狗、鯊魚和蜘蛛寫入標準輸出，而不是貓。物件 a1 連結到列表中。這就是為什麼當程式遍歷列表中的元素並顯示名稱時名稱的更改是可見的。

因為侵入式容器不儲存副本，所以必須在銷燬它們之前從侵入式容器中移除物件。

範例 18.2。刪除和銷燬動態分配的物件

#include <boost/intrusive/list.hpp>
#include <string>
#include <utility>
#include <iostream>
using namespace boost::intrusive;
struct animal : public list_base_hook<>
{
  std::string name;
  int legs;
  animal(std::string n, int l) : name{std::move(n)}, legs{l} {}
};
int main()
{
  animal a1{"cat", 4};
  animal a2{"shark", 0};
  animal *a3 = new animal{"spider", 8};
  typedef list<animal> animal_list;
  animal_list animals;
  animals.push_back(a1);
  animals.push_back(a2);
  animals.push_back(*a3);
  animals.pop_back();
  delete a3;
  for (const animal &a : animals)
    std::cout << a.name << 'n';
}

Example18.2

example18.2 使用 new 建立一個動物型別的物件並將其插入到動物列表中。如果您想在不再需要時使用 delete 來銷燬該物件，則必須將其從列表中刪除。確保在銷燬之前從列表中刪除該物件——順序很重要。否則，侵入式容器元素中的指標可能會參照不再包含動物型別物件的記憶體位置。

因為侵入式容器既不分配也不釋放記憶體，所以當侵入式容器被破壞時，儲存在侵入式容器中的物件繼續存在。

由於從侵入式容器中刪除元素不會自動破壞它們，因此容器提供了非標準擴充套件。 pop_back_and_dispose() 就是這樣的成員函數之一。

範例 18.3。使用 pop_back_and_dispose() 刪除和銷燬

#include <boost/intrusive/list.hpp>
#include <string>
#include <utility>
#include <iostream>
using namespace boost::intrusive;
struct animal : public list_base_hook<>
{
  std::string name;
  int legs;
  animal(std::string n, int l) : name{std::move(n)}, legs{l} {}
};
int main()
{
  animal a1{"cat", 4};
  animal a2{"shark", 0};
  animal *a3 = new animal{"spider", 8};
  typedef list<animal> animal_list;
  animal_list animals;
  animals.push_back(a1);
  animals.push_back(a2);
  animals.push_back(*a3);
  animals.pop_back_and_dispose([](animal *a){ delete a; });
  for (const animal &a : animals)
    std::cout << a.name << 'n';
}

pop_back_and_dispose() 從列表中刪除一個元素並銷燬它。因為侵入式容器不知道應該如何銷燬元素，所以您需要向 pop_back_and_dispose() 傳遞一個知道如何銷燬元素的函數或函數物件。 pop_back_and_dispose() 將從列表中刪除物件，然後呼叫函數或函數物件並將指向要銷燬的物件的指標傳遞給它。範例 18.3 傳遞了一個呼叫 delete 的 lambda 函數。

在範例 18.3 中，只有動物中的第三個元素可以使用 pop_back_and_dispose() 刪除。列表中的其他元素尚未使用 new 建立，因此不得使用 delete 銷燬。

Boost.Intrusive 支援另一種機制來連結元素的刪除和銷燬。

範例 18.4。使用自動取消連結模式刪除和銷燬

#include <boost/intrusive/list.hpp>
#include <string>
#include <utility>
#include <iostream>
using namespace boost::intrusive;
typedef link_mode<auto_unlink> mode;
struct animal : public list_base_hook<mode>
{
  std::string name;
  int legs;
  animal(std::string n, int l) : name{std::move(n)}, legs{l} {}
};
int main()
{
  animal a1{"cat", 4};
  animal a2{"shark", 0};
  animal *a3 = new animal{"spider", 8};
  typedef constant_time_size<false> constant_time_size;
  typedef list<animal, constant_time_size> animal_list;
  animal_list animals;
  animals.push_back(a1);
  animals.push_back(a2);
  animals.push_back(*a3);
  delete a3;
  for (const animal &a : animals)
    std::cout << a.name << 'n';
}

Hooks 支援一個引數來設定連結模式。連結模式使用類別範本 boost::intrusive::link_mode 設定。如果 boost::intrusive::auto_unlink 作為模板引數傳遞，則選擇自動取消連結模式。

自動取消連結模式會在破壞容器時自動從侵入式容器中刪除元素。範例 18.4 僅將 cat 和 Shark 寫入標準輸出。

僅當所有侵入式容器提供的成員函數 size() 沒有恆定的複雜性時，才能使用自動取消連結模式。預設情況下，它具有恆定的複雜性，這意味著：size() 返回元素數量所花費的時間不取決於容器中儲存了多少元素。開啟或關閉恆定複雜性是優化效能的另一種選擇。

要更改 size() 的複雜性，請使用類別範本 boost::intrusive::constant_time_size，它需要 true 或 false 作為模板引數。 boost::intrusive::constant_time_size 可以作為第二個模板引數傳遞給侵入式容器，例如 boost::intrusive::list，以設定 size() 的複雜度。

現在我們已經看到侵入式容器支援連結模式，並且可以選擇設定 size() 的複雜度，看起來似乎還有很多東西需要發現，但實際上並沒有。例如，僅支援三種連結模式，而自動取消連結模式是您唯一需要了解的一種。如果您不選擇連結模式，則使用的預設模式足以滿足所有其他用例。

此外，沒有其他成員函數的選項。除了 boost::intrusive::constant_time_size 之外，沒有其他類是您需要了解的。

範例 18.5 引入了使用另一個侵入式容器的掛鉤機制：boost::intrusive::set。

範例 18.5。將 boost::intrusive::set 的勾點定義為成員變數

#include <boost/intrusive/set.hpp>
#include <string>
#include <utility>
#include <iostream>
using namespace boost::intrusive;
struct animal
{
  std::string name;
  int legs;
  set_member_hook<> set_hook;
  animal(std::string n, int l) : name{std::move(n)}, legs{l} {}
  bool operator<(const animal &a) const { return legs < a.legs; }
};
int main()
{
  animal a1{"cat", 4};
  animal a2{"shark", 0};
  animal a3{"spider", 8};
  typedef member_hook<animal, set_member_hook<>, &animal::set_hook> hook;
  typedef set<animal, hook> animal_set;
  animal_set animals;
  animals.insert(a1);
  animals.insert(a2);
  animals.insert(a3);
  for (const animal &a : animals)
    std::cout << a.name << 'n';
}

有兩種方法可以將勾點新增到類：從勾點派生類或將勾點定義為成員變數。雖然前面的範例從 boost::intrusive::list_base_hook 派生了一個類，但範例 18.5 使用類 boost::intrusive::set_member_hook 來定義一個成員變數。

請注意，成員變數的名稱無關緊要。但是，您使用的勾點類取決於侵入式容器。例如，要將掛鉤定義為侵入式列表的成員變數，請使用 boost::intrusive::list_member_hook 而不是 boost::intrusive::set_member_hook。

侵入式容器有不同的勾點，因為它們對元素有不同的要求。但是，您可以使用不同的幾個掛鉤來允許將物件儲存在多個侵入式容器中。 boost::intrusive::any_base_hook 和 boost::intrusive::any_member_hook 讓您可以將物件儲存在任何侵入式容器中。多虧了這些類，您不需要從多個勾點派生或將多個成員變數定義為勾點。

預設情況下，侵入式容器期望在基礎類別中定義掛鉤。如果將成員變數用作掛鉤（如範例 18.5），則必須告知侵入式容器使用哪個成員變數。這就是為什麼動物和型別掛鉤都被傳遞給 boost::intrusive::set 的原因。 hook 使用 boost::intrusive::member_hook 定義，每當成員變數用作 hook 時都會使用它。 boost::intrusive::member_hook 期望元素型別、勾點型別和指向成員變數的指標作為模板引數。

範例 18.5 按此順序將鯊魚、貓和蜘蛛寫入標準輸出。

除了本章介紹的類 boost::intrusive::list 和 boost::intrusive::set 之外，Boost.Intrusive 還提供了例如單連結串列的 boost::intrusive::slist 和 boost::intrusive ::unordered_set 用於雜湊容器。

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