Removing duplicates from std::vector

There are 3 coordinate vectors: x_vect, y_vect, z_vect. They contain the coordinates of the points, i.e. the coordinate of one i-th point is (x_vect[i], y_vect[i], z_vect[i]). But the dots are repeated. It is necessary to make sure that all the points remain in the end, but without repetitions. It is necessary to remove duplicate points.

Author: αλεχολυτ, 2011-04-10

5 answers

You can use set , std::set:

UPD

struct Point {
    int x;
    int y;
    int z;
};

std::set<Point> pointsSet;

UPD2

Example on the fingers.

 10
Author: AlexDenisov, 2016-10-02 08:45:06

Building a set to remove duplicates is not good, since a set is much slower than a vector, and consumes decently more memory. For such a simple task, it is much better to just sort the vector. It is known that it is easy to remove duplicates from a sorted sequence, and in linear time. Moreover, the STL already has a ready-made unique function for this.

//для вектора
#include <vector>
//для sort и unique
#include <algorithm>
using namespace std;

struct Point
{
    int x,y,z;
    Point(int x=0,int y=0,int z=0):x(x),y(y),z(z){}
};

//оператор меньше для sort
bool operator<(const Point& a, const Point& b)
{
    return a.x<b.x || a.x==b.x && (a.y<b.y || a.y==b.y && a.z<b.z);
}
//оператор проверки на равенство для unique
bool operator==(const Point& a, const Point& b)
{
    return a.x==b.x && a.y==b.y && a.z==b.z;
}

...

vector<Point> p;
...//как-то заполняем p
//сортируем
sort(p.begin(),p.end());
//и удаляем дубликаты
p.resize(unique(p.begin(),p.end())-p.begin());
//всё, теперь p содержит только уникальные точки
 8
Author: quyse, 2011-04-16 07:57:02

Add methods for initialization, which would be more convenient to fill in the structure. And what exactly is your problem with insert ?

struct {
    int x;
    int y;
    int z;
    Point(){ x = 0; y = 0; z = 0; }
    Point(int _x, int _y, int _z){ x = _x; y = _y; z = _z; }

}typedef Point;

std::set<Point> pointsSet;

for(;;){
   Point p(x,y,z);
   pointsSet.insert(p);
}

Something like that ...

 3
Author: Alex Kapustin, 2011-04-10 10:17:40

If you don't want to get rid of vectors, you can do this:

class Point {
    typedef std::vector<int> Coords;
public:
    Point(size_t index,
          const Coords& x,
          const Coords& y,
          const Coords& z)
        : index_(index),
          x_(x),
          y_(y),
          z_(z)
    {}

    bool operator<(const Point& other) const {
        return (x() < other.x())
               || (x() == other.x() && y() < other.y())
               || (x() == other.x() && y() == other.y() && z() < other.z());
    }

    int x() const {
        return x_[index_];
    }

    int y() const {
        return y_[index_];
    }

    int z() const {
        return z_[index_];
    }

private:
    size_t index_;
    const Coords& x_;
    const Coords& y_;
    const Coords& z_;
};

void removeDuplicates(std::vector<int>& x,
                      std::vector<int>& y,
                      std::vector<int>& z)
{
    std::set<Point> points;
    for (size_t i = 0; i < x.size(); ++i) {
        points.insert(Point(i, x, y, z));
    }
    std::vector<int> newX, newY, newZ;
    for (std::set<Point>::const_iterator it = points.begin();
         it != points.end();
         ++it)
    {
        newX.push_back(it->x());
        newY.push_back(it->y());
        newZ.push_back(it->z());
    } 
    x.swap(newX);
    y.swap(newY);
    z.swap(newZ);
}
 2
Author: dzhioev, 2011-04-11 09:03:16

For proper compilation, the response of shurik and 1101_debian lacks the implementation of the

I will try to give a simpler solution:=)


 #include <iostream>
 #include <vector>
 #include <set>

struct Point {
    int x, y, z;
    Point( int _x, int _y, int _z )
      : x(_x), y(_y), z(_z)
    {}
    //
    bool operator< ( const Point& r ) const
    {
        return (x < r.x)
               || (x == r.x && y < r.y)
               || (x == r.x && y == r.y && z < r.z);
    }

};
// Функция уникализирует точки; результат - в uniq_points
void Unique( std::vector<int>& x_vect, std::vector<int>& y_vect, std::vector<int>& z_vect )
{
    std::set<Point> uniq_points;
    // Предполагается, что размерность векторов одинакова.
    for (unsigned i = 0; i < x_vect.size(); ++i) {
        uniq_points.insert(Point(x_vect[i], y_vect[i], z_vect[i]));
    }
    // Печатаем уникальные точки
    std::set<Point>::const_iterator it = uniq_points.begin(), e = uniq_points.end();
    for (; it != e; ++it) {
        std::cout << "(" << it->x << "," << it->y << "," << it->z << ")" << std::endl;
    }
}

int main()
{
    // Заполняем векторы неуникальными точками.
    std::vector<int> x_vect, y_vect, z_vect;
    for (int i = 0; i < 10; ++i) {
        x_vect.push_back(i);
        y_vect.push_back(i);
        z_vect.push_back(i);
        // Создаём неуникальные точки
        x_vect.push_back(i);
        y_vect.push_back(i);
        z_vect.push_back(i);
    }
    // Уникализируем и выводим
    Unique(x_vect, y_vect, z_vect);
    return 0;
}

Total: Use the Unique function to get unique points from a common set and display them on the screen.

 0
Author: Alex Medveshchek, 2011-04-12 11:31:47