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

Question

我的 Item 类如下所示:

class Item {
    int unique_key;
    long property;
};

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

我在想这样的事情:

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

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

Answer 1

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

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

如果您无法访问 C++11 编译器，那么就没有可进行恒定时间访问的字典/哈希表容器。

但是，如果 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 万)，那么这个解决方案就很糟糕了。