(C++) Possible to duplicate functionality of function pointers for templated fcns?

spursrule · 12-21-2007, 02:31 AM

Assume I have a templated family of sort fcns such as

Code:

template <class Bi, class Cmp>  insertion_sort(Bi begin, Bi end, Cmp cmp);
template <class Bi, class Cmp>  quicksort(Bi begin, Bi end, Cmp cmp);
template <class Ran, class Cmp>  shellsort(Ran begin, Ran end, Cmp cmp);
...

where Bi and Ran are iterator types (bidirectional and random-access), and Cmp is a binary predicate function object class (such as less<T> from <functional>). Is it possible to set something equivalent to a fcn pointer, capable of calling any of these fcns?

I.e., in main I would check the command-line args, and say one specifies to do quicksort. I would like to do something along the lines of:

Code:

sort = &quicksort;

and then call the sort later (from the main fcn) as something like

Code:

// lt is an object of type std::less<T>
sort(&A[0],&A[n],lt)

- or -

Code:

// lst is a doubly-linked list
sort(lst.begin(),lst.end(),lt)

so that I don't have some long switch statement in my main fcn like:

Code:

switch(sort_type) {
case INSERTION:
  insertion_sort(&A[0],&A[n],lt);
  break;
case QUICK:
  quicksort(&A[0],&A[n],lt);
  break;
case SHELL:
  shellsort(&A[0],&A[n],lt);
  break;
...
}

What's a good way to do something like this? I.e., something equivalent to the idea of a templated fcn pointer sort, capable of handling whatever iterators are passed to it without knowing beforehand.

Can fcn objects be used to duplicate the functionality of generic fcn pointers (since I can't just create a templated fcn pointer)?

graemef · 12-22-2007, 04:26 PM

There may be different ways of looking at this problem but I think that you will need to have a proper class hierarchy so that you iterators are specialised and that you have a sort function that expects a pointer to the the generalised version.
sort (Iter, Cmp)
and your iterators Bi and Ran inherit Iter. That way the signature of your functions will match and you should then be able to achieve what you require.

ta0kira · 12-23-2007, 04:36 PM

Do you want it to choose the algorithm automatically based on iterator type? You'll need some ugly compile-time template tricks for that, I'm afraid, since random-access sort functions won't compile with bidirectional iterators. You may need something like this:

Code:

#include <iterator>
#include <vector>
#include <list>

//fake sort functions for demo purposes

template <class Iterator> void random_access_sort(Iterator, Iterator, int(*)(const Iterator, const Iterator));

template <class Iterator> void bidirectional_sort(Iterator, Iterator, int(*)(const Iterator, const Iterator));


//partially-specialized class to determine sort type

template <class>
struct sort_function {};

//specialized for random-access iterators
template <>
struct sort_function <std::random_access_iterator_tag>
{
    template <class Iterator> static
    void sort(Iterator sStart, Iterator eEnd, int(*cComp)(const Iterator, const Iterator))
    { random_access_sort(sStart, eEnd, cComp); }
};

//specialized for bidirectional iterators
template <>
struct sort_function <std::bidirectional_iterator_tag>
{
    template <class Iterator> static
    void sort(Iterator sStart, Iterator eEnd, int(*cComp)(const Iterator, const Iterator))
    { bidirectional_sort(sStart, eEnd, cComp); }
};


//fake comparison function for demo purposes

template <class Iterator>
int less_than_compare(Iterator, Iterator);



//automatic sorting function which selects algorithm based on iterator type

template <class Iterator>
void auto_sort(Iterator sStart, Iterator eEnd)
{
    sort_function <typename std::iterator_traits <Iterator> ::iterator_category> ::
      sort(sStart, eEnd, &less_than_compare <Iterator>);
}

int main()
{
    std::vector <int> random_access;

    std::list <int>   bidirectional;

    //this uses the random-access sort function
    auto_sort(random_access.begin(), random_access.end());

    //this uses the bidirectional sort function
    auto_sort(bidirectional.begin(), bidirectional.end());
}

ta0kira

PS I think I probably misunderstood the question. Have you looked into using a functor? That would probably be the easiest way to get it done.