c++ - sorting table in place using stl sort -

c++ - sorting table in place using stl sort -

i have huge table (about 50gb) in (i,j,k) format (from sparse matrix) stored

uint32_t * idx1, * idx2; float * vals; uint32_t tablesize;

and i'd sort in place given comparing function that's function of idx1 , idx2. can done using std::sort?

specifically, each nonzero entry (i,j) value v in sparse matrix stored placing in idx1, j in idx2, , v in corresponding entry in vals. i'd sort these entries according (i1, j1, v1) <= (i2, j2, v2) if

(i1 < i2) || (i1==i2 && j1 <= j2)

the examples i've been able scrounge of using std::sort on nonstandard datatypes assume each item beingness compared single instance of class; here each item represented 3 values in different arrays.

if have maintain using existing info structure, std::tuple of 3 std::vectors, using boost::zip_iterator seem way go. zip_iterator treats 3 iterators (two indices , 1 value) single tuple, , can utilize custom comparing function object sort info in-place. alas, boost::zip_iterator can't used std::sort, explained in this q&a, because can't written into.

this means have write own zip_iterator class can used std::sort. note not trivial exercise, see this q&a and/or paper.

it lot easier sort std::vector of std::tuple. effort below uses std::tuple of 2 indices , value, , stores entries std::vector. sorting, utilize c++14 generic lambda forwards 2 indices smaller tuple , compares lexicographically (i.e. first on row-index, on column-index) using library operator< of std::tuple.

#include <algorithm> #include <iostream> #include <tuple> #include <vector> using index = uint32_t; using value = float; using sparse_entry = std::tuple<index, index, value>; using sparse_matrix = std::vector<sparse_entry>; int main() { // sparse 3x3 matrix auto m = sparse_matrix { std::make_tuple( 1, 1, -2.2), std::make_tuple( 1, 0, 42 ), std::make_tuple( 0, 2, 3.4), std::make_tuple( 0, 1, 1.7) }; // sort row-index, column-index std::sort(begin(m), end(m), [](auto const& l, auto const& r) { homecoming std::forward_as_tuple(std::get<0>(l), std::get<1>(l)) < std::forward_as_tuple(std::get<0>(r), std::get<1>(r)) ; }); (auto const& elem : m) std::cout << "{ " << std::get<0>(elem) << ", " << std::get<1>(elem) << ", " << std::get<2>(elem) << "}, \n"; }

live example.

if application can utilize transformed info layout (and there maybe cache-performance reasons why can't), above code sorting want it.

note: @casey mentions, can utilize std::tie instead of std::forward_as_tuple, can bite when alter sparse_entry full-fledged user-defined class getters returning by-value.

c++ algorithm sorting stl