std::merge和std::set_union有什么区别？

Question

std::merge和std::set_union有什么区别？

c++merge

10

问题很明确，我的 Google 和 cplusplus.com/reference 没有帮助到我。

- rubenvb

@Emilie：正如我在问题中所说的那样，这并没有为我提供答案。 - rubenvb

5个回答

6

std::merge函数会保留两个范围中的所有元素，第一个范围中等价的元素排在第二个范围中等价元素之前。如果两个范围中都有等价元素，则std::set_union函数只选择第一个范围中的元素，否则每个元素都按顺序合并，与std::merge相同。

参考文献：ISO/IEC 14882:2003 25.3.4 [lib.alg.merge] 和 25.3.5.2 [lib.set.union]。

- CB Bailey

这听起来更像是交集，不是吗？ - davka

@davka：我在谈论的是第二个范围中存在等价物的行为。我认为所有没有在另一个范围中有等价物的元素都会被保留。我已经澄清了我的措辞。 - CB Bailey

好的，在读了这句话5遍之后 :) 我明白你的意思了。我把它理解成“只需要”了... - davka

@davka：请仔细阅读，我说的是“takes only”，我认为这更清晰。 - CB Bailey

我会尽力的 :) 你的新措辞更清晰易懂，我认为。对于我们许多人来说，英语是第二（或第n）语言。 - davka

2

这是我在已接受答案的评论中建议的验证（即，如果一个元素在其中一个输入集中出现N次，则它将在set_union的输出中出现N次 - 因此，set_union不会以我们“自然”或“数学”的方式删除重复的等效项 - 但是，如果两个输入范围仅包含一个共同项，则set_union将“看起来”删除重复项）

#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>

using namespace std;

void printer(int i) { cout << i << ", "; }

int main() {
    int mynumbers1[] = { 0, 1, 2, 3, 3, 4 }; // this is sorted, 3 is dupe
    int mynumbers2[] = { 5 };                // this is sorted


    vector<int> union_result(10);
    set_union(mynumbers1, mynumbers1 + sizeof(mynumbers1)/sizeof(int),
              mynumbers2, mynumbers2 + sizeof(mynumbers2)/sizeof(int),
              union_result.begin());
    for_each(union_result.begin(), union_result.end(), printer);

    return 0;
}

这将输出：0、1、2、3、3、4、5、0、0、0。

- aho

1

为了补充之前的回答 - 请注意，std::set_union 的复杂度是 std::merge 的两倍。在实践中，这意味着 std::set_union 中的比较器可能会在解引用后应用于元素，而对于 std::merge，则从不出现这种情况。

为什么这很重要？考虑以下内容：

std::vector<Foo> lhs, rhs;

你想要生成lhs和rhs的并集：

std::set_union(std::cbegin(lhs), std::cend(lhs),
               std::cbegin(rhs), std::cend(rhs),
               std::back_inserter(union));

但是现在假设Foo不可复制，或者复制非常昂贵而且您不需要原件。您可以考虑使用：

std::set_union(std::make_move_iterator(std::begin(lhs)),
               std::make_move_iterator(std::end(lhs)),
               std::make_move_iterator(std::begin(rhs)),
               std::make_move_iterator(std::end(rhs)),
               std::back_inserter(union));

但这是未定义的行为，因为有可能比较一个已经移动的 Foo！因此正确的解决方案是：

std::merge(std::make_move_iterator(std::begin(lhs)),
           std::make_move_iterator(std::end(lhs)),
           std::make_move_iterator(std::begin(rhs)),
           std::make_move_iterator(std::end(rhs)),
           std::back_inserter(union));
union.erase(std::unique(std::begin(union), std::end(union), std::end(union));

这与 std::set_union 具有相同的复杂度。

- Daniel

1

std::merge 合并所有的元素，不会消除重复，而 std::set_union 会消除重复。也就是说，后者使用了 集合论 中并集运算的规则。

- Nawaz

1

为什么我只考虑了使用std::set的算法...感谢你给出了我眼中最简洁和清晰的答案。 - rubenvb

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mat · Accepted Answer

std::set_union会包含那些在两个集合中都出现一次的元素，std::merge会将它们包含两次。

例如，对于 A = {1, 2, 5}; B = {2, 3, 4}:

并集将给出 C = {1, 2, 3, 4, 5}
归并将给出 D = {1, 2, 2, 3, 4, 5}

两者都适用于排序范围，并返回一个已排序的结果。

简单示例:

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

int main()
{
  std::set<int> A = {1, 2, 5};
  std::set<int> B = {2, 3, 4};

  std::vector<int> out;
  std::set_union(std::begin(A), std::end(A), std::begin(B), std::end(B),
                 std::back_inserter(out));
  for (auto i : out)
  {
    std::cout << i << " ";
  }
  std::cout << '\n';

  out.clear();
  std::merge(std::begin(A), std::end(A), std::begin(B), std::end(B),
             std::back_inserter(out));
  for (auto i : out)
  {
    std::cout << i << " ";
  }
  std::cout << '\n';
}

输出：

1 2 3 4 5 
1 2 2 3 4 5