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:
- find parent node.
- if one child, replace self with said child from parent.
- 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 I
th 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.
#include
s and the main function) and the command you use to compile the code? \$\endgroup\$std::iterator
is deprecated, anyway you have no iterator there... \$\endgroup\$