c++ template structure about iterator_traits

Question

I'm studying about iterator and I found some source code on github.
I realize what this code do but cannot find how.


    template <class T>
    struct _has_iterator_category
    {
    private:
        struct _two { char _lx; char _lxx; };
        template <class U>  static _two _test(...);
        template <class U>  static char _test(typename U::iterator_category * = 0);
    public:
        static const bool value = sizeof(_test<T>(0)) == 1;
    };

I think this code check if T has iterator_category, but I cannot figure few things about how and why this works.

Why this code use two template? what class U template does?
Is _test(...) function or constructor? And what is (...) means?
2-1. If _test is function, is this code doing function overloading? then how can be overloaded with different return type?
2-2. If _test is constructor, then is char a class in c++?
What does * = operator do in (typename U::iterator_category * = 0)? Is it multiplying iterator_category or make 0 of iterator_category pointer?
what sizeof(_test<T>(0)) == 1; means? Is it return true if sizeof(_test<T>(0)) is 1?

I searched a lot of document for iterator_traits and other things, but failed to interpret this code.

You can also raise the same question on Github repo itself as an issue. Maybe someone answers and clarifies things or even better improve the code for better readability. — kiner_shah, May 31 '22 at 06:12
The second `U` is used for SFINAE. I'll suggest to read book related to template. Find one [here](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). I suggest to read *C++ Templates: The Complete Guide* since it covers C++11~17 and *C++ 20 - The Complete Guide* if you'd like to use newer standard. — Louis Go, May 31 '22 at 06:22

Swift - Friday Pie · Accepted Answer · 2022-05-31T14:47:29.123

First thing first, this code is completely interpretable on it's own, if you know C++. No documentation on external components is required. It's not depending on anything. You have asked questions which suggest some gaps in basic C++ syntax understanding.

1. Template definition _test is a template member of class template _has_iterator_category. It's a template defined within template, so even if you instantiate _has_iterator_category, you still have to instantiate _test later, it got a separate template parameter.

2. Technically, it's neither. Because a class template isn't a type and a function template, which _test is, is not a function.

Constructor's name always matched the most nested enclosing class scope, i.e. _has_iterator_category in here. _has_iterator_category doesn't have a constructor declared.

It's a template of function. There are two templates, for different arguments, with different argument type. If both templates can be instantiated through successful substitution of U with concrete type, the function is overloaded.

3. It's not operator * =, operators cannot have a whitespace in them. It's * and =. This is a nameless version of argument list which could be written otherwise:

template <class U>  static char _test(typename U::iterator_category *arg = 0);

= 0 is default value of function parameter arg. As arg is not being used in this context, its name can be skipped.

The single parameter of function's signature got type U::iterator_category *. typename is a keyword required by most but recent C++ standards for a nested type dependant on template parameter. This assumes that U must have a nested type iterator_category. Otherwise the substitution of template parameters would fail.

template <class U>  static _two _test(...);

Here function signature is "variadic". It means that function may take any number of arguments after substitution of template parameters. Just like printf.

4. sizeof(_test<T>(0)) == 1 equals to true if size of _test<T>(0) result is equal to 1.

The whole construction is a form of rule known as SFINAE - Substitution Failure Is Not An Error. Even if compiler fails to substitute one candidate, it would still try other candidates. The error would diagnosed when all options are exhausted.

In this case the expression sizeof(_test<T>(0)), which attempts to substitute U with T. It's the reason why _test is made into a nested template. The class is valid, but now we check the function.

If type-id T::iterator_category is valid, then substitution will be successful, as the resulting declaration will be valid. _test(...) can be successful too, but then we go to overload choice rules.

A variadic argument always implies type conversion, so there is no ambiguity and _test(...) will be discarded.

If T::iterator_category is not a valid type, _two _test(...) is the only instance of _test().

Assuming that sizeof(char) equals to 1, the constant value is initialized with true if return value of expression would be _test<T>(0) got same size as char. Which is only true if T::iterator_category exists.

Essentially this constructs checks, if class T contains nested type T::iterator_category in somewhat clumsy and outdated ways. But it is compatible with very early C++ standards as it doesn't use nullptr or <type_traits> header.

I am very grateful to you for giving me this detailed answer. I've learned about template, SFINAE, and variadic. but I never thought about how applied in this code. This really clears my thought. — J HoYA, May 31 '22 at 08:28
@JHoYA I wanted to write it all down anyway to not miss something. This way answer might be helpful for someone else — Swift - Friday Pie, May 31 '22 at 08:43
@JHoYA also this example uses dated approach of SFINAE, you might have been taught more modern ones. This is essentially original C++ code, may work in pre-standard compilers. — Swift - Friday Pie, May 31 '22 at 08:52

c++ template structure about iterator_traits

1 Answers1