How to Pass a Custom Comparator to "Sort"

How to pass a custom comparator to sort?

Define your own <=>, and include Comparable. This is from the Comparable doc:

class SizeMatters
  include Comparable
  attr :str
  def <=>(an_other)
    str.size <=> an_other.str.size
  end
  def initialize(str)
    @str = str
  end
  def inspect
    @str
  end
end

s1 = SizeMatters.new("Z")
s2 = SizeMatters.new("YY")
s3 = SizeMatters.new("XXX")
s4 = SizeMatters.new("WWWW")
s5 = SizeMatters.new("VVVVV")

s1 < s2                       #=> true
s4.between?(s1, s3)           #=> false
s4.between?(s3, s5)           #=> true
[ s3, s2, s5, s4, s1 ].sort   #=> [Z, YY, XXX, WWWW, VVVVV]

You don't actually have to include Comparable, but you get extra functionality for free if you do that after having defined <=>.

Otherwise, you can use Enumerable's sort with a block if your objects implement <=> already.

Another way to use several different comparisons is to use lambdas. This uses the new 1.9.2 declaration syntax:

ascending_sort  = ->(a,b) { a <=> b }
descending_sort = ->(a,b) { b <=> a }

[1, 3, 2, 4].sort( & ascending_sort ) # => [1, 2, 3, 4]
[1, 3, 2, 4].sort( & descending_sort ) # => [4, 3, 2, 1]

foo = ascending_sort
[1, 3, 2, 4].sort( & foo ) # => [1, 2, 3, 4]

Custom Comparator - Java

Comparison-based sorts distinguish values by determining whether or not they are <, =, or >.

For example, 3 < 4, 4 = 4, 4 > 3.

Java Comparators use the convention that

• cmp(a, b) < 0 means a < b
• cmp(a, b) = 0 means a = b
• cmp(a, b) > 0 means a > b

Note that this means if cmp(x, y) = x - y, then you get the normal ordering for the integers. You can check yourself that cmp(x, y) = -(x- y) = y - x gives you the reverse ordering.

When sorting (or doing something else that moves generic elements around by their order, like a PriorityQueue), the algorithm will (repeatedly) consult the comparator to determine whether or not values it has been given are <, =, or >.

std::sort with custom comparator

std::sort accepts a functor. This is any object that can be called (with the correct parameters). The function achieves this by using templates, like the following

template<typename Iter, typename Comp>
void sort(Iter begin, Iter end, Comp compare) { ... }

IntComparator1, 2, and 3 are all valid functors for this comparator, since they can all be called using operator() with 2 integers.

Also like you said, the third option is indeed usually more intuitive.

How to add a comparator to a custom sort function

Considering you have a class or struct CustomType

Pre c++11

struct CustomCompare
{
    bool operator ()(const CustomType& a, const CustomType& b)
    {
        return a.Watever < b.Watever;
    }
};

//usage
merge(vector<CustomType> ..., CustomCompare());

Post c++11, using lambdas:

auto CustomCompare = [](const CustomType & a,const CustomType& b)
{
    return a. .... ;
};
//usage
merge(vector<CustomType> ..., CustomCompare);

There is third option:

You can use std::less but there must exist an operator < that takes your CustomType as arguments

Example:

struct CustomType
{
    //...
    bool operator < (const CustomType& other)const
    {
        return this->Whatever < other.Whatever;
    }
};

And you can specialize std::less:

namespace std
{
    template <>
    struct less <CustomType>
    {
        bool operator()(const CustomType & a, const CustomType & b)
        {
            return ...
        }
    };
}

---

Related Topics