How can I sort a vector based on sort of another vector?

Question

I have a four vectors that I want to sort in relation to each other.

vector<string> color;
vector<string> shape;
vector<int> size;

Each vector is the same size each vector element is tied to each other such that it forms a row

{color[0], shape[0], size[0]}
{color[1], shape[1], size[1]}
{color[2], shape[2], size[2]}, etc

So what I am trying to do is sort the color vector by color and sort the other two vectors based on the rearranged color vector. Then within every group of colors (i.e red) I want to sort by shape and rearrange the size vector based on that sort. And then finally I want to sort the size vector within each group of color and shape. I think I know how to do it but it feels very very messy and difficult to conceptualize/read (I'm still new to C++). Is there an easy way to accomplish something like this?

For example I want to do something like this:

Blue    Circle      1   ->    Red   Triangle    1           
Red     Triangle    1   ->    Red   Triangle    2
Blue    Circle      3   ->    Red   Triangle    3
Red     Triangle    3   ->    Red   Circle      1
Red     Circle      2   ->    Red   Circle      2
Blue    Triangle    1   ->    Red   Circle      3
Red     Circle      1   ->    Blue  Triangle    1
Blue    Triangle    3   ->    Blue  Triangle    2
Red     Circle      3   ->    Blue  Triangle    3
Blue    Circle      2   ->    Blue  Circle      1
Blue    Triangle    2   ->    Blue  Circle      2
Red     Triangle    2   ->    Blue  Circle      3

Answer 1

First solution

One way to solve the problem is to not sort the vectors, but instead to produce a new vector of indexes, let's name it I, such that the items at position j in the sorted vectors are at position I[j] in the current unsorted vectors.

It is easy to produce this indexing vector by initializing it with the increasing values 0 .. n-1 and sorting the vector with a custom comparison function:

std::vector<int> I(N);
std::iota(begin(I), end(I), 0);
std::sort(begin(I), end(I), [&](int ia, int ib) { return color[ia] < color[ib]; });
// this is a simplified comparison function to not clutter the code

Now if you want to access the shape of the 3rd element in the sequence sorted by color you write:

auto shape3 = shape[I[3]];

Second solution

The first solution works, but it may not be to your liking for many reasons. Maybe you don't like the fact that it randomizes memory accesses (and the associated penalty) when you walk the items in ascending order. Or maybe you really need to sort the vectors because you have to pass them to another component.

In that case, you can still use the first method as a first step, and then reorder the vectors based on the indexes just computed. Here is an example of such reordering for the shape vector:

std::vector<std::string> tmp_shape;
tmp_shape.reserve(N);
for(int j=0; j<N; ++j)
    tmp_shape.emplace_back(std::move(shape[I[j]]));
shape.swap(tmp_shape);

Obviously you need to do that for the three vectors to maintain their relationship.

Answer 2

You should make a single Shape class or struct, and then make a std::vector<Shape>, which you can then sort on color, primarily, followed by your other parameters. You define an overloaded operator< so that the std::sort function will find it.

It would look like this:

#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>

struct Shape
{
    std::string color_;
    std::string shape_;
    int size_;

    Shape(const std::string& color, const std::string& shape, int size)
        : color_(color)
        , shape_(shape)
        , size_(size)
    {}

    // returns true if this shape is less than the other shape
    // "less than" is up to us: here we give priority to color, then shape, then size
    bool operator<(const Shape& other) const
    {
        // std::tie makes lexicographical compare of complex structures easy!
        return (std::tie(color_, shape_, size_) <
                std::tie(other.color_, other.shape_, other.size_));
    }

    friend std::ostream& operator<<(std::ostream& os, const std::vector<Shape>& shapes)
    {
        for (auto& shape : shapes)
        {
            os << shape.color_ << " " << shape.shape_ << " " << shape.size_ << "\n";
        }

        return os;
    }
};

int main(int argc, char** argv)
{
    std::vector<Shape> shapes;

    shapes.emplace_back("Blue", "Circle", 1);
    shapes.emplace_back("Red", "Triangle", 1);
    shapes.emplace_back("Blue", "Circle", 3);
    shapes.emplace_back("Red", "Triangle", 3);
    shapes.emplace_back("Red", "Circle", 2);
    shapes.emplace_back("Blue", "Triangle", 1);
    shapes.emplace_back("Red", "Circle", 1);
    shapes.emplace_back("Blue", "Triangle", 3);
    shapes.emplace_back("Red", "Circle", 3);
    shapes.emplace_back("Blue", "Circle", 2);
    shapes.emplace_back("Blue", "Triangle", 2);
    shapes.emplace_back("Red", "Triangle", 2);

    std::cout << "Pre sorted vector:\n";
    std::cout << shapes;

    // std::sort by default will use the operator< for the types
    // being sorted, if it's available
    std::sort(shapes.begin(), shapes.end());

    std::cout << "\nPost sorted vector:\n";
    std::cout << shapes;
}

This gives the output:

Pre sorted vector:
Blue Circle 1
Red Triangle 1
Blue Circle 3
Red Triangle 3
Red Circle 2
Blue Triangle 1
Red Circle 1
Blue Triangle 3
Red Circle 3
Blue Circle 2
Blue Triangle 2
Red Triangle 2

Post sorted vector:
Blue Circle 1
Blue Circle 2
Blue Circle 3
Blue Triangle 1
Blue Triangle 2
Blue Triangle 3
Red Circle 1
Red Circle 2
Red Circle 3
Red Triangle 1
Red Triangle 2
Red Triangle 3

Answer 3

Like John pointed out, you should make a single struct, and then make a std::vector, which you can then sort on color. Here is a solution:

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

struct MyStruct
{
    std::string color;
    std::string shape;
    int size;

    MyStruct(std::string co, std::string sh, int si): 
        color{co}, shape{sh}, size{si} {};
};

bool MyComp(MyStruct a,MyStruct b)
{ 
    auto f = [](unsigned char c){ return std::tolower(c);};
    std::transform(a.color.begin(), a.color.end(), a.color.begin(),f);
    std::transform(b.color.begin(), b.color.end(), b.color.begin(),f);

    return (a.color < b.color); 
}

int main() {

    std::vector<MyStruct> MyVec;

    MyVec.emplace_back("Blue","Circle",1); 
    MyVec.emplace_back("Red","Triangle",1);  
    MyVec.emplace_back("Blue","Circle",3);
    MyVec.emplace_back("Red","Triangle",3);   
    MyVec.emplace_back("Red","Circle",2);  
    MyVec.emplace_back("Blue","Triangle",1);   
    MyVec.emplace_back("Red","Circle",1);   
    MyVec.emplace_back("Blue","Triangle",3);   
    MyVec.emplace_back("Red","Circle",3);  
    MyVec.emplace_back("Blue","Circle",2);  
    MyVec.emplace_back("Blue","Triangle",2);   
    MyVec.emplace_back("Red","Triangle",2);

    std::sort(MyVec.begin(), MyVec.end(), MyComp);

    for(auto s : MyVec)
        std::cout << s.color << " " << s.shape  << " " << s.size << std::endl; 

    return 0;
}

You can run the code online to see the following output:

Blue Circle 1
Blue Circle 3
Blue Triangle 1
Blue Triangle 3
Blue Circle 2
Blue Triangle 2
Red Triangle 1
Red Triangle 3
Red Circle 2
Red Circle 1
Red Circle 3
Red Triangle 2