Iterator requirements for a fake container supporting C++11 range-based for

Question

Around a year ago, I wrote this Stack Overflow answer where I suggested an idea to replace deeply nested loops with a single iterable virtual-container object that "contains" all the indices.

The following is an implementation, but I'm still not that familiar with C++11 at the moment, so I thought I'd ask for a review.

Key points are...

1. Although this seems to work in GCC, that doesn't necessarily mean I've implemented all the interfaces I need for an iterator - what have I missed?

2. I wasn't confident about all the parameter-passing choices - where to use rvalue references, or lvalue references, pass-by-value, or letting the classes generate default methods. Have I made bad choices? Is it OK to pass std::initializer_list by value? Should loopnest_state have copy/move constructors and assignments?

3. The "elements" in the "container" obviously don't really exist. Instead, each iterator contains a unique_ptr to a computed element value - the unique_ptr is null for end. The computed element value is mutated when the iterator is incremented, so it still references the same object, just with a new state. Is this sensible? Should I try to avoid the extra heap allocation, get rid of the unique_ptr, and build the computed value into the iterator?

Anything else is welcome.

class loopnest;
class loopnest_iterator;
class loopnest_state;

class loopnest_state
{
  friend class loopnest_iterator;

  private:
    const std::vector<unsigned> &m_counts;
          std::vector<unsigned>  m_indices;

    unsigned m_depth;

    bool step_next ()
    {
      m_depth = m_indices.size ();

      while (m_depth > 0)
      {
        m_depth--;

        unsigned &l_index (m_indices [m_depth]);

        l_index++;
        if (l_index != m_counts [m_depth])  return true;
        l_index = 0UL;
      }

      return false;
    }

  public:
    loopnest_state (const std::vector<unsigned> &p_counts,
                    const std::vector<unsigned> &p_indices,
                          unsigned               p_depth   )
      : m_counts (p_counts), m_indices (p_indices), m_depth (p_depth)
    {
    }

    loopnest_state (const std::vector<unsigned>  &p_counts,
                          std::vector<unsigned> &&p_indices,
                          unsigned                p_depth   )
      : m_counts (p_counts), m_indices (std::move (p_indices)), m_depth (p_depth)
    {
    }

    unsigned Outermost_Changed () const  {  return (~m_depth ? m_depth : 0);  }
    unsigned Inc_Depth         () const  {  return m_depth;  }
    unsigned Nest_Depth        () const  {  return m_counts.size ();  }

    const std::vector<unsigned> &Indices () const  {  return m_indices;  }

    unsigned size       ()           const  {  return m_indices.size ();  }
    unsigned operator[] (unsigned p) const  {  return m_indices [p];  }

    bool is_first () const  {  return m_depth == ~0UL;  }

    bool operator== (const loopnest_state &p)
    {
      if (m_depth != p.m_depth) return false;
      if (m_depth == ~0UL)  return true;

      for (unsigned i = 0UL; i < m_indices.size (); ++i)
      {
        if (m_indices [i] != p.m_indices [i])  return false;
      }

      return true;
    }

    bool operator!= (const loopnest_state &p)
    {
      return !operator== (p);
    }
};

class loopnest_iterator
{
  private:
    std::unique_ptr<loopnest_state> m_state;

  public:
    loopnest_iterator ()
    {
    }

    loopnest_iterator (std::unique_ptr<loopnest_state> &&p_state)
      : m_state (std::move (p_state))
    {
    }

    loopnest_iterator (loopnest_state *p_state)
      : m_state (p_state)
    {
    }

    void operator++ ()
    {
      if (m_state && !((*m_state).step_next ()))  m_state = nullptr;
    }

    bool operator== (const loopnest_iterator &p) const
    {
      if (m_state == p.m_state)  return true;
      if ((!m_state) || (!p.m_state))  return false;
      return m_state->operator== (*p.m_state);
    }

    bool operator!= (const loopnest_iterator &p) const
    {
      return !operator== (p);
    }

    const loopnest_state &operator*  () const  {  return *m_state;  }
};

class loopnest
{
  public:
    typedef loopnest_iterator const_iterator;

  private:
    std::vector<unsigned>  m_counts;

    //  If any count is zero, there are no cases to iterate over.
    bool begin_is_end () const
    {
      bool l_Result = false;

      for (auto i : m_counts)
      {
        if (i == 0)  l_Result = true;
      }

      return l_Result;
    }

  public:
    loopnest ()  {}

    loopnest (std::vector<unsigned> p_counts)
      : m_counts (std::move (p_counts))
    {
    }

    loopnest (std::vector<unsigned> &&p_counts)
      : m_counts (std::move (p_counts))
    {
    }

    loopnest (std::initializer_list<unsigned> p_counts)
      : m_counts (p_counts)
    {
    }

    const_iterator begin () const
    {
      if (begin_is_end ())  return const_iterator ();
      return const_iterator (new loopnest_state (m_counts, std::vector<unsigned> (m_counts.size (), 0UL), ~0UL));
    }

    const_iterator end () const
    {
      return const_iterator ();
    }
};

Answer 1

1. There are standard requirements for class to satisfy iterator model. They are needed to your class to be guaranteed to operate with stl and stl-compatible algorithms. But if you just need it to work in range-based for loop, your implementation is enough. Even operator== is not needed.

2. Initializer list is ok to pass by value, because it is just a pair of pointers or something similar. R-value references are mostly used in move constructors and assigments. In other cases just use copy instead of these functions:

   loopnest (std::vector<unsigned> &&p_counts)

   loopnest_iterator (std::unique_ptr<loopnest_state> &&p_state)

   loopnest_state (const std::vector<unsigned> &p_counts, std::vector<unsigned> &&p_indices, unsigned p_depth )

   Caller will deside if he is ok with copy or move: loopnest(counts) / loopnest(move(counts))

   Copy/move assignments are useful for classes with resources. loopnest_state have resources in form of vectors. But vectors are good at managing their resources, so compiler-defined constructors/assigments will suffice. Just be aware of some compilers are old enough to not to generate move constructors/assigments.

3. In C++ classes have value semantics, which means instances fully can be held on the stack or as memeber in memory occuppied by another instance. This is preffered way and pointers should only be used in situations where heap allocation / indirection is inevitable. So yes, element should be direct member of iterator, not an unique_ptr.

Other observations.

I'm not sure user will need counts inside loop, consider return just indices from iterator.

There is still allocation (and, hence, indirection) in loopnest_state in form of vectors. Vectors are needed for a user to be able to created arbitrary-depth loops. The same result can be achived with touples, but it will require some heavy variadic metaprogramming.