Самый быстрый способ удалить дубликаты из std :: list пользовательского типа

Question

Если об этом уже спрашивали, пожалуйста, прости меня, я не смог найти его. У меня есть пользовательский тип, для которого я могу реализовать (нечеткое) равенство, но нет оператора <, который является транзитивным. Сравнение стоит дорого, но у меня не так много элементов. Мне нужно разобрать многоугольники, которые почти одинаковы (они перекрываются с большой долей). Поскольку упорядочение с использованием < невозможно из-за отсутствия транзитивной реализации, я использую std :: list, как показано ниже:

typedef std::list<Polygon> PolyList;
PolyList purged(rawList);
for (PolyList::iterator iter= purged.begin(); iter!=  purged.end(); ++iter) {
  for(PolyList::iterator toRemove = find(boost::next(iter),purged.end(),*iter); toRemove != purged.end(); ){
      PolyList::iterator next = purged.erase(toRemove);
      toRemove = find(next,purged.end(),*iter);
    }
  }

Сложность n * n / 2, что, на мой взгляд, неизбежно и Хотя алгоритм работает нормально, его все равно очень трудно читать и писать, и я почти уверен, что для него есть стандартный алгоритм, который я просто не знаю или, по крайней мере, что-то более быстрое, но более точное для ввода. Как я уже сказал, сортировка не возможна из-за нечеткости данных, поэтому нет уникального набора или сортировки. Большое спасибо заранее за помощь мне

Answer 1

Вы, вероятно, не найдете ответ в Стандарте, поскольку ваши "дубликаты" звучат так, как будто они также не переходные. То есть a==b && b==c не означает a==c.

Только по этой причине любой алгоритм должен сравнивать все пары, что дает вам (N*N-1)/2 сравнений (при условии, что ваше равенство симметрично, т. Е. a==b означает подразумевает b==a).

Answer 2

Я сомневаюсь, что есть «стандартный алгоритм» для достижения того, что вы хотите, но если вы определите метрику расстояния, описывающую разницу между двумя полигонами, то вы можете выбрать (любой) один полигон (назовите его базовым полигоном) и отсортировать все остальные на расстоянии от этого многоугольника. Только полигоны, чье расстояние от основания одинаково, могут быть похожи друг на друга.

Теперь вам нужно учитывать только группы многоугольников с одинаковыми расстояниями, когда решаете, что удалять. Не доказывая это - и я подозреваю, что доказательство может быть вовлечено - я считаю, что это N log N.