What is the difference between an array and a sequence?

[idknuttin]

I know what an array is, I recently learned what my professor calls sequences, they are basically arrays but with pointers. I will give two examples of code, one with an array being passed into a function and the other a sequence being passed into a function. Both of these will do the same thing but I want to understand what the difference between arrays and sequences is, are they officially called sequences?

first code: array

#include<iostream>

void changeArray(int arr[]){
  arr[0]=5;
  arr[1]=6;
  arr[2]=7;
  arr[3]=8;
}

int main(){
  int arrayX[]={1, 2, 3, 4};
  std::cout<<"the original array is ";
  for(int i=0; i<4; ++i){
    std::cout<<arrayX[i] <<" ";
  }
  std::cout<<std::endl;

  changeArray(arrayX);

  std::cout<<"the new array is ";
  for(int j=0; j<4; ++j){
    std::cout<<arrayX[j] <<" ";
  }
  std::cout<<std::endl;

  return 0;
}

second code: sequences

#include<iostream>

void changeArray(int** pX){
  *(*pX)=5;
  *(*pX+1)=6;
  *(*pX+2)=7;
  *(*pX+3)=8;
}

int main(){
  int *arrayX;
  arrayX=new int[4];
  arrayX[0]=1;
  arrayX[1]=2;
  arrayX[2]=3;
  arrayX[3]=4;
  std::cout<<"the original array is ";
  for(int i=0; i<4; ++i){
    std::cout<<arrayX[i] <<" ";
  }
  std::cout<<std::endl;

  changeArray(&arrayX);

  std::cout<<"the new array is ";
  for(int j=0; j<4; ++j){
    std::cout<<arrayX[j] <<" ";
  }
  std::cout<<std::endl;

  return 0;
}

Questions:
1. Why do the the integers in the array change values in the first code when I am not passing by reference (not doing void changeArray(int &arr[])) or declaring the array as a pointer?

2. Inside the changeArray function in the second piece of code is there a way to write *pX[2]=7 instead of what I have written *(*pX+2)=7 ? I get compiling errors when I try to write it like this.

3. What is the difference between an array and a sequence?

[jonnin]

sequence is something in math, but it isn't a c++ data type or concept.

1) arrays are pointers. The name of an array (its variable name) is a pointer, conceptually. A pointer is a reference (& is really the "get pointer of" operator, as you see once in a while with type *x = &other; ) So that boils down to saying that arrays are passed by reference anyway, whether you like it or not. You can use const to prevent accidental changes to arrays.

2) yes. I never use *s. I always use []. *p is the same as p[0]
I think what you are trying to write is px[2][0] = 7; or the other way around, px[0][2]. I'm not sure today.

3) As I said, sequence isn't anything in c++ that I have heard of. The only real difference between pointers and arrays is that the user has to allocate (or provide via & of) and handle the memory for the pointers. Both arrays and pointers can use [] notation, the array name can be used as a pointer (int * p = arraynamevar;), there is no real conceptual difference and while you can "ugly up" pointer code, you don't have to do that. Your second function could have been written totally as a 1d pointer instead of 2d, as best I can tell. The key is simple this: arrays have a fixed, compile time determined size, and pointers do not have to have this. That puts the arrays in a different area in the physical memory of your program, and you can make an array too big to fit there, since its the program's stack, but when that happens the compiler or execution of the program tell you (out of memory errors).

the underlying mess here is the ** px function parameter and calling it with &arrayx. If you just make it *px and (arrayx) it would work fine, and you would only have to deal with 1 level of pointers. The entire second level of pointers is artificial and uglys up the code for no gains.


Hopefully this makes sense?

[Cubbi]

idknuttin wrote:

are they officially called sequences

No, it appears to be somebody's invented terminology.

Your first example works with an array of four integers that is allocated on the stack (formally, "automatic"). It is passed to the function as a pointer to the first element of the array.

Your second example works with an array of four integers that is allocated on the heap (formally, "dynamic"). It is passed to the function as a pointer to a pointer to the first element of the array. It also has a memory leak.

idknuttin wrote:

Why do the the integers in the array change values in the first code when I am not passing by reference (not doing void changeArray(int &arr[])) or declaring the array as a pointer?

It is a confusing feature of C's function declaration that C++ inherited: functions that take arrays by value do not exist. But instead of making the declaration void changeArray(int arr[]) an error, it is re-written, before the compiler gets to see it, into a *different* declaration: void changeArray(int* arr). Your first function has nothing to do with arrays. It takes a pointer to int. (the code inside the function then assumes that pointer happens to point to an element of an array)

You can observe that if you attempt to also define a function called void changeArray(int* arr) later in the program and the compiler will tell you you already defined this one, something like

main.cpp: In function 'void changeArray(int*)':
main.cpp:10:6: error: redefinition of 'void changeArray(int*)'
 void changeArray(int* arr){
      ^~~~~~~~~~~
main.cpp:3:6: note: 'void changeArray(int*)' previously defined here
 void changeArray(int arr[]){
      ^~~~~~~~~~~

At the call site, changeArray(arrayX); is attempting to use an array where arrays are not allowed, but pointers are, and the compiler inserts an implicit conversion that constructs a pointer. It is as if you wrote changeArray(&arrayX[0]);.

In order to declare a function that takes an array by reference you have to write void changeArray(int (&arr)[4]), but that's probably distracting at this point.

Inside the changeArray function in the second piece of code is there a way to write *pX[2]=7 instead of what I have written *(*pX+2)=7 ?

Yes, the syntax is (*pX)[2]=7;.
You can also use your first function with the array from the second example, call it the same way, changeArray(arrayX); (this time there will be no conversion since second example's "arrayX" is a pointer, not an array)

oh, and

jonnin wrote:

arrays are pointers

No, not at all.

[idknuttin]

@Cubbi

So basically the two codes that I wrote are exactly the same because in the first code the compiler simply rewrites it so that it looks like the second code, correct? So it's like there is two ways of typing arrays in C++.

I could have wrote changeArray(&arrayX[0]); instead of what I had written, I tried to write this code with a 4 in the brackets and with an empty bracket and both times I got a compiling error. Is there a reason for the 0 in the brackets? I would think it would make more sense to leave the brackets empty to let the compiler know that you want to pass the entire array.

Just wondering, where is the memory leak in the second code?
If I added delete[] arrayX; at the end of the second code would that get rid of the memory leak?

[Cubbi]

the compiler simply rewrites it so that it looks like the second code, correct?

no. It rewrites void changeArray(int arr[]) to void changeArray(int* arr). Your second example has void changeArray(int** pX)

I could have wrote changeArray(&arrayX[0]); ... I would think it would make more sense to leave the brackets empty to let the compiler know that you want to pass the entire array.

you're not passing "the entire array". There is no way to pass a naked C-style array by value (you can pass a C++ array by value, as in std::array<int,4>, but that's another distraction from the topic) You're passing a pointer to the first element of the array, because that's what your first function expects. The first element is arrayX[0], pointer to it is &arrayX[0]. Because it's a popular operation, the compiled can do it for you.

To pass the entire C-style array by reference, you would define that function as void changeArray(int (&arr)[4]){ and call it as changeArray(arrayX); demo: http://coliru.stacked-crooked.com/a/b6c76515ad1e091e -- that's just to illustrate the difference between passing by reference and passing a pointer.

If I added delete[] arrayX; at the end of the second code would that get rid of the memory leak?

Yes, though a better solution would be to use C++ properly and define that array as std::vector<int> arrayX;

[idknuttin]

@Cubbi, thank you for your answers, I just have one last question. If there is a memory leak in my second code, then why isn't there a memory leak in my first code? Is it because arrays automatically return the ram back to the computer once the program ends, meaning that if I put delete[] arrayX; at the end of my first code it wouldn't really do anything?

[jonnin]

you can't delete arrays. As I tried to say, they are on the stack, allocated in memory differently, that is THE main difference between arrays and pointers. That delete statement will fail. If you force it by taking an address to an array into a pointer then delete, it will either crash or fail quietly, I can't remember, but it won't work properly for sure, it either won't delete at all or it will fail.

[Cubbi]

If there is a memory leak in my second code, then why isn't there a memory leak in my first code?

The first program does not call new. It places the array on stack. When the function (not the program) ends, all local variables are destoyed and deallocated, including that array.

The second program places the array on the heap and does not use a vector or a unique_ptr to refer to it (as it should!), so when the function ends, the array remains in memory.

[48T7M4Gy]

all local variables are destroyed and deallocated, including that array

... as part of going out of scope.

[48T7M4Gy]

arrays vs sequences is interesting in that mathematically they are the same, perhaps arrays are a special case of sequences but that is a fairly loose hierarchy.

There is a difference in C++/C in that arrays are a built-in data structure and sequences are not. But there is no reason why they can't be implemented in either language, especially if they are the same.