Optimize simple C++ function to minimize copying

Question

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

3. Any other simplifying comments.

#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) {
    // Add a set with v added for each set
    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;
}

Answer 1

A few things about your code that you could improve:

• 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) {
    // Add a set with v added for each set
    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) {
      // Add a set with v added for each set
      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.

Answer 2

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;
}