在我的应用程序中,我存储了一组包含 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)。也许吧,但可能有点矫枉过正。
- 维护另一个将外部引用映射到内部引用的映射。
在这些选项中,第三个选项似乎是最理智的。有没有更好的选择?
最佳答案
- 如果任一键几乎连续(即通常使用连续的值,中间没有太多未使用的数字),则数组 - 直接由该 id 索引 - 是最佳的,否则
- 如果您正在创建数值越来越大的新 key ,您可以
push_back
到vector
并使用std::binary_search
甚至 interpolation search , 否则 unordered_map
或map
。
一如既往 - 要知道什么是最快的,实现备选方案和衡量标准(但我已经按照预期的性能顺序在上面列出了它们)。
如果使用第一个或第三个选项,您可能希望将两个映射放入一个类中,以便在两者之间一致地进行插入和删除,并且仅在不需要时删除链接到的对象(您也可以使用共享来管理它指针,但这可能有点重量级 - 取决于您的需要。
关于c++ - 用于快速查找 2 个键的最快数据结构或算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26479650/