14. Arrays

An array is an ordered collection of items all of the same type. Arrays are somewhat similar to the lists we used in Python. We index them with square brackets [], and the indexing starts at zero. However, the size of an array is fixed when it is declared.

14.1. Declaring and Initializing Arrays

Array variables are similar to normal variables, but after the variable name, one pair of square [ ] brackets is present for each dimension of the array. Uninitialized arrays must have the dimension(s) listed within the brackets.

To initialize an array, place data in curly {} braces following the equals sign, with each value separated by commas. Arrays may be partially initialized by providing fewer elements than the size of the array. The remaining array elements are initialized to zero. If an array is completely initialized, then the dimension of the array is not required - the compiler has enough information to appropriately size the array. When explicitly declaring the size of the array, the dimensions must be positive integer constants, constant expressions, or positive integer variables.

//filename: array_declare.cpp
//complile: g++ -std=c++17 -o array_declare array_declare.cpp
//execute: ./array_declare
#include <iostream>

int main(int argc, char *argv[]) {
    int numbers[10]; /* declares an array called numbers with 10 integers, values not initialized */ 
    int contestants[] = {1, 2, 3}; /* array of 3 elements initialized with the values of 1,2,3 */
    float averages[5] = {7.6, 3.2}; /* array of 5 elements, the last 3 elements are zeros */

    const int nRows = 20;
    const int nColumns = 40;
    int matrix[nRows][nColumns]; /* declares a matrix */

    /* Create an array where the size comes from a variable */
    int numElements = 30;
    double data[numElements];
    double d = 3.14;
    std::cout << "data array size: " << sizeof(data) << "\n";
    std::cout << "size of d: " << sizeof(d) << "\n";

   return EXIT_SUCCESS;
}

14.2. Using Arrays

Access elements of an array by specifying their index in square brackets after the variable name. Array indices must be an integer type (char, int, size_t, etc.). Indices start at 0 and go to the array size - 1.

//filename: factorial.cpp
//complile: g++ -std=c++17 -o factorial factorial.cpp
//execute: ./factorial
#include <iostream>

 int main(int argc, char *argv[] ) {
     int factorial[7] = {1};

     for (int i=1; i < 7; i++) {
         factorial[i] = i * factorial[i-1];
     }
                
    for (int i = 0; i < 7; i++) {
        std::cout << "Factorial[" << i << "] = " << factorial[i] << "\n";
    }

    return EXIT_SUCCESS;
 }

For two-dimensional arrays, the first dimension is generally considered to be the number of rows, and the second dimension to be the number of columns. As with Python and lists of lists, two-dimensional arrays are considered to be an array of “single dimension arrays”. E.g., int a[3][4] is a single-dimension array of three elements. Each of those elements is a single-dimension array of 4 elements. At the bottom of the following example, you can see how C++ stores a two-dimensional array in memory. (The section discusses arrays and pointers.)

//filename: add_matrix.cpp
//complile: g++ -std=c++17 -o add_matrix add_matrix.cpp
//execute: ./add_matrix
#include <iostream>

int main(int argc, char *argv[]) {
    int a[3][4] = { { 5, 6, 7, 8 }, { 10, 20, 30, 40 }, {5, 15, 20, 25} };
    int b[3][4] = { { 1, 2, 3, 4 }, {  3,  2,  1,  0 }, {0, 1,  2,  3 } };
    int sum[3][4];
    
    for (int row = 0; row < 3; row++) {
        for (int column = 0; column < 4; column++) {
            sum[row][column] = a[row][column] + b[row][column]; 
        }
    }

    std::cout << "Result:\n";    
    for (int row = 0; row < 3; row++) {
        for (int column = 0; column < 4; column++) {
            std::cout << "\t" << sum[row][column]; 
        }
        std::cout << "\n";    /*new line to end the row */
    }    

    /* demonstrates how the data is layed out in memory */
    std::cout << "\n";
    int *ptr = (int *) a;
    for (int i = 0; i < 12; i++) {
        std::cout << *ptr << " ";
        ptr++;
    }
    std::cout << "\n";

    return EXIT_SUCCESS;

}

14.3. Arrays and Pointers

Arrays and pointers are inextricably linked in C and C++. Passing an array to a function causes the array to decay into pointer to the relevant type. By decay, the compiler loses information about the type and dimension(s) of the array. Consider the following code - in the function f, the array has decayed/become a pointer to a double.

Note: Any function that takes a built-in array as a parameter, takes a pointer to that array as well as another argument that specifies the array’s length.

//filename: decay.cpp
//complile: g++ -std=c++17 -o decay decay.cpp
//execute: ./decay
#include <iostream>

void f(double param[], size_t param_length) {
    std::cout << "size of param: " << sizeof(param) << ".  Address: " << param << "\n";
}

int main(int argc, char *argv[]) {
    double data[30];
    std::cout << "data array size: " << sizeof(data) << ".  Address: " << data << "\n";
    f(data,30);

    return EXIT_SUCCESS;
}

As array elements are accessed, we effectively perform pointer arithmetic.

int array[10];
int *ptr = array;

/* the following pairs of lines are equivalent */
array[0] = 100;
*ptr = 100;

array[5] = 500;
*(ptr + 5) = 500;

array[1] = 50;
ptr++; *ptr = 50;  /* increment the pointer, then dereference for the assignment */

The initial declaration of a static array forms a constant that cannot be altered. The constant value is the same as the address of the first element.

int arr[10];    /* arr is "pointer constant", value equals &arr[0] */
arr = arr + 1;  /* ERROR: can't re-assign to arr. Compiler message: assignment to expression with array type */

We can declare pointer variables to locations in the array and manipulate/update the pointer variable (i.e., the address that it points to).

The arithmetic that we can perform on pointers is basically adding or subtracting integers from the address values. Effectively, we move our pointer left (subtract) or right (addition) to a memory location. These moves occurs in steps of the size of the thing pointed to by the address. For example, incrementing a char pointer increases the value by one as a char variable is just a single byte. Incrementing an int pointer increases the value by four as ints use four bytes in memory.

Manipulating a pointer value that points to a regular variable, though, could change that pointer to refer to an invalid memory location. With arrays, the compiler allocates a contiguous sequence of memory locations; hence, we can manipulate pointer values as long as we stay within the bounds of that allocated space for the array.

//filename: ptr_arithm.cpp
//complile: g++ -std=c++17 -o ptr_arithm ptr_arithm.cpp
//execute: ./ptr_arithm
#include <iostream>

int main(int argc, char *argv[]) {
    int i = 10;
    char c = 'A';
    
    int *ip = &i;
    char *cp = &c;

    /* demonstrates the difference when adding 1 between int and char pointer types */
    std::cout << "i: initial address " << ip << ", incremented address " << ip+1 << "\n";   /* Note: ip+1 does not point to valid memory location */
    std::cout << "c: initial address " << cp << ", incremented address " << cp+1 << "\n";   // notice how C++ streams assumes char * is C-style string. 
                                                                                            // this output line behavior is undefined
    std::cout << "c: initial address " << (void *) cp << ", incremented address " << (void *) cp+1 << "\n";  // cast to void * to show the address

    int arr[10] = {}; 
    int *ptr = arr;

    ptr++;        /* this now points to arr[1] */
    *ptr = 1;
    
    *(ptr+5) = 6;   /* ptr + 5 is not arr[6], we had incremented ptr in line 17 */
    
    ptr = &arr[9];   /* point ptr to the memory address of the last element */
    *ptr = 9;

    --ptr;     /* ptr now points to arr[8] */
    *ptr = 8;

    for (int i=0;i<10; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << "\n";


    return EXIT_SUCCESS;
}

One way to think about pointers and array indexing is that the array index []is “syntactic sugar” for pointer arithmetic. The formula to compute the index i of an array of type T, where ptr points to the array becomes: addr(ptr + i) = addr(ptr) + (sizeof(T) + i)

14.4. Array Limitations

Arrays have a number of limitations compared to just a simple type (e.g., an int). These limitations also show the differences from Python’s lists.

1. We cannot assign one array to another.

2. We cannot directly compare arrays. We need to loop through the arrays and compare each element one by one.

3. Arrays do not know their own size. If the array has not decayed into a pointer, we can compute the size with the sizeof operators. However, the correct and safe thing to do is to track the number of elements in the array.

4. Arrays do not provide automatic bounds checking.

14.5. Invalid Array Example

While the following code does compile (although with warning messages), we cannot return the address of the array defined in the function f. Once the function exists, any space allocated to that frame on the stack is removed and can no longer be safely accessed. Either a segmentation fault will occur or an invalid value will be printed on line 11. This demonstrates a dangling pointer.

//filename: bad.cpp
//complile: g++ -std=c++17 -o bad bad.cpp
//execute: ./bad
#include <iostream>

int* f(size_t array_length) {
    int a[array_length] ;     /* allocates space for this on the call stack */
    return a;
}

int main(int argc, char *argv[]) {
    int *ptr = f(5);    /* f's return value points to a memory address */
                        /* that has been deallocated / no longer exists */

    std::cout  << *ptr << "\n";

    return EXIT_SUCCESS;
}

14.6. C++11 - Standard Library Functions: begin and end

We can also use the built-in function, sort, available in the algorithm include to sort arrays. Note, that the array name needs to be passed here, not a pointer to the first element.

//filename: sort.cpp
//complile: g++ -std=c++17 -o sort sort.cpp
//execute: ./sort
#include <iostream>
#include <algorithm>

int main(int argc, char *argv[]) {
    int numbers[] = { 4820, 3130, 3124, 1992, 1842 };

    std::sort(std::begin(numbers),std::end(numbers));  // try placing "&numbers[0]" as the argument to begin()

    for (int num: numbers) {
        std::cout << num << "\n";
    }

    return EXIT_SUCCESS;
}

14.7. C++20 - Convert a Built-in Array to std::array

Under C++20, we can easily convert a built-in array to std::array. Note: To compile this example, use g++ -std=c++20 -o convert convert.cpp

//filename: convert.cpp
//complile: g++ -std=c++17 -o convert convert.cpp
//execute: ./convert
#include <iostream>
#include <array>

int main(int argc, char *argv[]) { 
    int numbers[] = { 4820, 3130, 3124, 1992, 1842 };
   
    // create std::array from a built-in array
    auto array{std::to_array(numbers)};

    std::cout << "array.size() = " << array.size() << "\n";
    for (int num: numbers) {
        std::cout << num << " ";
    }
    std::cout << "\n";

}

14.8. C++20 - Use Span to Pass Built-In Arrays

The C++20 standard added a new type - std::span - that is a “non-owning” view over a contiguous sequence (or part of that sequence) and provides a way to safely access that data without owning or duplicating that data. By non-owning, std::span does not manage the lifetime of the data that it point to - if the data is destroyed while a std::span still references it, accessing the std::span would lead to undefined behavior. std::span by be using with any contiguous memory sequence such as std::vector, std::array, and built-in arrays. std::span does provide bounds-checked access to the underlying data. Essentially, std::span is a lightweight container tracking a pointer to the data and the corresponding size of that data. https://en.cppreference.com/w/cpp/container/span

Note: To compile this example, use g++ -std=c++20 -o span span.cpp

//filename: span.cpp
//complile: g++ -std=c++17 -o span span.cpp
//execute: ./span
#include <array>
#include <iostream>
#include <numeric>
#include <span>
#include <vector>

// passing built-in array, need size to due to "decay"
void displayArray(const int items[], size_t size) {
    for (size_t i = 0; i < size; i++) {
        std::cout << items[i] << " ";
    }
    std::cout << "\n";
}

void displaySpan(std::span<const int> items) {
    for (const auto& item : items) { // spans are iterable
        std::cout << item << " ";
    }
    std::cout << "\n";
}

// modify elements in the original data structure
void square(std::span<int> items) {
    for (int& item : items) {
        item *= item;
    }
}

int main() {
    int value_array[] = {1, 2, 3, 4, 5};
    std::array value_stdarray{11, 12, 13, 14, 15};
    std::vector value_vector{101, 102, 103, 104, 105};

    std::cout << "value_array via displayArray: ";
    displayArray(value_array, 4);

    std::cout << "values_array via displaySpan: ";
    displaySpan(value_array); // notice how the complile automatically creates the span

    std::cout << "value_stdarray via displaySpan: ";
    displaySpan(value_stdarray);
    std::cout << "value_vector via displaySpan: ";
    displaySpan(value_vector);

    // Show that passing a span still refers to the underlying data (a view into it)
    square(value_array);
    std::cout << "value_array after squaring each element: ";
    displaySpan(value_array);

    // create a span object directly, use some of the methods in span: https://en.cppreference.com/w/cpp/container/span
    std::span mySpan{value_array}; // span<int>
    std::cout << "mySpan's first element: " << mySpan.front() << "\nmySpan's last element: " << mySpan.back() << "\n";

    // access a span element via []
    std::cout << "The element at index 2 is: " << mySpan[2] << "\n";

    // spans can be used with standard library algorithms 
    std::cout << "Sum mySpan: " << std::accumulate(std::begin(mySpan), std::end(mySpan), 0) << "\n";

    // Create subviews of a container
    std::cout << "First three elements of mySpan: ";
    displaySpan(mySpan.first(3));
    std::cout << "Last three elements of mySpan: ";
    displaySpan(mySpan.last(3));
    std::cout << "Middle three elements of mySpan: ";
    displaySpan(mySpan.subspan(1, 3));

    square(mySpan.subspan(1, 3)); // change subview's contents.
    std::cout << "value_array after modify subspan: ";
    displaySpan(value_array); 
}
// Note: Adapted from C++20: How to Program by Deitel and Deitel.

14.9. C-Style Strings

A C-style string is an array of charaters terminated by a null character '\0', which signifies the end of the string.

char message[] = "Hello!";

In the above example, message is an array of 7 characters - the six visible characters plus the terminating null character. Note that we could have manually initialized each element of the array:

char message[7];
message[0] = 'H';
message[1] = 'e';
message[2] = 'l';
message[3] = 'l';
message[4] = 'o';
message[5] = '!';
message[6] = '\0';

14.10. <cstring>

The header <cstring> provides several functions to examine and manipulate C-style strings.

14.10.1. strlen()

Returns the length of a string, not including the null terminator.

#include <cstring>
#include <iostream>

int main() {
    char str[] = "Hello";
    std::cout << strlen(str);  // Outputs: 5
}

14.10.2. strpy()

Copies a string

char source[] = "World";
char destination[6];
strcpy(destination, source);

14.10.3. strcat()

Concatenates (appends) one string to another. When using strcat(), the destination string must have enough space to accommodate the concatenated result.

char hello[12] = "Hello ";  // 6 characters + 6 more for "World" and the null terminator
char world[] = "World";
strcat(hello, world);  // hello now contains "Hello World"

__Note: __strcpy() and strcat() as presented are problematic to use - especially as the destination must have sufficient room to store the resulting string. Using strncpy() and strncat() are alternatives, but not risk-free (e.g., strncpy() can leave a string without a null terminator.)

14.10.4. Others

• strcmp(): Compare two strings.

• strchr(): Find first occurrence of a character.

• strstr(): Find first occurrence of a substring.

See https://en.cppreference.com/w/cpp/header/cstring

14.11. Converting to and from std::string

With C++, you can easily convert between both styles of strings.

char cstr[] = "Hello";
std::string cppstr = cstr;   // Convert to std::string

const char* backToC = cppstr.c_str();  // Convert back to C-style string
const char* backToC = cppstr.data();   // Convert back to C-style string.  Requires C++11 or greater. Prior versions did not include null terminator

14.12. Iteration with Pointers

One of interesting things that you can do with C-style strings is to iterate over them with pointers. As you perform pointer arithmetic, the pointer can “start at” different points in the string.

In the following code block, we create a C-style string greeting. A char pointer, p, is then initialized to point to the start of the string. The while loop then iterates through the string until it reaches the null terminator. Within the loop, we print out the current character, the string as it points, and then the memory address that p contains.

//filename: iterate.cpp
//complile: g++ -std=c++17 -o iterate iterate.cpp
//execute: ./iterate
#include <iostream>
#include <iomanip>

int main() {
    char greeting[] = "Hello, World!";
    char* p = greeting;  // Pointer initialized to the start of the string

    while (*p != '\0') {
        std::cout << *p << ": " << std::setw(15) << std::left << p << " address: " << (void *) p << "\n";
        p++;
    }
    std::cout << "\n";

    return 0;
}

14.12.1. Advantages of Using Pointers with C-Style Strings

1. Efficiency: Direct memory access through pointers can be more efficient than array indexing because no additional arithmetic (like base address addition) is involved.

2. Flexibility: Pointers provide a flexible way to work with substrings. You can easily move the pointer to a desired position within the string and start operations from there. This is particularly useful in string parsing tasks.

3. Interoperability: Many C and C++ libraries/APIs use pointer-based access to C-style strings, so being comfortable with this approach allows for smoother integration with such libraries.

4. Dynamic Memory: If the C-style string is allocated dynamically (using malloc in C or new in C++), pointers are essential for accessing the string.

5. Advanced Operations: Pointers can be used to implement more advanced operations, like reversing a string in-place, or performing other in-memory manipulations directly.

14.13. Risks with C-Style Strings

C-Style strings have been extremely problematic - especially as it’s easy to have buffer overflow situations where a program writes past the allocated array and into adjacent memory or missing null terminators, which leds to undefined behavior. Wikipedia: Buffer Overflow. Whenever possible you should prefer using std::string in C++ - both safer and more versatile. If you do have to use C-style strings, be wary of buffer sizes and always ensure null termination.