Функция редукции (для множества множеств) в C ++

Question

Что я пытаюсь сделать: У меня есть простая функция объединения множеств в C ++ с использованием 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 это будет reduce моей sunion функции по отношению к некоторому повторяемому объекту set_type с).Например, у меня может быть

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

или

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

и т. Д., И я хочу получить объединение всех наборов в all_sets.Я пытаюсь реализовать простое сокращение для этого, которое по существу делает (более быструю, более элегантную, не копирующую) версию:

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

По сути, чтобы сделать это быстро, я просто хочу объявитьset_type result, а затем переберите all_sets и вставьте значение в каждый набор в 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>.A

После сбоя компиляции из-за несовместимости типов итераторов, я посмотрел на источник вектора stl (находится в / usr / include / c ++ / 4.6 / bits / stl_vector.h для g ++4.6 и Ubuntu 11.10), и был удивлен, увидев, что typedef для vector<T>::iterator равен typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;.Я думал, что ForwardIterator является подтипом RandomAccessIterator, и поэтому должно быть в порядке , но, очевидно, я ошибся, или я не буду здесь.

Как я благодарени мне стыдно подстрекать вас к разочарованию из-за моей неопытности: Извинения, если я показываю свое невежество - я пытаюсь научиться быть лучшим объектно-ориентированным программистом (в прошлом я просто все взламывал в стиле Cкод).

Я стараюсь изо всех сил, тренер!Пожалуйста, помогите мне и избавьте мир от плохого кода, который я мог бы создать без вашего понимания ниндзя кода ...

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; } );

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.

Кстати, шаблон итератора не связан с ООП. (Это не значит, что это плохо).