Q:

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

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.

A:

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:

Set read and write iterators to the beginning of the vector.
Start moving the read iterator through, checking elements against a hashset or octtree or something that allows finding nearby elements quickly.
For each element that collides with one in the hashset/octtree, advance the read iterator only.
For elements that do not collide, move from read iterator to write iterator, copy to hashset/octtree, then advance both.
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).

