C, lesson 13
Most languages ship a dictionary type and a set type. C does not. That is not as bad as it sounds: C programmers pick the simplest structure that fits the keys they actually have. This lesson walks through the usual choices, from simplest to most general.
When keys are small non-negative integers (a dice face, an age, a letter minus 'a'), an
array is the map: the key is the index. Lookup is instant.
A set only needs to answer "is this key in it?". For keys from 0 to N-1, a bool array does
that, and set operations become one loop:
Adding a key twice changes nothing, which is exactly what a set should do. Looping over the indices in order also gives you the members sorted for free.
When there are at most 64 possible members, one unsigned long long can hold the whole set:
bit k is 1 when is in the set. The bitwise operators then are the set operations:
2 exercises to try what you just read.
kUse unsigned types for bit work, and never shift by 64 or more: that is undefined behaviour.
C23's <stdbit.h> adds stdc_count_ones to count the members of such a set.
For a handful of string keys, an array of key-value structs searched from start to end is simple and fast enough:
Each lookup scans the whole table, so with thousands of keys it gets slow.
A hash function turns a key into a number. Use that number, modulo the table size, as the starting slot. If the slot is taken by another key, try the next slot (linear probing) until you find the key or an empty slot. As long as the table stays less than about 70% full, a lookup usually checks only one or two slots, however many keys there are.
The caller checks whether the returned slot is empty, and if so copies the key in. A hash table
keeps no order, so when you need sorted output, copy the used entries into an array and qsort
it.
Read words (lowercase letters only, at most 30 characters each) separated by spaces and new lines
until the input ends. There are at most 500 different words. Print each distinct word with its
count, most frequent first; words with the same count are in strcmp order. If there are no
words, print nothing.
Use either a table of pairs or a hash table, then sort the entries with qsort.
Two clubs share a building. Member ids are whole numbers from 0 to 999. The input is a count followed by that many ids for the chess club, then a count followed by that many ids for the drama club. A list may repeat an id.
Print three lines. Lists are in increasing order, separated by spaces; an empty list is shown as
-.
Total members counts each distinct id that is in at least one club.
int age_count[130] = {0};
age_count[age]++;bool a[100] = {}, b[100] = {};
// ... fill them ...
for (int k = 0; k < 100; k++) {
bool in_both = a[k] && b[k]; // intersection
bool in_either = a[k] || b[k]; // union
bool only_a = a[k] && !b[k]; // difference
}unsigned long long s = 0;
s |= 1ULL << k; // add k
bool has_k = (s >> k) & 1; // is k in the set?
unsigned long long both = a & b; // intersection
unsigned long long either = a | b; // union
unsigned long long only_a = a & ~b; // differencestruct entry { char word[32]; int count; };
struct entry table[500];
int used = 0;
int find_or_add(const char *word) {
for (int i = 0; i < used; i++) {
if (strcmp(table[i].word, word) == 0) return i;
}
snprintf(table[used].word, sizeof table[used].word, "%s", word);
table[used].count = 0;
return used++;
}constexpr int SLOTS = 1024; // keep it well above the number of keys
struct entry slots[SLOTS]; // a word of "" marks an empty slot
unsigned hash(const char *s) {
unsigned h = 2166136261u; // FNV-1a: simple and well spread
for (; *s; s++) {
h = (h ^ (unsigned char)*s) * 16777619u;
}
return h;
}
struct entry *lookup(const char *key) {
unsigned i = hash(key) % SLOTS;
while (slots[i].word[0] != '\0' && strcmp(slots[i].word, key) != 0) {
i = (i + 1) % SLOTS; // probe the next slot
}
return &slots[i]; // the key's slot, or the empty one to claim
}Input:
the cat saw the dog
the dog ran
Output:
the 3
dog 2
cat 1
ran 1
saw 1Input:
5
4 8 15 16 8
3
16 4 42
Output:
Both: 4 16
Chess only: 8 15
Total members: 5