Problem overview
Some passwords are weak whatever they contain, because everybody tries them first. The starter code holds a list of well-known passwords in an unordered_set<string> named common, and a password to check. The program prints the password, prints whether it is in the set (True or False), and then prints Weak: reject for a common password or Strong: accept for any other.
For qwerty, which is in the set, the output is:
Password: qwerty
Common: True
Weak: reject
For Tr0ub4dor, which is not:
Password: Tr0ub4dor
Common: False
Strong: accept
Approach: ask a hash set whether it holds the password
You could compare the password with each entry of a list, one by one. A set answers the question directly: an unordered_set is a hash table, so checking whether a value is in it takes about the same time whether it holds four entries or four million. That makes it the standard tool for a question of the form "is this value in my collection?".
The program asks the set once, keeps the answer in a bool, and uses that answer twice: to print the Common line and to choose between the two verdicts.
Step by step
- Print the first line:
"Password: ", thenpassword, thenendl. - Create
bool isCommonfromcommon.count(password) > 0. For a set,countreturns 0 or 1, because a set holds each value at most once. - Print the
Commonline, choosingTrueorFalsewithisCommon ? "True" : "False". - Write an
if (isCommon)whose body printsWeak: reject. - Add the
elsethat printsStrong: accept.
The solution in C++
unordered_set<string> common = {"password", "123456", "qwerty", "letmein"};
string password = "qwerty";
cout << "Password: " << password << endl;
bool isCommon = common.count(password) > 0;
cout << "Common: " << (isCommon ? "True" : "False") << endl;
if (isCommon) {
cout << "Weak: reject" << endl;
} else {
cout << "Strong: accept" << endl;
}
Details worth a closer look:
- Printing a
string.coutprints astringvariable just like a literal, so the first line is an ordinary chain of<<. count(...) > 0turns a number into abool. The comparison is true when the value is in the set and false otherwise.- Why not
contains?unordered_set::containsexists only from C++20. With C++17 it does not compile, so the lesson usescount. Another C++17 way iscommon.find(password) != common.end(), which gives the same answer. - Asking does not change the set.
countandfindonly look. The set keeps its four entries after any number of lookups. - A bool prints as 1 or 0. That is why the
Commonline picks its words with the conditional operator, inside parentheses so the<<chain stays valid. - The
ifreads the flag directly.if (isCommon)needs no comparison, because the variable is already abool.
Complexity
Time: O(1) on average for the lookup in the hash set, plus time proportional to the password's length to hash and compare it. Space: O(1) beyond the set itself.
Edge cases and common mistakes
- Case matters.
Qwertyis not the same string asqwerty, so it is not found in the set. The output isCommon: FalseandStrong: accept. - An empty password. The empty string is not in the set, so the program prints
Password:with nothing after the space, thenCommon: FalseandStrong: accept. This version does not check the length. - Common is not the same as weak in general. This version only rejects passwords on the list. Anything else is accepted, even a short one.
- Using
countas the whole condition.if (common.count(password))also works, since 1 is true, but storing a namedboolmakes the two uses clearer. - Printing the flag directly. It would show
1or0instead ofTrueorFalse. - Using
[]. Sets don't have it. For maps,[]inserts a missing key as a side effect, which is another reason to ask withcountorfind.
Testing
| password | Output after the first line |
|---|---|
| qwerty | Common: True, then Weak: reject |
| Tr0ub4dor | Common: False, then Strong: accept |
| Qwerty | Common: False, then Strong: accept |
| (empty string) | Common: False, then Strong: accept |
The next version builds on this program.
