c++ - 使用STL按列对二维数组进行排序

Question

在this问题，我们看到一个很好的解释如何按每个 vector 的第一个元素对 vector 进行排序，以及第二个示例遍历每个 vector 并按其元素排序。

我知道数组对于 STL 的高级用户来说不是 C++ 的一等公民，但我喜欢数组(就像 Andrei Alexandrescu)。

那么，让我们考虑一下代码:

typedef int arr2D[3];

arr2D array2D[3] = { { 1, 4, 3 },
                     { 9, 2, 5 },
                     { 7, 6, 8 } };

std::sort(begin(array2D[2]), end(array2D[2]), greater<>());

这样做的结果是，按降序对 array2D 的最后 行 进行排序，如下所示:

1 4 3
9 2 5
8 7 6 <- last row by descending order

但是，我想要的是按降序排列 array2D 的最后一个列，如下所示:

1 4 8
9 2 5
7 6 3
    ^
    └--- last column by descending order

使用普通的数组(不是 vector )和std::sort，有人可以帮我吗？

谢谢

Answer 1

您可以编写自定义迭代器，在每一行上迭代特定列中的元素。像这样:

template<class Arr>
using sub_array_t = std::remove_pointer_t<std::decay_t<Arr>>;

template<class Arr>
using column_iterator_base = std::iterator<std::random_access_iterator_tag, sub_array_t<sub_array_t<Arr>>>;

template<std::size_t col_index, class Arr>
struct column_iterator : column_iterator_base<Arr>
{
    using parent = column_iterator_base<Arr>;
    using value_type = typename parent::value_type;
    using difference_type = typename parent::difference_type;
    using sub_array = sub_array_t<Arr>;

    Arr* arr;
    sub_array* row;

    column_iterator(Arr* arr)                 : arr(arr), row(*arr) {}
    column_iterator(Arr* arr, sub_array* row) : arr(arr), row(row) {}

    column_iterator begin() {return {arr};}
    column_iterator end()   {return {arr, std::end(*arr)};}

    column_iterator& operator+=(difference_type rhs) {row += rhs; return *this;}
    column_iterator& operator-=(difference_type rhs) {row -= rhs; return *this;}
    value_type& operator*() const {return (*row)[col_index];}
    value_type* operator->() const {return (*row) + col_index;}
    value_type& operator[](difference_type rhs) const {return row[rhs][col_index];}

    column_iterator& operator++() {++row; return *this;}
    column_iterator& operator--() {--row; return *this;}
    column_iterator operator++(int) {column_iterator tmp(arr, row); ++row; return tmp;}
    column_iterator operator--(int) {column_iterator tmp(arr, row); --row; return tmp;}

    difference_type operator-(const column_iterator& rhs) const {return row-rhs.row;}
    column_iterator operator+(difference_type rhs) const {return column_iterator(arr, row+rhs);}
    column_iterator operator-(difference_type rhs) const {return column_iterator(arr, row-rhs);}
    friend inline column_iterator operator+(difference_type lhs, const column_iterator& rhs)
    {return column_iterator(rhs.arr, lhs+rhs.row);}
    friend inline column_iterator operator-(difference_type lhs, const column_iterator& rhs)
    {return column_iterator(rhs.arr, lhs-rhs.row);}

    bool operator==(const column_iterator& rhs) const {return row == rhs.row;}
    bool operator!=(const column_iterator& rhs) const {return row != rhs.row;}
    bool operator> (const column_iterator& rhs) const {return row >  rhs.row;}
    bool operator< (const column_iterator& rhs) const {return row <  rhs.row;}
    bool operator>=(const column_iterator& rhs) const {return row >= rhs.row;}
    bool operator<=(const column_iterator& rhs) const {return row <= rhs.row;}
};

template<std::size_t col_index, class Arr>
auto make_column_iterator(Arr* arr)
{
    return column_iterator<col_index, Arr>(arr);
}


int main()
{
    // array2D = ...
    auto foo = make_column_iterator<1>(&array2D);
    std::sort(foo.begin(), foo.end());
}

自定义迭代器的许多样板文件可能可以通过使用来自 boost 的东西来避免。

注意:这是快速编写的，可能包含错误和不必要的复杂代码。