Discussion:
Rewriting the standard algorithm std::reverse.
(too old to reply)
'Vlad from Moscow' via ISO C++ Standard - Discussion
2018-10-26 17:31:01 UTC
Permalink
As it si known the standard algorithm std::reverse is specialized based on
the iterator category.

I tried to rewrite the algorithm using the clause requires. And I got the
following.

#include <iostream>
#include <type_traits>
#include <iterator>
#include <list>
#include <vector>


template <typename Iterator>
requires std::is_base_of_v<std::bidirectional_iterator_tag, typename std::
iterator_traits<Iterator>::iterator_category> &&
std::is_base_of_v<typename std::iterator_traits<Iterator>::
iterator_category, std::bidirectional_iterator_tag>
void reverse( Iterator first, Iterator last )
{
std::cout << "reverse with a bidirectional iterator is called\n";
for ( ; first != last && first != --last; ++first )
{
std::iter_swap( first, last );
}
}


template <typename Iterator>
requires std::is_base_of_v<std::random_access_iterator_tag, typename std::
iterator_traits<Iterator>::iterator_category> &&
std::is_base_of_v<typename std::iterator_traits<Iterator>::
iterator_category, std::random_access_iterator_tag>
void reverse( Iterator first, Iterator last )
{
std::cout << "reverse with a random access iterator is called\n";
if ( first != last )
{
for ( ; first < --last; ++first )
{
std::iter_swap( first, last );
}
}
}


int main()
{
std::list<int> lst = { 1, 2, 3, 4, 5 };

std::cout << "std::list<int>: ";
for ( int x : lst ) std::cout << x << ' ';
std::cout << '\n';

reverse( std::begin( lst ), std::end( lst ) );


for ( int x : lst ) std::cout << x << ' ';
std::cout << '\n';


std::vector<int> v = { 1, 2, 3, 4, 5 };

std::cout << "\nstd::vector<int>: ";
for ( int x : v ) std::cout << x << ' ';
std::cout << '\n';


reverse( std::begin( v ), std::end( v ) );


for ( int x : v ) std::cout << x << ' ';
std::cout << '\n';
}


Is there any other ways to rewrite the requires expression more simpler?
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
b***@gmail.com
2018-10-30 14:58:07 UTC
Permalink
Post by 'Vlad from Moscow' via ISO C++ Standard - Discussion
As it si known the standard algorithm std::reverse is specialized based on
the iterator category.
I tried to rewrite the algorithm using the clause requires. And I got the
following.
#include <iostream>
#include <type_traits>
#include <iterator>
#include <list>
#include <vector>
template <typename Iterator>
iterator_traits<Iterator>::iterator_category> &&
iterator_category, std::bidirectional_iterator_tag>
void reverse( Iterator first, Iterator last )
{
std::cout << "reverse with a bidirectional iterator is called\n";
for ( ; first != last && first != --last; ++first )
{
std::iter_swap( first, last );
}
}
template <typename Iterator>
iterator_traits<Iterator>::iterator_category> &&
iterator_category, std::random_access_iterator_tag>
void reverse( Iterator first, Iterator last )
{
std::cout << "reverse with a random access iterator is called\n";
if ( first != last )
{
for ( ; first < --last; ++first )
{
std::iter_swap( first, last );
}
}
}
This kind of refinement is what concepts are really good at. You just want:

template <BidirectionalIterator It>
void reverse(It, It);

template <RandomAccessIterator It>
void reverse(It, It);

These concepts are proposed in
P0896: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0896r3.pdf,
RandomAccessIterator subsumes BidirectionalIterator which is what you need
to make this work.

Your requirement set is the pre-concepts approach to doing something like
this, where you have to make your overloads mutually exclusive. That isn't
something you'll need to do anymore.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
'Vlad from Moscow' via ISO C++ Standard - Discussion
2018-11-08 13:28:45 UTC
Permalink
Anyway it is interesting to know what is the preferable way of defining of
the algorithm among these approaches. :)

The first one is classic

template <typename Iterator>
void reverse( Iterator first, Iterator last, std::bidirectional_iterator_tag
)
{
// std::cout << "reverse with a bidirectional iterator is called\n";
for ( ; first != last && first != --last; ++first )
{
std::iter_swap( first, last );
}
}

template <typename Iterator>
void reverse( Iterator first, Iterator last, std::random_access_iterator_tag
)
{
// std::cout << "reverse with a random access iterator is called\n";
if ( first != last )
{
for ( ; first < --last; ++first )
{
std::iter_swap( first, last );
}
}
}

template <typename Iterator>
void reverse( Iterator first, Iterator last )
{
reverse( first, last, typename std::iterator_traits<Iterator>::
iterator_category() );
}



The second one is the following

template <typename Iterator>
requires std::is_same_v<std::bidirectional_iterator_tag, typename std::
iterator_traits<Iterator>::iterator_category>
void reverse( Iterator first, Iterator last )
{
// std::cout << "reverse with a bidirectional iterator is called\n";
for ( ; first != last && first != --last; ++first )
{
std::iter_swap( first, last );
}
}

template <typename Iterator>
requires std::is_same_v<std::random_access_iterator_tag, typename std::
iterator_traits<Iterator>::iterator_category>
void reverse( Iterator first, Iterator last )
{
// std::cout << "reverse with a random access iterator is called\n";
if ( first != last )
{
for ( ; first < --last; ++first )
{
std::iter_swap( first, last );
}
}
}


And at last the third one is

template <typename BidirectionalIterator>
requires std::is_base_of_v<std::bidirectional_iterator_tag, typename std::
iterator_traits<BidirectionalIterator>::iterator_category>
void reverse( BidirectionalIterator first, BidirectionalIterator last )
{
if constexpr( std::is_same_v<std::random_access_iterator_tag, typename
std::iterator_traits<BidirectionalIterator>::iterator_category> )
{
// std::cout << "reverse with a random access iterator is
called\n";
if ( first != last )
{
for ( ; first < --last; ++first )
{
std::iter_swap( first, last );
}
}
}
else
{
// std::cout << "reverse with a bidirectional iterator is
called\n";
for ( ; first != last && first != --last; ++first )
{
std::iter_swap( first, last );
}
}
}


Too many posibbilities.:)

втПрМОк, 30 Пктября 2018 г., 17:58:07 UTC+3 пПльзПватель
Post by b***@gmail.com
Post by 'Vlad from Moscow' via ISO C++ Standard - Discussion
As it si known the standard algorithm std::reverse is specialized based
on the iterator category.
I tried to rewrite the algorithm using the clause requires. And I got the
following.
#include <iostream>
#include <type_traits>
#include <iterator>
#include <list>
#include <vector>
template <typename Iterator>
requires std::is_base_of_v<std::bidirectional_iterator_tag, typename std
::iterator_traits<Iterator>::iterator_category> &&
iterator_category, std::bidirectional_iterator_tag>
void reverse( Iterator first, Iterator last )
{
std::cout << "reverse with a bidirectional iterator is called\n";
for ( ; first != last && first != --last; ++first )
{
std::iter_swap( first, last );
}
}
template <typename Iterator>
requires std::is_base_of_v<std::random_access_iterator_tag, typename std
::iterator_traits<Iterator>::iterator_category> &&
iterator_category, std::random_access_iterator_tag>
void reverse( Iterator first, Iterator last )
{
std::cout << "reverse with a random access iterator is called\n";
if ( first != last )
{
for ( ; first < --last; ++first )
{
std::iter_swap( first, last );
}
}
}
template <BidirectionalIterator It>
void reverse(It, It);
template <RandomAccessIterator It>
void reverse(It, It);
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0896r3.pdf,
RandomAccessIterator subsumes BidirectionalIterator which is what you need
to make this work.
Your requirement set is the pre-concepts approach to doing something like
this, where you have to make your overloads mutually exclusive. That isn't
something you'll need to do anymore.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Casey Carter
2018-11-13 04:35:15 UTC
Permalink
template<std::BidirectionalIterator I>
void reverse(I first, I last) {
for (; first != last && first != --last; ++first) {
std::ranges::iter_swap(first, last);
}
}
Post by 'Vlad from Moscow' via ISO C++ Standard - Discussion
Anyway it is interesting to know what is the preferable way of defining of
the algorithm among these approaches. :)
The first one is classic
template <typename Iterator>
void reverse( Iterator first, Iterator last, std::bidirectional_iterator_tag
)
{
// std::cout << "reverse with a bidirectional iterator is called\n";
for ( ; first != last && first != --last; ++first )
{
std::iter_swap( first, last );
}
}
template <typename Iterator>
void reverse( Iterator first, Iterator last, std::random_access_iterator_tag
)
{
// std::cout << "reverse with a random access iterator is called\n";
if ( first != last )
{
for ( ; first < --last; ++first )
{
std::iter_swap( first, last );
}
}
}
template <typename Iterator>
void reverse( Iterator first, Iterator last )
{
iterator_category() );
}
The second one is the following
template <typename Iterator>
iterator_traits<Iterator>::iterator_category>
void reverse( Iterator first, Iterator last )
{
// std::cout << "reverse with a bidirectional iterator is called\n";
for ( ; first != last && first != --last; ++first )
{
std::iter_swap( first, last );
}
}
template <typename Iterator>
iterator_traits<Iterator>::iterator_category>
void reverse( Iterator first, Iterator last )
{
// std::cout << "reverse with a random access iterator is called\n";
if ( first != last )
{
for ( ; first < --last; ++first )
{
std::iter_swap( first, last );
}
}
}
And at last the third one is
template <typename BidirectionalIterator>
iterator_traits<BidirectionalIterator>::iterator_category>
void reverse( BidirectionalIterator first, BidirectionalIterator last )
{
if constexpr( std::is_same_v<std::random_access_iterator_tag, typename
std::iterator_traits<BidirectionalIterator>::iterator_category> )
{
// std::cout << "reverse with a random access iterator is called\n";
if ( first != last )
{
for ( ; first < --last; ++first )
{
std::iter_swap( first, last );
}
}
}
else
{
// std::cout << "reverse with a bidirectional iterator is called\n";
for ( ; first != last && first != --last; ++first )
{
std::iter_swap( first, last );
}
}
}
Too many posibbilities.:)
втПрМОк, 30 Пктября 2018 г., 17:58:07 UTC+3 пПльзПватель
Post by b***@gmail.com
Post by 'Vlad from Moscow' via ISO C++ Standard - Discussion
As it si known the standard algorithm std::reverse is specialized based
on the iterator category.
I tried to rewrite the algorithm using the clause requires. And I got
the following.
#include <iostream>
#include <type_traits>
#include <iterator>
#include <list>
#include <vector>
template <typename Iterator>
requires std::is_base_of_v<std::bidirectional_iterator_tag, typename std
::iterator_traits<Iterator>::iterator_category> &&
iterator_category, std::bidirectional_iterator_tag>
void reverse( Iterator first, Iterator last )
{
std::cout << "reverse with a bidirectional iterator is called\n";
for ( ; first != last && first != --last; ++first )
{
std::iter_swap( first, last );
}
}
template <typename Iterator>
requires std::is_base_of_v<std::random_access_iterator_tag, typename std
::iterator_traits<Iterator>::iterator_category> &&
iterator_category, std::random_access_iterator_tag>
void reverse( Iterator first, Iterator last )
{
std::cout << "reverse with a random access iterator is called\n";
if ( first != last )
{
for ( ; first < --last; ++first )
{
std::iter_swap( first, last );
}
}
}
template <BidirectionalIterator It>
void reverse(It, It);
template <RandomAccessIterator It>
void reverse(It, It);
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0896r3.pdf,
RandomAccessIterator subsumes BidirectionalIterator which is what you need
to make this work.
Your requirement set is the pre-concepts approach to doing something like
this, where you have to make your overloads mutually exclusive. That isn't
something you'll need to do anymore.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussion+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.
Continue reading on narkive:
Loading...