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

Question

So, I have a class

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

so i have an array of objects of the above shown class and my objective is to write a function with input as product, region, province the function searches this in the array and returns the price.

Now to search efficiently with least time I thought of using stl map in c++ but i require to have 3 keys in my map with price as the value,so I used this.

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

and my map definition is this.

unordered_map<key,string> mp;

1. Is this even practical to have three keys in map?
2. does having 3 keys affect the search time complexity for the map?

I am still pretty new to computer science field so please forgive me for any mistake in this question, and also if i am completely wrong with the map idea a slight push in the right direction for me will be very helpful. thankyou for your time.

Answer 1

if you are using map then you can use 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

Yes you can do this with std::unordered_map, and it isn't as difficult as it may first seem. All a std::unordered_map cares about is:

1. The key type must be hashable using either a default hash algorithm or one provided to the container as a template-parameter type or a construction instance.
2. The key type must support equivalence checks (i.e. comparing two key instances for equivalence using either a custom "equals" type similar to the hasher template parameter argument, or the default std::equals, which uses operator == with two instances).

This is easier to see than to explain. Below is a trivial example:

#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';
}

To answer probably the most important part of your question, no this does NOT affect search time. Obviously it takes longer to generate a hash value from three string than from one, but once that value is acquired the search mechanics are identical to any other unordered_map. If a collision is found, the equivalence check kicks in, and again, that's unavoidable, but not going affect the big-O complexity of your overall performance profile.

Answer 3

std::map is a touch easier to get working

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();
  }
};

now key works as a key in a std::map. Here I let std tuple (via std tie) implement my < operator.

For an unordered map, you need to specialize std hash and provide == (or pass a hasher/equality function object to the template).

In C++20 you can just

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

instead of the tie stuff and get map to work.

3 part keys don't change the big-O complexity of maps, ordered or not.

Unordered map still needs a custom hash.

Answer 4

Firstly, you'll want to be able to hash multiple key fields to provide one high quality hash value, and - in the style of boost hash_combine - you can do that with:

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

...combined with a general-purpose tuple hash function...

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;
    }
};

The above will work for any length of tuple, and any contained types that are themselves hashable.

You can then either use an unordered_map from a std::tuple of your key fields to the price double, as in:

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;

...or, you might want to have a struct with your keys and price combined...

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_;
    }
};

...and store those in an 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';

You'll need various headers of course...

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

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

Not if you have a decent hash function.