TMP: how to generalize a Cartesian Product of Vectors?
Simpler recursive solution. It takes vectors as function arguments, not as a tuple. This version doesn't build temporary tuples, but uses lambdas instead. Now it makes no unnecessary copies/moves and seems to get optimized successfully.
#include<tuple>
#include<vector>
// cross_imp(f, v...) means "do `f` for each element of cartesian product of v..."
template<typename F>
inline void cross_imp(F f) {
f();
}
template<typename F, typename H, typename... Ts>
inline void cross_imp(F f, std::vector<H> const& h,
std::vector<Ts> const&... t) {
for(H const& he: h)
cross_imp([&](Ts const&... ts){
f(he, ts...);
}, t...);
}
template<typename... Ts>
std::vector<std::tuple<Ts...>> cross(std::vector<Ts> const&... in) {
std::vector<std::tuple<Ts...>> res;
cross_imp([&](Ts const&... ts){
res.emplace_back(ts...);
}, in...);
return res;
}
#include<iostream>
int main() {
std::vector<int> is = {2,5,9};
std::vector<char const*> cps = {"foo","bar"};
std::vector<double> ds = {1.5, 3.14, 2.71};
auto res = cross(is, cps, ds);
for(auto& a: res) {
std::cout << '{' << std::get<0>(a) << ',' <<
std::get<1>(a) << ',' <<
std::get<2>(a) << "}\n";
}
}
How can I create cartesian product of vector of vectors?
First, I'll show you a recursive version.
// Cartesion product of vector of vectors
#include <vector>
#include <iostream>
#include <iterator>
// Types to hold vector-of-ints (Vi) and vector-of-vector-of-ints (Vvi)
typedef std::vector<int> Vi;
typedef std::vector<Vi> Vvi;
// Just for the sample -- populate the intput data set
Vvi build_input() {
Vvi vvi;
for(int i = 0; i < 3; i++) {
Vi vi;
for(int j = 0; j < 3; j++) {
vi.push_back(i*10+j);
}
vvi.push_back(vi);
}
return vvi;
}
// just for the sample -- print the data sets
std::ostream&
operator<<(std::ostream& os, const Vi& vi)
{
os << "(";
std::copy(vi.begin(), vi.end(), std::ostream_iterator<int>(os, ", "));
os << ")";
return os;
}
std::ostream&
operator<<(std::ostream& os, const Vvi& vvi)
{
os << "(\n";
for(Vvi::const_iterator it = vvi.begin();
it != vvi.end();
it++) {
os << " " << *it << "\n";
}
os << ")";
return os;
}
// recursive algorithm to to produce cart. prod.
// At any given moment, "me" points to some Vi in the middle of the
// input data set.
// for int i in *me:
// add i to current result
// recurse on next "me"
//
void cart_product(
Vvi& rvvi, // final result
Vi& rvi, // current result
Vvi::const_iterator me, // current input
Vvi::const_iterator end) // final input
{
if(me == end) {
// terminal condition of the recursion. We no longer have
// any input vectors to manipulate. Add the current result (rvi)
// to the total set of results (rvvvi).
rvvi.push_back(rvi);
return;
}
// need an easy name for my vector-of-ints
const Vi& mevi = *me;
for(Vi::const_iterator it = mevi.begin();
it != mevi.end();
it++) {
// final rvi will look like "a, b, c, ME, d, e, f"
// At the moment, rvi already has "a, b, c"
rvi.push_back(*it); // add ME
cart_product(rvvi, rvi, me+1, end); add "d, e, f"
rvi.pop_back(); // clean ME off for next round
}
}
// sample only, to drive the cart_product routine.
int main() {
Vvi input(build_input());
std::cout << input << "\n";
Vvi output;
Vi outputTemp;
cart_product(output, outputTemp, input.begin(), input.end());
std::cout << output << "\n";
}
Now, I'll show you the recursive iterative version that I shamelessly stole from @John :
The rest of the program is pretty much the same, only showing the cart_product function.
// Seems like you'd want a vector of iterators
// which iterate over your individual vector<int>s.
struct Digits {
Vi::const_iterator begin;
Vi::const_iterator end;
Vi::const_iterator me;
};
typedef std::vector<Digits> Vd;
void cart_product(
Vvi& out, // final result
Vvi& in) // final result
{
Vd vd;
// Start all of the iterators at the beginning.
for(Vvi::const_iterator it = in.begin();
it != in.end();
++it) {
Digits d = {(*it).begin(), (*it).end(), (*it).begin()};
vd.push_back(d);
}
while(1) {
// Construct your first product vector by pulling
// out the element of each vector via the iterator.
Vi result;
for(Vd::const_iterator it = vd.begin();
it != vd.end();
it++) {
result.push_back(*(it->me));
}
out.push_back(result);
// Increment the rightmost one, and repeat.
// When you reach the end, reset that one to the beginning and
// increment the next-to-last one. You can get the "next-to-last"
// iterator by pulling it out of the neighboring element in your
// vector of iterators.
for(Vd::iterator it = vd.begin(); ; ) {
// okay, I started at the left instead. sue me
++(it->me);
if(it->me == it->end) {
if(it+1 == vd.end()) {
// I'm the last digit, and I'm about to roll
return;
} else {
// cascade
it->me = it->begin;
++it;
}
} else {
// normal
break;
}
}
}
}
How to convert a tuple of vectors into a vector of tuples using the Cartesian product?
http://ideone.com/ThhAoa
Not that tricky:
#include <cstddef>
#include <utility>
#include <vector>
#include <tuple>
#include <string>
#include <iostream>
using std::size_t;
template<size_t...> struct seq {};
template<size_t Min, size_t Max, size_t... s>
struct make_seq:make_seq< Min, Max-1, Max-1, s... > {};
template<size_t Min, size_t... s>
struct make_seq< Min, Min, s... > {
typedef seq<s...> type;
};
template<size_t Max, size_t Min=0>
using MakeSeq = typename make_seq<Min, Max>::type;
size_t product_size() {
return 1;
}
template<typename... Sizes>
size_t product_size( size_t x, Sizes... tail ) {
return x * product_size(tail...);
}
namespace details {
template<typename max_iterator, typename Lambda>
void for_each_index( max_iterator mbegin, max_iterator mend, Lambda&& f, std::vector<size_t>& idx ) {
if (mbegin == mend) {
f(idx);
} else {
for (size_t i = 0; i < *mbegin; ++i) {
idx.push_back(i);
for_each_index(mbegin+1, mend, f, idx);
idx.pop_back();
}
}
}
template<typename Lambda>
void for_each_index( std::vector<size_t> const& maxes, Lambda&& f ) {
std::vector<size_t> idx;
details::for_each_index( maxes.begin(), maxes.end(), f, idx );
}
template<size_t... s, typename... Ts>
std::vector< std::tuple<Ts...> > does_it_blend( seq<s...>, std::tuple< std::vector<Ts>... >const& input ) {
std::vector< std::tuple<Ts...> > retval;
retval.reserve( product_size( std::get<s>(input).size()... ) );
std::vector<size_t> maxes = {
(std::get<s>(input).size())...
};
for_each_index( maxes, [&](std::vector<size_t> const& idx){
retval.emplace_back( std::get<s>(input)[idx[s]]... );
});
return retval;
}
}
template<typename... Ts>
std::vector< std::tuple<Ts...> > does_it_blend( std::tuple< std::vector<Ts>... >const& input ) {
return details::does_it_blend( MakeSeq< sizeof...(Ts) >(), input );
}
int main() {
std::tuple< std::vector<int>, std::vector<bool>, std::vector<std::string> > input {
{ 1, 2, 3}, { false, true}, { "Hello", "World"}
};
// should become 3 x 2 x 2 = 12 cases { {1, false, "Hello"}, ... , {3, true, "World"} }
std::vector< std::tuple<int, bool, std::string> > test_cases = does_it_blend( input );
for( auto&& x:test_cases ) {
std::cout << std::get<0>(x) << "," << std::get<1>(x) << "," << std::get<2>(x) << "\n";
}
}
Here I create a function that does a Cartesian product of the possible indexes, then creates the tuples directly in the output container.
I also do the bother of reserving the output size.
Now with less code.
Call lambda with the cartesian product of values in multiple input vectors
Here's a short recursive version that just works with any iterables. It takes everything by const& for simplicity:
template <typename F>
void product(F f) {
f();
}
template <typename F, typename C1, typename... Cs>
void product(F f, C1 const& c1, Cs const&... cs) {
for (auto const& e1 : c1) {
product([&](auto const&... es){
f(e1, es...);
}, cs...);
}
}
Which would be:
product(process, iv, jv, kv);
cartesian product indices generator
Here's a rather straightforward and boring implementation.
#include <cstdlib>
#include <iostream>
namespace ct {
template <typename, typename>
struct pair {};
template <typename... a>
struct list {};
template <typename a, typename... b>
struct cons_t;
template <typename a>
struct cons_t<a, list<>>
{
using type = list<a>;
};
template <typename a, typename bh, typename... bt>
struct cons_t<a, list<bh, bt...>>
{
using type = list<a, bh, bt...>;
};
template <typename a, typename... b>
struct concat_t;
template <typename b>
struct concat_t<list<>, b>
{
using type = b;
};
template <typename b, typename ah, typename... at>
struct concat_t<list<ah, at...>, b>
{
using type = typename cons_t<ah, typename concat_t<list<at...>, b>::type>::type;
};
template <typename a, typename b>
using cons = typename cons_t<a,b>::type;
template <typename a, typename b>
using concat = typename concat_t<a,b>::type;
template <typename a, typename b>
struct cartesian1;
template <typename a>
struct cartesian1<a, list<>>
{
using type = list<>;
};
template <typename a, typename bh, typename... bt>
struct cartesian1<a, list<bh, bt...>>
{
using type = cons<pair<a, bh>, typename cartesian1<a, list<bt...>>::type>;
};
template <typename a, typename b>
struct cartesian_t;
template <typename a>
struct cartesian_t<list<>, a>
{
using type = list<>;
};
template <typename ah, typename b, typename... at>
struct cartesian_t<list<ah, at...>, b>
{
using type = concat<typename cartesian1<ah, b>::type,
typename cartesian_t<list<at...>, b>::type>;
};
template <typename a, typename b>
using cartesian = typename cartesian_t<a,b>::type;
template <size_t x>
struct val {};
template <size_t... a>
struct vlist {};
template <typename t>
struct vlist2list_t;
template <>
struct vlist2list_t<vlist<>>
{
using type = list<>;
};
template <size_t ah, size_t... at>
struct vlist2list_t<vlist<ah, at...>>
{
using type = cons<val<ah>, typename vlist2list_t<vlist<at...>>::type>;
};
template <typename a>
using vlist2list = typename vlist2list_t<a>::type;
template <size_t...a>
using vl = vlist2list<vlist<a...>>;
template<size_t x1, size_t x2>
std::ostream& operator<< (std::ostream& s,
pair<val<x1>, val<x2>> z)
{
s << "(" << x1 << "," << x2 << ")";
return s;
}
std::ostream& operator<< (std::ostream& s,
list<> z)
{
s << "[]";
}
template <typename ah, typename... at>
std::ostream& operator<< (std::ostream& s,
list<ah, at...> z)
{
s << ah() << ":" << list<at...>();
}
}
int main ()
{
using a = ct::cartesian<ct::vl<1,2,3>, ct::vl<4,5,6>>;
std::cout << a() << std::endl;
}
Intrusive reflection like functionality for c++?
With Cartesian product, we might do:
// cartesian_product_imp(f, v...) means
// "do `f` for each element of cartesian product of v..."
template<typename F>
void cartesian_product_imp(F f) {
f();
}
template<typename F, typename H, typename... Ts>
void cartesian_product_imp(F f, std::vector<H> const& h,
std::vector<Ts> const&... vs) {
for (H const& he: h) {
cartesian_product_imp([&](Ts const&... ts){
f(he, ts...);
}, vs...);
}
}
template <typename... Ts>
std::vector<std::tuple<Ts...>> cartesian_product(std::vector<Ts> const&... vs) {
std::vector<std::tuple<Ts...>> res;
cartesian_product_imp([&](Ts const&... ts){
res.emplace_back(ts...);
}, vs...);
return res;
}
template <typename T>
std::vector<T> PossibleInstantiations()
{
auto validValuesByArgs = T::ValidValuesForArgs();
auto validArgs =
std::apply([](const auto&... args){ return cartesian_product(args...); },
validValuesByArgs);
std::vector<T> res;
std::transform(validArgs.begin(), validArgs.end(),
std::back_inserter(res),
[](const auto& t){
return std::apply([](const auto&... args) { return T(args...); },
t);
});
return res;
}
With
class SomeClass
{
public:
int i;
double j;
const std::string s;
static std::tuple<std::vector<int>, std::vector<double>, std::vector<std::string>>
ValidValuesForArgs() { return {{1, 4, 5}, {1.1, 4.5}, {"foo", "bar"}}; }
SomeClass(int i, double j, const std::string& s) : i(i), j(j), s(s) {}
};
Demo
Replacing Multi-Dimension for-loop with range-based for-loop
This is about the simplest implementation I could manage:
#include <iostream>
#include <tuple>
using namespace std;
using tuple_3d = tuple<int, int, int>;
struct range_3d;
struct range_3d_iterator
{
const range_3d& c;
tuple_3d i;
bool operator!=(const range_3d_iterator& other)
{ return get<0>(i) != get<0>(other.i) && get<1>(i) != get<1>(other.i) && get<2>(i) != get<2>(other.i); }
tuple_3d operator*() const
{ return make_tuple(get<0>(i), get<1>(i), get<2>(i)); }
const range_3d_iterator& operator++();
};
struct range_3d
{
tuple_3d s;
tuple_3d e;
range_3d_iterator begin() const
{ return { *this, s }; }
range_3d_iterator end() const
{ return { *this, e }; }
};
const range_3d_iterator& range_3d_iterator::operator++()
{
++get<2>(i);
if (get<2>(i) == get<2>(c.e))
{
get<2>(i) = get<2>(c.s);
++get<1>(i);
if (get<1>(i) == get<1>(c.e))
{
get<1>(i) = get<1>(c.s);
++get<0>(i);
}
}
return *this;
}
int main(void)
{
for (auto&& v : range_3d{ make_tuple(20, 40, 2), make_tuple(25, 45, 4) })
cout << get<0>(v) << ' ' << get<1>(v) << ' ' << get<2>(v) << endl;
}
The naming is a bit crap, but that aside, the concept is simple. The range_3d is a simple class which supports begin(), end() to get the range for loop to work, then the "smartness" is in the range_3d_iterator which will iterate the tuple. Given the way I've used the tuple here, it's trivial to extend to arbitary dimensions...
TBH, the original for loop is pretty clear... IMO!
How to get dot product of two sparsevectors in O(m+n) , where m and n are the number of elements in both vectors
You can do it if your vectors are stored as a linked list of tuples whith each tuple containing the index and the value of a non zero element and sorted by the index.
You iterate through both vectors, by selecting the next element from the vector where you are at the lower index. If the indexes are the same you multiply the elements and store the result.
Repeat until one list reaches the end.
Since you have one step per non zero element in each list, the complexity is O(m+n) as required.
Footnote: The datastructure doesn't have to be linked list, but must provide a O(1) way to access the next non 0 element and it's index.
Related Topics
Microsecond Resolution Timestamps on Windows
Default Class Inheritance Access
Non-Class Rvalues Always Have Cv-Unqualified Types
What Kinds of Optimizations Does 'Volatile' Prevent in C++
Why Are Strings in C++ Usually Terminated with '\0'
Building and Accessing a List of Types at Compile Time
Why Does the Library Linker Flag Sometimes Have to Go at the End Using Gcc
How to Expand Call to Variadic Template Base Classes
How to Check Whether Two Matrices Are Identical in Opencv
How to Call MAChine Code Stored in Char Array
Does the Gotw #101 "Solution" Actually Solve Anything
C++: Safe to Use Longjmp and Setjmp
How to Get the CPU Usage Per Thread on Windows (Win32)