名稱空間
變體
操作

std::ranges::set_union, std::ranges::set_union_result

來自 cppreference.com
< cpp‎ | 演算法‎ | 範圍
 
C++
 
演算法庫
有約束演算法與針對範圍的演算法 (C++20)
有約束的演算法，例如 ranges::copy、 ranges::sort 等……
執行策略 (C++17)
排序及相關操作
劃分操作
排序操作
二分搜尋操作
（於已劃分範圍上）
集合操作（於已排序範圍上）
歸併操作（於已排序範圍上）
堆操作
最小/最大值操作
(C++11)
(C++17)
字典序比較操作
(C++20)
排列操作
C 庫
數值操作
未初始化記憶體上的操作
 
受約束演算法
此選單中的所有名稱均屬於名稱空間 std::ranges
非修改序列操作
修改序列操作
劃分操作
排序操作
二分查詢操作（在已排序的範圍內）
       
       
    
集合操作（於已排序範圍上）
堆操作
最小/最大值操作
       
       
排列操作
摺疊操作
數值操作
(C++23)            
對未初始化儲存的操作
返回型別
 
定義於標頭檔案 <algorithm>
呼叫簽名 (Call signature)
template< std::input_iterator I1, std::sentinel_for<I1> S1,

          std::input_iterator I2, std::sentinel_for<I2> S2,
          std::weakly_incrementable O, class Comp = ranges::less,
          class Proj1 = std::identity, class Proj2 = std::identity >
requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2>
constexpr set_union_result<I1, I2, O>
    set_union( I1 first1, S1 last1, I2 first2, S2 last2,
               O result, Comp comp = {},

               Proj1 proj1 = {}, Proj2 proj2 = {} );
 (1) (C++20 起)
template< ranges::input_range R1, ranges::input_range R2,

          std::weakly_incrementable O, class Comp = ranges::less,
          class Proj1 = std::identity, class Proj2 = std::identity >
requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>,
                        O, Comp, Proj1, Proj2>
constexpr set_union_result<ranges::borrowed_iterator_t<R1>,
                           ranges::borrowed_iterator_t<R2>, O>
    set_union( R1&& r1, R2&& r2, O result, Comp comp = {},

               Proj1 proj1 = {}, Proj2 proj2 = {} );
 (2) (C++20 起)
輔助型別
template< class I1, class I2, class O >
using set_union_result = ranges::in_in_out_result<I1, I2, O>;
 (3) (C++20 起)

構造一個以 result 開頭的已排序並集，它由兩個已排序輸入範圍 [first1, last1) 和 [first2, last2) 中一個或兩個都存在的元素組成。

如果某個元素在 [first1, last1) 中出現 m 次，在 [first2, last2) 中出現 n 次，那麼所有 m 個元素將從 [first1, last1) 複製到 result，保持順序，然後恰好 max(n - m, 0) 個元素將從 [first2, last2) 複製到 result，也保持順序。

若出現以下情況，行為未定義：

  • 輸入範圍未根據 comp 和 proj1 或 proj2 進行排序，或者
  • 結果範圍與任一輸入範圍重疊。
1) 使用給定的二元比較函式 comp 比較元素。
2) 同 (1)，但使用 r1 作為第一個範圍，r2 作為第二個範圍，如同使用 ranges::begin(r1) 作為 first1，ranges::end(r1) 作為 last1，ranges::begin(r2) 作為 first2，以及 ranges::end(r2) 作為 last2。

本頁描述的類函式實體是 演算法函式物件（非正式地稱為 niebloids），即

目錄

[編輯] 引數

first1, last1 - 定義第一個輸入已排序元素範圍的迭代器-哨兵對。
first2, last2 - 定義第二個輸入已排序元素範圍的迭代器-哨兵對。
r1 - 第一個輸入已排序範圍。
r2 - 第二個輸入已排序範圍。
result - 輸出範圍的起始
comp - 應用於投影元素的比較
proj1 - 應用於第一個範圍元素的投影。
proj2 - 應用於第二個範圍元素的投影。

[編輯] 返回值

{last1, last2, result_last}，其中 result_last 是構造範圍的末尾。

[編輯] 複雜度

最多 2·(N1+N2)-1 次比較和每個投影的應用，其中 N1 和 N2 分別是 ranges::distance(first1, last1) 和 ranges::distance(first2, last2)。

[編輯] 注意

此演算法執行與 ranges::merge 類似的任務。兩者都消費兩個已排序的輸入範圍，並生成一個包含兩個輸入元素的已排序輸出。這兩個演算法的區別在於處理來自兩個輸入範圍的等價值（參見 LessThanComparable 的說明）。如果任何等價值在第一個範圍中出現 n 次，在第二個範圍中出現 m 次，ranges::merge 將輸出所有 n+m 個出現，而 ranges::set_union 只會輸出 std::max(n, m) 個。因此 ranges::merge 精確輸出 (N1+N2) 個值，而 ranges::set_union 可能會產生更少。

[編輯] 可能的實現

struct set_union_fn
{
    template<std::input_iterator I1, std::sentinel_for<I1> S1,
             std::input_iterator I2, std::sentinel_for<I2> S2,
             std::weakly_incrementable O, class Comp = ranges::less,
             class Proj1 = std::identity, class Proj2 = std::identity>
    requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2>
    constexpr ranges::set_union_result<I1, I2, O>
        operator()(I1 first1, S1 last1, I2 first2, S2 last2,
                   O result, Comp comp = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        for (; !(first1 == last1 or first2 == last2); ++result)
        {
            if (std::invoke(comp, std::invoke(proj1, *first1), 
                                  std::invoke(proj2, *first2)))
            {
                *result = *first1;
                ++first1;
            }
            else if (std::invoke(comp, std::invoke(proj2, *first2),
                                       std::invoke(proj1, *first1)))
            {
                *result = *first2;
                ++first2;
            }
            else
            {
                *result = *first1;
                ++first1;
                ++first2;
            }
        }
        auto res1 = ranges::copy(std::move(first1), std::move(last1), std::move(result));
        auto res2 = ranges::copy(std::move(first2), std::move(last2), std::move(res1.out));
        return {std::move(res1.in), std::move(res2.in), std::move(res2.out)};
    }
 
    template<ranges::input_range R1, ranges::input_range R2,
             std::weakly_incrementable O, class Comp = ranges::less,
             class Proj1 = std::identity, class Proj2 = std::identity>
    requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>,
                            O, Comp, Proj1, Proj2>
    constexpr ranges::set_union_result<ranges::borrowed_iterator_t<R1>,
                                       ranges::borrowed_iterator_t<R2>, O>
        operator()(R1&& r1, R2&& r2, O result, Comp comp = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (*this)(ranges::begin(r1), ranges::end(r1),
                       ranges::begin(r2), ranges::end(r2),
                       std::move(result), std::move(comp),
                       std::move(proj1), std::move(proj2));
    }
};
 
inline constexpr set_union_fn set_union {};

[編輯] 示例

執行此程式碼
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
void print(const auto& in1, const auto& in2, auto first, auto last)
{
    std::cout << "{ ";
    for (const auto& e : in1)
        std::cout << e << ' ';
    std::cout << "} ∪ { ";
    for (const auto& e : in2)
        std::cout << e << ' ';
    std::cout << "} =\n{ ";
    while (!(first == last))
        std::cout << *first++ << ' ';
    std::cout << "}\n\n";
}
 
int main()
{
    std::vector<int> in1, in2, out;
 
    in1 = {1, 2, 3, 4, 5};
    in2 = {      3, 4, 5, 6, 7};
    out.resize(in1.size() + in2.size());
    const auto ret = std::ranges::set_union(in1, in2, out.begin());
    print(in1, in2, out.begin(), ret.out);
 
    in1 = {1, 2, 3, 4, 5, 5, 5};
    in2 = {      3, 4, 5, 6, 7};
    out.clear();
    out.reserve(in1.size() + in2.size());
    std::ranges::set_union(in1, in2, std::back_inserter(out));
    print(in1, in2, out.cbegin(), out.cend());
}

輸出

{ 1 2 3 4 5 } ∪ { 3 4 5 6 7 } =
{ 1 2 3 4 5 6 7 }
 
{ 1 2 3 4 5 5 5 } ∪ { 3 4 5 6 7 } =
{ 1 2 3 4 5 5 5 6 7 }

[編輯] 另請參閱

(C++20)
 計算兩個集合的差集
(演算法函式物件)[編輯]
(C++20)
 計算兩個集合的交集
(演算法函式物件)[編輯]
(C++20)
 計算兩個集合的對稱差
(演算法函式物件)[編輯]
(C++20)
 歸併兩個已排序的範圍
(演算法函式物件)[編輯]
(C++20)
 如果一個序列是另一個序列的子序列，則返回 true
(演算法函式物件)[編輯]
 計算兩個集合的並集
(函式模板) [編輯]
取自 "https://cppreference.tw/mwiki/index.php?title=cpp/algorithm/ranges/set_union&oldid=180580"