Remove duplicates from a vector where < is not defined

[daviddoria]

To remove duplicates from a vector, my first thought was to insert them all into a set, it would take care of the uniqueness of the elements, and then read them back out into my vector. However, I have a vector<Point>, where Point is a point in 3d space (ie. x,y,z). So the < operator is ill-defined. How else can I remove duplicate points without looping through the entire vector for each element and testing equality?

Thanks,

Dave

[boblied]

For the purpose of sorting, any complete ordering will do. You could define a sort that uses x as primary key, y as secondary, and z as tiebreaker.

// Comparator function object to define less-than for Points
struct PointLess
{
    bool operator()(const Point& p1, const Point& p2) const
    {
        if ( p1.x < p2.x )
            return true;
        else if ( p2.x < p1.x )
            return false;
        // assert(p1.x == p2.x )
        if ( p1.y < p2.y )
            return true;
        else if ( p2.y < p1.y )
            return false;
        // assert(p1.x == p2.x && p1.y == p2.y )
        if ( p1.z < p2.z )
            return true;
        else
            return false;
    }
};

std::set<Point, PointLess> sp( pointVec.begin(), pointVec.end() );

std::vector<Point> noDupVec( sp.begin(), sp.end());

[Ancient Dragon]

You could check before adding it to the vector.

[Narue]

Have you looked into the standard library? There's a std::unique and std::unique_copy function.

[boblied]

Have you looked into the standard library? There's a std::unique and std::unique_copy function.

std::unique requires that the duplicate elements are next to each other in the vector. The vector would have to be sorted and you end up back at defining a predicate for ordering the elements. It might be more expressive of the intent, though.

[daviddoria]

Cool, that'll do it. I sorted the points and then used unique.

sort(Points.begin(), Points.end());
	vector<Point>::iterator new_end = unique(Points.begin(), Points.end());
	Points.erase(new_end, Points.end());

Thanks all.

Dave