链表的替代品--Vector组件

原创

Rice加饭

发布于 2023-03-24 09:09:52

6510

文章被收录于专栏：Rice嵌入式Rice嵌入式

概述

在之前的一篇文章中，作者写了一个事件组件-- 超精简的订阅发布事件组件--SPEvent，这个组件是采用链表建立所有事件节点的关系的。
链表的优缺点：
1. 优点：①链表上的元素在空间存储上内存地址不连续；②在插入和删除操作时，只需要修改被删节点上一节点的链接地址，不需要移动元素；
2. 缺点：①没有解决连续存储分配带来的表长难以确定的问题；②失去了顺序存储结构随机存取的特性；③不能通过数学表达式计算被查找元素的内存地址，每一次查找都是从头节点开始遍历，直到找到为止。
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 < 0) {
            return INVALID_INDEX;
        }

        void **data = (void **)malloc(sizeof(void *) * (vector->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 < 0) {
        return NULL;
    }

    return vector->data[index];
}

Vector列表对象根据下标替换对象方法：Vector可以直接通过顺序表的策略，直接通过下标修改元素；相对于链表来说，效率更加有优势。

void *VECTOR_Swap(Vector *vector, int16_t index, void *element)
{
    if (vector == NULL || vector->top <= index || index < 0) {
        return NULL;
    }
    if (element == NULL) {
        vector->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 < vector->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.h"

Vector 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: %d\r\n", pos);

    vector_test *temp = VECTOR_At(&vector, pos);

    printf("name: %s\r\n", temp->name);

    return RT_EOK;
}