c++ - 具有通用索引类型的数组

Question

C++11/STL/Boost 中是否有任何数据结构表示具有通用索引类型的数组，还是我必须自己实现这样的类型？

即我想做这样的事情:

std::set<std::string>> to_lookup, to_lookup2;
int i = 10, j = 13;

// initialization of to_lookup

// count is of the container type/data structure I am looking for
count[to_lookup] = i;
count[to_lookup2] = j;

我知道来自 STL 的 std::map 和 std::unordered_map 容器，但它们不符合我的要求。插入和查找可以在 O(1) 中完成对我来说至关重要。

Answer 1

如果您已经在使用 std::unordered_map，这基本上几乎不可能显着 boost 速度，这仅仅是因为基于元素的数量总会有一些开销(所以您可以无法获得完美的 O(1)(除非您能够将所有可能的键作为数组中的索引进行引用)。

但是，如果您仍然认为 std::unordered_map 仅仅是因为条目数量太多而太慢，请尝试添加另一个层以减少映射中的元素数量。

在您的示例中，使用 std::string 作为键 (?)，您可以只使用第一个字符(未经测试但应该有效):

std::vector<std::unordered_map<const std::string, myWhateverType> > container(256);

// To access an element, this just adds one more layer:
container[key[0]][key] = value;

遍历所有元素会变得有点复杂。然而，这实质上将 std::unordered_map 中的元素数量减少到 1/255(当然取决于键值的实际分布；如果所有键都以诸如 key 之类的东西开头，那么除了少量的开销之外，您将一无所获。

它会 boost 性能吗？这实际上取决于条目数和您的 key 。