Как удалить практически дубликаты из вектора в Stack Overflow
У меня есть std :: vector с плавающей точкой, который я не хочу содержать дубликаты, но математика, которая заполняет вектор, не на 100% точна. Вектор имеет значения, которые отличаются на несколько сотых, но должны рассматриваться как одна и та же точка. Например, вот некоторые значения в одном из них:
...
X: -43.094505
X: -43.094501
X: -43.094498
...
Что было бы лучшим / наиболее эффективным способом удаления дубликатов из вектора, как это.
Решение
Сначала отсортируйте ваш вектор, используя std::sort. Тогда используйте std::unique с пользовательским предикатом для удаления дубликатов.
std::unique(v.begin(), v.end(),
[](double l, double r) { return std::abs(l - r) < 0.01; });
// treats any numbers that differ by less than 0.01 as equal
Другие решения
-
Сортировка всегда хороший первый шаг. использование
std::sort(), -
Удалить не достаточно уникальные элементы:
std::unique(), -
Последний шаг, позвоните
resize()и, возможно, такжеshrink_to_fit(),
Если вы хотите сохранить порядок, выполните предыдущие 3 шага для копии (но не уменьшайте ее).
Тогда используйте std::remove_if с помощью лямбды, проверяя наличие элемента в копии (бинарный поиск) (не забудьте удалить его, если он найден), и сохраняйте элементы только в том случае, если они найдены в копии.
Я говорю std::sort() затем пройдитесь по одному и удалите значения в пределах определенного поля.
Вы можете иметь отдельный итератор записи в тот же вектор и одну операцию изменения размера в конце — вместо вызова erase() для каждого удаленного элемента или наличия другой целевой копии для увеличения производительности и меньшего использования памяти.
Если ваш вектор не может содержать дубликаты, может быть более целесообразно использовать станд :: набор. Затем вы можете использовать пользовательский объект сравнения, чтобы рассматривать небольшие изменения как несущественные.
Привет, ты мог сравнить это
bool isAlmostEquals(const double &f1, const double &f2)
{
double allowedDif = xxxx;
return (abs(f1 - f2) <= allowedDif);
}
но это зависит от вашего диапазона сравнения и двойной точности не на вашей стороне
если ваш вектор отсортирован, вы можете использовать std :: unique с функцией в качестве предиката
Я бы сделал следующее:
-
Создать
set<double> -
пройти через ваш вектор в цикле или с помощью функтора
-
Округлите каждый элемент и вставьте в набор
-
Тогда вы можете поменять свой вектор с пустым вектором
-
Скопировать все элементы из набора в пустой вектор
Сложность этого подхода будет n * log(n) но это проще и может быть сделано в несколько строк кода. Потребление памяти удвоится от простого хранения вектора. К тому же set потребляет чуть больше памяти на каждый элемент, чем вектор. Тем не менее, вы будете уничтожать его после использования.
std::vector<double> v;
v.push_back(-43.094505);
v.push_back(-43.094501);
v.push_back(-43.094498);
v.push_back(-45.093435);
std::set<double> s;
std::vector<double>::const_iterator it = v.begin();
for(;it != v.end(); ++it)
s.insert(floor(*it));
v.swap(std::vector<double>());
v.resize(s.size());
std::copy(s.begin(), s.end(), v.begin());
Проблема с большинством ответов до сих пор в том, что у вас необычное «равенство». Если A и B похожи, но не идентичны, вы хотите рассматривать их как равные. В основном, A и A + эпсилон по-прежнему сравниваются как равные, но A + 2 * эпсилон не сравнивает (для некоторых неопределенных эпсилон). Или, в зависимости от вашего алгоритма, A * (1 + эпсилон) делает, а A * (1 + 2 * эпсилон) — нет.
Это означает, что A + эпсилон сравнивается равным A + 2 * эпсилон. Таким образом, A = B и B = C не подразумевает A = C. Это нарушает общие предположения в <algorithm>,
Вы все еще можете сортировать значения, это нормальное занятие. Но вы должны рассмотреть, что делать с большим диапазоном похожих значений в результате. Если диапазон достаточно длинный, разница между первым и последним все еще может быть большой. Там нет простого ответа.