Friday, November 02, 2012

Dynamically allocated arrays in C++

For several years, your uncle Bob has been keeping track of his finances in the following format:
    4
    potatoes       1800
    carrots        1300
    beer           2500
    tomato_sauce    500
The first line always has the number of items, and every next line has a single-word product, some spaces, and then the amount it costs. However, being a little eccentric, uncle Bob decided that he'd like to sort all his files, and that's where you come in.

You've been given the task of writing a program that reads a file, sorts the contents, and then writes them back in a similar format. For simplicity, we'll use std::cin and std::cout for reading and writing, and we won't worry about how many spaces there are between the item name and the cost.
We'll start by reading the number of items and printing it right back out:
#include <iostream>

int main() {
    int num_items;
    std::cin >> num_items;
    std::cout << num_items << '\n';
}
Nothing new here. We'd also like to have a data structure to store the item name and cost in:
struct Item {
    std::string name;
    int cost;
};
We now know our program will look roughly like:
#include <iostream>
#include <string>

struct Item {
    std::string name;
    int cost;
};

int main() {
    int num_items;
    std::cin >> num_items;
    // A: Where do we put the items?
    for (int i = 0; i < num_items; ++i) {
        Item item;
        std::cin >> item.name;
        std::cin >> item.cost;
        // B: How do we store the item?
    }
    // C: How do we sort the items?
}

While we now have a program that reads the input just fine, we still need to find something to store the items in. We can't use an array, because we don't know how many items there will be until we run the program. We want something to create an array at runtime, with the size that we specify.

C++ allows us to do this using the new[] operator. This is a strange operator because instead of taking one or two variables, it takes a type and a variable. We want an array of Items that has num_items elements, and we can do that using
new Item[num_items];
The problem with this is that we created the array, but we don't know where it is! We need to store the result of new in a variable of type Item*, pronounced "pointer to Item". We thus have
Item* items = new Item[num_items];
The fancy term for this is "dynamic allocation". By "dynamic", we mean that we can choose how long this array will keep existing ourselves. Normally, any array we create in a function will be destroyed when we return from that function; an array created with the new[] operator won't be. When you are doing using it, you must explicitly destroy it with
delete[] items;
A common mantra is: for every new[], you must have one delete[]. Our main function is thus:
int main() {
    int num_items;
    std::cin >> num_items;

    Item* items = new Item[num_items];

    for (int i = 0; i < num_items; ++i) {
        Item item;
        std::cin >> item.name;
        std::cin >> item.cost;
        // B: Store the item in the array.
    }
    // C: How do we sort the items?

    delete[] items;
}
Accessing the elements of items can be done just like if it was a normal array; to get the first element, we use items[0], and so on. We can write our for loop like this:
for (int i = 0; i < num_items; ++i) {
    Item item;
    std::cin >> item.name;
    std::cin >> item.cost;
    items[i] = item;
}
We now have working code for filling a dynamic array with data! In order to sort it, we need to write a function that determines whether one item is "less than" another or not. We are sorting the items based on price, so we the cheapest item to be the "smallest". Let's write this function, which we will call compare_items:
bool compare_items(Item const& left, Item const& right) {
    return left.cost < right.cost;
}
If the Item const& notation is new, don't worry about it; in this case, it's almost the same thing as if we'd write Item, but it may run faster.

Now we need to sort the array. That's surprisingly easy in C++:
std::sort(items, items + num_items, compare_items);
Notice how items points to the first item, and items + num_items points one past the last item. This is like saying "sort items from beginning to end, using compare_items to find out the order we want". We don't have to worry about how exactly the sorting is done; as long as compare_items is correct, items will sorted correctly.

Now all we need to do is print out the number of items, which goes just like printing out an array. The code, from beginning to end, is:
#include <iostream>
#include <string>
#include <algorithm> // needed for std::sort

struct Item {
    std::string name;
    int cost;
};

bool compare_items(Item const& left, Item const& right) {
    return left.cost < right.cost;
}

int main() {
    int num_items;
    std::cin >> num_items;

    Item* items = new Item[num_items];

    for (int i = 0; i < num_items; ++i) {
        Item item;
        std::cin >> item.name;
        std::cin >> item.cost;
        items[i] = item;
    }

    std::sort(items, items + num_items, compare_items);

    for (int i = 0; i < num_items; ++i) {
        std::cout << items[i].name << ' ' << items[i].cost << '\n';
    }

    delete[] items;
}
This program compiles and does what uncle Bob asked us to do. If you want a bit more of a challenge, you could try to do one of the following:

  1. How do you make the most expensive item come first?
  2. Could you make the output be neatly formatted, just like the input example was?
  3. Is the item object we create inside the for loop necessary? Can you rewrite the code without it?



While processing his records, uncle Bob discovered that some were missing the number of items! He wants us to write a second program that works without that number.

This is a much harder problem than the previous one. Think about how you could approach it before reading on.

Just like with a normal array, we can't make the dynamic array "grow". Instead, we create a larger dynamic array, copy the items, and then destroy the original.

However, before we do anything with dynamically allocated arrays, we need to find a way to read any number of items. Instead of using a for loop, we use "while (std::cin)" — roughly, this means "while reading from std::cin is working correctly". If we encounter bad input or reach the end of the file, we'll stop reading. The code looks something like this:
while (std::cin) {
    Item item;
    if (std::cin >> item.name && std::cin >> item.cost) {
        // add item to items
    }
}
You should read the if statement as "if we successfully read item.name and item.cost".

Let's take a look at this in the context of the rest of the program:
int main() {
    int num_items = 0;

    // create items

    while (std::cin) {
        Item item;
        if (std::cin >> item.name && std::cin >> item.cost) {
            // add item to items
        }
    }

    std::sort(items, items + num_items, compare_items);

    for (int i = 0; i < num_items; ++i) {
        std::cout << items[i].name << ' ' << items[i].cost << '\n';
    }

    delete[] items;
}
Here, we're going to cheat a little bit to avoid having a special case. We're going to start by creating items:
Item* items = new Item[1];
Notice that the one item we have doesn't mean anything yet; it's just a dummy value. Instead of using item in the while loop, we'll read directly into this dummy value:
int main() {
    int num_items = 0;
    Item* items = new Item[1];

    while (std::cin) {
        if (std::cin >> items[num_items].name && std::cin >> items[num_items].cost) {
            // add item to items
        }
    }

    // ...

    delete[] items;
}
Here's the trick: items[num_items] is valid, because the dynamic array is actually one bigger than the number of items we have. Once we did the reading, we need to create a new array, copy things over, and make items refer to the new array.
int main() {
    int num_items = 0;
    Item* items = new Item[1];

    while (std::cin) {
        if (std::cin >> items[num_items].name && std::cin >> items[num_items].cost) {
            num_items += 1;
            Item* new_items = new Item[num_items+1];
            for (int i = 0; i < num_items; ++i)
                new_items[i] = items[i];
            items = new_items;
        }
    }

    std::sort(items, items + num_items, compare_items);

    for (int i = 0; i < num_items; ++i) {
        std::cout << items[i].name << ' ' << items[i].cost << '\n';
    }

    delete[] items;
}
Take a long look at that code. It doesn't actually look all that bad, does it? You can compile it and check whether it returns the right results. But does anything seem off about it?

Count the times we use new[], then count the times we use delete[]. Every time we read a user input, we create a new array, but we never get rid of the old one. We can't access it any more, but it is still our responsibility. This is called a memory leak; it's a little like leaving the gas on when you're not cooking any more. Our program is small, so this might not be noticeable; after our program exits, the operating system cleans things up for us. If your browser did this, however, you would soon switch to something better: chances are, it would become unusable very quickly.

In order to fix this, we need to destroy the old array before we overwrite items:
int main() {
    int num_items = 0;
    Item* items = new Item[1];

    while (std::cin) {
        if (std::cin >> items[num_items].name && std::cin >> items[num_items].cost) {
            num_items += 1;
            Item* new_items = new Item[num_items+1];
            for (int i = 0; i < num_items; ++i)
                new_items[i] = items[i];
            delete[] items;
            items = new_items;
        }
    }

    std::sort(items, items + num_items, compare_items);

    for (int i = 0; i < num_items; ++i) {
        std::cout << items[i].name << ' ' << items[i].cost << '\n';
    }

    delete[] items;
}
With this in place, the program should compile and run successfully. Once more, some exercises:

  1. At the moment, we create a new array for every new item. This is very expensive; could we somehow create fewer arrays, while still allowing the user to enter as many items as they want?
  2. Try rewriting this to work without the dummy item at the end. How do you initialise items? What extra work has to be done?
  3. This is a lot of code to do something that looks quite simple. Take a look at www.cppreference.com. Can you find anything that you could use to make this easier? Rewrite the code using that.

No comments:

Post a Comment