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

Question

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

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

编辑:by序数与O(n)循环没那么重要.这将被用作基本结构,将继承以便以其他方式使用,例如,如果它是可绘制对象的结构,我希望能够在单个循环中绘制所有这些对象

Answer 1

您可以使用std::map的O(log n)搜索速度.查看此分支以获取更多详细信息 在这个分支中,正好讨论了您的情况(通过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
}