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
