Sort a 3D std::vector based on values in a 1D std::vector

Question

I have a 3D vector :

vector<vector<vector<char>>> children;

this vector contains multiple 2D vectors and I would like to sort them based on a 1D vector:

vector<int> score;

each 2D vector in children is associated with a value in score. I have tried multiple similar questions but with no luck, so I was wondering how different the case of 3D vectors or is it even possible to sort with a vector of a different dimension in the first place?

I'm still fairly new to C++.

So you are trying to sort the scores, while maintaining the relative position inside the 3D vector? If so, then sort indices that point within the 3D vector, and not the actual vectors themselves. — PaulMcKenzie, Mar 08 '21 at 01:30
I'm not sure if I understood you correctly but I'm trying to use `children` later on and iterate through it, so i need the first child to be the one with the lowest score to save time. this is what i'm trying to do — kaMOON, Mar 08 '21 at 01:56
See my answer. Don't sort the vector, sort a vector of indices based on score and then use the indices to access the children vector. — PaulMcKenzie, Mar 08 '21 at 01:58
*I'm still fairly new to C++.* -- Also, this way of sorting is not related to C++ -- it is a general way of maintaining several related items that are not interconnected (like parallel arrays), or sorting large objects without having to actually copy the items around, or sorting the items is not a good option due to the complexity of the types being sorted (your case being an example). — PaulMcKenzie, Mar 08 '21 at 02:06

PaulMcKenzie · Accepted Answer · 2021-03-08T18:36:41.917

If your goal is to sort the scores and maintain the sorted scores with their relative position in the 3D vector, as the comment suggested and based on this answer, you can sort an array of indices that are based on the score criteria.

After sorting the indices, you use the indices to "point to" each sorted item in the 3D vector.

Here is an example:

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

int main()
{
    std::vector<std::vector<std::vector<char>>> children;
    std::vector<int> score;
    //...
    // Assume score and children have values
    //...
    // Sort the 3D vector based on the scores     
    // Set up the index vector
    std::vector<int> index(score.size());
    std::iota(index.begin(), index.end(), 0);
    //...
    // sort the indices based on the scores
    std::sort(index.begin(), index.end(), [&](int n1, int n2)
    { return score[n1] < score[n2]; });
    //...
    // Do something with the "sorted" 3D vector
    // The first sorted child is children[index[0]], the second is children[index[1]], etc.
}

Note that the linked answer has a thorough explanation of why and when this technique is used.

Cow Corporation · Answer 2 · 2021-03-08T01:27:53.900

Object-orientation may help you here.

As the first step in that direction, you could make the type of children to be this:

std::vector<std::pair<std::vector<std::vector<char>>, int>> children;

(The first component of the std::pair<> is your "2D data"; its second component is the scores.)

As for how to sort this, use the sorting capabilities that the C++ standard library already makes available to your outer std::vector<> (i.e., std::sort()). Instead of using its often-used std::less<> criteria, you would formulate something that knows the format of the std::pair<> and accesses the score portion of it.

Next, also consider encapsulating that entire std::pair<> as a user-defined type (i.e., define yourself a class which has both your "2D data" and the scores as data members), and use your newly-defined type in place of this std::pair<>.

The result is programming that is easier to maintain and work with (including doing manipulations like sorting):

std::vector<YourNewType> children;

Sort a 3D std::vector based on values in a 1D std::vector

2 Answers2