一、說明

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

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

這些優(yōu)勢通過更復(fù)雜的代碼得到了回報，因為必須滿足先決條件才能將對象存儲在侵入式容器中。您不能將任意類型的對象存儲在侵入式容器中。例如，您不能將 std::string 類型的字符串放入侵入式容器中；相反，您必須使用標(biāo)準(zhǔn)庫中的容器。

二、示例

示例 18.1 準(zhǔn)備了一個類動物，以允許將此類對象存儲在侵入式列表中。

示例 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)內(nèi)存分配的情況下存儲動物類型的對象，則指針必須存在于某處以連接元素。

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

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

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

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

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

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

示例 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 來銷毀該對象，則必須將其從列表中刪除。確保在銷毀之前從列表中刪除該對象——順序很重要。否則，侵入式容器元素中的指針可能會引用不再包含動物類型對象的內(nèi)存位置。

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

由于從侵入式容器中刪除元素不會自動破壞它們，因此容器提供了非標(biāo)準(zhǔn)擴展。 pop_back_and_dispose() 就是這樣的成員函數(shù)之一。

示例 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() 從列表中刪除一個元素并銷毀它。因為侵入式容器不知道應(yīng)該如何銷毀元素，所以您需要向 pop_back_and_dispose() 傳遞一個知道如何銷毀元素的函數(shù)或函數(shù)對象。 pop_back_and_dispose() 將從列表中刪除對象，然后調(diào)用函數(shù)或函數(shù)對象并將指向要銷毀的對象的指針傳遞給它。示例 18.3 傳遞了一個調(diào)用 delete 的 lambda 函數(shù)。

在示例 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 支持一個參數(shù)來設(shè)置鏈接模式。鏈接模式使用類模板 boost::intrusive::link_mode 設(shè)置。如果 boost::intrusive::auto_unlink 作為模板參數(shù)傳遞，則選擇自動取消鏈接模式。

自動取消鏈接模式會在破壞容器時自動從侵入式容器中刪除元素。示例 18.4 僅將 cat 和 Shark 寫入標(biāo)準(zhǔn)輸出。

僅當(dāng)所有侵入式容器提供的成員函數(shù) size() 沒有恒定的復(fù)雜性時，才能使用自動取消鏈接模式。默認情況下，它具有恒定的復(fù)雜性，這意味著：size() 返回元素數(shù)量所花費的時間不取決于容器中存儲了多少元素。打開或關(guān)閉恒定復(fù)雜性是優(yōu)化性能的另一種選擇。

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

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

此外，沒有其他成員函數(shù)的選項。除了 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';
}

有兩種方法可以將鉤子添加到類：從鉤子派生類或?qū)^子定義為成員變量。雖然前面的示例從 boost::intrusive::list_base_hook 派生了一個類，但示例 18.5 使用類 boost::intrusive::set_member_hook 來定義一個成員變量。

請注意，成員變量的名稱無關(guān)緊要。但是，您使用的鉤子類取決于侵入式容器。例如，要將掛鉤定義為侵入式列表的成員變量，請使用 boost::intrusive::list_member_hook 而不是 boost::intrusive::set_member_hook。

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

默認情況下，侵入式容器期望在基類中定義掛鉤。如果將成員變量用作掛鉤（如示例 18.5），則必須告知侵入式容器使用哪個成員變量。這就是為什么動物和類型掛鉤都被傳遞給 boost::intrusive::set 的原因。 hook 使用 boost::intrusive::member_hook 定義，每當(dāng)成員變量用作 hook 時都會使用它。 boost::intrusive::member_hook 期望元素類型、鉤子類型和指向成員變量的指針作為模板參數(shù)。

示例 18.5 按此順序?qū)Ⅴ忯~、貓和蜘蛛寫入標(biāo)準(zhǔn)輸出。

除了本章介紹的類 boost::intrusive::list 和 boost::intrusive::set 之外，Boost.Intrusive 還提供了例如單鏈表的 boost::intrusive::slist 和 boost::intrusive ::unordered_set 用于哈希容器。