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.
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.
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 содержит только уникальные точки
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 ...
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);
}
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.