Iterator for multi-dimensional vector that is used as unidimensional?

Question

I have a vector that looks like this:

std::vector<std::vector<MyClass>> myVector;

And I would like to access its elements through iterators as if it was an unidimensional vector:

for (auto& x : myVector)
{
     foo(x); // x is an object of type MyClass
}

(i.e. the fact that there are multiple dimensions is transparent to whoever loops through myVector)

I have an idea of how this should be done, have a custom iterator implementation that saves current indexes so that when one of the vectors has no more elements, it resets one of the indexes and increments the other so that it can start iterating through the next vector and so on. But I have been trying to code this idea but can't seem to get this working. Does anyone have any idea of how I can possibly achieve this? Or even better, if there's any open-source project that has a similar implementation?

Thanks.

If this is rectangular, make a unidimensional vector of size rows* columns. 2D access is performed with a wrapper that returns `myvector[row*columns+column]`. Couple performance advantages (contiguous memory) to doing 2D vectors like this even when you don't need to 1D iterate. — user4581301, Jun 17 '16 at 00:31

Jack · Answer 1 · 2016-06-17T01:08:46.733

It's totally possible to define your own iterator to hide all the details of iterating through a vector of vector, I wrote some code to give you the idea, mind that it should require more checks but it basically works and give you the idea.

You just need to write the required operations to make it work in other code like an opaque iterator.

template <typename T>
struct vector2d
{
public:
  class iterator
  {
  public:
    using vector_type = std::vector<std::vector<T>>;
    using first_level_iterator = typename std::vector<std::vector<T>>::iterator;
    using second_level_iterator = typename std::vector<T>::iterator;

  private:
    vector_type& data;
    first_level_iterator fit;
    second_level_iterator sit;

  public:
    iterator(vector_type& data, bool begin) : data(data)
    {
      if (begin)
      {
        fit = data.begin();
        sit = fit->begin();
      }
      else
      {
        fit = data.end();
      }
    }

    inline bool operator!=(const iterator& other) const { return fit != other.fit || (fit != data.end() && sit != other.sit); }
    inline const iterator& operator++() {
      // don't go past end
      if (fit == data.end())
        return *this;

      // increment inner iterator
        ++sit;

      // if we reached the end of inner vector
      if (sit == fit->end())
      {
        // go to next vector
        ++fit;

        // if we reached end then don't reset sit since it would be UB
        if (fit != data.end())
        sit = fit->begin();
      }

      return *this;
    }

    T& operator*() const { return *sit; }
  };

public:
  std::vector<std::vector<T>> data;

  iterator begin() { return iterator(this->data, true); }
  iterator end() { return iterator(this->data, false); }
};

A small test:

int main() {
  vector2d<int> data;

  data.data.push_back(vector<int>());
  data.data.push_back(vector<int>());
  data.data.push_back(vector<int>());

  for (int i = 1; i < 5; ++i)
  {
    data.data[0].push_back(i);
    data.data[1].push_back(i*2);
    data.data[2].push_back(i*3);
  }

  for (auto i : data)
  {
    cout << i << endl;
  }

  return 0;
}

The behavior is rather simple but you must make sure that it's always consistent for all the edge cases.

I read somewhere that it is not advisable to derive from standard library classes. Does that guideline not extend to `std::iterator`? — The Vivandiere, Jun 17 '16 at 00:54
If some of the inner vectors are empty, wouldn't you need a `while` to skip empty vectors? Also, `data.end()->end()` is ill-formed: so you'd probably need some special handling so that if `fit == end()` then `sit` is not used. — Daniel Schepler, Jun 17 '16 at 00:54
@DanielSchepler: this is just to give the OP the idea behind how to do it. I explicitly wrote it's not complete and it requires sanity checks. — Jack, Jun 17 '16 at 00:55
@type traitor The advice against inheriting from std objects stems from their lack of a virtual destructor. So if you decide to derive an object from `std::string` called `MyString`, and then you or someone else down the line starts accessing `MyString` objects using pointers to `std::string`, then bad things happen because `MyString`'s overrides (like its destructor) will not be called, and copies will be missing the `MyString`-specific data. But it is common to derive from objects, like `std::exception`, stream objects, and `std::iterator`. Just no polymorphic access. — Christopher Oicles, Jun 17 '16 at 01:44

score 1 · Answer 2 · answered Jun 17 '16 at 02:19

A pretty minimal range type:

template<class It>
struct range_t {
private:
  It b, e;
public:
  It begin() const { return b; }
  It end() const { return e; }

  decltype(auto) front() const { return *b; }
  decltype(auto) back() const { return *std::prev(e); }

  bool empty() const { return b==e; }

  range_t without_front( std::size_t n = 1 ) const {
    auto r = *this;
    std::advance(r.b,n);
    return r;
  }      
  range_t without_back( std::size_t n = 1 ) const {
    auto r = *this;
    std::advance(r.e,std::ptrdiff_t(-n));
    return r;
  }      

  range_t(It s, It f):b(std::move(s)), e(std::move(f)) {}
  range_t():b(), e() {}
};
template<class It>
range_t<It> range( It b, It e ) {
  return {std::move(b), std::move(e)};
}

Doing this task is far easier with ranges than with iterators.

template<class Outer, class Inner>
struct stacked_range_t {
  range_t<Outer> outer;
  stacked_range_t()=default;
  stacked_range_t( range_t<Outer> o ):outer(std::move(o)) {}
  struct iterator {
  private:
    range_t<Outer> outer;
    range_t<Inner> inner;
  public:
    iterator(
      range_t<Outer> o,
      range_t<Inner> i
    ):outer(std::move(o)), inner(std::move(i)) {}
    iterator()=default;

    friend auto mytie(iterator const& it) {
      return std::tie( it.outer.begin(), it.inner.begin(), it.inner.end() );
    }
    friend bool operator==(iterator const& lhs, iterator const& rhs) {
      return mytie(lhs)==mytie(rhs);
    }
    friend bool operator!=(iterator const& lhs, iterator const& rhs) {
      return mytie(lhs)==mytie(rhs);
    }
    using difference_type = std::ptrdiff_t;
    using value_type = typename std::iterator_traits<Inner>::value_type;
    using pointer = typename std::iterator_traits<Inner>::pointer;
    using reference = typename std::iterator_traits<Inner>::reference;
    using iterator_category = std::input_iterator_tag;

    reference operator*() const {
      return *inner.begin();
    }
    pointer operator->() const {
      return inner.begin().operator->();
    }
    iterator& operator++() {
      using std::begin; using std::end;
      inner = inner.without_front();
      while (inner.empty())
      {
        outer = outer.without_front();
        if (!outer.empty())
          inner = range( begin(outer.front()), end(outer.front()) );
      }
      return *this;
    }
    iterator operator++(int) {
      auto it = *this;
      ++*this;
      return it;
    }
  };
  iterator end() const {
    return { range( outer.end(), outer.end() ), {} };
  }
  // a bit tricky:
  iterator begin() const {
    if (outer.empty()) return end();

    auto rout = outer;
    while( !rout.empty() ) {
      using std::begin; using std::end;
      auto rin = range( begin(rout.front()), end(rout.front()) );
      if (!rin.empty())
        return {std::move(rout), std::move(rin)};
      rout = rout.without_front();
    }
    return end();
  }
};

and a function to create it:

template<class Range>
auto make_stacked_range(Range& r) {
  using std::begin; using std::end;
  using Outer = decltype(begin(r));
  using Inner = decltype(begin(*begin(r));
  return stacked_range_t<Outer, Inner>{
    {begin(r), end(r)}
  };
}

there probably are typos. Use of C++1z features can be worked around with overly annoying decltype expressions and helper traits classes.

Relies on the iterators being trivially constructible, and such trivially constructed iterators are equal.

score 1 · Answer 3 · answered Jun 17 '16 at 02:20

1

try to use template recursion,e.g.:

#include <stdio.h>
#include <vector>
template <typename V>
void f(V& v){
    for(auto& e : v){
        f(e);
    }
    printf("\n");
}

template <>
void f(int& v){
    printf("%d ",v);
}

int main(){
    std::vector<int> v1={1,2};
    f(v1);
    std::vector<std::vector<int> > v2={{3,4},{5,6,7}};
    f(v2);
    return 0;
};

answered Jun 17 '16 at 02:20

ggrr

7,737
5
31
53

[Prefer overload to specialization](http://stackoverflow.com/questions/7108033/template-specialization-vs-function-overloading): i.e `void f(int& v) { .. }` – Jarod42 Jun 17 '16 at 20:23

score 1 · Answer 4 · answered Jun 17 '16 at 20:17

1

With range/v3:

for (auto& x : myVector | ranges::view::join)
{
     foo(x); // x is an object of type MyClass&
}

Demo

answered Jun 17 '16 at 20:17

Jarod42

203,559
14
181
302

Iterator for multi-dimensional vector that is used as unidimensional?

4 Answers4

Linked