使用排序函数和递归比较器对提升的 multi_array 进行排序
Sorting boost's multi_array using sort function and a recursive comparator
我从事大数据和 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 multi_array.
进行排序
问题。
谁能告诉我用于 boost multi_array 的递归比较器的确切工作语法来对 multi_array 进行排序？代码不得使用依赖于特定编译器/操作系统的 API。假设 multi_array 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) 比如说，我们对所有维度的 multi_array A 进行排序。我们想对 multi_array B 应用相同的交换/交换/转换。我们可以用你给出的想法来做到这一点吗？
我知道我们可以通过编写一个单独的自定义排序器来解决这个问题（当我们交换时，我们可以交换 A 和 B 中的组件）。但是我很好奇这个问题是否可以用比较器的概念来解决，因为当我们用它来对 A 进行排序时，比较器对 multi_array B 一无所知。如何解决这个问题？
(2)my_comp中有几个重载函数真的有必要吗？难道我们不能为此目的拥有一个完全通用的功能吗？ （抱歉，我是 multi_array、sub_array 概念的新手）。
你不仅需要一个比较器，你还需要另一个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 ;
我从事大数据和 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 multi_array.
进行排序问题。
谁能告诉我用于 boost multi_array 的递归比较器的确切工作语法来对 multi_array 进行排序？代码不得使用依赖于特定编译器/操作系统的 API。假设 multi_array 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) 比如说，我们对所有维度的 multi_array A 进行排序。我们想对 multi_array B 应用相同的交换/交换/转换。我们可以用你给出的想法来做到这一点吗？
我知道我们可以通过编写一个单独的自定义排序器来解决这个问题（当我们交换时，我们可以交换 A 和 B 中的组件）。但是我很好奇这个问题是否可以用比较器的概念来解决，因为当我们用它来对 A 进行排序时，比较器对 multi_array B 一无所知。如何解决这个问题？
(2)my_comp中有几个重载函数真的有必要吗？难道我们不能为此目的拥有一个完全通用的功能吗？ （抱歉，我是 multi_array、sub_array 概念的新手）。
你不仅需要一个比较器，你还需要另一个concepts required for std::sort to work。具体来说：
RandomItmust meet the requirements ofValueSwappableandRandomAccessIterator.
因此，我破解了一个通用的 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 ;