0

有排序向量或动态分配数组的示例，但我找不到关于静态数组的任何帮助。假设我有一个数组

int array[10][10];

和比较功能，

bool compare(const int (*a)[10], const int (*b)[10]);

当我这样称呼它时，

std::sort(array, array + 10, compare);

我有编译错误：error: cannot convert 'int*' to 'const int (*)[10]' in argument passing

我尝试了很多方法，将数组转换(void**)为排序函数，但随后出现分段错误。我猜我的问题是使用数组作为函数参数，但我不知道如何使用这个 std::sort。否则，我将不得不编写自己的排序函数。

4

3 回答 3

2

当std::sort在类型元素的容器上调用时T，比较函数需要接收类型为Tor的参数const T&。在这种情况下，您有一个二维数组，因此元素的类型是一维数组int[10]。由于一维数组衰减为指针，compare可以是：

bool compare(int a[10], int b[10]);

或等效地：

bool compare(int *a, int *b);

这将解决您遇到的错误，但您的代码仍然无法工作：std::sort需要容器元素可分配（或在 C++11 中可移动），但数组不可分配。

您可以std::vector<std::vector<int> >按照人们的建议使用。请注意，您对性能问题的担心是错误的：即使可以对二维数组进行排序，也需要大量复制一维数组，这将花费很长时间。另一方面，交换向量是通过简单地交换更快的指针来完成的。一般来说，如果您没有先测试过性能，您不应该对性能做出假设。

于 2012-12-18T01:11:15.360 回答
1

我说，如果我们要使用 STL 和 C++ .. 让我们以现代风格编写它并真正使用 STL。

我尝试使用现代 c++11 解决这个问题：

#include <vector>
#include <iostream>
#include <algorithm>

typedef std::vector<int> ArrayInt;
typedef std::vector< std::vector<int> > ArrayData;

bool compare(const ArrayInt& a, const ArrayInt& b) {
    std::cout << &(a) << ' ' << &(b) << std::endl;
    int sumA = std::accumulate(a.begin(), a.end(), 0);
    int sumB = std::accumulate(b.begin(), b.end(), 0);
    return sumA < sumB;
}

int main(int argc, char** argv) {
    ArrayData array = {
        {1,2,4,0,3,7,6,8,3,3},
        {13,2,4,0,3,7,6,8,3,3},
        {10,2,4,0,3,7,6,8,3,3},
        {1,2,4,0,3,7,6,8,3,3},
        {16,2,4,0,3,7,6,8,3,3},
        {1,2,400,0,3,7,6,8,3,3},
        {1,2,4,0,3,7,6,8,3,3},
        {120,2,4,0,3,7,6,8,3,3},
        {1,2,4,0,3,7,6,8,3,3},
        {1,2,4,0,3,7,6,8,3,3}
    };
    std::sort(array.begin(), array.end(), compare);
    for (auto row : array) {
        for (int num : row)
            std::cout << num << ' ';
        std::cout << std::endl;
    }
}

它使用累积来对每个子数组求和，并对总和进行排序.. 它的效率非常低，因为它必须多次对同一行求和.. 但它只是为了展示自定义比较函数。

作为练习，我编写了这个版本，它使用异步将求和部分分配到任何可用的内核上，以便在排序之前进行求和。很抱歉，话题有点跑题了。我希望它对某些人仍然有用：

#include <vector>
#include <iostream>
#include <algorithm>
#include <future>

typedef std::vector<int> IntRow;
typedef std::pair<int, IntRow> DataRow;
typedef std::vector<DataRow> DataTable;

int main(int argc, char** argv) {
    // Holds the sum of each row, plus the data itself
    DataTable array = {
        {0, {1,2,4,0,3,7,6,8,3,3}},
        {0, {13,2,4,0,3,7,6,8,3,3}},
        {0, {10,2,4,0,3,7,6,8,3,3}},
        {0, {1,2,4,0,3,7,6,8,3,3}},
        {0, {16,2,4,0,3,7,6,8,3,3}},
        {0, {1,2,400,0,3,7,6,8,3,3}},
        {0, {1,2,4,0,3,7,6,8,3,3}},
        {0, {120,2,4,0,3,7,6,8,3,3}},
        {0, {1,2,4,0,3,7,6,8,3,3}},
        {0, {1,2,4,0,3,7,6,8,3,3}}
    };
    // Make use of multiple cores if it's efficient enough
    // get the sum of each data row
    std::vector<std::future<int>> sums(array.size());
    auto next = sums.begin();
    for (auto& row : array)
        *next++ = std::async([](const IntRow& row) { return std::accumulate(row.begin(), row.end(), 0); }, row.second);
    // Get the results
    auto nextRow = array.begin();
    for (auto& sum: sums)
        (*nextRow++).first = sum.get();
    // Sort it 
    std::sort(array.begin(), array.end(),
              [](const DataRow& a, const DataRow& b) { return a.first < b.first; });
    // Print it
    for (auto row : array) {
        for (int num : row.second)
            std::cout << num << ' ';
        std::cout << std::endl;
    }
}

它需要使用 pthread 库或类似库进行编译：

g++ -O6 sort.cpp --std=c++11 -g -lpthread

于 2012-12-18T00:32:47.233 回答
1

比较函数没有得到传递的元素的迭代器，而是解引用的迭代器，即值类型。因此，您的比较函数需要声明如下：

bool compare(int (&a0)[10], int (&a1)[10]);

您可以验证您是否可以使用数组迭代器实际调用它：

compare(*(std::begin(array) + 0), *(std::begin(array) + 1));

但是，这将无法对数组进行排序：内置数组不可复制分配。对静态大小的数组（外部维度灵活）进行排序的最简单方法是使用std::array<T, N>：

std::array<int, 10> array[10];
std::sort(std::begin(array), std::end(array));
于 2012-12-18T01:11:55.867 回答