A Classic Compilation Error with Dependent Types

There is a compilation error that occurs often when writing template code that uses dependent types.

If you know what’s going on, it is easy to fix it immediately. But if you don’t, you can spend a while staring a what looks like reasonable code, and wondering why the complier won’t have it.

I’ve been bitten a few times by this compilation error, and did spend some time staring at code in confusion.

Let’s explain the problem and how to fix it, in case that could save you some time if you run into the same problem with dependent types in templates.

A simple example that doesn’t compile

To check for the presence of a value in a non-sorted collection in C++, we use the STL algorithm std::find.

std::find returns an iterator pointing to that value if it is in the collection, and std::end if it doesn’t. So to check for the presence of a value, we call std::find and compare it to the end of the collection:

if (std::find(begin(myCollection), end(myCollection), 42) != end(myCollection))
{
    // myCollection contains 42
}

Often the code then needs the iterator returned by std::find afterwards, so the return value of std::find is used both for checking whether the value is in the collection, and to give access to that value if it is.

But sometimes, like in the above code, you just need to know if the value is in the collection. And in this case, the above code is pretty verbose.

It would be nicer to have a contains function that returns a bool:

if (contains(myCollection, 42))
{
    // myCollection contains 42
}

Let’s design one!

Several types of collections could benefit from that function, including std::vector, std::array and custom containers. So we will template it on the type of the collection.

To write the prototype, we also need to type of the value inside of the collection, for the second parameter (42 in the above example). STL containers have a value_type alias for that, and custom containers should have thqt alias too, because custom containers should follow the conventions of the STL.

All in all, our function is pretty simple to write:

template<typename Collection>
bool contains(Collection&& collection, typename Collection::value_type const& value)
{
    return std::find(std::begin(collection), std::end(collection), value) != std::end(collection);
}

If you’re wondering why there is a typename in the interface, check out item 42 of Effective C++ for the whole story about dependent names.

And the function takes collection by forwarding reference, because that’s how algorithms on ranges are designed.

Our function can be used that way:

auto numbers = std::vector<int>{1, 2, 3, 4, 5};

std::cout << std::boolalpha << contains(numbers, 3);

All good? Let put that into a program and compile it.

But the compiler won’t accept that. Here is its output:

main.cpp: In function 'int main()':
main.cpp:16:55: error: no matching function for call to 'contains(std::vector<int>&, int)'
     std::cout << std::boolalpha << contains(numbers, 3);
                                                       ^
main.cpp:7:6: note: candidate: 'template<class Collection> bool contains(Collection&&, const typename Collection::value_type&)'
 bool contains(Collection&& collection, typename Collection::value_type const& value)
      ^~~~~~~~
main.cpp:7:6: note:   template argument deduction/substitution failed:
main.cpp: In substitution of 'template<class Collection> bool contains(Collection&&, const typename Collection::value_type&) [with Collection = std::vector<int>&]':
main.cpp:16:55:   required from here
main.cpp:7:6: error: 'std::vector<int>&' is not a class, struct, or union type

Excuse me? “no matching function for call to ‘contains(std::vector<int>&, int)'”, you say?

The types created by forwarding references

On the second line of its output, the compiler says it doesn’t find a contains function that can accept our parameters. This is what I find confusing at first glance. Let’s look at the call site:

contains(numbers, 3)

Then look back at the prototype:

bool contains(Collection&& collection, typename Collection::value_type const& value)

They’re the same! What’s the problem then?

It is the type Collection. Our first instinct is to think that Collection is std::vector<int>, but it’s not. Collection is deduced by the compiler in the context of the forwarding reference Collection&&.

In general we don’t need to know about reference collapsing and types generated by the compiler with forward references, but in this case we do. Collection is not std::vector<int>. It is std::vector<int>&. Note the &. That’s what the last lines of the compilation output say.

This is a completely different type. std::vector<int> has a value_type but std::vector<int>&, like int& or any other reference type, doesn’t have any alias. Hence the compilation error.

Removing the reference

Starting from here, the fix to make the program compile is easy. We just need to remove the reference. To do that we can use std::remove_reference in C++11, or the more convenient std::remove_reference_t in C++14.

The C++11 version, with std::remove_reference:

template<typename Collection>
bool contains(Collection&& collection, typename std::remove_reference<Collection>::type::value_type const& value)
{
    return std::find(std::begin(collection), std::end(collection), value) != std::end(collection);
}

The C++14 version, with std::remove_reference_t:

template<typename Collection>
bool contains(Collection&& collection, typename std::remove_reference_t<Collection>::value_type const& value)
{
    return std::find(std::begin(collection), std::end(collection), value) != std::end(collection);
}

std::remove_reference_t is more convenient here because it doesn’t require to access the non-reference type with the ::type alias.

But the resulting interface is… not very pretty.

We could make an additional alias to get the value type:

template<typename Collection>
using value_type = typename std::remove_reference_t<Collection>::value_type;

And use it this way:

template<typename Collection>
bool contains(Collection&& collection, value_type<Collection> const& value)
{
    return std::find(std::begin(collection), std::end(collection), value) != std::end(collection);
}

Is it worth it? On the one hand, this is a non-standard component. But on the other hand, its meaning is pretty clear.

Have you encountered that compilation error with dependent types? Do you think the value_type wrapper is worth it?

You will also like

• How to Make SFINAE Pretty &#8211; Part 1: What SFINAE Brings to Code
• The Most Vexing Parse: How to Spot It and Fix It Quickly
• Default Parameters With Default Template Parameters Types
• Strong Templates

Don't want to miss out ? Follow:   
Share this post!