在C语言环境下，编写自己的Vector容器。
由 王宇 原创并发布 ：
最近工作中，需要用标准C去实现一些统计数据的功能。开发过程中没有容器非常不方便，所以自己尝试着编写了一个简单的Vector容器。
一、功能说明：
通过一个例子来说明如何使用这个Vector：
#include "containers.h"
#include <stdio.h>
// 测试用的结构体
typedef struct tagTextStruct
{
int key;
char* value;
}TestStruct;
// 失败提示函数
static void ABORT( char *file,int line)
{
fprintf(stderr ,"*****\n\nABORT\nFile %s Line %d\n**********\n\n",file,line);
abort();
}
#define Abort () ABORT(__FILE__,__LINE__)
// 摧毁资源
static int destructorFunc( void *v)
{
// 获得Vector中的一个元素
TestStruct* ts = (TestStruct*)v;
if(ts->value != NULL )
{
int l = strlen (ts->value);
// 释放内存
free(ts->value);
ts->value = NULL;
}
return 0;
}
// 遍历并打印Vector中的元素
static void PrintVector(Vector *AL)
{
size_t i;
TestStruct* ts;
// 打印Vector中已有元素，和总容量
printf("Count %ld, Capacity %ld\n",(long)iVector. Size(AL),(long )iVector.GetCapacity(AL));
// 遍历Vector
for (i=0; i<iVector.Size (AL);i++) {
// 获得Vector中的元素
ts = (TestStruct*)iVector. GetElement(AL, i);
printf("%d\n" ,ts->key);
printf("%s\n" ,ts->value);
}
printf("\n" );
}
// 测试Vector
static int testVector(Vector** AL)
{
int errors=0;
char* s1 = "ts1 value." ;
char* s2 = "ts2 value" ;
char* temp1 = NULL ;
char* temp2 = NULL ;
TestStruct ts1, ts2;
*AL = iVector. Create(sizeof (TestStruct),5);
// 配置摧毁资源的回调函数，这里的destructorFunc是一个指针函数。
iVector. SetDestructor(*AL, destructorFunc );
// 初始化元素，并分配堆空间
ts1.key = 1;
temp1 = ( char*)malloc (strlen(s1) + 1);
if(temp1 == NULL)
{
Abort();
}
strcpy(temp1, s1);
ts1.value = temp1;
ts2.key = 2;
temp2 = ( char*)malloc (strlen(s2) + 1);
if(temp2 == NULL)
{
Abort();
}
strcpy(temp2, s2);
ts2.value = temp2;
// 将元素加入到Vecotor中
iVector. Add(*AL,&ts1);
iVector. Add(*AL,&ts2);
// 删除一个Vector
iVector. Erase(*AL, &ts1);
// 获得容器中的实际大小
if (1 != iVector.Size (*AL))
Abort();
return errors;
}
// 主程序入口
int main (void)
{
int errors=0;
Vector* AL = NULL;
// 测试Vector
errors += testVector (&AL);
// 释放Vector
iVector.Finalize(*AL);
return errors;
}
二、Vector的结构：
声明Vector类型：
/*----------------------------------------------------------------------------*/
/* Definition of the vector type */
/*----------------------------------------------------------------------------*/
struct _Vector {
VectorInterface *VTable; /* The table of functions */
size_t count; /* number of elements in the array */
unsigned int Flags; /* Read-only or other flags */
size_t ElementSize; /* Size of the elements stored in this array. */
void *contents; /* The contents of the collection */
size_t capacity; /* allocated space in the contents vector */
unsigned timestamp; /* Incremented at each change */
CompareFunction CompareFn; /* Element comparison function */
ErrorFunction RaiseError; /* Error function */
const ContainerAllocator *Allocator;
DestructorFunction DestructorFn;
} ;
声明Vector接口：
/****************************************************************************
* Vectors Interface *
****************************************************************************/
/* Definition of the functions associated with this type. */
typedef struct tagVector {
size_t (* Size)(const Vector *AL);
int (* Clear)(Vector *AL);
int (* Erase)(Vector *AL,const void *);
int (* EraseAll)(Vector *AL,const void *);
int (* Finalize)(Vector *AL);
int (* Apply)(Vector *AL,int (*Applyfn)( void *element,void * arg),void *arg);
int (* Equal)(const Vector *first,const Vector *second);
Vector *(* Copy)(const Vector *AL);
ErrorFunction (* SetErrorFunction)(Vector *AL,ErrorFunction );
size_t (* Sizeof)(const Vector *AL);
Vector *(* Load)(FILE *stream, ReadFunction readFn,void *arg);
size_t (* GetElementSize)(const Vector *AL);
int (* Add)(Vector *AL,const void *newval);
void *(* GetElement)(const Vector *AL,size_t idx);
int (* EraseAt)(Vector *AL,size_t idx);
int (* ReplaceAt)(Vector *AL,size_t idx,void *newval);
int (* IndexOf)(const Vector *AL,const void *data,void *ExtraArgs,size_t *result);
/* Vector container specific fields */
size_t (* GetCapacity)(const Vector *AL);
int (* SetCapacity)(Vector *AL,size_t newCapacity);
CompareFunction (* SetCompareFunction)(Vector *l,CompareFunction fn);
int (* Sort)(Vector *AL);
Vector *(* Create)(size_t elementsize,size_t startsize);
Vector *(* CreateWithAllocator)(size_t elemsiz,size_t startsiz,const ContainerAllocator *mm);
int (* CopyElement)(const Vector *AL,size_t idx,void *outbuf);
void **(* CopyTo)(const Vector *AL);
int (* Append)(Vector *AL1, Vector *AL2);
const ContainerAllocator *(* GetAllocator)(const Vector *AL);
DestructorFunction (* SetDestructor)(Vector *v,DestructorFunction fn);
int (* SearchWithKey)(Vector *vec,size_t startByte,size_t sizeKey,size_t startIndex,void *item,size_t *result);
int (* Resize)(Vector *AL,size_t newSize);
} VectorInterface;
内存分配对象：
/************************************************************************** */
/* */
/* Memory allocation object */
/* */
/************************************************************************** */
typedef struct tagAllocator {
void *(* malloc)(size_t); /* Function to allocate memory */
void (* free)(void *); /* Function to release it */
void *(* realloc)(void *,size_t);/* Function to resize a block of memory */
void *(* calloc)(size_t,size_t);
} ContainerAllocator;
三、功能的实现：
1，创建Vector
static Vector *CreateWithAllocator (size_t elementsize,size_t startsize,const ContainerAllocator *allocator)
{
Vector *result;
size_t es;
// 给Vector结构体分配内存空间。
/* Allocate space for the array list header structure */
result = allocator-> malloc(sizeof (*result));// 这个地方的malloc就是stdlib.h中的malloc, 通过指针函数赋予ContainerAllocator结构体。
// 判断内存分配是否成功。
if (result == NULL) {
iError.RaiseError( "iVector.Create",CONTAINER_ERROR_NOMEMORY );
return NULL ;
}
// 初始化内存。
memset(result,0, sizeof(*result));
if (startsize == 0)
startsize = DEFAULT_START_SIZE;
// 给Vector里面的内容分配内存空间。
es = startsize * elementsize; // 元素的个数乘单个元素的大小 ，如果在添加元素时，超出了这个范围会自动扩容。
result->contents = allocator-> malloc(es); // 这个地方的malloc就是stdlib.h中的malloc, 通过指针函数赋予ContainerAllocator结构体。
// 判断内存分配是否成功。
if (result->contents == NULL) {
iError.RaiseError( "iVector.Create",CONTAINER_ERROR_NOMEMORY ); // 这里有一个统一的错误处理接口iError
allocator-> free(result); // 这里的free就是stdlib.h中free, 通过指针函数赋予了ContainerAllocator结构体。
result = NULL;
}
else {
// 初始化内存
memset(result->contents,0,es);
// Vector的容量
result->capacity = startsize;
// Vector 接口
result->VTable = &iVector;
// Vector 中实际拥有的元素数量
result->ElementSize = elementsize;
// 元素对比
result->CompareFn = DefaultVectorCompareFunction;
result->RaiseError = iError.RaiseError;
// 内存管理器
result->Allocator = (ContainerAllocator *)allocator;
}
return result;
}
// 具体实现，此函数将会赋予指针函数接口：Vector *(* Create)(size_t elementsize,size_t startsize);
static Vector *Create (size_t elementsize,size_t startsize)
{
return CreateWithAllocator(elementsize,startsize,CurrentAllocator);
}
2， 向Vector中添加元素：
// 当超出规划大小时(vector->capacity), 将自动增长。
static int grow(Vector *AL)
{
size_t newcapacity;
void **oldcontents;
int r = 1;
// 自增长为原先的四分之一
newcapacity = AL->capacity + 1+AL->capacity/4;
oldcontents = ( void **)AL->contents;
// 变更内存空间
AL->contents = AL->Allocator->realloc (AL->contents,newcapacity*AL->ElementSize);
if (AL->contents == NULL ) {
NoMemory(AL,"Resize" ); // 输出错误。
AL->contents = oldcontents;
r = CONTAINER_ERROR_NOMEMORY;
}
else {
// 变更容量
AL->capacity = newcapacity;
AL->timestamp++;
}
return r;
}
// 具体实现，此函数将会赋予指针函数接口： int (* Add)(Vector *AL,const void *newval);
/*------------------------------------------------------------------------
Procedure: Add ID:1
Purpose: Adds an item at the end of the Vector
Input: The Vector and the item to be added
Output: The number of items in the Vector or negative if
error
Errors:
------------------------------------------------------------------------*/
static int Add(Vector *AL, const void *newval)
{
char *p;
// 判断输入参数是否合法
if (AL == NULL ) {
return NullPtrError ("Add");
}
if (newval == NULL ) {
AL->RaiseError( "iVector.Add",CONTAINER_ERROR_BADARG );
return CONTAINER_ERROR_BADARG ;
}
// 扩容
if (AL->count >= AL->capacity) {
int r = grow (AL);
if (r <= 0)
return r;
}
// 将添加的元素分布到内存当中
p = ( char *)AL->contents;
p += AL-> count*AL->ElementSize;
memcpy(p,newval,AL->ElementSize);
AL->timestamp++;
++AL-> count;
return 1;
}
3，删除Vector中的元素：
// 按照index 删除Vector中的元素
static int EraseAt(Vector *AL,size_t idx)
{
char *p;
// 判断输入参数是否合法
if (AL == NULL) {
return NullPtrError ("EraseAt");
}
if (idx >= AL-> count) {
AL->RaiseError( "iVector.Erase",CONTAINER_ERROR_INDEX ,AL,idx);
return CONTAINER_ERROR_INDEX ;
}
// 确定元素在内存中的位置
p = ( char *)AL->contents;
p += AL->ElementSize * idx;
// 如果用户定义了催化资源函数，则调用
if (AL->DestructorFn) {
AL->DestructorFn(p);
}
// 在内存中，移除元素
if (idx < (AL-> count-1)) {
memmove(p,p+AL->ElementSize,(AL->count -idx-1)*AL->ElementSize);
}
AL-> count--;
AL->timestamp++;
return 1;
}
static int EraseInternal(Vector *AL, const void *elem,int all)
{
size_t i;
char *p;
CompareInfo ci;
int result = CONTAINER_ERROR_NOTFOUND;
// 判断输入参数是否合法
if (AL == NULL) {
return NullPtrError ("Erase");
}
if (elem == NULL) {
AL->RaiseError( "iVector.Erase",CONTAINER_ERROR_BADARG );
return CONTAINER_ERROR_BADARG ;
}
if (AL->Flags & CONTAINER_READONLY)
return ErrorReadOnly(AL,"Erase" );
restart:
p = AL->contents;
ci.ContainerLeft = AL;
ci.ContainerRight = NULL;
ci.ExtraArgs = NULL;
// 遍历Vecotr容器
for (i=0; i<AL-> count;i++) {
// 判断删除的内容, 这里的CompareFn 是一个指针函数，用户可以自定义它，并且授予Vector
if (!AL->CompareFn(p,elem,&ci)) {
if (i > 0) {
// 获得元素的内存位置
p = GetElement(AL,--i);
result = EraseAt(AL,i+1);
} else {
// 删除第一个元素
result = EraseAt(AL,0);
// all = 0 则指删除一个，不在遍历Vector
if (result < 0 || all == 0) return result;
if (all) goto restart;
}
if (all == 0) return result;
result = 1;
}
p += AL->ElementSize;
}
return result;
}
// 具体实现，此函数将会赋予指针函数接口： int (* Erase)(Vector *AL,const void *);
static int Erase(Vector *AL, const void *elem)
{
// 参数0 ，表示只删除一个元素
return EraseInternal(AL,elem,0);
}
4，确定Vector的大小：
// 具体实现，此函数将会赋予指针函数接口： size_t (* Size)(const Vector *AL);
static size_t Size(const Vector *AL)
{
// 判断输入参数是否合法
if (AL == NULL) {
NullPtrError("Size" );
return 0;
}
// 返回Vector的实际大小
return AL-> count;
}
5，获得Vector中的元素：
// 具体实现，此函数将会赋予指针函数接口： void *(* GetElement)(const Vector *AL,size_t idx);
static void *GetElement( const Vector *AL,size_t idx)
{
char *p;
// 判断输入参数是否合法
if (AL == NULL) {
NullPtrError("GetElement" );
return NULL ;
}
if (idx >=AL-> count ) {
return AL->RaiseError("iVector.GetElement" ,CONTAINER_ERROR_INDEX,AL,idx);
}
// 获得内容的首地址
p = AL->contents;
// 计算元素地址
p += idx*AL->ElementSize;
return p;
}
6，释放Vector资源：
// 具体实现，此函数将会赋予指针函数接口： int (* Clear)(Vector *AL);
/*------------------------------------------------------------------------
Procedure: Clear ID:1
Purpose: Frees all memory from an array list object without
freeing the object itself
Input: The array list to be cleared
Output: The number of objects that were in the array list
Errors: The array list must be writable
------------------------------------------------------------------------*/
static int Clear(Vector *AL)
{
// 判断输入参数是否合法
if (AL == NULL) {
return NullPtrError ("Clear");
}
// 判断用户是否配置了摧毁函数，这里的DestructorFn 是一个指针函数。在例子中，就是函数destructorFunc()
if (AL->DestructorFn) {
size_t i;
unsigned char *p = (unsigned char *)AL->contents;
// 遍历Vector 并且使用DestructorFn 释放每一个元素的资源
for(i=0; i<AL->count ;i++) {
AL->DestructorFn(p);
p += AL->ElementSize;
}
}
AL-> count = 0;
AL->timestamp = 0;
AL->Flags = 0;
return 1;
}
// 具体实现，此函数将会赋予指针函数接口： int (* Finalize)(Vector *AL);
/*------------------------------------------------------------------------
Procedure: Finalize ID:1
Purpose: Releases all memory associated with an Vector,
including the Vector structure itself
Input: The Vector to be destroyed
Output: The number of items that the Vector contained or
zero if error
Errors: Input must be writable
------------------------------------------------------------------------*/
static int Finalize(Vector *AL)
{
unsigned Flags;
int result;
// 判断输入参数是否合法
if (AL == NULL)
return CONTAINER_ERROR_BADARG ;
// 释放元素所拥有的资源
result = Clear(AL);
if (result < 0)
return result;
// 释放Vector自身分配的内存空间
if (AL->VTable != &iVector)
AL->Allocator-> free(AL->VTable); //这里的free就是stdlib.h中free, 通过指针函数赋予了ContainerAllocator结构体。
AL->Allocator-> free(AL->contents);
AL->Allocator-> free(AL);
return result;
}
四、总结
由于篇幅的原因，这里仅仅介绍了这个Vector的基本功能，即 Create、Add、Erase、Size、GetElement、Finalize 。其他功能，例如：Appent RelaceAt Search IndexOf Sort Resize 等等。就不在这里介绍了， 原因是这篇博客的目的仅仅是为学习和研究C语言的朋友抛砖引玉，我在学习过程中总结了以下几方面相对比较重要的内容，提供给大家参考：
1、充分理解C语言程序，在内存中的分布。堆、栈、数据区等等。
2、内存的分配和释放。
3、指针和指针函数的灵活运用。
4、结构体和指针函数的配合使用，形成接口对象。
相关推荐
为了在这些场景下也能实现类似的功能，我们可以自己编写一个纯C语言版本的向量（vector）数据结构。`vector_master`项目就是这样一个实现，它提供了C语言环境下向量的基本操作。 首先，让我们理解一下向量（vector...
在C++编程中，`vector`是一个非常重要的容器，它属于标准模板库（STL）的一部分。`vector`提供了一种动态数组的概念，允许我们高效地存储和操作一系列元素。在C语言中，我们通常使用数组来存储和管理数据，但它们在...
它还会介绍STL（Standard Template Library），这是C++的标准库，包括容器（如vector、list、set）、算法（如排序、查找）和迭代器等组件，这些都是编写高效、可复用代码的重要工具。 总的来说，C语言的学习涉及到...
- **优化性能**：由于是用C语言编写的，因此在性能上通常优于C++的STL，尤其是在内存管理和计算密集型任务上。 使用libcstl时，开发者需要注意以下几点： - **类型安全**：C语言没有内置的类型检查机制，使用...
标题中提到的"一个通用的C语言编写的类似STL功能的集合库"，是针对C语言的一个扩展，它尝试模仿STL的模式，为C程序员提供了一套容器和算法的实现。这样的库对于初学者来说是非常有价值的，因为它不仅能够帮助他们...
在C++中，`#include "stdafx.h"`通常用于预编译头文件，这在Visual Studio环境下常见，但不是所有编译器都支持。其他如`#include "iostream.h"`和`#include "cs.h"`是包含必要的库和自定义类的头文件。 主函数`main...
C语言API则指的是用C语言编写的库函数，这些函数提供了丰富的功能，方便程序员进行系统级操作或实现特定任务。C++ API通常是在C++环境中使用的API，可能包括C++标准库、第三方库或者特定平台的扩展。 本压缩包"**...
这个项目不仅涵盖了C语言和C++的基本语法，还涉及到面向对象编程、容器（如vector）的使用，以及控制台操作的相关技术。 ### 一、项目功能概述 1. **背景音乐/音效**：增加游戏体验感。 2. **欢迎界面和游戏选项**...
C语言头文件是C语言编程中的一部分，包含了许多有用的函数和宏定义，这些函数和宏定义可以帮助程序员更方便地编写C语言程序。下面我们将对C语言头文件中的函数进行详细的介绍。 assert.h assert.h头文件提供了一个...
在编写这些容器时，尽可能遵循C++ STL的设计原则，提供一致的接口和行为，以便用户能轻松迁移代码。 总之，这个项目旨在通过C语言来实现C++ `<std>`库中的一些核心数据容器，这既是对C语言能力的挑战，也是对C++ ...
根据提供的文件信息，标题与描述均提到了“c.STL 学习c语言的必看”，这表明文章的主题是关于C++标准模板库（STL）在C语言学习中的重要性，尽管C语言本身并不支持STL，但此处应当理解为C++语言的学习资料。...
通过《11_C语言_visualc_》的学习，你可以掌握C语言编程的基本技能，并进一步了解如何在Visual C++环境下进行高效的C++开发，同时也能接触到面向对象编程这一重要的编程范式。结合书中内容，实践操作，将理论知识...
STL包含容器（如vector、list、set等）、算法（如排序、查找等）和迭代器等组件，极大地提升了C语言的生产力。学习如何有效地利用STL，可以让你的代码更加简洁高效。在源码帝国的资料中，你会发现关于STL的深入讲解...
同时，C++还包含了STL（标准模板库），提供了容器（如vector、list）、迭代器、算法和函数对象，极大地丰富了编程工具箱。 在 Turbo C/C++ V3.0 的环境中，用户可以通过创建项目来组织多个源文件，这对于大型软件的...
在C语言中，程序员需要理解和掌握ASCII码表，以便处理字符输入输出、字符串操作等任务。例如，你可以通过比较ASCII码来实现字符的大小写转换，或者通过计算ASCII值来进行简单的文本处理。手册中的这部分内容会详细...
C++中的容器是标准模板库(STL)的重要组成部分，提供了多种数据结构来适应不同场景下的需求。本篇文章将深入探讨C++容器的使用经验，帮助开发者更好地理解和运用这些工具。 首先，选择合适的容器类型至关重要。C++...
- **标准模板库(STL)**：C++标准库提供了丰富的容器类，如vector、list、map等，可以方便地管理各种类型的数据集合。 - **智能指针**：使用智能指针（如shared_ptr、unique_ptr）来自动管理内存，减少内存泄漏的风险...
1. **语法兼容**：C++完全兼容C语言，C语言的代码可以直接在C++环境中编译运行。 2. **编程范式**：C语言是面向过程的，而C++支持面向过程、面向对象和泛型编程。 3. **安全性**：C++通过异常处理和智能指针等机制...