tags:
  - Cpp

Standard Array Basics (ENG)

This note is not about std::array at the first place. We are going to talk about the C-style array.

What is a Array?

Array is a homogeneous data structure where you store all items of same kind together. The data is stored in a contiguous block of memory (Virtual Memory in particular). In programming languages, you could often see something like int id[100];, which basically means an array named id that can store 100 integers.

This type of data structure offers many advantages. It is easy to use, simple to index, and changes are quite straightforward. Moreover, if you are familiar with the memory layout of the operating system, you would notice that arrays allow for efficient memory usage and provide fast access to elements due to their contiguous memory allocation. (Caching and buffering)

When you want to index an element, you basically indicate the offset of the element, which starts at [0]. If you want to iterate through the entire id array, you can do it like this:

#include <iostream>

int main(){
	int id[100]; // Assuming the array is already initialized
	for(int i = 0; i < 100; i++){
		std::cout << id[i];
	}
}

But with the help of standard library, it could be like this, we would talk this later:

#include <iostream>
#include <array>

int main() {
    std::array<int, 100> id; // Assuming the array is already initialized
    for(const int& element : id) {
        std::cout << element << std::endl;
    }
    return 0;
}

This also be called range-based for loop, we will also cover this later on.

Compile Time Size Limits

C++ standard library provides a wealth of algorithms to use. We could use this function iota help us initialize our array with sequential values starting from a specified value. Below is a example of how you can do about this:

#include <iostream>
#include <numeric>
#include <iterator> 

int main() {
    int ids[100];
    std::iota(std::begin(ids), std::end(ids), 0);
    for(int i = 0; i < 100; i++) {
        std::cout << ids[i] << std::endl;
    }
    return 0;
}

Because this iterates the array, you may should include the <iterator> for a good practice.

Everything looks good so far, but there is one limitation: the size of an array is fixed, and you cannot resize it. In the example above, we have ids[100];, which is a raw array. The array size is decided only at compile time only, you cannot change this at runtime, this 100 element size is all you can get.

If you try to index an element beyond the size limit of an array, you will likely encounter an error. So, what if you want an array with a bigger range? What machine can really do for you is allocate another new piece of memory, copy the data to it, and then free the current array. And we have so called dynamic array std::vector is actually following this pattern internally, managing memory allocation and resizing automatically for you.

Standard Array

The standard array is still a fixed-size array provided by the C++ Standard Library (STL). It offers the same semantics as a struct type holding a C-style array T[N] as its only non-static data member, but it doesn't decay to T* automatically.

template<  
    class T,  
    std::size_t N  
> struct array;

Standard array can be initialized like this:

std::array<int, 3> a = {1, 2, 3};

And alone with this data type, STL provides tons of member functions you can use. Now you can access the element using at function with a bound checking.

#include <iostream>
#include <numeric>
#include <iterator> // because <array> library covered the <iterator>, you dont really need this explicitly...
#include <array>

int main() {
    std::array<int, 100> ids = {};
    std::iota(std::begin(ids), std::end(ids), 0);
    // std::iota(ids.begin(), ids.end(), 0);
    ids.at(1) = 5; // ok
    ids.at(1000) = 0; //You will get a error instead of a segmentation fault.
    for(int i = 0; i < 100; i++) {
        std::cout << ids[i] << std::endl;
    }
    return 0;
}
/*
You can also use std::fill() to initialize your array with a specific value.
#include <algorithm>
	std::fill(ids.begin(), ids.end(), 0); // Fill every element in array ids to 0
*/

Range-Based `for` Loops

#include <iostream>
#include <numeric>
#include <iterator> 
#include <array>

int main() {
    std::array<int, 100> ids = {};
    std::iota(std::begin(ids), std::end(ids), 0);
    ids.at(1) = 5; // ok
    ids.at(1000) = 0; //You will get a error instead of a segmentation fault.
    for(int element: ids) {
        std::cout << elememt << std::endl;
    }
    for(auto element: ids){
	    std::cout << element << std::endl;
    }
    return 0;
}

Array is The Best (Sometimes)

We talk about Big-Oh in computer science. We know that array operations have different time complexities based on the type of operation being performed. When we traverse an array, we have a time complexity of O(n). On the other hand, tree structures, for example, searching for an element in a balanced binary search tree has a time complexity of O(log n).