如何在 C++ STL 中实现具有三个键的映射？

Question

所以，我有一个 class

class table()
{
  public:
  string product, region, province ,price;
};

所以我有一个上面显示的对象数组 class 并且我的 objective 是编写一个函数，输入为产品、地区、省份，该函数在数组中搜索这个和 returns价格。

现在为了用最少的时间进行高效搜索，我想到了在 C++ 中使用 stl 映射，但我需要在我的映射中有 3 个键，价格作为值，所以我使用了这个。

struct key
{
string product, region, province;
};

我的地图定义是这样的。

unordered_map<key,string> mp;

地图中有三个键是否可行？
有 3 个键会影响地图的搜索时间复杂度吗？

我对计算机科学领域还是很陌生，所以请原谅我在这个问题上的任何错误，而且，如果我对地图的想法完全错误，稍微朝正确的方向推动对我来说将非常有帮助。谢谢你的时间。

Answer 1

如果您正在使用地图，那么您可以使用 tuple<type1, type2....>

map<tuple<int, int , int> , string> foo;

foo.insert(make_tuple(1,2,3), "bar");
foo[make_tuple(1,3,1)] = "bar1";
foo[{2,2,3}] = "bar2";

c++ tuple

Answer 2

std::map 更容易开始工作

struct key {
  std::string product, region, province;
  auto as_tie() const{
    return std::tie(product, region, province);
  }
  friend bool operator<( key const& lhs, key const& rhs ){
    return lhs.as_tie()<rhs.as_tie();
  }
};

现在 key 用作 std::map 中的键。在这里，我让 std 元组（通过 std tie）实现我的 < 运算符。

对于无序映射，您需要专门化 std hash 并提供 ==（或将 hasher/equality 函数对象传递给模板）。

在 C++20 中你可以

auto operator<=>(key const&)const =default;

而不是领带的东西，让地图工作。

3 部分键不会改变 big-O 地图的复杂性，无论是否有序。

无序映射仍然需要自定义哈希。

Answer 3

是的，您可以使用 std::unordered_map 做到这一点，而且并不像乍看起来那么困难。 std::unordered_map 关心的是：

密钥类型必须可以使用默认哈希算法或作为 template-parameter 类型或构造实例提供给容器的算法进行哈希处理。
密钥类型必须支持等价性检查（即使用类似于散列模板参数参数的自定义“等于”类型或默认 std::equals 来比较两个密钥实例的等价性，后者使用 operator == 有两个实例）。

这看起来容易，解释起来难。下面是一个简单的例子：

#include <iostream>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <tuple>
#include <unordered_map>

struct MyKey
{
    struct Hash
    {
        // jacked up derivation of bernstiens string hasher
        std::size_t operator()(MyKey const& key) const
        {
            std::size_t hash = 5381u;
            for (auto c : key.s1)
                hash = (hash << 5) + hash + c;
            for (auto c : key.s2)
                hash = (hash << 5) + hash + c;
            for (auto c : key.s3)
                hash = (hash << 5) + hash + c;
            return hash;
        }
    };

    std::string s1, s2, s3;

    // equivalence determination.
    bool operator ==(MyKey const& key) const
    {
        return std::tie(s1, s2, s3) == std::tie(key.s1, key.s2, key.s3);
    }
};

int main()
{
    std::unordered_map<MyKey, int, MyKey::Hash> ht;
    ht.insert(std::make_pair<MyKey>({ "one", "two", "three" }, 42));
    ht.insert(std::make_pair<MyKey>({ "four", "five", "six" }, 1999));
    ht.insert(std::make_pair<MyKey>({ "seven", "eight", "nine" }, 1999));

    auto it = ht.find(MyKey{ "one", "two", "three" });
    if (it != ht.end())
        std::cout << it->second << '\n';

    it = ht.find(MyKey{ "four", "five", "six" });
    if (it != ht.end())
        std::cout << it->second << '\n';

    it = ht.find(MyKey{ "seven", "eight", "nine" });
    if (it != ht.end())
        std::cout << it->second << '\n';

    // shoudl NOT find anything
    it = ht.find(MyKey{ "one", "three", "two" });
    if (it != ht.end())
        std::cout << it->second << '\n';
}

回答您问题中可能最重要的部分，不，这不会影响搜索时间。显然，从三个字符串生成哈希值比从一个字符串生成哈希值需要更长的时间，但是一旦获得该值，搜索机制就与任何其他字符串相同 unordered_map。如果发现冲突，等效性检查将再次启动，这是不可避免的，但不会影响整体性能配置文件的 big-O 复杂性。

Answer 4

首先，您需要能够散列多个关键字段以提供一个高质量的散列值，并且 - 在 boost hash_combine 的风格中 - 你可以通过以下方式做到这一点：

template <class T>
inline void hash_combine(std::size_t& seed, T const& v) {
    seed ^= std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

...结合 general-purpose tuple 哈希函数...

struct hash_tuple {
    auto operator()(const auto& tuple) const {
        std::size_t seed = 0;
        std::apply([&](const auto& ...element){(..., hash_combine(seed, element));}, tuple);
        return seed;
    }
};

以上内容适用于任何长度的元组，以及任何本身可散列的包含类型。

然后您可以使用 std::tuple 键字段中的 unordered_map 到价格 double，如：

using key = std::tuple<std::string, std::string, std::string>;
std::unordered_map<key, double, hash_tuple> m;
// ...then just use the map...
m[{"abc", "def", "ghi"}] = 3.14;

...或者，您可能想要 struct 结合您的钥匙和价格...

struct X {
    std::string a, b, c;
    double price_;
    auto tie_keys() const { return std::tie(a, b, c); }
    bool operator==(const X& rhs) const {
        return tie_keys() == rhs.tie_keys();
    }
    friend std::ostream& operator<<(std::ostream& os, const X& x) {
        return os << x.a << ' ' << x.b << ' ' << x.c << ' ' << x.price_;
    }
};

...并将它们存储在 unordered_set<>...

auto hash_fn = [](const X& x) { return hash_tuple{}(x.tie_keys()); };
std::unordered_set<X, decltype(hash_fn)> m2;
// ...and use it...
m2.emplace("ab", "cde", "fg", 3.14);
m2.emplace("hij", "kl", "mn", 2.71);
for (const auto& x : m2)
    std::cout << x << '\n';

你当然需要各种 headers...

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <tuple>

does having 3 keys affect the search time complexity for the map?

如果你有一个像样的散列函数就不会。

如何在 C++ STL 中实现具有三个键的映射？

How to implement a map with three keys in C++ STL?

c++

oop

stl

c++17