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);
To support C++11 range-based for loops, begin and end need to be member functions.
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.
You're right, that would be sufficient.
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.
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.
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
Created attachment 366 [details] A CRTP base class which can be used to implement standard conforming iterators.
Created attachment 367 [details] Three functions for 2D index arithmetic.
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.
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.
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.
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 "
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()
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));
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.
Taking an iterator pair (or range) as ctor's input is a different, almost unrelated, issue. Better open a new entry for that.
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()) {...}
You're all very welcome to comment on this initial implementation: https://bitbucket.org/eigen/eigen/pull-requests/519
PR merged.
-- GitLab Migration Automatic Message -- This bug has been migrated to gitlab.com's GitLab instance and has been closed from further activity. You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.com/libeigen/eigen/issues/231.