C++ Arrays

Basics

Arrays are commonly used to store multiple values. It's one of the basic data structures. We can use it to model a list/array/collection of items. Say, an array of cellphone numbers, an array of first names, etc.

To declare an array in C++, we need to specify 3 things, using the square bracket notation.

• Data Type
• Size
• Name of the array

For example,

float scores[5];

To initialize values in the array during declaration, we can use the curly bracket notation.

float scores[5] = {90.5, 88, 75.5, 89, 95.5}

Or simply omitting the size, the compiler is smart enough to count the number of values to be inserted.

float scores[] = {90.5, 88, 75.5, 89, 95.5}

We can access each of the values in an array by its index, using the square bracket notation. C++ is zero-indexed, meaning the first value in the array has an index of 0.

For example, to retrieve the second scores from the scores array, we can simply

cout << scores[1] << endl;

If the fourth score should be 98 instead of 89, we can modify the value by index as well

scores[3] = 98;

Iteration

Since there are multiple values in an array, and each of value can be controlled by its index, we can easily loop through an array with a loop.

With a for loop,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <iostream>

using namespace std;

int main()
{
    string fruits[4] = {"apple",
                        "banana",
                        "coconut",
                        "durian"};

    for (int i = 0; i < 4; i++)
    {
        cout << fruits[i] << endl;
    }

    return 0;
}

Or with a while loop,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>

using namespace std;

int main()
{
    string fruits[4] = {"apple",
                        "banana",
                        "coconut",
                        "durian"};

    int i = 0;
    while (i < 4)
    {
        cout << fruits[i] << endl;
        i++;
    }

    return 0;
}

Both of the above looping examples are not elegant enough since we hardcoded the number of values in an array, which is not necessary.

sizeof() would return the size in bytes. When we divide the size in bytes of an array by the size of data type, there comes the number of values.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <iostream>

using namespace std;

int main()
{
    string fruits[4] = {"apple",
                        "banana",
                        "coconut",
                        "durian"};

    int i;
    int size = sizeof(fruits) / sizeof(string);
    for (i = 0; i < size; i++)
    {
        cout << fruits[i] << " ";
    }

    cout << endl;

    i = 0;
    while (i < size)
    {
        cout << fruits[i] << " ";
        i++;
    }

    cout << endl;

    return 0;
}

Modern C++ also support foreach like loop to iterate all the values,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <iostream>

using namespace std;

int main()
{
    string fruits[4] = {"apple",
                        "banana",
                        "coconut",
                        "durian"};

    for (string fruit : fruits)
    {
        cout << fruit << endl;
    }

    return 0;
}

Assignment 12

Create a C++ program named score-keeper.cpp that would prompt the user for the number of scores it's going to keep. Then it asks the user to enter a numeric value score for that given number of times. Finally it displays the average of the scores.

A sample run looks like the following.

g++ score-keeper.cpp -o score-keeper
./score-keeper
Enter number of scores: 3
Enter score: 100
Enter score: 99
Enter score: 60
Average score is 86.3333

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <iostream>

using namespace std;

int main()
{
    int numScores;
    cout << "Enter number of scores: ";
    cin >> numScores;

    float scores[numScores];
    for (int i = 0; i < numScores; i++)
    {
        cout << "Enter score: ";
        cin >> scores[i];
    }
    float total = 0;
    for (float score : scores)
    {
        total += score;
    }
    cout << "Average score is " << total / numScores << endl;

    return 0;
}

Multi-Dimensional Arrays

A multi-dimensional array is a set of embedded arrays. For example, a 2D array is an array of arrays. A 3D array is an array of 2D array.

To declare a 2D array, define the variable type, specify the name of the array followed by square brackets which specify how many elements the main array has, followed by another set of square brackets which indicates how many elements the sub-arrays have.

In case we have higher dimensional arrays, we simply keep on adding square brackets to generate more dimensions.

For example, we have to create an array to keep the scores for all 3 students in a class, where all students study the same 4 subjects. We can use a 2D (3x4 or 4x3) array to store the information.

float scores[3][4];

Similar with ordinary arrays, we can initialize the values upon declaration. But since we have more dimensions, the curly bracket notation becomes embedded as well.

float scores[3][4] = {
    {90, 85, 64, 72},
    {100, 100, 100, 50},
    {80, 90, 99, 95},
};

Accessing and changing values in a multi-dimensional array is conceptually same with the ordinary one. But instead of using one index, we have to use multiple index to refer to its location in different dimensions.

scores[0][1]=80;
cout << scores[0][1] << endl;
cout << scores[2][3] << endl;

And to loop through the entire array, we normally need to use embedded loops.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <iostream>

using namespace std;
int main()
{
    float scores[3][4] = {
        {90, 85, 64, 72},
        {100, 100, 100, 50},
        {80, 90, 99, 95},
    };

    for (int i = 0; i < 3; i++)
    {
        cout << "Student " << i + 1 << ":" << endl;
        for (int j = 0; j < 4; j++)
        {
            cout << "\tSubject " << j + 1 << ":" << scores[i][j] << endl;
        }
    }

    return 0;
}

Assignment 13

Create a C++ program named multi-score-keeper.cpp that would prompt the number of players to begin with. Then it prompts the user for the number of scores it's going to keep for each player. Then it asks the user to enter numericals for all players' scores. Finally it displays the average of the scores for each player.

A sample run looks like the following.

g++ multi-score-keeper.cpp -o multi-score-keeper
./multi-score-keeper
Enter number of players: 2
Enter number of scores: 2

Play 1:
Enter score 1: 100
Enter score 2: 90

Play 2:
Enter score 1: 80
Enter score 2: 77

Average score of Player 1 is 95
Average score of Player 2 is 78.5

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <iostream>

using namespace std;

int main()
{
    int numPlayers, numScores;
    cout << "Enter number of players: ";
    cin >> numPlayers;
    cout << "Enter number of scores: ";
    cin >> numScores;
    cout << endl;

    float scores[numPlayers][numScores];
    float averages[numPlayers];

    for (int i = 0; i < numPlayers; i++)
    {
        cout << "Player " << i + 1 << ":" << endl;
        for (int j = 0; j < numScores; j++)
        {
            cout << "Enter score " << j + 1 << ": ";
            cin >> scores[i][j];
        }
        float total = 0;
        for (float score : scores[i])
        {
            total += score;
        }
        averages[i] = total / numScores;
        cout << endl;
    }

    for (int i = 0; i < numPlayers; i++)
    {
        cout << "Average score of Player " << i + 1 << " is " << averages[i] << endl;
    }
    return 0;
}

Strings

A string variable in C++ is a collection of characters. We can use the square bracket notation to access and modify the value in a string.

For example,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <iostream>

using namespace std;

int main()
{
    string car = "tesla";

    cout << car[0] << endl;

    car[0] = 'T';

    cout << car << endl;

    return 0;
}

For convenience, we can use length() or size() to get the length of a string.

cout << car.length() << endl;
cout << car.size() << endl;

The + operator when used with strings, it operates as concatenation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#include <iostream>

using namespace std;

int main()
{
    string firstName = "Peter";
    string lastName = "Parker";
    string fullName = firstName + " " + lastName;
    cout << fullName << endl;

    return 0;
}

In C++ a string variable can store whitespaces. But cin considers whitespaces as a terminating character. If we want the freeform text from terminal, use getline instead.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <iostream>

using namespace std;

int main()
{
    string input1;
    cin >> input1;
    cout << input1 << endl;

    string input2;
    getline(cin, input2);
    cout << input2 << endl;

    return 0;
}

There are other functions that may be useful for string.

For example,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <iostream>

using namespace std;

int main()
{
    string car = "tesla";
    cout << car << endl;

    car.push_back('!');
    cout << car << endl;

    car.pop_back();
    cout << car << endl;

    car.erase(0, 1);
    cout << car << endl;

    car.insert(0, "T");
    cout << car << endl;

    car.append(" and Ford!");
    cout << car << endl;

    string number1 = "123";
    cout << stoi(number1) + 100 << endl;

    string number2 = "123.45";
    cout << stof(number2) + 100 << endl;

    return 0;
}

Assignment 14

Let's use J3 from 2021 as an exercise.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <iostream>

using namespace std;

int main()
{
    string s, prev;
    while (true)
    {
        cin >> s;
        if (s == "99999")
        {
            break;
        }
        int sum = int(s[0] - '0') + stoi(s.substr(1, 1));
        cout << sum << endl;

        if (sum == 0)
        {
            cout << prev << " ";
        }
        else if (sum % 2)
        {
            prev = "left";
            cout << "left ";
        }
        else
        {
            prev = "right";
            cout << "right ";
        }
        cout << s.substr(2, 3) << endl;
    }
}

Dynamic Programming

We often use multi-dimensional arrays to solve dynamic programming problems. Let's solve Lattice paths.

Dynamic programming is a method to simplify a complex problem into simpler sub-problems recursively. In this manner we can forward propagate to find the result by solving easy problems.

Use the Lattice paths problem for example. Think about the scenarios for:

1. 0x0 grid
2. 1x1 grid
3. 1x2 grid
4. 2x1 grid

Assignment 15

Create a C++ program named edit-distance.cpp that would prompt the user for two strings. Given two strings str1 and str2 and below operations that can be performed on str1. Find minimum number of edits (operations) required to convert str1 into str2.

1. Insert
2. Remove
3. Replace

Here are a few examples.

Example 1

Input: str1 = "cat", str2 = "cut"

Output: 1

Explanation: We can convert str1 into str2 by replacing a with u.

Example 2

Input: str1 = "sunday", str2 = "saturday"

Output: 3

Explanation: Last three and first characters are same. We basically need to convert un to atur. This can be done using below three operations. Replace n with r, insert t, insert a

A sample run looks like the following.

g++ edit-distance.cpp -o edit-distance
./edit-distance
str1: sunday
str2: saturday
edit distance is 3