链表的替代品--Vector组件
概述 在之前的一篇文章中，作者写了一个事件组件-- 超精简的订阅发布事件组件--spevent，这个组件是采用链表建立所有事件节点的关系的。 链表的优缺点： 优点：①链表上的元素在空间存储上内存地址不连续；②在插入和删除操作时，只需要修改被删节点上一节点的链接地址，不需要移动元素； 缺点：①没有解决连续存储分配带来的表长难以确定的问题；②失去了顺序存储结构随机存取的特性；③不能通过数学表达式计算被查找元素的内存地址，每一次查找都是从头节点开始遍历，直到找到为止。 spevent实际不会存在删改的动作，显然链表的优点在这个组件中无法体现优势。而实际顺利存储更能满足spevent的业务及能力，那么有什么方式能做到这个操作了？答案肯定是有的，有一个好组件(vector)正好可以解决掉这个问题。 vector组件--向量；这个名称一点也不陌生，比如我们单片机开发中常常听到中断向量表，它是通过地址查找对应中断服务函数；而vector组件也有点类似这个概念，它可以通过名称、类型查找对象。 vector组件的优势可以应用像spevent这类组件中，如：spevent就可以通过event类型去查找事件节点。那么vector是怎么实现的？？ vector组件 vector组件--它是类似于链表拥有的能力，是一种动态数组存储组件，vector组件拥有的能力如下：
提供了顺序存储的能力，并且能够动态增大顺序存储空间； 提供了增加对象能力，查找对象能力。 提供获取顺序存储空间能力，获取对象个数能力。 采用key-value的特性开查找对象。 vector接口说明： 接口 描述
vector vector_make(vector_key key, vector_compare compare) 创建vector列表对象，用户根据业务注册vector_key方法和vector_compare方法
void vector_clear(vector *vector) 清空vector列表对象，并释放存储数据空间
int16_t vector_add(vector *vector, void *element) 添加元素到vector列表对象
int16_t vector_size(vector *vector) 获取vector列表对象的元素个数
int16_t vector_num(vector *vector) 获取vector列表对象的元素记录数目
void *vector_at(vector *vector, int16_t index) 根据下标获取vector列表对象的元素
void *vector_swap(vector *vector, int16_t index, void *element) 替换指定下标的vector列表对象的元素
int16_t vector_find(vector *vector, const void *element) 通过元素从vector列表对象中查找对应下标
int16_t vector_findbykey(vector *vector, const void *key) 通过键从vector列表对象中查找对应下标
vector实现： 数据结构：每一个存储列表都需要构造一个vector结构体对象，用于存储元素对象。 // vector.h#define grow_step 4#define invalid_index (-1)typedef void *(*vector_key)(const void *); // 应用层提供key-value获取方法，泛类型typedef int (*vector_compare)(const void *, const void *); // 应用层提供比较函数，泛类型typedef struct simplevector { int16_t max; // vector所能存储的最大数据记录数目 int16_t top; // vector当前已经存储的数据的峰值数目 int16_t free; // vector已经被释放的数据记录数目 void **data; // vector存储数据指针 vector_key key; // 将数据元素转换为用于比较的键。方法由用户提供 vector_compare compare; // 将用于比较键值。方法由用户提供} vector; vector列表对象构造方法：其中max，top，free初始状态都为0。 vector vector_make(vector_key key, vector_compare compare){ vector vector = {0, 0, 0, null, key, compare}; return vector;} vector列表对象清除方法：将vector列表对象的数据元素空间释放，并将max，top，free清0。 void vector_clear(vector *vector){ if (vector == null) { return; } if (vector->data == null) { return; } free(vector->data); vector->max = 0; vector->top = 0; vector->free = 0; vector->data = null;} vector列表对象增加元素方法： 存储方式：采用顺序存储方式 存储空间扩展策略：通过grow_step的来决定没存储多少个元素来动态扩展空间；描述：如grow_step的值为4，每次申请4个空间进行存储，如果存储元素个数小于4个，不会重新申请空间；如果元素个数个数超过4个，那么将重新申请4个空间。以此类推。优点：减少每次增加元素都要重新申请空间，提高了效率。 int16_t vector_add(vector *vector, void *element){ if (vector == null || element == null) { return invalid_index; } if (vector->top >= vector->max) { int16_t i; for (i = vector->top - (int16_t)1; i >= 0; --i) { if (vector->data[i] == null) { vector->data[i] = element; vector->free--; return i; } } if (vector->max + grow_step max + grow_step)); if (data == null) { return invalid_index; } if (vector->data != null) { (void)memcpy(data, vector->data, sizeof(void *) * vector->max); free(vector->data); } vector->data = data; vector->max += grow_step; } vector->data[vector->top] = element; return vector->top++;} vector列表对象根据下标过去对象方法：vector可以直接通过顺序表的策略，直接通过下标获取元素；相对于链表来说，效率更加有优势。 void *vector_at(vector *vector, int16_t index){ if (vector == null || vector->top <= index || index data[index];} vector列表对象根据下标替换对象方法：vector可以直接通过顺序表的策略，直接通过下标修改元素；相对于链表来说，效率更加有优势。 void *vector_swap(vector *vector, int16_t index, void *element){ if (vector == null || vector->top <= index || index free++; } void *oldelement = vector->data[index]; vector->data[index] = element; return oldelement;} vector列表对象根据元素查找对应下标方法：最终也是调用vector_findbykey方法。 int16_t vector_find(vector *vector, const void *element){ if (vector == null || element == null) { return invalid_index; } return vector_findbykey(vector, (vector->key == null) ? element : vector->key(element));} vector列表对象根据键查找对应下标方法：遍历整个vector列表，查询对应的key值，并返回对应下边。 int16_t vector_findbykey(vector *vector, const void *key){ if (vector == null || key == null) { return invalid_index; } int16_t i; for (i = 0; i top; ++i) { if (vector->data[i] == null) { continue; } void *first = (vector->key != null) ? vector->key(vector->data[i]) : vector->data[i]; if (first == key) { return i; } if (vector->compare == null || first == null) { continue; } if (vector->compare(first, key) == 0) { return i; } } return invalid_index;} vector列表对象中元素个数获取方法： int16_t vector_size(vector *vector){ if (vector == null) { return invalid_index; } return vector->top;} vector列表对象中元素记录数目获取方法： int16_t vector_num(vector *vector){ if (vector == null) { return invalid_index; } return vector->top - vector->free;} vector使用： 定义一个元素结构体（vector_test），包含两个字段：name和data，其中name可以作为元素对象的唯一标识。
定义两个vector_test变量，test1和test2。
我们这个demo是采用name作为唯一标识，需要顶一个函数用于获取vector_test变量的name字段成员的值，作为vector_key指向函数。
通过vector_make构造一个vector对象。其中vector_key指向vector_name_get函数作为key获取，vector_compare指向strcmp函数用于key（name字符串）的比较。
通过vector_add向vector对象增加元素test1和test2。
通过vector_findbykey从vector对象查找元素对象下标。如：key为rice的元素对象下标。
通过vector_findbykey获取的pos，调用vector_at获取元素对象。
验证：根据获取元素对象调用其成员，确定是否成功。
#include vector.hvector vector;typedef struct { char *name; int data;}vector_test;vector_test test1 = {rice, 100};vector_test test2 = {chen, 100};const char *vector_name_get(vector_test *test){ return test->name;}int main(void){ vector = vector_make(vector_name_get, strcmp); vector_add(&vector, &test1); vector_add(&vector, &test2); int16_t pos = vector_findbykey(&vector, rice); printf(pos: %drn, pos); vector_test *temp = vector_at(&vector, pos); printf(name: %srn, temp->name); return rt_eok;} 结果： 欢迎关注微信公众号『rice嵌入式开发技术分享』
中国四组半导体产业联盟呼之欲出 台湾封测受威胁
怎样在Windows8.1中设置双显示器显示
小型太阳能光伏发电系统中的电路保护思考
针对5G承载需求诺基亚贝尔已经做好了充分的准备
可调稳压电源电路
链表的替代品--Vector组件
2020Medtec中国展参观注册系统正式开放， 助力医疗器械制造企业研发采购
华为对三星元器件组件的依赖在逐渐减小，尤其是在半导体领域
性能说iPhone 8,其实也不过如此
更新太快，华为P10还没发布，P系列曲面机就来了
【世说芯品】兆易创新GD25WDxxK6 SPI NOR Flash产品系列问世，“超小尺寸、超轻薄、宽电压”持续领跑市场
华为mate10什么时候上市?华为mate10最新消息:高颜值+高配置,售价很良心,还买什么iPhone8?
用74ls138实现2位二进制乘法器
密码指纹锁的安全性能怎么样
Vishay新款可熔断绕线安全电阻 可承受6kV浪涌电压
台积电3nm工艺进度超前 EUV工艺获突破：直奔1nm
2020全球半导体15强业绩预估出炉
OPPO手机，最能代表年轻用户群体的手机品牌
Helieon（TM）LED照明模块让你即插即用
案例 | 网络上云，内有乾坤 —— 华为助力万达加速企业数智化升级
提供了顺序存储的能力，并且能够动态增大顺序存储空间； 提供了增加对象能力，查找对象能力。 提供获取顺序存储空间能力，获取对象个数能力。 采用key-value的特性开查找对象。 vector接口说明： 接口 描述
vector vector_make(vector_key key, vector_compare compare) 创建vector列表对象，用户根据业务注册vector_key方法和vector_compare方法
void vector_clear(vector *vector) 清空vector列表对象，并释放存储数据空间
int16_t vector_add(vector *vector, void *element) 添加元素到vector列表对象
int16_t vector_size(vector *vector) 获取vector列表对象的元素个数
int16_t vector_num(vector *vector) 获取vector列表对象的元素记录数目
void *vector_at(vector *vector, int16_t index) 根据下标获取vector列表对象的元素
void *vector_swap(vector *vector, int16_t index, void *element) 替换指定下标的vector列表对象的元素
int16_t vector_find(vector *vector, const void *element) 通过元素从vector列表对象中查找对应下标
int16_t vector_findbykey(vector *vector, const void *key) 通过键从vector列表对象中查找对应下标
vector实现： 数据结构：每一个存储列表都需要构造一个vector结构体对象，用于存储元素对象。 // vector.h#define grow_step 4#define invalid_index (-1)typedef void *(*vector_key)(const void *); // 应用层提供key-value获取方法，泛类型typedef int (*vector_compare)(const void *, const void *); // 应用层提供比较函数，泛类型typedef struct simplevector { int16_t max; // vector所能存储的最大数据记录数目 int16_t top; // vector当前已经存储的数据的峰值数目 int16_t free; // vector已经被释放的数据记录数目 void **data; // vector存储数据指针 vector_key key; // 将数据元素转换为用于比较的键。方法由用户提供 vector_compare compare; // 将用于比较键值。方法由用户提供} vector; vector列表对象构造方法：其中max，top，free初始状态都为0。 vector vector_make(vector_key key, vector_compare compare){ vector vector = {0, 0, 0, null, key, compare}; return vector;} vector列表对象清除方法：将vector列表对象的数据元素空间释放，并将max，top，free清0。 void vector_clear(vector *vector){ if (vector == null) { return; } if (vector->data == null) { return; } free(vector->data); vector->max = 0; vector->top = 0; vector->free = 0; vector->data = null;} vector列表对象增加元素方法： 存储方式：采用顺序存储方式 存储空间扩展策略：通过grow_step的来决定没存储多少个元素来动态扩展空间；描述：如grow_step的值为4，每次申请4个空间进行存储，如果存储元素个数小于4个，不会重新申请空间；如果元素个数个数超过4个，那么将重新申请4个空间。以此类推。优点：减少每次增加元素都要重新申请空间，提高了效率。 int16_t vector_add(vector *vector, void *element){ if (vector == null || element == null) { return invalid_index; } if (vector->top >= vector->max) { int16_t i; for (i = vector->top - (int16_t)1; i >= 0; --i) { if (vector->data[i] == null) { vector->data[i] = element; vector->free--; return i; } } if (vector->max + grow_step max + grow_step)); if (data == null) { return invalid_index; } if (vector->data != null) { (void)memcpy(data, vector->data, sizeof(void *) * vector->max); free(vector->data); } vector->data = data; vector->max += grow_step; } vector->data[vector->top] = element; return vector->top++;} vector列表对象根据下标过去对象方法：vector可以直接通过顺序表的策略，直接通过下标获取元素；相对于链表来说，效率更加有优势。 void *vector_at(vector *vector, int16_t index){ if (vector == null || vector->top <= index || index data[index];} vector列表对象根据下标替换对象方法：vector可以直接通过顺序表的策略，直接通过下标修改元素；相对于链表来说，效率更加有优势。 void *vector_swap(vector *vector, int16_t index, void *element){ if (vector == null || vector->top <= index || index free++; } void *oldelement = vector->data[index]; vector->data[index] = element; return oldelement;} vector列表对象根据元素查找对应下标方法：最终也是调用vector_findbykey方法。 int16_t vector_find(vector *vector, const void *element){ if (vector == null || element == null) { return invalid_index; } return vector_findbykey(vector, (vector->key == null) ? element : vector->key(element));} vector列表对象根据键查找对应下标方法：遍历整个vector列表，查询对应的key值，并返回对应下边。 int16_t vector_findbykey(vector *vector, const void *key){ if (vector == null || key == null) { return invalid_index; } int16_t i; for (i = 0; i top; ++i) { if (vector->data[i] == null) { continue; } void *first = (vector->key != null) ? vector->key(vector->data[i]) : vector->data[i]; if (first == key) { return i; } if (vector->compare == null || first == null) { continue; } if (vector->compare(first, key) == 0) { return i; } } return invalid_index;} vector列表对象中元素个数获取方法： int16_t vector_size(vector *vector){ if (vector == null) { return invalid_index; } return vector->top;} vector列表对象中元素记录数目获取方法： int16_t vector_num(vector *vector){ if (vector == null) { return invalid_index; } return vector->top - vector->free;} vector使用： 定义一个元素结构体（vector_test），包含两个字段：name和data，其中name可以作为元素对象的唯一标识。
定义两个vector_test变量，test1和test2。
我们这个demo是采用name作为唯一标识，需要顶一个函数用于获取vector_test变量的name字段成员的值，作为vector_key指向函数。
通过vector_make构造一个vector对象。其中vector_key指向vector_name_get函数作为key获取，vector_compare指向strcmp函数用于key（name字符串）的比较。
通过vector_add向vector对象增加元素test1和test2。
通过vector_findbykey从vector对象查找元素对象下标。如：key为rice的元素对象下标。
通过vector_findbykey获取的pos，调用vector_at获取元素对象。
验证：根据获取元素对象调用其成员，确定是否成功。
#include vector.hvector vector;typedef struct { char *name; int data;}vector_test;vector_test test1 = {rice, 100};vector_test test2 = {chen, 100};const char *vector_name_get(vector_test *test){ return test->name;}int main(void){ vector = vector_make(vector_name_get, strcmp); vector_add(&vector, &test1); vector_add(&vector, &test2); int16_t pos = vector_findbykey(&vector, rice); printf(pos: %drn, pos); vector_test *temp = vector_at(&vector, pos); printf(name: %srn, temp->name); return rt_eok;} 结果： 欢迎关注微信公众号『rice嵌入式开发技术分享』
中国四组半导体产业联盟呼之欲出 台湾封测受威胁
怎样在Windows8.1中设置双显示器显示
小型太阳能光伏发电系统中的电路保护思考
针对5G承载需求诺基亚贝尔已经做好了充分的准备
可调稳压电源电路
链表的替代品--Vector组件
2020Medtec中国展参观注册系统正式开放， 助力医疗器械制造企业研发采购
华为对三星元器件组件的依赖在逐渐减小，尤其是在半导体领域
性能说iPhone 8,其实也不过如此
更新太快，华为P10还没发布，P系列曲面机就来了
【世说芯品】兆易创新GD25WDxxK6 SPI NOR Flash产品系列问世，“超小尺寸、超轻薄、宽电压”持续领跑市场
华为mate10什么时候上市?华为mate10最新消息:高颜值+高配置,售价很良心,还买什么iPhone8?
用74ls138实现2位二进制乘法器
密码指纹锁的安全性能怎么样
Vishay新款可熔断绕线安全电阻 可承受6kV浪涌电压
台积电3nm工艺进度超前 EUV工艺获突破：直奔1nm
2020全球半导体15强业绩预估出炉
OPPO手机，最能代表年轻用户群体的手机品牌
Helieon（TM）LED照明模块让你即插即用
案例 | 网络上云，内有乾坤 —— 华为助力万达加速企业数智化升级