// Array.h typedef struct{ int* array; int size; }Array;
Array a; a.array = (int*)malloc(seizof(int)*init_size) //malloc 返回void*,这里做强制转换 a.size = init_size; return a; // 为什么不返回指针,因为a是本地变量,返回本地变量的指针是无效的 } // 为什么不Array* array_create(Array* a, int init_size) // 如果a==NULL?又或者a已经指向一个数组,那要先做free。 /*Array* array_create(Array* a,int init_size) { a-->size = init_size; a-->array = ... return a; } */ void array_free(Array *a) { free(a->array); // free a所指的那个array a->array = NULL; // 为了保险起见 a->size = 0; } // 使用时,例如:为什么不直接用printf("%d\n", a.size)而用printf("%d\n", array_size(&a)) // 这种做法叫封装,把a的size保护起来(这个版本比较简单,体现不出来) int array_size(cosnt Array *a) { return a->size; } int* array_at(Array *a, int index) { if (index >= a->size) { array_inflate(a, (index/BLOCK_SIZE+1)*BLOCK_SIZE-a->size); // 每次长一个BLOCK } return &(a->array[index]); // a->array[index]返回的是int } // 核心部分(数组增长) int array_inflate(Array *a, int more_size) // 其实malloc出来的东西不能长大,所以需要重新申请 { int *p = (int*)malloc(sizeof(int)*(a->size + more_size)); int i; for (i=0; isize; i++){ p[i] = a->array[i]; } free(a->array); a->array = p; a->size += more_size; }
int main(int argc, char const *argv[]) { Array a = array_create(100); printf("%d\n", array_size(&a)); *array_at(&a,0) = 10; // int* array_at返回的是指针,所以这里可以把值写进数组里头去。*(函数调用。。。。) printf("%d\n", *array_at(&a,0)); int number = 0; int cnt = 0; while(number != -1){ scanf("%d", &number); if (number != -1) *array_at(&a, cnt++) = number; } array_free(&a); return 0; }
int a; a = 3; return a; // 返回a的一个拷贝,即返回3。之后a就被销毁了。
int a[] = {1, 2}; return a; // 返回指针a的一个拷贝。假定a的地址值为0X001234FC,这个值是能够成返回的。 // 当return执行完成后,a随即被销毁,a指向的内存被回收。若此时去地址0X001234FC取值,是危险行为。3)对于静态变量
static int b = 10; return &b; // 由于静态变量是存放在静态存储区的,所以不会被系统回收,返回值有效
#include#include #include #incude using namespace std; int main() { int ia[6] = {27, 210, 12, 47, 109, 83}; // 声明一个容器,里面放int,使用分配器allocator,每次分配的内存是int。给初值。 // vector的模板参数(元素类型)必须和allocator的模板参数匹配。 vector > vi(ia, ia+6); // 容器、分配器都是模板;一般不写第二参数(默认) // not1 否定第一参数 // count_if() 大部分元素都带有begin和end,得到iterator,似C里头数组的头跟尾这两个指针。 cout << count_if(vi.begin(),vi.end(), not1(bind2nd(less (), 40))); return 0; }
3.关于复杂度,Complexity, Big-oh
在n比较大时(十万、一百万的工业级数量才会体现运行时间上的差异)。复杂度在谈容器时是免不了的,有利于选择合适的容器,提高运行效率。目前常见的Big-oh 有下列几种情形:
1)O(1)或O(c):称为常数时间(constant time)
2)O(n):称为线性时间(linear time)
3)O(log2n):称为次线性时间(sub-linear time)
4)O(n2):称为平方时间(quadratic time)
5)O(n3):称为立方时间(cubic time)
6)O(2n):称为指数时间(exponential time)
7)O(nlog2n):称为线性及二次方成长的中间之行为模式
4.关于“前闭后开”区间 [ )
一个直观的例子:begin和end 传回来的泛化指针就是前闭后开的区间。
*(c.end())指通过c调用end得到iterator(看成一种泛化指针)后解引用,得到的这一块不是容器的一部分,不确定会拿到什么,因此是危险动作。