一个在C++中用于多个集合并的reduce函数

Question

我想做的事情： 我有一个使用STL的简单集合并函数，我试图将其包装在一个函数中，以便让我执行包含在STL数据结构中的任意多个集合的并集（例如std::list、std::vector、std::forward_list等）。

我的尝试方法： 首先，我的简单集合并：

#include <algorithm>
template <typename set_type>
set_type sunion(const set_type & lhs, const set_type & rhs)
{
  set_type result;
  std::set_union( lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), std::inserter(result, result.end()) );
  return result;
}

其中，set_type 定义了一些STL std::set<T>，例如 std::set<int>。

在注意到多次需要对集合的迭代器执行多个联合操作后（在Python中，这将是对某个可迭代集合对象上我的sunion函数的一个reduce），例如，我可能会有：

std::vector<std::set<int> > all_sets;

或者

std::list<std::set<int> > all_sets;

等等，我需要澄清一下，您是需要将以下的句子翻译成中文吗？

all_sets是多个集合，我希望得到它们的并集。为此，我正在尝试实现一个简单的reduce函数来完成这项任务（它本质上实现了一个更快、更优雅、非复制的版本）。

sunion(... sunion( sunion( all_sets.begin(), all_sets.begin()+1 ), all_sets.begin()+2 ) , ... )

简单来说，为了快速实现这一点，我只需声明一个set_type result，然后迭代遍历all_sets并将每个集合中的值插入到结果对象中:

template <typename set_type>
set_type sunion_over_iterator_range(const std::iterator<std::forward_iterator_tag, set_type> & begin, const std::iterator<std::forward_iterator_tag, set_type> & end)
{
  set_type result;
  for (std::iterator<std::forward_iterator_tag, set_type> iter = begin; iter != end; iter++)
    {
      insert_all(result, *iter);
    }
  return result;
}

其中 insert_all 被定义为：

// |= operator; faster than making a copy and performing union
template <typename set_type>
void insert_all(set_type & lhs, const set_type & rhs)
{
  for (typename set_type::iterator iter = rhs.begin(); iter != rhs.end(); iter++)
    {
      lhs.insert(*iter);
    }
}

为什么它不起作用： 不幸的是，我的sunion_over_iterator_range(...)在使用std::vector<set_type>::begin(), std::vector<set_type>::end()这些参数时不起作用，因为它们的类型为std::vector<set_type>::iterator。我认为std::vector<T>::iterator返回一个iterator<random_access_iterator_tag, T>。

在编译失败后，由于迭代器类型不兼容，我查看了stl vector源码（位于/usr/include/c++/4.6/bits/stl_vector.h，适用于g++ 4.6和Ubuntu 11.10），惊讶地发现vector<T>::iterator的typedef被定义为typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;。我曾认为ForwardIterator是RandomAccessIterator的子类型，应该可以正常工作，但显然我是错误的，否则我就不会在这里了。

我感激并为激起你的不满而感到羞愧： 如果我表现出自己的无知，请原谅——我正在努力学习成为更好的面向对象程序员（过去我只是以C风格的代码进行所有操作）。

我会尽力而为的，教练！请帮助我，避免我制造出糟糕的代码，让您的编程智慧不浪费于此...

- user

---

C++有Python的reduce等效函数。它被称为std::accumulate。（虽然我不确定它是否在这种情况下有用）。 - Mankarse

Answer 1

这是一个非常幼稚的方法:

std::set<T> result;
std::vector<std::set<T>> all_sets;

for (std::set<T> & s : all_sets)
{
    result.insert(std::make_move_iterator(s.begin()),
                  std::make_move_iterator(s.end()));
}

这会使源集合中的元素失效，但并不实际移动元素节点。如果您想保留源集合的完整性，只需删除make_move_iterator即可。

不幸的是，std::set没有接口能够以不重新分配内部树节点的方式将两个集合“拼接”起来，因此这差不多就是最好的方法了。

以下是一种可变模板方法：

template <typename RSet> void union(RSet &) { }

template <typename RSet, typename ASet, typename ...Rest>
void union(RSet & result, ASet const & a, Rest const &... r)
{
    a.insert(a.begin(), a.end());
    union(result, r...);
}

使用方法：

std::set<T> result
union(result, s1, s2, s3, s4);

（类似的移动优化在这里也是可行的；如果你喜欢，甚至可以添加一些分支，从不可变对象中复制，从可变对象中移动，或仅从右值中移动。）

这是一个使用std::accumulate的版本：

std::set<T> result =
   std::accumulate(all_sets.begin(), all_sets.end(), std::set<T>(),
                   [](std::set<T> & s, std::set<T> const & t)
                     { s.insert(t.begin(), t.end()); return s; }    );

这个版本似乎大量依赖于返回值优化，但是你可能想将其与这个魔改丑陋的版本进行比较：

std::set<T> result;
std::accumulate(all_sets.begin(), all_sets.end(), 0,
                [&result](int, std::set<T> const & t)
                { result.insert(t.begin(), t.end()); return 0; } );

- Kerrek SB

---

这是小题大做，但是你必须把 <std::set<T>> 中的 > > 字符分开，以便你有 <std::set<T> >。如果你把它们放在一起，C++ 会将其解释为右移操作符，这不是你想要的。 - DataPlusPlus

@Datalore：那么你也应该挑剔一下for(T& s : ss)的语法 :) - kennytm

第一次向我展示for(T& s : ss)，非常感谢！^_^ - user

我知道标准库中一定有类似于accumulate的东西，但我不知道它们叫什么。 - drewish

Answer 2

通常，在使用迭代器时，我们并不关心实际的类别。只需让实现来解决这个问题。这意味着，只需更改函数以接受任何类型：

template <typename T>
typename std::iterator_traits<T>::value_type sunion_over_iterator_range(T begin, T end)
{
   typename std::iterator_traits<T>::value_type result;
   for (T iter = begin; iter != end; ++ iter)
   {
      insert_all(result, *iter);
   }
   return result;
}

注意，我使用了typename std::iterator_traits<T>::value_type，它是*iter的类型。顺便说一下，迭代器模式与面向对象编程无关（这并不意味着它是一件坏事）。

- kennytm

---

+1 这基本上就是我想要做的事情。有没有办法让返回值是 set_type 而不是一个迭代器？有了那个，这正是我想要的。 - user

啊——算了，不知怎么的编译器自己就找到了正确的模板参数类型。但是无论如何，我很想看一下std::iterator_traits的解释（我会查看链接的）。它似乎是iterable_type::iterator的反函数，从迭代器转换为包含它的某种类型。其他答案非常完整和有用，但这个最接近我的想法（毕竟，难点不在于算法，而在于允许正确的参数类型）。 - user