Any "2D" iterator?
I have on several occasions encountered situations in which it would be advantageous to view a container of containers as a flat sequence. It seems like there ought to be a natural way to do this using an iterator class. For instance, if you have vector<list<T>> v, you ought to be able to design an iterator which begins at v.begin()->begin() and runs until v.end(), over every element of every list. Does such a thing exist in Boost, or is it planned in the near future?
On Fri, Sep 17, 2010 at 11:15 AM, <lfrfly@icqmail.com> wrote:
I have on several occasions encountered situations in which it would be advantageous to view a container of containers as a flat sequence. It seems like there ought to be a natural way to do this using an iterator class. For instance, if you have vector<list<T>> v, you ought to be able to design an iterator which begins at v.begin()->begin() and runs until v.end(), over every element of every list.
Does such a thing exist in Boost, or is it planned in the near future?
I'd be interested as well. Conversely, I just finished writing an iterator that does the opposite. It takes a flat sequence like vector<int> and allows one to iterate a "2d view" of it. So if vector<int> represents a 2D array of size 6x6, you could iterate a 3x3 view of it. I think both iterators would make a good addition to Boost.Iterators (or hopefully they already exist!) --Michael Fawcett
2010/9/17 <lfrfly@icqmail.com>
It seems like there ought to be a natural way to do this using an iterator class.
I don't think that'll be a good solution to this problem, not efficient enough. Using this approach would introduce redundant overhead of checking equality of iterators.
Does such a thing exist in Boost, or is it planned in the near future?
No, as I know, there's no such thing in Boost. If you really want one, boost::iterator_facade can help you. For myself, I'd prefer making some generic algorithms like for_each_in_depth<n>(range, func) instead.
On Sat, Sep 18, 2010 at 10:37 AM, TONGARI <tongari95@gmail.com> wrote:
2010/9/17 <lfrfly@icqmail.com>
It seems like there ought to be a natural way to do this using an iterator class.
I don't think that'll be a good solution to this problem, not efficient enough.
Whether it's efficient "enough" really depends on the OP's requirements. However, if you're worried about efficiency you should look up Matt Austern's 1998 paper "Segmented Iterators and Hierarchical Algorithms" -- Dave Abrahams BoostPro Computing http://www.boostpro.com
[Please do not mail me a copy of your followup] boost-users@lists.boost.org spake the secret code <AANLkTi=RiR=piq5CzT8kNchjht=KR1co11OsVeF1DaqC@mail.gmail.com> thusly:
On Sat, Sep 18, 2010 at 10:37 AM, TONGARI <tongari95@gmail.com> wrote:
2010/9/17 <lfrfly@icqmail.com>
It seems like there ought to be a natural way to do this using an iterator class.
I don't think that'll be a good solution to this problem, not efficient enough.
Whether it's efficient "enough" really depends on the OP's requirements. However, if you're worried about efficiency you should look up Matt Austern's 1998 paper "Segmented Iterators and Hierarchical Algorithms"
It was an interesting read and not hard to implement. <http://lafstern.org/matt/segmented.pdf> -- "The Direct3D Graphics Pipeline" -- DirectX 9 draft available for download <http://legalizeadulthood.wordpress.com/the-direct3d-graphics-pipeline/> Legalize Adulthood! <http://legalizeadulthood.wordpress.com>
I have the same problem, to view a map (k1->k2->v) as a sequence(k1, k2) -> v. With iterator_facade and iterator_transform, the problem solved verbosely. in the code, Begin and End is unary functors applied to first iterator to get second begin, end iterator. template <class F, class S, class Begin, class End, class Tag=boost::bidirectional_traversal_tag> class chain_iter : public boost::iterator_facade< chain_iter<F, S, Begin, End, Tag>, std::pair<F, S>, Tag, std::pair<F, S> > { public: typedef F first_type; typedef S second_type; typedef std::pair<first_type, second_type> value_type; typedef value_type reference; // no, no reference to temporary chain_iter() {} chain_iter(const F &f, const F &f_end, const S &s) : m_first(f), m_first_end(f_end), m_second(s) { normalize(); } chain_iter(const chain_iter &r) : m_first(r.m_first), m_first_end(r.m_first_end), m_second(r.m_second) { normalize(); } private: friend class boost::iterator_core_access; void normalize() { while (m_first != m_first_end && m_second == End()(m_first)) { ++m_first; if (m_first != m_first_end) m_second = Begin()(m_first); } } void increment() { assert(m_first != m_first_end); ++m_second; normalize(); } void decrement() { while (m_second == Begin()(m_first)) { --m_first; m_second = End()(m_first); } --m_second; } reference dereference() const { return std::make_pair(m_first, m_second); } bool equal(const chain_iter &r) const { if (m_first == m_first_end) { return r.m_first == r.m_first_end; } return m_first == r.m_first && m_second == r.m_second; } F m_first; F m_first_end; S m_second; }; Changsheng Jiang On Sun, Sep 19, 2010 at 22:57, Richard <legalize+jeeves@mail.xmission.com<legalize%2Bjeeves@mail.xmission.com>
wrote:
[Please do not mail me a copy of your followup]
boost-users@lists.boost.org spake the secret code <AANLkTi=RiR=piq5CzT8kNchjht=KR1co11OsVeF1DaqC@mail.gmail.com> thusly:
On Sat, Sep 18, 2010 at 10:37 AM, TONGARI <tongari95@gmail.com> wrote:
2010/9/17 <lfrfly@icqmail.com>
It seems like there ought to be a natural way to do this using an
iterator
class.
I don't think that'll be a good solution to this problem, not efficient enough.
Whether it's efficient "enough" really depends on the OP's requirements. However, if you're worried about efficiency you should look up Matt Austern's 1998 paper "Segmented Iterators and Hierarchical Algorithms"
It was an interesting read and not hard to implement.
<http://lafstern.org/matt/segmented.pdf> -- "The Direct3D Graphics Pipeline" -- DirectX 9 draft available for download <http://legalizeadulthood.wordpress.com/the-direct3d-graphics-pipeline/>
Legalize Adulthood! <http://legalizeadulthood.wordpress.com>
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (6)
-
Changsheng Jiang -
Dave Abrahams -
legalize+jeeves＠mail.xmission.com -
lfrfly＠icqmail.com -
Michael Fawcett -
TONGARI