Pairwise iteration over a vector

Question

Question Synopsis

Given a std::vector<T>, how can I create a view that exposes the interface of a std::vector<std::pair<T, T>>, where each pair consists of two consecutive elements in the underlying vector?

Details

The goal is to create multiple container abstractions over the same storage, which is a std::vector<T>. The type T is some sort of discriminated union, à la Boost Variant. The storage requirement is given, otherwise I would simply use a std::vector<std::pair<T, T>>. The views over the storage I would like to support are sets (unique elements) and tables (associative array, unique keys). While the former is straight-forward by ensuring the set uniqueness property, the latter requires handling keys and values.

To support associative array semantics over a std::vector<T>, I am currently thinking that the best way would be to create a view of the form std::vector<std::pair<T, T>>, and that this view would allow me use STL algorithms to maintain the required properties. Does this sound like a good strategy? Are there any other ideas?

Related

If I had an iterator i that goes over every even element and iterator j that goes through every odd element, Boost's zip iterator comes to mind, which would enable iteration in (i,j) pairs. But my use case is slightly different in that I do not have two separate containers.

Answer 1

It seems that Boost's iterator_facade is indeed what I want. Here is a toy example (with rough edges):

#include <algorithm>
#include <iostream>
#include <vector>
#include <boost/iterator/iterator_facade.hpp>

template <typename Value>
class pair_iterator
  : public boost::iterator_facade<
        pair_iterator<Value>
      , Value
      , boost::random_access_traversal_tag
      , std::pair<Value&, Value&>
      , typename std::vector<Value>::difference_type
    >
{
public:
    typedef std::vector<Value> vector_type;
    typedef typename vector_type::difference_type difference_type;
    typedef typename vector_type::iterator iterator;

    pair_iterator()
        : i_(0)
    {
    }

    explicit pair_iterator(iterator i)
      : i_(i)
    {
    }

private:
    friend class boost::iterator_core_access;

    bool equal(pair_iterator<Value> const& other) const
    {
        return i_ == other.i_;
    }

    void increment()
    {
        ++i_;
        ++i_;
    }

    std::pair<Value&, Value&> dereference() const
    {
        return { std::ref(*i_), std::ref(*(i_ + 1)) };
    }

    void advance(difference_type n)
    {
        i_ += n << 1;
    }

    difference_type distance_to(pair_iterator<Value> const& other) const
    {
        return other.i_ - i_;
    }

    iterator i_;
};

int main()
{
    typedef pair_iterator<int> int_map_iterator;
    std::vector<int> v{2, 20, 3, 30, 5, 50, 7, 70};
    int_map_iterator first(v.begin());
    int_map_iterator last(v.end());

    std::for_each(first + 1, last,
                  [](std::pair<int&, int&> p)
                  {
                      std::cout
                          << p.first << " -> "
                          << p.second << std::endl;
                  });

    return 0;
}

The output is:

3 -> 30
5 -> 50
7 -> 70

Issues

• Conversion from iterator to const_iterator has not yet been addressed by this example.
• The iterator only works when the underlying vector has even size and needs a more conservative implementation of dereference().

Answer 2

The first thing to note is that you won't be able to expose a std::pair<T const, T>& as a means to modify the objects. What may be sufficantly close, however, is a std::pair<T const, T&> as you'll only be able to change the second part.

With this out of the way it seems you need

1. An iterator type which skips every other value and is used to iterate over the keys (elements with even indices) and the values (elements with odd indices).
2. Something like a "zip iterator" which takes two iterators and exposes a std::pair<T const, T&> obtained from them.