C++ multidimensional arrays

Question

i was thinkg about writing a code that creates a pascal triangle. I 've done it but then i thought about doing it better. One idea came to my mind but i couldnt find a proper answer for it. Is it possible to create an array which will be look like that? [1]|[1][1]|[1][2][1]|[1][3][3][1]|[1][4][6][4][1]| and so on? so my [1] would be (0,0) and [1][2][1] would be elements of cells(2,0),(2,1),(2,2). I would be grateful for any advise.

Answer 1

The nicest thing would be to wrap the whole thing in a class called PascalTriangle and implement it along the following lines:

class PascalTriangle
{
private:
    std::vector<std::vector<int> > m_data;

    std::vector<int> CalculateRow(int row_index) const
    {
        // left as an exercise :)
    }

public:
    PascalTriangle(int num_rows) :
        m_data()
    {
        assert(num_rows >= 0);
        for (int row_index = 0; row_index < num_rows; ++row_index)
        {
            m_data.push_back(CalculateRow(row_index));
        }
    }

    int operator()(int row_index, int column_index) const
    {
        assert(row_index >= 0 && row_index < m_data.size());
        assert(column_index >= 0 && column_index < row_index);
        return m_data[row_index][column_index];
    }  
};

Now here comes the catch: this approach allows you to perform lazy evaluation. Consider the following case: you might not always need each and every value. For example, you may only be interested in the 5th row. Then why store the other, unused values?

Based on this idea, here's an advanced version of the previous class:

class PascalTriangle
{
private:
    int m_num_rows;

    std::vector<int> CalculateRow(int row_index) const
    {
        // left as an exercise :)
    }

public:
    PascalTriangle(int num_rows) :
        m_num_rows(num_rows)
    {
        assert(num_rows >= 0);
        // nothing is done here!
    }

    int operator()(int row_index, int column_index) const
    {
        assert(row_index >= 0 && row_index < m_num_rows);
        assert(column_index >= 0 && column_index < row_index);

        return CalculateRow(row_index)[column_index];
    }  
};

Notice that the public interface of the class remains exactly the same, yet its internals are completely different. Such are the advantages of proper encapsulation. You effectively centralise error handling and optimisation points.

I hope these ideas inspire you to think more about the operations you want to perform with your Pascal triangle, because they will dictate the most appropriate data structure.

---

Edit: by request, here are some more explanations:

In the first version, m_data is a vector of vectors. Each contained std::vector<int> represents a row in the triangle.

The operator() function is a syntactical helper, allowing you to access PascalTriangle objects like this:

PascalTriangle my_triangle(10);
int i = my_triangle(3, 2);

assert makes sure that your code does not operate on illegal values, e.g. a negative row count or a row index greater than the triangle. But this is just one possible error reporting mechanism. You could also use exceptions, or error return values, or the Fallible idiom (std::optional). See past Stackoverflow questions for which error reporting mechanism to use when. This is a pure software-engineering aspect and has nothing to do with maths, but as you can imagine, it's, well, very important in software :)

CalculateRow returns a std::vector<int> representing the row specified by row_index. To implement it correctly, you'll need some maths. This is what I just found on Google: http://www.mathsisfun.com/pascals-triangle.html

In order to apply the maths, you'll want to know how to calculate n! in C++. There have been a lot of past Stackoverflow questions on this, for example here: Calculating large factorials in C++

Note that with the class approach, you can easily switch to another implementation later on. (You can even take it to the extreme and switch to a specific calculation algorithm based on the triangle height, without the users of the class ever noticing anything! See how powerful proper encapsulation can be?)

In the second version of the class, there is no permanent data storage anymore. CalculateRow is called only if and when needed, but the client of the class doesn't know this. As an additional possibly performance-improving measure, you could remember rows which you already calculated, for example by adding a private std::map<int, std::vector<int> > member variable whose int key represents the row index and whose values the rows. Every CalculateRow call would then first look if the result is already there, and add calculated ones at the end:

    private mutable std::map<int, std::vector<int> > m_cache;

    std::vector<int> CalculateRow(int row_index) const
    {
        // find the element at row_index:
        std::map<int, std::vector<int> >::const_iterator cache_iter =
            m_cache.find(row_index);

        // is it there?
        if (cache_iter != m_cache.end())
        {
            // return its value, no need to calculate it again:
            return cache_iter->second;
        }

        // actual calculation of result left as an exercise :)

        m_cache[row_index] = result;
        return result;
    }

By the way, this would also be a nice application of the new C++11 auto keyword. For example, you'd then just write auto cache_iter = m_cache.find(row_index);

---

And here's for another edit: I made m_cache mutable, because otherwise the thing wouldn't compile, as CalculateRow is a const member function (i.e. shouldn't change an object of the class from the client's point of view). This is a typical idiom for cache member variables.

Answer 2

No it's not possible. In an array, all the element must have the same type. Two dimensional arrays are arrays of arrays. That means that for a multidimensional array, all the line must have the same length. You should probably use a

std::vector<std::vector<int> >

here. Or a one dimensional array and and the logic to compute the 1 dim position from the 2 dim index:

index = row*(row+1)/2 + column.

See iterate matrix without nested loop if you want the reverse indexing.

Edit: fixed my formula which was off by one. Here is a check in Python:

The following index function takes row, col and compute the corresponding index in a one dimensional array using my formula:

>>> index = lambda row, col: row*(row+1)/2 + col

Here are the coordinate pairs

>>> [[(i,j) for j in range(i+1)] for i in range(5)]
[[(0, 0)],
 [(1, 0), (1, 1)],
 [(2, 0), (2, 1), (2, 2)],
 [(3, 0), (3, 1), (3, 2), (3, 3)],
 [(4, 0), (4, 1), (4, 2), (4, 3), (4, 4)]]

I'm now checking that the corresponding index are the sequence of integer starting from 0 (indentation of the printing is mine):

>>> [[index(i,j) for j in range(i+1)] for i in range(5)]
[[0], 
 [1, 2], 
 [3, 4, 5], 
 [6, 7, 8, 9], 
 [10, 11, 12, 13, 14]]

Answer 3

You can implement triangle array through a single-dimension array. Fixed-size array may look like this:

template<typename T, size_t N>
struct TriangleArray {
    T& element(size_t i, size_t j)
    {
        if (i >= N || j >= N || i < j)
            throw std::out_of_range("incorrect index");
        return container[(i + 1) * i / 2 + j];
    }
private:
    T container[(N + 1) * N / 2];
};