سریع ترین روش برای حذف نقاط تکراری

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);

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

پیشنهاد دوستان چیه؟

Comments

چرا از اول از set استفاده نمی‌کنید. این جا روش برای تبدیل هست: http://stackoverflow.com/questions/20052674/how-to-convert-vector-to-set
قائدتا الگوریتم تبدیل در کتابخانه استاندارد باید سریع باشه.

---

set ترتیب رو رعایت نمی کنه .

---

حرفی از ترتیب نیست. حرف از حذف تکراری‌هاست. در ضمن set ترتیب داره این طور که این جا نوشته: http://www.cplusplus.com/reference/set/set/

---

منظور من از ترتیب این نیست .
شما فرض کنید ورودی اینه
[4,1]
[4,1]
[1,1]
باید وقتی حذف شد نتیجه این بشه :
[4,1]
[1,1]
که با set میشه
[1,1]
[4,1]
ایشون داخل سوال یادشون رفته  حرفی از ترتیب بزنن ولی داخل پیام خصوصی که به من دادن ذکر کردن که ترتیب هم مهمه !

---

اگه ترتیب لازمه هیچچی. ولی می‌شه یه اندیس اضافه کرد که نشان دهندۀ ترتیب باشه و اونو به set  داد. هر چند به دردسرش نمی‌یرزه.

---

این جا: http://stackoverflow.com/a/9366613/2029077
و این جا http://stackoverflow.com/questions/1453333/how-to-make-elements-of-vector-unique-remove-non-adjacent-duplicates
راه حل‌هایی هست.

Answer 1

به نظر من از 2 میشه اشتفاده کرد:

روش اول مرتب سازی 2 بعدی با حفظ شاخص که پس از مرتب سازی به راحتی با یک پیمایش می تونید کلیه نقاط تکراری را حذف کنید.

روش دوم استفاده از hash برای یافتن نقاط تکراری که در این پست هم توضیح داده شده.

 

روش hash:

#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;
}