6 Replies - 11789 Views - Last Post: 26 June 2013 - 12:45 PM

#1 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

variadic template sorting

Post icon  Posted 22 March 2013 - 11:00 PM

Sorting at Compile Time with Variadic Templates

C++11 added variadic templates which allow an arbitrary number of template arguments to be used in templates, very much like variadic arguments for functions. This allows for an arbitrary number of types, ints, template templates, etc... to be passed to templates. This gives rise to, among MANY other things, a nice way of representing sequences of information. It used to be that to represent lists of information at compile nasty cons cells were used. Now something as simple as seq<1, 2, 3, 4, 5, 6, 7> can used instead.

The goal of this challenge is to use variadic templates to create a meta function which sorts a sequence of integers.

You can use any sorting algorithm you want, any representation for the sequences you want, and any means of showing the sorted list just so long as variadic templates are used somehow.

This is how I chose to represent my sequences and how I chose to output the sequences; you might find it useful

template<int... xs>
struct seq {};

template<class>
struct printer;
template<int x, int... xs>
struct printer<seq<x, xs...>> {
    static void print() {
        std::cout << x << '\n';
        printer<seq<xs...>>::print();
    }
};
template<>
struct printer<seq<>> {
    static void print() {}
};

//...other code for sorting...


typedef seq<10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0> my_test;

int main() {
    printer<my_test>::print();
    printer<typename sort<my_test>::type>::print();
    return 0;
}



I actually implemented a quicksort. here is my implmentation
Spoiler


Try implementing merge sort, or heap sort(heap sort with a skew heap might be really cool), or even really simple sorts like insertion sort, anything really.

Is This A Good Question/Topic? 3
  • +

Replies To: variadic template sorting

#2 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: variadic template sorting

Posted 21 June 2013 - 04:53 PM

This was a lot of fun. I took a shortcut and used Haskell code from LiteratePrograms as a basis. Of course I needed to convert the code to something that I could translate into templates!

I also wanted to have something more general the just and int sequence so I added a type specifier to the Sequence template. I also used the std::tuple class rather than roll my own.

Here is the haskell:
split_accum_fst :: a -> ([a], [a]) -> ([a],[a])
split_accum_fst x tpl = (x:(fst tpl), snd(tpl))

split_gather :: [a] -> [a] -> ([a], [a])
split_gather (x:xs) (_:_:zs) = split_accum_fst x (split_gather xs zs)
split_gather xs _ = ([], xs)

split :: [a] -> ([a], [a])
split xs = split_gather xs xs 


merge :: (a -> a -> Bool) -> [a] -> [a] -> [a]
merge pred xs []         = xs
merge pred [] ys         = ys
merge pred (x:xs) (y:ys) =
  case pred x y of
    True  -> x: merge pred xs (y:ys)
    False -> y: merge pred (x:xs) ys

mergesort :: (a -> a -> Bool) -> [a] -> [a]
mergesort pred []   = []
mergesort pred [x]  = [x]
mergesort pred xs = merge pred (mergesort pred xs1) (mergesort pred xs2)
  where
    (xs1,xs2) = split xs
    
main = putStrLn (show (mergesort (>) [1,2,3,4,6,5,6,7,8,9,9]))


Here is the C++ TMP solution:
Spoiler


I think I will try to upgrade this to use boost::mpl/boost::fusion but for now this was a LOT of fun and very challenging. Translating from Haskell to C++ templates is an interesting challenge. There are couple of blog pieces that cover the subject and even a couple of sample compilers.

Thanks for the fun ishkabible!!!

This post has been edited by NickDMax: 21 June 2013 - 09:10 PM

Was This Post Helpful? 2
  • +
  • -

#3 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: variadic template sorting

Posted 22 June 2013 - 01:21 PM

Nice!! I had figured this was too templatey for anyone to take up at this point; people tend to steer away from this stuff when I show them :/ I really love doing compile time programming in C++ and I love Haskell; my quick sort was also based on a Haskell implementation. You can do some truly amazing stuff with TMP and other compile time methods. I wanted this challenge to show people how much can be done.

Thanks for taking the challenge up!
Was This Post Helpful? 0
  • +
  • -

#4 vividexstance  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 653
  • View blog
  • Posts: 2,240
  • Joined: 31-December 10

Re: variadic template sorting

Posted 25 June 2013 - 12:46 PM

ishkabible your code compiled for me but didn't print the list sorted, it only moves the 10 to the end of the list. I'm not too familiar with variadic template arguments, so I figured I could learn a little from your and NickDMax's code.

This is the exact output I get upon running the program:

Quote

10
9
8
7
6
5
4
3
2
1
0
9
8
7
6
5
4
3
2
1
0
10

This post has been edited by vividexstance: 25 June 2013 - 12:47 PM

Was This Post Helpful? 1
  • +
  • -

#5 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: variadic template sorting

Posted 26 June 2013 - 08:07 AM

Hrm...let me see.

edit:

somehow I managed to post the wrong version of this. There was just a slight issue with it. I wasn't recursively sorting the partitions

here is the fix
typedef typename concat<
        typename sort<less_stuff>::type,
        typename prepend<
            x,
            typename sort<more_stuff>::type
        >::type
    >::type type;



replace the typedef in the 'sort' class with that and it will be correct

This post has been edited by ishkabible: 26 June 2013 - 08:52 AM

Was This Post Helpful? 0
  • +
  • -

#6 vividexstance  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 653
  • View blog
  • Posts: 2,240
  • Joined: 31-December 10

Re: variadic template sorting

Posted 26 June 2013 - 09:23 AM

Yup that fixed it, thanks.
Was This Post Helpful? 0
  • +
  • -

#7 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: variadic template sorting

Posted 26 June 2013 - 12:45 PM

Thanks for pointing that out by the way!

Also, if you are unfamilair with varadic templates, I think this best helped me understand them if I recall. Of cource, using them was required to really understand their power. It sounds strange to learn this from a vedio, and in general I think that is a bad way to learn to program, but it really teaches the concepts.

edit:
Also, there is an amazing refrence on rvalue refrences here. This enlightened my whole way of thinking about rvalue refrences. This vedio maid it MUCH easier to get rvalue refrences right.

This post has been edited by ishkabible: 26 June 2013 - 12:51 PM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1