频道栏目
首页 > 资讯 > 其他 > 正文

Boolan STL与泛型编程

18-02-12        来源:[db:作者]  
收藏   我要投稿

补充知识

1.链表、树和hash表(待补充)
散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
链表
2. 数组是固定大小的。怎么用C语言设计一个大小可以变化的数组?
Think about a set of functions that provide a mechanism of resizable array of int.
Growable
Get the current size
Access to the elements
为了实现上面的构想,我们可以提供一个函数库:
Array array_create(int init_size);
void array_free(Array *a);
int array_size(const Array *a);
int* array_at(Array *a, int index);
void array_inflate(Array *a, int more_size)
// 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;
}
3.Issues:2中构建的可变数组的缺陷
Allocate new memory each time it inates is an easy and clean way. But
It takes time to copy, and
may fail in memory restricted situation
链表能够解决3中讨论的问题。
4.为什么不能返回本地指针变量,却可以返回本地变量?
函数局部变量用作返回值时,会生成一个局部变量的拷贝用作返回值,之后局部变量会被系统回收。如果返回局部变量的地址,系统回收后,指针指向的内容就无意义了。静态变量也可以返回其指针。
1)返回一个基本类型的变量
int a;
a = 3;
return a;
// 返回a的一个拷贝,即返回3。之后a就被销毁了。
2)返回本地变量的指针
int a[] = {1, 2};
return a;
// 返回指针a的一个拷贝。假定a的地址值为0X001234FC,这个值是能够成返回的。
// 当return执行完成后,a随即被销毁,a指向的内存被回收。若此时去地址0X001234FC取值,是危险行为。
3)对于静态变量
static int b = 10;
return &b;
// 由于静态变量是存放在静态存储区的,所以不会被系统回收,返回值有效

本周基础知识(C++标准库——体系结构与内核分析)

关于C++标准库的学习,由浅到深可以分为这样四个阶段:
1)浅谈C++标准库:简单地使用
2)深入认识C++标准库:学习C++标准库的结构
3)良好使用C++标准库:知道整个体系结构后才能良好地使用
4)扩充C++标准库:通常必要性不是很大
1. C++ Standard Library vs. Standard Template Library
C++ Standard Library (C++ 标准库): 标准库以header files 的形式呈现。
Standard Template Library (STL, 标准库模板): 占据标准库的绝大部分,包含六大部件。
C++ 标准库的 header files 不带副档名 .h,例如 #include
新式 C header files 不带副档名 .h,例如 #include
旧式 C header files带有副档名 .h,仍然可用,例如 #include
旧式headers 内的组件不封装于namespace “std”,而新式 headers 内的组件封装于 namespace ”std”。
在不同的编译器,标准库的用法几乎是一样的,只有小部分细微的差别。一些关于标准库的重要网页:
CPlusPlus.com; CppReference.com; gcc.gnu.org
2.STL六大部件
容器(Containers)分配器(Allocators)算法(Algorithms)迭代器(Iterators)适配器(Adapters)放函数(Functors)算法和容器是六大主件重最重要的两个部分。容器就是数据结构,容器把内存的东西帮我们解决,所以背后要分配器的支持。要对容器的元素进行操作,有的时候可以调用类的成员函数,有时候却要独立出来,这部分就是算法(如search等)。注意到这里的设计理念跟OO不一样,之前鼓励的是将数据和处理数据的函数放在类里面,而结构里面的容器和算法是分开的。

例程(将上面C++标准库中所有的组件都应用上):
#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(看成一种泛化指针)后解引用,得到的这一块不是容器的一部分,不确定会拿到什么,因此是危险动作。

使用容器(C++标准库——体系结构与内核分析)

1.容器——结构与分类
容器大概分为两类:Sequence Containers序列式+ Associative Containers关联式
容器的结构与分类详见下面的图:

注意:C++有内置数组(C语言原生数组),C++把数组变成一个类。

相关TAG标签
上一篇:Spring集成Shiro
下一篇:根据阿里云的OSS服务上传图片
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站