On some Arduino devices, and perhaps some embedded platforms, you may not have access to the full measure of The Standard Template Library. In those cases, it might not be feasible to rely on the STL for std::map - maybe even std::vector. Also these are very lightweight compared to The STL implementation, because aren't designed to handle every possible scenario - just the simple ones.
Introduction
I target the Arduino framework a lot, and there is no reliable cross-platform std::map implementation that can be relied on, mostly because The STL isn't fully implemented for many of these devices. Also The STL tends to have some hidden overhead due to the general purpose nature of it. It's designed to handle all scenarios, so it trades on complexity in order to do so.
To that end, I've created some simple alternatives to std::vector<> and std::map<>. The interfaces aren't exactly the same as The STL versions, but they are similar, minus many of the methods, including having no way to remove individual items.
Coding this Mess
Using it is simple:
#include <stdio.h>
#include <htcw_data.hpp>
using namespace data;
int hash(const int& x) {
return x;
}
int main(int argc, char** argv) {
simple_vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
printf("v.begin()[0]=%d\r\n",v.begin()[0]);
printf("v.begin()[1]=%d\r\n",v.begin()[1]);
printf("v.begin()[2]=%d\r\n",v.begin()[2]);
simple_fixed_map<int,int,2> test(hash);
test.insert({1,3});
test.insert({2,2});
test.insert({3,1});
printf("test.find(1)=%d\r\n",*test.find(1));
printf("test.find(2)=%d\r\n",*test.find(2));
printf("test.find(3)=%d\r\n",*test.find(3));
if(test.find(4)==nullptr) {
printf("test.find(4)=nullptr\r\n");
}
return 0;
}
Keep in mind that these classes do not allocate memory for your individual items, so if you are storing pointers (like C strings or arrays for example), those pointers must be kept valid outside of this class.
The entire implementation is here:
#pragma once
#include <stdlib.h>
namespace data {
template <typename T>
class simple_vector final {
void* (*m_allocator)(size_t);
void* (*m_reallocator)(void*, size_t);
void (*m_deallocator)(void*);
size_t m_size; T* m_begin;
size_t m_capacity; bool resize(size_t new_size) {
size_t capacity = new_size;
if (capacity > this->m_capacity) {
size_t newcap = capacity + (this->m_capacity >> 1u);
void* data ;
if(this->m_begin) {
data = m_reallocator(this->m_begin, newcap * sizeof(T));
} else {
newcap=8;
const size_t newsz = newcap*sizeof(T);
data = m_allocator(newsz);
}
if (data) {
this->m_capacity = newcap;
this->m_begin = (T*)data;
} else
return false; }
this->m_size = new_size;
return true;
}
public:
simple_vector(void*(allocator)(size_t) = ::malloc,
void*(reallocator)(void*, size_t) = ::realloc,
void(deallocator)(void*) = ::free) :
m_allocator(allocator),
m_reallocator(reallocator),
m_deallocator(deallocator) {
m_begin = nullptr;
m_size = 0;
m_capacity = 0;
}
~simple_vector() {
m_size = 0;
if (m_begin != nullptr) {
m_deallocator(m_begin);
m_begin = nullptr;
}
}
inline size_t size() const { return m_size; }
inline size_t capacity() const { return m_capacity; }
inline const T* cbegin() const { return m_begin; }
inline const T* cend() const { return m_begin + m_size; }
inline T* begin() { return m_begin; }
inline T* end() { return m_begin + m_size; }
void clear() {
if(m_begin) {
m_size = 0;
m_capacity = 0;
m_deallocator(m_begin);
m_begin = nullptr;
}
}
bool push_back(const T& value) {
if (!resize(m_size + 1)) {
return false;
}
m_begin[m_size - 1] = value;
return true;
}
};
template<typename TKey, typename TValue>
struct simple_pair {
TKey key;
TValue value;
simple_pair(TKey key,TValue value) : key(key), value(value) {
}
simple_pair(const simple_pair& rhs) {
key = rhs.key;
value = rhs.value;
}
simple_pair& operator=(const simple_pair& rhs) {
key = rhs.key;
value = rhs.value;
return *this;
}
simple_pair(simple_pair&& rhs) {
key = rhs.key;
value = rhs.value;
}
simple_pair& operator=(simple_pair&& rhs) {
key = rhs.key;
value = rhs.value;
return *this;
}
};
template<typename TKey,typename TValue, size_t Size>
class simple_fixed_map final {
static_assert(Size>0,"Size must be a positive integer");
using bucket_type = simple_vector<simple_pair<TKey,TValue>>;
bucket_type m_buckets[Size];
int(*m_hash_function)(const TKey&);
size_t m_size;
public:
simple_fixed_map(int(hash_function)(const TKey&),
void*(allocator)(size_t) = ::malloc,
void*(reallocator)(void*, size_t) = ::realloc,
void(deallocator)(void*) = ::free) :
m_hash_function(hash_function),
m_size(0) {
for(int i = 0;i<Size;++i) {
m_buckets[i]=bucket_type(allocator,reallocator,deallocator);
}
}
using key_type = TKey;
using mapped_type = TValue;
using value_type = simple_pair<const TKey,TValue>;
inline size_t size() const { return m_size; }
void clear() {
m_size = 0;
for(int i = 0;i<Size;++i) {
m_buckets->clear();
}
}
bool insert(const value_type& value) {
int h = m_hash_function(value.key)%Size;
bucket_type& bucket = m_buckets[h];
if(bucket.size()) {
auto it = bucket.cbegin();
while(it!=bucket.cend()) {
if(it->key==value.key) {
return false;
}
++it;
}
}
if(bucket.push_back({value.key,value.value})) {
++m_size;
return true;
}
return false;
}
const mapped_type* find(const key_type& key) const {
int h = m_hash_function(key)%Size;
const bucket_type& bucket = m_buckets[h];
if(bucket.size()) {
auto it = bucket.cbegin();
while(it!=bucket.cend()) {
if(it->key==key) {
return &it->value;
}
++it;
}
}
return nullptr;
}
};
}
Including Using Platform IO
This library is available as a Platform IO library and can be installed by adding the following line to your platformio.ini:
lib_deps =
codewitch-honey-crisis/htcw_data@^1.0.2
History
- 17th March, 2022 - Initial submission
