在将HM的C++代码改为C的过程中，HM中有STL库中的容器类型list ,vector等。
下面的代码是将vector<int>类型使用C来实现，具体的函数对应参考文件 vector 中的源码实现。
vector 实际上是一个容量可以动态变化的数组类型，保证了元素存储空间的连续性，数组的大小又可以动态的改变。使用size来指示实际元素的数目，capacity指示容量的大小。当capacity不够时就要重新分配内存，这些元素插入及删除的操作都需要内存的移动。
#ifndef __VECTOR_INT__
#define __VECTOR_INT__
#include <stdint.h>
#include <memory.h>
#include <stdlib.h>
#include <stdio.h>
typedef struct vector_int
{
unsigned long size;
unsigned long capacity;
int* data;
}vector_int;
inline vector_int* vector_int_Constructor(vector_int* thisptr)
{
/* Check if memory has been allocated for struct */
if (thisptr == NULL)
{
/* Allocate memory of struct size. */
thisptr = (vector_int *) malloc(sizeof(vector_int));
}
if (thisptr)
{
thisptr->size = 0;
thisptr->capacity = 0;
thisptr->data = NULL;
}
return thisptr;
}
inline void vector_int_Destructor(vector_int* thisptr)
{
if(thisptr->data)
{
free(thisptr->data);
thisptr->data=NULL;
}
thisptr->size=0;
thisptr->capacity=0;
}
inline int* vector_int_front(vector_int* thisptr)
{
return &thisptr->data[0];
}
inline int* vector_int_back(vector_int* thisptr)
{
return &thisptr->data[thisptr->size-1];
}
inline int* vector_int_begin(vector_int* thisptr)
{
return &thisptr->data[0];
}
inline int* vector_int_end(vector_int* thisptr)
{
return &thisptr->data[thisptr->size];
}
inline unsigned long vector_int_size(vector_int* thisptr)
{
return thisptr->size;
}
static inline unsigned int _Grow_to(vector_int* thisptr,unsigned int _Count)
{ // grow by 50% or at least to _Count
unsigned int _Capacity = thisptr->capacity;
_Capacity = _Capacity + _Capacity / 2; // try to grow by 50%
if (_Capacity < _Count)
_Capacity = _Count;
return (_Capacity);
}
static inline void reserve(vector_int* thisptr,unsigned int _Count)
{ // determine new minimum length of allocated storage
int* _Ptr;
if (thisptr->capacity < _Count)
{ // not enough room, reallocate
_Ptr = (int*)malloc(sizeof(int)*_Count);//注意要用 sizeof(int)*
if(_Ptr==NULL)
{
printf("memory malloc failed!\n");
exit(0);
}
memcpy(_Ptr,thisptr->data,sizeof(int)*thisptr->size);
if (thisptr->data != 0)
{ // destroy and deallocate old array
free(thisptr->data);
}
thisptr->capacity = _Count;
thisptr->data = _Ptr;
}
}
static inline void _Reserve(vector_int* thisptr,unsigned int _Count)
{ // ensure room for _Count new elements, grow exponentially
unsigned int _Size = thisptr->size;
if ((_Size += _Count) > thisptr->capacity)
reserve(thisptr,_Grow_to(thisptr,_Size));
}
inline void vector_int_push_back(vector_int* thisptr,int _Val)
{
if(thisptr->size==thisptr->capacity)
_Reserve(thisptr,1);
thisptr->data[thisptr->size] = _Val;
thisptr->size++;
}
//一个元素插入到 pos 指示的位置之前,返回x的新位置
inline int* vector_int_insert1(vector_int* thisptr,int* position, int x)
{
int i;
int n = position - vector_int_begin(thisptr);
if (position == vector_int_end(thisptr)) {
vector_int_push_back(thisptr, x);
}
else
{
if(thisptr->size==thisptr->capacity)
_Reserve(thisptr,1);
for(i=thisptr->size-1;i>=n;i--)
thisptr->data[i+1] = thisptr->data[i];
thisptr->data[i+1] = x;
thisptr->size++;
}
return vector_int_begin(thisptr) + n;
}
inline void vector_int_insert(vector_int* thisptr,int* position,int* first,int* last)
{
int* pos=position;
for ( ; first != last; ++first)
{
pos = vector_int_insert1(thisptr,pos, *first);
++pos;
}
}
//删除[beg,end)区间的数据，传回下一个数据的位置。
inline int* vector_int_erase(vector_int* thisptr,int* _First,int* _Last)
{
int* _Ptr;
if (_First != _Last)
{ // worth doing, copy down over hole
if (_Last < _First || _First < thisptr->data
|| vector_int_end(thisptr) < (_Last))
{printf("vector erase iterator outside range");exit(0);}
for(_Ptr=_First;_Ptr<_Last;_Ptr++)
{
if( _Ptr+(_Last-_First)<vector_int_end(thisptr) )
*_Ptr=*(_Ptr+(_Last-_First));
else
break;
}
thisptr->size -= (_Last-_First) ;
}
return (_First);
}
inline void vector_int_clear(vector_int* thisptr)
{
vector_int_erase(thisptr,vector_int_begin(thisptr) , vector_int_end(thisptr));
}
inline void vector_int_resize(vector_int* thisptr,unsigned int _Newsize)
{ // determine new length, padding with _Ty() elements as needed
if (_Newsize < thisptr->size)
vector_int_erase(thisptr,vector_int_begin(thisptr) + _Newsize, vector_int_end(thisptr));
else if (thisptr->size < _Newsize)
{ // pad as needed
_Reserve(thisptr,_Newsize - thisptr->size);
memset(thisptr->data+thisptr->size,0,_Newsize - thisptr->size);
thisptr->size = _Newsize ;
}
}
//算法库中的 search_n函数
inline int* vector_int_search_n(int* _First1, int* _Last1,
int _Count, int _Val)
{
int* _Mid1;
int _Count1;
if (_Count <= 0)
return (_First1);
for (; _First1 != _Last1; ++_First1)
if (*_First1 == _Val)
{ // found start of possible match, check it out
_Mid1 = _First1;
for ( _Count1 = _Count; ; )
if (--_Count1 == 0)
return (_First1); // found rest of match, report it
else if (++_Mid1 == _Last1)
return (_Last1); // short match at end
else if (!(*_Mid1 == _Val))
break; // short match not at end
_First1 = _Mid1; // pick up just beyond failed match
}
return (_Last1);
}
#endif