struct hash_set_iterator

[view source]

An iterator implementation, similar to those in the Standard Template Library, to enable iteration of elements in a hash_set. This iterator is typically initialized using hash_set::begin.

This definition enables the use of range-based for loops.

struct hash_map_iterator

[view source]

An iterator implementation, similar to those in the Standard Template Library, to enable iteration of elements in a hash_map. This iterator is typically initialized using hash_map::begin.

This definition enables the use of range-based for loops.

struct array_map_iterator

[view source]

An iterator implementation, similar to those in the Standard Template Library, to enable iteration of elements in an array_map. This iterator is typically initialized using array_map::begin.

This definition enables the use of range-based for loops.

struct hash_set

[view source]

1. If T is_pointer, is_fundamental, or is_enum, core::default_hash() provides the hash.

2. For all other types, the T::hash function provides the hash. Once the hash is computed, the index into hash_set::keys is computed using hash % hash_set::capacity (modular division by the capacity).

The above approach could produce the same index for distinct elements. This event is known as a collision. We use linear probing to resolve collisions: When adding an element to the hash_set, we compute its index using the above procedure, then we inspect hash_set::keys[index] and use core::is_empty() to determine if another element already occupies that position. If so, we try the next position (index + 1) % hash_set::capacity. We continue until we find an empty index, and the element is inserted there.

Thus, the function core::is_empty() is used to determine if a position in hash_set::keys is occupied or empty. The total number of occupied positions is given by hash_set::size. WARNING: If hash_set::keys becomes full, the above linear probing mechanism could lead to an infinite loop. The function hash_set::check_size should be used whenever adding new elements to avoid this scenario.

Performance: This data structure provides constant-time access and modification, given that the load factor (size / capacity) is not too large.

Below is an example of a simple use-case of hash_set, where the expected output is a.contains(2): false, a.contains(3): true, -4 9 3.

#include <core/map.h>
#include <stdio.h>
using namespace core;

int main() {
    hash_set<int> a = hash_set<int>(8);
    a.add(-1); a.add(-4);
    a.add(3); a.add(9);
    a.remove(-1);

    printf("a.contains(2): %s, ", a.contains(2) ? "true" : "false");
    printf("a.contains(3): %s, ", a.contains(3) ? "true" : "false");
    for (int element : a)
        printf("%d ", element);
}

However, if a is not allocated on the stack, the destructor will not be automatically called, and so it must be freed manually using core::free or hash_set::free. In the example below, the expected output is the same as that of the program above: a.contains(2): false, a.contains(3): true, -4 9 3.

#include <core/map.h>
#include <stdio.h>
using namespace core;

int main() {
    hash_set<int>& a = *((hash_set<int>*) alloca(sizeof(hash_set<int>)));
    hash_set_init(a, 8);
    a.add(-1); a.add(-4);
    a.add(3); a.add(9);
    a.remove(-1);

    printf("a.contains(2): %s, ", a.contains(2) ? "true" : "false");
    printf("a.contains(3): %s, ", a.contains(3) ? "true" : "false");
    for (int element : a)
        printf("%d ", element);
    free(a);
}

A number of member functions require T to be CopyAssignable. If this is not the case, those operations can be performed directly on the public fields, as in the following example. In addition, when using a custom struct/class with hash_set, it must implement public static functions, like hash, is_empty, and move, as well as the operator ==. The expected output of the following example is first second.

#include <core/map.h>
#include <stdio.h>
#include <string.h>
using namespace core;

struct custom_string {
    char* buffer;

    static unsigned int hash(const custom_string& s) {
        return default_hash(s.buffer, strlen(s.buffer));
    }

    static bool is_empty(const custom_string& s) {
        return s.buffer == NULL;
    }

    static void move(const custom_string& src, custom_string& dst) {
        dst.buffer = src.buffer;
    }

    static void free(custom_string& s) {
        core::free(s.buffer);
    }
};

inline bool operator == (const custom_string& first, const custom_string& second) {
    if (first.buffer == NULL)
        return second.buffer == NULL;
    return strcmp(first.buffer, second.buffer) == 0;
}

bool init(custom_string& s, const char* src) {
    s.buffer = (char*) malloc(sizeof(char) * (strlen(src) + 1));
    if (s.buffer == NULL)
        return false;
    memcpy(s.buffer, src, sizeof(char) * (strlen(src) + 1));
    return true;
}

int main() {
    custom_string first, second;
    init(first, "first");
    init(second, "second");

    hash_set<custom_string> a = hash_set<custom_string>(8);
    a.check_size(a.size + 2);

    bool contains; unsigned int index;
    index = a.index_of(first, contains);
    if (!contains) {
        core::move(first, a.keys[index]);
        a.size++;
    }

    index = a.index_of(second, contains);
    if (!contains) {
        core::move(second, a.keys[index]);
        a.size++;
    }

    for (const custom_string& s : a)
        printf("%s ", s.buffer);
    for (custom_string& s : a)
        free(s);
}

struct hash_map

[view source]

An unordered associative container that contains a set of key-value pairs, where the keys are unique and have type K and the values have type V. The keys are stored in a hash_set structure, and the values are stored in hash_map::values, which is a native array parallel to the key array in hash_set::keys. To compute the index of a key-value pair, we compute the index of the key using the algorithm described in hash_set. The value has the same index in hash_map::values. This structure uses the same linear probing approach to resolve collisions (i.e. when two distinct keys are computed to have the same index).

WARNING: As with hash_set, if the map becomes full, the linear probing mechanism could lead to an infinite loop in many hash_map operations. The function hash_map::check_size should be used whenever adding new elements to avoid this scenario.

Performance: This data structure provides constant-time access and modification, given that the load factor (size / capacity) is not too large.

Below is a simple example using a hash_map, where the expected output is a.get(3): c, a.get(4): d, 1:a 4:d 3:c.

#include <core/map.h>
#include <stdio.h>
using namespace core;

int main() {
    hash_map<int, char> a = hash_map<int, char>(8);
    a.put(1, 'a'); a.put(2, 'b');
    a.put(3, 'c'); a.put(4, 'd');
    a.remove(2);

    printf("a.get(3): %c, ", a.get(3));
    printf("a.get(4): %c,  ", a.get(4));
    for (const auto& entry : a)
        printf("%d:%c ", entry.key, entry.value);
}

However, if a is not allocated on the stack, the destructor will not be automatically called, and so it must be freed manually using core::free or hash_map::free. In the example below, the expected output is the same as that of the program above: a.get(3): c, a.get(4): d, 1:a 4:d 3:c.

#include <core/map.h>
#include <stdio.h>
using namespace core;

int main() {
    hash_map<int, char>& a = *((hash_map<int, char>*) malloc(sizeof(hash_map<int, char>)));
    hash_map_init(a, 8);
    a.put(1, 'a'); a.put(2, 'b');
    a.put(3, 'c'); a.put(4, 'd');
    a.remove(2);

    printf("a.get(3): %c, ", a.get(3));
    printf("a.get(4): %c,  ", a.get(4));
    for (const auto& entry : a)
        printf("%d:%c ", entry.key, entry.value);
    free(a);
}

A number of member functions require K and V to be CopyAssignable. If this is not the case, those operations can be performed directly on the public fields, as in the following example. In addition, when using a custom struct/class as the key type in hash_map, it must implement public static functions, like hash, is_empty, and move, as well as the operator ==. The expected output of the following example is first:1 second:2.

#include <core/map.h>
#include <stdio.h>
#include <string.h>
using namespace core;

struct custom_string {
    char* buffer;

    static unsigned int hash(const custom_string& s) {
        return default_hash(s.buffer, strlen(s.buffer));
    }

    static bool is_empty(const custom_string& s) {
        return s.buffer == NULL;
    }

    static void move(const custom_string& src, custom_string& dst) {
        dst.buffer = src.buffer;
    }

    static void free(custom_string& s) {
        core::free(s.buffer);
    }
};

inline bool operator == (const custom_string& first, const custom_string& second) {
    if (first.buffer == NULL)
        return second.buffer == NULL;
    return strcmp(first.buffer, second.buffer) == 0;
}

bool init(custom_string& s, const char* src) {
    s.buffer = (char*) malloc(sizeof(char) * (strlen(src) + 1));
    if (s.buffer == NULL)
        return false;
    memcpy(s.buffer, src, sizeof(char) * (strlen(src) + 1));
    return true;
}

int main() {
    custom_string key_one, key_two;
    int value_one = 1, value_two = 2;
    init(key_one, "first");
    init(key_two, "second");

    hash_map<custom_string, int> a = hash_map<custom_string, int>(8);
    a.check_size(a.table.size + 2);

    bool contains; unsigned int index;
    a.get(key_one, contains, index);
    if (!contains) {
        core::move(key_one, a.table.keys[index]);
        a.values[index] = value_one;
        a.table.size++;
    }

    a.get(key_two, contains, index);
    if (!contains) {
        core::move(key_two, a.table.keys[index]);
        a.values[index] = value_two;
        a.table.size++;
    }

    for (const auto& entry : a)
        printf("%s:%d ", entry.key.buffer, entry.value);
    for (auto entry : a)
        free(entry.key);
}

struct array_map

[view source]

A sequentially-ordered associative container that contains a set of key-value pairs, where the keys are unique and have type K and the values have type V. The keys are stored sequentially in a native array array_map::keys, and the values are stored sequentially in a parallel native array array_map::values.

When inserting a key-value pair into an array_map, a linear search is performed to determine if the key already exists in the map. If so, its corresponding value is replaced by the new value. If not, the new key and value are inserted at the ends of their respective arrays, and array_map::size is incremented.

Performance: This data structure provides linear-time access and modification. However, due to locality of reference, this data structure may perform operations more quickly than hash_map if the size of the map is small.

A simple example of the use of array_map is given below, where the expected output is a.get(3): c, a.get(4): d, 1:a 4:d 3:c.

#include <core/map.h>
#include <stdio.h>
using namespace core;

int main() {
    array_map<int, char> a = array_map<int, char>(8);
    a.put(1, 'a'); a.put(2, 'b');
    a.put(3, 'c'); a.put(4, 'd');
    a.remove(2);

    printf("a.get(3): %c, ", a.get(3));
    printf("a.get(4): %c,  ", a.get(4));
    for (const auto& entry : a)
        printf("%d:%c ", entry.key, entry.value);
}

However, if a is not allocated on the stack, the destructor will not be automatically called, and so it must be freed using core::free or hash_map::free. In the example below, the expected output is the same as that of the program above: a.get(3): c, a.get(4): d, 1:a 4:d 3:c.

#include <core/map.h>
#include <stdio.h>
using namespace core;

int main() {
    array_map<int, char>& a = *((array_map<int, char>*) alloca(sizeof(array_map<int, char>)));
    array_map_init(a, 8);
    a.put(1, 'a'); a.put(2, 'b');
    a.put(3, 'c'); a.put(4, 'd');
    a.remove(2);

    printf("a.get(3): %c, ", a.get(3));
    printf("a.get(4): %c,  ", a.get(4));
    for (const auto& entry : a)
        printf("%d:%c ", entry.key, entry.value);
    free(a);
}

A number of member functions require K and V to be CopyAssignable. If this is not the case, those operations can be performed directly on the public fields, as in the following example. The expected output is first:1 second:2.

#include <core/map.h>
#include <stdio.h>
#include <string.h>
using namespace core;

struct custom_string {
    char* buffer;

    static void move(const custom_string& src, custom_string& dst) {
        dst.buffer = src.buffer;
    }

    static void free(custom_string& s) {
        core::free(s.buffer);
    }
};

inline bool operator == (const custom_string& first, const custom_string& second) {
    if (first.buffer == NULL)
        return second.buffer == NULL;
    return strcmp(first.buffer, second.buffer) == 0;
}

bool init(custom_string& s, const char* src) {
    s.buffer = (char*) malloc(sizeof(char) * (strlen(src) + 1));
    if (s.buffer == NULL)
        return false;
    memcpy(s.buffer, src, sizeof(char) * (strlen(src) + 1));
    return true;
}

int main() {
    custom_string key_one, key_two;
    int value_one = 1, value_two = 2;
    init(key_one, "first");
    init(key_two, "second");

    array_map<custom_string, int> a = array_map<custom_string, int>(8);
    a.ensure_capacity(2);

    unsigned int index;
    a.get(key_one, index);
    if (index == a.size) {
        core::move(key_one, a.keys[index]);
        a.values[index] = value_one;
        a.size++;
    }

    a.get(key_two, index);
    if (index == a.size) {
        core::move(key_two, a.keys[index]);
        a.values[index] = value_two;
        a.size++;
    }

    for (const auto& entry : a)
        printf("%s:%d ", entry.key.buffer, entry.value);
    for (auto entry : a)
        free(entry.key);
}