我需要创建一个可以通过字符串键或序号访问元素的数据结构。
该类当前使用包含字符串键和指向任何元素的指针的节点数组。这允许 O(n) 循环,或 O(1) 按序数获取元素,但是我发现按键查找元素的唯一方法是执行 O(n) 循环并比较键,直到找到什么我想要,当有 1000 多个元素时,这很慢。有没有办法使用键来引用指针,还是我运气不好?
编辑:by 序数不如 O(n) 循环重要。这将用作将被继承以用于其他方式的基础结构,例如,如果它是可绘制对象的结构,我希望能够在一个循环中绘制所有对象
最佳答案
您可以使用 std::map
来提高 O(log n)
的搜索速度。查看this branch更多细节。在这个分支中,讨论了您的具体情况(通过 string
或/和 ordinal
键快速检索值)。
小例子(使用序号键,你可以用字符串做类似的事情):
#include <map>
#include <string>
using std::map;
using std::string;
struct dummy {
unsigned ordinal_key;
string dummy_body;
};
int main()
{
map<unsigned, dummy> lookup_map;
dummy d1;
d1.ordinal_key = 10;
lookup_map[d1.ordinal_key] = d1;
// ...
unsigned some_key = 20;
//determing if element with desired key is presented in map
if (lookup_map.find(some_key) != lookup_map.end())
//do stuff
}
关于c++ - 存储可通过键或序号 c++ 访问的数据的简单有效方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5907276/