Sorting in C++ of a sparse matrix in COO format

Question

I use sparse matrices in COO format in my program. The COO format uses 3 separate vectors to represent the matrix: rowindex, colindex and values. I need to sort the matrix first by rowindex and then by colindex. For example, if the vectors contain:

rowindex = [1 2 2 1 0 2 0 1 0 2 1 2]
colindex   = [7 7 2 1 3 9 8 6 6 0 3 4]
values      = [0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2]

(meaning that element [1,7] in the matrix has a value of 0.1, element [2,7] has a value of 0.2, element [2,2] has a value of 0.3, etc) the matrix after sorting should be:

rowindex = [0 0 0   1 1 1 1   2 2 2 2 2]
colindex  = [3 6 8   1 3 6 7   0 2 4 7 9] 
values     = [0.5 0.9 0.7 0.4 1.1 0.8 0.1 1.0 0.3 1.2 0.2 0.6]

I left some more spaces in the desired result to (hopefully) better show what I would like to achieve.

Can this be achieved somehow:

• Using the available sort functions in C++
• Without using additional memory (e.g. additional vectors), as the sparse matrices I use are huge and almost take up all memory
• Without having to resort to representing the matrix as an array of structs (where I know that the sort() function can be used).

Some answers I found about sorting multiple vectors, perform sorting regarding values of only one of the vectors. They do not have the requirement to sort elements that have the same value in the first vector, according to the second vector.

Answer 1

Generally it is possible to sort sparse matrices given in COO. But not with your constraints.

• Using the available sort functions in C++: Basically not possible, because existing sort functions from the std::libraries will only work on one range. Even with putting the other vectors in the predicates closure and come up with some complex lambda functions, or, outting everything in a Functor, it is not meaningful feasible.

• Additional space would be required, would make the solution feasable and easy to solve.

• same of constraint 3.

So, you need to make comprimises. Or use non standard C++ libraries.

Answer 2

After thinking more about the issue, I decided to follow a different path. Instead of reading the whole sparse matrix from the corresponding file and then sorting it, I now sort it while reading it. Each element read from the file is directly inserted into the correct position. For anyone interested, the part of the program that performs the sorting follows. Works correctly for the cases I have tested.

row = read value from file (zero-based indexing)
col = read value from file (zero-based indexing)
val = read value from file

/*
 * Identify the easy cases:
 *   - Insertion of the first element or
 *   - The new element must be inserted at the end of the vectors
 *
 * The second case could be handled by the 'else', but handling it this way
 * avoids more expensive searches by equal_range() and upper_bound().
 */
if ((rowindex.empty()) ||
     ((row >= rowindex[rowindex.size() - 1]) && (col >  colindex[colindex.size() - 1]))) {
        rowindex.push_back(row);
        colindex.push_back(col);
        values.push_back(val);
} else {
/*
 * Find the elements of the same row as the element being inserted into the matrix.
 *
 * If this is the first element in a specific row, the two iterators returned by equal_range()
 * point to the first element of the next larger row.
 *
 * If there are already other elements in the same row, the two iterators returned by equal_range()
 * point to the first element of the row and the first element of the next larger row.
 *
 * Using the iterators also calculate indices to the elements returned by equal_range().
 * These are used to index the corresponding elements in the other two vectors representing
 * the sparse matrix (colindex and values).
 */
    const auto p = equal_range(rowindex.begin(), rowindex.end(), row);
    const auto index_of_first = p.first  - rowindex.begin();
    const auto index_of_last  = p.second - rowindex.begin();

/*
 * Create iterators to point to the corresponding elements in colindex.
 */
    const auto first = next(colindex.begin(), index_of_first);
    const auto last  = next(colindex.begin(), index_of_last);

/*
 * Find the correct position where the new element must be inserted and perform the corresponding
 * insertions into the three vectors representing the sparse matrix.
 */
    auto col_pos_it = upper_bound(first, last, col);
    auto pos = col_pos_it - colindex.begin();
    colindex.insert(col_pos_it, col);

    auto row_pos_it = next(rowindex.begin(), pos);
    rowindex.insert(row_pos_it, row);

    auto val_pos_it = next(values.begin(), pos);
    values.insert(val_pos_it, value);
}

Answer 3

C++23 will add std::ranges::views::zip, so that you can write something like the following.

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

int main()
{
  std::vector colindex{ 1, 2, 2, 1, 0, 2, 0, 1, 0, 2, 1, 2 };
  std::vector rowindex{ 7, 7, 2, 1, 3, 9, 8, 6, 6, 0, 3, 4 };
  std::vector values{ 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0, 1.1, 1.2 };

  auto el_view{ std::views::zip(colindex, rowindex, values) };
  
  std::ranges::sort( el_view );

  for ( auto [r, c, v] : el_view )
    std::cout << r << ' ' << c << ' ' << v << '\n';
}

Live, here.