SFINAE compiler troubles

Question

The following code of mine should detect whether T has begin and end methods:

template <typename T>
struct is_container
{
    template <typename U, typename U::const_iterator (U::*)() const,
                          typename U::const_iterator (U::*)() const>
    struct sfinae {};

    template <typename U> static char test(sfinae<U, &U::begin, &U::end>*);
    template <typename U> static long test(...);

    enum { value = (1 == sizeof test<T>(0)) };
};

And here is some test code:

#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <map>

int main()
{
    std::cout << is_container<std::vector<std::string> >::value << ' ';
    std::cout << is_container<std::list<std::string> >::value << ' ';
    std::cout << is_container<std::set<std::string> >::value << ' ';
    std::cout << is_container<std::map<std::string, std::string> >::value << '\n';
}

On g++ 4.5.1, the output is 1 1 1 1. On Visual Studio 2008, however, the output is 1 1 0 0. Did I do something wrong, or is this simply a VS 2008 bug? Can anyone test on a different compiler? Thanks!

Answer 1

Why are you going to all that effort? If you want to check if U::begin() exists, why not try it?

template <typename T>
struct is_container
{
    template <typename U> static char test(U* u,
       typename U::const_iterator b = ((U*)0)->begin(),
       typename U::const_iterator e = ((U*)0)->end());
    template <typename U> static long test(...);

    enum { value = (1 == sizeof test<T>(0)) };
};

In addition to checking for the existance of U::begin() and U::end(), this also checks whether they return something that is convertible to a const_iterator. It also avoids the pitfall highlighted by Stephan T. Lavavej by using a call expression that must be supported, instead of assuming a particular signature.

[edit] Sorry, this relied on VC10's template instantiation. Better approach (puts the existance check in the argument types, which do participate in overloading):

template <typename T> struct is_container
{
    // Is.
    template <typename U>
    static char test(U* u, 
                     int (*b)[sizeof(typename U::const_iterator()==((U*)0)->begin())] = 0,
                     int (*e)[sizeof(typename U::const_iterator()==((U*)0)->end())] = 0);
    // Is not.
    template <typename U> static long test(...);

    enum { value = (1 == sizeof test<T>(0)) };
};

Answer 2

This probably should be a comment, but I don't have enough points

@MSalters

Even though your is_container works (almost) and I've used your code myself, I've discovered two problems in it.

First is that type deque<T>::iterator is detected as a container (in gcc-4.7). It seems that deque<T>::iterator has begin/end members and const_iterator type defined.

2nd problem is that this code is invalid according to GCC devs. I qoute: values of default arguments are not part of the function type and do not take part in deduction. See GCC bug 51989

I am currently using this (C++11 only) for is_container<T>:

template <typename T>
struct is_container {
    template <
        typename U,
        typename S = decltype (((U*)0)->size()),
        typename I = typename U::const_iterator
    >
    static char test(U* u);
    template <typename U> static long test(...);
    enum { value = sizeof test<T>(0) == 1 };
};

Answer 3

Stephan T. Lavavej has this to say:

Please note that it is technically forbidden to take the address of a Standard Library member function. (They can be overloaded, making &foo::bar ambiguous, and they can have additional default arguments, defeating attempts to disambiguate via static_cast.)

So I guess I'm going to use the simpler version that only checks for the nested const_iterator type.

Answer 4

So, here's how I go about debugging these things.

First, comment out the negative alternative so you get an error instead of just a mismatch. Next, try to instantiate the type you're putting in the function with one of the items that do not work.

At this step, I was able to instantiate your sfinae object but it still wasn't working. "This lets me know it IS a VS bug, so the question then is how to fix it." -- OBS

VS seems to have troubles with SFINAE when done the way you are. Of course it does! It works better when you wrap up your sfinae object. I did that like so:

template <typename U, typename it_t = typename U::const_iterator >
struct sfinae 
{
  // typedef typename U::const_iterator it_t; - fails to compile with non-cont types.  Not sfinae
  template < typename U, typename IT, IT (U::*)() const, IT (U::*)() const >
  struct type_ {};

  typedef type_<U,it_t,&U::begin,&U::end> type;
};

Still wasn't working, but at least I got a useful error message:

error C2440: 'specialization' : cannot convert from 'overloaded-function' to 'std::_Tree_const_iterator<_Mytree> (__thiscall std::set<_Kty>::* )(void) const'

This lets me know that &U::end is not sufficient for VS (ANY compiler) to be able to tell which end() I want. A static_cast fixes that:

  typedef type_<U,it_t,static_cast<it_t (U::*)() const>(&U::begin),static_cast<it_t (U::*)() const>(&U::end)> type;

Put it all back together and run your test program on it...success with VS2010. You might find that a static_cast is actually all you need, but I left that to you to find out.

I suppose the real question now is, which compiler is right? My bet is on the one that was consistent: g++. Point to the wise: NEVER assume what I did back then.

Edit: Jeesh... You are wrong!

Corrected version:

template <typename T>
struct is_container
{
    template <typename U, typename it_t = typename U::const_iterator > 
    struct sfinae 
    {
      //typedef typename U::const_iterator it_t;
      template < typename U, typename IT, IT (U::*)() const, IT (U::*)() const >
      struct type_ {};

      typedef type_<U,it_t,static_cast<it_t (U::*)() const>(&U::begin),static_cast<it_t (U::*)() const>(&U::end)> type;
    };

    template <typename U> static char test(typename sfinae<U>::type*);
    template <typename U> static long test(...);

    enum { value = (1 == sizeof test<T>(0)) };
};



#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <map>

int main()
{
    std::cout << is_container<std::vector<std::string> >::value << ' ';
    std::cout << is_container<std::list<std::string> >::value << ' ';
    std::cout << is_container<std::set<std::string> >::value << ' ';
    std::cout << is_container<std::map<std::string, std::string> >::value << ' ';
    std::cout << is_container<bool>::value << '\n';
}

-- The debugging above is sensible, but the assumption about the compiler was wrong headed. G++ should have failed for the reason I emphasized above.

Answer 5

With C++11, there are now better ways to detect this. Instead of relying on the signature of functions, we simply call them in an expression SFINAE context:

#include <type_traits> // declval

template<class T>
class is_container{
  typedef char (&two)[2];

  template<class U> // non-const
  static auto test(typename U::iterator*, int)
      -> decltype(std::declval<U>().begin(), char());

  template<class U> // const
  static auto test(typename U::const_iterator*, long)
      -> decltype(std::declval<U const>().begin(), char());

  template<class>
  static two  test(...);

public:
  static bool const value = sizeof(test<T>(0, 0)) == 1;
};

Live example on Ideone. The int and long parameters are only to disambiguate overload resolution when the container offers both (or if iterator is typedef const_iterator iterator, like std::set is allowed to) - literal 0 is of type int and forces the first overload to be chosen.