Sorting boost's multi_array using sort function and a recursive comparator

Question

I work on big data and program in c++. For example, I need to create 4-dimensional arrays of size [7 x 128^3 x 5 x 5] etc. I will have to create many more arrays as intermediate data structures for different properties. After researching a lot, I finally chose boost's multi_array to implement my data structures. I chose multi_array for two reasons: (1) It handles exceptions such as array index out of bound which is very important to me for debugging. (2) It handles arrays of higher dimensions (other options such as stl's multi dimensional arrays have lots of problems with arrays of 3 and higher dimensions)

---

Problem example.

It becomes easy if I explain the problem using an example. Say, I have the following 3-D array.

[(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)]

I want to sort these rows in such a way that the sorting must happen based on column_1, then column_2, and then column_3. After sorting I will have

[(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)]

You see that column_1 is sorted. For every two rows that have same column_1, then column_2 is sorted, and so on.

---

What I have tried.

I was able to solve this problem with ordinary 3-D array and writing a recursive comparator and calling the library's sort function (that uses the comparator). But, after I changed to boost's multi_array I have not been able to solve the problem. I searched a lot for boost documentation I could not find any solution. I do not know how to write a recursive comparator for sorting the boost multi_array.

---

Question.

Can someone give me the exact working syntax of the recursive comparator for boost multi_array to sort the multi_array? The code must not use APIs that depend on the specific compiler / operating system. Assume the dimensions of multi_array A as n1 x n2 x ... x nd.

Thanks.

---

Reply to Yakk.

recursive comparator is like this:

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 function that uses the recursive comparator is like this:

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

the multi-dimensional array is like this:

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];

I have not included many other details of what does each parameter represents because it gets messy (as it tries to do many other things) but the core idea is as explained in the example.

What I want to do is to write a recursive comparator for the multi_array as defined by the following.

boost::multi_array<int, 3> cell_tuple;

I cannot simply write the comparator like the compareByID as I do not how to pass arguments to comparator function when the object is a multi_array.

Does this help?

---

Reply to sehe.

Excellent solution. Thanks a ton. It seems that you are a genius in using boost and c++. It totally worked. The idea you have used for swap and comparator function is amazing. I had no idea that these function calls (such as lexicographical_compare() etc) even existed. Thank you so much.

I have two related questions:

(1) Say, we sort a multi_array A for all dimensions. We want to apply the identical swaps / exchanges / transformations to multi_array B. Can we do this with the idea you have given?

I understand that we can solve this problem by writing a separate custom sorter (when we swap, we can swap components both in A and B). But I am curious if this problem can be solved with the comparator concept because the comparator does not know anything about the multi_array B when we are using it to sort A. How to solve this problem?

(2) Is it really necessary that we have several overloaded functions in my_comp? Can't we have one totally generic function for that purpose? (Sorry, I am new to multi_array, sub_array concepts).

Answer 1

Not only do you need a comparator, but you need the other concepts required for std::sort to work as well. Specifically:

• RandomIt must meet the requirements of ValueSwappable and RandomAccessIterator.

Therefore, I hacked a generic swap implementation. Note it uses implementation details:

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

The comparator can be similarly straight-forward, and looks like:

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

In all cases we simply defer to a standard library algorithm to do the work, recursively passing *this as the comparator!

Full Live Demo: 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;
}

Printing:

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 ;