c++ - 使用排序函数和递归比较器对 boost 的 multi_array 进行排序

Question

我从事大数据和 C++ 编程工作。例如，我需要创建大小为 [7 x 128^3 x 5 x 5] 等的 4 维数组。我将不得不创建更多的数组作为不同属性的中间数据结构。研究了很多，最终还是选择了boost的multi_array来实现我的数据结构。我选择 multi_array 有两个原因:(1) 它处理数组索引越界等异常，这对我调试非常重要。(2) 它处理更高维度的数组(其他选项如STL的多维数组对于3维和更高维度的数组有很多问题)

---

问题示例。

如果我用一个例子来解释这个问题就变得容易了。比方说，我有以下 3-D 数组。

[(1,2,3), (4,5,6), (7,8,9)] 
[(1,2,3), (1,3,3), (4,1,1)]
[(8,9,9), (6,9,7), (17,2,3)]
[(1,2,3), (1,3,2), (2,8,1)]
[(1,2,3), (1,3,3), (4,2,1)]

我想以这样一种方式对这些行进行排序，即排序必须先基于 column_1，然后是 column_2，然后是 column_3。排序后我会有

[(1,2,3), (1,3,2), (2,8,1)]
[(1,2,3), (1,3,3), (4,1,1)]
[(1,2,3), (1,3,3), (4,2,1)]
[(1,2,3), (4,5,6), (7,8,9)]
[(8,9,9), (6,9,7), (17,2,3)]

您会看到 column_1 已排序。对于每两行具有相同的 column_1，则对 column_2 进行排序，依此类推。

---

我尝试过的。

我能够用普通的 3-D 数组解决这个问题，并编写一个递归比较器并调用库的排序函数(使用比较器)。但是，我改成boost的multi_array后，一直没能解决问题。我搜索了很多 boost 文档我找不到任何解决方案。我不知道如何编写递归比较器来对 boost multi_array 进行排序。

---

问题。

谁能告诉我用于 boost multi_array 的递归比较器的确切工作语法来对 multi_array 进行排序？代码不得使用依赖于特定编译器/操作系统的 API。假设多数组A的维度为n1 x n2 x ... x nd。

谢谢。

---

回复 Yakk。

递归比较器是这样的:

struct comparebyID
{
    bool operator()(celltuple const &t, celltuple const &u)
    {
        return comparator(0, t, u);
    }
    bool comparator(int i, celltuple const &t, celltuple const &u)
    {
        if (i == (levels - 1))
            return t.childIDs[i] < u.childIDs[i];

        if (t.childIDs[i] == u.childIDs[i])
            return comparator(i + 1, t, u);
        else
            return t.childIDs[i] < u.childIDs[i];
    }
};

使用递归比较器的排序函数是这样的:

sort(cellset, cellset + count, comparebyID());

多维数组是这样的:

struct celltuple
{
    cell c[MAX_SIZE];
    unsigned long long IDs[MAX_IDS];
    int childIDs[MAX_IDS];
    int prevChildIDs[MAX_IDS];
    unsigned long long prevIDs[MAX_IDS];
}cellset[MAX_CELLTUPLES];

我没有包括每个参数代表什么的许多其他细节，因为它变得困惑(因为它试图做许多其他事情)但核心思想如示例中所述。

我想做的是为 multi_array 编写一个递归比较器，如下定义。

boost::multi_array<int, 3> cell_tuple;

我不能像 compareByID 这样简单地编写比较器，因为当对象是 multi_array 时，我不知道如何将参数传递给比较器函数。

这有帮助吗？

---

回复sehe.

优秀的解决方案。万分感谢。看来你是使用boost和c++的天才。它完全奏效了。您用于交换和比较器功能的想法非常棒。我不知道这些函数调用(例如 lexicographical_compare() 等)甚至存在。非常感谢。

我有两个相关的问题:

(1) 例如，我们对所有维度的多数组 A 进行排序。我们想对 multi_array B 应用相同的交换/交换/转换。我们可以用你给出的想法来做到这一点吗？

我知道我们可以通过编写一个单独的自定义排序器来解决这个问题(当我们交换时，我们可以交换 A 和 B 中的组件)。但是我很好奇这个问题是否可以用比较器的概念来解决，因为当我们使用它来对 A 进行排序时，比较器对多数组 B 一无所知。如何解决这个问题？

(2) my_comp 中有几个重载函数真的有必要吗？难道我们不能为此目的拥有一个完全通用的功能吗？ (抱歉，我是 multi_array、sub_array 概念的新手)。

Answer 1

你不仅需要一个比较器，你还需要另一个concepts required for std::sort to work以及。具体来说:

• RandomIt must meet the requirements of ValueSwappable and RandomAccessIterator.

因此，我破解了一个通用的 swap 实现。注意它使用了实现细节:

namespace boost { namespace detail { namespace multi_array {
    template <typename T, size_t dims>
    static void swap(sub_array<T, dims> a, sub_array<T, dims> b) {
        using std::swap;
        for (auto ai = a.begin(), bi = b.begin(); ai != a.end() && bi != b.end(); ++ai, ++bi) {
            swap(*ai, *bi);
        }
    }
} } }

比较器可以同样简单明了，看起来像:

struct my_comp {
    template <typename T, size_t dims>
    bool operator()(sub_array<T, dims> const& a, sub_array<T, dims> const& b) const {
        return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(), *this);
    }

    // ... some technical overloads omitted

    template <typename T>
    bool operator()(T a, T b) const {
        return std::less<T>()(a,b);
    }
};

在所有情况下，我们只是遵从标准库算法来完成工作，递归传递 *this 作为比较器!

完整的现场演示: Live On Coliru

#include <boost/multi_array.hpp>
#include <iostream>

namespace ba = boost::multi_array_types;

using Arr = boost::multi_array<int, 3>;

static std::ostream& operator<<(std::ostream& os, Arr const& arr) {
    for(auto const& row : arr) {
        for (auto const& col : row) {
            for (auto const& cell : col) os << cell << " ";
            os << ";";
        }
        os << "\n";
    }
    return os;
}

struct my_comp {
    // short hand only:
    template <typename T, size_t dims> using sub_array = boost::detail::multi_array::sub_array<T, dims>;

    template <typename T, size_t dims>
    bool operator()(sub_array<T, dims> const& a, sub_array<T, dims> const& b) const {
        return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(), *this);
    }

    template <typename T, size_t dims>
    bool operator()(boost::multi_array<T, dims> const& a, sub_array<T, dims> const& b) const {
        return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(), *this);
    }

    template <typename T, size_t dims>
    bool operator()(sub_array<T, dims> const& a, boost::multi_array<T, dims> const& b) const {
        return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(), *this);
    }

    template <typename T>
    bool operator()(T a, T b) const {
        return std::less<T>()(a,b);
    }
};

namespace boost { namespace detail { namespace multi_array {
    template <typename T, size_t dims>
    static void swap(sub_array<T, dims> a, sub_array<T, dims> b) {
        using std::swap;
        for (auto ai = a.begin(), bi = b.begin(); ai != a.end() && bi != b.end(); ++ai, ++bi) {
            swap(*ai, *bi);
        }
    }
} } }

using boost::detail::multi_array::swap;

#include <boost/range/algorithm.hpp>
int main() {
    Arr arr(boost::extents[5][3][3]);

    auto initial = {
        1,2,3, 4,5,6, 7,8,9,
        1,2,3, 1,3,3, 4,1,1,
        8,9,9, 6,9,7, 17,2,3,
        1,2,3, 1,3,2, 2,8,1,
        1,2,3, 1,3,3, 4,2,1,
    };

    boost::copy(initial, arr.origin());
    std::cout << arr;

    std::sort(arr.begin(), arr.end(), my_comp{});
    std::cout << "After sort\n" << arr;
}

打印:

1 2 3 ;4 5 6 ;7 8 9 ;
1 2 3 ;1 3 3 ;4 1 1 ;
8 9 9 ;6 9 7 ;17 2 3 ;
1 2 3 ;1 3 2 ;2 8 1 ;
1 2 3 ;1 3 3 ;4 2 1 ;
After sort
1 2 3 ;1 3 2 ;2 8 1 ;
1 2 3 ;1 3 3 ;4 1 1 ;
1 2 3 ;1 3 3 ;4 2 1 ;
1 2 3 ;4 5 6 ;7 8 9 ;
8 9 9 ;6 9 7 ;17 2 3 ;