General functions std::reverse and std::sort

[Vlad from Moscow]

In most cases standard algorithms (and some containers' member functions) std::sort and std:;reverse are called over a whole container. For example

 

[code]

std::forward_list<int> f;

// filling the list

f.sort();

// or

f.sort( std::greater<int>() );

 

std::vector<int>  v;

//filling the vector

std::sort( v.begin(), v.end() );

// or

std::sort( v.begin(), v.end(), std::greater<int>() );

[/code]

 

So I suggest to introduce general functions std::reverse and std::sort that will accept  the reference to a container.

 

Below a demostrative example that illustrates the proposal

 

[code]

#include <iostream>

#include <algorithm>

#include <iterator>

#include <functional>

#include <vector>

#include <forward_list>

#include <list>

 

namespace N1 // std

{

 

template <typename T>
void reverse( T &c )
{
 std::reverse( std::begin( c ), std::end( c ) );
}

 

template <typename T, typename Allocator>
void reverse( std::forward_list<T, Allocator> &f )
{
   f.reverse();
}

 

template <typename T, typename Allocator>
void reverse( std::list<T, Allocator> &l )
{
    l.reverse();
}

template <typename T>
void sort( T &c )
{
   std::sort( std::begin( c ), std::end( c ) );
}

 

template <typename T, typename Allocator>
void sort( std::forward_list<T, Allocator> &f )
{
   f.sort();
}

 

template <typename T, typename Allocator>
void sort( std::list<T, Allocator> &l )
{
   l.sort();
}

template <typename T, typename Compare>
void sort( T &c, Compare comp )
{
   std::sort( std::begin( c ), std::end( c ), comp );
}

 

template <typename T, typename Allocator, typename Compare>
void sort( std::forward_list<T, Allocator> &f, Compare comp )
{
   f.sort( comp );
}

 

template <typename T, typename Allocator, typename Compare>
void sort( std::list<T, Allocator> &l, Compare comp )
{
   l.sort( comp );
}

} // end of N1

int main()

{
   int a[3] = { 1, 2, 3 };
   std::forward_list<int> f( std::begin( a ), std::end( a ) );
   std::list<int> l( std::begin( a ), std::end( a ) );
   std::vector<int> v( std::begin( a ), std::end( a ) );

 

   std::cout << "a:\t";
   for ( int x : a ) std::cout << x << ' ';
   std::cout << std::endl;
   std::cout << "f:\t";
   for ( int x : f ) std::cout << x << ' ';
   std::cout << std::endl;
   std::cout << "l:\t";
   for ( int x : l ) std::cout << x << ' ';
   std::cout << std::endl;
   std::cout << "v:\t";
   for ( int x : v ) std::cout << x << ' ';
   std::cout << std::endl;

 

   N1::reverse( a );
   N1::reverse( f );
   N1::reverse( l );
   N1::reverse( v );

 

   std::cout << "a:\t";
   for ( int x : a ) std::cout << x << ' ';
   std::cout << std::endl;
   std::cout << "f:\t";
   for ( int x : f ) std::cout << x << ' ';
   std::cout << std::endl;
   std::cout << "l:\t";
   for ( int x : l ) std::cout << x << ' ';
   std::cout << std::endl;
   std::cout << "v:\t";
   for ( int x : v ) std::cout << x << ' ';
   std::cout << std::endl;

 

   N1::sort( a );
   N1::sort( f );
   N1::sort( l );
   N1::sort( v );

 

   std::cout << "a:\t";
   for ( int x : a ) std::cout << x << ' ';
   std::cout << std::endl;
   std::cout << "f:\t";
   for ( int x : f ) std::cout << x << ' ';
   std::cout << std::endl;
   std::cout << "l:\t";
   for ( int x : l ) std::cout << x << ' ';
   std::cout << std::endl;
   std::cout << "v:\t";
   for ( int x : v ) std::cout << x << ' ';
   std::cout << std::endl;

 

   N1::sort( a, std::greater<int>() );
   N1::sort( f, std::greater<int>() );
   N1::sort( l, std::greater<int>() );
   N1::sort( v, std::greater<int>() );

 

   std::cout << "a:\t";
   for ( int x : a ) std::cout << x << ' ';
   std::cout << std::endl;
   std::cout << "f:\t";
   for ( int x : f ) std::cout << x << ' ';
   std::cout << std::endl;
   std::cout << "l:\t";
   for ( int x : l ) std::cout << x << ' ';
   std::cout << std::endl;
   std::cout << "v:\t";
   for ( int x : v ) std::cout << x << ' ';
   std::cout << std::endl;

}
[/code]

 

[Zhihao Yuan]

On Mon, Jun 24, 2013 at 5:05 PM, Vlad from Moscow <vlad....@mail.ru> wrote:
> In most cases standard algorithms (and some containers' member functions)
> std::sort and std:;reverse are called over a whole container. For example

Don't worry. The Ranges study group is responsible for handling that.

--
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://4bsd.biz/

[Vlad from Moscow]

I am not worry I am making a proposal.

вторник, 25 июня 2013 г., 1:09:21 UTC+4 пользователь Zhihao Yuan написал:

[morw...@gmail.com]

Honestly, I would be more interested in std::reversed and std::sorted on containers, which could be handy to use with rnge-based for loopd than in std::sort and std::reverse.

[Vlad from Moscow]

You can make a corresponding proposal.

вторник, 25 июня 2013 г., 3:10:17 UTC+4 пользователь morw...@gmail.com написал:

[morw...@gmail.com]

Well, I thought I could write one once, but there were many design choices that I did not overcome: for example,
my first intent was to create generator objects in order to iterate through them (the feature was really made for
range-based for loops and almost not to be used anywhere else), but my choices when trying to implement it
seemed clumsy.

Moreover, that was close to Boost's range adapters, so I finally decided to wait to see if a more generic
mecanism could work with range instead of having specialized generator functions lost somewhere into
<utility> (or any other standard header).

The generator I implemented could be used like this for example:

    for (auto elem: std::reversed(container))
    {
        if (elem)
        {
            do_something();
            break;
        }
    }

Whatever, it's probably wiser to wait for ranges before trying anything else, unless reversed/sorted are
useful enough by themselves to undergo a proposal.

[Vlad from Moscow]

Your ideas are different than mine. So they do not contradict each other. I want to have general functions sort and reverse even for classes that have no iterators. The only condition they must satisfy is the presence of  their own member functions sort and reverse.

For the demontsrative example I selected the approach used for std:;swap that only to illustrate the idea. However it would be better to write these functions based on conditions

std::is_member_function_pointer<decltype( &Container::reverse)>::value

std::is_member_function_pointer<decltype( &Container::sort)>::value

 

 

вторник, 25 июня 2013 г., 11:49:04 UTC+4 пользователь morw...@gmail.com написал:

[Martinho Fernandes]

On Thu, Jun 27, 2013 at 12:07 PM, Vlad from Moscow <vlad....@mail.ru> wrote:
> Your ideas are different than mine. So they do not contradict each other. I
> want to have general functions sort and reverse even for classes that have
> no iterators. The only condition they must satisfy is the presence of their
> own member functions sort and reverse.
> For the demontsrative example I selected the approach used for std:;swap
> that only to illustrate the idea. However it would be better to write these
> functions based on conditions
>
> std::is_member_function_pointer<decltype( &Container::reverse)>::value
> std::is_member_function_pointer<decltype( &Container::sort)>::value
>

The conditions you want are whether or not
`decltype(std::declval<Container>().reverse())` and
`decltype(std::declval<Container>().sort())` cause substitution
failures.

[Vlad from Moscow]

So the task is to write appropriate overloaded functions based on these conditions.

четверг, 27 июня 2013 г., 14:10:10 UTC+4 пользователь R. Martinho Fernandes написал:

[Vlad from Moscow]

It seems using requires expressions it is not difficult to write the general function sort and reverse.

I do not know yet requires expressions enough well but the initial implementation an look for example the following way. It can be further elaborated.

Here is a demonstrative program

#include <iostream>

#include <forward_list>
#include <vector>
#include <iterator>
#include <algorithm>


template <typename Container>
void sort( Container &container ) requires requires() { &Container::sort; }
{
    std::cout << "sort with requires is called.\n";
    container.sort();
}


template <typename Container>
void sort( Container &container )
{
    std::cout << "sort without requires is called.\n";
    std::sort( std::begin( container ), std::end( container ) );
}


template <typename Container>
void reverse( Container &container ) requires requires() { &Container::reverse; }
{
    std::cout << "reverse with requires is called.\n";
    container.reverse();
}


template <typename Container>
void reverse( Container &container )
{
    std::cout << "reverse without requires is called.\n";
    std::reverse( std::begin( container ), std::end( container ) );
}


int main()
{
    std::forward_list<int> lst = { 3, 2, 1 };
   
    for ( const auto &item : lst ) std::cout << item << ' ';
    std::cout << '\n';
   
    sort( lst );


    for ( const auto &item : lst ) std::cout << item << ' ';
    std::cout << '\n';


    reverse( lst );



    for ( const auto &item : lst ) std::cout << item << ' ';
    std::cout << '\n';


    std::cout << '\n';
   
    std::vector<int> v = { 3, 2, 1 };


    for ( const auto &item : v ) std::cout << item << ' ';
    std::cout << '\n';
   
    sort( v );


    for ( const auto &item : v ) std::cout << item << ' ';
    std::cout << '\n';


    reverse( v );


    for ( const auto &item : v ) std::cout << item << ' ';
    std::cout << '\n';


    std::cout << '\n';


    int a[] = { 3, 2, 1 };
   
    for ( const auto &item : a ) std::cout << item << ' ';
    std::cout << '\n';
   
    sort( a );


    for ( const auto &item : a ) std::cout << item << ' ';
    std::cout << '\n';


    reverse( a );


    for ( const auto &item : a ) std::cout << item << ' ';
    std::cout << '\n';
}

So I am going to put your attention to this propoisal of general functions std::sort and std::reverse. Of course another set of the function sort should be with a second parameter that specifies the comparison.

 

четверг, 27 июня 2013 г., 14:23:48 UTC+4 пользователь Vlad from Moscow написал:

[Vlad from Moscow]

Maybe it is reasonable tp introduce also similar general functions  like find, lower_bound, upper_bound, equal_range.

пятница, 5 октября 2018 г., 18:51:40 UTC+4 пользователь Vlad from Moscow написал:

[Justin Bassett]

I believe ranges will fill this role. I'm not entirely familiar with it, so I'm not sure if it allows you to write `std::ranges::sort(some_std_list)` (I remember hearing that it does, though), but I believe it otherwise does what you are talking about.

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposal...@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/44e18e2a-13c7-46ec-8d5a-2d4b7acf0e95%40isocpp.org.

[Vlad from Moscow]

I'm sorry.

It would be more correctly to define the function the following way changing the return type tas it is shown

template <typename Container>
Container & sort( Container &container ) requires requires() { &Container::sort; }
{
    container.sort();
   
    return container;
}
 
template <typename Container>
Container & sort( Container &container )
{
    std::sort( std::begin( container ), std::end( container ) );
   
    return container;
}

Consider for example this question of a beginner as me at Stackoverflow https://stackoverflow.com/questions/53557881/checking-if-two-strings-are-anagram#

It is required to determine whether two strings are anagrams of each other.

One of approaches is to sort the strings and compare them.

Using the functions above the function that determines whether strings are anagrams can be written easy.

#include <iostream>
#include <iomanip>
#include <string>

#include <iterator>
#include <algorithm>
 
template <typename Container>

Container & sort( Container &container ) requires requires() { &Container::sort; }
{
    container.sort();
   
    return container;
}
 
template <typename Container>
Container & sort( Container &container )
{
    std::sort( std::begin( container ), std::end( container ) );
   
    return container;
}


bool isAnagrams( std::string s1, std::string s2 )
{
    return std::size( s1 ) == std::size( s2 ) and sort( s1 ) == sort( s2 );
}


int main()
{
    std::cout << "Enter two strings: ";
   
    std::string s1, s2;
   
    std::cin >> s1 >> s2;
   
    std::cout << "The strings " << std::quoted( s1 )
              << " and " << std::quoted( s2 )
              << " are " << ( isAnagrams( s1, s2 ) ? "" : "not" )
              << " anagrams of each other.\n";
}

Its output might look like

Enter two strings: act tac
The strings "act" and "tac" are anagrams of each other.

вторник, 25 июня 2013 г., 1:05:40 UTC+4 пользователь Vlad from Moscow написал:

[Gašper Ažman]

Vlad,

as Justin already said, Ranges already do all that and more. What you want is already in C++20.

G

--

You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposal...@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.

To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/126acf7d-4224-4a72-a34d-890d23ce5759%40isocpp.org.