element iterator for mathematical containers

First of all this is kind of a repost of this blog entry. I was going to post the code to the blog as well, but remembered "this" dm feature :)

so i was writing those damned classes (again) and i was thinking how nice it'd be to have an iterator for these things. Something standards compliant. I was writing an "abs" function when it hit me. I wrote abs for vector2/vector3/vector4/matrix3x3/matrix4x4/etc and it'd be great if i could add a generic algo that'd do it for me :

template< class In >
void abs( In begin, In end ) {
    while( begin != end ) {
        *begin = abs(*begin);
        ++begin;
    }
}

matrix m
vector v;
abs( m.begin(), m.end() );
abs( v.begin(), v.end() );

So I wrote an element iterator which is a little bit beefy, but gets the job done nicely. I do not know how badly this would affect performance as I have not tested this out heavily yet, but it's something that's nice and can be useful for other objects and not just mathematical containers. The iterator is fully standard compliant (afaik) and it has all the functionality of a random iteraotor, so you can use it with any algorithm. To create the begin/end functions for an object you'd do this:

// example vector3
struct vector3 {
    float x, y, z;

    typedef elem_iter< vector3, float, 3 > iterator;
    iterator begin();
    iterator end();
};

iterator vector3::begin() {
    return iterator( &x, &y, &z ); // make sure you actually pass in 3 elements.
}

iterator vector3::end() {
    return begin() + 3; // make sure you add the correct amount.
}

Now you can use any vector3 object with any iterator compatable algorithm. You are of course not limited to 3 elements, the number of elements you pass in to the constructor of elem_iter depends on the third template parameter. In this case it was 3 so I passed in 3 addresses of each element.

Some notes:
* the elements in a container have to be the same type;
* the constructor of elem_iter does not check how many elements you pass in.
* You have to pass in the address of each element of your container.

So here's the elem_iter class:

#include <iterator>
#include <cstdarg>

template< class C, class T, int N >
class elem_iter 
  : public std::iterator< std::random_access_iterator_tag, T, std::size_t, T*, T& > {

    T* elems[N + 1];
    std::size_t cur;

public:

    elem_iter( T* first, ... ) {
        va_list args;
        va_start( args, first );
        elems[0] = first;
        for( int i = 1; i < N; ++i ) {
            elems[i] = va_arg(args, T*);
        }
        elems[N] = 0;
        cur = 0;
        va_end(args);
    }

    elem_iter& operator ++ () {
        ++cur;
        return *this;
    }

    elem_iter operator ++ (int) {
        elem_iter cpy(*this);
        cur++;
        return cpy;
    }

    elem_iter& operator -- () {
        --cur;
        return *this;
    }

    elem_iter operator -- (int) {
        elem_iter cpy(*this);
        cur--;
        return cpy;
    }

    T& operator * () {
        return *elems[cur];
    }

    bool operator != ( const elem_iter& e ) const {
        return cur != e.cur;
    }

    bool operator == ( const elem_iter& e ) const {
        return cur == e.cur;
    }

    T& operator [] ( std::size_t i ) {
        return *elems[i];
    }

    const T& operator [] ( std::size_t i ) const {
        return *elems[i];
    }

    void operator += ( std::size_t i ) {
        cur += i;
    }

    void operator -= ( std::size_t i ) {
        cur -= i;
    }

    elem_iter operator + ( std::size_t i ) const {
        elem_iter cpy(*this);
        cpy += i;
        return cpy;
    }

    elem_iter operator - ( std::size_t i ) const {
        elem_iter cpy(*this);
        cpy -= i;
        return cpy;
    }

    std::size_t operator - ( const elem_iter& other ) const {
        return cur - other.cur;
    }
        
    bool operator < ( const elem_iter& other ) const {
        return cur < other.cur;
    }

    bool operator > ( const elem_iter& other ) const {
        return cur > other.cur;
    }

    bool operator <= ( const elem_iter& other ) const {
        return cur <= other.cur;
    }

    bool operator >= ( const elem_iter& other ) const {
        return cur >= other.cur;
    }

};

template< class C, class T, int N >
elem_iter< C, T, N > operator + ( std::size_t i, const elem_iter< C, T, N >& iter ) {
    elem_iter< C, T, N > cpy(iter);
    cpy += i;
    return cpy;
}

Don't need a copy ctor, default ctor or assignment op because the compiler generated ones will suffice. The best part about this code is that it's non-intrusive. You can just add a begin/end pair to all your already written math objects. Of course if you have a vector3 class implemented in terms of a float* then this little gem is useless, but for someone like me, who just doesnt like to implement a vec3 in terms of a float* and would rather use explicit member names, this piece of code is pretty handy. Still, have to sort out the performance considerations because it does add a bit of overhead, might be negligible in most cases but dcant say for sure.

Slightly off topic but that first example would be better written like this

std::transform(v.begin(), v.end(), v.begin(), std::ptr_fun<T, T>(abs) );

you can probably even use your new iterator!

Originally Posted by dave_

Slightly off topic but that first example would be better written like this

std::transform(v.begin(), v.end(), v.begin(), std::ptr_fun<T, T>(abs) );

you can probably even use your new iterator!

I don't know you about guys, but I definitely prefer having a somewhat cleaner looking code myself. Using iterators and std::transform for something like getting absolute value of a 3D-Vector... It's not cool, it's not handy, It's overengineered! It would be bad even it didn't have the considerable overhead it has..

Just write a custom abs function for your float2, float3 and float4 types and you are all set for 99% of the cases.


[edit]
If you are doing this because you don't like vector members being in an array you have other choices than making iterator like this.

1. se union and implement [] operator of the vector class. That way you can do both: use .x, or [0].

2 Use array internally and implement [] operator and methods x(), y() and z().

Originally Posted by juhnu

Just write a custom abs function for your float2, float3 and float4 types and you are all set for 99% of the cases.

Fair enough, I wouldn't do it for something like this.
I was saying cos transform is often ignored.

Originally Posted by juhnu

2 Use array internally and implement [] operator and methods x(), y() and z().

Thats the way I've done it in the past.

The point of using generic code is always questionable but you kind of miss the point if you think it is to gain performence. The gain is that you can apply just about any other generic algorithm. There is STL with comes with a lot of stuff but also Boost which have a huge set of algorithms and stuff for generic coding. The fact is that even though you might have a point with vectors when you get to the matrices it kind of makes sense using an generic iterator. But more importantly he motivated it by the fact that he was enforced to write several of them which could motivate the usage of generic code (not demanding so).

You might be correct with the notation that it will most probably not give the best performence but that's not the deal with generic coding. It deals with writing code for every possible instance of it.