New user self-registration is disabled due to spam. Please email eigen-core-team @ lists.tuxfamily.org if you need an account.
Before reporting a bug, please make sure that your Eigen version is up-to-date!
Bug 231 - STL compatible iterators
Summary: STL compatible iterators
Status: RESOLVED FIXED
Alias: None
Product: Eigen
Classification: Unclassified
Component: Interoperability (show other bugs)
Version: 3.0
Hardware: All All
: Low Feature Request
Assignee: Nobody
URL:
Whiteboard:
Keywords: JuniorJob
Depends on: 360
Blocks: 3.4 1104
  Show dependency treegraph
 
Reported: 2011-03-22 00:20 UTC by Gael Guennebaud
Modified: 2018-10-08 20:34 UTC (History)
11 users (show)



Attachments
A CRTP base class which can be used to implement standard conforming iterators. (3.88 KB, text/plain)
2013-07-03 09:12 UTC, Hauke Heibel
no flags Details
Three functions for 2D index arithmetic. (1.67 KB, text/plain)
2013-07-03 09:13 UTC, Hauke Heibel
no flags Details

Description Gael Guennebaud 2011-03-22 00:20:14 UTC
Some day it would be cool to support STL's iterators, here is a start written by "inverse" from the forum (http://forum.kde.org/viewtopic.php?f=74&t=94120#p191501):

template<typename Value_t, typename Container_t>
class index_iterator : public std::iterator<std::random_access_iterator_tag, Value_t>
{
protected:
   Container_t* container_;
   int          index_;

public:
   index_iterator() : container_(0), index_(0) { }
   index_iterator(Container_t& container, int index) : container_(&container), index_(index) { }

   bool operator==(const index_iterator& other) { return container_ == other.container_ && index_ == other.index_; }
   bool operator!=(const index_iterator& other) { return !(*this == other); }

   Value_t&       operator*()       { return (*container_)[index_]; }
   Value_t const& operator*() const { return (*container_)[index_]; }
   
   Value_t*       operator->()       { return &((*container_)[index_]); }
   Value_t const* operator->() const { return &((*container_)[index_]); }

   index_iterator& operator++() { ++index_; return *this;}
   index_iterator operator++(int) { index_iterator prev(*this); operator++(); return prev;}

   index_iterator& operator--() { --index_; return *this;}
   index_iterator operator--(int) { index_iterator prev(*this); operator--(); return prev;}
   
   friend index_iterator operator+(const index_iterator& a, int b) { index_iterator ret(a); ret += b; return ret; }
   friend index_iterator operator-(const index_iterator& a, int b) { index_iterator ret(a); ret -= b; return ret; }
   friend index_iterator operator+(int a, const index_iterator& b) { index_iterator ret(b); ret += a; return ret; }
   friend index_iterator operator-(int a, const index_iterator& b) { index_iterator ret(b); ret -= a; return ret; }

   int operator-(const index_iterator& other) const { return index_ - other.index_; }

   bool operator< (const index_iterator& other) { return container_ == other.container_ && index_ <  other.index_; }
   bool operator<=(const index_iterator& other) { return container_ == other.container_ && index_ <= other.index_; }
   bool operator> (const index_iterator& other) { return container_ == other.container_ && index_ >  other.index_; }
   bool operator>=(const index_iterator& other) { return container_ == other.container_ && index_ >= other.index_; }

   index_iterator& operator+=(int b) { index_ += b; }
   index_iterator& operator-=(int b) { index_ -= b; }

   Value_t&       operator[](int i)       { return (*container_)[i]; }
   Value_t const& operator[](int i) const { return (*container_)[i]; }
};
template<typename Value_t, typename Container_t>
inline index_iterator<Value_t, Container_t> index_begin(Container_t& container)
{
   return index_iterator<Value_t, Container_t>(container, 0);
}
template<typename Value_t, typename Container_t>
inline index_iterator<Value_t, Container_t> index_end(Container_t& container)
{
   return index_iterator<Value_t, Container_t>(container, container.size());
}
template<typename Value_t, typename Container_t>
inline index_iterator<const Value_t, const Container_t> index_begin(const Container_t& container)
{
   return index_iterator<const Value_t, const Container_t>(container, 0);
}
template<typename Value_t, typename Container_t>
inline index_iterator<const Value_t, const Container_t> index_end(const Container_t& container)
{
   return index_iterator<const Value_t, const Container_t>(container, container.size());
}



usage example:

Eigen::MatrixXd m(100, 20);

auto row_2 = m.row(2);
auto begin = index_begin<double>(row_2);
auto end   = index_end  <double>(row_2);

// sort a row:
std::sort(begin, end);

// copy row to standard library container:
std::vector<double> std_v(begin, end);

// find a value in a row:
std::find(begin, end, 3.14);
Comment 1 Aaron Kaluszka 2012-03-02 10:24:27 UTC
To support C++11 range-based for loops, begin and end need to be member functions.
Comment 2 Hauke Heibel 2012-03-02 11:25:46 UTC
Aaron, are you sure that one does not need overloads for the free functions std::begin and std::end? 

Maybe they are already enough which would be nice since we would not "infect" our interface with those methods.
Comment 3 Aaron Kaluszka 2012-03-02 19:37:07 UTC
You're right, that would be sufficient.
Comment 4 Hauke Heibel 2013-06-18 13:34:47 UTC
I have recently written iterators for my own image classes (basically the same problem). If we implement iterators we should think about providing different ones for performance reasons. 

a) a random access iterator which only allows to access the raw values of a dense matrix/array
b) a random access iterator which allows users to traverse maps (requires also strides and cols)
c) random access iterators which give the users access to the current entries' index (might be required for some algorithms)

a) can be implemented to work as fast and efficient as hand written loops
b) is a bit slower than a) since we need to check when a row's end is reached before switching to the next one via the strides
c) is even slower because we also need to take care of the indices

I am also not sure if my earlier statement regarding begin() and end() is good. The standard explicitly allows overloads in the std namespace though implementing the functions in Eigen's namespace would work as well due to Koenig lookup. Personally, I prefer not to mess with the std namespace.
Comment 5 Thomas Flynn 2013-07-03 06:23:32 UTC
Hey Hauke,

What happened with the conversation at http://listengine.tuxfamily.org/lists.tuxfamily.org/eigen/2010/01/msg00021.html ?

It seemed like you guys were seriously discussing putting iterators in a couple of years ago.
Comment 6 Hauke Heibel 2013-07-03 09:12:13 UTC
Hi Thomas,

Nobody really found the time to implement iterators. Thank you anyways for bringing up that link again. I totally forgot to think about the impact of the memory layout on iterators.

As I have mentioned recently on the mailing list, I wrote iterators for images a few weeks ago and these are almost identical to iterators for matrices. I am going to attach 2 files which can be used as building block for writing iterators for Eigen::Matrix/Array.

One of the two files I am attaching contains an IteratorFacade inspired by boost (http://www.boost.org/doc/libs/1_54_0/libs/iterator/doc/iterator_facade.html) but without any boost dependency since we are trying to prevent this in Eigen.

The second file contains code for 2D matrix index arithmetic.

The rest of the iterators should be quite easy to implement but we still need somebody to step up.

I am always willing to review code but have unfortunately little time to do something for Eigen at the moment.

Regards,
Hauke
Comment 7 Hauke Heibel 2013-07-03 09:12:57 UTC
Created attachment 366 [details]
A CRTP base class which can be used to implement standard conforming iterators.
Comment 8 Hauke Heibel 2013-07-03 09:13:33 UTC
Created attachment 367 [details]
Three functions for 2D index arithmetic.
Comment 9 Hauke Heibel 2013-07-03 09:16:12 UTC
Just one more comment. The base class simply exists because much of iterator implementation is pure boiler plate. The base class reduces the task of writing an iterator to inheriting from the base class and to implementing 6 functions for random access iterators.
Comment 10 Christoph Hertzberg 2014-06-16 13:09:52 UTC
If we implement this, I think it would be nice to also support .colwise() and .rowwise() iterators to traverse the columns or rows of a 2d object:

  for(auto col = A.colwise().begin(); col != A.colwise().end(); ++col)
    // do something with col

For directly using iterators on 2d objects we need to decide if they shall be forbidden (i.e. only be allowed for objects that are 1d at compile time) or if we traverse elements according to the object's storage order.
Comment 11 Gael Guennebaud 2014-06-16 14:18:13 UTC
Nice idea. For 2D objects, once we got a "reshape" implementation, A.asLinearVector().begin()/.end() would do the job explicitly. Perhaps that's nicer than silently allowing to iterate over all elements because there will always be the confusion of whether A.begin()/end() iterates over all elements or over columns/rows.
Comment 12 Andrew Hundt 2015-06-16 20:26:37 UTC
I recommend the syntax armadillo uses which can remove the ambiguity described by Gael.

From http://arma.sourceforge.net/docs.html

"
.begin()	 
iterator referring to the first element
.end()	 
iterator referring to the past-the-end element
 
.begin_row( row_number )	 
iterator referring to the first element of the specified row
.end_row( row_number )	 
iterator referring to the past-the-end element of the specified row
 
.begin_col( col_number )	 
iterator referring to the first element of the specified column
.end_col( col_number )	 
iterator referring to the past-the-end element of the specified column
"
Comment 13 Gael Guennebaud 2015-06-16 21:34:12 UTC
I was rather thinking about iterators on rows or columns and not on the coefficients of a row/columns. For instance *(A.beginRow()) would be equivalent to A.row(0).

For begin_row(row_number) as in Armadillo we have the row/col/block API for that. For instance:

  A.row(i).begin()/A.row(i).end()

  A.middleRows(10).begin()/A.middleRows(10).end()
Comment 14 patrikhuber 2017-08-20 14:35:00 UTC
Hi all,
Let me express my interest for STL compatible iterators in Eigen too, and I think the suggestions in this thread are great.
Apart from the use cases mentioned like looping over matrices and use C++11 range-based for-loops, my particular use case today (that ended in me finding this bug report) was that I wanted to apply std::partial_sum to an Eigen::VectorXf, i.e. do something like:

VectorXf eigenvalues = ... // coming form somewhere else
VectorXf cum_sum;
std::partial_sum(std::begin(eigenvalues), std::end(eigenvalues), std::begin(cum_sum));
Comment 15 Erik Snider 2018-09-29 19:37:34 UTC
I am also interested in STL iterators for Eigen containers. I'd love to be able to use Eigen containers with the standard <algorithm> functions, It would also be a great convenience to be able to initialize Eigen containers from iterators. For example:

std::vector<double> v1{1, 2, 3, 4};
Eigen::VectorXd v2{v1.begin(), v1.end()};

These features would make it easier to introduce Eigen into existing projects that already make heavy use of STL containers.
Comment 16 Gael Guennebaud 2018-09-30 20:13:27 UTC
Taking an iterator pair (or range) as ctor's input is a different, almost unrelated, issue. Better open a new entry for that.
Comment 17 Gael Guennebaud 2018-09-30 20:44:18 UTC
Now that we have reshaping implemented, we can eventually implement STL compatible iterators. All we have to do is converge on the API. I propose to enable them on 1D expressions only as STL iterators are intrinsically linear. We would thus write stuff like:

VectorXd v;
MatrixXd A;
RowMatrix B;
for(auto x : v) {...}
for(auto x : A.col(j)) {...}
for(auto x : A.row(i)) {...}
for(auto x : A.reshape()) {...}
for(auto x : B.reshape()) {...}

The last two lines iterate over all elements in column-major order, so the loop on A will be fast, but the on of B will be slow :( To make it fast regardless of the underlying storage order, you currently would have to write:

for(auto x : B.reshape<AutoOrder>(fix<1>,AutoSize)) {...}

a bit verbose. This is perhaps a good use case for allowing AutoOrder on reshape():

for(auto x : B.reshape<AutoOrder>()) {...}

not too bad.

Then I'd also like to support iterators on rows or columns. Ideally I would write:

for(auto r : A.rows()) {...}

but Matrix::rows() is already taken. The existing rowwise()/colwise() proxy (as suggested in comment #10) does not work well in this context:

for(auto r : A.rowwise()) {...}

Recall that in Eigen "A.rowwise()" reads "for each row of A", and thus the previous loop reads: "for each r in for each row of A"... so I would rather expect this loop to go through all coefficients of A in a row-major order, as accomplished by:

for(auto r : A.reshape<RowMajor>()) {...}

So I guess we need to introduce a new proxy for that, maybe allRows()/allCols():

for(auto r : A.allRows()) {...}
Comment 18 Gael Guennebaud 2018-10-01 21:32:11 UTC
You're all very welcome to comment on this initial implementation: https://bitbucket.org/eigen/eigen/pull-requests/519
Comment 19 Gael Guennebaud 2018-10-08 20:34:47 UTC
PR merged.

Note You need to log in before you can comment on or make changes to this bug.