如何使STD :: MAP不需要两次比较整个字符串?
std :: Map
通过检查要搜索的值是否小于与当前比较的值进行比较,因此,这意味着如果MAP
键是字符串,则将如果它们相等,需要将整个字符串进行两次比较。
我试图通过记录最后一个字符串来解决这个问题,并使用最后比较的结果,如果字符串相同。问题是我很确定这不是线程安全的,所以我认为每次使用MAP
时,我都需要使用锁定。
有更好的方法吗?
#include <iostream>
#include <chrono>
#include <string>
#include <map>
const char* lastComparedlhs = nullptr;
const char* lastComparedrhs = nullptr;
int lastCompResult = 0;
struct ComparerForMap
{
bool operator()(const std::string& lhs, const std::string& rhs) const
{
if (rhs.data() == lastComparedlhs && lhs.data() == lastComparedrhs)
{
lastComparedlhs = nullptr;
lastComparedrhs = nullptr;
return lastCompResult != 0;
}
lastComparedlhs = lhs.data();
lastComparedrhs = rhs.data();
lastCompResult = lhs.compare(rhs);
return lastCompResult < 0;
}
};
int main()
{
std::map<std::string, int> normalMap;
std::map<std::string, int, ComparerForMap> specialMap;
std::string str1(10000000, 'a');
std::string str2(str1);
normalMap[str1] = 123;
specialMap[str1] = 123;
auto start1 = std::chrono::high_resolution_clock::now();
int n1 = normalMap[str2];
auto stop1 = std::chrono::high_resolution_clock::now();
auto duration1 = std::chrono::duration_cast<std::chrono::nanoseconds>(stop1 - start1);
auto start2 = std::chrono::high_resolution_clock::now();
int n2 = specialMap[str2];
auto stop2 = std::chrono::high_resolution_clock::now();
auto duration2 = std::chrono::duration_cast<std::chrono::nanoseconds>(stop2 - start2);
std::cout << "normalMap: " << duration1.count() << '\n';
std::cout << "specialMap: " << duration2.count() << "\npress enter to exit\n";
// normalMap: about 4000000 ns
// specialMap: about 2000000 ns
char ch = getchar();
}
std::map
makes comparisons by checking if the value being searched for is less than the value currently being compared against, so this means if the map
keys are strings, it will need to compare the entire strings twice if they're equal.
I tried to get around this by recording the last strings compared, and using the result of the last comparison if the strings are the same. The problem is that I'm pretty sure this isn't thread safe, so I think I would need to use a lock every time I used the map
.
Is there a better way to do this?
#include <iostream>
#include <chrono>
#include <string>
#include <map>
const char* lastComparedlhs = nullptr;
const char* lastComparedrhs = nullptr;
int lastCompResult = 0;
struct ComparerForMap
{
bool operator()(const std::string& lhs, const std::string& rhs) const
{
if (rhs.data() == lastComparedlhs && lhs.data() == lastComparedrhs)
{
lastComparedlhs = nullptr;
lastComparedrhs = nullptr;
return lastCompResult != 0;
}
lastComparedlhs = lhs.data();
lastComparedrhs = rhs.data();
lastCompResult = lhs.compare(rhs);
return lastCompResult < 0;
}
};
int main()
{
std::map<std::string, int> normalMap;
std::map<std::string, int, ComparerForMap> specialMap;
std::string str1(10000000, 'a');
std::string str2(str1);
normalMap[str1] = 123;
specialMap[str1] = 123;
auto start1 = std::chrono::high_resolution_clock::now();
int n1 = normalMap[str2];
auto stop1 = std::chrono::high_resolution_clock::now();
auto duration1 = std::chrono::duration_cast<std::chrono::nanoseconds>(stop1 - start1);
auto start2 = std::chrono::high_resolution_clock::now();
int n2 = specialMap[str2];
auto stop2 = std::chrono::high_resolution_clock::now();
auto duration2 = std::chrono::duration_cast<std::chrono::nanoseconds>(stop2 - start2);
std::cout << "normalMap: " << duration1.count() << '\n';
std::cout << "specialMap: " << duration2.count() << "\npress enter to exit\n";
// normalMap: about 4000000 ns
// specialMap: about 2000000 ns
char ch = getchar();
}
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论