Implementing SFINAE

Pages: 12
You didn't bother to use the right definition of required_input_iterator.


Sorry, thought I copy pasted it from your comment, but it wasn't the right one.
Last edited on
@mbozzi
The right way to do this is to query std::iterator_traits<T>::iterator_category as discussed in OP's prior thread

But it failed to work properly because it conflicted with this ctor:

List(size_type n, const_reference v);

Maybe it is missing something. This is still tricky for me because I can't tell exactly why one method works and the other doesn't.
For now I will be using TheToaster's implementation as it works. At least until I have c++20 concepts ready to use..
Last edited on
@hbcpp
I'm sorry for misunderstanding about what you want to do.

here is example how to make it work with comments what it does and how it works:

Step1: Insert bellow code into your iterator class, this describes your iterator traits:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class iterator
{
	// Define your iterator traits however you like here
	// These members will be used by std::iterator_traits for SFINAE
public:
	// what values that my iterator accept?
	using value_type = std::remove_reference_t<T>;

	// What is the difference type of 'Node' struct?
	using difference_type = std::ptrdiff_t;

	// What is the pointer type of this iterator?
	using pointer = value_type*;

	// What is the reference type of this iterator?
	using reference = value_type&;

	// What is the category of this iterator?
	// What kinds of iterators shall our List class accept?
	using iterator_category = std::input_iterator_tag;

	// Uncomment bellow line to accept ex. std::vector iterator
	// using iterator_category = std::random_access_iterator_tag

       // THE REST OF THE CLASS GOES HERE:
       // ...
}


Step2: Define acceptable List iterator trait like so:

1
2
3
4
5
6
// My 'List' class accepts iterators of same type traits as my own iterator 'List::iterator'
template<typename InputIterator>
using required_input_iterator =
	std::enable_if_t<std::is_same_v<
	typename std::iterator_traits<InputIterator>::iterator_category,
	typename std::iterator_traits<List<T>::iterator>::iterator_category>>;



Step 3: Define your constructors however you like, I made following definition as a demonstration that correct constructor is called:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
explicit List(size_type n)
{
	std::cout << "List(size_type n)" << std::endl;
}

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

List(const std::initializer_list<T>& i_list)
{
	std::cout << "List(const std::initializer_list<T>& i_list)" << std::endl;
}

template<typename InputIterator, typename = required_input_iterator<InputIterator>>
List(InputIterator, InputIterator)
{
	std::cout << "List(InputIterator, InputIterator)" << std::endl;
}


Step 4: Finally test constructor call and initialization:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main()
{
	// TEST CASE 1: List(size_type n, const_reference v)
	List<int> lis(5, 6);

	// TEST CASE 2: List(InputIterator, InputIterator)
	List<int> iter_list(lis.begin(), lis.end());

	// TEST CASE 3: explicit List(size_type n)
	List<int> asdf(10);

	// TEST CASE 4: List(const std::initializer_list<T>& i_list)
	List<int> int_list({ 1,2,3,4,5,6 });

	// TEST CASE 5: with vector this doesn't work because vector is random access iterator
	// If you want to accept vector iterator then define your iterator as follows:
	// using iterator_category =  std::random_access_iterator_tag
	
	std::vector<int> vec_lis{ 1,2,3,4,5 };
	// List<int> vec_lis_test(vec_lis.begin(), vec_lis.end()); // ERROR: my iterator is input iter not random!
}


Sample program output:
List(size_type n, const_reference v)
List(InputIterator, InputIterator)
List(size_type n)
List(const std::initializer_list<T>& i_list)

test.exe exited with code 0



Following are required headers:
1
2
3
#include <type_traits> // for iterator tratis
#include <iostream> // To test constructors
#include <vector>  // To test vector iterators 


EDIT:
You can get compilable code from your post here:
http://s000.tinyupload.com/?file_id=05825238966543919545

If you want this file to be removed from tinyupload, let me know.
Last edited on
@malibor
Your code doesn't seem to work with raw C-style arrays:
1
2
        int arr[] {1,2,3,4,5};
	List<int> arr_list(arr, arr+5);
@hbcpp
mbozzi's code works just fine with both constructors for me:
https://onlinegdb.com/Bk8znlgoI
Last edited on
@TheToaster
I don't want either you or @mbozzi to take this personal but you have both missed the point not just of the OP but also misread my post on how to make it work and how it should be done.

Your code doesn't seem to work with raw C-style arrays:

Not true it works just fine with C-style arrays

mbozzi's code works just fine with both constructors for me


Well my code also works just fine, if you look at comments I've put into code sample in my previous code post you'll see this:
1
2
// Uncomment bellow line to accept ex. std::vector iterator
// using iterator_category = std::random_access_iterator_tag 


If you uncomment this line it will work.

1
2
3
4
5
6
7
8
class iterator
{
	// Define your iterator traits however you like here
public:
        using iterator_category = std::random_access_iterator_tag  /* THIS */
 
        // ...
};


1
2
3
4
5
6
int main()
{
     // works just fine!
     int arr[] {1,2,3,4,5};
     List<int> arr_list(arr, arr+5);
}


Now, the major issue you people missed is that OP want's his iterator to be input iterator not random access iterator which is FYI not the same, and to construct from C style array requires random access iterator.

in mbozzi code version he defines constructor like this: (added impl. for testing)
1
2
3
4
5
template<typename InputIterator, typename = decltype(*std::declval<InputIterator>())>
List(InputIterator first, InputIterator last)
{
	std::cout << "List(InputIterator, InputIterator)" << std::endl;
}


but the OP want's his iterator to be:
using iterator_category = std::input_iterator_tag;

Do you see the problem?
The problem is that the design of the OP's iterator is now broken

1
2
3
// THIS WILL WORK, BUT IT SHOULD NOT!
std::vector<int> vec_lis{ 1,2,3,4,5 };
List<int> vec_lis_test(vec_lis.begin(), vec_lis.end());


the above works, but OP defined his List class iterator as input iterator but std::vector iterator is random access iterator, so the promise has been broken, and the design is bad, as simple as that.

Ofc. if the OP wants to accept random access iterator he just defines is like this:
using iterator_category = std::input_iterator_tag;

and everthing will work just fine, in which case even the mbozzi version is valid!
Last edited on
Not true it works just fine with C-style arrays
See the following code.
https://onlinegdb.com/B16PPWeoL


EDIT: I guess if you replace it with RandomAccessIterator it works, never mind.

Now, the major issue you people missed is that OP want's his iterator to be input iterator not random access iterator which is FYI not the same.


A random-access iterator IS an input iterator. OP is attempting to recreate std::list using his own implementation. See the following from cppreference:

https://en.cppreference.com/w/cpp/iterator

All of the iterator categories (except LegacyOutputIterator) can be organized into a hierarchy, where more powerful iterator categories (e.g. LegacyRandomAccessIterator) support the operations of less powerful categories (e.g. LegacyInputIterator).


As you can see, LegacyRandomAccessIterator contains all the capabilities of LegacyInputIterators. They can therefore be used for Input Iterator operations. OP is attempting to recreate the following from std::list:

1
2
3
template< class InputIt >
list( InputIt first, InputIt last,
      const Allocator& alloc = Allocator() );


std::list allows the construction of a list with RandomAccessIterators, ForwardIterators, or BidirectionalIterators, since they all support InputIterator operations. You can construct an std::list from a std::vector::iterator. You can construct a std::list from an std::list::iterator. You can construct a std::list with raw array pointers.

However, your version does not allow certain iterators. mbozzi's version does.
Last edited on
See the following code.
https://onlinegdb.com/B16PPWeoL


You forgot to uncomment the line:
using iterator_category = std::random_access_iterator_tag

EDIT:

A random-access iterator IS an input iterator.

Yes, it is, but type trait wants an input iterator because it's declared as

std::enable_if_t<std::is_same_v<...>>

NOT:

std::enable_if_t<std::is_base_of_v<...>>

I declared it so because the I think that's what the OP want's.
he can modify it if his intentions are different.
Last edited on
I saw that, fixed now.
Yes, it is, but type trait wants an input iterator because it's declared as


Which is why mbozzi's type trait is better because it uses std::enable_if_t<std::is_base_of_v<...>> and it operates more like how std::list operates than being unnecessarily restrictive.
Last edited on
OK no problem, it looks like we both modified our posts, but the point remains the same.

Which is why mbozzi's type trait is better because it uses std::enable_if_t<std::is_base_of_v<...>>


OK, I used std::is_same_v instead of std::is_base_of_v because in last OP post it looked like that's what he wants:
http://www.cplusplus.com/forum/beginner/270540/#msg1165962
Wow, thanks guys. Awesome discussion, now I understand it much better. Still I have some reading to do but, I am certainly in a pretty better position than I was before this post.


@TheToaster
mbozzi's code works just fine with both constructors for me:

It doesn't when lis is of type List. In the link you gave me it works because lis is of type std::vector. See here:
https://onlinegdb.com/SymGxOWjU

@malibor
Thank you for the code, it works.
The code is similar to what I found in the file stl_list.h:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
uct _List_iterator
    {
      typedef _List_iterator<_Tp>		_Self;
      typedef _List_node<_Tp>			_Node;

      typedef ptrdiff_t				difference_type;
      typedef std::bidirectional_iterator_tag	iterator_category;
      typedef _Tp				value_type;
      typedef _Tp*				pointer;
      typedef _Tp&				reference;

// THE REST OF THE CLASS
// ... 


According to the reference that TheToaster provided through the link, the difference between std::bidirectional_iterator_tag and std::random_access_iterator_tag is that the former supports a random access operation.
Now, hoping that I am not overextending the post and bothering you too much with this question, what exactly is being accessed randomly there. Is it the data? If so, how does it happen?
Iterator categories in C++ can broadly be divided into multiple categories, like Random Access iterators, Bidirectional iterators, and Forward iterators. Even beyond that, these iterators can support Input/Output operations, which make them input or output iterators as well, respectively.

Random access means that you can randomly access any element inside of the container. This is the case with std::vector, because you can simply call operator[] with an index n and receive the nth element of the container instantly. This is a constant time ( O(1) ) operation. You can think of raw pointers as "random access iterators" because they can jump anywhere. If you have an array of 100 elements called arr, then arr[0] would take about the same time to access as arr[99] since they are stored contiguously in memory.

Linked lists cannot do this because they are not contiguous. Thus, linked lists do not support random access iteration. Thus, they do not provide operator[]. They are not able to access any element in the underlying container with an index. Even if they provided an operator[] that does this, internally the list would just be traversing the pointers in a loop or something to reach the specified element, which takes O(n) time. Thus, they support bidirectional iteration, which means they can operate incrementally in either direction, moving one element at a time, but they cannot jump to, say, 5 elements in the list without having to traverse the list through loops.

Forward iterators are like bidirectional iterators, but they only support "forward iteration", meaning they can only go in one direction rather than two. This is the case with singly linked lists, like std::forward_list.
Last edited on
It doesn't when lis is of type List. In the link you gave me it works because lis is of type std::vector. See here:



That's because you need to provide public type aliases for the iterator category in List::iterator and List::const_iterator. You need to provide public aliases for the following types:
https://en.cppreference.com/w/cpp/iterator/iterator_traits

difference_type
value_type
pointer
reference
iterator_category

Do this and it should work just fine:
https://onlinegdb.com/Sy_TMKbsI

You are implementing a doubly linked list so the correct iterator_category should be bidirectional_iterator_tag, not a generic input_iterator_tag.

By the way, the reason it is segfaulting is because of the way you have implemented your begin() and end() functions in the iterator. You are dereferencing a nullptr when head is empty.
Last edited on
@TheToater ooh I see. The explanation was really useful!

By the way, the reason it is segfaulting is because of the way you have implemented your begin() and end() functions in the iterator.

Yeah I am aware of that, I haven't started writing code for the operations of the list yet.
I was trying to get all the methods' declarations right first and got stuck on the implementation of SFINAE, but now I think it is all good to go.

A silly question I forgot to ask: when you guys were saying OP were you referring to me (the post author)?
Yes. OP = Original Poster
;)
Topic archived. No new replies allowed.
Pages: 12