我有课
class Zaposlenik {
private:
string prezime;
string funkcija;
double placa;
public:
bool operator==(const string& prezime) const;
bool operator<(const string &prezime) const;
bool operator<(const Zaposlenik &other) const;
我使用带有字符串的运算符进行二分查找,使用带有 Zaposlenik 的运算符<进行排序
我无法更改 header 类我只能在.cpp 中编写代码。
我也有
class Firma {
private:
vector<Zaposlenik> zaposlenici;
public:
void sort();
我也不能改变那个类,我必须为它写.cpp。 我将 2.cpp 上传到自动分级服务器,该服务器将 500 000 Zaposlenik 输入到 vector zaposlenici,然后执行 2 000 000 次搜索。
我使用了 qsort 和 bsearch,但速度太慢了。上传时不能超过3s。
我写过重载运算符,我相信它们没问题,但显然 qsort 可以更快。
vector 按字符串首字母排序,名称从“aaaa”到“ZZZZ”,因此大小写字母的 4 个字母组合。
string funkcija;
和 double placa;
对排序没有任何意义。
有人能告诉我哪种排序比 qsort 更快吗?请记住,我对 main 没有任何控制权,并且在创建成员时我无法对其进行计数。
附言类中还有其他函数,但它们对这部分没有任何意义。 Bsearch 也有功能,但我相信它的速度是最快的。
最佳答案
三件事:
使用
std::sort
它比std::qsort
更快,因为它可以内联调用比较运算符(如果您在 header 中定义它或启用链接时优化)。Override
swap
为您的类(class),以便可以有效地交换它,而不是通过临时变量进行复制。但是,这需要更改 header (因为您需要访问私有(private)变量)。由于您排序的字符串的长度固定为 4,因此使用不同的排序算法会有所帮助。相当容易实现的经典选择是 radix sort .从您的一些评论来看,您的教授似乎希望您实现这一点。
关于C++ 排序类比 qsort 更快,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16279270/