Counting arrays

Why this matters

Many programs need to know how often each thing appears. A shop wants to know how many orders came in on each day of the week. A teacher wants to know how many students scored each mark from 0 to 10. A word game wants to know how many times each letter appears in a word.

The slow way is to take each value and scan the whole list again to count the matches. If the list has n values, that means about n times n comparisons. For a list of 10,000 values, that is about 100 million checks. A counting array does the same job in one pass, which means one loop that visits each item once, with about n steps.

The idea: the value is the shelf number

Imagine a row of numbered boxes, one box for each possible value. Each time you see a value, you walk to its box and drop in a token. When you finish, the number of tokens in each box is the count for that value. You never have to search the pile again.

In C++, the boxes are the slots of an array, and the box number is the array index. An index is the position of an item inside an array, counted from 0. If the array is called counts, then the value v selects the slot counts[v]. The counting step is one line:

counts[v] += 1;

The += 1 means "add one to what is already there". Each slot starts at 0, so after the loop each slot holds the number of times its index appeared.

Two conditions make this work:

• Every value must be a whole number that can be used as an index, such as 0, 1, 2 and so on.
• The array must have a slot for every value you might see.

The rest of the lesson shows how to meet those conditions, and what to do when the values are too large to meet them.

Worked example 1: counting dice rolls

A die has faces 1 to 6. Suppose you roll it ten times and write the results down: 3, 1, 6, 3, 3, 5, 1, 6, 2, 3. How many times did each face come up?

Face 6 needs slot 6. The array therefore needs seven slots, with indexes 0 through 6. Index 0 is never used. Wasting one slot is a fair price, because the index then matches the face number, and the code is easier to read than code that subtracts 1 everywhere.

The output is:

face 1: 2
face 2: 1
face 3: 4
face 4: 0
face 5: 1
face 6: 2
size of counts: 7

Here is what each part does.

• std::vector<int> counts(7, 0); creates seven int slots and sets each one to 0. A vector is the resizable array from the vectors lesson earlier in this module. The 0 matters: without it, the slots would hold leftover values from memory.
• for (int roll : rolls) visits each value in the list in turn. The loop variable roll holds one value at a time.
• counts[roll] += 1; adds one to the slot for that face. A roll of 3 adds one to counts[3].
• The last loop prints faces 1 to 6. It starts at 1 because slot 0 has no meaning here.

Check the answer by hand. The face 3 appears at positions 1, 4, 5 and 10 of the list, so the count is 4. The program agrees.

Worked example 2: counting letters in a word

Letters are a good next step, because a letter is stored as a number. Each character has a code, and the codes for the letters a to z come one after another. Subtracting the code of a from a letter gives a number from 0 to 25: 'a' - 'a' is 0, 'b' - 'a' is 1, and 'z' - 'a' is 25. The char arithmetic lesson in the variables module explains why this works.

Here the array has a fixed size, so std::array fits better than a vector. std::array is an array whose size is set at compile time and cannot change. Its size is part of its type, which is written std::array<int, 26>.

The output is:

i: 4
m: 1
p: 2
s: 4

Some details to notice.

• std::string_view is a read-only view of text. It does not copy the characters, so it is a cheap way to hold a string literal such as "mississippi".
• std::array<int, 26> counts{}; uses empty braces, which set every slot to 0. For arrays of numbers, that is the same as writing zeros out by hand.
• static_cast<char>('a' + i) turns the index back into a letter for printing. static_cast is the explicit way to tell the compiler "convert this value to that type on purpose".
• Letters with a count of 0 are skipped by the if. The output lists only the letters the word uses, in alphabetical order, because the slots are in alphabetical order.

Worked example 3: anagrams and the most frequent digit

Two words are anagrams when they use the same letters the same number of times. listen and silent are anagrams. rat and car are not, because rat has a t and car has a c.

A counting array can check this in one pass with a trick. Add one for each letter of the first word. Subtract one for each letter of the second word. If every slot ends at 0, the letters matched exactly.

The output is:

listen / silent: true
rat / car: false
most frequent digit in 4071442144: 4

Trace the rat and car case by hand. After the first loop, the slots for r, a and t are each 1. The second loop subtracts one for c, a and r. Now r is 0, a is 0, t is still 1 and c is -1. Two slots are not 0, so the function returns false.

The digit function uses the same idea with ten slots, one for each digit. The digit c - '0' is the number the character stands for, so the character '4' goes to slot 4. The digit 4 appears five times in 4071442144, which is more than any other digit, so the answer is 4.

The check counts[d] > counts[best] uses a strict greater-than. If two digits tie, the first one found, which is the smaller digit, wins. A >= would pick the later digit instead. Either choice is valid, but the program should say which one it makes.

When the values are large

A counting array needs one slot for every possible value. That works well when the range is small, such as digits, letters or the faces of a die. It breaks down when the range is large.

Suppose the values run from 0 to one billion. A counting array would need 1,000,000,001 slots. With g++ on Linux, sizeof(int) is 4 bytes, so the array needs about 4 GB of memory even when the input has only three values. This is the output of the size arithmetic, computed without allocating the array:

slots for 0 to 1000000000: 1000000001
bytes needed: 4000000004

Three options handle large values. Each one trades something.

The first is an offset. If the values run from -5 to 5, add 5 to every value before using it as an index. The value -5 then goes to slot 0 and the value 5 goes to slot 10. This works for any range that is small and known in advance, including ranges with negative numbers. It does not help a range of a billion.

The second is a map. A map is a container that stores a key and a value together, and it only creates an entry for keys that appear. The C++ std::map and std::unordered_map are covered in the maps and sets lesson later in this course. A map uses memory only for the values that appear, so it handles a range of a billion easily. Each lookup costs more than a plain array index.

The third is coordinate compression. This keeps the array but shrinks it to the number of distinct values. The steps are:

1. Copy the values and sort the copy.
2. Remove the duplicates from the sorted copy.
3. For each original value, find its position in the sorted copy. That position is its index.

Here is a program that does this for three large values. long long is a whole-number type that holds larger values than int.

The output is:

7: 1
42: 3
900000000: 2

std::unique moves the repeated values to the end of the list, and erase removes them. After that, the list holds each distinct value once, in order. std::lower_bound finds the first position where a value fits in a sorted list. Because the value is in the list, that position is the value's own position. The counts array now has three slots, not a billion.

Coordinate compression costs time. Sorting takes about n times log n steps, where log n is the number of times you can halve n before reaching 1. Each lower_bound takes about log n steps. The total is still far less than the cost of the n times n search from the start of the lesson. It also needs the whole input before it can start, so it does not suit a stream of values that arrive one by one. For that case, a map is the better choice.

Common mistakes

Using an index that does not exist

The most common error is an index one past the end of the array. In this program, the array has six slots, which are indexes 0 to 5. A roll of 6 needs index 6.

This program compiles without a warning, and the [] operator does not check the index. On this build of g++ 15 the standard library checks it anyway, and the program stopped with this message:

/usr/include/c++/15/bits/stl_vector.h:1263: constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](size_type) [with _Tp = int; _Alloc = std::allocator<int>; reference = int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.

The file path and line number depend on your install. The message is long, but the last part says what happened: __n < this->size() failed. The value __n is the index, and this->size() is the number of slots. Other builds may not check at all. Then the write goes into memory that does not belong to the array, and the program may seem to work until something else breaks. The fix is to size the array from the largest value you expect, plus one.

Using a character as an index

A letter such as 'm' is not the number 0 to 25. In the usual character table, 'm' is the number 109. An array of 26 slots indexed with counts[c] would be out of range for almost every letter. The fix is counts[c - 'a'], as in worked example 2.

Using at() to read the error

The at() function checks the index and throws an error when it is out of range. A throw is a way of stopping the normal flow and reporting an error. Here is the same mistake with at():

The program stops with this output:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 9) >= this->size() (which is 7)

The message names the exception, std::out_of_range, and gives the bad index and the size. Use at() while you are testing, because a wrong index then fails at once with a clear message. Plain [] is faster, so many programs use it once the code is known to be right. One practical point: text printed just before a crash may not appear in the output, because the program stops before it writes its held text to the screen. Print the important lines before the risky step, or run the program in a debugger.

Comparing a signed int with size()

The size() function returns an unsigned type, which cannot hold a negative number. Comparing it with an int produces a warning under -Wall:

std::vector<std::vector<int>> m = {{1, 2}, {3, 4}};
for (int i = 0; i < m.size(); ++i) {
    std::cout << m[i][0] << "\n";
}

The compiler prints this warning:

warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]

The fix is to use std::size_t for the loop variable, or to use a range-based loop when the index is not needed. The matrix rotation lesson uses std::size_t for every index.

Reusing a counts array without clearing it

A counts array keeps its numbers until you change them. If you count one list, then count a second list into the same array without setting the slots back to 0, the two counts are added together. Create a new array for each list, or fill the old one with zeros before you start.

Practice

Exercise 1

The ages of five people are 18, 21, 18, 35 and 21. Using a counting array, how many people are age 21, and what is the size of the array you need?

Show the answer

Two people are age 21. The largest age is 35, so the array needs 36 slots, with indexes 0 to 35. Index 21 holds the count 2.

Exercise 2

Write the index used for each letter of the word zebra when the array has 26 slots and is indexed as in worked example 2. Which letter has the largest index?

Show the answer

The indexes are 25 for z, 4 for e, 1 for b, 17 for r and 0 for a. The letter z has the largest index, 25, because z is the 26th letter of the alphabet and indexes start at 0.

Exercise 3

Use the counting trick from the anagram example to decide whether night and thing are anagrams, and say what the slots look like at the end.

Show the answer

They are anagrams. After adding the letters of night and subtracting the letters of thing, every slot is 0. The letters n, i, g, h and t each appear once in both words, so each slot cancels to 0.

Exercise 4

Values run from -5 to 5. Give the formula for the index of a value v, and state the array size.

Show the answer

The index is v + 5, and the array needs 11 slots. The value -5 goes to index 0, the value 0 goes to index 5, and the value 5 goes to index 10.

Exercise 5

A sensor reports readings such as 1000000007. Why is a counting array a poor choice for these readings, and what would you use instead?

Show the answer

A counting array with one slot per possible value would need about 1,000,000,008 slots, which is roughly 4 GB, and most of those slots would stay 0. Use a std::map or std::unordered_map if the readings arrive one at a time, which stores only the readings that appear. Use coordinate compression if all readings are available before counting starts, which needs one slot for each distinct reading.

Summary

• A counting array uses the value itself as the index, so counts[v] += 1 tallies one value in one step.
• Size the array to cover every possible value, and remember that indexes start at 0.
• For letters, subtract 'a' from a character to turn it into an index from 0 to 25.
• A counts array can check anagrams by adding one for the first word and subtracting one for the second.
• Large or negative value ranges need an offset, a map, or coordinate compression, each with its own cost.
• An index outside the array is undefined behaviour in C++. Use at() while testing to get a clear error.