如何使STD :: MAP不需要两次比较整个字符串?

发布于 2025-02-07 04:06:04 字数 2031 浏览 0 评论 0原文

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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文