其实本质就是适配库函数sort
c++ 想要适配sort 需要
1、适配随机随机迭代器
2、提供begin(), end() 函数

下面的代码看起来很复杂， 其实主要是需要适配的接口稍多，核心代码很简单

 template<typename Derived>
    class EqualityComparable {
    public:
        friend bool operator==(Derived const& x1, Derived const& x2) {
            return !(x1 < x2) && !(x2 < x1);
        }

        friend bool operator!=(Derived const& x1, Derived const& x2) {
            return !(x1 == x2);
        }

        friend bool operator>(Derived const& x1, Derived const& x2) {
            return x2 < x1;
        }

        friend bool operator>=(Derived const& x1, Derived const& x2) {
            return !(x1 < x2);
        }

        friend bool operator<=(Derived const& x1, Derived const& x2) {
            return !(x1 > x2);
        }
    };


    class DiagIte : public EqualityComparable<DiagIte> {
    private:
        std::vector<std::vector<int>>& mat;
        int lx, ly;

    public:
        using difference_type = int;
        using value_type = int;
        using pointer = int*;
        using reference = int&;
        using iterator_category = std::random_access_iterator_tag;

        DiagIte(std::vector<std::vector<int>>& mat, int lx, int ly) : mat(mat), lx(lx), ly(ly) {}

        DiagIte(const DiagIte& other) : mat(other.mat), lx(other.lx), ly(other.ly) {}

        DiagIte& operator=(const DiagIte& other) {
            if (this != &other) {
                mat = other.mat;
                lx = other.lx;
                ly = other.ly;
            }
            return *this;
        }

        reference operator*() const {
            return mat[lx][ly];
        }

        DiagIte& operator++() {
            ++lx;
            ++ly;
            return *this;
        }

        DiagIte operator++(int) {
            DiagIte temp = *this;
            ++(*this);
            return temp;
        }

        DiagIte& operator--() {
            --lx;
            --ly;
            return *this;
        }

        DiagIte operator--(int) {
            DiagIte temp = *this;
            --(*this);
            return temp;
        }

        DiagIte& operator+=(difference_type n) {
            lx += n;
            ly += n;
            return *this;
        }

        DiagIte& operator-=(difference_type n) {
            lx -= n;
            ly -= n;
            return *this;
        }

        DiagIte operator+(difference_type n) const {
            DiagIte result = *this;
            result += n;
            return result;
        }

        DiagIte operator-(difference_type n) const {
            DiagIte result = *this;
            result -= n;
            return result;
        }

        difference_type operator-(const DiagIte& other) const {
            return (lx - other.lx);
        }

        reference operator[](difference_type n) const {
            return *(*this + n);
        }

        bool operator<(const DiagIte& other) const {
            return (lx < other.lx);
        }
    };

    class Diag {
    public:
        vector<vector<int>>& mat;
        int lx, ly;

        Diag(vector<vector<int>>& mat, int lx, int ly) : mat(mat), lx(lx), ly(ly) {}

        DiagIte begin() {
            return DiagIte(mat, lx, ly);
        }

        DiagIte end() {
            int w = std::min(mat.size() - lx, mat[0].size() - ly);
            return DiagIte(mat, lx + w, ly + w);
        }
    };

    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        for (int i = 0; i < mat.size(); i++) {
            Diag Di(mat, i, 0);
            std::sort(Di.begin(), Di.end());
        }
        for (int j = 1; j < mat[0].size(); j++) {
            Diag Di(mat, 0, j);
            std::sort(Di.begin(), Di.end());
        }
        return mat;
    }