https://sintheta.nexus/blog/feed.xml

C++'s sort()

2024-06-09

Just some exploratory fun with C++'s sort() function (from <algorithm>) and loved what I ended up w/. (Ab-)Using templates and operator overloading along the way for good measure.

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

#include <fmt/format.h>

using namespace std;

template <typename Container>
void print_container_values(const Container& container)
{
    for (auto it = begin(container); it != end(container); ++it)
    {
        cout << *it << ' ';
    }
    cout << '\n';
}

template <typename T>
void print_pair_vector(const vector<pair<T, T>>& v)
{
    for (auto e : v)
    {
        cout << fmt::format("({}, {}) ", e.first, e.second);
    }
    cout << '\n';
}

struct Point
{
    int x, y;

    /* operator instance method should return 
     *   true if element smaller
     *   false otherwise
     */
    bool operator<(const Point &p)
    { 
        return x < p.x; 
    }
    /* this is simply C++ operator overloading 
     * defining < allows for sorting, comparison
     * (and other operations relying on ordering semantics)
     */
};

void print_point_vector(const vector<Point> &vp)
{
    for (auto p : vp)
    {
        cout << fmt::format("({}, {}) ", p.x, p.y);
    }
    cout << '\n';
}


int main()
{
    // vector sort

    vector<int> v = {0, 5, 2, 6, 7, 1, 3, 7, 6, 8, 5, 9, 8, 7, 2};
    sort(v.begin(), v.end());
    print_container_values(v);

    sort(v.rbegin(), v.rend());
    print_container_values(v);

    // array sort

    int a[15] = {0, 5, 2, 6, 7, 1, 3, 7, 6, 8, 5, 9, 8, 7, 2};
    sort(a,a+15);
    print_container_values(a);

    // string sort

    string s = "YQHAGDFVznmjyuq";
    sort(s.begin(), s.end());
    print_container_values(s);
    sort(s.rbegin(), s.rend());
    print_container_values(s);

    // pair (tuples is same in regards to sorting)

    vector<pair<int, int>> vt = {{4, 3}, {3, 4}, {0, 9}, {1, -3}};

    sort(vt.begin(), vt.end());
    print_pair_vector(vt);
    sort(vt.rbegin(), vt.rend());
    print_pair_vector(vt);

    // custom struct (see Point strcut for how to implement ordering)

    vector<Point> vp = {{5, 7}, {4, 9}, {0, 4}, {6, 3}, {3, 2}};

    sort(vp.begin(), vp.end());
    print_point_vector(vp);
    sort(vp.rbegin(), vp.rend());
    print_point_vector(vp);

    // use a custom comparison function

    auto compare = [](string a, string b) -> bool
    {
        // sort alphabetically if same length (secondary sorting)
        if (a.size() == b.size()) return a < b;
        // sort by length otherwise (primary sorting)
        else return a.size() < b.size();
    };

    vector<string> vs = {"BbC", "AaA", "Z", "EE", "AbAAA"};
    sort(vs.begin(), vs.end(), compare);
    print_container_values(vs);
    sort(vs.rbegin(), vs.rend(), compare);
    print_container_values(vs);
}

Output

0 1 2 2 3 5 5 6 6 7 7 7 8 8 9
9 8 8 7 7 7 6 6 5 5 3 2 2 1 0
0 1 2 2 3 5 5 6 6 7 7 7 8 8 9
A D F G H Q V Y j m n q u y z
z y u q n m j Y V Q H G F D A
(0, 9) (1, -3) (3, 4) (4, 3)
(4, 3) (3, 4) (1, -3) (0, 9)
(0, 4) (3, 2) (4, 9) (5, 7) (6, 3)
(6, 3) (5, 7) (4, 9) (3, 2) (0, 4)
Z EE AaA BbC AbAAA
AbAAA BbC AaA EE Z