Re: [Boost-users] Any "2D" iterator?

Subject: Re: [Boost-users] Any "2D" iterator?
From: Changsheng Jiang (jiangzuoyan_at_[hidden])
Date: 2010-09-19 20:57:56

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_at_[hidden]<legalize%2Bjeeves_at_[hidden]>
> wrote:

> [Please do not mail me a copy of your followup]
>
> boost-users_at_[hidden] spake the secret code
> <AANLkTi=RiR=piq5CzT8kNchjht=KR1co11OsVeF1DaqC_at_[hidden]> thusly:
>
> >On Sat, Sep 18, 2010 at 10:37 AM, TONGARI <tongari95_at_[hidden]> wrote:
> >>
> >>
> >> 2010/9/17 <lfrfly_at_[hidden]>
> >>>
> >>> 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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>