代码之家  ›  专栏  ›  技术社区  ›  Hao Wooi Lim

利用结构上唯一的STL向量

  •  2
  • Hao Wooi Lim  · 技术社区  · 15 年前

    在编程任务中,我试图确保一个特定的向量只包含唯一的项。对于基元类型,操作简单如下:

    vector<int> lala;
    lala.push_back(1);
    lala.push_back(99);
    lala.push_back(3);
    lala.push_back(99);
    
    sort(lala.begin(), lala.end()); // lala: 1, 3, 99, 99
    lala.erase(unique(lala.begin(), lala.end()), lala.end()); // lala: 1, 3, 99
    

    但是,问题是我没有使用int,但是:

    typedef struct
    {
        int x;
        int y;
        int maxX;
        int maxY;
        int width;
        int height;
        int id;
    } Rect;
    
    bool SameRect(Rect first, Rect second)
    {
        return first.x      == second.x &&
               first.y      == second.y &&
               first.width  == second.width &&
               first.height == second.height &&
               first.maxX   == second.maxX &&
               first.maxY   == second.maxY;
    }
    
    //...
    vector<Rect> lala;
    //...
    sort(lala.begin(), lala.end());
    lala.erase(unique(lala.begin(), lala.end(), SameRect), lala.end());
    //...
    

    不太管用。我做错了什么?

    编辑:

    根据sth的建议,我为std::sort()实现了两个排序谓词:

    bool SortRect(const Rect &first, const Rect &second)
    {
        if (first.x < second.x) return true;
        if (first.x > second.x) return false;
    
        if (first.y < second.y) return true;
        if (first.y > second.y) return false;
    
        if (first.maxX < second.maxX) return true;
        if (first.maxX > second.maxX) return false;
    
        if (first.maxY < second.maxY) return true;
        if (first.maxY > second.maxY) return false;
    
        if (first.width < second.width) return true;
        if (first.width > second.width) return false;
    
        if (first.height < second.height) return true;
        if (first.height > second.height) return false;
    
        if (first.id < second.id) return true;
        if (first.id > second.id) return false;
    
        return false;
    }
    

    但我发现它的效果与:

    bool SortRect(const Rect &first, const Rect &second)
    {
        return first.x < second.x;
    }
    

    如果SGI的文件有什么需要的话。较短、简单的排序谓词也应该工作。我的测试已经证实了这一点(尽管我没有尝试所有可能的组合)。

    5 回复  |  直到 11 年前
        1
  •  5
  •   sth    11 年前

    您还必须定义一个比较函数, sort() 对rect进行排序。这个 comparison function 应该实现 strict weak ordering 这样相等的元素在向量中彼此相邻。

    如果向量没有排序, unique() 将找不到未排序的重复元素。

        2
  •  4
  •   Georg Fritzsche    15 年前

    你为什么不用 std::set 首先?其内容保证是独一无二的。

    Sidenotes:
    你不需要 typedef C++中的结构 struct Rect {}; 足够了。
    比较函数应该采用常量引用(即 const Rect& )因为它不需要修改它们,也不需要副本。

        3
  •  1
  •   Alexander Gessler    15 年前

    sort(lala.begin(), lala.end());

    将如何 std::sort 知道如何排序 Rect S?合适吗?定义一个比较函数并将其作为第三个参数传递,正如您在 std::unique . 一定要两个人 直肠切除术 s作为参数,如果第一个是第二个,则返回true。

    例如:

    bool CompareRect(const Rect& first, const Rect& second) {
        return first.id<second.id;
    }
    

    注意,我正在通过 直肠 作为常量引用,您似乎在示例中忘记了这一点。

        4
  •  0
  •   Hao Wooi Lim    15 年前

    这就是我想到的:

    我在排序函数中添加了一个谓词:

    bool SortRect(const Rect &first, const Rect &second)
    {
        if (first.x < second.x) return true;
        if (first.x > second.x) return false;
    
        if (first.y < second.y) return true;
        if (first.y > second.y) return false;
    
        if (first.maxX < second.maxX) return true;
        if (first.maxX > second.maxX) return false;
    
        if (first.maxY < second.maxY) return true;
        if (first.maxY > second.maxY) return false;
    
        if (first.width < second.width) return true;
        if (first.width > second.width) return false;
    
        if (first.height < second.height) return true;
        if (first.height > second.height) return false;
    
        if (first.id < second.id) return true;
        if (first.id > second.id) return false;
    
        return false;
    }
    

    但我发现它的效果与:

    bool SortRect(const Rect &first, const Rect &second)
    {
        return first.x < second.x;
    }
    

    那么,就像某个东西说的,我只需要对第一个元素进行排序(为了使唯一的函数能够正常工作)?

        5
  •  0
  •   Community CDub    8 年前

    我不确定您要实现什么,但一般来说,正如所指出的,您需要设计出矩形的比较结果。是什么使一个矩形在一个序列中排在另一个矩形之前?

    最简单的变体之一是在x坐标上进行比较。更复杂的选择是根据为矩形计算的希尔伯特值进行排序。见问题计算 Hilbert value of a point for use in a Hilbert R-Tree?

    也许你正在研究某种空间索引,然后了解 R-tree