Implementation of container searchable by any element

Question

Writing game engine as a hobby, I've come across many situations where I need a container like a map, but searchable by different keys: a block allocator where a block needs to be searched by either offset or size, or resources searchable by either name or file.

Having multiple maps for each of those keys is ugly and pain in the ass to erase an entry, so I came up with the following.

Implementation:

template <typename... T>
class omni_map
{
    static constexpr size_t num_element = sizeof...(T);

    using tuple_t = std::tuple<T...>;

    template <size_t I>
    using element_t = typename std::tuple_element_t<I, tuple_t>;

    struct node;

    struct branch {
        branch() : 
            left(nullptr), 
            right(nullptr) {}
        node* left;
        node* right;
    };

    struct node {
        node(T&&... t) :
            values(t...) {}
        tuple_t values;
        branch branches[num_element];
    };

public:
    template <size_t I>
    class iterator {
        friend class omni_map<T...>;
    public:
        iterator(node* n = nullptr) :
            curr(n) {}
        const tuple_t& operator*() {
            return curr->values;
        }
        const tuple_t& operator->() {
            return curr->values;
        }
        bool operator==(const iterator<I>& r) {
            return curr == r.curr;
        }
        bool operator!=(const iterator<I>& r) {
            return curr != r.curr;
        }
    private:
        node* curr;
    };

public:
    omni_map() : 
        m_roots{ nullptr } {}

    void emplace(T&&... t) {
        node* n = m_nodepool.construct(std::forward<T>(t)...);
        insert_node<0>(n);
    }

    template <size_t I>
    iterator<I> find(const element_t<I>& value) {
        node* curr = m_roots[I];
        while (curr)
            if (value < std::get<I>(curr->values))
                curr = curr->branches[I].left;
            else if (value > std::get<I>(curr->values))
                curr = curr->branches[I].right;
            else
                return iterator<I>(curr);
        return iterator<I>();
    }

    template <size_t I>
    void erase(iterator<I> it) {
        remove_node<0>(it.curr);
        m_nodepool.destroy(it.curr);
    }

    template <size_t I>
    iterator<I> begin() {
        node* curr = m_roots[I];
        while (curr->branches[I].left)
            curr = curr->branches[I].left;
        return iterator<I>(curr);
    }

    template <size_t I>
    iterator<I> end() {
        return iterator<I>();
    }

private:
    template <size_t I>
    void insert_node(node* n) {
        node** curr = &m_roots[I];
        while (*curr) {
            if (std::get<I>(n->values) <= std::get<I>((*curr)->values))
                curr = &(*curr)->branches[I].left;
            else
                curr = &(*curr)->branches[I].right;
        }
        *curr = n;
        insert_node<I + 1>(n);
    }

    template <>
    void insert_node<num_element>(node* n) {}

    template <size_t I>
    void remove_node(node* n) {
        node** curr = &m_roots[I];
        while (*curr != n)
            if (std::get<I>(n->values) <= std::get<I>((*curr)->values))
                curr = &(*curr)->branches[I].left;
            else
                curr = &(*curr)->branches[I].right;
        if (n->branches[I].left)
            if (n->branches[I].right) {
                node* left = n->branches[I].left;
                node* max_left = n->branches[I].left;
                while (max_left->branches[I].right)
                    max_left = max_left->branches[I].right;
                *curr = max_left;
                while (max_left->branches[I].left)
                    max_left = max_left->branches[I].left;
                max_left->branches[I].left = left;
            }
            else
                *curr = n->branches[I].left;
        else
            if (n->branches[I].right)
                *curr = n->branches[I].right;
            else
                *curr = nullptr;
        remove_node<I + 1>(n);
    }

    template <>
    void remove_node<num_element>(node* n) {}

private:
    mem_pool<node> m_nodepool;
    node* m_roots[num_element];
};

mem_pool is my implementation of free list memory pool allocator for data locality and fast allocation.

This implementation is basically a one big graph where each element has a binary search tree structure. A node has an left/right child node for each of the element. The values of each entry are stored as a tuple in each node.

emplace function creates a node with a tuple constructed with given arguments, and calls insert_node<0> which will insert the newly created node in the binary tree structure of the first element, then call insert_node<1> for second element, and so on recursively until insert_node<num_element>. The container accepts duplicate entries, which will be placed as the left child of already existing entry.

find<0> searches by the first element(int in the example code's case), find<1> searches by the second element(std::string in the example code's case) and so on; returning iterator<I> that points to the found entry.

erase function takes said iterator<I> to removes the node it points to. The function does so by calling remove_node<I> recursively before destroying the node, which will, for each element:

1. find parent node.
2. if one child, replace self with said child from parent.
3. if two child, replace self with maximum value node from left branch (has to be maximum from left if duplicates are passed to the left, minimum from right if otherwise).

I gave the iterator an index template argument, so that it could iterate based on given Ith element. But I might not implement that feature since I won't ever have to iterate in my use cases.

Example Code:

#include <iostream>
#include "omni_map.h"

int main()
{
    util::omni_map<int, std::string> test_map;

    test_map.emplace(3, "three");
    test_map.emplace(2, "two");
    test_map.emplace(7, "seven");
    test_map.emplace(1, "one");
    test_map.emplace(6, "six");
    test_map.emplace(4, "four");
    test_map.emplace(5, "five");

    auto it0 = test_map.find<0>(4);
    auto it1 = test_map.find<1>("seven");
    std::cout << std::get<0>(*it0) << " " << std::get<1>(*it0) << std::endl;
    std::cout << std::get<0>(*it1) << " " << std::get<1>(*it1) << std::endl;

    test_map.emplace(25, "twenty-five");
    test_map.emplace(16, "sixteen");
    test_map.emplace(18, "eighteen");
    test_map.emplace(17, "seventeen");
    test_map.emplace(23, "twenty-three");
    test_map.emplace(21, "twenty_one");
    test_map.emplace(21, "twenty_one(1)");

    it0 = test_map.find<0>(25);
    std::cout << (it0 == test_map.end<0>() ? "true" : "false") << std::endl;
    test_map.erase(it0);
    it0 = test_map.find<0>(25);
    std::cout << (it0 == test_map.end<0>() ? "true" : "false") << std::endl;

    it0 = test_map.find<0>(21);
    it1 = test_map.find<1>("sixteen");
    std::cout << std::get<0>(*it0) << " " << std::get<1>(*it0) << std::endl;
    std::cout << std::get<0>(*it1) << " " << std::get<1>(*it1) << std::endl;
}

Above test code outputs as follows:

4 four
7 seven
false
true
21 twenty_one
16 sixteen

I have published the solution to my GitHub here to show the entire code.

Answer 1

struct branch can have default and aggregate initialisation very simply:

struct branch {
    node* left = {};
    node* right = {};
};

struct node has forwarding-reference parameters, then forgets to forward them when constructing its values member. We should use std::forward here:

    node(T&&... t) :
        values(std::forward<T>(t)...) {}

omni_map owns memory through raw pointers in m_roots yet doesn't have a destructor to free all these, nor any copy constructor or assignment operator, so looks very vulnerable to all the usual pointer-ownership problems.