3

Here I just want to define a function which returns the multiplication of matrices, with N arbitrary, I would like to generate a matrix with a new command. When I execute the function I get the error:

Segmentation fault (core dumped)

Whenever I assign values to C I have this error, could anybody tell me what happened and how to fix it?

int **multiply(int **A, int **B, int N){
    int **C = new int*[N];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++)
                C[i][j] = C[i][j] + A[i][k] * B[k][j];
        }
    }
    return (C);
}
ErstwhileIII
  • 4,829
  • 2
  • 23
  • 37
user3622064
  • 43
  • 2
  • 4
    You allocated space for N int pointers, but you have not set them to point anywhere yet. You must not read from them till you've written valid pointers into them. – mah May 09 '14 at 22:20
  • Since you're allocating primitive arrays, you may want to use [`calloc`](http://en.cppreference.com/w/cpp/memory/c/calloc) instead of `new`. – Jason May 09 '14 at 22:35
  • @Jason, Or, assuming vectors and actual matrix classes are out of the question, you could keep it working properly for non-POD types and just use `new int*[N]();` to get the same effect. – chris May 10 '14 at 00:33
  • @chris `new[]()` doesn't initialize the memory though. IMHO, `std::calloc` is safer/clearer. It's more obvious what `std::calloc(N * N, sizeof(int))` does (allocate N*N array, initialize to 0). – Jason May 10 '14 at 02:08
  • @Jason, It actually does value-initialize the elements, whereas leaving out the parentheses only default-initializes them. The nice thing about it is that it works with every type without you having to check whether it's a POD, or change an existing allocation to something that isn't a POD and have it break. – chris May 10 '14 at 02:10
  • @chris I was under the impression that `new[]()` didn't initialize memory. Still, I would worry a bit that it could sacrifice clarity at the altar of cleverness. Honestly, matrix multiplication can probably be better expressed in terms of templates and operator overloads instead of explicit multiplication though. – Jason May 10 '14 at 02:31
  • @Jason, Yes, a proper abstraction would be better. For the `new` thing, there's [this question](http://stackoverflow.com/questions/620137/do-the-parentheses-after-the-type-name-make-a-difference-with-new). It applies to `[]` because the `[]` is part of *noptr-new-declarator*, which doesn't coincide with *new-initializer* (which is what the `()` is). – chris May 10 '14 at 02:51
  • @chris It looks like you're right, the parens will *value-initialize* each of the array elements for POD types with `new[]()`. Thanks, I'll have to take a closer look through the spec. – Jason May 10 '14 at 17:13

3 Answers3

5

It is not a good idea to make matrices as pointers of pointers. To do that properly, you need a rather complex:

int **C = new int*[N];
for(int i = 0; i < N; ++ i)
    C[i] = new int[M];

And freeing this up is a similarly complicated process. Also think about what happens if one of the operator new fails and you want to free up the partially allocated matrix.

It is a convention to store 2D arrays inside of a 1D ones. You can do:

int *C = new int[M * N];

And then the elements are accessed as:

C_ij = C[i + N * j];

or as:

C_ij = C[j + M * i];

Where i is in [0, N) interval and j is in [0 to M) interval. These are actually quite similar to how the compiler generates accesses to a constant-sized 2D array (so the multiplication is in fact not overly costly, and when considering cache, the whole thing is likely to be much faster than your array of arrays). The difference between the two lines above is that the one is column-major (the elements of a column are consecutive items when unrolled to 1D) or alternately row-major. That is a matter of convention. The default "C" arrays will be row-major. Some libraries, such as OpenGL or Eigen use column major.

the swine
  • 10,713
  • 7
  • 58
  • 100
4
int **C=new int*[N];

This makes space for an array of pointers. It doesn't initialize them, so they could point anywhere. They might even be NULL pointers.

C[i][j]

This might cause a null pointer dereference. That's probably what causes the segmentation fault.

guest
  • 6,450
  • 30
  • 44
  • 6
    It doesn't just matter if its `nullptr`. Dereferencing *any* address that was not reserved for you is Undefined Behavior. – David G May 09 '14 at 22:28
  • 3
    @user2079303 There are no different "kinds" of Undefined Behavior. If dereferencing a null pointer is Undefined Behavior, it may or may not cause a segmentation fault; it may do nothing, or it could crash your computer. The point is that if your program invokes UB, don't have any expectations of what might happen. – David G May 09 '14 at 22:44
  • 2
    @user2079303 Those are the **effects** of Undefined Behavior. UB in itself is just a blanket term for "your program is now ill-formed, so your implementation can do whatever it wants now". – David G May 09 '14 at 22:50
  • I see where it goes wrong, I should allocate address for C[i] with another "new" command after having C defined. Thank all you guys! – user3622064 May 09 '14 at 23:36
0

As guest has pointed out, the pointers inside C haven't been initialised. You need to initialise them in the first loop (commented 1) and initialise their elements to zero in the second (commented 2):

int **multiply(int **A, int **B, int N){
    int **C = new int*[N];
    for (int i = 0; i < N; i++) {
        C[i] = new int[N]; //1
        for (int j = 0; j < N; j++) {
            C[i][j] = 0; //2
            for (int k = 0; k < N; k++)
                C[i][j] = C[i][j] + A[i][k] * B[k][j];
        }
    }
    return (C);
}
thus spake a.k.
  • 1,607
  • 12
  • 12