Duplikate entfernen

Einen sortierten Bereich unique zu machen, geht mit STL-Algorithmen sehr elegant:

v.resize(unique(v.begin(),v.end())-v.begin());

..aber gibt es auch eine schöne Lösung, jene Elemente komplett zu entfernen,
die nicht unique sind? Beispiel [0,1,1,2,2,2,3] -> [0,3]. Mir fällt nur ein,
mit einer Schleife drüber zu laufen.

ja klar
alle in multiset eintragen, und dann die mit count==0 rausfiltern.

http://www.cplusplus.com/reference/stl/multiset/count/

Die Sortierung geht allerdings verloren, aber vielleicht kommt es daruf nicht an?

SeppJ

unique wird so oder ähnlich implementiert sein:

template <class ForwardIterator>
  ForwardIterator unique ( ForwardIterator first, ForwardIterator last )
{
  ForwardIterator result=first;
  while (++first != last)
  {
    if (!(*result == *first))  
      *(++result)=*first;
  }
  return ++result;
}

Das kannst du dir ja einfach mal anpassen, um das Gegenteil zu erreichen. Mit fertigen STL-Algorithmen alleine wirst du glaube ich nicht zum Ziel kommen, irgendwo wirst du ein bisschen eigenen Code schreiben müssen. Der Aufruf wird dann aber ähnlich elegant aussehen wie in deinem Beispiel für unique.

Mir ist mittlerweile was eingefallen:

Partitionieren mit unique, so daß zwei Bereiche entstehen. Dann mit
set_difference den zweiten vom ersten abziehen. Sollte funktionieren.

Dobi

http://www.cplusplus.com/reference/algorithm/unique/ : "The elements past the new end of range are still valid, although with unspecified values."

So etwa müsste das gehen:

#include <algorithm>
#include <iostream>
#include <iterator>

template<typename iter_t>
iter_t swap_ranges_fwd(iter_t first, iter_t last, iter_t first2) {
  using std::swap;

  while(first != last) {
    swap(*first, *first2);
    ++first;
    ++first2;
  }

  return first2;
}

template<typename iter_t>
iter_t keep_only_unique(iter_t first,
                        iter_t last)
{
  iter_t dest;

  dest = first = std::adjacent_find(first, last);

  while(first != last) {
    iter_t prev;

    do {
      prev = std::adjacent_find(first, last, std::not_equal_to<typename std::iterator_traits<iter_t>::value_type>());

      if(prev == last) {
        first = prev;
        break;
      } else {
        ++prev;
        first = std::adjacent_find(prev, last);
      }
    } while(prev == first);

    dest = swap_ranges_fwd(prev, first, dest);
  }

  return dest;
}

template<typename T, std::size_t N>
std::size_t array_size(T(&)[N]) { return N; }

template<typename T, std::size_t N>
void print_uniques(T (&arr)[N]) {
  std::copy(arr, keep_only_unique(arr, arr + N), std::ostream_iterator<int>(std::cout, " "));
  std::cout << '\n';
}

int main() {
  int foo [] = { 1, 2, 2, 3, 4, 4, 4, 5, 5, 6, 7, 8, 8, 9, 9, 9, 10, 11, 12, 13, 13, 14, 14, 15 };
  int foo2[] = { 1, 2, 2, 3, 4, 4, 4, 5, 5, 6, 7, 8, 8, 9, 9, 9, 10, 11, 12, 13, 13, 14, 14, 14 };
  int foo3[] = { 1, 1, 1, 2, 3 };
  int foo4[] = { 1, 1, 1, 2, 2, 3 };
  int foo5[] = { 1, 1, 1, 2, 2 };

  print_uniques(foo);
  print_uniques(foo2);
  print_uniques(foo3);
  print_uniques(foo4);
  print_uniques(foo5);
}

Wahlweise statt swap_ranges_fwd auch std::copy, aber bei komplexeren Datentypen will man vielleicht unnötige Kopien vermeiden. Mit C++11 bietet sich hier natürlich Move-Semantik an. Die Standard-Funktionsvorlage std::swap_ranges verbietet sich überlappende Speicherbereiche als Parameter, also konnte ich sie hier leider nicht verwenden.

Eine schöne Lösung. Danke.