Sometimes you need a container that stores related pairs of values. You also want to be able to access the pairs of values relatively flexibly.
In C there is not a container like this so I will show you today how we can implement our own Map type written purely in C. We will rely on some concepts frommy article on how to implement Classes in C, so read it firstif you are interested.
If you need an overview of different containers and their advantages and disadvantages you can find them in my article here.
In this Article...
How a Map works
In some languages the Map datatype is called Dictionary and this is exactly what a Map represents. We have a Key that is present only once and thus a unique Identifier which has a corresponding Value. Key and Value do not have to be the same type.
Goals of the Implementation of a Map Class in C
We will implement a Map Class in C that is capable of the following features:
- Initialization of Map (and clean up!)
- Adding Elements to Map
- Accessing Elements in Map
- Looking Up Elements in Map
- Removing Elements from Map
- Swapping Maps
We will only implement a Map for the <int, int> Key-Value Pair. The C language is missing the <template> stuff that C++ provides so you have to make an implementation for every type that you need. (You maybe could use void-Pointers but that is a rabbit whole of it’s own…)
Map Initialization in C
We will need three files for our implementation:
- map.h– here we define the Interface for our Map
- map.c– the actual Map Implementation
- main.c– here we write a little program to test our Map
The map Interface declares the struct for the map objects as well as the initialization, construction and destruction functions. Note that the struct is only declared here but not defined. This keeps the members private. The downside to this is that you have to allocate memory with thelist_new()function in order to use it (and remember to uselist_dtr()in order to free the allocated memory).
#pragma oncetypedef struct map_t map_t;map_t* map_new();void map_ctr(map_t* obj);void map_dtr(map_t* obj);In the Implementation file the struct map_t is defined. It has the Elements for its keys, values and size. The constructor initializes the keys and values with zero memory and sets the map size to 0. This way we are able to reallocate memory for keys and values later. The destructor frees all allocated memory to prevent memory leaks.
#include "map.h"#include <stdlib.h>typedef struct map_t { int* keys; char* values; int size;} map_t;map_t* map_new(){ return (map_t*) malloc(sizeof(map_t));}void map_ctr(map_t* obj){ obj->size = 0;}void map_dtr(map_t* obj){ if(NULL != obj) { if(NULL != obj->keys) { free(obj->keys); } if(NULL != obj->values) { free(obj->values); } free(obj); }}The first test program does nothing besides creating and destroying a stack object. Its only purpose is to test the functions we just implemented.
# include "map.h"int main(int argc, char** argv){ map_t* my_map = map_new(); map_ctr(my_map); map_dtr(my_map); return 0;}Adding Map Elements in C
When you add an element to a Map you have to provide a Key and a Value in the appropriate data types. The Key has to be unique so inserting fails if you try to add a already existing Key.
Therefore we need feedback wheter the insertion was successful or not. We introduce a struct called map_element_t that has key, value and wasInserted as members. The memeber wasInserted is true when the insertion was successful, and the value is either the new value or the value of the key that already existed.
The parameters for our function (besides the map object) are the new key and the corresponding value.
#pragma once#include <stdbool.h>...typedef struct map_element_t { int key; char value; bool wasInserted;} map_element_t;...map_element_t map_insert(map_t* obj, const int key, const char value);The implementation starts with the lookup if the key already exists in the map. If yes we return the key, its value and set wasInserted to false.
If the key does not exist we increment the map size, reallocate enough memory and set the key an value for the new index.
map_element_t map_insert(map_t* obj, const int key, const char value){ int existsAt = -1; for(int i=0;i<obj->size;i++) { if(key == obj->keys[i]) { existsAt = i; break; } } int index = -1; map_element_t insertion_result; if(existsAt >= 0) { index = existsAt; insertion_result.wasInserted = false; insertion_result.key = obj->keys[existsAt]; insertion_result.value = obj->values[existsAt]; } else { index = obj->size; insertion_result.wasInserted = true; obj->size++; obj->keys = (int*) realloc(obj->keys, obj->size); obj->keys[index] = key; obj->values = (char*) realloc(obj->values, obj->size); obj->values[index] = value; } insertion_result.key = obj->keys[index]; insertion_result.value = obj->values[index]; return insertion_result;}Due to further implementations, we will have to come back to this function again later.
Now we have a little more sophisticated Test program that tries to add three Elements to the Map but is successful only two times. In order to not repeat ourselves we extract the result analysis into its own function and call it after every insertion.
#include "map.h"#include <stdio.h>void checkResult(const map_element_t result){ if(result.wasInserted) { printf("Insertion successful! Key: %d, Value: '%c'\n", result.key, result.value); } else { printf("Insertion failed! Key %d already exists with Value: '%c'\n", result.key, result.value); }}int main(int argc, char** argv){ map_t* my_map = map_new(); map_ctr(my_map); map_element_t result = map_insert(my_map, 1, 'A'); checkResult(result); result = map_insert(my_map, 2, 'B'); checkResult(result); result = map_insert(my_map, 1, 'A'); checkResult(result); map_dtr(my_map); return 0;}This test program leads to the following output:
Insertion successful! Key: 1, Value: 'A'Insertion successful! Key: 2, Value: 'B'Insertion failed! Key 1 already exists with Value: 'A'Accessing Map Elements in C
In theory there would be two ways to access a map element. But the first one is not applicable in C (I tell you why in a second), so only one possibility is left. In general, Map Elements are accessed by its key.
(Not) Accessing Elements with[]
Unfortunatly, the C Language does not support operator overloading. If you create a standard C++ Map you access Elements with this syntax:
std::map<std::string, int> m{{"CPU", 10}, {"GPU", 15}};m["CPU"] = 25;However, we cannot do this with our “Class” because we cannot overload the brackets operator. We use a pointer to a struct and cannot set a value to the elements within the struct directly. This means that we cannot create the syntax from above.
Or can we? Maybe there is a way using MACROS and/or Pointer Magic but I leave this as an exercise to you
Accessing Elements withat()
We are left with the possibility to access Map Elements with the at(…) function. We just pass in the object (as always) and the key whose value we want to access.
char map_at(map_t* obj, const int key);When we access en Element with at(…) in C++ we get an std::out_of_range Exception. However, C does not know Exceptions and does not have such a concept. So we are basically left with two Options: Imitate exception behaviour or catch the error ourselves and print out an error message.
While the first option leads to more overhead and maybe undefined behaviour, the second option does have the flaw that we still have to return a value which then is not valid respectively what the user expected. Because C++ itself does throw an exception, I will go with option one here.
You may come up with a better solution for yourself. If so, you may let me know.
#include "map.h"#include <stdlib.h>#include <assert.h>...char map_at(map_t* obj, const int key){ int existsAt = -1; for(int i=0;i<obj->size;i++) { if(key == obj->keys[i]) { existsAt = i; break; } } assert(existsAt >= 0); return obj->values[key];}...We modify our test program and add again two keys with a value. When we access the values, we give a valid and an invalid index to the function.
...int main(int argc, char** argv){ map_t* my_map = map_new(); map_ctr(my_map); map_element_t result = map_insert(my_map, 1, 'A'); result = map_insert(my_map, 2, 'B'); printf("Value at 1: %c\n", map_at(my_map, 1)); /* Valid Key */ printf("Value at 5: %c\n", map_at(my_map, 5)); /* Invalid Key */ map_dtr(my_map); return 0;}...While the first key is available and returns its value, the second is not in the map and the assert(…) function tells us what went wrong and where.
Value at 1: BAssertion failed: existsAt >= 0, file map.c, line 85Lookup Functions for Map in C
There are several ways to lookup ceratain elements within a map, either to check if they already exist or to get them for iteration.
Checking Existence of an Element with count()
The function count(…) searches the container for a given key and returns either 1 if it is found or 0 if not. It cannot be greater than 1 because maps don’t allow duplicate keys.
...int map_count(map_t* obj, const int key);...First we take the code that checks for existence of a key from our insert(..) and add(…) functions and put them into a seperate function. (We will refactore the mentioned functions later). Then we simply return if the key exists or not. The function is static which makes it “private” to the file and thus can be treated like a private memeber.
...static int key_exists(map_t* obj, const int key) { int existsAt = NOWHERE; for(int i=0;i<obj->size;i++) { if(key == obj->keys[i]) { existsAt = i; break; } } return existsAt;}int map_count(map_t* obj, const int key){ return key_exists(obj, key) != NOWHERE;}...The Test Program simply checks for existing by using the count(…) function.
...int main(int argc, char** argv){ map_t* my_map = map_new(); map_ctr(my_map); map_insert(my_map, 1, 'A'); map_insert(my_map, 2, 'B'); printf("Count Key 1: %d\n", map_count(my_map, 1)); printf("Count Key 5: %d\n", map_count(my_map, 5)); map_dtr(my_map); return 0;}The output shows the count results:
Count Key 1: 1Count Key 5: 0Checking Existence of an Element with contains()
The function contains(…) is essentially the same as count(…) but has bool instead of int as a return value. For this reason I only put the header and implementation here and leave the test program up to you.
...bool map_contains(map_t* obj, const int key);......bool map_contains(map_t* obj, const int key){ return key_exists(obj, key) != NOWHERE;}...Finding an Element by its Key with find()
We implement the find function which returns the map element that we are looking for or an iterator the end of the map in C++. We don’t have such an iterator here (maybe you could imlpement them), and therefore we will use the wasInserted flag of the map_element_t struct.
For convienience I will not rename the struct element now but it should have another name, for example wasUpdatedOrFound.
...typedef struct map_element_t { int key; char value; bool wasInserted;} map_element_t;...map_element_t map_find(map_t* obj, const int key);...The implementation just checks if the key is present in the map and then either returns the valid key value pair or an “invalid” pair with the (implicit) information that nothing was found.
...map_element_t map_find(map_t* obj, const int key){ int existsAt = key_exists(obj, key); map_element_t map_element; if(existsAt == NOWHERE) { map_element.wasInserted = false; map_element.key = key; map_element.value = NOWHERE; } else { map_element.wasInserted = true; map_element.key = key; map_element.value = obj->values[key]; } return map_element;}...In our Test Program we now use the newly create find function:
...int main(int argc, char** argv){ map_t* my_map = map_new(); map_ctr(my_map); map_insert(my_map, 1, 'A'); map_insert(my_map, 2, 'B'); map_element_t find_result = map_find(my_map, 1); printf("Find Value '%c' at key %d\n", find_result.value, find_result.key); find_result = map_find(my_map, 5); if(!find_result.wasInserted) { printf("Key %d nout found in map!\n", find_result.key); } map_dtr(my_map); return 0;}...This leads to the following output:
Find Value 'B' at key 1 Key 5 nout found in map!Modifying insert(…) and add(…)
We now can refactor our insert and add function and remove some duplicate code. We use the “private” function key_exists(…) that we created a bit earlier:
...map_element_t map_insert(map_t* obj, const int key, const char value){ int index = -1; map_element_t insertion_result; int existsAt = key_exists(obj, key); if(existsAt >= 0) { index = existsAt; insertion_result.wasInserted = false; insertion_result.key = obj->keys[existsAt]; insertion_result.value = obj->values[existsAt]; } else { index = obj->size; insertion_result.wasInserted = true; obj->size++; obj->keys = (int*) realloc(obj->keys, obj->size); obj->keys[index] = key; obj->values = (char*) realloc(obj->values, obj->size); obj->values[index] = value; } insertion_result.key = obj->keys[index]; insertion_result.value = obj->values[index]; return insertion_result;}...char map_at(map_t* obj, const int key){ int existsAt = key_exists(obj, key); assert(existsAt >= 0); return obj->values[key];}...Now they are much better to read and we removed duplication which always is a good thing.
Removing Map Elements in C
One can either remove Elements from a Map by its key or remove all Elements of a Map at once.
Removing all Elements in a Map with clear()
The function clear(…) removes all Elements from a Map (which are destroyed) and thus leaves the container with a size of 0.
...void map_clear(map_t* obj);...The clear function itself is very simple:
...void map_clear(map_t* obj){ obj->keys = (int*) realloc(obj->keys, 0); obj->values = (char*) realloc(obj->values, 0); obj->size = 0;}...The Test Program now uses the clear function and we make sure that no Elements are left with our outputs.
... map_insert(my_map, 1, 'A'); map_insert(my_map, 2, 'B'); map_clear(my_map); find_result = map_find(my_map, 1); if(!find_result.wasInserted) { printf("Key %d nout found in map!\n", find_result.key); } find_result = map_find(my_map, 2); if(!find_result.wasInserted) { printf("Key %d nout found in map!\n", find_result.key); }...The Output
Key 1 nout found in map!Key 2 nout found in map!Removing one Element in a Map with erase()
Removing only one Element from a Map by its key is also a common task. The header again is very straightforward.
...void map_erase(map_t* obj, const int key);...The Implementation is a little bit more work than removing all elements. First we have to find the Element that we want to delete. If it doesn’t exist within the map we simply exit the function.
If it does exist we shift all remaining values that are at a greater index than the Element to erase one index down and then reallocate the memory so we’re going to get rid of one element.
...void map_erase(map_t* obj, const int key){ int existsAt = key_exists(obj, key); if(existsAt == NOWHERE) { return; } obj->size--; for(int i=existsAt;i<obj->size;i++) { obj->keys[i] = obj->keys[i+1]; obj->values[i] = obj->values[i+1]; } obj->keys = (int*) realloc(obj->keys, obj->size); obj->values = (char*) realloc(obj->values, obj->size);}...To test this function we modify the Test Program for clear() just slightly:
... map_erase(my_map, 1); find_result = map_find(my_map, 1); if(!find_result.wasInserted) { printf("Key %d nout found in map!\n", find_result.key); } else { printf("Key %d is still here!\n", find_result.key); } find_result = map_find(my_map, 2); if(!find_result.wasInserted) { printf("Key %d nout found in map!\n", find_result.key); } else { printf("Key %d is still here!\n", find_result.key); }...And here we are with our final output. The first key Element is gone but the second still exists, so we did not accidentally erase the wrong Element.
Key 1 nout found in map!Key 2 is still here! Summary & Further Ideas
Now we have a map class in C that we can use for our projects. There are some functions more in the C++ STL map implementation that I left out so go ahead and implement them yourself.
The Implementaion of our Map is a Unordered Map. You may implement a version where the content is automatically sorted by key.
This article was first published by Marco Lieblang on moderncprogramming.com. If you are reading this somewhere else, it may be plagiarism.
Related posts:
How To Implement a Linked List Class in Pure C?How To Implement a Queue Class in Pure C?How To Implement a Stack Class in Pure C?How To Implement a Dynamic Array Class in Pure C?
