Howto elegantly extract a 2D rectangular region from a C++ vector

Question

The problem is pretty basic. (I am puzzled why the search didn't find anything)

I have a rectangular "picture" that stores it's pixel color line after line in a std::vector

I want to copy a rectangular region out of that picture.

How would I elegantly code this in c++?

My first try:

 template <class  T>    std::vector<T> copyRectFromVector(const std::vector<T>& vec, std::size_t startx,  std::size_t starty, std::size_t endx, std::size_t endy, std::size_t fieldWidth, std::size_t fieldHeight)
    {
     using namespace std;
    vector<T> ret((endx-startx)*(endy-starty)+10);  // 10: chickenfactor

    // checks if the given parameters make sense:
    if (vec.size() < fieldWidth*endy)
    {
     cerr << "Error: CopyRectFromVector: vector to small to contain rectangular region!" << std::endl;
     return ret;
    }

    // do the copying line by line:
    vector<T>::const_iterator vecIt = vec.begin();
    vector<T>::forward_iterator retIt = ret.end();

    vecIt += startx + (starty*fieldWidth);
     for(int i=starty; i < endy; ++i)
    {
         std::copy(vecIt, vecIt + endx - startx, retIt);
        }
        return ret;
}

does not even compile.....

Addit: Clarification: I know how to do this "by hand". It is not a problem as such. But I would love some c++ stl iterator magic that does the same, but faster and... more c++ stylish.

Addition: I give the algorithm the pictureDataVector, the width and height of the picture and a rectangle denoting the region that I want to copy out of the picture. The return value should be a new vector with the contents of the rectangle.

Think of it as opening your favorite image editor, and copy a rectangular region out of that. The Picture is stored as a long 1D array(vector) of pixelcolors.

Answer 1

for (int r = startRow; r < endRow; r++)
    for (int c = startCol; c < endCol; c++)
        rect[r-startRow][c-startCol] = source[r*rowWidth+c];

Answer 2

Good C++ code must first be easy to read and understand (just like any code), object oriented (like any code in an object oriented language) and then should use the language facilities to simplify the implementation.

I would not worry about using STL algorithms to make it look more C++-ish, it would be much better to start simplifying the usability (interface) in an object oriented way. Do not use plain vectors externally to represent your images. Provide a level of abstraction: make a class that represents the image and provide the funcionality you need in there. That will improve usability by encapsulating details from the regular use (the 2D area object can know its dimensions, the user does not need to pass them as arguments). And this will make the code more robust as the user can make less mistakes.

Even if you use STL containers, always consider readability first. If it is simpler to implement in terms of a regular for loop and it will be harder to read with STL algorithms, forget them: make your code simple and maintainable.

That should be your focus: making better, simpler, more readable code. Use language features to improve your code, not your code to exercise or show off the features in the language. It will pay off if you need to maintain that code two months from now.

Note: Using more STL will not make your code more idiomatic in C++, and I believe this is one of those cases. Abusing STL can make the code actually worse.

Answer 3

Basically the same idea, except that it compiles and is a bit more iteratory:

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

template <typename I, typename O> 
void copyRectFromBiggerRect(
    I input,
    O output,
    std::size_t startx,  
    std::size_t cols, 
    std::size_t starty, 
    std::size_t rows, 
    std::size_t stride
) {
    std::advance(input, starty*stride + startx);
    while(rows--) {
        std::copy(input, input+cols, output);
        std::advance(input, stride);
    }
}

template<typename T>
std::vector<T> copyRectFromVector (
    const std::vector<T> &vec, 
    std::size_t startx,  
    std::size_t starty, 
    std::size_t endx, 
    std::size_t endy, 
    std::size_t stride
) {
    // parameter-checking omitted: you could also check endx > startx etc.

    const std::size_t cols = endx - startx;
    const std::size_t rows = endy - starty;

    std::vector<T> ret;
    ret.reserve(rows*cols);
    std::back_insert_iterator<std::vector<T> > output(ret);

    typename std::vector<T>::const_iterator input = vec.begin();
    copyRectFromBiggerRect(input,output,startx,cols,starty,rows,stride);
    return ret;
}

int main() {
    std::vector<int> v(20);
    for (int i = 0; i < 20; ++i) v[i] = i;
    std::vector<int> v2 = copyRectFromVector(v, 0, 0, 1, 2, 4);
    std::copy(v2.begin(), v2.end(), std::ostream_iterator<int>(std::cout, "\n"));
}

I wouldn't expect this to be any faster than two loops copying by index. Probably slower, even, although it's basically a race between the overhead of vector::push_back and the gain from std::copy over a loop.

However, it might be more flexible if your other template code is designed to work with iterators in general, rather than vector as a specific container. copyRectFromBiggerRect can use an array, a deque, or even a list as input just as easily as a vector, although it's currently not optimal for iterators which aren't random-access, since it currently advances through each copied row twice.

For other ways of making this more like other C++ code, consider boost::multi_array for multi-dimensional arrays (in which case the implementation would be completely different from this anyway), and avoid returning collections such as vector by value (firstly it can be inefficient if you don't get the return-value optimisation, and second so that control over what resources are allocated is left at the highest level possible).

Answer 4

Your question asks for a C++ way of copying a rectangular field of elements in some container. You have a fairly close example of doing so and will get more in the answers. Let's generalize, though:

You want an iterator that travels a rectangular range of elements over some range of elements. So, how about write a sort of adapter that sits on any container and provides this special iterator.

Gonna go broad strokes with the code here:

vector<pixels> my_picture;
point selTopLeft(10,10), selBotRight(40, 50);
int picWidth(640), picHeight(480);
rectangular_selection<vector<pixels> > selection1(my_picture.begin(),
  my_picture.end(), picWidth, picHeight, selTopLeft, selBotRight);

// Now you can use stl algorithms on your rectangular range
vector<pixels> rect_copy = std::copy(selection1.begin(), selection1.end());
// or maybe you don't want to copy, you want 
// to modify the selection in place
std::for_each (selection1.begin(), selection1.end(), invert_color);

I'm sure this is totally do-able, but I'm not comfortable coding stl-style template stuff off-the-cuff. If I have some time and you're interested, I may re-edit a rough-draft later, since this is an interesting concept.

See this SO question's answer for inspiration.