米拓建站模板,本地wordpress模板编辑器,免费作图网站,信息推广的方式有哪些std::set 是C标准库中的容器之一#xff0c;它基于红黑树实现。std::set 利用红黑树的特性来实现有序的插入、查找和删除操作#xff0c;并且具有较好的平均和最坏情况下的时间复杂度。 当向 std::set 插入元素时#xff0c;它会按照特定的比较函数#xff08;bool less标准库中的容器之一它基于红黑树实现。std::set 利用红黑树的特性来实现有序的插入、查找和删除操作并且具有较好的平均和最坏情况下的时间复杂度。 当向 std::set 插入元素时它会按照特定的比较函数bool lessT::operator() const(const T lhs, const T rhs)将新元素插入到红黑树的适当位置以保持树的有序性质。插入操作的平均时间复杂度为 O ( log n ) O(\log n) O(logn)其中 n n n是 std::set 中元素的数量。查找操作find()使用红黑树的性质通过比较函数在树中进行二分查找查找操作的平均时间复杂度为 O ( log n ) O(\log n) O(logn)。
但是当我们把 struct 放入 std::set 会有什么后果呢因为 std::set 需要在插入到时候排序所以需要重载 struct 的比较运算符这个时候就出现问题了首先我们定义一个结构体 Person
struct Person {Person(int _ID, string _name, int _age) : ID(_ID), age(_age), name(_name) {}int ID;int age;string name;
};当我们直接插入到 std::setPerson 中时会报 complier error 的错误因此简单补写一个比较运算符重载如下
bool operator(const Person lhs, const Person rhs) {return lhs.age rhs.age;
}OK编译起来没有问题但是我们运行测试一下下面的find操作就会发现问题
#include iostream
#include setusing namespace std;struct Person {Person(int _ID, string _name, int _age) : ID(_ID), age(_age), name(_name) {}int ID;int age;string name;
};bool operator(const Person lhs, const Person rhs) {return lhs.age rhs.age;
}int main() {setPerson person;for (int i 0; i 1000; i) {Person p_tmp(i, sxj, 10);person.insert(p_tmp);}Person p(2000, sxj, 10);auto it person.find(p);if (it ! person.end())cout Find Person --- ID: it-ID name: it-name age: it-age;elsecout Cant find endl;return 0;
}明明不在set中的 ID-2000 的Person也可以被找到。造成这个结果的原因是我们所提供的 operator() 当Person p1、p2在 p1p2 与 p2p2 都不成立时find 就会判断 p1 和 p2 是同一个 Person 因此会造成这样的错误结果。
解决方案就是补充完整我们的比较运算符重载完整代码如下
#include iostream
#include setusing namespace std;struct Person {Person(int _ID, string _name, int _age) : ID(_ID), age(_age), name(_name) {}int ID;int age;string name;
};bool operator(const Person lhs, const Person rhs) {if (lhs.ID rhs.ID) return true;if (lhs.ID rhs.ID) return false;if (lhs.name rhs.name) return true;if (lhs.name rhs.name) return false;return lhs.age rhs.age;
}int main() {setPerson person;for (int i 0; i 1000; i) {Person p_tmp(i, sxj, 10);person.insert(p_tmp);}Person p(2000, sxj, 10);auto it person.find(p);if (it ! person.end())cout Find Person --- ID: it-ID name: it-name age: it-age;elsecout Cant find endl;return 0;
}
