一、說明

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

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

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

二、示例

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

示例 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';
}

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

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

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

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

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

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

因?yàn)榍秩胧饺萜鞑淮鎯?chǔ)副本，所以必須在銷毀它們之前從侵入式容器中移除對(duì)象。

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

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

因?yàn)榍秩胧饺萜骷炔环峙湟膊会尫艃?nèi)存，所以當(dāng)侵入式容器被破壞時(shí)，存儲(chǔ)在侵入式容器中的對(duì)象繼續(xù)存在。

由于從侵入式容器中刪除元素不會(huì)自動(dòng)破壞它們，因此容器提供了非標(biāo)準(zhǔn)擴(kuò)展。 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() 從列表中刪除一個(gè)元素并銷毀它。因?yàn)榍秩胧饺萜鞑恢缿?yīng)該如何銷毀元素，所以您需要向 pop_back_and_dispose() 傳遞一個(gè)知道如何銷毀元素的函數(shù)或函數(shù)對(duì)象。 pop_back_and_dispose() 將從列表中刪除對(duì)象，然后調(diào)用函數(shù)或函數(shù)對(duì)象并將指向要銷毀的對(duì)象的指針傳遞給它。示例 18.3 傳遞了一個(gè)調(diào)用 delete 的 lambda 函數(shù)。

在示例 18.3 中，只有動(dòng)物中的第三個(gè)元素可以使用 pop_back_and_dispose() 刪除。列表中的其他元素尚未使用 new 創(chuàng)建，因此不得使用 delete 銷毀。

Boost.Intrusive 支持另一種機(jī)制來鏈接元素的刪除和銷毀。

示例 18.4。使用自動(dòng)取消鏈接模式刪除和銷毀

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

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

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

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

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

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

示例 18.5 引入了使用另一個(gè)侵入式容器的掛鉤機(jī)制：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 派生了一個(gè)類，但示例 18.5 使用類 boost::intrusive::set_member_hook 來定義一個(gè)成員變量。

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

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

默認(rèn)情況下，侵入式容器期望在基類中定義掛鉤。如果將成員變量用作掛鉤（如示例 18.5），則必須告知侵入式容器使用哪個(gè)成員變量。這就是為什么動(dòng)物和類型掛鉤都被傳遞給 boost::intrusive::set 的原因。 hook 使用 boost::intrusive::member_hook 定義，每當(dāng)成員變量用作 hook 時(shí)都會(huì)使用它。 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 用于哈希容器。

到此這篇關(guān)于C++ Boost Intrusive庫(kù)示例精講的文章就介紹到這了,更多相關(guān)C++ Boost Intrusive內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論