一、說明

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

• 侵入式容器不會動態(tài)分配內存。對 push_back() 的調用不會導致使用 new 進行動態(tài)分配。這是侵入式容器可以提高性能的一個原因。
• 侵入式容器不會動態(tài)分配內存。對 push_bacIntrusive 容器的調用存儲原始對象，而不是副本。畢竟，它們不會動態(tài)分配內存。這帶來了另一個優(yōu)勢：諸如 push_back() 之類的成員函數不會拋出異常，因為它們既不分配內存也不復制對象。k() 不會導致使用 new 進行動態(tài)分配。這是侵入式容器可以提高性能的一個原因。

這些優(yōu)勢通過更復雜的代碼得到了回報，因為必須滿足先決條件才能將對象存儲在侵入式容器中。您不能將任意類型的對象存儲在侵入式容器中。例如，您不能將 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';
}

在列表中，總是從另一個元素訪問一個元素，通常使用指針。如果侵入式列表要在沒有動態(tài)內存分配的情況下存儲動物類型的對象，則指針必須存在于某處以連接元素。

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

鉤子可以忽略實現細節(jié)。但是，可以安全地假設 boost::intrusive::list_base_hook 至少提供了兩個指針，因為 boost::intrusive::list 是一個雙向鏈表。多虧了基類 boost::intrusive::list_base_hook，animal 定義了這兩個指針以允許連接這種類型的對象。

請注意 boost::intrusive::list_base_hook 是一個帶有默認模板參數的模板。因此，不需要顯式傳遞任何類型。

Boost.Intrusive 提供類 boost::intrusive::list 來創(chuàng)建一個侵入式列表。此類在 boost/intrusive/list.hpp 中定義，并像 std::list 一樣使用?？梢允褂?push_back() 添加元素，也可以迭代元素。

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

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

示例 18.2。刪除和銷毀動態(tài)分配的對象

#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 創(chuàng)建一個動物類型的對象并將其插入到動物列表中。如果您想在不再需要時使用 delete 來銷毀該對象，則必須將其從列表中刪除。確保在銷毀之前從列表中刪除該對象——順序很重要。否則，侵入式容器元素中的指針可能會引用不再包含動物類型對象的內存位置。

因為侵入式容器既不分配也不釋放內存，所以當侵入式容器被破壞時，存儲在侵入式容器中的對象繼續(xù)存在。

由于從侵入式容器中刪除元素不會自動破壞它們，因此容器提供了非標準擴展。 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 創(chuàng)建，因此不得使用 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() 返回元素數量所花費的時間不取決于容器中存儲了多少元素。打開或關閉恒定復雜性是優(yōu)化性能的另一種選擇。

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

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

此外，沒有其他成員函數的選項。除了 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內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論