12
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ It's an interesting idea. I haven't had chance to go over the code yet but a thought occurred to me and I wondered if you'd considered it and rejected it. Wouldn't it be simpler in some ways to wrap the output iterator (assuming that's always raw floats) to step over multiple elements at a time , perhaps dereferencing as a tuple of references. You could then easily adapt to any particular vector type in the lambda passed to your algorithm. \$\endgroup\$ – mattnewport Nov 4 '14 at 19:07
  • \$\begingroup\$ @mattnewport Haha, yeah, that was actually my initial take on elementwise. It is much simpler to implement. I specifically chose not to continue with that approach since doesn't compose it with other iterator adapters. E.g., std::reverse_iterator or boost::transform_iterator. Good comment. I hope you get the time to look through the code. Cheers! \$\endgroup\$ – Frederik Aalund Nov 4 '14 at 23:02
5
+25
\$\begingroup\$

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 ;)

\$\endgroup\$
  • 2
    \$\begingroup\$ It's common to see this kind of things in C++: one style for class/struct definition, on style for functions, one style for control structures and another one for initialization. Plus, some people write one-liners when the code is short. Some argue that the style reminds them of what they are opening. That said, in this code, it isn't even consistent for the same elements. \$\endgroup\$ – Morwenn Dec 19 '14 at 16:08
  • \$\begingroup\$ That's a good point. I should be consistent with my braces! I generally use the style found in decrement. However, if it's a one-liner, then I use the style found in distance_to. The is_const_iterator and advance bracing styles were blunders. Nice catch! \$\endgroup\$ – Frederik Aalund Dec 20 '14 at 2:03
5
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Indeed the compiler was complaining about the missing default case. As for the assertion, I quote Andrzej Krzemieński: "..the only place where you put assertions is where you are sure that the situation never ever occurs (unless we have a bug). This is what they are for!". So if the assert is reached, the developer made a mistake. The assert allows me to find such mistakes. ...But there is an error: The comment itself. It shouldn't be there. The assert is not meant to silence the compiler. It's meant to shout at the developer. \$\endgroup\$ – Frederik Aalund Dec 20 '14 at 2:17
  • \$\begingroup\$ @FrederikAalund: I can understand that. Putting anything for the default will silence the compiler. As for the comment, the second sentence should be removed, but also because it's more of a mental note. The first sentence may be considered redundant since that's usually what an assert implies. \$\endgroup\$ – Jamal Dec 20 '14 at 2:33
  • \$\begingroup\$ I'm glad we can agree. It's a good find and thanks for bringing it to my attention. I will be more careful with my code comments in the future. \$\endgroup\$ – Frederik Aalund Dec 20 '14 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.