Can a function template deduce a container's value type?

Question

Suppose I define the following function template that removes an item from the given set if the specified function returns true for that item.

template<typename TYPE>
int removeItems(
    QSet<TYPE>& set,
    const std::function<bool (const TYPE&)>& shouldRemove)
{
    int numRemoved = 0;

    auto iter = set.begin();
    while (iter != set.end())
    {
        if (shouldRemove(*iter))
        {
            iter = set.erase(iter);
            ++numRemoved;
        }
        else
        {
            ++iter;
        }
    }

    return numRemoved;
}

I can use this function template like this:

QSet<QString> stuff = {"A", "a", "B", "b", "C", "c"};
removeItems<QString>(stuff, [](const QString& thing) {
    return thing.toLower() == "a";
});
qDebug() << stuff; // QSet("B", "b", "C", "c")

But can the function template be defined in such a way that the template argument can be omitted from the function call?

QSet<QString> stuff = {"A", "a", "B", "b", "C", "c"};
removeItems(stuff, [](const QString& thing) {
    return thing.toLower() == "a";
});
qDebug() << stuff; // QSet("B", "b", "C", "c")

I don't have a real object, but you could use a QObject base instead to accept and then try to cast it inside using a dynamic cast. — Wes Hardaker, May 26 '21 at 19:30
I think this could be done with a template template, e.g. `template — 0x5453, May 26 '21 at 19:33
This shows how you can set templates for stl containers: [c++ template class; function with arbitrary container type, how to define it?](https://stackoverflow.com/questions/7728478/c-template-class-function-with-arbitrary-container-type-how-to-define-it), with many of them could be easily applied for your case as well. — Ranoiaetep, May 26 '21 at 19:55
The optimal solution imo would be to ditch the `std::function` from the signature entirely. To incure the cost of type erasure (not to mention the effect on TAD) while *still* using a function template is in my book a pessimization. Just add a template parameter `Pred` and declare the function parameter as `Pred shouldRemove`. Everything will just work (TM) from then on (with better inlining). — StoryTeller - Unslander Monica, May 26 '21 at 20:10

score 3 · Answer 1 · 2021-05-26T20:01:50.657

If you can tolerate slightly more aggressive duck-typing, templating on the container itself and extracting the value_type within the template gets you there.

template<typename ContainerT>
int removeItems(
    ContainerT& set,
    const std::function<bool (const typename ContainerT::value_type&)>& shouldRemove)
{

At that point, I would also duck-type the callback as well to get rid of the extra indirection from std::function, but there is something to be said for cleaner error messages, so it's a matter of preference.

template<typename ContainerT, typename CheckT>
int removeItems(
    ContainerT& set,
    const CheckT& shouldRemove)
{

Edit For reference, it's worth noting that if it wasn't for that std::function<> parameter, the compiler would have been able to infer the type correctly just fine as is. So the following works as well:

template<typename TYPE, typename CheckT>
int removeItems(
    QSet<TYPE>& set,
    const CheckT& shouldRemove)
{

The std::function<> messes things up because the lambda needs to be implicitly converted into a std::function<>, and implicitly conversions don't play well with template inference.

The value_type version works because the type of the std::function<> is completely determined by the first argument.
The versions with duck-typed callbacks work because the lambda is used as is without having to go through implicit conversion.

273K · Answer 2 · 2021-05-26T20:24:00.150

2

You may use

template<typename SET>
int removeItems(
    SET& set,
    const std::function<bool (const typename SET::key_type&)>& shouldRemove);

This will deduce the type:

removeItems(stuff, [](const QString& thing) {
    return thing.toLower() == "a";
});

edited May 26 '21 at 20:24

answered May 26 '21 at 19:35

273K

29,503
10
41
64

score 1 · Answer 3 · answered May 26 '21 at 20:02

Yes, you can definitely do so. Just like this:

 template<typename T>
 struct do_not_deduce
 {
    using type = T;
 };

 template<typename T>
 using do_not_deduce_t = typename do_not_deduce<T>::type;

 template<typename TYPE>
 int removeItems(
 QSet<TYPE>& set,
 const std::function<bool (const do_not_deduce_t<TYPE>&)>& shouldRemove)
 ....

The issue is that removeItems attempts to deduce types from both inputs. Thus passing a lambda as second parameter causes issues with the deduction as it needs to be converted to the correct type of std::function which is rather complicated to do during template argument deduction.

In the solution I provided I simply removed the argument deduction from the second parameters thus the deduction is done according to the first parameter only - and subsequently is succeeds.

Notes: you shouldn't use std::function for fast checks as it is rather slow. You'd better accept a general template argument instead and just verify via SFINAE that it is invokable and has correct signature.

score 0 · Accepted Answer · answered May 27 '21 at 13:49

I ended up going with something based on the answer provided by Frank and the comment posted by StoryTeller - Unslander Monica. The former provided a solution that handled more than just QSet, while the latter provided a solution that was simpler overall.

template<typename ContainerT, typename Pred>
int removeItems(ContainerT& container, Pred shouldRemove)
{
    int numRemoved = 0;

    auto iter = container.begin();
    while (iter != container.end())
    {
        if (shouldRemove(*iter))
        {
            iter = container.erase(iter);
            ++numRemoved;
        }
        else
        {
            ++iter;
        }
    }

    return numRemoved;
}

Can a function template deduce a container's value type?

4 Answers4