sorting vector<variant<...>> does not work correctly via operator<

user_10923857 0
Viewed 508

I wanted to sort a std::vector of type std::variant with two custom classes by their member return value. See code below.

Now, using

std::sort(std::begin(shapes), std::end(shapes), [](auto const& a, auto const& b){
        return std::visit([](auto const& s) { return s.area(); }, a)
            < std::visit([](auto const& s) { return s.area(); }, b);
        });

does seem to work, but it is very ugly. Since std::variants operator< operates on their respective values I thought supplying a templated comparison operator would look better. But why does it not work?

Code:

#include <algorithm>
#include <iostream>
#include <variant>
#include <vector>

constexpr double pi = 3.141592865;

struct Square {
    double d{};
    double area() const { return d * d; }
};

struct Circle {
    double r{};
    double area() const { return pi * r * r; }
};

// comparison operator for using std::sort(begin, end);
template <class S, class T>
double operator<(S const& a, T const& b) {
    return a.area() < b.area();
}

int main (int, char**)
{
    std::vector<std::variant<Square, Circle>> shapes;

    shapes.push_back(Circle{2});
    shapes.push_back(Square{2});
    shapes.push_back(Circle{1});
    shapes.push_back(Square{3});

    for (auto const& e: shapes)
    { std::cout << std::visit([](auto const& x) { return x.area(); }, e) << "\n"; }

    std::cout << "\n[SORT]\n\n";
    // Does not work
    std::sort(std::begin(shapes), std::end(shapes));

    /* works
    std::sort(std::begin(shapes), std::end(shapes), [](auto const& a, auto const& b){
            return std::visit([](auto const& s) { return s.area(); }, a)
                < std::visit([](auto const& s) { return s.area(); }, b);
            });
    */

    for (auto const& e: shapes)
    { std::cout << std::visit([](auto const& x) { return x.area(); }, e) << "\n"; }

    return 0;
}

Anyone able to point me in the right direction? I suspect the problem lies within the operator< not working with different types.

Compilation command: $ g++8.2 -std=c++17 test.cpp -o test

Output:

12.5664
4
3.14159
9

[SORT]

4
9
3.14159
12.5664

Weirdly, I run into compilation errors when using godbolts compile explorer and g++8.2, but not when using g++ trunk. See: https://gcc.godbolt.org/z/tKJa4t

c++17 stl c++
2 Answers

This:

std::sort(std::begin(shapes), std::end(shapes));

uses the default sort comparison, which is operator<. operator< on std::variant is defined as comparing on indices first and then, if the two variants hold the same alternative, comparing the underlying values.

In other words:

using V = std::variant<char, int>;
V v1(static_cast<char>(42));  // holds a char
V v2(15);                     // holds an int
v1 < v2;                      // this is true, because 'char' comes before 'int'

So when you sort your variants, you're not sorting by area. You're effectively sorting by the tuple (index, area). Which we could write out the long way:

std::sort(std::begin(shapes), std::end(shapes),
    [](auto const& lhs, auto const& rhs)
    {
        auto tied = [](auto const& x) {
            return std::make_tuple(
                // the index
                x.index(),
                // the area
                std::visit([](auto const& e){ return e.area(); }, x)
                );
        };
        return tied(lhs) < tied(rhs);
    });

This gives the same ordering as your original example. And then if you remove the x.index() part of the tuple, you'll get the ordering that you want.

But it's shorter to just use multiple visitation:

std::sort(std::begin(shapes), std::end(shapes),
    [](auto const& lhs, auto const& rhs)
    {
        std::visit([](auto const& x, auto const& y){
            return x.area() < y.area();
        }, lhs, rhs);
    });

Which will become shorter still in C++20 with Ranges and projections:

std::ranges::sort(shapes, std::less(), [](auto const& x){
    return std::visit([](auto const& e){ return e.area(); }, x);
    });
user_20690640
user_52450330
Related