C sort table by column while preserving row contents-CodePudding

Given a row-major table of type std::vector<std::vector<T>> (where T is a less-comparable type like int or std::string), I'd like to sort the table by a specific column while preserving the row contents (i.e. a row can only be moved as a whole, not the individual cells).

For example, given this table:

Sorting by the 3rd column (index 2), the desired result would be:

What is the STL way of achieving this?

One solution I can think of is copying the column that should be sorted into an associative container (for example std::unordered_map<T, std::size_t> where the key is the cell value and the value is the row index), then sorting the map by key (using std::sort()), extracting the resulting row index order and using that to re-order the rows in the original table.

However, this solution seems non-elegant and rather verbose when writing it as actual code.

What are possible, "nice" solutions to implement this?

Note: The table type of std::vector<std::vector<T>> is a given and cannot be changed/modified.

CodePudding user response：

Use a comparator that compare the element to compare.

std::vector<std::vector<T>> vec;
// add elements to vec
int idx = 2;
std::sort(vec.begin(), vec.end(), [idx](const std::vector<T>& a, const std::vector<T>& b) {
    return a.at(idx) < b.at(idx);
});

Full working example:

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

typedef int T;

int main() {
    std::vector<std::vector<T>> vec = {
        {2, 8, 1, 4},
        {3, 7, 6, 7},
        {3, 3, 4, 9},
        {8, 6, 3, 4},
        {7, 1, 5, 7}
    };
    int idx = 2;
    std::sort(vec.begin(), vec.end(), [idx](const std::vector<T>& a, const std::vector<T>& b) {
        return a.at(idx) < b.at(idx);
    });
    for (size_t i = 0; i < vec.size(); i  ) {
        for (size_t j = 0; j < vec[i].size(); j  ) {
            std::cout << vec[i][j] << (j   1 < vec[i].size() ? ' ' : '\n');
        }
    }
    return 0;
}

CodePudding user response：

You can do this by using a custom projection function for std::ranges::sort.

#include <algorithm>
#include <vector>

int main() {
  std::vector<std::vector<int>> v{
    {2, 8, 1, 4},
    {3, 7, 6, 7},
    {3, 3, 4, 9},
    {8, 6, 3, 4},
    {7, 1, 5, 7}
  };
  
  int col = 2;
  std::ranges::sort(
    v, {}, [&col](auto& x) { return x[col]; }
  );
}

Demo

CodePudding user response：

std::sort can optionally take a comparator argument.

comparison function object ... which returns true if the first argument is less than (i.e. is ordered before) the second.

The signature of the comparison function should be equivalent to the following:
bool cmp(const Type1 &a, const Type2 &b); 

So if you've got a std::vector<std::vector<T>> called vec (and assuming the type T is orderable by the < operator) and we want to sort based on the third column, we can write

std::sort(
  std::begin(vec),
  std::end(vec),
  [](const std::vector<T>& a, const std::vector<T>& b) { return a[2] < b[2]; }
);

If you want to change the column, simply change the 2. It can also be a variable provided that you capture that variable in the lambda.

CodePudding user response：

C 20 way:

std::ranges::sort(v, std::less<> {}, [](const auto& vv) { return vv[2]; });

Live demo

CodePudding user response：

There is another to sort the array, and that is to not sort the array.

Instead, sort an array of indices that point to the data item:

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

int main() {
    std::vector<std::vector<int>> vec = {
        {2, 8, 1, 4},
        {3, 7, 6, 7},
        {3, 3, 4, 9},
        {8, 6, 3, 4},
        {7, 1, 5, 7}
    };

    // index starts out as 0,1,2,3,4 
    std::vector<int> index(5);
    std::iota(index.begin(), index.end(), 0);

    // desired column
    int idx = 2;
    
    // sort index array based on vec's column value
    std::sort(index.begin(), index.end(), [&](int n1, int n2) 
              { return vec[n1][idx] < vec[n2][idx]; });

    // Output results using the index array
    for (size_t i = 0; i < vec.size();   i)
    {
        for (size_t j = 0; j < vec[index[i]].size();   j)
              std::cout << vec[index[i]][j] << " ";
       std::cout << "\n";
   }
}

Output:

One advantage to this is that you're not swapping entire vectors around during the sort. Instead, a simple int is swapped.