- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
class Solution {
public:
std::vector<std::vector<int>> diagonalSort(std::vector<std::vector<int>> & mat) {
if (!mat.size()) return mat;
const size_t rl = mat[0].size();
const size_t cl = mat.size();
sort(mat, rl, cl, 0, 0);
for (size_t i = 1; i < rl; ++i) {
sort(mat, rl, cl, 0, i);
}
for (size_t i = 1; i < cl; ++i) {
sort(mat, rl, cl, i, 0);
}
return mat;
}
private:
void sort(std::vector<std::vector<int>> & mat, size_t rl, size_t cl, size_t i, size_t j) {
const size_t len = std::min(rl - j, cl - i);
const size_t endj = j + len;
const size_t endi = i + len;
std::sort(diag_iter<false>{&mat, i, j}, diag_iter<false>{&mat, endi, endj});
}
template <bool isConst>
class diag_iter {
std::vector<std::vector<int>> *base;
size_t i, j;
using T = int;
public:
using iterator_category = std::forward_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = T;
using pointer = T*;
using reference = typename std::conditional<isConst, const T&, T&>::type;
diag_iter(std::vector<std::vector<int>> *base, size_t i, size_t j) : base(base), i(i), j(j) { }
diag_iter(const diag_iter&) = default;
diag_iter& operator=(const diag_iter&) = default;
~diag_iter() = default;
reference operator*() const { return (*base)[i][j]; }
diag_iter& operator++() { i++; j++; return *this; }
friend bool operator== (const diag_iter& a, const diag_iter& b) { return a.i == b.i && a.j == b.j; };
friend bool operator!= (const diag_iter& a, const diag_iter& b) { return !(a == b); };
pointer operator->() const { return &(this->operator*()); }
diag_iter operator++(int) { diag_iter tmp = *this; ++(*this); return tmp; }
diag_iter() = default;
diag_iter& operator--() { i--; j--; return *this; }
diag_iter operator--(int) { diag_iter tmp = *this; --(*this); return tmp; }
diag_iter& operator+=(difference_type n) { i += n; j += n; return *this; }
friend diag_iter operator+(diag_iter it, difference_type n) { return it += n; }
diag_iter& operator-=(difference_type n) { i -= n; j -= n; return *this; }
diag_iter operator-(difference_type n) const { return diag_iter(*this) -= n; }
friend difference_type operator-(const diag_iter& a, const diag_iter& b) { return (b.j * b.base->size() + b.i) - (a.j * a.base->size() + a.i); }
reference operator[](difference_type n) const { return *(*this + n); }
friend bool operator<(const diag_iter& a, const diag_iter& b) { return b - a > 0; }
friend bool operator>(const diag_iter& a, const diag_iter& b) { return b < a; }
friend bool operator>=(const diag_iter& a, const diag_iter& b) { return !(a < b); }
friend bool operator<=(const diag_iter& a, const diag_iter& b) { return !(a > b); }
};
};
Follow us!
Я не знал что так можно писать.
У себя компилировал с разной оптимизацией (gcc 10.2.1):
Результаты для матрицы 10 000 x 1000:
iter-O0 5606 ms
iter-O3 360 ms
vec-O0 267 ms
vec-O3 45 ms
reference operator*() const { return (*base)[i][j]; }
а вот это что за багор?
using reference = typename std::conditional<isConst, const T&, T&>::type;
https://en.cppreference.com/w/cpp/named_req/InputIterator
*i returns reference, convertible to value_type
Без этого не будет работать *foo = 42.
reference at (size_type n);
const_reference at (size_type n) const;
reference operator[](difference_type n) const { return *(*this + n); }
а не реф
Для конст_итераторов reference = const T&
Поскольку reference = typename std::conditional<isConst, const T&, T&>::type
https://coliru.stacked-crooked.com/a/4e5c0e21de62f769