C++优雅判断类实例在std::vector的存在性、去重实现及报错解决
移除冗余占位点的正确实现
空vector调用std::find是完全合法的行为:当查找区间为空时,std::find直接返回区间尾迭代器,天然满足“未找到重复元素”的判断逻辑,之前引入占位点的写法属于完全多余的操作,只需要删掉所有和to_erase相关的代码、把循环边界从M+1改回M、去掉循环结束后的头部删除步骤即可。
注意原代码存在逻辑bug:循环内生成坐标后调用point.set(x,y),但去重判断时查找的是未被赋值的to_add对象,会直接导致去重逻辑失效,修正时需要把生成的坐标直接构造为待检查的候选对象,不要混淆赋值和判断的目标。另外std::uniform_int_distribution实例可复用,不需要每次循环都重新构造,提到循环外部即可减少不必要的开销。
修正后的基础实现(保留vector+std::find的逻辑,完全移除占位):
#include <algorithm> #include <random> #include <vector> #include <iostream> #include <cstdlib> std::mt19937 mt(std::random_device{}()); std::vector<Point> InitList(int M) { if (M <= 0) { std::cout << "InitList: Length of vector must be greater than zero. Don't play around!" << std::endl; exit(EXIT_FAILURE); } std::uniform_int_distribution<int> coord_dist(0, 100); std::vector<Point> vec; // 提前申请容量减少动态扩容开销 vec.reserve(M); while (vec.size() < M) { int x = coord_dist(mt); int y = coord_dist(mt); Point candidate(x, y); // 空向量场景下find直接返回end(),天然适配去重判断 if (std::find(vec.begin(), vec.end(), candidate) == vec.end()) { vec.push_back(candidate); } } return vec; }
unordered_set编译报错的解决方法
这里报错提示里的Site就是你代码中的Point类(大概率是后续改名导致的命名不一致),核心错误原因是:std::unordered_set存储自定义类型时,必须满足两个前置要求,你的代码刚好缺这两个必要实现:
- 需要可调用的相等比较逻辑:用于判断两个对象是否重复,默认的
std::equal_to<Point>会自动调用类的operator==重载 - 需要针对自定义类型的哈希计算函数:标准库没有内置将Point类实例映射为
size_t类型哈希值的逻辑,默认的std::hash<Point>会被编译器隐式删除,这就是报错中“use of deleted function”的直接来源
具体实现步骤
- 给Point类补全相等比较逻辑
class Point { int x, y; public: Point(int x_ = 0, int y_ = 0) : x(x_), y(y_) {} // 补全相等比较,供去重判断使用 bool operator==(const Point& other) const { return x == other.x && y == other.y; } int getX() const { return x; } int getY() const { return y; } }; - 补充Point类型的哈希计算逻辑,可二选一:
- 方式一:特化
std::hash模板,让标准库能识别Point类型的哈希规则// 放在全局命名空间、Point类定义之后 namespace std { template<> struct hash<Point> { size_t operator()(const Point& p) const noexcept { size_t h1 = hash<int>()(p.getX()); size_t h2 = hash<int>()(p.getY()); // 组合两个整数的哈希值,降低碰撞概率 return h1 ^ (h2 << 1); } }; } - 方式二:构造unordered_set时手动传入自定义哈希函数,不需要侵入标准库模板
auto point_hash = [](const Point& p) { size_t h1 = std::hash<int>()(p.getX()); size_t h2 = std::hash<int>()(p.getY()); return h1 ^ (h2 << 1); };
- 方式一:特化
- 用unordered_set实现去重逻辑,攒够M个不重复的点后直接转成vector返回即可,相比每次遍历vector查找重复的O(n)复杂度,unordered_set的平均O(1)查找效率在M值较大时优势明显:
std::vector<Point> InitList(int M) { if (M <= 0) { std::cout << "InitList: Length of vector must be greater than zero. Don't play around!" << std::endl; exit(EXIT_FAILURE); } std::mt19937 mt(std::random_device{}()); std::uniform_int_distribution<int> coord_dist(0, 100); auto point_hash = [](const Point& p) { size_t h1 = std::hash<int>()(p.getX()); size_t h2 = std::hash<int>()(p.getY()); return h1 ^ (h2 << 1); }; std::unordered_set<Point, decltype(point_hash)> unique_points; unique_points.reserve(M); while (unique_points.size() < M) { int x = coord_dist(mt); int y = coord_dist(mt); unique_points.emplace(x, y); } // 从set转成目标vector返回 return std::vector<Point>(unique_points.begin(), unique_points.end()); }
如果不想为Point类补写哈希和相等比较逻辑,也可以先用std::set<std::pair<int,int>>存生成的坐标对(标准库内置了pair的比较和排序逻辑),等攒够M个不重复坐标后,再批量构造Point实例塞进vector即可,适合快速实现的场景。
内容的提问来源于stack exchange,提问作者Angelos
相关产品推荐
相关产品推荐

