Elementwise iterator adaptor

Question

There are many C++ implementations of the Euclidean vector. I.e., a vector in what is typically a 3- or 4-dimensional space. Something along the lines of

struct vec3f { float x, y, z; };

It can of course also be a much more advanced implementation. Since we don't have a standard implementation, nearly every library provides their own. E.g., GLM, Assimp, FBX, etc.

It is common to work with ranges of vectors such as std::vector<vec3f> (in computer graphics for instance). Furthermore, it is common to elementwise (by x, y, z) iterate through such a range. E.g.,

std::vector<vec3f> uv_coordinates; // Given from 3rd party library
std::vector<float> raw_uv_coordinates; // Used later for low-level transformations
for (const auto& position : positions) {
    raw_uv_coordinates.emplace_back(position.x);
    raw_uv_coordinates.emplace_back(position.y);
    // The z-coordinate is discarded since it is not used.
}

Note how I can't use std::copy since there isn't a one-to-one mapping between uv_coordinates and raw_uv_coordinates. Say you have to support another vector type like

struct Vector4 { double data[4] };

This will further complicate the code.

I solve this problem by introducing an iterator adaptor called elementwise. It wraps an iterator to a container of vector elements. E.g.,

auto first = elementwise(begin(uv_coordinates));
*first++; // Returns the x-coordinate of the 1st element.
*first++; // Returns the y-coordinate of the 1st element.
*first++; // Returns the z-coordinate of the 1st element.
*first++; // Returns the x-coordinate of the 2nd element.
...

This can be used to output all the coordinates

std::copy(
    elementwise(begin(uv_coordinates)),
    elementwise(end(uv_coordinates)),
    std::ostream_iterator<float>{std::cout, ", "});

elementwise gets information about the underlying vector type (vec3f, Vector4, etc.) through the vector_traits class. Consequently, vector_traits must be specialized for each vector type you wish to use with elementwise.

Here is the implementation along with all the needed helper classes

////////////////////////////////////////////////////////////////////////////////
/// Utility
////////////////////////////////////////////////////////////////////////////////
// is_const_iterator
// Reference: http://stackoverflow.com/a/5423637/554283
template<typename T>
struct is_const_pointer { static const bool value = false; };

template<typename T>
struct is_const_pointer<const T*> { static const bool value = true; };

template <typename TIterator>
struct is_const_iterator
{
    typedef typename std::iterator_traits<TIterator>::pointer pointer;
    static const bool value = is_const_pointer<pointer>::value;
};



////////////////////////////////////////////////////////////////////////////////
/// Vector Traits
////////////////////////////////////////////////////////////////////////////////
enum class vector_indexing_method { brackets, xyz, xyzw };
template<typename Vector> struct vector_traits {};

// Must be specialized. Say you have a vector like
//    struct vector_xyz { float x, y, z; };
//
// Then you must provide the specialization
//
//    template<>
//    struct vector_traits<vector_xyz> {
//        using value_type = float;
//        const static vector_indexing_method indexing_method{vector_indexing_method::xyz};
//        const static int num_elements{3};
//    };


// Get vector traits from an iterator
template<typename Iterator>
using vector_traits_from_iterator = vector_traits<typename iterator_traits<Iterator>::value_type>;

// Get vector value_type from an iterator
template<typename Iterator>
struct vector_value_type {
    using base_value_type = typename vector_traits_from_iterator<Iterator>::value_type;
    using type = conditional_t<is_const_iterator<Iterator>::value, const base_value_type, base_value_type>;    
};
template<typename Iterator>
using vector_value_type_t = typename vector_value_type<Iterator>::type;



////////////////////////////////////////////////////////////////////////////////
/// Elementwise Iterator Base
////////////////////////////////////////////////////////////////////////////////
template<typename Iterator, vector_indexing_method>
struct elementwise_iterator_base {};

// Specialization for brackets
template<typename Iterator>
struct elementwise_iterator_base<Iterator, vector_indexing_method::brackets> {
    vector_value_type_t<Iterator>& dereference() const
    { return (*current)[element]; }

    Iterator current;
    int element;
};

// Specialization for xyz
template<typename Iterator>
struct elementwise_iterator_base<Iterator, vector_indexing_method::xyz> {
    vector_value_type_t<Iterator>& dereference() const {
        switch (element) {
        case 0: return current->x;
        case 1: return current->y;
        case 2: return current->z;
        default: assert(false); // Shouldn't be reached. Prevents compiler warnings.
        }
    }

    Iterator current;
    int element;
};

// Specialization for xyzw
template<typename Iterator>
struct elementwise_iterator_base<Iterator, vector_indexing_method::xyzw> {
    vector_value_type_t<Iterator>& dereference() const {
        switch (element) {
        case 0: return current->x;
        case 1: return current->y;
        case 2: return current->z;
        case 3: return current->w;
        default: assert(false); // Shouldn't be reached. Prevents compiler warnings.
        }
    }

    Iterator current;
    int element;
};



////////////////////////////////////////////////////////////////////////////////
/// Elementwise Iterator
////////////////////////////////////////////////////////////////////////////////
// Template class
template<typename Iterator, int N = vector_traits_from_iterator<Iterator>::num_elements>
class elementwise_iterator 
    : public boost::iterator_facade<
        elementwise_iterator<Iterator, N>,
        vector_value_type_t<Iterator>,
        typename iterator_traits<Iterator>::iterator_category>
    , public elementwise_iterator_base<Iterator, vector_traits_from_iterator<Iterator>::indexing_method>
{
public:
    static_assert(N <= vector_traits_from_iterator<Iterator>::num_elements, "elementwise_iterator: Exceeded vector's num_elements limit.");

    using difference_type = typename iterator_traits<Iterator>::difference_type;
    using base = elementwise_iterator_base<Iterator, vector_traits_from_iterator<Iterator>::indexing_method>;
    using base::current;
    using base::element;

    elementwise_iterator() : base{nullptr, 0} {}
    elementwise_iterator( Iterator current ) : base{current, 0} {}

private:
    friend class boost::iterator_core_access;

    bool equal( const elementwise_iterator& other ) const
    { return current == other.current && element == other.element; }

    void increment() {
        element = (element + 1) % N;
        if (!element) ++current;
    }

    void decrement() {
        if (!element) {
            element = N;
            --current;
        }
        --element;
    }

    void advance( difference_type n )
    { 
        auto div = std::div(n, N);
        current += div.quot; element += div.rem;
    }

    difference_type distance_to( const elementwise_iterator& other ) const
    { return (other.current - current) * N - (other.element - element); }
};

// Utility functions
template<typename Iterator>
auto elementwise( Iterator iterator )
{ return elementwise_iterator<Iterator>{iterator}; }

template<int N, typename Iterator>
auto elementwise( Iterator iterator )
{ return elementwise_iterator<Iterator, N>{iterator}; }

Note that I use boost::iterator_facade to define the elementwise_iterator. Currently, the implementation supports element indexing through brackets (E.g., vec[0]) and through direct member access (E.g., vec.x). Additional indexing methods can easily be added by specializing elementwise_iterator_base.

Now the example from before can be rewritten to

std::vector<vec3f> uv_coordinates; // Given from 3rd party library
std::vector<float> raw_uv_coordinates; // Used later for low-level transformations
for_each(
    elementwise<2>(cbegin(uv_coordinates)),
    elementwise<2>(cend(uv_coordinates)),
    [] ( auto& value ) { raw_uv_coordinates.emplace_back(value); });

Note that I have explicitly provided the template parameter N = 2. This clamps the output to the two first elements of each vector. We could even just do

std::vector<vec3f> uv_coordinates; // Given from 3rd party library
std::vector<float> raw_uv_coordinates; // Used later for low-level transformations
copy(
    elementwise<2>(cbegin(uv_coordinates)),
    elementwise<2>(cend(uv_coordinates)),
    back_inserter(raw_uv_coordinates));

In contrast to the earlier code, the above will work with any vector type. The only requirement is that there exists a specialization of vector_traits for the vector type (this can be done once).

I've made a code sample to demonstrate further. Herein, you will also find nested adaptations. E.g., a std::reverse_iterator of an elementwise_iterator.

Have I missed any edge cases? What do you think of the naming/style/implementation? Any critique is welcome.

Answer 1

I don't write C++, but one thing I've noticed is that your bracing style isn't consistent. You have the standard/expected C-style braces:

struct is_const_iterator
{
    typedef typename std::iterator_traits<TIterator>::pointer pointer;
    static const bool value = is_const_pointer<pointer>::value;
};

Then you have the one-liner style:

template<int N, typename Iterator>
auto elementwise( Iterator iterator )
{ return elementwise_iterator<Iterator, N>{iterator}; }

And then you have the Java-style braces:

void decrement() {
    if (!element) {
        element = N;
        --current;
    }
    --element;
}

---

Perhaps it's nitpicky, but you should strive to make your code look like it was written by one person - this looks like a Java and a C# programmer are fighting over which bracing style the C++ code base should be using:

void decrement() {
    if (!element) {
        element = N;
        --current;
    }
    --element;
}

void advance( difference_type n )
{ 
    auto div = std::div(n, N);
    current += div.quot; element += div.rem;
}

I'd say just pick one, and stick to it ;)

Answer 2

I'm a little unsure about this line:

default: assert(false); // Shouldn't be reached. Prevents compiler warnings.

I assume that your compiler was complaining because there was no default case, which can happen in some situations. However, it feels odd to put an assert there, which is mostly used for debugging. You do say that that shouldn't be reached, but you must also be sure that if it's reached anyway, that it won't cause problems for anyone. If so, then the program should still proceed. If you cannot replace it with anything else, then a break may suffice.

In addition, the comment is partly redundant and misleading. An assert usually signifies some code that shouldn't be reached. You've also already stated that the default, not the assert itself, was added to stop those compiler errors. As such, this comment should just be removed, unless you have something else that's worthwhile to put there.