分类 - C++

2017-03-28 15:20:22    71    0    0

对象

 1、使用类进行封装的成本

相对于C语言来说,C++的类的封装对普通的数据成员和非内联函数并没有增加什么成本,

非内联函数虽然都是在类的内部声明,但是其实现却是在类外并且只有一个实体

内联函数只会在类的使用者(类对象)产生实际的实体

C++真正会增加成本的是对于虚函数和虚基类的实现上。

简单对象模型

        简单对象模型的概念就是对象的所有的数据成员和成员函数都不是直接的存储在对象的内部,为所有的对象的成员每个人都分配了一个插槽,存储自己的指针,

这样的话通过插槽的下标即可找到相应的对象的成员(数据成员或者是成员函数)。

\"\"    


表格驱动对象模型

        简单对象模型的不足之处就是在实际的运作中没有办法提供统一的操作手段,因为不同的插槽可能是函数或者数据成员,

表格驱动对象模型就是解决这个问题:把所有的数据成员存储在一个表格中,所有的成员函数存储在一个表格中,在对象的内部只存储指向这两个表格的指针即可。

存储数据的表格直接存储数据,存储函数的表格存储指向函数的指针。

\"\"

 

C++的对象模型

C++的对象模型是对简单对象模型的升级:

在C++的对象模型中

1、把所有的非静态数据成员都直接的放在对象的内部

2、把静态数据成员和所有的静态和非静态成员函数都放在对象的外部

3、针对所有的虚函数,类会生成一堆指向这些函数的指针存放在一张表中,叫做vtbl

     每个对象内部生成一个vptr指向格子的vtbl,vptr的创建和修改都是由类构造和析构函数来执行。

\"\"

在虚拟继承场景下的对象模型的两种讨论

在虚拟继承下,每个派生类都只含有基类的一个实体,那么在在派生类中如何找到或者是定位他自己的基类

第一种:

       如果是简单对象模型中,只需要在对象的一个插槽中存储其基类的地址即可

第二种:

        就是virtual base class table 的概念,对每个对象来说,该表创建时每个插槽就保存有其基类的地址,然后在对象的内部添加一个指向该表的指针

关于C++的继承模型,后继有讨论

 

对象模型是如何影响程序的

    我的理解,通过上面的几种不同的对象模型可以看出,不同的对象模型,会导致我们实例化一个对象以及在后继的开发过程中通过该对象对函数的调动,对数据成员的修改

都会有不同的操作过程,尽管可能从表面的操作上看没有什么不同。

 

关键词所带来的差异

1、struct关键词在C++中和class并没有什么

2017-03-28 15:20:22    385    0    0

基础

1、对象的定义就是为对象命名并且说明他的类型

2、对象的初始化就是在定义的时候顺便给一个初始的值。

    对象的初始化可以是直接使用赋值等号(=),或者是直接使用构造函数 int  a(3);

3、const 类型的对象必须在定义的时候进行初始化因为其他任何时间你都无法再次的修改他的值。

4、模运算的经常运用的地方就是当我们希望限制一个范围不超过多少的时候,就可以使用

5、条件表达式 a = (result)? A:B 结果取决于result的真假,为真时A为假时是B。

6、复合赋值表达式 a +=2,这种

7、递增递减运算符,需要注意的是放置的位置(前后)对变量当前数值的影响

8、逻辑运算符,以及他们之间的组合

9、运算符之间的优先级

10、条件、循环语句

11、数组和向量

数组的使用就是在定义开始的时候我们需要制定一个数组的名称以及存储于数组中的数据的类型,以及数组的大小,int  a[10]像这样。

我们可以通过数组元素的下标直接的使用相对应位置上的元素。

向量是另外一种和数组相似的存储的结构,下面整理向量的相关的使用方法和知识点。

1、使用前必须要包含头文件:#include <vector>

2、定义: vector<类型>名称(大小) 举例:  vector<int> test(10),这样便是定义了一个用于存储int类型数值的长度为10 的一个向量的存储的结构。

3、使用方法:

3.1、随机位置插入,test.insert(位置,插入的数据),需要注意的是,insert使用的前插法,就是找到具体的位置,在该位置的前面插入相应的数据。

3.2、尾插法:test.push_back(插入的数据)

3.3、删除:test.clear(),删除整个的向量

3.4、有范围删除:test.erase(开始位置,起始位置)

3.5、向量的大小:test.size()返回该向量的大小

3.6、使用迭代器进行遍历:

vector<int>::iterator it

for(it=test.begin();it!=test.end();it++)

{

    ///

}

3.7、使用下标直接的访问相应位置上的数据

比较:

相同点:

1、都是使用连续的存储空间存储数据

2、在开始的定义的时候都必须事先声明好要存储的数据的对象。

3、都可以使用下标对相应位置上的数据的元素进行提领。

不同点:

1、数组的长度是固定的,但是向量不一样,向量可以

2017-03-29 16:30:36    318    0    0

下面的内容是我从网上摘抄的;

一个HASH的结果所对应的地址可存放两个BUCKET。可解决HASH冲突。 

  • 要存数据时,第一次HASH到这里,在第一个BUCKET存放一个数据。 
  • 要存数据时,当第二次因某些原因HASH到这里时,在第二个BUCKET存放另一个数据。  

一个由5个buckets组成的哈希表,里面有7个元素:

linux的hash函数hash_long等,用了golden ratio来计算。因为桶(bits)的数量需要由hash函数和对冲突的期望来决定,那么对于hash_long这样的hash函数,我们怎么确定桶的数量呢? 

一般情况下都是自己根据数据特性来考虑使用的 hash 算法,不是千篇一律咬死一个不放。

比如存放 IP 地址的 hash table,用一个 65536 的桶就很好,把 IP 的后 16bit 作为 key。这种方法绝对比 hash_long、jhash 等函数的碰撞率低。 

其实就是这个界和性能的折中。我可以取我问题空间的最大值。这样肯定能保证键值分散。但是这样会浪费很多空间。然而取得太小,又影响查找效率。感觉还是要在试验中进行测试。而且个人觉得,hash比其他搜索的数据结构灵活的地方就是它的可定制性。可以根据具体情况调整,以达到最优的效果。

 

大致的思路是这样的:


首先哈希桶的个数是固定的,有用户构建的时候输入,一旦构建,个数就已经固定;查找的时候首先将key值通过哈希函数获取哈希值,根据哈希值获取到对应的哈希桶,然后遍历哈希桶内的pairs数组获取;

这两种实现方法看似比较类似,但也有差异:

基于哈希桶的情况下,由于Hash桶容量的限制,所以,有可能发生Hash表填不满的情况,也就是,虽然Hash表里面还有空位,但是新建的表项由于冲突过多,而不能装入Hash表中。不过,这样的实现也有其好处,就是查表的最大开销是可以确定的,因为最多处理的冲突数是确定的,所以算法的时间复杂度为O(1)+O(m),其中m为Hash桶容量。

而另一种通过链表的实现,由于Hash桶的容量是无限的,因此,只要没有超出Hash表的最大容量,就能够容纳新建的表项。但是,一旦发生了Hash冲突严重的情况,就会造成Hash桶的链表过长,大大降低查找效率。在最坏的情况下,时间复杂度退化为O(n),其中n为Hash表的总容量。当然,这种情况的概率小之又小,几乎是可以忽略的。


我的理解:

工作中