Search code examples
c++stlstl-algorithm

Efficient way to reverse three consecutive subranges [A,B,C] -> [C,B,A]

I've got an array [A,B,C] consisting of three consecutive sub-arrays A, B and C. I'd like to reverse the larger array into [C,B,A]. My current attempt involves thee calls to std::rotate, as shown below. I wonder if there is a more straightforward/efficient way to achieve this, preferably using an std algorithm.

Step 1: "swap" sub-array B,C
[A,B,C] -> [A|B,C] -> [A,C,B]

Step 2: "swap" sub-array A,C
[A,C,B] -> [A,C|B] -> [C,A,B]

Step 3: "swap" sub-array A,B
[C,A,B] -> [C|A,B] -> [C,B,A]

Edit

For example given the array [1,2,3|4,5,6|7,8,9] I would like to "reverse" it into [7,8,9|4,5,6|1,2,3]

Sample implementation. Please note that the sizes of the "ranges" are merely illustrative.

Solution

  • Reverse the whole array then reverse each subarray.

    [1,2,3|4,5,6|7,8,9]
[9,8,7|6,5,4|3,2,1]
[7,8,9|4,5,6|1,2,3]

    This will take two linear passes and is extremely CPU cache friendly.