2
\$\begingroup\$

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 ();
    }
};
\$\endgroup\$
1
\$\begingroup\$
  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.

\$\endgroup\$
  • \$\begingroup\$ The vector is needed for the actual use I finally decided to write it for, where the depth of nesting isn't known until runtime. I spotted a silly mistake in that loopnest_state::operator== etc aren't marked const, though loopnest_iterator::operator== etc are marked const. That suggests loopnest_iterator::operator== must be making a temporary copy of the loopnest_state instance, though I haven't checked. The reason for the unique_ptr was to avoid having the vector etc in the end iterator. But it does seem likely to be a pessimization. \$\endgroup\$ – Steve314 Feb 11 '15 at 9:42
  • \$\begingroup\$ Personally, my style preference is more towards using a single iterator that knows when it's exhausted unless you really need to pick an arbitrary position as the end of your iteration, but c++ iterators are a generalization of pointers not the OOP pattern - which is a slight pain sometimes when you don't really have an element to point to. \$\endgroup\$ – Steve314 Feb 11 '15 at 9:45
  • \$\begingroup\$ Those functions with the rvalue references are constructors, and meant to move-construct all or some part of an instance - e.g. the loopnest_iterator constructor gets it's loopnest_state instance from a temporary that loopnest::begin creates purely to initialize it. The extra loopnest constructors (beyond the initializer list) though are probably badly judged - for initializing from existing containers it should probably accept begin and end iterators (any container type) and (optionally) a lambda to extract the counts. \$\endgroup\$ – Steve314 Feb 11 '15 at 10:00
  • \$\begingroup\$ If the depth is not known at runtime, vector indeed is the choice, but I can hardly imagine such a situation. In initial stackoverflow question person wanted to get rid from deep nested loops, this implies depth is known in compile time. \$\endgroup\$ – GeniusIsme Feb 11 '15 at 12:06
  • \$\begingroup\$ Functions with r-values are constructors, but they are not "move constructors", ie do not move from instance of the same type. Those types already know how to move themselves, pass them by value is enough. \$\endgroup\$ – GeniusIsme Feb 11 '15 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.