How to indicate the type of a container template argument?

Question

Suppose we have this template

template<typename Container, typename T> 
bool    contains (const Container & theContainer, const T & theReference) {
     ...
}

How can it be stated that, obviously the elements in container should be of type T?

Can this all be abbreviated (maybe in C++11)?

Answer 1

You might restrict the container type in the template:

#include <algorithm>
#include <iostream>
#include <vector>

template< template<typename ... > class Container, typename T>
bool contains(const Container<T>& container, const T& value) {
    return std::find(container.begin(), container.end(), value) != container.end();
}

int main()
{
    std::vector<int> v = { 1, 2, 3 };
    std::cout << std::boolalpha
        << contains(v, 0) << '\n'
        << contains(v, 1) << '\n';
    // error: no matching function for call to ‘contains(std::vector<int>&, char)’
    contains(v, '0') ;
    return 0;
}

A more complete solution (addressing some comments):

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <set>
#include <vector>


// has_member
// ==========

namespace Detail {
    template <typename Test>
    struct has_member
    {
        template<typename Class>
        static typename Test::template result<Class>
        test(int);

        template<typename Class>
        static std::false_type
        test(...);
    };
}
template <typename Test, typename Class>
using has_member = decltype(Detail::has_member<Test>::template test<Class>(0));


// has_find
// ========

namespace Detail
{
    template <typename ...Args>
    struct has_find
    {
        template<
            typename Class,
            typename R = decltype(std::declval<Class>().find(std::declval<Args>()... ))>
        struct result
        :   std::true_type
        {
            typedef R type;
        };
    };
}
template <typename Class, typename ...Args>
using has_find = has_member<Detail::has_find<Args...>, Class>;


// contains
// ========

namespace Detail
{
    template<template<typename ...> class Container, typename Key, typename ... Args>
    bool contains(std::false_type, const Container<Key, Args...>& container, const Key& value) {
        bool result = std::find(container.begin(), container.end(), value) != container.end();
        std::cout << "Algorithm: " << result << '\n';;
        return result;
    }

    template<template<typename ...> class Container, typename Key, typename ... Args>
    bool contains(std::true_type, const Container<Key, Args...>& container, const Key& value) {
        bool result = container.find(value) != container.end();
        std::cout << "   Member: " << result << '\n';
        return result;
    }
}

template<template<typename ...> class Container, typename Key, typename ... Args>
bool contains(const Container<Key, Args...>& container, const Key& value) {
    return Detail::contains(has_find<Container<Key, Args...>, Key>(), container, value);
}

template<typename T, std::size_t N>
bool contains(const std::array<T, N>& array, const T& value) {
    bool result = std::find(array.begin(), array.end(), value) != array.end();
    std::cout << "    Array: " << result << '\n';;
    return result;
}

// test
// ====

int main()
{
    std::cout << std::boolalpha;

    std::array<int, 3> a = { 1, 2, 3 };
    contains(a, 0);
    contains(a, 1);

    std::vector<int> v = { 1, 2, 3 };
    contains(v, 0);
    contains(v, 1);

    std::set<int> s = { 1, 2, 3 };
    contains(s, 0);
    contains(s, 1);

    std::map<int, int> m = { { 1, 1}, { 2, 2}, { 3, 3} };
    contains(m, 0);
    contains(m, 1);

    return 0;
}

Answer 2

Using std::enable_if (http://en.cppreference.com/w/cpp/types/enable_if), but a little more complicated than with static_assert.

EDIT: According to P0W's comment, using std::enable_if allows us to use SFINAE, which is nice when you decide to have more overloads. For example if the compiler decides to use this templated function, with a Container with no value_type typedefed, it won't generate an error instantly, like static_assert would, just looks for other functions which perfectly fits the signature.

Tested on Visual Studio 12.

#include <vector>
#include <iostream>

template<typename Container, typename T>
typename std::enable_if<
    std::is_same<T, typename Container::value_type>::value, bool>::type //returns bool
    contains(const Container & theContainer, const T & theReference)
{
    return (std::find(theContainer.begin(), theContainer.end(), theReference) != theContainer.end());
};

int main()
{
    std::vector<int> vec1 { 1, 3 };
    int i = 1;
    float f = 1.0f;
    std::cout << contains(vec1, i) << "\n";
    //std::cout << contains(vec1, f); //error
    i = 2;
    std::cout << contains(vec1, i) << "\n";
};

output:

1
0

PS: Your original function does it too, except that allows derived classes too. These solutions does not.

Answer 3

While other answers using value_type are correct , the canonical solution to this frequent problem is to not pass the container in the first place : use the Standard Library semantics, and pass a pair of iterators.

By passing iterators, you don't have to worry about the container itself. Your code is also much more generic : you can act on ranges, you can use reversed iterators, you can combine your template with other standard algorithms etc.. :

template<typename Iterator, typename T> 
bool contains (Iterator begin, Iterator end, const T& value) {
     ...
}

int main(){
    std::vector<int> v { 41, 42 };
    contains(std::begin(v), std::end(v), 42);
};

If you want to check the type carried by Iterator, you can use std::iterator_traits :

static_assert(std::is_same<typename std::iterator_traits<Iterator>::value_type, T>::value, "Wrong Type");

(Note that this assertion is generally not needed : if you provide a value not comparable with T, the template will not compile in the first place)

---

The final template would look like :

template<typename Iterator, typename T> 
bool contains (Iterator begin, Iterator end, const T& value) {

    static_assert(std::is_same<typename std::iterator_traits<Iterator>::value_type, T>::value, "Wrong Type");

     while(begin != end)
       if(*begin++ == value)
         return true;
     return false;
}

---

Live demo

---

Notes:

1) This should not be a surprise, but our contains template now has almost the same signature than std::find (which returns an iterator) :

template< class InputIt, class T >
InputIt find( InputIt first, InputIt last, const T& value );

2) If modifying the signature of the original contains is too much, you can always forward the call to our new template :

template<typename Container, typename T> 
bool contains (const Container & theContainer, const T & theReference) {
     return contains(std::begin(theContainer), std::end(theContainer), theReference);
}

Answer 4

You can check the value_type of container and T using static_assert

template<typename Container, typename T> 
bool    contains (const Container & theContainer, const T & theReference) {
     static_assert(  std::is_same<typename Container::value_type, T>::value,
                    "Invalid container or type" );
     // ...
}

^{Demo Here}

Answer 5

For standard container, you may use value_type:

template<typename Container> 
bool contains (const Container & theContainer, const typename Container::value_type& theReference) {
     ...
}

Note that there is also const_reference in your case:

template<typename Container> 
bool contains (const Container & theContainer, typename Container::const_reference theReference) {
     ...
}