|
一般在写 C 程序时用 typedef 将容器中元素的类型抽象,无法在同一个程序中用到两种类型,而本文试图在一个程序中用到两种不同类型的容器,比如实现类似于 C++ 中的 vector<char> 和 vector<double>。核心技术是将元素类型定义为 void *,管它什么类型,都用 void * 类型的指针指向真正的数据,与此同时,类型的大小是个重要信息,比如一般地,char 为1个字节,double 为4个字节。
本文以模仿 STL 中的 vector 类写了一个 C 语言的 vector 结构体,为了体现封装性,将 Vector 类型定义为 vector *,程序如下:
1、Vector 的接口
#ifndef vector_h__
#define vector_h__
typedef struct vector * Vector;
typedef void ** vec_iterator;
Vector vec_construct(int data_size);
void vec_destruct(Vector V);
int vec_size(Vector V);
vec_iterator vec_begin(Vector V);
vec_iterator vec_end(Vector V);
void vec_insert_n(Vector V, vec_iterator position, int n, void *pelem);
void vec_push_back(Vector V, void *pelem);
#endif // vector_h__
2、Vector 的实现
#include "vector.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <malloc.h>
#include <assert.h>
typedef struct vector vector;
typedef void * vec_value_type;
struct vector {
vec_iterator start;
vec_iterator finish;
vec_iterator end_of_storage;
int elem_size;
};
Vector vec_construct(int data_size) {
Vector V = (vector *)malloc(sizeof(vector));
if (NULL == V) {
exit(OVERFLOW);
}
V->start = NULL;
V->finish = NULL;
V->end_of_storage = NULL;
V->elem_size = data_size;
return V;
}
void vec_destruct(Vector V) {
vec_iterator ite;
for (ite = V->start; ite != V->finish; ++ite) {
free(*ite);
}
free(V->start);
free(V);
}
vec_iterator vec_begin(Vector V) {
return V->start;
}
vec_iterator vec_end(Vector V) {
return V->finish;
}
int vec_size(Vector V) {
return vec_end(V) - vec_begin(V);
}
void vec_insert_n(Vector V, vec_iterator position, int n, void *pelem) {
int old_size = 0;
int new_size = 0;
int insert_index = 0;
vec_iterator ite = NULL; vec_iterator old_finish = NULL;
if (0 == n) {
return ;
}
insert_index = position - V->start;
old_size = vec_size(V);
new_size = old_size + n;
if (V->end_of_storage - V->finish < n) {
const int new_capacity = old_size + __max(old_size, n);
vec_value_type *new_base = (vec_value_type *)realloc(V->start, new_capacity * sizeof(vec_value_type));
if (NULL == new_base) {
exit(OVERFLOW);
}
V->start = new_base;
V->end_of_storage = V->start + new_capacity;
}
V->finish = V->start + new_size;
old_finish = V->start + old_size; position = V->start + insert_index;
for (ite = old_finish + n - 1; ite >= position + n; --ite) {
assert(V->start <= ite && ite < V->finish);
assert(V->start <= ite - n && ite - n < V->finish);
*ite = *(ite - n);
}
for (; ite >= position; --ite) {
*ite = malloc(V->elem_size);
if (NULL == *ite) {
exit(OVERFLOW);
}
memcpy(*ite, pelem, V->elem_size);
}
}
void vec_push_back(Vector V, void *pelem) {
vec_insert_n(V, vec_end(V), 1, pelem);
}
3、测试程序
#include <stdio.h>
#include "vector.h"
void output_c(Vector V) {
vec_iterator iter;
for (iter = vec_begin(V); iter != vec_end(V); ++iter) {
printf("%c\n", *(char *)*iter); }
}
void output_d(Vector V) {
vec_iterator iter;
for (iter = vec_begin(V); iter != vec_end(V); ++iter) {
printf("%.2f\n", *(double *)*iter); }
}
void test1() {
char ch = 'A';
int cnt = 5;
Vector my_vec = vec_construct(sizeof(char));
while (cnt--) {
vec_push_back(my_vec, &ch);
++ch;
}
output_c(my_vec);
printf("size is %d\n", vec_size(my_vec));
vec_destruct(my_vec);
}
void test2() {
double d = 3.142;
int cnt = 13;
Vector my_vec = vec_construct(sizeof(double));
while (cnt--) {
vec_push_back(my_vec, &d);
++d;
}
output_d(my_vec);
printf("size is %d\n", vec_size(my_vec));
vec_destruct(my_vec);
}
int main(int argc, char **argv) {
test1();
printf("\n");
test2();
return 0;
}
4、运行结果
A
B
C
D
E
size is 5
3.14
4.14
5.14
6.14
7.14
8.14
9.14
10.14
11.14
12.14
13.14
14.14
15.14
size is 13
请按任意键继续. . .
注意输出时的参数,下面以字符类型解释:
printf("%c\n", *(char *)*iter);
因为元素类型为 void *,故迭代器类型为 void **,所以在输出时需注意将 void * (即 *iter 的类型)强制类型转换为 data_type *,因为对 void * 指针解引用无意义,最后再解一次引用得到想要的 data_type 输出。
还有一种方法更简明,可写成
printf("%c\n", **(char **)iter);
这里干脆把迭代器先强转为 data_type**,再两次解引用即可。
|
|
|
|