C++ sort table by column while preserving row contents

user_1414496 0
Viewed 147

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:

2 8 1 4
3 7 6 7
3 3 4 9
8 6 3 4
7 1 5 7

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

2 8 1 4
8 6 3 4
3 3 4 9
7 1 5 7
3 7 6 7

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.

c++20 sorting c++
5 Answers

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

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

user_116387180

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.

user_22886590

C++20 way:

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

Live demo

user_13874380

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:

2 8 1 4 
8 6 3 4 
3 3 4 9 
7 1 5 7 
3 7 6 7

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

user_31333160
Related