7
\$\begingroup\$

Motivated by some SO quesitons [1, 2] I made an attempt at implementing a custom container with a bi-directional custom iterator for iterating over all combinations of elements from multiple sets.

I am quite unfamiliar with the topic, so any feedback on design (including naming) and performance is very appreciated.

Some implementation details:

  • The container does not store all the combinations
  • Combinations are calculated on the fly when iterator is incremented or decremented
  • Combination is represented as a vector of iterators: one for each set
  • When combinations iterator is dereferenced or arrow operator is called, combination is returned by value to avoid dangling

combinations.hpp

#ifndef COMBINATIONS_HPP
#define COMBINATIONS_HPP

#include <iterator>
#include <limits>
#include <vector>

// Precondition: all sets between iterators should be non-empty:
// contain at least 1 element
template <typename SetOfSetsIter>
class combinations
{
public:
    typedef combinations<SetOfSetsIter> Combination_type;
    typedef typename std::iterator_traits<SetOfSetsIter>::value_type Set;
    typedef typename std::vector<typename Set::const_iterator> Combination;

    typedef Combination value_type;
    typedef long long difference_type;
    typedef size_t size_type;

    class const_iterator
    {
    public:
        typedef std::bidirectional_iterator_tag iterator_category;
        typedef typename Combination_type::difference_type difference_type;
        typedef typename Combination_type::value_type value_type;
        typedef const Combination reference;
        typedef const Combination pointer;

        const_iterator()
        {}
        const_iterator(const const_iterator& other)
            : first_(other.first_)
            , last_(other.last_)
            , combination_(other.combination_)
        {}
        const_iterator(SetOfSetsIter first, SetOfSetsIter last)
            : first_(first)
            , last_(last)
        {
            for(SetOfSetsIter it = first_; it != last_; ++it)
                combination_.push_back(it->begin());
        }
        static const_iterator make_end(SetOfSetsIter first, SetOfSetsIter last)
        {
            const_iterator res;
            res.first_ = first;
            res.last_ = last;
            SetOfSetsIter it = first;
            res.combination_.push_back(it->end());
            for(++it; it != last; ++it)
                res.combination_.push_back(--it->end());
            return res;
        }
        ~const_iterator()
        {}
        const_iterator& operator=(const const_iterator other)
        {
            swap(*this, other);
            return *this;
        }
        bool operator==(const const_iterator& other) const
        {
            return combination_ == other.combination_ &&
                   first_ == other.first_ && last_ == other.last_;
        }
        bool operator!=(const const_iterator& other) const
        {
            return !(*this == other);
        }
        const_iterator& operator++()
        {
            typename Combination::iterator combIt = combination_.begin();
            for(SetOfSetsIter it = first_; it != last_; ++it, ++combIt)
            {
                if(++(*combIt) != it->end())
                    return *this;
                *combIt = it->begin();
            }
            set_to_end_();
            return *this;
        }
        const_iterator& operator--()
        {
            typename Combination::iterator combIt = combination_.begin();
            for(SetOfSetsIter it = first_; it != last_; ++it, ++combIt)
            {
                if(*combIt != it->begin())
                {
                    --(*combIt);
                    return *this;
                }
                *combIt = --it->end();
            }
            set_to_begin_();
            return *this;
        }
        Combination operator*() const
        {
            return combination_;
        }
        Combination operator->() const
        {
            return combination_;
        }
        friend void swap(
            const_iterator& first,
            const_iterator& second) // nothrow
        {
            std::swap(first.first_, second.first_);
            std::swap(first.last_, second.last_);
            std::swap(first.combination_, second.combination_);
        }
        void swap(Combination_type other)
        {
            swap(*this, other);
        }

    private:
        void set_to_end_()
        {
            typename Combination::iterator combIt = combination_.begin();
            SetOfSetsIter it = first_;
            *(combIt++) = (it++)->end();
            for(; it != last_; ++it, ++combIt)
                *combIt = --it->end();
        }
        void set_to_begin_()
        {
            typename Combination::iterator combIt = combination_.begin();
            for(SetOfSetsIter it = first_; it != last_; ++it, ++combIt)
                *combIt = it->begin();
        }
        friend class combinations<SetOfSetsIter>;

    private:
        SetOfSetsIter first_;
        SetOfSetsIter last_;
        Combination combination_;
    };

    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    combinations()
    {}
    combinations(SetOfSetsIter first, SetOfSetsIter last)
        : first_(first)
        , last_(last)
    {}
    combinations(const combinations<SetOfSetsIter>& other)
        : first_(other.first_)
        , last_(other.last_)
    {}
    ~combinations()
    {}
    combinations& operator=(const combinations<SetOfSetsIter>& other)
    {
        swap(*this, other);
        return *this;
    }
    bool operator==(const combinations<SetOfSetsIter>& other) const
    {
        return first_ == other.first_ && last_ == other.last_;
    }
    bool operator!=(const combinations<SetOfSetsIter>& other) const
    {
        return !(*this == other);
    }
    const_iterator begin() const
    {
        return const_iterator(first_, last_);
    }
    const_iterator cbegin() const
    {
        return begin();
    }
    const_iterator end() const
    {
        return const_iterator::make_end(first_, last_);
    }
    const_iterator cend() const
    {
        return end();
    }
    const_reverse_iterator rbegin() const
    {
        return crbegin();
    }
    const_reverse_iterator crbegin() const
    {
        return const_reverse_iterator(end());
    }
    const_reverse_iterator rend() const
    {
        return crend();
    }
    const_reverse_iterator crend() const
    {
        return const_reverse_iterator(begin());
    }
    friend void swap(
        combinations<SetOfSetsIter>& first,
        combinations<SetOfSetsIter>& second) // nothrow
    {
        std::swap(first.first_, second.first_);
        std::swap(first.last_, second.last_);
    }
    void swap(combinations<SetOfSetsIter> other)
    {
        swap(*this, other);
    }
    size_type size() const
    {
        size_type result = 1;
        for(SetOfSetsIter it = first_; it != last_; ++it)
            result *= it->size();
        return result;
    }
    size_type max_size() const
    {
        return std::numeric_limits<size_type>::max();
    }
    bool empty() const
    {
        return first_ == last_;
    }

private:
    SetOfSetsIter first_;
    SetOfSetsIter last_;
};

template <typename SetOfSets>
combinations<typename SetOfSets::const_iterator>
make_combinations(const SetOfSets& data)
{
    return combinations<typename SetOfSets::const_iterator>(
        data.cbegin(), data.cend());
}

#endif // COMBINATIONS_HPP

main.cpp

#include <algorithm>
#include <iostream>

#include "combinations.hpp"

int main()
{
    typedef std::vector<int> Set;
    typedef std::vector<Set> SetOfSets;
    typedef SetOfSets::const_iterator SetOfSetsCIt;
    const SetOfSets data = {{2, 4}, {1, 3, 8}, {7, 5}};
    {
        std::cout << "First to last-------" << std::endl;
        typedef combinations<SetOfSetsCIt> Combinations;
        Combinations cmbs = make_combinations(data);
        {
            std::cout << "Forward:" << std::endl;
            for(const auto& combination : cmbs)
            {
                for(const auto& elemIt : combination)
                    std::cout << *elemIt << " ";
                std::cout << std::endl;
            }
        }
        {
            std::cout << "Reverse:" << std::endl;
            for(Combinations::const_reverse_iterator combIt = cmbs.crbegin();
                combIt != cmbs.crend();
                ++combIt)
            {
                for(const auto& elemIt : *combIt)
                    std::cout << *elemIt << " ";
                std::cout << std::endl;
            }
        }
    }
    {
        std::cout << "Last to first-------" << std::endl;
        typedef SetOfSets::const_reverse_iterator SetOfSetsCRIt;
        typedef combinations<SetOfSetsCRIt> Combinations;
        Combinations cmbs(data.crbegin(), data.crend());
        {
            std::cout << "Forward:" << std::endl;
            for(Combinations::const_iterator cmbIt = cmbs.begin();
                cmbIt != cmbs.end();
                ++cmbIt)
            {
                Combinations::Combination c = *cmbIt;
                std::reverse(c.begin(), c.end());
                for(const auto& it : c)
                    std::cout << *it << " ";
                std::cout << std::endl;
            }
        }
        {
            std::cout << "Reverse:" << std::endl;
            for(Combinations::const_reverse_iterator cmbIt = cmbs.crbegin();
                cmbIt != cmbs.crend();
                ++cmbIt)
            {
                Combinations::Combination c = *cmbIt;
                std::reverse(c.begin(), c.end());
                for(const auto& it : c)
                    std::cout << *it << " ";
                std::cout << std::endl;
            }
        }
    }
}

Output of main.cpp:

First to last-------
Forward:
2 1 7 
4 1 7 
2 3 7 
4 3 7 
2 8 7 
4 8 7 
2 1 5 
4 1 5 
2 3 5 
4 3 5 
2 8 5 
4 8 5 
Reverse:
4 8 5 
2 8 5 
4 3 5 
2 3 5 
4 1 5 
2 1 5 
4 8 7 
2 8 7 
4 3 7 
2 3 7 
4 1 7 
2 1 7 
Last to first-------
Forward:
2 1 7 
2 1 5 
2 3 7 
2 3 5 
2 8 7 
2 8 5 
4 1 7 
4 1 5 
4 3 7 
4 3 5 
4 8 7 
4 8 5 
Reverse:
4 8 5 
4 8 7 
4 3 5 
4 3 7 
4 1 5 
4 1 7 
2 8 5 
2 8 7 
2 3 5 
2 3 7 
2 1 5 
2 1 7 
\$\endgroup\$
1
\$\begingroup\$

Whenever you need to write an iterator, start out with Boost.Iterator. It has a iterator_facade and iterator_adaptor class that makes short (and accurate) work of it.

If you never store the combinations at all, but compute them on the fly, what you really have is a Range Adaptor. If you have a function that maps input (index?) to outputs, it is quick work to use an existing library to do that. Calculating changes with ++ and −− rather than computing it from scratch is more difficult, and I think can be done with iterator_facade where you just supply increment and decrement functions.

\$\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.