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

Question

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

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

编辑：按序数并不像 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
}

Answer 2

如果您很少修改数组，则可以保持其排序并对其使用 binary_search在 O(logn) 时间内通过键查找元素（从技术上讲，O(klogn)，因为您使用的是字符串 [其中 k 是键字符串的平均长度] ).
当然，这（就像使用 map 或 unordered_map 一样）会弄乱您的序数检索，因为元素将以排序顺序而不是插入顺序存储。

Answer 3

使用向量和映射：

std::vector<your_struct> elements;
std::map<std::string, int> index;

映射允许您在 O(lg n) 时间内检索键的索引，而向量允许通过索引访问 O(1) 元素。

Answer 4

使用哈希图