Learn/C/13. Maps and sets in C
Lesson 13 of 15
Sign in

C, lesson 13

Maps and sets in C

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.

Small integer keys: an array

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 boolean array as a set

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.

Bit masks for tiny sets

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.

Exercise 1

Word frequency

Press Ctrl Enter or Check to test your code.

Exercise 2

Club members

Press Ctrl Enter or Check to test your code.

k

Use 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.

Text keys: a table of pairs

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 table

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.

Further reading

  • cppreference: Bitwise and arithmetic operators
  • cppreference: Bit manipulation <stdbit.h> (C23)
  • cppreference: strcmp
  • cppreference: qsort

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;   // difference
struct 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 1
Input:
5
4 8 15 16 8
3
16 4 42
Output:
Both: 4 16
Chess only: 8 15
Total members: 5