c++ - 存储可通过键或序号 c++ 访问的数据的简单有效方法

Question

我需要创建一个可以通过字符串键或序号访问元素的数据结构。

该类当前使用包含字符串键和指向任何元素的指针的节点数组。这允许 O(n) 循环，或 O(1) 按序数获取元素，但是我发现按键查找元素的唯一方法是执行 O(n) 循环并比较键，直到找到什么我想要，当有 1000 多个元素时，这很慢。有没有办法使用键来引用指针，还是我运气不好？

编辑:by 序数不如 O(n) 循环重要。这将用作将被继承以用于其他方式的基础结构，例如，如果它是可绘制对象的结构，我希望能够在一个循环中绘制所有对象

Answer 1

您可以使用 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
}