Deduce template return type in C++

Question

Currently I try to write a function retrieveKeys() which gives me the keys of a std::map and stores it in some std::container. The function shall be generic in two ways:

• Accept std::map and std::unordered_map as parameter type.
• Return the keys in a user defined container, e. g. std::vector or std::deque (the container has to supports a push_back() method).

Currently the use of this function works as follows:

std::unordered_map<int, int> testMap;
std::map<int, int> testMap2;

std::vector<int> keys1 = retrieveKeys<std::vector>(testMap);    
std::deque<int> keys2 = retrieveKeys<std::deque>(testMap);
std::vector<int> keys3 = retrieveKeys<std::vector>(testMap2);
std::deque<int> keys4 = retrieveKeys<std::deque>(testMap2);

With the following function:

template<template<typename...> typename KeyContainer, typename... KeyContainer_Rest,
         template<typename...> typename MapContainer, typename K, typename V, typename... MapContainer_Rest>
inline KeyContainer<K, KeyContainer_Rest...> retrieveKeys(const MapContainer<K, V, MapContainer_Rest...>& map)
{
    KeyContainer<K, KeyContainer_Rest...> keys;

    for (const auto& m : map)
    {
        keys.push_back(m.first);
    }

    return keys;
}

It would be nice if I would not have to write the return type explicitly. But when I try something like

std::vector<int> keys1_ = retrieveKeys(testMap);
/*
error: no matching function for call to 'retrieveKeys'
std::vector<int> keys1_ = retrieveKeys(testMap);
                          ^~~~~~~~~~~~
*/

I get the mentioned error when compiling with clang 3.6 (C++17).

So my question is: Is it possible to rewrite the function so that the return type can be reduced by the compiler?

Here again the complete code for easy copying:

#include <deque>
#include <vector>
#include <unordered_map>
#include <map>

template<template<typename...> typename KeyContainer, typename... KeyContainer_Rest,
         template<typename...> typename MapContainer, typename K, typename V, typename... MapContainer_Rest>
inline KeyContainer<K, KeyContainer_Rest...> retrieveKeys(const MapContainer<K, V, MapContainer_Rest...>& map)
{
    KeyContainer<K, KeyContainer_Rest...> keys;

    for (const auto& m : map)
    {
        keys.push_back(m.first);
    }

    return keys;
}

int main() 
{
    std::unordered_map<int, int> testMap;
    std::map<int, int> testMap2;

    std::vector<int> keys1 = retrieveKeys<std::vector>(testMap);    
    std::deque<int> keys2 = retrieveKeys<std::deque>(testMap);
    std::vector<int> keys3 = retrieveKeys<std::vector>(testMap2);
    std::deque<int> keys4 = retrieveKeys<std::deque>(testMap2);

    //std::vector<int> keys1_ = retrieveKeys(testMap);
    /*
    error: no matching function for call to 'retrieveKeys'
    std::vector<int> keys1_ = retrieveKeys(testMap);
                              ^~~~~~~~~~~~
    */
}

Answer 1

template <typename K, typename M>
struct ReturnTypeDeducer
{
    const M& map;

    ReturnTypeDeducer(const M& m) : map(m) {}

    template <template <typename...> typename KeyContainer, typename... KeyContainer_Rest>
    operator KeyContainer<K, KeyContainer_Rest...>() &&
    {
        KeyContainer<K, KeyContainer_Rest...> keys;
        for (const auto& m : map)
        {
            keys.push_back(m.first);
        }
        return keys;
    }
};

template <template <typename...> typename MapContainer, typename K, typename V, typename... MapContainer_Rest>
inline ReturnTypeDeducer<K, MapContainer<K, V, MapContainer_Rest...>> retrieveKeys(const MapContainer<K, V, MapContainer_Rest...>& map)
{
    return map;
}

int main() 
{
    std::unordered_map<int, int> testMap;
    std::map<int, int> testMap2;

    std::vector<int> keys1 = retrieveKeys(testMap);    
    std::deque<int> keys2 = retrieveKeys(testMap);
    std::vector<int> keys3 = retrieveKeys(testMap2);
    std::deque<int> keys4 = retrieveKeys(testMap2);
}

DEMO

Answer 2

An example of how you can use container::key_type

template <class CONTAINER>
std::vector <typename CONTAINER::key_type>
retrieveKeys(CONTAINER container)
{
    std::vector <typename CONTAINER::key_type> keys;
    for (auto itr : container)
    {
        keys.push_back(itr.first);
    }
    return keys;
}


int _tmain(int argc, _TCHAR* argv[])
{
    typedef std::map <int, int> MYMAP;
    MYMAP values;
    values.insert(std::make_pair(1, 1));
    values.insert(std::make_pair(2, 2));
    values.insert(std::make_pair(3, 3));

    typedef std::vector <typename MYMAP::key_type> KEYVECTOR;
    KEYVECTOR keys = retrieveKeys<MYMAP>(values);
    for (auto itr : keys)
        std::cout << itr std::endl;
}

Answer 3

No, there is no return type deduction at the call site because the compiler would lack the necessary context. Compare with e.g. std::make_unique:

auto derived_ptr = std::make_unique<Derived>(args); // have to specify return type

In general, template argument-deduction works on, well, the supplied template arguments. Supplying an out-parameter will deduce everything

template<class InputParam, class OutputParam>
void copy(InputParam const& src, OutParam& dst) { /* bla */ }

// call as:
InputParam src = /* fill */;
OutputParam dst; // empty
copy(src, dst)   // template arguments deduced from supplied src, dst

In contrast, without it, you have to explicitly supply the template argument:

template<class InputParam, class OutputParam>
OutputParam copy(InputParam const& src) { OutputParam x; /* bla */ return x; }

// call as: 
InputParam src = /* fill */;
auto dst = copy<OutputParam>(src); // InputParam deduced from src, supply OutputParam template argument

In contrast, at the point of definition, C++14 does have return type deduction, so you could write

template<template<typename...> typename KeyContainer, typename... KeyContainer_Rest,
         template<typename...> typename MapContainer, typename K, typename V, typename... MapContainer_Rest>
auto // <-- here
retrieveKeys(const MapContainer<K, V, MapContainer_Rest...>& map)
{
    KeyContainer<K, KeyContainer_Rest...> keys;

    for (const auto& m : map)
    {
        keys.push_back(m.first);
    }

    return keys; // compiler will deduce return-type of retrieveKeys from this
}

Answer 4

No. There's no way for the compiler to tell what the return type should be because it has no information it can use to determine that (you can call retrieveKeys() outside of the context of immediately assigning it to a variable of the type you want).

However, you can reduce the code duplication by using auto:

auto keys1 = retrieveKeys<std::vector>(testMap);    
auto keys2 = retrieveKeys<std::deque>(testMap);
auto keys3 = retrieveKeys<std::vector>(testMap2);
auto keys4 = retrieveKeys<std::deque>(testMap2);