c ++以不止一种方式访问相同的元素

Question

我的 Item class 如下所示：

class Item {
    int unique_key;
    long property;
};

我有一个或多个项目，我需要在恒定的 O(1) 时间内通过 unique_key（每个项目不同）和 property（更多项目可以具有相同的属性).

我正在考虑这样的事情：

std::map<int, Item*> my_map1;
std::multimap<long, Item*> my_map2;

但我想知道是否有其他更好的解决方案可以使用更少的内存并避免保持地图同步。

Answer 1

I need to access them in constant O(1) time

std::map 和 std::multi_map 都没有固定时间访问元素，都是 O(lg N)。如果您需要持续访问，则必须使用 std::unordered_map and std::unordered_multimap，这两个容器都是在 C++11 中引入的。

如果您无法访问 C++11 编译器，那么就没有 dictionary/hashtable 容器可以进行恒定时间访问。

但是，如果unique_key的生成方式是0...N，而property也是0...M，对于某些N , M, 那么你可以简单地拥有：

std::vector<Item*> my_map1;
std::vector<std::vector<Item*>> my_map2;

如果您有密集的 ID 集合，那将是持续访问并且是最有效的解决方案。但是如果 ID 的集合是稀疏的（例如，你的 ID 可能有 0、500 和 1000 万），那么这个解决方案就很糟糕了。

c++ access same elements in more than one way