Reversing vector order

Question

I'm working on a vision sensor that provides depth data for each pixel through its API. The buffer is ordered row by row, left to right, and bottom to top, see below. The image has a resolution of width by height.

I need to reorder the depth data list for transformation purposes, taking into account the resolution. For example, if bottomLeftData = 1 2 3 4 5 6, I need to iterate in reverse to get topLeftData = 5 6 3 4 1 2. Note, this is not merely reversing per se. It involves two operations. For example, for width=2, I iterate bottomLeftData in reverse to extract 6 5 and reverse this order to get 5 6. I will continue all over bottomLeftData like this.

My solution is

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() 
{
    vector<double> a = {1,2,3,4,5,6};
    int w(2),h(3);
    
    for (int i=0; i < a.size(); ++i)
      cout << a[i] << ' ';
    cout << endl << endl;

    k=a.size();
    vector<double> c;
    for(int i=0; i < h; ++i){
        vector<double> b;
        for(int j=0; j < w; ++j)
            b.push_back(a[--k]);
      
        std::reverse(b.begin(), b.end());
        for (int h=0; h < b.size(); ++h)
            c.push_back(b[h]);
    }
        
    for (int i=0; i < c.size(); ++i)
      cout << c[i] << ' ';
    cout << endl << endl;
  
    
    return 0;
}

Are there better methods to accomplish this task? Note that the resolution can be large.

Answer 1

Actual problems with your code

• Your code does not compile, as k is not declared.

• std::size_t is probably a better type for array dimensions than int. This will also help you with a number of warnings. Make sure you're compiling with warnings turned on/up. To take this a step further, compile with warnings treated as errors, to force yourself to fix them.

Opportunities for improvement

• Variables are often best declared on individual lines. There's very little room for confusion in your specific program, but when we combine this with pointers, the syntax can be misleading. E.g. int* a, b; is equivalent to int *a; int b; rather than int *a; int *b;

• using namespace std; is strongly discouraged.

• Your first loop: for (int i=0; i < a.size(); ++i) std::cout << a[i] << ' '; is better written as a range-based for loop. for (const auto &x : a) std::cout << x << ' ';

• Your code would be improved by utilizing braces consistently. This can prevent common sources of confusion. Your use of indentation is good, though!

• On the subject of consistency, you should use whitespace consistently around operators. You may wish to employ an automatic formatting tool.

• std::endl does rather more than simply outputting a newline. It also flushes the output stream. Maybe you want to do this to prevent out of sync I/O, but that doesn't look like an issue. You would be better off simply pushing '\n' or "\n\n" to the output stream.

• main is a special case and returns 0 automatically on ending, making an explicit return 0; a bit extraneous.

• Your variable names aren't very meaningful. w is probably better as width, for instance.

• Use const or constexpr when you know variable will not change. This will let the compiler help you by causing errors if you make a mistake and change them.

A first revision

Taking some of these thoughts into consideration, we might have a program that looks like the following, and compiles without warnings.

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

int main()
{
    const std::vector<double> a {1,2,3,4,5,6};
    constexpr std::size_t w {2};
    constexpr std::size_t h {3};

    for (const auto &x : a) {
        std::cout << x << ' ';
    }
    std::cout << "\n\n";


    std::size_t k {a.size()};
    std::vector<double> c;
    for (std::size_t i {0}; i < h; ++i) {
        std::vector<double> b;
        for (std::size_t j {0}; j < w; ++j) {
            b.push_back(a[--k]);
        }

        std::reverse(b.begin(), b.end());
        for (const auto x : b) {
            c.push_back(x);
        }
    }

    for (const auto &x : c) {
        std::cout << x << ' ';
    }
    std::cout << "\n\n";
}

A second revision

But really we can streamline this with some math and a pair of loops which populate a new vector b. The intermediate vectors are gone, so there's no need for a vector c.

#include <iostream>
#include <vector>

int main()
{
    const std::vector<double> a {1,2,3,4,5,6};
    constexpr std::size_t w {2};
    constexpr std::size_t h {3};

    for (const auto &x : a) {
        std::cout << x << ' ';
    }
    std::cout << "\n\n";

    std::vector<double> b;

    for (std::size_t i {h}; i > 0; --i) {
        const std::size_t offset {(i-1) * w};
        for (std::size_t j {0}; j < w; ++j) {
            b.push_back(a[offset + j]);
        }
    }

    for (const auto &x : b) {
        std::cout << x << ' ';
    }

    std::cout << '\n';
}

The output:

1 2 3 4 5 6

5 6 3 4 1 2

Don't repeat yourself

You may also wish to factor out the printing of the vectors to avoid pointless repetition and make it possible to change your printing in one place.

#include <iostream>
#include <vector>

template <typename T>
void print_vector(const std::vector<T> &v) {
    for (const auto &x : v) {
        std::cout << x << ' ';
    }
    std::cout << '\n';
}

int main()
{
    const std::vector<double> a {1,2,3,4,5,6};
    constexpr std::size_t w {2};
    constexpr std::size_t h {3};

    print_vector(a);

    std::vector<double> b;

    for (std::size_t i {h}; i > 0; --i) {
        const std::size_t offset {(i-1) * w};
        for (std::size_t j {0}; j < w; ++j) {
            b.push_back(a[offset + j]);
        }
    }

    print_vector(b);
}

Answer 2

Is This an XY-Problem?

Frame challenge: You describe needing to iterate through the rows in reverse order, while keeping the columns of each row in the same order, as input to a transformation algorithm.

Can You Access the Data in the Correct Order?

If you have control over the transformation algorithm, you can instead access the elements in a different order, such as:

// Width w and total size n are already computed, w <= INT_MAX, and n <= PTRDIFF_MAX.
for (ptrdiff_t i = n - w; i >= 0; i -= w) { // i must be SIGNED and wide enough!
    for (int j = 0; j < w; ++j) { // j should have the same signedness as i.
        const auto pixel_ij = *(buffer + i + j);
        /* ... */

You could instead slice the array into rows with std::span or std::ranges::subrange as your slice type, and pass those slices to algorithms that use the range interface.

An alternative using ranges and adapters is to reverse a chunk view, as in Toby Speight’s excellent answer, but instead of collecting the data to a vector, flatten the view.

In a more complicated convolution, you might separately calculate the addresses of two input rows, counting down here and up elsewhere, possibly as array slices or std::span, then iterate over the elements of the two rows in parallel.

Can You Permute in Place?

You can apply the algorithm for reversing an array in place to an array of rows. That is, you can find the addresses of the rows starting from the top and counting down, and the addresses of the rows starting from the bottom and counting up, swap the two rows element-wise, and stop when the addresses meet in the middle.

Feedback on the Code as Written

Make The Permute Operation a Function

Not only is this better organization that putting everything in main, it lets you chain the returned vector, such as transform(permutePixelRows(getRawImage(camera))).

You might accept the input as a std::vector<double>&& that can be permuted in place, then return the permuted input vector (by move). Alternatively, it could accept an input range and an output range, and return the output range.

Optimizing with Vector

First, you want to avoid allocating a std::vector off the heap within each iteration of the loop, as in:

    for(int i=0; i < h; ++i){
        vector<double> b;

This slows the loop down immensely and inhibits vectorization. Since each row has the same width, if you need a temporary buffer to hold a row, you can allocate it once before the loop, and overwrite it on each iteration.

Consider taking the output buffer as a parameter (possibly std::span<double>, which can alias any array-like contiguous data structure, or you could make it a template for any output range that supports std::begin(dest) and std::end(dest)). This lets the caller fill any range of memory it owns.

If you stick with creating your own std::vector to hold the output data, it is faster than push_back to resize to the known final size, obtaining an initialized output buffer, and copy or move the input data to the correct offsets within the output buffer.

In 2025, inserting one element at a time at the end causes compilers to actually call the non-trivial push_back code each time, and copying to a pre-allocated output buffer does not. If you must build your output as you go, at least copy a row of data at a time to minimize the number of bounds checks. This is explicitly what Toby Speight’s excellent solution (which is very easy on the eyes) does.

However, you could also use the access pattern in the first code sample to fill an empty std::vector in order, which could give you simple code.

However you do, you probably want to call shrink_to_fit before you return, since you almost certainly will not be appending any more elements to the buffer.

Answer 3

Everything that Chris said, plus:

• Reserve vectors when we have a good idea how big they'll become:

    c.reserve(w * h);
  

• Know your standard algorithms and views:

  auto c = a
      | std::views::chunk(w)
      | std::views::reverse
      | std::views::join
      | std::ranges::to<std::vector>();
  

Answer 4

Let me reframe how you index into your image, and this whole problem will go away.

You define the image as:

vector<double> data = {1,2,3,4,5,6};
int width = 2;
int height = 3;

I suggest you also need the strides, how to increase or decrease the index into data to go to the next pixel along each dimension:

int h_step = 1;
int v_step = width;

And also an origin, the index of the pixel at (0,0):

int origin = 0;

Your loop over the pixels now is:

for (int i = 0; i < height; ++i) {
   int index = origin + i * v_step;
   for (int j = 0; j < width; ++j) {
      std::cout << data[index] << ' ';
      index += h_step;
   }
   std::cout << '\n';
}
std::cout << '\n';

[Note that I'd prefer to use std::size_t and/or std::ptrdiff_t over int, but I left the int in to keep changes from your code minimal.]

The double loop above prints the pixel values in address order, starting with the first one, which is considered to be at the bottom left of the image (we print downwards, so it shows upside-down here, ignore that):

1 2
3 4
5 6

You now want to flip the image, so that the pixel at index (0,0) is the top-left pixel. This requires updating the origin to point to the top-left pixel, and the v_step to move downwards:

origin = (height - 1) * v_step
v_step = -v_step;

The exact same double-loop above now outputs the data in the new order:

5 6
3 4
1 2

You didn't need to copy any data over, you didn't need to reorder or reorganize your pixels, all you needed to do was to specify a new origin and strides. This trick allows you to rotate the image over multiples of 90 degrees, mirror and flip the image as you please.

[Imaging libraries usually have origin be a pointer rather than an index, which avoids one addition per pixel accessed, but this is a minor difference, as memory access generally takes more time than an addition.]

---

That said, I highly recommend that you use an existing image processing library to do all this stuff, so you don't need to reinvent the wheel.