Skip to content

Instantly share code, notes, and snippets.

@Alexhuszagh
Created February 18, 2017 20:12
Show Gist options
  • Save Alexhuszagh/67efb078a82616ed07529ed97586646a to your computer and use it in GitHub Desktop.
Save Alexhuszagh/67efb078a82616ed07529ed97586646a to your computer and use it in GitHub Desktop.
Cartesian Product Implementation in C++
// :copyright: (c) 2017 Alex Huszagh.
// :license: MIT.
/**
* Cartesian product algorithm.
*
* Lazily calculates the cartesian product from a container of containers,
* of either linear (array, vector, set, unordered_set) or associative
* (map, unordered_map, multimap, unordered_multimap) containers.
*
* The code can be used as follows:
*
* std::vector<std::vector<int>> aa = {{1, 2, 3}, {4, 5, 6}};
* product(aa, [](const auto &i) {
* std::cout << "[";
* for (auto j : i) {
* std::cout << j << ", ";
* }
* std::cout << "]" << std::endl;
* });
*
* The above example would print:
* [1, 4, ]
* [1, 5, ]
* [1, 6, ]
* [2, 4, ]
* [2, 5, ]
* [2, 6, ]
* [3, 4, ]
* [3, 5, ]
* [3, 6, ]
*
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the “Software”), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following
* conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/
#include <algorithm>
#include <functional>
#include <vector>
// SFINAE
// ------
template <typename T>
struct is_reference_wrapper: std::false_type
{};
template <typename T>
struct is_reference_wrapper<std::reference_wrapper<T>>: std::true_type
{};
template <typename T>
constexpr bool is_reference_wrapper_v = is_reference_wrapper<T>::value;
template <bool B, typename T, typename F>
using conditional_t = typename std::conditional<B, T, F>::type;
template <bool B, typename T = void>
using enable_if_t = typename std::enable_if<B, T>::type;
template <typename T>
using type_t = typename T::type;
template <typename T>
using value_t = typename T::value_type;
template <typename T>
using iterator_t = typename T::iterator;
template <typename T>
using const_iterator_t = typename T::const_iterator;
template <typename T>
using iterator_value_t = value_t<std::iterator_traits<T>>;
template <typename T>
using reference_t = typename T::reference_type;
template <typename T>
using mapped_t = typename T::mapped_type;
template <typename T>
using list_t = typename T::list_type;
template <typename T>
using matrix_t = typename T::matrix_type;
#define HAS_MEMBER_TYPE(member, name) \
template<typename T> \
class name \
{ \
protected: \
struct U {}; \
typedef conditional_t<std::is_class<T>::value, T, U> V; \
\
struct Fallback \
{ \
struct member {}; \
}; \
\
struct Derived: V, Fallback \
{}; \
\
template <typename C> static char &test(typename C::member*); \
template <typename C> static long &test(...); \
\
public: \
enum { \
value = sizeof(test<Derived>(0)) == sizeof(long) \
}; \
};
HAS_MEMBER_TYPE(mapped_type, has_mapped_type);
template <typename T>
constexpr bool has_mapped_type_v = has_mapped_type<T>::value;
// FUNCTIONS
// ---------
namespace detail
{
// PRODUCT
// -------
/** \brief Helper demangle and product reference types.
*
* Due to the various levels of indirection with our wrapper classes,
* we can have the inner container be a reference, or a value, and the
* `value_type` of that container be a reference, or a value.
*
* Since we want the output to be a vector of reference wrappers,
* appropriately detect when we are using references and when we
* are using values.
*/
template <typename T>
struct ReferenceHelper
{
typedef conditional_t<is_reference_wrapper_v<T>, T, std::reference_wrapper<const T>> type;
typedef type_t<type> container_type;
typedef value_t<container_type> value_type;
typedef const_iterator_t<container_type> iterator;
typedef conditional_t<
is_reference_wrapper_v<value_type>,
value_type,
std::reference_wrapper<const value_type>
> reference_type;
static iterator begin(const container_type &t)
{
return t.begin();
}
static iterator end(const container_type &t)
{
return t.end();
}
};
/** \brief Calculate cartesian product with zero data copies.
*/
template <
typename BidirIter,
typename Function
>
void product_impl(BidirIter first,
BidirIter last,
Function function)
{
typedef ReferenceHelper<iterator_value_t<BidirIter>> Helper;
typedef iterator_t<Helper> Iterator;
typedef reference_t<Helper> Reference;
// sanity check
if (first == last) {
return;
}
// fill vector for function calls
const size_t size = last - first;
std::vector<Iterator> iterators;
std::vector<Reference> values;
iterators.reserve(size);
values.reserve(size);
std::for_each(first, last, [&](const auto &value) {
iterators.emplace_back(--Helper::begin(value));
values.emplace_back(*Helper::begin(value));
});
// iterate over all elements
auto it = first;
while (it >= first) {
const size_t k = it - first;
if (it == last) {
function(values);
--it;
} else if (iterators[k] != --Helper::end(*it)) {
values[k] = *++iterators[k];
++it;
} else {
iterators[k] = --Helper::begin(*it);
--it;
}
}
}
// LINEAR - LINEAR
// ---------------
/** \brief Type detection for linear collection of linear collections.
*/
template <typename T>
struct LinearLinearHelper
{
typedef value_t<T> first_type;
typedef value_t<first_type> second_type;
typedef std::reference_wrapper<const second_type> reference_type;
typedef std::vector<reference_type> list_type;
typedef std::vector<list_type> matrix_type;
};
/** \brief Product wrapper for linear collection of linear collections.
*/
template <
typename Container,
typename Function
>
void linearLinear(const Container &container,
Function function)
{
typedef LinearLinearHelper<Container> Helper;
typedef typename Helper::list_type List;
typedef typename Helper::matrix_type Matrix;
Matrix matrix;
matrix.reserve(container.size());
for (const auto &outer: container) {
List list;
list.reserve(outer.size());
for (const auto &inner: outer) {
list.emplace_back(std::cref(inner));
}
matrix.emplace_back(std::move(list));
}
product_impl(matrix.begin(), matrix.end(), function);
}
// LINEAR - ASSOCIATIVE
// --------------------
/** \brief Type detection for linear collection of associative collections.
*/
template <typename T>
struct LinearAssociativeHelper
{
typedef value_t<T> first_type;
typedef mapped_t<first_type> second_type;
typedef std::reference_wrapper<const second_type> reference_type;
typedef std::vector<reference_type> list_type;
typedef std::vector<list_type> matrix_type;
};
/** \brief Product wrapper for linear collection of associative collections.
*/
template <
typename Container,
typename Function
>
void linearAssociative(const Container &container,
Function function)
{
typedef LinearAssociativeHelper<Container> Helper;
typedef typename Helper::list_type List;
typedef typename Helper::matrix_type Matrix;
Matrix matrix;
matrix.reserve(container.size());
for (const auto &outer: container) {
List list;
list.reserve(outer.size());
for (const auto &inner: outer) {
list.emplace_back(std::cref(inner.second));
}
matrix.emplace_back(std::move(list));
}
product_impl(matrix.begin(), matrix.end(), function);
}
// ASSOCIATIVE - LINEAR
// --------------------
/** \brief Type detection for associative collection of linear collections.
*/
template <typename T>
struct AssociativeLinearHelper
{
typedef mapped_t<T> first_type;
typedef value_t<first_type> second_type;
typedef std::reference_wrapper<const second_type> reference_type;
typedef std::vector<reference_type> list_type;
typedef std::vector<list_type> matrix_type;
};
/** \brief Product wrapper for associative collection of linear collections.
*/
template <
typename Container,
typename Function
>
void associativeLinear(const Container &container,
Function function)
{
typedef AssociativeLinearHelper<Container> Helper;
typedef list_t<Helper> List;
typedef matrix_t<Helper> Matrix;
Matrix matrix;
matrix.reserve(container.size());
for (const auto &outer: container) {
List list;
list.reserve(outer.second.size());
for (const auto &inner: outer.second) {
list.emplace_back(std::cref(inner));
}
matrix.emplace_back(std::move(list));
}
product_impl(matrix.begin(), matrix.end(), function);
}
// ASSOCIATIVE - ASSOCIATIVE
// -------------------------
/** \brief Type detection for associative collection of associative collections.
*/
template <typename T>
struct AssociativeAssociativeHelper
{
typedef mapped_t<T> first_type;
typedef mapped_t<first_type> second_type;
typedef std::reference_wrapper<const second_type> reference_type;
typedef std::vector<reference_type> list_type;
typedef std::vector<list_type> matrix_type;
};
/** \brief Product wrapper for associative collection of associative collections.
*/
template <
typename Container,
typename Function
>
void associativeAssociative(const Container &container,
Function function)
{
typedef AssociativeAssociativeHelper<Container> Helper;
typedef typename Helper::list_type List;
typedef typename Helper::matrix_type Matrix;
Matrix matrix;
matrix.reserve(container.size());
for (const auto &outer: container) {
List list;
list.reserve(outer.second.size());
for (const auto &inner: outer.second) {
list.emplace_back(std::cref(inner.second));
}
matrix.emplace_back(std::move(list));
}
product_impl(matrix.begin(), matrix.end(), function);
}
// SFINAE
// ------
/** \brief Associative-like type-wrapper.
*/
template <typename T>
struct AssociativeLike
{
typedef value_t<T> mapped_type;
};
/** \brief Base class to check if it contains associative containers.
*/
template <typename T>
struct IsAssociativeImpl
{
static constexpr bool outer = has_mapped_type_v<T>;
typedef mapped_t<conditional_t<outer, T, AssociativeLike<T>>> U;
static constexpr bool inner = has_mapped_type_v<U>;
};
/** \brief Check if linear collection of linear collections.
*/
template <typename T>
struct IsLinearLinear
{
enum {
value = !(IsAssociativeImpl<T>::outer || IsAssociativeImpl<T>::inner)
};
};
/** \brief Check if linear collection of associative collections.
*/
template <typename T>
struct IsLinearAssociative
{
enum {
value = !IsAssociativeImpl<T>::outer && IsAssociativeImpl<T>::inner
};
};
/** \brief Check if associative collection of linear collections.
*/
template <typename T>
struct IsAssociativeLinear
{
enum {
value = IsAssociativeImpl<T>::outer && !IsAssociativeImpl<T>::inner
};
};
/** \brief Check if associative collection of associative collections.
*/
template <typename T>
struct IsAssociativeAssociative
{
enum {
value = IsAssociativeImpl<T>::outer && IsAssociativeImpl<T>::inner
};
};
template <typename T>
constexpr bool IsLinearLinearV = IsLinearLinear<T>::value;
template <typename T>
constexpr bool IsLinearAssociativeV = IsLinearAssociative<T>::value;
template <typename T>
constexpr bool IsAssociativeLinearV = IsAssociativeLinear<T>::value;
template <typename T>
constexpr bool IsAssociativeAssociativeV = IsAssociativeAssociative<T>::value;
// PRODUCT
// -------
/** \brief Deduce container type and invoke correct dispatcher.
*/
struct ProducerHelper
{
template <typename T, typename Function>
enable_if_t<IsLinearLinearV<T>, void>
static product(const T &t,
Function function)
{
return detail::linearLinear(t, function);
}
template <typename T, typename Function>
enable_if_t<IsLinearAssociativeV<T>, void>
static product(const T &t,
Function function)
{
return detail::linearAssociative(t, function);
}
template <typename T, typename Function>
enable_if_t<IsAssociativeLinearV<T>, void>
static product(const T &t,
Function function)
{
return detail::associativeLinear(t, function);
}
template <typename T, typename Function>
enable_if_t<IsAssociativeAssociativeV<T>, void>
static product(const T &t,
Function function)
{
return detail::associativeAssociative(t, function);
}
};
/** \brief Invoke the appropriate product function.
*/
template <
typename Container,
typename Function
>
void product(const Container &container,
Function function)
{
return ProducerHelper::product(container, function);
}
} /* detail */
// PRODUCT
// -------
/** \brief Wrapper for implied cartesian product.
*/
template <
typename Container,
typename Function
>
void product(const Container &container,
Function function)
{
return detail::product(container, function);
}
// MAIN
// ----
#include <chrono>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
int main(void)
{
std::vector<std::vector<int>> aa = {{1, 2, 3}, {4, 5, 6}};
std::vector<std::unordered_map<int, int>> am = {{{2, 3}}, {{5, 6}}};
std::unordered_map<int, std::vector<int>> ma = {{1, {2, 3}}, {4, {5, 6}}};
std::unordered_map<int, std::unordered_map<int, int>> mm = {{1, {{2, 3}}}, {4, {{5, 6}}}};
// TYPE-CHECKING
std::cout << "-------------------" << std::endl;
std::cout << " Array-Array Type: " << std::endl;
std::cout << "-------------------" << std::endl;
product(aa, [](const auto &i) {
std::cout << "[";
for (auto j : i) {
std::cout << j << ", ";
}
std::cout << "]" << std::endl;
});
std::cout << "-------------------" << std::endl;
std::cout << std::endl;
std::cout << std::endl;
std::cout << "-------------------" << std::endl;
std::cout << " Array-Map Type: " << std::endl;
std::cout << "-------------------" << std::endl;
product(am, [](const auto &i) {
std::cout << "[";
for (auto j : i) {
std::cout << j << ", ";
}
std::cout << "]" << std::endl;
});
std::cout << "-------------------" << std::endl;
std::cout << std::endl;
std::cout << std::endl;
std::cout << "-------------------" << std::endl;
std::cout << " Map-Array Type: " << std::endl;
std::cout << "-------------------" << std::endl;
product(ma, [](const auto &i) {
std::cout << "[";
for (auto j : i) {
std::cout << j << ", ";
}
std::cout << "]" << std::endl;
});
std::cout << "-------------------" << std::endl;
std::cout << std::endl;
std::cout << std::endl;
std::cout << "-------------------" << std::endl;
std::cout << " Map-Map Type: " << std::endl;
std::cout << "-------------------" << std::endl;
product(mm, [](const auto &i) {
std::cout << "[";
for (auto j : i) {
std::cout << j << ", ";
}
std::cout << "]" << std::endl;
});
std::cout << "-------------------" << std::endl;
std::cout << std::endl;
std::cout << std::endl;
// BENCHMARKING
// 2.73 s in Python
// 291 ms in Clang, -O3
// 235 ms in G++, -O3
std::vector<std::vector<int>> v(2);
v[0].reserve(10000);
v[1].reserve(10000);
for (int i = 0; i < 10000; ++i) {
v[0].emplace_back(i);
v[1].emplace_back(10000+i);
}
typedef std::chrono::high_resolution_clock Clock;
auto t1 = Clock::now();
product(v, [](volatile auto &i) {
});
auto t2 = Clock::now();
std::cout << "Benchmark is: "
<< std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count()
<< " ms" << std::endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment