Cryptic error on templates

Question

I am rather stumped by the error message I am seeing for a piece of code I am working on currently. I've tried to extract the most relevant pieces of the code to make it easy on the eyes.

The error I see:

error: no matching function for call to ‘Map(Print&, std::shared_ptr< LinkedList< int> >&)’
note: template argument deduction/substitution failed: cannot convert ‘p’ (type ‘Print’) to type ‘int’

Why is the compiler trying to cast Print to int at all?

template<typename T>
class LinkedList
{
public:
  using NodeType = std::shared_ptr<LinkedList>;
  ... Other things
}

template<class Func, typename T>
typename LinkedList<T>::NodeType Map(Func func, typename  LinkedList<T>::NodeType seq)
{
  // Some stuff
}

class Print
{
 public:

 int operator()(int i)
 {
     cout << i << endl;
     return i;
 }
};

void main()
{
  Print p;
  auto one = std::make_shared< LinkedList <int>> ();
  auto result = Map<int>(p, one);  << ---- Error
}

gcc 4.8.4

Thanks for reading.

Answer 1

I'm adding a new answer after gaining a better understanding of OP's goal. My first answer addressed difficulties related to dependent template type parameters encountered when compiling some example code, so I think it is still a valid answer.

This answer demonstrates creating a custom container class and how to write a generic Map function which iterates over containers, calling a custom function object for each element, and adding each result to another container which is finally returned by the function.

The container in this example is a linked list, defined with a minimal set of features, only enough for this example to compile and run.

The linked list class supplies begin() and end() functions which return iterator objects which are used for traversing the list. Only non-constant versions are defined here, versions for returning constant iterators should also be added for when the LinkedList object is const.

The Map function here takes a functor and a container object as arguments. All argument types are deduced, so there is no need to explicitly supply template parameters. The container is passed by value to avoid problems with const-correctness in LinkedList, and also because LinkedList's (default) copy constructor doesn't do a lot of work -- it only needs to copy two shared_ptr objects, rather than perform a deep copy of all contained data.

This Map is very simple, additional, improved versions might take two iterators (a begin and end), take a const reference to the container object (to avoid useless copying), or use type traits to handle containers which need to be accessed in special ways.

As it is here, Map should work with other containers, like std::vector, because it uses the standard iterator API.

The original version of LinkedList was just maintained as a pointer to a single list node. In the code below, LinkedList is real a container object which keeps (smart) pointers to the first and last Node objects. We need to access pointers to both the head and tail nodes here, so keeping a pointer to just one node would be inadequate.

#include <iostream>
#include <memory>
#include <string>

template<typename T>
class LinkedList {
public:
    struct Node;
    using NodeType = std::shared_ptr<Node>;
    struct Node {
        NodeType   next;
        T          value;
    };

    class forward_iterator {
        NodeType cur_node;
    public:
        forward_iterator() {}
        forward_iterator(NodeType cur_node) : cur_node(cur_node) {}
        T& operator * () { return cur_node->value; }
        forward_iterator& operator ++ () { cur_node = cur_node->next; return *this; }
        bool operator == (const forward_iterator& it) const { return cur_node == it.cur_node; }
        bool operator != (const forward_iterator& it) const { return !operator == (it); }
    };

    void push_back(const T& t) {
        NodeType node = std::make_shared<Node>();
        if(tail) {
            tail->next = node;
            tail = node;
        } else {
            head = tail = node;
        }
        node->value = t;
    }

    forward_iterator begin() { return forward_iterator(head); }
    forward_iterator end()   { return forward_iterator(); }

protected:
    NodeType head, tail;
};

inline std::string upper_case(const std::string& s) {
    std::string r;
    for(auto c : s) {
        if(c >= 'a' && c <= 'z') c = c - 'a' + 'A';
        r.push_back(c);
    }
    return r;
}

template <typename Func, typename S>
inline S Map(Func func, S seq) {
    S result;
    for(const auto& elem : seq) {
        result.push_back(func(elem));
    }
    return result;
}


int main() {
    // add strings to a LinkedList of strings named "original"
    static const char* my_data[] = { "Hello", "1234", "John Cena", "xd" };
    LinkedList<std::string> original;
    for(auto cstr : my_data) { original.push_back(cstr); }

    // dump "original" to cout
    std::cout << "-- original --\n";
    for(const auto& s : original) { std::cout << s << '\n'; }
    std::cout << '\n';

    // Run the generic Map function with "original" as input
    // A lambda will be called for each element and
    // its returned value added to the result, named "mapped".
    // A functor object may be used in place of the lambda
    auto mapped = Map(
        [](const std::string& s) { return upper_case(s); },
        original);

    // dump "mapped" to cout
    std::cout << "-- mapped --\n";
    for(const auto& s : mapped) { std::cout << s << '\n'; }
    std::cout << '\n';
}

Answer 2

If I was doing this, I would define Map as an inline friend of LinkedList. This removes problems with dependent type deduction, so you can call Map without any explicit template parameters.

Keep in mind that the only way for the compiler to find a function defined like this is with Argument-Dependent Lookup -- so it only works when a LinkedList object is passed as one of the function's arguments. Also inline friends seem to freak people out.

But it goes a long way to clean up and simplify the code.

#include <iostream>
#include <memory>

template<typename T>
class LinkedList
{
public:
    using NodeType = std::shared_ptr<LinkedList>;


    template <typename Func>
    friend NodeType Map(Func func, NodeType seq) {
        return seq;
    }

};

class Print
{
public:
    int operator()(int i)
    {
        std::cout << i << std::endl;
        return i;
    }
};

int main()
{
  Print p;
  auto one = std::make_shared< LinkedList<int> >();
  auto result = Map(p, one);
}