How to check if a template parameter is an iterator type or not? SFINAE

I am trying to implement a std::list-like doubly linked list and in a template constructor I need to restrict the type that would be used.

So after a couple of google searches, I came across the topic SFINAE which until today I had never heard of it. Even though I haven't fully understood it yet but I have the essential idea of how it works, and when it is used.

Which brings me to my question: I need to make sure that the template parameter is an iterator, something that I can't seem to figure it out on my own how to do.

I know that I will be using std::enable_if, but I don't understand how exactly I am going to use it(I saw some examples on my google searches and its syntax looked quite difficult to get a grasp on).

This is the stripped down version of my code that is meant to highlight only the part where I have the question about.
1
2
3
4
5
6
7
8
template <typename T>
class List
{
public: 
   template<typename InputIt, typename = typename td::enable_if_t<> > //this is where I am stuck
   List(InputIt first, InputIt last);

};


So, if someone could shine a light on this issue for me I would very much appreciate it.

Also, a bonus question: What's with the iterator_traits, what exactly are they and what they are for?
It can be done, but it might be simpler to just try to use the iterator as such. If the actual supplied type is not an iterator then you will get a compile error, and a properly named typename will clue the user in when reading the error message.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <typename T>
class List
{
public:
  template <typename ForwardIterator>
  List( ForwardIterator first, ForwardIterator last )
  {
    while (first != last)
      append( *first++ );
  }

  void append( const T& value )
  {
    ...
  }
}

If you try to construct a List with a non-iterator type, it will barf at you (profusely).

Hope this helps.
I think I might have solved this and it was quite simple.

I went on to the file std_list.h to check it out how this overloaded ctor is defined and found this:
1
2
3
4
template<typename _InputIterator,
	       typename = std::_RequireInputIter<_InputIterator>>
	list(_InputIterator __first, _InputIterator __last,
	     const allocator_type& __a = allocator_type())


So I went on to my code and did this:
1
2
3
4
5
6
7
8
template <typename T>
class List
{
public: 
   template<typename InputIt, typename = std::_RequireInputIter<InputIt>>
   List(InputIt first, InputIt last);

};


And now my code works fines and as I expected it to.
std::_RequireInputIter<InputIt>
Names that begin with an underscore followed by a capital letter are strictly reserved to the implementation for any use (i.e., they're potentially macro names), and so user code that uses those names has undefined behavior.

A more convincing reason to avoid this solution is that there's no template named _RequireInputIter<InputIt> in the standard.

Just write your own (or enable Concepts support):
1
2
3
template <typename Iter>
using require_input_iterator = std::enable_if_t<std::is_base_of_v<
  std::input_iterator_tag, typename std::iterator_traits<Iter>::iterator_category>>;

Last edited on
...and now your code is completely non-portable and may break unexpectedly...
Last edited on
ooh wow, OMG.

And me thinking I found a really clever cheat-sheet LOL.

Anyway, pretty useful information you guys provided me here, thanks.

@mbozzi Thanks for the code, tried it and seems to work OK.
However, I am unfamiliar with how that code works, I will search the keywords I am not familiar with (namely is_base_of_, terator_traits<>::iterator_category, input_iterator_tag).
But would appreciate it if you give me an explanation. Thanks.
Last edited on
For any iterator type Iter,
typename std::iterator_traits<Iter>::iterator_category
Is a type that indicates which operations are supported on Iter.

When that type is std::input_iterator_tag, it indicates that Iter meets the named requirement LegacyInputIterator (it is an input iterator):
https://en.cppreference.com/w/cpp/named_req/InputIterator

There are other tag types that indicate the different kinds of iterators. The tag types form a class hierarchy with each derived type corresponding to a named requirement that's stronger than the one it inherits:
https://en.cppreference.com/w/cpp/iterator/iterator_tags

is_base_of_v<Base, Derived> compares equal to true if Derived inherits from the type Base, or Derived and Base are the same types.
https://en.cppreference.com/w/cpp/types/is_base_of

Putting it all together,
1
2
std::is_base_of_v<
  std::input_iterator_tag, typename std::iterator_traits<Iter>::iterator_category>

Is true if iterator_traits says Iter is an input iterator or better.
Last edited on
That assumes that the iterator is represented by an iterator_traits...
A little mind-boggling but I am beginning to get it.

Why the keyword typename has to be here?

...typename std::iterator_traits<Iter>::iterator_category>
Last edited on
Why the keyword typename has to be here?

See: https://stackoverflow.com/a/613132/2085046

Duthomhas wrote:
That assumes that the iterator is represented by an iterator_traits...

All iterator types provide the member type iterator_traits<I>::iterator_category by definition.
https://en.cppreference.com/w/cpp/named_req/Iterator

If you really wanted to widen the definition of "Iterator", you can test whether or not the type supports the required operations directly. This is definitely more direct, although substantially more complicated.

Without concepts, C++14 users can do this "nicely" by writing a function template which attempts to instantiate a generic function object's operator(), for example:
[](auto x) -> std::void_t<decltype( expression-involving-x )> {}
For a particular type T, and testing whether or not it results in a substitution failure.

(Note that std::iterator_traits works back in C++98, before expression-SFINAE was a thing).
Last edited on
Thank you for the explanation, I really appreciate people like you who take time and put effort to explain things.

However, this is still a little mind-boggling (not your explanation), I will have to read more upon SFINAE.Any reference?

Also I have noticed that these topics are not present at any of the books talking about templates I have read (Are they part of C++ metaprogramming, will I have to read cpp metaprogramming books?). I think they are not for beginners, so as I learn best on books do you have any suggestion on c++ books for more advanced programmers.
However, this is still a little mind-boggling (not your explanation), I will have to read more upon SFINAE.Any reference?

Also I have noticed that these topics are not present at any of the books talking about templates I have read (Are they part of C++ metaprogramming, will I have to read cpp metaprogramming books?)

Yes, this is firmly a metaprogramming question.

C++'s metaprogramming facilities are changing quickly, so it's pretty important to get an up-to-date reference. For instance, SFINAE's effectively being replaced by C++20's concepts, and there's a broader trend away from "type computation" with templates and towards "value computation" with constexpr & C++20's consteval.

The problem is, there aren't very many good books about this to begin with, and even fewer are up-to-date. You might try Vandevoorde, Josuttis, and Gregor's C++ Templates: The Complete Guide (2nd Edition). This one has been updated for C++17. I've not read the second edition (sorry!), but all three authors are extremely well-qualified.

I don't know of any books about constexpr that explore the current bleeding edge.

You might also try reading some libraries. There's a tremendous amount to learn just in the standard library alone.
Last edited on
Gregor's C++ Templates: The Complete Guide (2nd Edition)


This is the best book on the subject IMO. I've just completed reading it. However, it can get very dry at times delving deep into obscure rules of template implementations.

OP, you really don't need std::enable_if. First of all, you aren't overloading your constructor, so there isn't really any use. SFINAE would automatically come into play if you have a second templated List constructor that can match the given operands, and if the substitution of the said operands into the first templated List constructor in the immediate context produces a failure, then the second one will be used. This is SFINAE. You don't even need enable_if.

In any case, since you aren't providing any overloads of the constructor, there is no need to explicitly disable one of them from participating in overload resolution by using std::enable_if, since you will receive a compilation error either way if there is a substitution failure.
Last edited on
@mbozzi oh I see. Good to know, I am not sure I want to get into metaprogramming right now so I will leave it be for now, I want to learn some other stuff about C++ first like GUI, Networking, OpenCV(maybe). Again, thanks for everything.


@TheToaster

First of all, you aren't overloading your constructor, so there isn't really any use.


I assume you are basing on the code provided in the question. That is a stripped down version that is meant to highlight only the part where I am having trouble.
As in std::list, my implementation has a few constructor overloads.
As in std::list, my implementation has a few constructor overloads.


Either way, SFINAE would apply even without the usage of std::enable_if. SFINAE means "Substitution-Failure-Is-Not-An-Error". You don't need std::enable_if to use SFINAE. If the constructor overload contains an unknown method of a class (which is evaluated in the immediate context of a function).

In your case, you are looking for an input iterator. Any operation that you use involving input iterators will automatically cause the desired substitution failure if an invalid iterator type is substituted for it since there are no other overloads that take two iterators.
Last edited on
Substitution failure only eliminates candidate functions when template argument substitution would produce ill-formed code within the function type or its template parameter list. That's the "immediate context" that's often discussed and rarely defined -- a regular source of confusion.

Consider these two declarations
1
2
3
4
5
6
7
template <typename InputIter> void f(InputIter begin, InputIter end)
{ while (*begin++ != end) /* do nothing */; }
void f(long x, long y) {}

int main() { 
  f(2, 3); // error: instantiating the unconstrained function template
}
Overload resolution chooses void f<int>(int, int) because its type and parameter list are well-formed and it is the best-viable. The program fails to compile.
Last edited on
Topic archived. No new replies allowed.