CODEWITHSUNDEEP
c++comparisonc++17
rtpax
rtpax

Reputation: 1777

Is there a three way comparison for stl containers in c++17

Is there a standard function that allows three way comparison of stl containers

eg

cmp({1,2},{1,3}) < 0
cmp({1,2},{1,2}) == 0

I would like to avoid doing two comparisons on some potentially large containers when one will do, and I'd rather use a standard function than roll my own if there's something standard. I didn't see any on the cppreference page for stl containers, but I'm hoping there's something.

Upvotes: 2

Views: 519

Answers (1)

Barry
Barry

Reputation: 302922

Is there a standard function that allows three way comparison of stl containers

No. C++20 will add std::lexicographical_compare_3way which has a dependency on operator<=> and all of the other things it brought with it.

Until then, it's fairly straightforward to implement an algorithm that does this, by just slightly modifying what std::lexicographical_compare does:

template<class InputIt1, class InputIt2>
int compare_3way(InputIt1 first1, InputIt1 last1,
                 InputIt2 first2, InputIt2 last2)
{
    for ( ; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2 ) {
        if (*first1 < *first2) return -1;
        if (*first2 < *first1) return 1;
    }

    if (first1 == last1) {
        return (first2 == last2) ? 0 : -1;
    } else {
        return 1;
    }
}

This still potentially does two comparisons per element. So an alternative to this simplistic implementation would be to pass another template parameter that is itself a 3-way comparison function that returns an int, so that the body of the loop would be:

int c = compare3way(*first1, *first2);
if (c != 0) {
    return c;
}

Where a default implementation could fallback to just:

struct Compare3way {
    template <typename T, typename U>
    int operator()(T const& lhs, U const& rhs) const {
        if (lhs < rhs) return -1;
        if (rhs < lhs) return 1;
        return 0;
    }
};

Upvotes: 9

Related Questions