6
\$\begingroup\$

I needed a general-purpose function that accepts some sequence_container<sequence_container<T>> and iterates all permutations of the inner container. To be more precise, the outer sequence_container should be described by an iterator pair to easily allow selecting parts of it.

For example {{1,2},{},{3,4}} shall iterate {1,?,3},{1,?,4},{2,?,3},{2,?,4}. The function provides a callback to deal with each of these 4 permutations. The callback has two parameters:

  • a vector of indices, giving in each iteration one of {0,-1,0},{0,-1,1},{1,-1,0},{1,-1,1} in above example
  • a vector of values, giving in each iteration one of {1,?,3},{1,?,4},{2,?,3},{2,?,4} in above example

Through -1, the user can check whether the value should be checked or not. This might be helpful if the original indices should be retained.

I have written the following code that accomplishes it. It works both for const and non-const containers, albeit only const containers should actually be fine since we cannot change anything in the container so far. Usage is nestedFor::run(beginIterator, endIterator, callback).

Roast me, glad for any feedback!

#include <iterator>
#include <vector>

namespace nestedFor
{
    // helper to check if an iterator is const
    template<typename Iterator>
    struct isConstIterator
    {
        typedef typename std::iterator_traits<Iterator>::pointer pointer;
        static const bool value =
        std::is_const<typename std::remove_pointer<pointer>::type>::value;
    };

    // helper to get const_iterator or iterator, whatever applicable, for nested type
    template<typename OuterItT, typename=void>
    struct retrieveConstCorrectIterator
    {
        using iterator = typename OuterItT::value_type::iterator;
    };

    template<typename OuterItT>
    struct retrieveConstCorrectIterator<OuterItT, std::enable_if_t<isConstIterator<OuterItT>::value>>
    {
        using iterator = typename OuterItT::value_type::const_iterator;
    };

    // given a container<container<T>>, loops all combinations of inner vector;
    // Func should be of type:
    // void func(const std::vector<int>& indices, std::vector<T>& values);
    // in each iteration, func is called with indices showing the position
    // and respective values;
    // note that empty inner vectors are allowed, the respective index is -1, then
    template<typename OuterItT, typename Func>
    void run(OuterItT begin, OuterItT end, Func func)
    {
        using InnerItT = typename retrieveConstCorrectIterator<OuterItT>::iterator;
        using ItVecT = std::vector<InnerItT>;
        using ItVecItT = typename ItVecT::iterator;

        // idx -1 means that there is no valid entry
        using IdxVecT = std::vector<int>;
        using ValueVecT = std::vector<typename InnerItT::value_type>;
        using IdxVecItT = typename IdxVecT::iterator;
        using ValueVecItT = typename ValueVecT::iterator;

        const typename std::iterator_traits<OuterItT>::difference_type numInnerVecs =
        std::distance(begin, end);

        IdxVecT idxVec(numInnerVecs, -1);
        ValueVecT valueVec(numInnerVecs);

        ItVecT runIterators(numInnerVecs), startIterators(numInnerVecs), endIterators(numInnerVecs);
        ItVecItT runItVecIt = runIterators.begin(),
        startItVecIt = startIterators.begin(),
        endItVecIt = endIterators.begin();
        IdxVecItT runIdxIterators = idxVec.begin(),
        runValueIterators = valueVec.begin();

        for(OuterItT it = begin; it != end; ++it, ++runItVecIt, ++startItVecIt, ++endItVecIt,
            ++runIdxIterators, ++runValueIterators)
        {
            *runItVecIt = it->begin();
            *startItVecIt = it->begin();
            *endItVecIt = it->end();

            if(it->begin() == it->end())
            {
                *runIdxIterators = -1;
                // value idx undefined then
            }
            else
            {
                *runIdxIterators = 0;
                *runValueIterators = *(*startItVecIt);
            }
        }

        while(true)
        {
            func(idxVec, valueVec);

            ItVecItT itToMove = runIterators.begin(),
            itToMoveStart = startIterators.begin(),
            itToMoveEnd = endIterators.begin();

            IdxVecItT idxIt = idxVec.begin();
            ValueVecItT valueIt = valueVec.begin();

            bool bigBreak = false;
            ++*itToMove;

            if(*itToMove != *itToMoveEnd)
            {
                ++*idxIt;
                *valueIt = **itToMove;
            }

            while(*itToMove == *itToMoveEnd)
            {
                *itToMove = *itToMoveStart;

                if(*itToMove != *itToMoveEnd)
                {
                    *idxIt = 0;
                    *valueIt = **itToMoveStart;
                }

                ++itToMove;
                ++itToMoveStart;
                ++itToMoveEnd;
                ++idxIt;
                ++valueIt;

                if(itToMove == runIterators.end())
                {
                    bigBreak = true;
                    break;
                }

                if(*itToMove != *itToMoveEnd)
                {
                    ++*itToMove;
                    ++*idxIt;
                    *valueIt = **itToMove;
                }
            };

            if(bigBreak)
                break;

        }
    }
}

#endif
\$\endgroup\$
  • \$\begingroup\$ @Deduplicator yes, good point. The function accepts iterators but a bare array won't work... std::array would, though \$\endgroup\$ – IceFire Oct 3 '18 at 15:42
2
\$\begingroup\$
  • Naming. What run iterates over is known as a direct (or Cartesian) product. It seems that namespace direct_product is more descriptive than nestedFor.

  • Parallel arrays (runIterators, startIterators, endIterators) remind me good old days of Fortran. It is definitely an anti-idiomatic C++. Consider a single vector of

    struct iterators {
        Iter runIterator,
        Iter startIterator,
        Iter endIterator,
        // Constructors, assignment, increment, and anything else which is needed
    }
    

    You will need much less lines to express the increment a vector idiom.

  • I strongly recommend to use a class instead of namespace. This way an initialization loop naturally becomes a constructor, and the actual loop becomes unnecessary. Define an iterator over states of the product, operator++ and operator* for it. This lifts the callback out of your responsibility, and enables the client to write

    direct_product dp{....};
    for (auto it = dp.begin(); it != dp.end(); ++it) {
        fun(*it);
    }
    

    or even a range-based loop.

  • Kudos for not resorting to recursion.

\$\endgroup\$

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.