What is the most efficient way of removing duplicates from a container only using almost equality criteria (no sort)

Question

How do I remove duplicates from a non sorted container (mainly vector) when I do not have the possibility to define operator< e.g. when I can only define a fuzzy compare function.

This answer using sort does not work since I cannot define a function for ordering the data.

template <typename T>
void removeDuplicatesComparable(T& cont){
 for(auto iter=cont.begin();iter!=cont.end();++iter){
    cont.erase(std::remove(boost::next(iter),cont.end(),*iter),cont.end());
 }
}

This is O(n²) and should be quite localized concerning cache hits. Is there a faster or at least neater solution?

Edit: On why I cannot use sets. I do geometric comparisons. An example could be this but I have other entities different from polygons as well.

bool match(SegPoly const& left,SegPoly const& right,double epsilon){
  double const cLengthCompare = 0.1; //just an example
  if(!isZero(left.getLength()- right.getLength(), cLengthCompare)) return false;
  double const interArea =areaOfPolygon(left.intersected(right)); //this is a geometric intersection
  if(!isZero(interArea-right.getArea(),epsilon)) return false;
  else return true;
}

So for such comparisons I would not know how to formulate sorting or a neat hash function.

Answer 1

First, don't remove elements one at a time.

Next, use a hash table (or similar structure) to detect duplicates.

If you don't need to preserve order, then copy all elements into a hashset (this destroys duplicates), then recreate the vector using the values left in the hashset.

If you need to preserve order, then:

1. Set read and write iterators to the beginning of the vector.
2. Start moving the read iterator through, checking elements against a hashset or octtree or something that allows finding nearby elements quickly.
3. For each element that collides with one in the hashset/octtree, advance the read iterator only.
4. For elements that do not collide, move from read iterator to write iterator, copy to hashset/octtree, then advance both.
5. When read iterator reaches the end, call erase to truncate the vector at the write iterator position.

The key advantage of the octtree is that while it doesn't let you immediately determine whether there is something close enough to be a "duplicate", it allows you to test against only near neighbors, excluding most of your dataset. So your algorithm might be O(N lg N) or even O(N lg lg N) depending on the spatial distribution.

Again, if you don't care about the ordering, you can actually move survivors into the hashset/octtree and at the end move them back into the vector (compactly).

Answer 2

If you don't want to rewrite your code to prevent duplicates from being placed in the vector to begin with, you can do something like this:

std::vector<Type> myVector;
// fill in the vector's data
std::unordered_set<Type> mySet(myVector.begin(), myVector.end());
myVector.assign(mySet.begin(), mySet.end());

Which will be of O(2 * n) = O(n).

std::set (or std::unordered_set - which uses a hash instead of a comparison) doesn't allow for duplicates, so it will eliminate them as the set is initialized. Then you re-assign the vector with the non-duplicated data.

Since you are insisting that you cannot create a hash, another alternative is to create a temporary vector:

std::vector<Type> vec1;
// fill vec1 with your data
std::vector<Type> vec2;
vec2.reserve(vec1.size()); // vec1.size() will be the maximum possible size for vec2
std::for_each(vec1.begin(), vec1.end(), [&](const Type& t)
{
    bool is_unique = true;
    for (std::vector<Type>::iterator it = vec2.begin(); it != vec2.end(); ++it)
    {
        if (!YourCustomEqualityFunction(s, t))
        {
            is_unique = false;
            break;
        }
    }

    if (is_unique)
    {
        vec2.push_back(t);
    }
});

vec1.swap(vec2);

If copies are a concern, switch to a vector of pointers, and you can decrease the memory reallocations:

std::vector<std::shared_ptr<Type>> vec1;
// fill vec1 with your data
std::vector<std::shared_ptr<Type>> vec2;
vec2.reserve(vec1.size()); // vec1.size() will be the maximum possible size for vec2
std::for_each(vec1.begin(), vec1.end(), [&](const std::shared_ptr<Type>& t)
{
    bool is_unique = true;
    for (std::vector<Type>::iterator it = vec2.begin(); it != vec2.end(); ++it)
    {
        if (!YourCustomEqualityFunction(*s, *t))
        {
            is_unique = false;
            break;
        }
    }

    if (is_unique)
    {
        vec2.push_back(t);
    }
});

vec1.swap(vec2);