C++優先順序佇列儲存智慧指標詳解

2020-07-16 10:04:31
現在主要講解智慧指標的使用。這和原生指標在本質上是相同的,除非想要自己負責刪除它們所指向的物件。當生成優先順序佇列或堆時,需要一個順序關係來確定元素的順序。當它們儲存的是原生指標或智慧指標時,總是需要為它們提供一個比較函數;如果不提供,就會對它們所儲存的指標而不是指標所指向的物件進行比較,這肯定不是我們所希望的。

讓我們考慮一下,如何定義一個儲存指標的 priority_queue,指標則指向自由儲存區的 string 物件。為了縮短程式碼中語句的長度,假定下面的 using 宣告對本節隨後的內容都生效:
using std::string;
using std::shared_ptr;
using std::unique_ptr;
我們需要定義一個用來比較物件的函數物件,被比較的物件由 shared_ptr<string> 型別的指標指向。按如下所示定義比較函數:
auto comp = [] (const shared_ptr<string>& wp1, const shared_ptr<string>& wp2)
{ return *wp1 < *wp2; };
這裡定義了一個 lambda 表示式 comp,可以用來比較兩個智慧指標所指向的物件。對 lambda 表示式命名的原因是需要將它作為 priority_queue 模板的型別引數。下面是優先順序佇列的定義:
std::priority_queue<shared_ptr<string>,std::vector<shared_ptr<string>>, decltype(comp)>wordsl {comp};
第一個模板型別引數是所儲存元素的型別,第二個用來儲存元素的容器的型別,第三個是用來比較元素的函數物件的型別。我們必須指定第三個模板型別引數,因為 lambda 表示式的型別和預設比較型別 std::less<T> 不同。

仍然可以指定一個外部容器來初始化存放指標的 priority_queue:
std::vector<shared_ptr<string>>init { std::make—shared<string> ("one"),std::make_shared<string>("two"), std::make_shared<string>("three"),std::make_shared<string> ("four") };
std::priority_queue<shared_ptr<string>, std::vector<shared_ptr<string>>, decltype(comp)>words(comp, init);
vector 容器 init 是用 make_s!iared<string>() 生成的初始值。優先順序佇列建構函式的引數是一個定義了元素比較方式的物件以及一個提供初始化元素的容器。先複製 vector 中的智慧指標,然後用它們來初始化優先順序佇列 words。當然,也可以用另一個容器中的元素來初始化優先順序佇列,這意味不能使用 unique_ptr<string> 元素,必須是shared_ptr<string>。

如果初始元素不需要保留,可以用 priority_queue 物件的成員函數 emplace() 直接在容器中生成它們:
std::priority_queue<shared_ptr<string>,std::vector<shared_ptr<string>>, decltype(comp)>words1{comp};

words1.emplace(new string {"one"});
words1.emplace(new string {"two”});
words1.emplace(new string {"three"});
words1.emplace(new string {"five"});
words1 的成員函數 emplace() 會呼叫它們所儲存物件的型別的建構函式,也就是 shared_ ptr<string> 的建構函式。這個建構函式的引數是自由儲存區的一個 string 物件的地址, string 物件是由 emplace() 的參數列達式生成的。這段程式碼會在優先順序佇列中儲存 4 個 string 物件的指標,它們分別指向"two"、"three"、"one"、"five"這 4 個物件。元素在優先順序佇列中的順序取決於這一節前面定義的 comp。

當然,如果不需要保留初始元素,可以用優先順序佇列儲存 unique_ptr<string> 元素。例如:
auto ucomp = [](const std::unique_ptr<string>& wp1, const std::unique_ptr<string>& wp2){ return *wp1 < *wp2; };
std::priority_queue<std::unique_ptr<string>, std::vector<std::unique_ptr<string»,decltype(ucomp)> words2 {ucomp};
這個定義比較運算的 lambda 表示式可以接受 unique_ptr<string> 物件的參照。我們需要為這個優先順序佇列指定 3 個模板型別引數,因為我們需要指定比較函數的型別。第二個模板型別引數可以是 deque<String>,它是預設使用的容器型別。也可以用 emplace() 向優先順序佇列中新增元素:
words2.emplace(new string{"one"});
words2.emplace(new string {"two"});
words2.emplace (new string {"three"});
words2.emplace(new string {"five"});
或者,也可以使用 push():
words2.push(std::make_unique<string>("one"));
words2.push(std::make_unique<string>("two"));
words2.push(std::make_unique<string>("three"));
words2.push(std::make_unique<string>("five"));
make_imique<string>() 返回的物件會被移到容器中,這是由右值參照引數版的 push() 自動選擇的。