How can I sort a Boost matrix by column?

Question

I have a 2d boost matrix (boost::numeric::ublas::matrix) of shape (n,m), with the first column being the timestamp. However, the data I'm getting is out of order. How can I sort it with respect to the first column, and what would be the most efficient way to do so? Speed is critical in this particular application.

Answer 1

As I commented ublas::matrix might not be the most natural choice for a task like this. Trying the naive approach using matrix_row and some range magic:

Live on Coliru

#define _SILENCE_ALL_CXX17_DEPRECATION_WARNINGS
#include <boost/numeric/ublas/io.hpp>
#include <boost/numeric/ublas/matrix.hpp>
#include <boost/numeric/ublas/matrix_proxy.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <iomanip>
#include <iostream>

using namespace boost::adaptors;
using Matrix = boost::numeric::ublas::matrix<float>;
using Row = boost::numeric::ublas::matrix_row<Matrix>;

static auto by_col0 = [](Row const& a, Row const& b) { return a(0) < b(0); };

int main()
{
  constexpr int nrows = 3, ncols = 4;
  Matrix m(nrows, ncols);
  for (unsigned i = 0; i < m.size1(); ++i)
    for (unsigned j = 0; j < m.size2(); ++j)
      m(i, j) = (10 - 3.f * i) + j;
  std::cout << "before: " << m << "\n";

  auto getrow = [&](int i) { return Row(m, i); };
  sort(boost::irange(nrows) | transformed(getrow), by_col0);

  std::cout << "after: " << m << "\n";
}

Does sadly confirm that the abstraction of the proxy doesn't hold:

before: [3,4]((10,11,12,13),(7,8,9,10),(4,5,6,7))
after: [3,4]((10,11,12,13),(10,11,12,13),(10,11,12,13))|

Oops.

Analysis?

I can't say I know what's wrong. std::sort is defined in terms of ValueSwappable which at first glance seems to work fine for matrix_row:

  auto r0 = Row(m, 0);
  auto r1 = Row(m, 1);
  using std::swap;
  swap(r0, r1);

Prints Live On Coliru

Maybe this starting point gives you something helpful. Since it's tricky like this, I'd highly consider using another data structure that is more conducive to your task (boost::multi_array[_ref] comes to mind).