Get maximum element of std::vector with strides

Question

I have a std::vector<float> with the following layout of data

x1 | y1 | z1 | x2 | y2 | z2 | .... | xn | yn | zn

I'm trying to figure out an STL-ish way to get the maximum x element as well as y or z

The obvious

double xyzmax = *std::max_element(myvector.begin(),myvector.end() );

picks the absolute maximum and does not allow me to specify the stride. Is there some trick with no for loops?

Answer 1

Here is a reference implementation of std::max_element.

template<class ForwardIt>
ForwardIt max_element(ForwardIt first, ForwardIt last)
{
    if (first == last) {
        return last;
    }
    ForwardIt largest = first;
    ++first;
    for (; first != last; ++first) {
        if (*largest < *first) {
            largest = first;
        }
    }
    return largest;
}

You can create your own algorithm by modifying this in the following way:

template<class ForwardIt>
ForwardIt max_element_nth(ForwardIt first, ForwardIt last, int n)
{
    if (first == last) {
        return last;
    }
    ForwardIt largest = first;
    first += n;
    for (; first < last; first += n) {
        if (*largest < *first) {
            largest = first;
        }
    }
    return largest;
}

Of course it has the limitation of working only with random access iterators, but it certainly works for vector.

double xmax = *max_element_nth(myvector.begin(),myvector.end(), 3);
double ymax = *max_element_nth(myvector.begin()+1,myvector.end(), 3);
double zmax = *max_element_nth(myvector.begin()+2,myvector.end(), 3);

But I'd rather do it by storing the (x, y, z) values in a structure, and take a vector of that. Then, you can use the standard max_element with a custom comparator.

Answer 2

You could use the Boost.Iterator library and the boost::iterator_facade to create a strided iterator that can be initalized with a std::vector<float>::iterator and for which ++it does it += 3; on the underlying iterator.

Given such an iterator of type StrideIt, you could write

maxX = *std::max_element(StrideIt(v.begin() + 0), StrideIt(v.end() - 2));
maxY = *std::max_element(StrideIt(v.begin() + 1), StrideIt(v.end() - 1));
maxZ = *std::max_element(StrideIt(v.begin() + 2), StrideIt(v.end() - 0));

This is preferably to redefining the algorithms because there are many more algorithms than iterator types.

If you want maximum flexibility, you could make StrideIt a class template taking the type (float in your case) and a runtime construtor argument defining the stride (3 in your case).