12
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ 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). \$\endgroup\$ – glampert Dec 17 '14 at 16:56
  • \$\begingroup\$ OK, that's good to know. \$\endgroup\$ – JT1 Dec 18 '14 at 8:10
13
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Edward Dec 17 '14 at 11:31
  • \$\begingroup\$ 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. \$\endgroup\$ – glampert Dec 17 '14 at 16:47
  • \$\begingroup\$ @glampert That's why I wrote "some implementations". I thought that I also wrote "still implement" but I didn't do it, my bad. \$\endgroup\$ – Morwenn Dec 17 '14 at 18:11
  • \$\begingroup\$ 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? \$\endgroup\$ – JT1 Dec 18 '14 at 8:14
  • \$\begingroup\$ 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". \$\endgroup\$ – JT1 Dec 18 '14 at 8:16
7
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.