Implementing SFINAE

[hbcpp]

I am trying to implement std::list and I am at the beginning and stuck on a constructor that take two iterators.

In that constructor is where I shall implement SFINAE, a topic very new to me which I understand what it is for but I don't know how to implement it correctly on my own as I've found many examples on several posts and I just don't know which one is the right one as I tried them in my code and tweak with them quite much but nothing worked and I haven't yet found a clear guide on SFINAE implementation.

Edit: I changed the code in the constructor that was wrong

Here is the code:

#include <iostream>


using namespace std;

template <typename T>
class List
{
    struct Node
    {
        T data;
        Node* prev = nullptr;
        Node*next = nullptr;

        Node() = default;
        Node(T d) : data(d), prev(nullptr), next(nullptr) {}
    };

    Node* head, *tail;
    std::size_t l_size;

    //SFINAE -> This worked for the implementation of std::vector but doesn't seem to work here
    template<typename InputIterator>
    using required_input_iterator = std::enable_if<std::is_base_of_v<std::input_iterator_tag,
          typename std::iterator_traits<InputIterator>::iterator_category >>;

public:
    using reference = T&;
    using const_reference = const T&;
    using size_type = std::size_t;

    class const_iterator
    {
        Node* node = nullptr;

        friend class List;

        const_iterator (Node* p) : node(p) {}

    public:
        const_iterator ()  = default;
        const_iterator(const const_iterator& other) : node(other.node) {}

        reference operator*()
        {
            return node->data;
        }

        T* operator->()
        {
            return node->data;
        }

        // prefix operators
        const_iterator& operator++()
        {
            node = node->next;
            return *this;
        }

        const_iterator& operator--()
        {
            node = node->prev;
            return *this;
        }

        // postfix operators
        const_iterator operator++(int)
        {
            Node* temp = *this;
            node = node->next;
            return temp;
        }

        const_iterator operator--(int)
        {
            Node* temp = *this;
            node = node->prev;
            return temp;
        }

        friend bool operator== (const const_iterator& lhs, const const_iterator& rhs) noexcept
        {
            return lhs.node == rhs.node;
        }

        friend bool operator!= (const const_iterator& lhs, const const_iterator& rhs) noexcept
        {
            return lhs.node != rhs.node;
        }
    };

    class iterator
    {
        Node * node = nullptr;

        friend class List;

        iterator(Node* p) : node(p) {}

    public:
        iterator ()  = default;

        reference operator*()
        {
            return node->data;
        }

        reference operator->()
        {
            return node->data;
        }

        // prefix operators
        iterator& operator++()
        {
            node = node->next;
            return *this;
        }

        iterator& operator--()
        {
            node = node->prev;
            return *this;
        }

        // postfix operators
        iterator operator++(int)
        {
            Node* temp = *this;
            node = node->next;
            return temp;
        }

        iterator operator--(int)
        {
            Node* temp = *this;
            node = node->prev;
            return temp;
        }

        friend bool operator== (const iterator& lhs, const iterator& rhs) noexcept
        {
            return lhs.node == rhs.node;
        }

        friend bool operator!= (const iterator& lhs, const iterator& rhs) noexcept
        {
            return lhs.node != rhs.node;
        }

    };

    List();
    explicit List(size_type n);
    ~List() {};

    template<typename InputIterator, typename = required_input_iterator<InputIterator> >
    List(InputIterator first, InputIterator last)
    {


    }

    // iterators
    iterator begin() noexcept
    {
        return iterator(head->next);
    }

    iterator end() noexcept
    {
        return iterator(tail);
    }


};

template<typename T>
List<T>::List() : head(nullptr), tail(nullptr), l_size(0) { }

int main()
{

    List<int> lis;

    List<int> lis1(lis.begin(), lis.end());

}

The error it throws:
error: no matching function for call to 'List<int>::List(List<int>::iterator, List<int>::iterator)'|


Any help!?

Thanks!

[malibor]

This will work:

1. define trait like so:

template<typename InputIterator>
using required_input_iterator = std::enable_if_t<std::is_base_of_v<std::input_iterator_tag, InputIterator>>;

2. Inherit from input iterator
class iterator : public input_iterator_tag

3. declare constructor that takes iterators

template<typename InputIterator, typename = required_input_iterator<InputIterator> >
List(InputIterator first, InputIterator last);

4. define constructor

template<typename T>
template<typename InputIterator, typename SFINAE>
List<T>::List(InputIterator first, InputIterator last)
{
      // TODO: implementation missing
}

[hbcpp]

It works, thanks!

Could you explain how this works. Also I removed the : public std::input_iterator_tag and still "works".

template<typename InputIterator, typename SFINAE> -> Is SFINAE some keyword, what does it do?

[TheToaster]

OP,

typename = required_input_iterator<InputIterator>

This is completely unnecessary. You only have one constructor that takes two iterators. It will fail to compile either way if the required iterator is not an InputIterator. You don't need a type trait here.

Also I removed the : public std::input_iterator_tag and still "works"

It will "work" as long as you don't call the constructor that takes the input iterators. When you call it with your List iterator (that doesn't derive from std::input_iterator_tag) it will not compile, but it will work on, say, a std::vector::iterator.

Is SFINAE some keyword, what does it do?

No. As I mentioned in your previous post, SFINAE means substitution failure is not an error. If the substitution of a type in a template in the immediate context (type or template arguments) produces a failure, the next best template is chosen. If there is none, then a compiler error is given. That's it.

In your case, you only have one constructor that takes two input iterators. This will cause a compiler error if the iterator substituted does not support input operations, SFINAE or not. Since you have no other overloads that accept iterators, this is unnecessary.

A general recommendation is to not make things more complicated just because you can, especially when they do absolutely nothing. There is no need for this here. Just name the iterator InputIterator and the compiler error received will be self-explanatory.

[TheToaster]

Furthermore, your code as it is right now will cause a segmentation fault because you are calling begin() on an empty List, which you have defined to treat the begin() iterator as if it always contains an element. Therefore, even when the head pointer has been initialized to nullptr, you attempt to dereference it and access its next member. In order to fix this, you need to treat the case when begin() is called on an empty list and make it return the same as end(), in which case you can then adjust your code accordingly.

[malibor]

template<typename InputIterator, typename SFINAE> -> Is SFINAE some keyword, what does it do?

See declaration of constructor, from point 3 in my post, it takes TWO template parameters one of which is SFINAE "enablement"

Therefore constructor definition must also have 2 template parameters, regardless if you need and use only one, this "SFINAE" typename could have been avoided by just writing following:

template<typename InputIterator, typename> /* second type name not needed */

but it's not bad practice to be explicit, and it this case it's just a dummy parameter name to denote that second typename is needed because of SFINAE parameter in declaration.

There are cases where you can't avoid typing dummy template parameter name, and this is when your entry class is "SFINAE" and you want to define function outside that class, for example:

template <typename BASE_TYPE,
	typename = std::enable_if_t<std::is_base_of_v<BASE_TYPE, DERIVED_TYPE>>>
class MyObject
{
public:
	MyObject(); // constructor declaration
};

Here if you omit dummy typename called "SFINAE" in this case it won't compile:

// Constructor definition outside class, dummy typename is must!
template<typename BASE_TYPE, typename SFINAE>
MyObject<BASE_TYPE, SFINAE>::MyObject()
{
}

Of course this is not needed if definition is inside class.

EDIT:
if you want to compile this sample, just replace DERIVED_TYPE with some actual class name such as std::vector<int>
And then try to omit SFINAE type name and see what happens.

[hbcpp]

@TheToaster Thanks for the explanation.

There is no need for this here.

-> By 'this' you mean the SFINAE?

Just name the iterator InputIterator...

-> What do you mean?

But I have to say, SFINAE is seeming very tricky to implement and non-intuitive (at least for me).
I guess I am better off for now if I just write this costructor like this:
List(iterator first, iterator last)
and maybe wait for the C++20 concepts as it is said to make this better.

[TheToaster]

By 'this' you mean the SFINAE?

I mean there is no need to make a type trait to check if it is an input iterator. It is going to fail to compile if it is not an input iterator anyways. So yes, SFINAE is not needed to differentiate between template constructors since only one constructor takes two iterators.

What do you mean?

I mean if you do this:

List(InputIterator first, InputIterator last)

Then if client code causes a compilation failure because they passed a forward iterator instead of an input iterator, the compiler error will display the definition of the List constructor and you will be able to see that the template type parameter is named "InputIterator" and thus realize that the function is expecting an input iterator.

and maybe wait for the C++20 concepts as it is said to make this better.

I mean there's nothing stopping you from learning concepts now. C++20 is out and GCC 10 supports concepts afaik.

[hbcpp]

@malibor, of I understand it now, seemed odd at first but now it makes sense.

I made some tests with the SFINAE implementation you gave me and it fails.

When I instantiate the List like this:

List<int> lis(5, 6);

it calls the constructor that I am trying to implement the SFINAE instead of this ctor:

List(size_type n, const_reference v);

[malibor]

List<int> lis(5, 6);
I don't understand what are you trying to do?

passing integers to constructor that expects input iterators?

If you want to pass integers define additional constructor that takes numbers.

[TheToaster]

List(size_type n, const_reference v);

Ah, now THIS is an example of where you would want to use SFINAE. You didn't put this constructor in your original post, so I didn't know you had another constructor that could conflict.

In this case, you can use some kind of basic SFINAE condition that disables the first constructor if it is an iterator. Something like this could work:

    List(size_type n, const_reference v = T{}) {std::cout << "function 2" << std::endl;}

    template<typename InputIterator, typename = decltype(*std::declval<InputIterator>())>
    List(InputIterator first, InputIterator last)
    {
        std::cout << "function 1" << std::endl;

    }
//...

#include <vector>
int main()
{

    vector<int> lis{1,2,3,4,5};

    List<int> lis1(lis.begin(), lis.end());
    List<int> lis2(2,3);

}

This basically checks if the InputIterator type can be dereferenced using operator*. If it can't, then it is a substitution failure and the other constructor is selected. Note, this condition will apply for ALL iterators, not just input ones. However, even if another Iterator type is provided, it will still fail to compile if you use an iterator that doesn't support input operations when the body of the constructor is substituted (which is after the immediate context of the template arguments and the return type).

There's probably a better way to write this check, but oh well :) It works on raw pointer types as iterators as well as iterator classes, so this is probably a good solution if you want to construct a list from, say, a raw C-style array.

@malibor:

I don't understand what are you trying to do? passing integers to constructor that expects input iterators?

He explained that he was trying to implement the following constructor:
List(size_type n, const_reference v);

But the iterator constructor was always chosen instead of this one. He didn't have it in his original post, so I assumed he didn't have any other constructors that could conflict with the template one.

[hbcpp]

Sorry I left a lot of methods out of the post to make it easy to focus on the question but I really thought I had put that constructor in this code though.
I mistakenly assumed that by leaving things out I was making the question better when I wasn't. Sorry!!


I will edit the post and provide all the class' methods.

[hbcpp]

The post will exceed its length if I add the whole class so I will add here, hope it is ok:

template <typename T>
class List
{
    struct Node
    {
        T data;
        Node* prev = nullptr;
        Node*next = nullptr;

        Node() = default;
        Node(T d) : data(d), prev(nullptr), next(nullptr) {}
    };

    Node* head = nullptr;
    Node *tail = nullptr;
    std::size_t l_size = 0;

    //SFINAE


public:
    using reference = T&;
    using const_reference = const T&;
    using size_type = std::size_t;

    class const_iterator
    {
        Node* node = nullptr;

        friend class List;

        const_iterator (Node* p) : node(p) {}

    public:
        const_iterator ()  = default;
        const_iterator(const const_iterator& other) : node(other.node) {}

        reference operator*()
        {
            return node->data;
        }

        T* operator->()
        {
            return node->data;
        }

        // prefix operators
        const_iterator& operator++()
        {
            node = node->next;
            return *this;
        }

        const_iterator& operator--()
        {
            node = node->prev;
            return *this;
        }

        // postfix operators
        const_iterator operator++(int)
        {
            Node* temp = *this;
            node = node->next;
            return temp;
        }

        const_iterator operator--(int)
        {
            Node* temp = *this;
            node = node->prev;
            return temp;
        }

        friend bool operator== (const const_iterator& lhs, const const_iterator& rhs) noexcept
        {
            return lhs.node == rhs.node;
        }

        friend bool operator!= (const const_iterator& lhs, const const_iterator& rhs) noexcept
        {
            return lhs.node != rhs.node;
        }
    };

    class iterator : public std::input_iterator_tag
    {
        Node * node = nullptr;

        friend class List;

        iterator(Node* p) : node(p) {}

    public:
        iterator ()  = default;

        reference operator*()
        {
            return node->data;
        }

        reference operator->()
        {
            return node->data;
        }

        // prefix operators
        iterator& operator++()
        {
            node = node->next;
            return *this;
        }

        iterator& operator--()
        {
            node = node->prev;
            return *this;
        }

        // postfix operators
        iterator operator++(int)
        {
            Node* temp = *this;
            node = node->next;
            return temp;
        }

        iterator operator--(int)
        {
            Node* temp = *this;
            node = node->prev;
            return temp;
        }

        friend bool operator== (const iterator& lhs, const iterator& rhs) noexcept
        {
            return lhs.node == rhs.node;
        }

        friend bool operator!= (const iterator& lhs, const iterator& rhs) noexcept
        {
            return lhs.node != rhs.node;
        }

    };

    template<typename InputIterator>
    using required_input_iterator = std::enable_if<std::is_same_v<List<T>::iterator, InputIterator >>;

    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

    List() = default;
    explicit List(size_type n);
    List(size_type n, const_reference v);
    List(const std::initializer_list<T>& i_list);
    template<typename InputIterator, typename = required_input_iterator<InputIterator>>
    List(InputIteratorfirst, InputIteratorlast);
    List(const List& src);
    List& operator=(const List& src);
    List(const List&& src);
    //~List();


    void assign(size_type n, const_reference v);
    void assign(const std::initializer_list<T>& i_list);
    template<typename InputIterator> void assign(InputIterator first, InputIterator last);

    // element acces
    reference front();
    const_reference front() const;
    reference back();
    const_reference back() const;

    // iterators
    iterator begin() noexcept
    {
        return iterator(head);
    }
    const_iterator begin() const noexcept
    {
        return iterator(head);
    }
    iterator end() noexcept
    {
        return iterator(tail);
    }
    const_iterator end() const noexcept
    {
        return iterator(tail);
    }
    const_iterator cbegin() const noexcept;
    const_iterator  cend() const;
    reverse_iterator rbegin() noexcept;
    const_reverse_iterator crbegin() const noexcept;
    reverse_iterator rend() noexcept;
    const_reverse_iterator crend() const noexcept;

    // capacity
    size_type size() const noexcept;
    bool empty() const noexcept;

    // modifiers
    void clear() noexcept;
    iterator insert(const_iterator pos, const_reference v);
    iterator insert(const_iterator pos, const T&& v);
    iterator insert(const_iterator pos, size_type n, const_reference v);
    template<typename InputIterator> iterator insert(InputIterator first, InputIterator last);
    iterator insert(const_iterator pos, std::initializer_list<T> i_list);
    template<typename... Args> iterator emplace(const_iterator pos, Args&&... args );
    iterator erase(const_iterator pos);
    iterator erase(const_iterator first, const_iterator last);
    void push_back(const_reference v);
    void push_back(T&& v);
    template<typename... Args> reference emplace_back(Args&&...args);
    void pop_back();
    void push_front(const_reference v);
    void push_front(T&& v);
    template<typename... Args> reference emplace_front(Args&&...args);
    void pop_front();
    void resize(size_type new_size);
    void resize(size_type new_size, const_reference v);
    void swap(List<T> other) noexcept;
};

[TheToaster]

Did you try the code I gave you with the SFINAE test?

    List(size_type n, const_reference v = T{}) {std::cout << "function 2" << std::endl;}

    template<typename InputIterator, typename = decltype(*std::declval<InputIterator>())>
    List(InputIterator first, InputIterator last)
    {
        std::cout << "function 1" << std::endl;

    }

[hbcpp]

@TheToaster

I mean there's nothing stopping you from learning concepts now. C++20 is out and GCC 10 supports concepts afaik.

Yeah you are right. When I said 'wait' I was referring to when I have C++20 working compiler ready to use though.
However, I have been trying to build GCC 10 since yesterday. Haven't succeeded yet, some errors when running make. I will focus on it in the next few days and learn more about concepts as well.

I will try the code you gave me. Thanks.

[mbozzi]

The right way to do this is to query std::iterator_traits<T>::iterator_category as discussed in OP's prior thread
http://www.cplusplus.com/forum/beginner/270488/#msg1165620

That type alias has been misquoted several times in this thread, with different issues each time.

[TheToaster]

The right way to do this is to query std::iterator_traits<T>::iterator_category

That would work. But of course, that would prevent the following from working I believe:

int arr[] = {1,2,3,4,5};
List<int> list(arr, arr+5);

You could do it like this:

template<typename InputIterator, typename = decltype(*std::declval<InputIterator>())>
    List(InputIterator first, InputIterator last);

And this would work for all iterators and pointers since they support operator*(). And if the user accidentally passes an iterator that is NOT an input iterator, it would fail to compile anyways in the non-immediate context of the function body. AFAIK, there are no other constructors that would conflict in OP's implementation that would require such a strict type trait.

[mbozzi]

But of course, that would prevent the following from working I believe

It works, as discussed in the prior thread
http://www.cplusplus.com/forum/beginner/270488/#msg1165699

It is poor practice to implement weak type constraints. Overly-weak type constraints restrict implementation flexibility and invite avoidable errors. Lengthy discussion here:
http://www.stroustrup.com/good_concepts.pdf

[TheToaster]

It works, as discussed in the prior thread

Well, it doesn't seem to be working here:
https://onlinegdb.com/HJAXlDki8

And a raw pointer is not a class type, so you wouldn't be able to query it with std::iterator_traits, right?

Never mind. I guess you can. But it doesn't seem to work in the above code

[mbozzi]

You didn't use the right definition of required_input_iterator.

[Edit. Sorry, I shouldn't snap at you.]