如何为boost::geometry::box编写排序谓词以移除重复元素？

首先，Boost.Geometry确实提供了现成的比较函数可以用来编写排序谓词——boost::geometry::less，它专门为几何类型（包括box）实现了严格弱序比较，完全符合std::list::sort对谓词的要求，不用你从头编写复杂的比较逻辑。

一、用boost::geometry::less实现排序谓词 #

你只需要基于这个函数，封装一个针对Feature结构体的比较逻辑，聚焦在bounds成员上即可。示例代码如下：

#include <boost/geometry/algorithms/less.hpp>

// 排序谓词：比较两个Feature的bounds
bool feature_sort_pred(const Feature& lhs, const Feature& rhs) {
    return boost::geometry::less(lhs.bounds, rhs.bounds);
}

// 执行排序+去重流程
v.sort(feature_sort_pred);
auto last = std::unique(v.begin(), v.end());
v.erase(last, v.end());

boost::geometry::less对box的比较逻辑是：先对比最小角（min_corner）的x坐标，相等则比y坐标；若最小角完全一致，再对比最大角（max_corner）的x、y坐标。这个逻辑严格遵循严格弱序规则，既能保证排序的正确性，也能让std::unique准确识别连续的重复元素。

二、Boost.Geometry场景下的其他去重思路 #

除了sort + unique的经典组合，还有两种适配不同需求的方案：

1. 用有序容器自动去重 #

如果你不需要保留原列表的元素顺序，可以直接把Feature存入std::set——插入过程会自动完成排序和去重。只需要为Feature指定基于boost::geometry::less的比较规则：

#include <set>

// 定义Feature的比较规则
struct FeatureCompare {
    bool operator()(const Feature& lhs, const Feature& rhs) const {
        return boost::geometry::less(lhs.bounds, rhs.bounds);
    }
};

// 直接通过set去重
std::set<Feature, FeatureCompare> feature_set(v.begin(), v.end());
// 若需要转回list，直接赋值即可
v.assign(feature_set.begin(), feature_set.end());

这种方式代码更简洁，但会改变元素顺序，时间复杂度和sort相当（O(n log n)）。

2. 用无序容器实现高效去重（无需排序） #

如果你的场景不需要排序后的结果，且追求更高的插入/查找效率，可以尝试std::unordered_set。不过Boost.Geometry没有默认提供box的哈希特化，需要你自定义哈希函数：

#include <unordered_set>

// 为box自定义哈希函数
struct BoxHash {
    std::size_t operator()(const Feature::box& b) const {
        std::size_t h1 = std::hash<double>()(boost::geometry::get<0>(b.min_corner()));
        std::size_t h2 = std::hash<double>()(boost::geometry::get<1>(b.min_corner()));
        std::size_t h3 = std::hash<double>()(boost::geometry::get<0>(b.max_corner()));
        std::size_t h4 = std::hash<double>()(boost::geometry::get<1>(b.max_corner()));
        // 组合哈希值减少碰撞概率
        return h1 ^ (h2 << 1) ^ (h3 << 2) ^ (h4 << 3);
    }
};

// 定义Feature的哈希和相等判断
struct FeatureHash {
    std::size_t operator()(const Feature& f) const {
        return BoxHash()(f.bounds);
    }
};

struct FeatureEqual {
    bool operator()(const Feature& lhs, const Feature& rhs) const {
        return boost::geometry::equals(lhs.bounds, rhs.bounds);
    }
};

// 用unordered_set去重
std::unordered_set<Feature, FeatureHash, FeatureEqual> feature_unordered_set(v.begin(), v.end());
v.assign(feature_unordered_set.begin(), feature_unordered_set.end());

这种方式平均时间复杂度为O(n)，但要注意哈希函数的质量，避免过多碰撞影响性能。

总结 #

• 若需要保留排序后的结果，**sort + unique搭配boost::geometry::less**是最直接可靠的方案，不用自己造轮子；
• 若不需要原顺序，std::set的实现更简洁；追求高效则可以尝试std::unordered_set（需自定义哈希）。

内容的提问来源于stack exchange，提问作者martin_ljchan