用于合并加法的STL算法

我正在使用stl :: merge将两个已排序的集合合并为一个。用于合并加法的STL算法

但我的对象有一个自然的关键;和一个定义的附加语义，所以我所追求的是merge_and_sum，它不会将两个集合合并成一个N + M长度集合，但如果对象上的运算符==返回true，那么将运算符+它们。

我就此

template<class _InIt1, class _InIt2, class _OutIt> 
_OutIt merge_and_sum(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest) 
{ // copy merging ranges, both using operator< 
    for (; _First1 != _Last1 && _First2 != _Last2; ++_Dest) 
    { 
     if (*_First2 < *_First1) 
      *_Dest = *_First2, ++_First2; 
     else if (*_First2 == *_First1) 
      *_Dest = *_First2 + *_First1, ++_First1, ++_First2; 
     else 
      *_Dest = *_First1, ++_First1; 
    } 
    _Dest = copy(_First1, _Last1, _Dest); // copy any tail 
    return (copy(_First2, _Last2, _Dest)); 
}

实现了它，但不知道如果我重新发明的东西是从其他算法可组合。

来源

2009-07-17 sdg

变量名称不允许以下划线开头，后跟大写字母。只有编译器提供的名称才允许这样做。 – rlbond 2009-07-17 20:02:27

是的 - 谢谢。当我开始剪切/粘贴编译器的std :: merge时，会发生这种情况:-) – sdg 2009-07-17 20:26:25

听起来你的收藏就像多重复制品，你的+操作符折叠了重复项（也许只是总结多项而不是保留多余的副本）。我假设是这样，因为当你+时你没有改变排序顺序，所以+不会影响你的密钥。

你应该使用你的实现。 STL没有什么能够有效地做到这一点。我能想到的最接近的语义是标准合并，然后是unique_copy。你可以差不多获得unique_copy与副作用的比较运算符一起工作，但这是非常不明智的建议，因为实现不承诺只比较事情直接与经过值复制的临时（或甚至给定次数）。

你的类型和变量名是令人不快长;）

来源

2009-07-17 19:49:45

嗯，你们的选择是使用set_symmetric_difference吃出了不同的元素，然后使用set_intersection得到是相同的的，但两次。然后将它们添加到一起并插入第一个。

typedef set<MyType, MyComp> SetType; 
SetType merge_and_add(const SetType& s1, const SetType& s2) 
{ 
    SetType diff; 
    set_symmetric_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(s2, s2.end()); 
    vector<SetType::value_type> same1, same2; 
    set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(same1)); 
    set_intersection(s2.begin(), s2.end(), s1.begin(), s1.end(), back_inserter(same2)); 
    transform(same1.begin(), same1.end(), same2.begin(), inserter(diff, diff.begin()), plus<SetType::value_type, SetType::value_type>()); 
    return diff; 
}

注意！您应该坚持使用operator==，在这种情况下，您应该使用unordered_set，或者您应该使用operator<作为常规设置。一套要求是部分订购这意味着如果!(a < b) && !(b < a)有2个条目被视为等效。所以即使你的两个物体在operator==之间不相等，如果它们满足这个条件，这个集合也会认为它们是重复的。因此，对于上面提供的功能，我强烈建议不要使用==比较。

来源

2009-07-17 20:01:04 rlbond

您可以使用std::merge和自己创建的输出迭代器，它在operator=中执行以下操作。尽管如此，我认为这最终会比你的版本更多地致电operator==，所以除非它作为更少的代码出现，否则它可能不值得。

if ((mylist.size() > 0) && (newvalue == mylist.back())) { 
    mylist.back() += newvalue; 
} else { 
    mylist.push_back(newvalue); 
}

（其实，写一个正确的输出迭代器可能会比这更繁琐的，我不记得了。但我希望你得到的总体思路）。

mylist是对您合并到的集合的引用。如果目标没有back()，那么您必须在输出迭代器中缓冲一个值，并且只有在看到不相等的值时才写入。然后在输出迭代器上定义一个flush函数来写入最后一个值，并在最后调用它。我敢肯定，在这种情况下，要打败你已经完成的事情太麻烦了。

来源

2009-07-17 20:29:21

用于合并加法的STL算法

回答

相关问题