如何实现具有多个键的快速地图？

发布于 2024-08-30 02:15:06 字数 394 浏览 8 评论 0原文

我正在寻找可以执行多个键查找的 C++ 关联映射容器类型。地图需要有恒定的时间查找，但我不在乎它是有序的还是无序的。它只需要快。

例如，我想在地图中存储一堆 std::vector 对象，并使用 int 和 void* 作为查找键。 int 和 void* 都必须匹配才能检索我的向量。

这样的容器已经存在吗？或者我必须自己推出？如果是这样，我该如何实施？我一直在尝试将 boost::unordered_map 存储在另一个 boost::unordered_map 中，但我还没有使用此方法取得任何成功。如果没有更简单的方法的话，也许我会继续潘兴这个方法。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

浅忆 2024-09-06 02:15:06

持续查找需要哈希图。您可以使用 boost::unordered_map (或tr1）。关键是组合哈希 int 和 void 指针。

回复收藏 0 原文

原来是傀儡 2024-09-06 02:15:06

如果你不想使用boost，你可以尝试map< int，map>。然而，查找的时间复杂度为 O(log(map size))。

回复收藏 0 原文

杯别 2024-09-06 02:15:06

自 C++11 起，您还可以使用 std::unordered_map，因为它似乎非常适合您的要求：

无序映射是一个关联容器，其中包含具有唯一键的键值对。元素的搜索、插入和删除具有平均恒定时间复杂度。

为了将 int 和 void* 组合成一个键，您可以使用 std::pair。

为了使无序映射与该对一起工作，您必须指定一个合适的哈希函数。为了使下面的示例简短，我使用手工制作的 lambda 表达式。如果此函数导致性能问题，您可能需要创建更复杂的哈希。

您没有指定向量的内容，因此为了简单起见，我选择了 int 。但是，您可以使解决方案适应任何矢量内容。总而言之，您的代码可能如下所示：

using Key = std::pair<int, void*>;
auto hash = [](const Key & k) {
    return std::hash<int>()(k.first) * 31 + std::hash<void*>()(k.second);
};
std::unordered_map<Key, std::vector<int>, decltype(hash)> um(8, hash);

Code on Ideone

Since C++11 you can also use an std::unordered_map, as it seems to fit your requirements quite nicely:

Unordered map is an associative container that contains key-value pairs with unique keys. Search, insertion, and removal of elements have average constant-time complexity.

In order to combine your int and void* into a single key, you can make use of std::pair.

To make the unordered map work with the pair, you have to specify a suitable hash function. In order to keep the following example short, I use a handcrafted combination of std::hash<> function calls inside a lambda expression. In case this function causes performance problems, you might want to create a more sophisticated hash.

You didn't specify the content of your vectors, so I chose int for the sake of simplicity. However, you can adapt the solution to any vector content. All in all your code could look as follows:

using Key = std::pair<int, void*>;
auto hash = [](const Key & k) {
    return std::hash<int>()(k.first) * 31 + std::hash<void*>()(k.second);
};
std::unordered_map<Key, std::vector<int>, decltype(hash)> um(8, hash);

Code on Ideone

回复收藏 0 原文