Search

6.3 — Arrays and loops

Consider the case where we want to find the average test score of a class of students. Using individual variables:

That’s a lot of variables and a lot of typing -- and this is just 5 students! Imagine how much work we’d have to do for 30 students, or 150.

Plus, if a new student is added, a new variable has to be declared, initialized, and added to the totalScore calculation. Any time you have to modify old code, you run the risk of introducing errors.

Using arrays offers a slightly better solution:

This cuts down on the number of variables declared significantly, but totalScore still requires each array element be listed individually. And as above, changing the number of students means the totalScore formula needs to be manually adjusted.

If only there were a way to loop through our array and calculate totalScore directly.

Loops and arrays

In a previous lesson, you learned that the array subscript doesn’t need to be a constant value -- it can be a variable. This means we can use a loop variable as an array index to loop through all of the elements of our array and perform some calculation on them. This is such a common thing to do that wherever you find arrays, you will almost certainly find loops! When a loop is used to access each array element in turn, this is often called iterating through the array.

Here’s our example above using a for loop:

This solution is ideal in terms of both readability and maintenance. Because the loop does all of our array element accesses, the formulas adjust automatically to account for the number of elements in the array. This means the calculations do not have to be manually altered to account for new students, and we do not have to manually add the name of new array elements!

Here’s an example of using a loop to search an array in order to determine the best score in the class:

In this example, we use a non-loop variable called maxScore to keep track of the highest score we’ve seen. maxScore is initialized to 0 to represent that we have not seen any scores yet. We then iterate through each element of the array, and if we find a score that is higher than any we’ve seen before, we set maxScore to that value. Thus, maxScore always represents the highest score out of all the elements we’ve searched so far. By the time we reach the end of the array, maxScore holds the highest score in the entire array.

Mixing loops and arrays

Loops are typically used with arrays to do one of three things:
1) Calculate a value (e.g. average value, total value)
2) Search for a value (e.g. highest value, lowest value).
3) Reorganize the array (e.g. ascending order, descending order)

When calculating a value, a variable is typically used to hold an intermediate result that is used to calculate the final value. In the above example where we are calculating an average score, totalScore holds the total score for all the elements examined so far.

When searching for a value, a variable is typically used to hold the best candidate value seen so far (or the array index of the best candidate). In the above example where we use a loop to find the best score, maxScore is used to hold the highest score encountered so far.

Sorting an array is a bit more tricky, as it typically involves nested loops. We will cover sorting an array in the next lesson.

Arrays and off-by-one errors

One of the trickiest parts of using loops with arrays is making sure the loop iterates the proper number of times. Off-by-one errors are easy to make, and trying to access an element that is larger than the length of the array can have dire consequences. Consider the following program:

The problem with this program is that the conditional in the for loop is wrong! The array declared has 5 elements, indexed from 0 to 4. However, this array loops from 0 to 5. Consequently, on the last iteration, the array will execute this:

But scores[5] is undefined! This can cause all sorts of issues, with the most likely being that scores[5] results in a garbage value. In this case, the probable result is that maxScore will be wrong.

However, imagine what would happen if we inadvertently assigned a value to array[5]! We might overwrite another variable (or part of it), or perhaps corrupt something -- these types of bugs can be very hard to track down!

Consequently, when using loops with arrays, always double-check your loop conditions to make sure you do not introduce off-by-one errors.

Quiz

1) Print the following array to the screen using a loop:

Hint: You can use the sizeof() trick to determine the array length.

2) Given the array in question 1:

Ask the user for a number between 1 and 9. If the user does not enter a number between 1 and 9, repeatedly ask for a number until they do. Once they have entered a number between 1 and 9, print the array. Then search the array for the number that the user entered and print the index of that element.

You can test std::cin for invalid input by using the following code:

3) Modify the following program so that instead of having maxScore hold the largest score directly, a variable named maxIndex holds the index of the largest score.

Quiz solutions

1) Show Solution

2) Show Solution

3) Show Solution

6.4 -- Sorting an array using selection sort
Index
6.2 -- Arrays (Part II)

154 comments to 6.3 — Arrays and loops

  • Lamont Peterson

    Perhaps it’s a bit more than most folks are trying to accomplish at this point, but as I’m going through all of these lessons and especially the quizzes, I’m trying to build more complete solutions, incorporating as many of the "best practices" of programming in general, C++ in particular and many / most mentioned in the Lessons (my compliments on many correct best practices advice, too).  Still, I felt it might be helpful to share a couple of thoughts I had and a minor optimization which most people never think of (I’ve never found any C++ book in over 25 years that would mention this simple min/max search optimization, for example), therefore, I’m sharing the thoughts, here.

    I hope they prove useful to others.

    I built my solution to #2 using several functions, some of which are actually placed in other files and I include the headers.  Here are the prototypes:

    One major reason is to be reusable, but even more useful at this stage of things, it makes the logical progression easier to read and modify if needed.  I’ve found these to be very useful benefits when developing new code.

    Here is my main () function:

    You’ll note that I’ve also added error checking and reporting in my findArrayElement () function, which is checked for in main () in case the requested number isn’t found.  The commented out version of the array[] initializer has such gaps (namely, -1 and 0).  The NOT_FOUND code is -2, and (of course) I have no problems using such error codes in this example.  The lesson here is, because arrays cannot have less than zero elements, the negative integers for error codes can never conflict.  Whenever one writes code, they should be able to identify and report errors where it’s sensible to do so and applying a little logical thinking can make the error reporting robust, too.

    Here are the findArrayMax () and findArrayMin () functions:

    The findArrayMax () function is easy to understand and the logic of how to start off, using "int max = 0;" as done in the Lessons is also easy logic for beginners.  But, think about what value should you start your "int min = ??" at?  If you start at 0 (zero), but the minimum value in the set is greater than 0, then your code won’t work.  Pause a second and go back to finding maximum, and the same problem exists.  Now, if we were working with unsigned integers, we could bound the start of min and the start of max (initial values before starting the array searches) at "int max = 0" and at "int min = 65535" (or other value, depending on the sizeof (int)).  For max, this appears to be easier to figure out than for min, and one could certainly go off and write a "fancy" bit of code to ensure that min starts with the largest possible value for the type in use.  That would be ugly, but I have a better solution.

    This very simple code optimization does two things for us, by simply initializing max or min with the value in the first array element (e.g., array[0]); first, we loop one less time, because the first comparison is now between array[0] and array[1], from which min (or max) will now hold the smaller (or larger) of the two, then as we loop, we compare the rest of the array elements against the smaller (or larger) of the first two elements; second, we don’t have to care about hardcoding a starting value for comparison, at all, because if the first value is the smallest (or largest) in the array, it works, but if not, it still works.

    One less trip through the loop isn’t too big of a deal, but it’s still technically an optimization.  Not having to bother with figuring out the bounds of the search at all and letting it find the bounds on it’s own … priceless.

    TL;DR

    Too late, right?

    For those who are interested in the rest of my solution’s code, here’s the complete program in one file:

  • Finn St John

    Hi alex,

    I think i missed this in an earlier lesson, but why, in the increment statement of your for loops do you increment before and not after? is it bad to increment after?

    • Alex

      Because pre-increment is more performant than post-increment.

      In most cases, it probably won’t matter (the compiler should optimize this for you).

      It’s not “bad” to do a post-increment instead of a pre-increment, it’s just not quite as good.

  • John Halfyard

    The solution to question#2, when executed, accepts the value of "4h".  So it as long as you put an integer between 1-9 then you can put anything after it.  How can this be fixed?

    • Alex

      Depends on how you want to fix it. Easiest thing to do is do a std::cin.ignore(32767, ‘\n’) after accepting the user input to get rid of any extraneous input (in this case, the ‘h’).

  • Rohit

    I wonder if this line:  

    const int numStudents = sizeof(scores) / sizeof(scores[0]);

    is a good candidate for the typedef size_t ? so something like const std::size_t = sizeof(scores) / sizeof(scores[0]);

    Since the time I have read about it, I am trying to find a good place to use it. From what I have read, it looks like it’s a good candidate for storing the output of sizeof operations..

    Can you confirm/deny this usage of size_t

    • Alex

      size_t is a typedef for an unsigned int (the size of the int isn’t specified and may vary). Size the sizeof() operator returns a size_t, and this calculating is the division of two size_t’s, it seems like using size_t here would be appropriate.

  • Peter B

    Hi. May I ask, what do you think about the following code? It’s not really suitable for ongoing usage but if you use the code only once, it produces the same result as your solution for Quiz #2, but only it uses one loop less.

  • samir sabbah

    [/
    #include <iostream>

    using namespace std;

    int num;

    bool Invalid()
    {
        do
        {
            cout<<"Please enter a number between 1 and 9 : ";
            cin>>num;
        }while(num < 1 || num > 9);

        return false;
    }

    void printArray()
    {
        int array[] = { 4, 6, 7, 3, 8, 2, 1, 9, 5 };
        int arrayLength = sizeof(array)/sizeof(array[0]);

        if(Invalid() == false)
        {
            for(int count = 0 ; count < arrayLength ; ++count)
            {
                cout<<array[count]<<" ";
            }
            cout<<‘\n'<<array[num];
        }
    }

    int main()
    {
        printArray();

    }]

    is correct if i wrote the code for question 2 like this ??.

    • Alex

      I’m not sure why invalid returns a result at all, since it always returns false. Similarly, I’m not sure why you’re checking if the return value of invalid() is false, since this will always be the case.

  • Hi Alex and other commenters,

    This was my approach to solving question 2, I thought I would include a check to make sure that the user not only entered a number in range but that it was also an integer, it is a bit of a hacky approach but it seems to work ok, what do you think?

    • Alex

      “while (value != static_cast(value) …” definitely seems hacky.

      The best way to do this kind of thing is to read in the user’s input as a string and then do validation on the string to ensure it’s an integer.

  • Scott

    Hey Alex! Love your tutorials, thank you so much for all your hard work! I just noticed that in your quiz question 1, the question initializes arraylength at 9 and then initializes the array with the length arraylength… however, in the solution, you show the array initialized first and then initialize the arraylength with the array’s size divided by an array element size. Was this intentional? Is this answer acceptable?

    Oh, and I’ve also been meaning to ask… when I type array into my codeblocks, it seems to recognize it as an actual C++ term and turns the word green, so I’ve just been using arra instead. Is it okay to use the word array if it is a green word?

    • Alex

      Thanks for pointing out the inconsistency between the quiz question and answer. I’ve updated the quiz question to be in alignment with the answer. Whether the former method (explicitly setting the length) or the current method (deriving the length from the initialized array) is “better” depends on your constraints. If the array length must be 9, then explicitly setting the length to 9 is better because it makes this clear, and enlists the compilers help in enforcing this limit. If the array length can be set to whatever the number of initializing elements is, then it’s better to derive the length so there isn’t a mismatch between the array length and number of initializers. In this example, I think the latter is likely be less error prone, so it’s a better choice.

      array isn’t a reserved word in C++, so it’s fine to use. However, many syntax highlighters do highlight it as a reserved word even though it’s not. Visual Studio does because it’s a reserved word in C++/CLI. I’m not sure what Code::Blocks’ reason is.

Leave a Comment

Put C++ code inside [code][/code] tags to use the syntax highlighter