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

问题很明显，我的google-和cplusplus.com/reference-fu正在让我失望。std :: merge和std :: set_union有什么区别？

2011-03-06 rubenvb

http://www.cplusplus.com/reference/algorithm/merge/ http://www.cplusplus.com/reference/algorithm/set_union/这花了我10secs找到。 – 2011-03-06 17:10:00

@Emilie：正如我在我的问题中所说的那样，*并没有给我提供答案。 – rubenvb 2011-03-07 10:35:36

set_union将仅包含一次出现在两个集合中的元素。合并将包含他们两次。

这两个工作在排序的范围，并返回一个排序的结果。

来源

2011-03-06 16:42:17 Mat

'std :: merge'也适用于已排序的范围并产生排序结果。 – 2011-03-06 16:43:36

@Charkes贝利：谢谢，我没有检查std :: merge，并没有认为它做到了。修改我的答案。 – Mat 2011-03-06 16:46:32

只是为了大家的缘故，也许这是我挑剔，但上述不够明确，我喜欢。阅读这个答案*可能会引导你相信重复项被set_union（）消除 - 虽然不一定如你所想。如果第一个范围不止一次包含等效元素，那么该元素将出现在输出范围内的次数也是同样多。这很容易验证： – aho 2015-11-09 23:33:04

std::merge合并所有元素，但不删除重复项，而std::set_union消除重复项。也就是说，后者适用的union操作规则。

来源

2011-03-06 16:41:09 Nawaz

为什么我只想用'std :: set'的方式来思考这些算法......感谢在我眼中短而干净的答案。 – rubenvb 2011-03-07 10:37:31

std::merge保留来自两个范围的所有元素，即来自输出中第二范围之前的第一个范围的等同元素。在两个范围内出现等效元素std::set_union仅取第一个范围内的元素，否则按照std::merge的顺序合并每个元素。

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

来源

2011-03-06 16:41:20

这听起来更像是十字路口，不是吗？ – davka 2011-03-06 16:43:18

@davka：我在谈论在第二个范围内存在等价物的行为。我认为它保留了其他范围中没有等价物的所有元素。我已经澄清了我的措辞。 – 2011-03-06 16:45:26

好的，看完这个句子5次后:)我明白你的意思了。我读它为“只需要”... – davka 2011-03-06 16:49:47

这是我在评论中建议的验证，我发布到接受的答案（即如果一个元素出现在其中一个输入集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，4，5，0，0，0，

来源

2015-11-09 23:39:18 aho

要添加到以前的答案 - 请注意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具有相同的复杂性。

来源

2016-09-26 14:39:28 Daniel

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

回答

相关问题