概述

• 在之前的一篇文章中，作者寫了一個事件組件-- 超精簡的訂閱發布事件組件--SPEvent，這個組件是采用鏈表建立所有事件節點的關系的。
• 鏈表的優缺點：

1. 優點：①鏈表上的元素在空間存儲上內存地址不連續；②在插入和刪除操作時，只需要修改被刪節點上一節點的鏈接地址，不需要移動元素；
2. 缺點：①沒有解決連續存儲分配帶來的表長難以確定的問題；②失去了順序存儲結構隨機存取的特性；③不能通過數學表達式計算被查找元素的內存地址，每一次查找都是從頭節點開始遍歷，直到找到為止。

• SPEvent實際不會存在刪改的動作，顯然鏈表的優點在這個組件中無法體現優勢。而實際順利存儲更能滿足SPEvent的業務及能力，那么有什么方式能做到這個操作了？答案肯定是有的，有一個好組件(Vector)正好可以解決掉這個問題。
• Vector組件--向量；這個名稱一點也不陌生，比如我們單片機開發中常常聽到中斷向量表，它是通過地址查找對應中斷服務函數；而Vector組件也有點類似這個概念，它可以通過名稱、類型查找對象。
• Vector組件的優勢可以應用像SPEvent這類組件中，如：SPEvent就可以通過Event類型去查找事件節點。那么Vector是怎么實現的？？

Vector組件

Vector組件--它是類似于鏈表擁有的能力，是一種動態數組存儲組件，Vector組件擁有的能力如下：

1. 提供了順序存儲的能力，并且能夠動態增大順序存儲空間；
2. 提供了增加對象能力，查找對象能力。
3. 提供獲取順序存儲空間能力，獲取對象個數能力。
4. 采用KEY-VALUE的特性開查找對象。

Vector接口說明：

Vector實現：

• 數據結構：每一個存儲列表都需要構造一個Vector結構體對象，用于存儲元素對象。

//vector.h
#defineGROW_STEP4

#defineINVALID_INDEX(-1)
typedefvoid*(*VECTOR_Key)(constvoid*);//應用層提供KEY-VALUE獲取方法，泛類型
typedefint(*VECTOR_Compare)(constvoid*,constvoid*);//應用層提供比較函數，泛類型

typedefstructSimpleVector{
int16_tmax;//vector所能存儲的最大數據記錄數目
int16_ttop;//vector當前已經存儲的數據的峰值數目
int16_tfree;//vector已經被釋放的數據記錄數目
void**data;//vector存儲數據指針
VECTOR_Keykey;//將數據元素轉換為用于比較的鍵。方法由用戶提供
VECTOR_Comparecompare;//將用于比較鍵值。方法由用戶提供
}Vector;

• Vector列表對象構造方法：其中max，top，free初始狀態都為0。

VectorVECTOR_Make(VECTOR_Keykey,VECTOR_Comparecompare)
{
Vectorvector={0,0,0,NULL,key,compare};
returnvector;
}

• Vector列表對象清除方法：將Vector列表對象的數據元素空間釋放，并將max，top，free清0。

voidVECTOR_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_tVECTOR_Add(Vector*vector,void*element)
{
if(vector==NULL||element==NULL){
returnINVALID_INDEX;
}

if(vector->top>=vector->max){
int16_ti;
for(i=vector->top-(int16_t)1;i>=0;--i){
if(vector->data[i]==NULL){
vector->data[i]=element;
vector->free--;
returni;
}
}

if(vector->max+GROW_STEP0){
returnINVALID_INDEX;
}

void**data=(void**)malloc(sizeof(void*)*(vector->max+GROW_STEP));
if(data==NULL){
returnINVALID_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;
returnvector->top++;
}

• Vector列表對象根據下標過去對象方法：Vector可以直接通過順序表的策略，直接通過下標獲取元素；相對于鏈表來說，效率更加有優勢。

void*VECTOR_At(Vector*vector,int16_tindex)
{
if(vector==NULL||vector->top<=?index?||?index?0){
returnNULL;
}

returnvector->data[index];
}

• Vector列表對象根據下標替換對象方法：Vector可以直接通過順序表的策略，直接通過下標修改元素；相對于鏈表來說，效率更加有優勢。

void*VECTOR_Swap(Vector*vector,int16_tindex,void*element)
{
if(vector==NULL||vector->top<=?index?||?index?0){
returnNULL;
}
if(element==NULL){
vector->free++;
}
void*oldElement=vector->data[index];
vector->data[index]=element;
returnoldElement;
}

• Vector列表對象根據元素查找對應下標方法：最終也是調用VECTOR_FindByKey方法。

int16_tVECTOR_Find(Vector*vector,constvoid*element)
{
if(vector==NULL||element==NULL){
returnINVALID_INDEX;
}
returnVECTOR_FindByKey(vector,(vector->key==NULL)?element:vector->key(element));
}

• Vector列表對象根據鍵查找對應下標方法：遍歷整個Vector列表，查詢對應的key值，并返回對應下邊。

int16_tVECTOR_FindByKey(Vector*vector,constvoid*key)
{
if(vector==NULL||key==NULL){
returnINVALID_INDEX;
}

int16_ti;
for(i=0;ivector->top;++i){
if(vector->data[i]==NULL){
continue;
}

void*first=(vector->key!=NULL)?vector->key(vector->data[i]):vector->data[i];
if(first==key){
returni;
}

if(vector->compare==NULL||first==NULL){
continue;
}

if(vector->compare(first,key)==0){
returni;
}
}
returnINVALID_INDEX;
}

• Vector列表對象中元素個數獲取方法：

int16_tVECTOR_Size(Vector*vector)
{
if(vector==NULL){
returnINVALID_INDEX;
}
returnvector->top;
}

• Vector列表對象中元素記錄數目獲取方法：

int16_tVECTOR_Num(Vector*vector)
{
if(vector==NULL){
returnINVALID_INDEX;
}
returnvector->top-vector->free;
}

Vector使用：

1. 定義一個元素結構體（vector_test），包含兩個字段：name和data，其中name可以作為元素對象的唯一標識。

2. 定義兩個vector_test變量，test1和test2。

3. 我們這個demo是采用name作為唯一標識，需要頂一個函數用于獲取vector_test變量的name字段成員的值，作為VECTOR_Key指向函數。

4. 通過VECTOR_Make構造一個vector對象。其中VECTOR_Key指向vector_name_get函數作為key獲取，VECTOR_Compare指向strcmp函數用于key（name字符串）的比較。

5. 通過VECTOR_Add向vector對象增加元素test1和test2。

6. 通過VECTOR_FindByKey從vector對象查找元素對象下標。如：key為"rice"的元素對象下標。

7. 通過VECTOR_FindByKey獲取的pos，調用VECTOR_At獲取元素對象。

8. 驗證：根據獲取元素對象調用其成員，確定是否成功。

#include"vector.h"

Vectorvector;

typedefstruct{
char*name;
intdata;
}vector_test;

vector_testtest1={"rice",100};
vector_testtest2={"chen",100};

constchar*vector_name_get(vector_test*test)
{
returntest->name;
}

intmain(void)
{
vector=VECTOR_Make(vector_name_get,strcmp);

VECTOR_Add(&vector,&test1);
VECTOR_Add(&vector,&test2);

int16_tpos=VECTOR_FindByKey(&vector,"rice");

printf("pos:%drn",pos);

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

printf("name:%srn",temp->name);

returnRT_EOK;
}

• 結果：

歡迎關注微信公眾號『Rice嵌入式開發技術分享』