user7140484 user7140484 - 18 days ago 5
C++ Question

Sorting bidimensional arrays by column using STL

In this question, we see a good explanation how sort vectors by the first element of each vector and a second example going through each vector and sort by it's elements.


I know that arrays are not the first class citizens of C++ for power users of STL, but I like arrays (just like Andrei Alexandrescu).




So, lets consider the code:

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<>());


The result of this is, ordering the last row of array2D by descending order, like this:


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


However, what I want is ordering the last column of array2D by descending order, like this:


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


Using plain
array
s (not vectors) and
std::sort
, can someone help me ?

Thank you

Answer

You can write a custom iterator, that iterates the elements in specific column, over each row. Something like this:

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());
}

A lot of the boilerplate for a custom iterator can probably be avoided by using something from boost.

Note: This was written quickly, and may contain errors and unnecessarily convoluted code.

Comments