C++ Sort vector by index

Question

I need to sort a std::vector by index. Let me explain it with an example:

Imagine I have a std::vector of 12 positions (but can be 18 for example) filled with some values (it doesn't have to be sorted):

Vector Index:    0    1     2     3     4     5     6     7     8     9     10    11  
Vector Values:   3    0     2     3     2     0     1     2     2     4     5     3

I want to sort it every 3 index. This means: the first 3 [0-2] stay, then I need to have [6-8] and then the others. So it will end up like this (new index 3 has the value of previous idx 6):

Vector Index:    0    1     2     3     4     5     6     7     8     9     10    11
Vector Values:   3    0     2     1     2     2     3     2     0     4      5    3

I'm trying to make it in one line using std::sort + lambda but I can't get it. Also discovered the std::partition() function and tried to use it but the result was really bad hehe

Found also this similar question which orders by odd and even index but can't figure out how to make it in my case or even if it is possible: Sort vector by even and odd index

Thank you so much!

Note 0: No, my vector is not always sorted. It was just an example. I've changed the values

Note 1: I know it sound strange... think it like hte vecotr positions are like: yes yes yes no no no yes yes yes no no no yes yes yes... so the 'yes' positions will go in the same order but before the 'no' positions

Note 2: If there isn't a way with lambda then I thought making it with a loop and auxiliar vars but it's more ugly I think.

Note 3: Another example:

Vector Index:   0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  
Vector Values:  3  0  2  3  2  0  1  2  2  4   5   3   2   3   0   0   2   1

Sorted Values:  3  0  2  1  2  2  2  3  0  3   2   0   4   5   3   0   2   1

The final Vector Values is sorted (in term of old index): 0 1 2 6 7 8 12 13 14 3 4 5 9 10 11 15 16 17

You can imagine those index in 2 colums, so I want first the Left ones and then the Right one:

  0 1 2      3 4 5
  6 7 8     9 10 11
 12 13 14   15 16 17

Answer 1

With the range-v3 library, you can write this quite conveniently, and it's very readable. Assuming your original vector is called input:

namespace rs = ranges;
namespace rv = ranges::views;

// input [3, 0, 2, 3, 2, 0, 1, 2, 2, 4, 5, 3, 2, 3, 0, 0, 2, 1]

auto by_3s = input | rv::chunk(3); // [[3, 0, 2], [3, 2, 0], [1, 2, 2], [4, 5, 3], [2, 3, 0], [0, 2, 1]]

auto result = rv::concat(by_3s | rv::stride(2),               // [[3, 0, 2],  [1, 2, 2], [2, 3, 0]]
                         by_3s | rv::drop(1) | rv::stride(2)) // [[3, 2, 0],  [4, 5, 3], [0, 2, 1]]
              | rv::join
              | rs::to<std::vector<int>>;  // [3, 0, 2, 1, 2, 2, 2, 3, 0, 3, 2, 0, 4, 5, 3, 0, 2, 1]

Here's a demo.

Answer 2

You don't want std::sort, you want std::rotate.

    std::vector<int> v = {20, 21, 22, 23, 24, 25,
                          26, 27, 28, 29, 30, 31};
    auto b = std::next(std::begin(v), 3); // skip first three elements
    auto const re = std::end(v);  // keep track of the actual end
    auto e = std::next(b, 6);  // the end of our current block
    while(e < re) {
        auto mid = std::next(b, 3);
        std::rotate(b, mid, e);
        b = e;
        std::advance(e, 6);
    }
    // print the results
    std::copy(std::begin(v), std::end(v), std::ostream_iterator<int>(std::cout, " "));

This code assumes you always do two groups of 3 for each rotation, but you could obviously work with whichever arbitrary ranges you wanted.

The output looks like what you'd want:

20 21 22 26 27 28 23 24 25 29 30 31

Update: @Blastfurnace pointed out that std::swap_ranges would work as well. The rotate call can be replaced with the following line:

std::swap_ranges(b, mid, mid);  // passing mid twice on purpose