Skip to main content

Arrays/Vectors

Some more caveats

Introduction

So far we've learnt 1 way to declare an array and covered some related aspects related to that.

In this article, we'll answer a few more things like:

  1. What exactly is this stack memory?
  2. Is there any other way of creating an array?
  3. Is it okay to create variable-length arrays?
  4. Creating an Array in a function v/s globally

Let's roll!

Types of Memories

As I said in the last article, RAM is divided into different memories, and different types of data related to your code are stored in different places. Here's a brief overview:

  1. Stack Memory:
    • Local variables, which are variables declared within a function or a code block, are typically stored on the stack.
    • Memory for these variables is allocated when the function is called and deallocated when the function exits.
    • The stack is a relatively small and fast region of memory.
  2. Heap Memory:
    • Dynamically allocated variables, such as those created with the new keyword, are stored on the heap.
    • Memory for these variables must be explicitly allocated and deallocated by the programmer. (i.e. deallocation isn't done automatically when the function exits.)
    • The heap is a larger but slower region of memory.
  3. Global Variables:
    • Global variables are stored in a separate memory area, often in a data segment.
    • They persist throughout the program's execution and are accessible from any part of the program.

Okay, enough theory. Let's sum things up.

  1. If you're creating an array normally (int arr[10];) in a function, then it'll be stored in the stack memory (which is a relatively small region, but fast).
  2. If you do it globally, it will go in something called the "data segment".
  3. And finally, if you do it using the new keyword (we'll see how), then no matter if it's in a function or globally, it'll use the heap memory (which is a relatively slower, but larger section of memory).

A "new" way to create an Array

As I've written in the Heap Memory section and summing things up above, another way to create is using the new keyword. Here it goes.

int *arr = new int[100]; //type *arr_name = new type[arr_size]

The above code simply creates an integer array arr of size 100. Now, this array, whether created in a function or globally, has some of the Heap Memory allocated to itself.

Pro Con
It allows to create larger
arrays compared to the
standard int arr[N];
It's a bit slower. From personal
experience, not slow enough to
actually matter though.
An optional piece of information.

If you remember, another thing about heap memory is that the deallocation of memory isn't done automatically when the function exits.

This means that, even though the array is no longer in use after the function ends, that particular part of memory will still be taken up, i.e. not available for use for any other purposes until the program is running.

Now, to deallocate the memory, the following code is used.
delete [] arr;

Creating variable-sized Arrays

Regarding this, let's not beat around the Bush and just get to it.

If you try and create a variable-sized array in either the stack memory or the heap memory, sure, it'll work on almost all the online judges unless the desired size is really large. (like 1e15 or something)

The code to do so is as follows:
// In stack memory
int arr[n];

// In heap memory
int *arr = new int[n];

Having said that, I've read things online that ask to avoid this stating reasons like Stack Overflow (in the case of stack memory), inefficiency (in the case of heap memory), error-prone, difficulty debugging etc.

I'll add two more points:

  1. I haven't faced any issues with this in online contests xD (I generally used heap memory)
  2. In interviews, I preferred using vectors over variable-sized arrays because vectors actually solve the problem of being able to modify the size of the array even after it's created.

Creating an Array in a function v/s globally

I'll just explain my point using this exercise I just did on my laptop which has 16 GB RAM.

#include<bits/stdc++.h>
using namespace std;

const int n = 1e5;

// int arr[n];

int32_t main()
{
    double kbs = (n*4)/1024.0, mbs = kbs/1024.0, gbs = mbs/1024.0;
    cout << kbs << " kbs\n";
    cout << mbs << " mbs\n";
    cout << gbs << " gbs\n";

    int arr[n]; // Try creating an array.
    // int *arr = new int[n];
    return 0;
}

So, I started with n = 105 , kept increasing the value of n, and tried creating an array in:

  1. Stack Memory:
    • The system gave up after n = 2*106.
    • The maximum memory possible to be allocated was only about 7-8 MB. (which is less than 0.1% of the total RAM)
  2. Heap Memory and Globally:
    • The system kept running even till n = 3*109 where the memory required is about 11 GB.