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?



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;
            return false;

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

std::vector<Point> noDupVec( sp.begin(), sp.end());
commented: Good idea. +2

You could check before adding it to the vector.

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

commented: staying with a vector is better than going to a set and then back again :) +2

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.

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.


Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.