Function template and ambigous template parameter

Question

I have several std::map<some_type, some_other_type> and I'm trying to write a function template Lookup as shown below.

The function template works fine when the key is a pointer or a scalar, but if the key is std::string there are problems.

#include <iostream>
#include <map>

// Usage :
//   bool valueisinmap = Lookup(themap, thekey, thevalue);
template <typename TK, typename TV>
bool Lookup(std::map<TK, TV>& map,  TK key, TV& value)
{
  auto it = map.find(key);
  if (it != map.end())
  {
    value = it->second;
    return true;
  }
  else
  {
    return false;
  }
}

int main()
{
    std::map<std::string, std::string> m;
    m.insert(std::make_pair("2", "two"));

    std::string x;
    std::string key = "2";

    if (Lookup(m, key, x))
      std::cout << "OK\n";

    if (Lookup(m, "2", x))  // problem here
      std::cout << "OK\n";
}

I understand why Lookup(m, "2", x) doesn't compile because the type of "2" is not std::string but is there a way to write the function template so I can use Lookup(m, "2", x) as well as Lookup(m, key, x), key being a std::string?

And if yes this raises a second question:

bool Lookup(std::map<TK, TV>& map,  TK key, TV& value)

key is passed by value and if the type of key is std::string, a copy is made. Is there a way to pass key by reference (or some C++14 and plus magic) and still being able to use Lookup(m, "2", x)?

Ton van den Heuvel · Answer 1 · 2019-10-01T10:37:12.293

One way to solve this is to introduce a separate type parameter for the key type, as follows:

template <typename TKM, typename TK, typename TV>
bool Lookup(const std::map<TKM, TV>& map, const TK& key, TV& value)
{
  auto it = map.find(key);
  if (it != map.end())
  {
    value = it->second;
    return true;
  }
  else
  {
    return false;
  }
}

As long as TK is implicitly convertible to TKM, Lookup can be called with a key of type TK in conjunction with a map that has key type TKM.

songyuanyao · Answer 2 · 2019-10-01T10:42:45.910

3

You can introduce another template parameter for key as @Ton van den Heuvel answered, another way is to exclude it from template argument deduction:

template <typename TK, typename TV>
bool Lookup(std::map<TK, TV>& map, const std::type_identity_t<TK>& key, TV& value)

Then TK will be only deduced from the 1st parameter map; if you pass a const char[] to the function as key it'll be converted to std::string then passed as the argument. And you can make is pass-by-const-reference to avoid potential unnecessary copy.

LIVE

^{BTW: std::type_identity is supported from C++20; if your compiler doesn't support it, you can make your own easily.}

template<typename T> struct type_identity { typedef T type; };

edited Oct 01 '19 at 10:42

answered Oct 01 '19 at 10:30

songyuanyao

169,198
16
310
405

What will be the value of `key` in this case? Is `std::type_identity_t` not an empty struct? – Ton van den Heuvel Oct 01 '19 at 10:41
@TonvandenHeuvel `std::type_identity` has only one member type, `std::type_identity_t` is same as `TK` in fact, they all refer to the type `TK`, except that it makes the template parameter non-deducible, then `TK` will be deduced from the 1st parameter only, the ambiguity in type deduction is avoided. – songyuanyao Oct 01 '19 at 10:45
Ah yes, I see now, interesting solution. – Ton van den Heuvel Oct 01 '19 at 11:04
Could not get it compiled with C++17. – Jabberwocky Oct 01 '19 at 12:01

score 1 · Accepted Answer · answered Oct 01 '19 at 10:29

1

You need two things here. First, the key type can be deduced seaparately (typename K below). Second, you want to pass the key as const-qualified reference and setup the map with a C++14 transparent comparison function (typename Comp below) to avoid unnecessary copies (see this thread for details about transparent comparators).

template <typename TK, typename TV, typename Comp, typename K>
bool Lookup(const std::map<TK, TV, Comp>& map,  const K& key, TV& value)
{
   // Same as before...
}

std::map<std::string, std::string, std::less<>> m;

Specifying std::less<> as the std::map comparison type makes sure that overloads #3 and #4 of std::map::find are available.

Note that I have additionally const-qualified the map parameter itself, as the Lookup template doesn't modify it.

answered Oct 01 '19 at 10:29

lubgr

37,368
3
66
117

In other words do I need to declare `std::map> m;` rather than `std::map m;` each time the key is a `std::string`? – Jabberwocky Oct 01 '19 at 12:37
Unfortunately, yes. – lubgr Oct 01 '19 at 18:28
@Jabberwocky, I would not go so far, only in case you are not prepared to pay for the implicit conversion from a non-`std::string` key to `std::string` when performing lookup should you use a transparent comparator. – Ton van den Heuvel Oct 21 '19 at 20:16

Function template and ambigous template parameter

3 Answers3