Есть 3 вектора координат: x_vect
, y_vect
, z_vect
. Они содержат координаты точек, т.е. координата одной i-ой точки - это (x_vect[i]
, y_vect[i]
, z_vect[i]
). Но точки повторяются. Необходимо сделать так, чтобы в итоге остались все точки, но без повторений. Необходимо убрать дубликаты точек.
5 ответов
Можно использовать множество, std::set
:
UPD
struct Point {
int x;
int y;
int z;
};
std::set<Point> pointsSet;
UPD2
Пример на пальцах.
-
не подскажите, как реализовать это в деле? т.е. как в set добавлять наюор из (x_vect[i], y_vect[i], z_vect[i]). с insert возникают проблемы 10 апр 2011 в 9:52
-
-
-
1Вы на 100% уверены, что если есть
operator <
, тоoperator =
можно не определять? Алгоритм поискаstd::set
же не знает, что вы определили только одну из операций корректно. Не пожалейте две строчки, определите иoperator =
, меньше геморроя будет.– VladD18 мар 2013 в 10:13 -
3Оператор == для set не нужен. cplusplus.com/reference/set/set . set использует только предикат с семантикой строгого оператора сравнения, который передан в шаблонном параметре Compare. Оператор < используется по умолчанию (через функтор less<T>).– quyse18 мар 2013 в 16:43
Строить set для удаления дубликатов не хорошо, так как set гораздо медленнее вектора, и потребляет порядочно больше памяти. Для такой простой задачи гораздо лучше просто отсортировать вектор. Известно, что из отсортированной последовательности удалить дубликаты легко, причём за линейное время. Более того, в STL для этого уже есть готовая функция unique.
//для вектора
#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 содержит только уникальные точки
Добавить методы для инициализации, что бы удобней было заполнять структуру. И в чем именно у вас проблемы с 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);
}
как то так ...
-
дело в том, что написана довольно крупная программа, в ней всё построено на vector, и данные, которые необходимо обработать таким образом тоже в vector 10 апр 2011 в 10:23
-
-
2Вадим Владимиров, в таком случае проблема в архитектуре системы, постарайтесь сделать рефакторинг, иначе в будущем может появиться много костылей для программы и костылей для костылей =) 10 апр 2011 в 10:53
-
1Ну тогда 2 вложенных цикла, и ищем такие же координаты, нашли - удаляем "Должен остаться только один!!"(с) Но работать это будет не очень быстро 10 апр 2011 в 16:26
-
4можно просто пробежать по массиву и закидывать ВСЕ значения в множество, в итоге там останутся только уникальные значения (мне прям стыдно такое писать =) ) <br/> P.S. что ж за ВУЗ, где дипломы таким образом пишутся? да и зачем писать такой диплом, который полетит "фтопку"? а что потенциальному работодателю показывать собираетесь? (простите) быдлокод с костылями на каждом шагу?.. но, дело Ваше... 10 апр 2011 в 20:23
Если не хочется избавляться от векторов, то можно сделать так:
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);
}
Для правильной компиляции в ответе shurik'а и 1101_debian не хватает реализации оператора < для структуры. dzhioev исправил это, но написал ИМХО громоздко.
Попытаюсь дать решение попроще: =)
#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;
}
Итого: используйте функцию Unique для получения уникальных точек из общего набора и вывода их на экран.