Why this matters
Many array tasks ask a yes or no question about each value. Has this value appeared before? Is this number in the list? Which numbers from 1 to 100 are missing? A quick way to answer these questions is to keep a record of the values you have met so far. The record is a boolean array, which is an array where each box holds either true or false.
Without a record, you must look back through the earlier values each time. That is the nested-loop approach, which gets slow on long arrays. The counting arrays lesson in this module uses a similar table, but each box there holds a count. This lesson keeps only a yes or no for each value.
The idea in plain words
A boolean is a value that is either true or false. In C++ the type is bool.
A seen-set is a record of which values you have met. The word "set" means a collection where each value appears at most once. The record in this lesson is an array with one box per possible value. If the value 7 has been met, box 7 holds true. If it has not, box 7 holds false.
Here is a trace of a seen-set for the values 4 8 15 8. The table shows the boxes that matter, not all of them. Each row shows the boxes before that value is read.
value read box 4 box 8 box 15 answer
4 false false false not seen before, mark it
8 true false false not seen before, mark it
15 true true false not seen before, mark it
8 true true true seen before: duplicateRead the table from top to bottom. Each row is one step. Before a value is marked, the code looks at its box. If the box already holds true, the value is a repeat. If the box holds false, the value is new, so the code sets the box to true.
The seen-set answers the question in one step per value. The code does not look back through the earlier values, so the work is proportional to the number of values, not to the square of that number.
The range must be known
A seen-set works only when the range of possible values is known before you start. The range is the smallest and largest values that can appear. The reason is that the value itself becomes the index of the box. The value 42 uses box 42, so the array must be big enough to have a box 42.
Suppose the task says every value is from 0 to 99. Then an array with 100 boxes, numbered 0 to 99, is enough. Box v stands for the value v.
If the values can be negative, the index cannot be negative. You fix this with an offset, which is a fixed number you add to every value so that all indexes are positive. For example, if the values are from -5 to 5, add 5 to each value. The value -5 then uses box 0, and the value 5 uses box 10. Exercise 4 in the practice section shows this.
The range must be small enough to fit in memory. On common compilers a bool takes one byte, so a range of one million values needs about one million bytes. A range of one billion values needs about one billion bytes, which is about 1 GB. Use a seen-set only when the range is small enough for that.
Example 1: is there a duplicate?
Here is the first program. It checks a list of values where every value is from 0 to 99. It returns true as soon as it finds a repeat.
#include <array>
#include <iostream>
#include <vector>
// The problem promises every value is in the range 0 to 99.
constexpr int kMaxValue = 99;
bool hasDuplicate(const std::vector<int>& values) {
std::array<bool, kMaxValue + 1> seen{}; // every entry starts as false
for (int v : values) {
if (seen[v]) {
return true; // this value was already seen earlier in the loop
}
seen[v] = true;
}
return false;
}
int main() {
std::cout << std::boolalpha;
std::cout << hasDuplicate({4, 8, 15, 16, 23, 42}) << "\n";
std::cout << hasDuplicate({4, 8, 15, 8}) << "\n";
std::cout << hasDuplicate({0, 99}) << "\n";
}Read the parts one at a time.
constexpr int kMaxValue = 99;sets the largest allowed value in one place. The name starts withkas a convention for a constant. A constant is a value that does not change while the program runs.std::array<bool, kMaxValue + 1> seen{};makes an array of 100 boxes, numbered 0 to 99. The empty braces{}set every box tofalse. Without them, the boxes would hold random leftover values.std::boolalphais a setting for the output stream. It makestrueprint as the wordtrueandfalseprint as the wordfalse, instead of 1 and 0.
Here is the output of the program.
false
true
falseThe first list has no repeats, so the answer is false. The second list has 8 twice, so the answer is true. The third list has 0 and 99, which are both allowed values and different from each other, so the answer is false.
Why is std::array used here instead of std::vector? The size is fixed at 100 and known when the program is compiled. An std::array is a fixed-size row of boxes, and it needs no memory allocation at run time. A std::vector is a resizable array, and it is the right choice when the size is only known while the program runs. Example 2 uses a std::vector.
Example 2: which values are missing?
Now the range is 1 to a value called maxValue, which the caller passes in. The size is not known until the program runs, so a std::vector is the right container. This example also shows that std::vector<bool> works like a boolean array.
#include <iostream>
#include <vector>
// Returns every value from 1 to maxValue that does not appear in values.
std::vector<int> missingValues(const std::vector<int>& values, int maxValue) {
std::vector<bool> seen(maxValue + 1, false); // index 0 is not used
for (int v : values) {
seen[v] = true;
}
std::vector<int> missing;
for (int v = 1; v <= maxValue; ++v) {
if (!seen[v]) {
missing.push_back(v);
}
}
return missing;
}
void print(const std::vector<int>& values) {
std::cout << "[";
for (std::size_t i = 0; i < values.size(); ++i) {
if (i > 0) std::cout << ", ";
std::cout << values[i];
}
std::cout << "]\n";
}
int main() {
print(missingValues({4, 3, 2, 7, 8, 2, 3, 1}, 8));
print(missingValues({1, 2, 3}, 3));
print(missingValues({}, 4));
}The program has two loops. The first loop marks every value that appears. The second loop walks from 1 to maxValue and collects each value whose box is still false.
Here is the output.
[5, 6]
[]
[1, 2, 3, 4]In the first call the input has 4, 3, 2, 7, 8, 2, 3 and 1. The value 2 and the value 3 each appear twice, but the second time the box is already true, and the code simply sets it to true again. That is harmless. The values 5 and 6 never appear, so they are the missing ones.
A note on std::vector<bool>. It is a special version of std::vector that packs each boolean into a single bit, so it uses less memory than a byte per value. You still write seen[v] and seen[v] = true as with a normal array. The one difference is that a std::vector<bool> does not hand out a real bool& reference, which matters only in advanced code. For this lesson, treat it as a boolean array that uses less memory.
Example 3: clearing the seen-set between tests
Many programs run the same check on many test cases. Each test needs a seen-set that starts empty. The simplest way is to clear every box before the next test. That works, but it has a cost. If the range is one million values and you run three thousand tests, clearing every box each time writes three billion false values. Most of that work is wasted, because a small test only marks a few boxes.
A better method is to remember which boxes were set and clear only those. The seen-set below does that. It keeps a second list, called touched_, that holds each value it marked. Clearing then walks that list and resets only those boxes.
#include <algorithm>
#include <iostream>
#include <vector>
// A seen-set for the range 0 to maxValue. reset() clears only the entries
// that insert() changed, so its cost depends on how many values were stored,
// not on the size of the range.
class SeenSet {
public:
explicit SeenSet(int maxValue) : seen_(maxValue + 1, false) {}
// Returns true if v was already in the set. Otherwise adds it and returns false.
bool insert(int v) {
if (seen_[v]) {
return true;
}
seen_[v] = true;
touched_.push_back(v);
return false;
}
// Clears only the entries that were set. Returns how many entries it wrote.
std::size_t reset() {
const std::size_t writes = touched_.size();
for (int v : touched_) {
seen_[v] = false;
}
touched_.clear();
return writes;
}
private:
std::vector<bool> seen_;
std::vector<int> touched_;
};
int main() {
const int maxValue = 999999;
SeenSet set(maxValue);
const std::vector<std::vector<int>> tests{
{5, 900000, 17},
{17, 42},
{999999, 0, 5, 5},
};
std::cout << std::boolalpha;
for (const auto& test : tests) {
bool sawDuplicate = false;
for (int v : test) {
if (set.insert(v)) {
sawDuplicate = true;
}
}
std::cout << "duplicate found: " << sawDuplicate << "\n";
std::cout << "entries cleared by reset: " << set.reset() << "\n";
}
// The same range cleared with a full fill would write every entry each time.
std::cout << "full fill would write " << (maxValue + 1) << " entries per test\n";
}The class has three parts. insert checks the box, marks it, and records the value in touched_. reset clears only the boxes listed in touched_, then empties that list. The main function runs three tests, and after each test it calls reset.
The output was the following.
duplicate found: false
entries cleared by reset: 3
duplicate found: false
entries cleared by reset: 2
duplicate found: true
entries cleared by reset: 3
full fill would write 1000000 entries per testLook at the second test. It holds 17 and 42. The value 17 was in the first test, but reset cleared it, so the second test sees 17 as new. The output says false, which is the right answer for a fresh test.
Look at the third test. The value 5 appears twice. The first 5 is marked, and the second 5 is found in the set, so insert returns true. That sets sawDuplicate. The touched_ list holds 999999, 0 and 5. It does not hold the second 5, because the code did not mark it again. So reset writes 3 entries, not 4.
The last line of output compares the two methods. A full fill would write 1000000 entries for each test. The reset in this program wrote 3, 2 and 3 entries. The gap grows with the range. The price is a second list, which takes memory in proportion to the number of values stored.
The same idea can be written with std::fill, which sets every box to a value. std::fill(seen.begin(), seen.end(), false); is simple and correct. Use it when most tests fill a large part of the range anyway, or when the code must stay short. Use the touched list when the range is large and each test touches only a few values.
Common mistakes
Forgetting to clear between tests
If the seen-set is not cleared, the second test sees the values left over from the first. Here is a small program with that mistake. It has two tests and never clears seen.
#include <iostream>
#include <vector>
int main() {
// Mistake: the seen array is never cleared between tests.
std::vector<bool> seen(10, false);
const std::vector<std::vector<int>> tests{{1, 2, 3}, {3, 4}};
std::cout << std::boolalpha;
for (const auto& test : tests) {
bool sawDuplicate = false;
for (int v : test) {
if (seen[v]) {
sawDuplicate = true;
}
seen[v] = true;
}
std::cout << "duplicate found: " << sawDuplicate << "\n";
}
}Here is the output.
duplicate found: false
duplicate found: trueThe second test contains 3 and 4, and 3 is not repeated within that test. The answer should be false. The program says true, because 3 was marked during the first test and never cleared. Call the clearing step at the start or end of each test, or use a seen-set class with a reset method.
Using an index outside the range
The index must be from 0 up to the size minus one. A value of 100 in an array of 100 boxes is one past the end. C++ does not check this on ordinary array access, so the write may land on other memory and the program may fail later in a confusing way.
The following program writes to box 100 of a 100-box array. It is compiled with GCC's checking option, -D_GLIBCXX_ASSERTIONS, which turns on checks in the standard library.
#include <array>
#include <iostream>
#include <vector>
int main() {
std::array<bool, 100> seen{};
std::vector<bool> seenVec(100, false);
int v = 100; // one past the last valid index, 99
seen[v] = true;
std::cout << "array done\n";
seenVec[v] = true;
std::cout << "vector done\n";
}The program stopped at the first write, before it printed array done. The error was the following.
/usr/include/c++/15/array:210: constexpr std::array<_Tp, _Nm>::value_type& std::array<_Tp, _Nm>::operator[](size_type) [with _Tp = bool; long unsigned int _Nm = 100; reference = bool&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.The message names the array, the size 100, and the failed check. On this Ubuntu install of GCC 15.2 the check ran even when the flag was left out. Other compilers may not check, so the write could go through silently. Make sure the array size is one more than the largest value, as in example 1 with kMaxValue + 1.
Sizing the array one short
A common error is to size the array from the largest value, but forget the zero box. If the values are from 1 to 100, the largest index is 100, so the array needs 101 boxes. The fix is the same as in example 1: size the array to kMaxValue + 1, where kMaxValue is the largest allowed value.
Negative values
A negative value such as -1 cannot be an index. Writing seen[-1] is out of range. Use the offset idea from the range section, and add a fixed number before indexing.
Using a seen-set when the range is huge
A seen-set costs memory in proportion to the range. Values up to 10 billion would need about 10 GB as a bool array, even if the input holds only a few values. In that case, sort the values, or use a hash set, which is covered in the maps and sets lesson of this course. The seen-set is the best choice only when the range is small.
Practice
Exercise 1
Trace hasDuplicate from example 1 on the list 3 1 2 1. At each step, say which box is read and whether the function returns.
Show the answer
Step 1: value 3, box 3 is false, so set box 3 to true. Step 2: value 1, box 1 is false, so set box 1 to true. Step 3: value 2, box 2 is false, so set box 2 to true. Step 4: value 1, box 1 is true, so the function returns true at once. The answer is true.
Exercise 2
Write a function isPermutation that returns true when a vector holds each number from 0 to n - 1 exactly once, where n is the size of the vector. Test it on {2, 0, 1}, {0, 1, 1}, {0, 3, 1} and {}.
Show the answer
#include <iostream>
#include <vector>
// True when values holds each number from 0 to n-1 exactly once.
bool isPermutation(const std::vector<int>& values) {
const int n = static_cast<int>(values.size());
std::vector<bool> seen(n, false);
for (int v : values) {
if (v < 0 || v >= n || seen[v]) {
return false;
}
seen[v] = true;
}
return true;
}
int main() {
std::cout << std::boolalpha;
std::cout << isPermutation({2, 0, 1}) << "\n";
std::cout << isPermutation({0, 1, 1}) << "\n";
std::cout << isPermutation({0, 3, 1}) << "\n";
std::cout << isPermutation({}) << "\n";
}The output is true, false, false and true. The first input is a valid permutation. The second repeats 1. The third holds 3, which is not from 0 to 2. The empty input has no values to check, so it is a valid permutation of nothing. The check v >= n comes before seen[v], so the code never reads a box that does not exist.
Exercise 3
The SeenSet class in example 3 has a reset method. A test calls insert with the values 7 and 8, then calls reset. Another test then calls reset again with no insert calls in between. What does the second reset return?
Show the answer
It returns 0. The second reset finds an empty touched_ list, so it writes nothing. The count of entries cleared is the length of that list, which is 0.
Exercise 4
The values in a test are from -5 to 5. Write the array declaration and the line that marks the value v. Then say what index the value -5 uses.
Show the answer
Use an array of 11 boxes, because the range from -5 to 5 has 11 values. The offset is 5. The declaration is std::array<bool, 11> seen{};, and the line that marks v is seen[v + 5] = true;. The value -5 uses box 0, since -5 + 5 is 0. The value 5 uses box 10.
Here is a program that uses this offset. It shows the first time each value appears and then the duplicate.
#include <array>
#include <iostream>
#include <vector>
// Values are in -5 to 5. Index = value + 5 maps -5 to 0 and 5 to 10.
constexpr int kOffset = 5;
int main() {
std::array<bool, 11> seen{};
const std::vector<int> values{-5, 0, 5, 0};
std::cout << std::boolalpha;
for (int v : values) {
const bool dup = seen[v + kOffset];
seen[v + kOffset] = true;
std::cout << v << " duplicate: " << dup << "\n";
}
}Its output was the following.
-5 duplicate: false
0 duplicate: false
5 duplicate: false
0 duplicate: trueExercise 5
A program has std::array<bool, 100> seen{}; and then marks seen[v] for values from 1 to 100. Which value causes an error, and what is the fix?
Show the answer
The value 100 causes the error, because the largest valid index in a 100-box array is 99. The fix is std::array<bool, 101> seen{};, which gives box 100 to the value 100. Box 0 is then never used, which costs one spare box and avoids the error.
Summary
- A seen-set is a boolean array with one box per possible value. A box holds
trueonce that value has been met. - The range of possible values must be known before you start, and the array must be big enough for the largest index.
- Use an offset to store negative values, by adding a fixed number to each value.
- Clear the seen-set between test cases. Either clear every box, or record the boxes you set and clear only those.
- Check each index against the array size. Writing past the end is a bug that C++ may not report.