C++ set_union(STL set_union)演算法詳解

2020-07-16 10:04:31
第一個版本的 set_union() 函數模板實現了集合的並集運算,它需要 5 個引數:兩個疊代器用來指定左運算元的集合範圍,另兩個疊代器用來作為右運算元的集合範圍,還有一個疊代器用來指向結果集合的存放位置。例如:
std::vector<int> set1 {1, 2, 3, 4, 5, 6};
std::vector<int> set2 {4, 5, 6, 7, 8, 9};
std::vector<int> result;
std::set_union(std::begin (set1), std::end(set1), // Range for set that is left operand
std::begin(set2), std::end(set2), // Range for set that is right operand
std::back_inserter(result));    // Destination for the result:1 2 3 4 5 6 7 8 9
set1 和 set2 中的初始值都是升序。如果它們都不是,那麼在使用 set_union() 演算法前,需要對 vector 容器排序。前面章節中介紹的 back_inserter() 函數模板定義在 iterator 標頭檔案中,它會呼叫傳入引數的函數 push_back() 來返回一個 back_inserter_iterator 物件。所以,set1 和 set2 並集中的元素會被儲存在 result 中。從並集運算得到的元素集合是容器元素的副本,因此這個運算並不會影響容器的原始內容。

當然,如果不儲存運算結果;可以用一個流疊代器輸出這些元素:
std::set_union(std::begin(set1), std::end(set1), std::begin(set2), std::end(set2),std::ostream_iterator<int> {std::cout, " "});
這裡的目的地址是一個 ostream_iterator,它可以將結果輸出到標準輸出流中。

第二個版本的 set_union() 函數模板接收的第 6 個引數是一個用來比較集合元素的函數物件。下面是它可能的一些用法:
std:: set<int, std::greater<int>>set1 {1, 2, 3, 4, 5, 6}; // Contains 6 5 4 3 2 1
std:: set<int, std:: greater<int>>set2 {4, 5, 6, 7, 8, 9}; // Contains 9 8 7 6 5 4
std::set<int, std::greater<int>>result; // Elements in descending sequence
std::set_union(std::begin(set1), std::end(set1),std::begin(set2), std::end(set2),std::inserter(result, std::begin(result)), // Result destination: 9 8 7 6 5 4 3 2 1
std::greater<int>()); // Function object for comparing elements
這一次的集合是 set 容器中的元素。這些元素是用函數物件 greater<int> 排序過的,因此它們都是升序。set_union() 的最後一個引數是一個用來比較集合元素的 greater<int> 型別的範例。結果的存放位置是 result 容器的 inserter_iterator,容器會呼叫成員函數 insert() 來新增元素。不能對 set 容器使用 back_insert_iterator,因為它沒有成員函數 push_back()。並集運算的結果是從兩個集合得到的元素的副本的降序集合。

這兩個版本的 set_union() 函數都會返回一個指向被複製元素段末尾後一個位置的疊代器。如果目的容器包含操作前的元素,這是很有用的。例如,如果目的容器是 vector 容器,set_union() 用 front_insert_iterator,如果用 back_inserter_iterator,可以用這個容器的結束疊代器,插入這個新元素,set_union() 返回的疊代器會指向第一個原始元素。