Sortable<Iterator<T>> dummy implementation

[SSteven]

I am writing a template function sort<Cont> to sort a Container type Cont:

template<typename Cont>
void sort(Cont& c)
{
   /// ...

   static_assert(Estd::Sortable<Estd::Iterator<Cont>>(),
                 "sort(): Cont argument not Sortable");

   std::sort(begin(c), end(c));
}

As you can see, this template function internally calls the standard library sort(b, e) algorithm.

To write the sort(Cont) template function, I need to implement the Sortable<Iterator<T>> type predicate, which is supposed to indicate if the iterator of type T is Sortable or not.

At this stage, I am not interested in implementing the actual semantics of the Sortable<Iterator<T>> type predicate; a dummy implementation is sufficient, just to test the interface.

I have tried the following:

   template<typename T>
   constexpr typename T::iterator Estd::Iterator()
   {
      return T::iterator;
   }

   template<typename T>
   constexpr bool Estd::Sortable()
   {
      return true;	/// dummy implementation
   }

The invocation of the sort(Cont&) function template was done as follows:

   vector<int> v {20, 15, 19, 1};

   sort(v);

However, I get the following compilation error:

   template<class T> constexpr bool Estd::Sortable()

   template argument deduction / substitution failed   

How should I code the Sortable() predicate's interface correctly?

Thanks.

[gunnerfunner]

The following program utilizes the fact that std::sort() requires random access iterators:

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


template <template <typename, typename...> class Container, typename T>
//function with arbitrary container type:
//http://stackoverflow.com/questions/7728478/c-template-class-function-with-arbitrary-container-type-how-to-define-it
void isStandardLibrarySortable(const Container<T>& c)
{
    using category = typename Container<T>::iterator::iterator_category;
    //iterator trats: http://en.cppreference.com/w/cpp/iterator/iterator_traits
    if (std::is_same<category, std::random_access_iterator_tag>::value)
    //http://en.cppreference.com/w/cpp/types/is_same
    {
        std::cout << "container uses std::sort() \n";
    }
    else
    {
        std::cout << "not \n";
    }
}
int main()
{
    std::vector<int> v{};
    std::set<int> s{};
    std::deque<int> d{};
    std::list<int> l{};

    isStandardLibrarySortable(v);//prints uses std::sort()
    isStandardLibrarySortable(s);//prints no (set already sorted && not random access)
    isStandardLibrarySortable(d);//prints uses std::sort()
    isStandardLibrarySortable(l);//prints no (list has its member sort())
}

std::sort() has some additional requirements viz. that type T is value-swappable and, for custom iterators, that the type of the dereferenced iterator is move assignable and move constructable. Also if std::sort() uses a predicate then the function object or lambda should be a valid comparator. For the purpose of this program we're not focussing on these additional requirements:
http://en.cppreference.com/w/cpp/algorithm/sort

[JLBorges]

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

template < typename ITERATOR > constexpr bool is_random_access_iterator()
{
    return std::is_same< typename std::iterator_traits<ITERATOR>::iterator_category,
                         std::random_access_iterator_tag >::value ;
}

template < typename ITERATOR > constexpr bool is_mutable_iterator()
{
    using element_type = typename std::remove_reference< decltype( *std::declval<ITERATOR>() ) >::type ;
    return !std::is_const<element_type>::value ;
}

// note: quick and dirty, does not cover all edge cases
// C++17: use std::is_swappable instead
template < typename ITERATOR > constexpr bool is_iter_swappable()
{
    using value_type = typename std::iterator_traits<ITERATOR>::value_type ;
    return std::is_copy_assignable<value_type>::value && std::is_copy_constructible<value_type>::value ;
}

template < typename ITERATOR > constexpr bool is_std_sortable_iterator()
{
    return is_random_access_iterator<ITERATOR>() &&
    is_mutable_iterator<ITERATOR>() &&
    is_iter_swappable<ITERATOR>() ;
}

template < typename SEQUENCE > constexpr bool is_std_sortable_sequence()
{ return is_std_sortable_iterator< decltype( std::begin( std::declval<SEQUENCE&>() ) ) >() ; }

template< typename SEQUENCE, typename CMP = std::less<> >
typename std::enable_if< is_std_sortable_sequence<SEQUENCE>() >::type
std_sort( SEQUENCE& seq, CMP cmp = {} )
{ std::sort( std::begin(seq), std::end(seq), cmp ) ; }

int main()
{
    struct A // not swappable
    {
        int v ;
        bool operator< ( const A& that ) const { return v < that.v ; }
        A& operator=(A) = delete ;
    };

    std::cout << std::boolalpha
              << is_std_sortable_sequence< int[50] >() << '\n' // true
              << is_std_sortable_sequence< const int[50] >() << '\n' // false
              << is_std_sortable_sequence< std::vector<int> >() << '\n' // true
              << is_std_sortable_sequence< const std::vector<int> >() << '\n' // false
              << is_std_sortable_sequence< std::vector<A> >() << '\n' ; // false

    int a[78] {} ; std_sort(a) ; // fine

    // std::list<int> lst( a, a+78 ) ; std_sort(lst) ; // error: no matching function
                                                       // note: candidate template ignored: disabled by 'enable_if'
}

http://coliru.stacked-crooked.com/a/f3d80491e50556f5

[SSteven]

Thanks for the replies.

Both replies would have been useful, if I were interested in using the standard library's mechanisms for checking if a container is sortable.

However, in this case, in fact I am not.

The sample code I had originally posted is from Stroustrup's book, viz:

template<typename Cont>
void sort(Cont& c)
{
   /// ...

   static_assert(Estd::Sortable<Estd::Iterator<Cont>>(),
                 "sort(): Cont argument not Sortable");

   std::sort(begin(c), end(c));
}

Thus, for this example, I am particularly interested in how to code (the interface) of the Estd::Sortable<Estd::Iterator<Cont>>() function. I am not interested in the semantics of the function, just the function interface.

As you can see, if the call is syntactically correct, the 2 type functions must be of the following pattern:

   template<typename T>
   constexpr typename T::iterator Estd::Iterator()
   {
      return T::iterator;
   }

   template<typename T>
   constexpr bool Estd::Sortable()
   {
      return true;	/// dummy implementation
   }

However, it doesn't work and instead gives a "template argument deduction/substitution failed" error.


Thus, let me restate the pattern of the problem:

Assuming it is possible to write a function call S<I<T>>, where T is a type, and S<T> and I<T> are function templates, how can we code the interfaces of the S<T> and I<T> function templates?

It is really a query about syntax. I'm not interested in the sorting per se.

I hope that clarifies the query.

Thanks.

[JLBorges]

> if the call is syntactically correct, the 2 type functions must be of the following pattern:

Should be:

template<typename T>
constexpr typename T::iterator Estd::Iterator()
{
    // return T::iterator;
    return typename T::iterator{} ; 
}

This is probably what was intended:

namespace Estd
{
    template < typename T > using Iterator = typename T::iterator ;

    template< typename T > constexpr bool Sortable() { return true ; }
}

template< typename Cont > void sort(Cont& c)
{
   static_assert( Estd::Sortable< Estd::Iterator<Cont> >(),
                  "sort(): Cont argument not Sortable");

   std::sort(begin(c), end(c));
}