signed

QiShunwang

“诚信为本、客户至上”

【四】面向对象程序设计

2020/12/30 10:03:30   来源:

1.c++中map底层实现,红黑树说一下?

  1. 红黑树形式的存储的键值是有序的,同时红黑树的插入,删除可以在O(logn)的完成。
  2. 红黑树的性质
  • 红黑树的每个节点要么是红色要么是黑色
  • 红黑树的根节点一定是黑色
  • 红黑树的所有外部节点都是黑色
  • 红黑树的所有有红色节点的两个子节点一定是黑色节点
  • 红黑树从根到任意一个外部节点的路径上的黑色节点的数目相同

2.说到map,也说说hashmap和Treemap

  1. C++中unordered_map的底层是用哈希表来实现的,通过key的哈希路由到每一个桶(即数组)用来存放内容。
  2. 通过key来获取value的时间复杂度就是O(1)。
  3. 因为key的哈希容易碰撞,所以需要对碰撞做处理。
  4. unordered_map里的每一个数组(桶)里面存的其实是一个链表,key的哈希冲突以后会加到链表的尾部,这是再通过key获取value的时间复杂度就变成O(n),当碰撞很多的时候查询就会变慢。
  5. 为了优化这个时间复杂度,map的底层就把这个链表转换成了红黑树,这样虽然插入增加了复杂度,但提高了频繁哈希碰撞时的查询效率,使查询效率变成O(log n)。

3.对多态的理解?(重要)

  1. 多态分为静态(编译:函数重载+运算符重载)和动态(运行:类继承关系+虚函数)。
  2. 虚函数通过派生实现运行时的多态。运行时,用指针定位到指向哪个对象,然后调用相应的函数体,虚函数属于对象,不属于类的函数。类外实现函数体,不能写成内联。
  3. 纯虚函数不能定义对象,只能做基类。基类中不定义具体操作的内容,要求派生类按需定义自己的版本,没有函数体,只是作为同一接口方便调用。
  4. 多态实现的三个条件:
  • a继承:抽象类不能实例化,需要通过派生类实现具体功能。
  • b虚函数重写:子类中实现,解决不同层次的类中同名函数的关系问题。
  • c赋值兼容规则:临时存储通过c++链表,父类指针指向子类对象。

4.指针的作用和应用场景

  1. 作用:(1)传较大的数据作参数(2)传入数组对数组做操作(3)函数返回不止一个结果(4)动态申请内存
  2. 应用场景:
  • 交换两个变量的值void swap(int *pa,int *pb)调用swap(&a,&b)
  • 函数返回多个值,某些值只能通过指针返回(把结果带出来min,max)
  • 函数返回运算的状态,结果通过指针返回(divide(int a,int b,int *result))

5.继承和多态

  1. 继承:在原有类特性的基础上进行扩展,增加功能。
  2. 多态:编译时多态(函数及运算符的重载)、运行时多态(以虚函数为基础的多态性,在不同层次的类中同名函数的关系问题)

6.初始化列表

  1. Eg:initialization初始化  student::student(string s):name(s){}构造函数前执行
  2. Eg:assignment通过构造函数初始化赋值 student::student(string s){name=s;}默认已经构造,多一次构造,然后赋值,必须有析构函数

7.代码重用/软件重用方式

  1. 对象组合(实体):拿已有对象拼装出新的对象(car:typr+foor)
  2. 继承(虚):对已有类进行改造(扩充)得到新的类(inheritance)

8.迭代器

  1. 表现和功能像指针,是封装了指针的类对象,可以是所需的任意类型。
  2. 用于访问容器中的部分和全部元素。
  3. 实现了容器和算法的分离。每个容器都有自己的迭代器,容器通过迭代器共享某一具体算法,算法不依赖于某一具体迭代器,只起一个中间媒介作用,算法通过迭代器访问容器中的元素。
  4. 迭代器返回的是对象引用而不是对象的值。
  5. 迭代器指向容器而指针指向函数。

9.函数对象

  1. 重载了operator()类的一个实例,operator()是函数调用运算符,本质是一个类而不是一个函数,行为类似函数调用。
  2. 通过函数对象可以对容器中的元素进行各种各样的操作。
  3. 函数对象有自己的状态,可以在类中定义这个状态,一个函数对象在多次调用中可以共享这个状态并维护自己的状态。
  4. 函数对象有自己特有的类型,可以传递相应的类型作为参数来实例化相应的模板。

 (欢迎您的意见和建议,感谢支持!!!❤❤❤)