一个小型向量和哈希表实现，无 STL 依赖
4.50/5 (7投票s)
即使在没有可靠 STL 实现的平台上，也能让你的数据发挥作用，使用这些简单但关键的类。
引言
我经常针对 Arduino 框架进行开发，并且没有可靠的跨平台 std::map 实现可以依赖，主要是因为 STL 对于许多这些设备来说并没有完全实现。此外，由于其通用性，STL 往往有一些隐藏的开销。它被设计用来处理所有场景，因此它以复杂性为代价来实现这一点。
为此，我创建了一些 std::vector<> 和 std::map<> 的简单替代方案。这些接口与 STL 版本并不完全相同，但它们相似，缺少许多方法，包括没有删除单个项目的方法。
编写这个混乱的程序
使用起来很简单
#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;
}
请记住，这些类不会为你的单个项目分配内存，因此，如果你存储的是指针（例如 C 字符串或数组），这些指针必须在类外部保持有效。
整个实现如下
#pragma once
#include <stdlib.h>
namespace data {
// dynamic vector of scalar 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; // size in number of T values
T* m_begin;
size_t m_capacity; // allocated size in T values
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; //error: not enough memory
}
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;
}
};
} // namespace data
包括使用 Platform IO
此库作为 Platform IO 库提供，可以通过将以下行添加到你的 platformio.ini 来安装
lib_deps =
codewitch-honey-crisis/htcw_data@^1.0.2
历史
- 2022年3月17日 - 初始提交