Variante von std::unique

Hallo Forum,

std::unique sorgt ja dafür, dass aus jeder aufeinanderfolgenden Sequenz von gleichen Werten nur der erste erhalten bleibt.
Aus

{ 1, 2, 2, 3, 4, 4, 5, 6 };

wird

{ 1, 2, 3, 4, 5, 6, ?, ? }

Ich würde gerne erreichen, dass die Sequenz so umsortiert wird, dass aufeinanderfolgende gleiche Werte ans Ende gestellt werden. Für obigen Fall also:

{ 1, 3, 5, 6, 2, 2, 4, 4 };

Folgende erste Implementation habe ich mir dazu einfallen lassen:

- comp wäre eine Vergleichsfunktion wie für std::sort, standardmäßig std::less<>()
- der zurückgegebene Iterator würde auf das erste Duplikat zeigen, also im obigen Fall auf die erste 2

template<typename RandomAccessIterator, typename Compare>
   RandomAccessIterator RemoveDuplicates(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
   {
      if (first == last)
         return last;

      std::sort(first, last, comp); // (1) dürfte auch voraussgesetzt werden

      auto result = last;
      while (first != result)
      {
         auto upper = std::upper_bound(first, result, *first, comp); // finde nächstes unterschiedliches Element

         if (upper != std::next(first)) // nächstes Element ist gleich
         {
            std::rotate(first, upper, last); // Duplikate ans Ende der Range
            std::advance(result, -std::distance(first, upper)); // (2) result-iterator auf erstes Duplikat
         }
         else
            ++first;
      }

      return result;
   }

Prinzipiell erfüllt das nach ersten Tests seinen Zweck, so richtig rund wirkt es auf mich aber noch nicht. Zudem wäre es mir lieber, ich könnte anstatt der RandomAccessIterators ForwardIterators verwenden. Dann müsste das sort (siehe (1)) vorausgesetzt werden und die Positionierung des result-iterators (siehe (2)) müsste jedesmal erneut vom Beginn der Range erfolgen.

Sofern jemand Muße hat, wäre ich für ein wenig konstruktive Kritik dankbar!

Columbo

Deine Variante kann deinen Anforderungen entsprechend angepasst werden, indem Duplikate immer zum nächsten Duplikat rotiert werden, etc. die Anzahl der swaps ist dann linear, und wir brauchen lediglich Forward Iterators.

Ich habe inzwischen eine Variante implementiert, die mit ForwardIterators auskommt. Es werden alle aufeinanderfolgenden gleichen (gemäß Vergleichsfunktion) Elemente ans Ende der Range verschoben. Will man also tatsächlich alle Duplikate entfernen, muss man vor Aufruf der Funktion sortieren (ähnlich wie bei std::unique).
Einzig die Positionierung des result-Iterators gefällt mir noch nicht hundertprozentig, weil ich den nach jedem rotate durch Inkrementierung ausgehend von "first" neu positioniere und damit möglicherweise unnötig oft inkrementiere.

Deinen Vorschlag bezüglich der Rotation der Duplikate werde ich mir mal anschauen. Vielen Dank für die Anregung!