Different sort methods with template collection

Question

I sorry if similar question already exists on this forum, if you could, give me the link.

I have a template class

template<typename type>
class DoublyLinkedList {};

And I want to have Sort method in it.

template<typename type>
class DoublyLinkedList
{
public:

void Sort(){}

};

But list is template so it can contains different types. So how I can create methods for all types that I foresee? I tried in this way:

template<typename type>
class DoublyLinkedList
{
public:

void DoublyLinkedList<int>::Sort(){}
void DoublyLinkedList<string>::Sort(){} 

};

But it's wrong. Please help.

You can do it like how [`std::list::sort`](http://en.cppreference.com/w/cpp/container/list/sort) does it. — NathanOliver, Jan 18 '17 at 16:29
Just use standard C++ containers. And Stack Overflow is not a "forum". — Christian Hackl, Jan 18 '17 at 16:29
@ChristianHackl So, It's not possible to do this? I want to have own implementations. — Michael, Jan 18 '17 at 16:31
I know I can possible do it in one method and next recognize type of list, but I ask about two methods. — Michael, Jan 18 '17 at 16:33
@Michael: Of course it's possible. See @NathanOliver's comment. Do it like `std::list` does and allow users to provide a functor which defaults to `std::less`. But it's a completely uninteresting thing to do, because it reinvents the wheel and will be a solution inferior to `std::list`, with not much to do about other than throwing it away and using `std::list` instead. — Christian Hackl, Jan 18 '17 at 16:34
There is another issue to deal with since C++ 11, not having a default allocator. Visual Studio 2015 changed std::list::sort from a bottom up merge sort using a small (25) array of lists to a slower top down merge sort that only uses the iterators. You can read more about this [here](http://stackoverflow.com/questions/40622430/stdlistsort-why-the-sudden-switch-to-top-down-strategy). Note that it is faster to copy a linked list to a vector, sort the vector and copy back, than it is to use std::list::sort. — rcgldr, Jan 18 '17 at 18:30

François Andrieux · Accepted Answer · 2017-01-18T16:37:46.903

1

The way the standard library generally deals with this problem is to allow users to specify their own compare functions. You can add a templated parameter that users of your type can use to provide a Compare function, like std::sort does. In the implementation of sort, you assume that comparer is a function that compares two elements of the list and returns rather or not the first should be before the second.

#include <string>
template<typename type>
class DoublyLinkedList
{
public:
    template<class Comp>
    void Sort(Comp comparer);

};

void foo(DoublyLinkedList<std::string> & list)
{
    // Sort list by length of strings
    list.Sort([](const std::string p_left, const std::string p_right){
        return p_left.size() < p_right.size();
    });
}

edited Jan 18 '17 at 16:37

answered Jan 18 '17 at 16:36

François Andrieux

28,148
6
56
87

I would default `compare` to `std::less` just so you do not always have to provide a functor. – NathanOliver Jan 18 '17 at 16:37
Your code looks pretty clear and proffesional, what do you think about this? http://pastebin.com/6rSJfF4Z I know that this code is bad. – Michael Jan 18 '17 at 16:38
@Michael That approach will not work in practice . It will only work as long as your supported types have compatible interfaces. That means will only be able to do things to your `type` that works for `int`, `std::string` and *all* other types you choose to support. Remember that even if only one of your branches is taken, they all have to compile for all `type` you support. For example, you couldn't access the characters in the case of `string` because when you tried to instantiate with `int` it would fail to find an `operator[]` for the type `int`. – François Andrieux Jan 18 '17 at 16:46
@Michael I've modified your example to demonstrate why it can't work. [pastebin](http://pastebin.com/4zSmXDws) – François Andrieux Jan 18 '17 at 16:51
@FrançoisAndrieux Ok, thanks! Can you tell me what I must do in Sort() method with that lambda to sort int's? If I have that lambda as parameter: http://pastebin.com/DAVjCqWP And I don't know how to use it in Sort(). – Michael Jan 18 '17 at 16:52
@Michael Whichever sort algorithm you are using, it will at one point compare elements. Wherever it would compare two elements (like `x < y`) change it to use the lamdba (like this `comparer(x, y)`). – François Andrieux Jan 18 '17 at 16:56

Different sort methods with template collection

1 Answers1