c++ - 用于快速查找 2 个键的最快数据结构或算法

Question

在我的应用程序中，我存储了一组包含 2 个整数引用值的数据结构。

• 内部引用 - 代表数据库中的对象。
• 外部引用 - 外部世界如何引用对象。(他们不能使用相同的值)。

我正在使用以内部引用为键的 std::map，但这给我带来了一个问题，如果我必须通过外部引用查找，我可能必须遍历整个 map 以找到正确的条目。由于此列表可能包含数千个条目，因此考虑起来很痛苦。

下面的代码展示了一个简单的例子。

#include <iostream>
#include <map>

class MyData
{
    public:
    MyData(int internal_id, int external_id)
        : internal_id_(internal_id), external_id_(external_id) 
    {}
    int internal_id_;
    int external_id_;
    /* more data members ... */
};

int main(int argc, char** argv)
{
    std::map<int, MyData*> datamap;

    /*
        Build the map structure with arbitrary values.
    */
    for(int i = 0; i < 100; ++i)
    {
        MyData* md = new MyData(i, (100 - i));
        std::cout << md->internal_id_ << " " << md->external_id_ << std::endl; 
        datamap.insert(std::make_pair(i, md));
    }

    /*
        Find with internal id 50 Cheap lookup O(log N) (I think)

    */
    std::map<int, MyData*>::iterator it1;
    if((it1 = datamap.find(50)) != datamap.end())
    {
        std::cout << "Found Mydata with internal id 50 external id is " << it1->second->external_id_ << std::endl;
    }

    /* 
        Find with external id 35. Expensive lookup O(N)
    */
    std::map<int, MyData*>::iterator it2;

    for(it2 = datamap.begin(); it2 != datamap.end(); ++it2)
    {
        if(it2->second->external_id_ == 35)
        {
            std::cout << "Found with external id 35 internal id is " << it2->second->internal_id_ << std::endl;
            break;
        }
    }

    /* remove from map and clean up allocated MyData objects ... */
}

我可以采用哪种方法来改进从外部引用中查找？

我考虑了以下选项。

• 2 映射都指向同一事物但以不同的值作为键。
• 一个简单的数据库 (sqlite)。也许吧，但可能有点矫枉过正。
• 维护另一个将外部引用映射到内部引用的映射。

在这些选项中，第三个选项似乎是最理智的。有没有更好的选择？

Answer 1

• 如果任一键几乎连续(即通常使用连续的值，中间没有太多未使用的数字)，则数组 - 直接由该 id 索引 - 是最佳的，否则
• 如果您正在创建数值越来越大的新 key ，您可以push_back 到vector 并使用std::binary_search 甚至 interpolation search , 否则
• unordered_map 或 map。

一如既往 - 要知道什么是最快的，实现备选方案和衡量标准(但我已经按照预期的性能顺序在上面列出了它们)。

如果使用第一个或第三个选项，您可能希望将两个映射放入一个类中，以便在两者之间一致地进行插入和删除，并且仅在不需要时删除链接到的对象(您也可以使用共享来管理它指针，但这可能有点重量级 - 取决于您的需要。