N
Man muss ja nicht alles von Hand erledigen. Ein Algorithmus, der zwei sortierte Sequenzen effizient zusammenführt und Duplikate löscht, sollte reichen. Ich dachte an sowas:
template <typename InputIterator, typename OutputIterator>
void advance_smaller(InputIterator& left, InputIterator& right, InputIterator& previous, OutputIterator& result)
{
if (*left < *right)
previous = left++;
else
previous = right++;
*result++ = *previous;
}
template <typename InputIterator, typename OutputIterator>
OutputIterator merge_unique(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2,
OutputIterator result)
{
InputIterator previous;
advance_smaller(first1, first2, previous, result);
for (;;)
{
if (first1 == last1)
return std::copy(first2, last2, result);
else if (first2 == last2)
return std::copy(first1, last1, result);
if (*first1 == *previous)
++first1;
else if (*first2 == *previous)
++first2;
else
advance_smaller(first1, first2, previous, result);
}
}
Eventuell noch eine Wrapper-Funktion:
template <class Container>
void merge_unique_containers(const Container& source1, const Container& source2, Container& dest)
{
merge_unique(source1.begin(), source1.end(), source2.begin(), source2.end(), std::back_inserter(dest));
}
Der STL-Algorithmus std::set_union() sieht eigentlich vielversprechend aus, allerdings trifft er die Annahme, dass beide Quell-Ranges keine Duplikate enthalten.
