How to remove almost duplicates from a vector in C++

Question

I have an std::vector of floats that I want to not contain duplicates but the math that populates the vector isn't 100% precise. The vector has values that differ by a few hundredths but should be treated as the same point. For example here's some values in one of them:

...
X: -43.094505
X: -43.094501
X: -43.094498
...

What would be the best/most efficient way to remove duplicates from a vector like this.

Answer 1

First sort your vector using std::sort. Then use std::unique with a custom predicate to remove the duplicates.

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

Live demo

Answer 2

1. Sorting is always a good first step. Use std::sort().

2. Remove not sufficiently unique elements: std::unique().

3. Last step, call resize() and maybe also shrink_to_fit().

If you want to preserve the order, do the previous 3 steps on a copy (omit shrinking though).
Then use std::remove_if with a lambda, checking for existence of the element in the copy (binary search) (don't forget to remove it if found), and only retain elements if found in the copy.

Answer 3

The problem with most answers so far is that you have an unusual "equality". If A and B are similar but not identical, you want to treat them as equal. Basically, A and A+epsilon still compare as equal, but A+2*epsilon does not (for some unspecified epsilon). Or, depending on your algorithm, A*(1+epsilon) does and A*(1+2*epsilon) does not.

That does mean that A+epsilon compares equal to A+2*epsilon. Thus A = B and B = C does not imply A = C. This breaks common assumptions in <algorithm>.

You can still sort the values, that is a sane thing to do. But you have to consider what to do with a long range of similar values in the result. If the range is long enough, the difference between the first and last can still be large. There's no simple answer.

Answer 4

I say std::sort() it, then go through it one by one and remove the values within certain margin.

You can have a separate write iterator to the same vector and one resize operation at the end - instead of calling erase() for each removed element or having another destination copy for increased performance and smaller memory usage.

Answer 5

If your vector cannot contain duplicates, it may be more appropriate to use an std::set. You can then use a custom comparison object to consider small changes as being inconsequential.

Answer 6

Hi you could comprare like this

bool isAlmostEquals(const double &f1, const double &f2)
{
  double allowedDif = xxxx;
  return (abs(f1 - f2) <= allowedDif);
}

but it depends of your compare range and the double precision is not on your side

if your vector is sorted you could use std::unique with the function as predicate

Answer 7

I would do the following:

1. Create a set<double>

2. go through your vector in a loop or using a functor

3. Round each element and insert into the set

4. Then you can swap your vector with an empty vector

5. Copy all elements from the set to the empty vector

The complexity of this approach will be n * log(n) but it's simpler and can be done in a few lines of code. The memory consumption will double from just storing the vector. In addition set consumes slightly more memory per each element than vector. However, you will destroy it after using.

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());