Pascal's triangle using C++ vectors

Question

This is my C++ program. I wanted to print out Pascal's triangle. I let the user decide how many rows to print out. The first row is considered as 0, and is just:

1

I'm using vectors for this task. I think that I do not have to store the full triangle as that would take up too much extra space. I just store the previous row and the next one. I use the SetRow() function to determine the numbers in the next row based on the numbers in the previous row. Then each row is printed out. Please give me some feedback on my code. Is it an effective way to approach this problem? Does my code have any "bad programming practices"? What would you have done differently?

#include <iostream>
#include <vector>
using std::vector;
using std::cout;
using std::cin;
using std::endl;

void SetRow(vector<int> &old_row, vector<int> &new_row, int row);

int main() {
  int n_num;
  cout << "What row of Pascal's triangle do you want to go up to?" << endl;
  cin >> n_num;
  cout << endl;

  vector <int> row_1 = {1};
  vector <int> row_2;
  vector <int> curr_row;

  cout << row_1.at(0) << endl;

  // loop through all the rows
  for (int i = 1; i < (n_num + 1); i++) {
    if (i % 2 == 1) {
      SetRow(row_1, row_2, i);
      curr_row = row_2;
    } else if (i % 2 == 0) {
      SetRow(row_2, row_1, i);
      curr_row = row_1;
    }
    for (auto k: curr_row) {
      cout << k << ' ';
    }
    cout << endl;
  }

  // This ends the program
  return 0;
}

void SetRow(vector<int> &old_row, vector<int> &new_row, int row) {
  new_row.clear();
  new_row.push_back(1);
  for (int i = 0; i < (row - 1); i++) {
    new_row.push_back(old_row.at(i) + old_row.at(i + 1));
  }
  new_row.push_back(1);
}

Answer 1

The code seems all right; you might add the uniform variable initialization: int n_num {};. Furthermore, the way you read the number of rows is unstable, when you use std::cin to do it. Imagine you enter "b" instead of a number. Your program has no loop, that prevents that. You could use a function that only reads integers:

int readInt(std::istream& stream) {
    /*
     * Function to get integers, that are entered by the user
     */
    int input;
    stream >> input;
    return input;
}

Then int num_n {readInt(std::cin)}; would be a possible way to do it.

Second off: why do you have the line else if (i % 2 == 0) ? I suppose you could just use else instead. If i % 2 == 1 returns false, it has to be 0. So there is no need to check again. It's like checking if your number is odd, and if it's not checking again if it's even.

Answer 2

I only want to point out some things that are perhaps of minor relevance here, I think, since I am pushing the limits. But it might still be valuable to know.

Using the STL here, and in the way you did, it very wasteful, both in terms of memory consumption as well as time. Take for instance the repeated assignments to curr_row. Those are all copy operations. That means there is a lot of heap operations (allocation/freeing) going on there. You can optimise that by making curr_row a pointer and just switch what it points to.

But, in fact, you can avoid curr_row entirely - and with it the if-else construct - if you chose to use an array of vectors and an index crow to alternate between them:

  vector <int> row[2] = {{1}, {}};
  int crow = 0;

  // loop through all the rows
  for (int i = 1; i < (n_num + 1); i++) {
      SetRow(row[crow], row[(crow+1)&1], i);
      crow ^= 1;
      ...
  }

To give you an idea of the difference, here is a valgrind output for 1000 rows

==690== HEAP SUMMARY:
==690== in use at exit: 0 bytes in 0 blocks
==690== total heap usage: 1,025 allocs, 1,025 frees, 2,097,128 bytes allocated

Compared to using array of vectors

==694== HEAP SUMMARY:
==694== in use at exit: 0 bytes in 0 blocks
==694== total heap usage: 25 allocs, 25 frees, 91,128 bytes allocated

In a next step, you might ask yourself: "Do I really need the assets that the vector class provides?"

As you see, you can calculate the total need of space in advance. Using direct array access is a lot faster than clearing and pushing into vectors. Plus, using arrays opens up the opportunity to reduce calculations exploiting the symmetry of the triangle.

After taking user input (and issues about that have already been raised), you can set yourself up like this:

  int *buffer = new int[2 * n_num];
  buffer[0] = 1;
  buffer[n_num] = 1;
  int crow = 0;

  cout << "1" << endl;

This is a contiguous memory block, twice the size of the maximum size of columns you will need. (Rooming two rows of the triangle as before)

Of course, SetRow needs to look a little different now:

void SetRow(int* buf, int crow, int row, int ncol) {
    int b0 = ncol * ((crow+1)&1);
    int b1 = ncol * crow;
    int i = 1, lim = row/2 + 1;
    for (; i < lim; i++) {
        buf[b0 + i] = buf[b1 + i - 1] + buf[b1 + i];
        buf[b0 + row - i] = buf[b0 + i];
    }
    buf[b0 + row] = 1;
}

the values b0 and b1 are simply pre-calculated offsets into the buffer, and lim only runs up to half the triangle because assignment to the new row is done symmetrically from the left and the right towards the middle.

The first entry is skipped (it is always 1) and the last is manually inserted.

Printing now needs an ordinary for-loop.

  // loop through all the rows
  for (int i = 1; i < (n_num + 1); i++) {
    SetRow(buffer, crow, i, n_num);
    crow ^= 1;

    int b0 = crow * n_num;
    for(int j = 0; j <= i; j++) {
      cout << buffer[b0 + j] << ' ';
    }
    cout << endl;
  }

And don't forget to delete[] the buffer once you're finished.

Primitive timing using OS time functionality for 30000 rows:

• vector based:

  ./pascal 25.37s user 0.12s system 95% cpu 26.678 total

• array based:

  ./pascal4 1.88s user 0.00s system 61% cpu 3.073 total

Heap summary (1000 rows):

==771== HEAP SUMMARY:
==771== in use at exit: 0 bytes in 0 blocks
==771== total heap usage: 4 allocs, 4 frees, 82,752 bytes allocated

These are values for my computer, of course, but the difference should be obvious.

As I said, I have been pushing the limits. I hardly think anyone would want to print out 30000 rows of the Pascal Triangle, but I wanted to make aware of the differences

Answer 3

This is reasonable looking code, and didn't produce any warnings on GCC with -Wall -Wextra and a few more that I normally use.

You might want to extend the range of the integers you use - I recommend unsigned or unsigned long instead of (signed) int, since Pascal's triangle will never contain negative entries.

SetRow() can accept the old row as a constant reference, as it writes only to the new row;

We don't actually need three vectors, if we use std::swap() to efficiently exchange the contents of curr_row and prev_row(). That also means that we don't need to branch for even/odd rows. Without that branch, SetRow() is used only once, and might as well be inlined.

We know the size both vectors will reach, so it makes sense to reserve sufficient capacity before creating any of their elements.

There's no need for an explicit return 0; from main() - some will recommend you write that only if there are other (error) returns possible. Which there should be, given that the input operator >> can fail.

Unless there's a real need to produce immediate output, use plain \n rather than std::endl.

---

Modified code

#include <iostream>
#include <vector>

int main()
{
    std::cout << "What row of Pascal's triangle do you want to go up to?"
              << std::endl;

    unsigned int n_num;
    std::cin >> n_num;
    if (!std::cin) {
        std::cerr << "Not a valid number!" << std::endl;
        return 1;
    }
    std::cout << '\n';

    std::vector<unsigned int> curr_row;
    std::vector<unsigned int> prev_row;
    prev_row.reserve(n_num);
    curr_row.reserve(n_num);

    while (curr_row.size() < n_num) {
        std::swap(prev_row, curr_row);
        curr_row.resize(prev_row.size()+1);
        // generate the new values
        curr_row[0] = 1;
        for (std::size_t i = 0;  i+1 < prev_row.size();  ++i) {
            curr_row[i+1] = prev_row[i] + prev_row[i+1];
        }
        curr_row[prev_row.size()] = 1;
        // print the row
        for (auto k: curr_row) {
            std::cout << k << ' ';
        }
        std::cout << '\n';
    }
}