Optimize simple C++ function to minimize copying

I've been coding C for almost 20 years and figured I should learn C++. As a starting point I wrote the following trivial code to generate the powerset of a set. I'm hoping that some experienced C++ coder could help me with three things:

1. Identify non-idiomatic constructions.

2. Explain where I'm doing unnecessary copying of objects

#include <iostream>
#include <vector>

using namespace std;

template<typename T>
vector<vector<T>> powerset(vector<T> s)
{
// Return the powerset containing the empty set
if(s.size() == 0) {
vector<int> dummy;
return vector<vector<T>> { dummy };
}

T v = s.back();
s.pop_back();

// Recursively generate powerset for s setminus v
vector<vector<T>> pss = powerset<T>(s);
// This is the basis for the current powerset set
vector<vector<T>> ps = pss;

for(auto&& i : pss) {
i.push_back(v);
ps.push_back(i);
}

return ps;
}

int main(void)
{
vector<int> v = {1,2,3,4};

vector<vector<int>> ps = powerset<int>(v);

cout << "Powerset contains the following elements:" << endl;
for(auto&& i : ps) {
for(auto&& j : i) {
cout << j << " ";
}
cout << endl;
}

return 0;
}

• Minor detail: Don't put void in the declaration of parameter-less functions. C++ does not requires it, so it is just code clutter. E.g.: int main() instead of int main(void). – glampert Dec 17 '14 at 16:56
• OK, that's good to know. – JT1 Dec 18 '14 at 8:10

• There is an error in powerset: while it works fine with your test case, you specifically try to return an std::vector<int> when size is 0 while you should be returning an std::vector<T>.

• You don't even need the dummy vector. You can take advantage of uniform initialization and brace initialization in a return statement to simply write this:

return { {} };

• Using s.size() == 0 in a condition is fine, but the idiomatic way to do it would be to use s.empty(). While it does not make a big difference for std::vector, some implementations of std::list still implement a $O(n)$ size while empty will always be $O(1)$ (C++11 requires std::list::size to be $O(1)$ but not all implementations are up-to-date). Using empty will be better if you ever need to change the kind of collection you use.

• Since pss won't be used after the last for loop of powerset, you can safely move the elements out of it instead of copying them:

for(auto&& i : pss) {
i.push_back(v);
ps.push_back(std::move(i));
}


The vectors in pss will be moved into ps, but left in a valid state, so you don't have to fear errors or undefined behaviour.

• Every time you call powerset, you copy a full std::vector while you only need to read the elements. Instead of a vector, you could pass iterators so that you don't have to endlessly copy vectors that you only need to read:

template<typename T>
vector<vector<T>> powerset(typename vector<T>::iterator first, typename vector<T>::iterator last)
{
// Return the powerset containing the empty set
if(std::distance(first, last) == 0) {
return { {} };
}

--last;
T v = *last;

// Recursively generate powerset for s setminus v
vector<vector<T>> pss = powerset<T>(first, last);
// This is the basis for the current powerset set
vector<vector<T>> ps = pss;

for(auto&& i : pss) {
i.push_back(v);
ps.push_back(std::move(i));
}

return ps;
}


This is not the prettiest in the world, but it works, and you should even be able to generalize the agorithm so that it takes any BidirectionalIterator instead of mere std::vector<T>::iterator.

• Good review as always. You might also want to point out that the range-for used for printing would normally use const auto & rather than the current auto &&. We don't need to move the items or alter them -- just to print them. – Edward Dec 17 '14 at 11:31
• Picking on a minor detail, since C++11 list::size() is required to be constant time (O(1)). I don't have a reference to the standard at hand, but cppreference.com is up-to-date on that. – glampert Dec 17 '14 at 16:47
• @glampert That's why I wrote "some implementations". I thought that I also wrote "still implement" but I didn't do it, my bad. – Morwenn Dec 17 '14 at 18:11
• Thank you. I had correctly identified the correct places, where copying happened, but didn't know exactly how to easily get rid of it. One question: if this was a divide-and-conquer algorithm and I want to recursively call something with the upper and lower half, how do I calculate the iterators? Is it just regular pointer arithmetic or is there another idiomatic way? – JT1 Dec 18 '14 at 8:14
• One more question: What does std::move(i) actually do? It must somehow change the type in order to call some "move" version of push_back(). However, it seems like magic how you would implement it such a "type changer". – JT1 Dec 18 '14 at 8:16

vector<vector<T>> is fairly specific to a powerset and cumbersome to write. Instead you could use a typedef and a more specific function name.

template<typename T>
using powerset = vector<vector<T>>;

template<typename T>
powerset<T> createPowerset(vector<T> s)
{
if(s.size() == 0) {
vector<int> dummy;
return powerset<T> { dummy };
}

T v = s.back();
s.pop_back();

// no explicit template parameter on createPowerset.
// Type deduction is used here
powerset<T> pss = createPowerset(s);
powerset<T> ps = pss;

for(auto&& i : pss) {
i.push_back(v);
ps.push_back(i);
}
return ps;
}