在C++/Arduino中实现类数组的字符串ID查找表优化查询效率

Arduino C++ 环境下可以通过两种主流方案实现你要的字符串ID键值查找能力，不需要每次遍历全量实例：

方案1：使用轻量HashMap库（推荐，O(1)查找效率） #

Arduino生态有现成的单头文件HashMap实现，无需引入重型依赖，适合嵌入式场景：

1. 先获取HashMap单头文件（可直接搜索Arduino HashMap.h下载，放入项目目录即可使用）
2. 定义查找表，创建实例时同步插入键值对，查询时直接读取

代码示例 #

// 顶部引入头文件
#include <HashMap.h>
#define MAX_ONE_TYPES 20
// 哈希表大小和最大实例数对齐即可，也可稍微设大减少冲突
#define HASH_MAP_SIZE MAX_ONE_TYPES

// 原有实例数组
oneTypeClass* oneTypeClasses[MAX_ONE_TYPES] EXT_RAM_ATTR;
// 新增ID到实例索引的查找表，也可以直接存实例指针省略数组访问
HashMap<const char*, int, HASH_MAP_SIZE> oneTypeClass_Lookup;
int createdOneTypesCounter = 0;

// 创建实例时同步插入查找表
for (JsonPair oneTypeRef: oneTypes) {
   const char* oneTypeID     = oneTypeRef.key().c_str();
   JsonObject oneTypeOptions = oneTypes[oneTypeID];
   oneTypeClasses[createdOneTypesCounter] = new oneTypeClass(oneTypeOptions);
   // 复制ID字符串存入查找表，避免JSON内存释放后出现野指针
   oneTypeClass_Lookup.put(strdup(oneTypeID), createdOneTypesCounter);
   createdOneTypesCounter++;
}

// 查询函数优化为直接查表
static const inline int getOneTypeClassIndex(const char* packetID){
    int index = -1;
    // get方法返回bool表示是否找到对应键，找到则写入index变量
    if(oneTypeClass_Lookup.get(packetID, index)){
        return index;
    }
    return -1;
}

// 业务函数无需修改，直接复用getOneTypeClassIndex即可
static const inline void setOneTypeMode(JsonObject packet){
   int myClassIndex = getOneTypeClassIndex(packet["id"]);
   if(myClassIndex > -1){
       oneTypeClasses[myClassIndex]->setModes(packet["mode"]);
   }
}

注意事项 #

• 若不需要保留实例数组，可直接将查找表定义为HashMap<const char*, oneTypeClass*, HASH_MAP_SIZE>，直接存储实例指针，省略数组索引的中转步骤
• 实例销毁时需要同步删除查找表对应条目，并free之前strdup的ID字符串，避免内存泄漏

方案2：无外部依赖极简实现 #

如果你的实例最多只有MAX_ONE_TYPES=20个，完全可以自己实现简单键值对存储，不需要引入外部库：

#define MAX_ONE_TYPES 20
// 定义查找表条目结构体
typedef struct {
    const char* id;
    int index;
} LookupEntry;

LookupEntry oneTypeClass_Lookup[MAX_ONE_TYPES];
int lookupEntryCount = 0;
oneTypeClass* oneTypeClasses[MAX_ONE_TYPES] EXT_RAM_ATTR;
int createdOneTypesCounter = 0;

// 创建实例时插入查找表
for (JsonPair oneTypeRef: oneTypes) {
   const char* oneTypeID     = oneTypeRef.key().c_str();
   JsonObject oneTypeOptions = oneTypes[oneTypeID];
   oneTypeClasses[createdOneTypesCounter] = new oneTypeClass(oneTypeOptions);
   oneTypeClass_Lookup[lookupEntryCount].id = strdup(oneTypeID);
   oneTypeClass_Lookup[lookupEntryCount].index = createdOneTypesCounter;
   lookupEntryCount++;
   createdOneTypesCounter++;
}

// 查询函数
static const inline int getOneTypeClassIndex(const char* packetID){
    for(int i=0; i<lookupEntryCount; i++){
        if(strcmp(oneTypeClass_Lookup[i].id, packetID) == 0){
            return oneTypeClass_Lookup[i].index;
        }
    }
    return -1;
}

该方案虽然还是遍历，但仅遍历纯内存存储的字符串索引，不需要访问外部RAM的实例对象，性能也远高于原来的遍历实例方案。

内容的提问来源于stack exchange，提问作者Dr.Random