使用std :: sort排序2d数组(基于列) [英] Sorting 2d Arrays using std::sort (column based)

问题描述

我正在运行一个测试，该测试显示了按列对2d数组进行排序的好处，方法是将数据提取到单个数组中并对该数组进行排序，然后将其复制回该列.我想将std :: sort作为每次运行的排序算法.我试图弄清楚如何先进行循环，然后再进行2D阵列的复制.输入/输出的一个例子就是这个.

I'm running a test showing the benefits of sorting a 2d array, by columns, by pulling the data off into an individual array and sorting that array, then copying it back to the column. I'm wanting to run std::sort as a the sorting algorithm for every run. I'm trying to figure out how to run the loop in place first, before moving into the copying on and off the 2D array. An example of the input / output would be this.

#include <iostream>
#include <algorithm>

int main() {
    int input[][5] =  { { 13, 27, 4 , 1 , 11 },
                        { 11, 19, 2 , 37, 1  },
                        { 32, 64, 11, 22, 41 },
                        { 71, 13, 27, -8, -2 },
                        { 0 , -9, 11, 99, 13 } };

    // std::sort something here.

    int output[][5] = { { 0 , -9, 2 , -8, -2 },
                        { 11, 13, 4 , 1 , 1  },
                        { 13, 19, 11, 22, 11 },
                        { 32, 27, 11, 37, 13 },
                        { 71, 64, 27, 99, 41 } };                      
    return 0;
}

感谢您的帮助.

推荐答案

您可以编写自己的迭代器，例如:

You may write your own iterator, something like:

#include <iterator>

template<typename Container>
class column_iterator : public std::iterator<std::random_access_iterator_tag,
                                            typename std::decay<decltype(std::declval<Container>()[0][0])>::type>
{
    typedef typename Container::iterator iterator;
    typedef typename std::decay<decltype(std::declval<Container>()[0][0])>::type type;
public:

    column_iterator(iterator it, int n) : it(it), n(n) {}

    column_iterator& operator++() {++it; return *this;}
    column_iterator& operator++(int) { auto res(*this); ++*this; return res;}
    column_iterator& operator +=(std::ptrdiff_t offset) { it += offset; return *this;}
    column_iterator operator +(std::ptrdiff_t offset) const { auto res(*this); res += offset; return res;}

    column_iterator& operator--() {--it; return *this;}
    column_iterator& operator--(int) { auto res(*this); --*this; return res;}
    column_iterator& operator -=(std::ptrdiff_t offset) { it -= offset; return *this;}
    column_iterator operator -(std::ptrdiff_t offset) const { auto res(*this); res -= offset; return res;}

    type& operator*() { return (*it)[n];}
    type* operator->() { return &(it)[n];}

    bool operator == (const column_iterator& rhs) const { return it == rhs.it && n == rhs.n; }
    bool operator != (const column_iterator& rhs) const { return !(*this == rhs); }
    bool operator < (const column_iterator& rhs) const { return it < rhs.it; }

    std::ptrdiff_t operator -(const column_iterator& rhs) const { return it - rhs.it; }

private:
    iterator it;
    int n;
};

template<typename Container>
column_iterator<Container> begin(Container& cont, int n)
{
    return column_iterator<Container>(cont.begin(), n);
}

template<typename Container>
column_iterator<Container> end(Container& cont, int n)
{
    return column_iterator<Container>(cont.end(), n);
}

现在，让我们对其进行测试:

Now, let's test it:

#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
#include <cassert>

void display(const std::vector<std::array<int, 5>>& v)
{
    for (auto rows : v) {
        for (auto elem : rows) {
            std::cout << elem << " ";
        }
        std::cout << std::endl;
    }
}

int main() {
    std::vector<std::array<int, 5>> input {
                        {{ 13, 27, 4 , 1 , 11 }},
                        {{ 11, 19, 2 , 37, 1  }},
                        {{ 32, 64, 11, 22, 41 }},
                        {{ 71, 13, 27, -8, -2 }},
                        {{ 0 , -9, 11, 99, 13 }} };

    for (int i = 0; i != 5; ++i) {
        std::sort(begin(input, i), end(input, i));
    }

    display(input);

    const std::vector<std::array<int, 5>> output {
                        {{ 0 , -9, 2 , -8, -2 }},
                        {{ 11, 13, 4 , 1 , 1  }},
                        {{ 13, 19, 11, 22, 11 }},
                        {{ 32, 27, 11, 37, 13 }},
                        {{ 71, 64, 27, 99, 41 }} };

    assert(input == output);
    return 0;
}

这篇关于使用std :: sort排序2d数组(基于列)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！