c++ - 如何删除 vector 的重复坐标

Question

我把点的坐标传给vector，有一些重复的点，所以我想删除其他重复的点，只保留唯一的点。

例如:

vector<Point2f>  points;

points[0]=Point2f(1,1);
points[1]=Point2f(2,3);
points[2]=Point2f(1,1);
points[3]=Point2f(2,3);
points[4]=Point2f(1,1);
points[5]=Point2f(4,1);

我想得到这样的结果:

points[0]=Point2f(1,1);
points[1]=Point2f(2,3);
points[2]=Point2f(4,1);

PS 元素顺序不变

我试过的显示如下:

#include <opencv2/core/core.hpp>

#include <vector>
#include<iostream>

using namespace std;
using namespace cv;

int main()
{
    vector<Point2f>  pointTemp;

    pointTemp[0]=Point2f(1,1);
    pointTemp[1]=Point2f(2,3);
    pointTemp[2]=Point2f(1,1);
    pointTemp[3]=Point2f(2,3);
    pointTemp[4]=Point2f(1,1);
    pointTemp[5]=Point2f(4,1);

    for(vector<Point2f>::iterator it=pointTemp.begin();it!=pointTemp.end();it++)
    {
        for(vector<Point2f>::iterator it1=it+1;it1!=pointTemp.end();)
        {
            if(it->x==it1->x&&it->y==it1->y)
            {
                it1=pointTemp.erase(it1);
            }
            else
            {
                it1++;
            }
        }
    }
    //cout<<pointTemp.size()<<endl;

    return 0;
}

Answer 1

这是我的破解方法。它可能需要您将 --std=c++11 作为 g++ 的参数传递。请注意，唯一元素的插入顺序保持不变。运行时复杂度也是 O(N)。

// remove_duplicates: removes all duplicated elements from the vector passed in
void remove_duplicates(std::vector<Point2f>& vec)
{
    std::unordered_set<Point2f> pointset;  // unordered_set is a hash table implementation

    auto itor = vec.begin();
    while (itor != vec.end())
    {
        if (pointset.find(*itor) != pointset.end())   // O(1) lookup time for unordered_set
        {
            itor = vec.erase(itor); // vec.erase returns the next valid iterator
        }
        else
        {
            pointset.insert(*itor);
            itor++;
        }
    }
}

上述函数是使用 unordered_set 的结果，需要先前为 Point2f 声明的哈希函数。您可以随心所欲地定义它。我的简单实现如下。

您可能还需要为 Point2f 定义一个 == 运算符以及适当的构造函数来满足 vector 和 unordered_set 语义。

完整的代码 list :

#include <vector>
#include <unordered_set>


struct Point2f
{
    float x;
    float y;
    Point2f(float a, float b) : x(a), y(b) {}
    Point2f() : x(0), y(0) {}
};

bool operator==(const Point2f& pt1, const Point2f& pt2)
{
    return ((pt1.x == pt2.x) && (pt1.y == pt2.y));
}

namespace std
{
    template<>
    struct hash<Point2f>
    {
        size_t operator()(Point2f const& pt) const
        {
            return (size_t)(pt.x*100 + pt.y);
        }
    };
}


void removedupes(std::vector<Point2f> & vec)
{
    std::unordered_set<Point2f> pointset;

    auto itor = vec.begin();
    while (itor != vec.end())
    {
        if (pointset.find(*itor) != pointset.end())
        {
            itor = vec.erase(itor);
        }
        else
        {
            pointset.insert(*itor);
            itor++;
        }
    }
}


int main(int argc, char* argv[])
{
    std::vector<Point2f>  pointTemp;

    pointTemp.resize(6);

    pointTemp[0]=Point2f(1,1);
    pointTemp[1]=Point2f(2,3);
    pointTemp[2]=Point2f(1,1);
    pointTemp[3]=Point2f(2,3);
    pointTemp[4]=Point2f(1,1);
    pointTemp[5]=Point2f(4,1);

    removedupes(pointTemp);

    return 0;
}