九章算法

作者: 去年匆匆今年匆匆 | 来源:发表于2019-07-26 12:22 被阅读0次

请简述智能指针原理，并实现一个简单的智能指针。

智能指针是一种资源管理类，通过对原始指针进行封装，在资源管理对象进行析构时对指针指向的内存进行释放；通常使用引用计数方式进行管理，一个基本实现如下：
class Object;
class SmartPointer;
 
class Counter
{
 friend class SmartPointer;
public:
 Counter()
 {
  ptr = NULL;
  cnt = 0;
 }
 Counter(Object* p)
 {
  ptr = p;
  cnt = 1;
 }
 ~Counter()
 {
  delete ptr;
 }
private:
 Object* ptr;
 int cnt;
};
 
class SmartPointer
{
public:
 SmartPointer(Object* p)
 {
  ptr_counter = new Counter(p);
 }
 SmartPointer(const SmartPointer &sp)
 {
  ptr_counter = sp.ptr_counter;
  ++ptr_count->cnt;
 }
 SmartPointer& operator=(const SmartPointer &sp)
 {
  ++sp.ptr_counter->cnt;
  --ptr_counter->cnt;
  if (ptr_counter->cnt == 0)
  {
   delete ptr_counter;
  }
  ptr_counter = sp.ptr_counter;
 }
 ~SmartPointer()
 {
  --ptr_counter->cnt;
  if (ptr_counter->cnt == 0)
  {
   delete ptr_counter;
  }
 }
private:
 Counter* ptr_counter;
 
};

如何处理循环引用问题？

刚刚研究过这个问题。
何为循环引用
如果有两个或者以上的对象，它们彼此引用，就会造成循环引用。如下面的例子

class Node { 

    Node next ;

} 

Node a = new Node (); 

Node b = new Node (); 

a . next = b ; 

b . next = a ; 

代码中，a对象引用了b对象，b对象也引用了a对象，这种情况下a对象和b对象就形成了循环引用。

## 引用计数GC处理

### 什么是引用计数

引用计数是一种垃圾回收的形式，每一个对象都会有一个计数来记录有多少指向它的引用。其引用计数会变换如下面的场景

*   当对象增加一个引用，比如赋值给变量，属性或者传入一个方法，引用计数执行加1运算。
*   当对象减少一个引用，比如变量离开作用域，属性被赋值为另一个对象引用，属性所在的对象被回收或者之前传入参数的方法返回，引用计数执行减1操作。
*   当引用计数变为0，代表该对象不被引用，可以标记成垃圾进行回收。

### 如何处理

实际上单纯的基于引用计数实现的计数器无法处理循环引用带来的问题。

CPython的垃圾回收就是采用引用计数,采用引用计数的主垃圾回收器会清理垃圾，对于那些因为循环引用无法清理的对象，CPython会不时启动一个辅助的基于引用遍历的垃圾回收器来清理它们。

## 引用遍历GC处理

### 什么是引用对象遍历

垃圾回收器从被称为GC Roots的点开始遍历遍历对象，凡是可以达到的点都会标记为存活，堆中不可到达的对象都会标记成垃圾，然后被清理掉。 GC Roots有哪些

*   类，由系统类加载器加载的类。这些类从不会被卸载，它们可以通过静态属性的方式持有对象的引用。注意，一般情况下由自定义的类加载器加载的类不能成为GC Roots
*   线程，存活的线程
*   Java方法[栈](http://droidyue.com/blog/2014/12/07/differences-between-stack-and-heap-in-java/)中的局部变量或者参数
*   [JNI方法栈](http://droidyue.com/blog/2014/12/21/java-runtime-data-areas/)中的局部变量或者参数
*   JNI全局引用
*   用做同步监控的对象
*   被JVM持有的对象，这些对象由于特殊的目的不被GC回收。这些对象可能是系统的类加载器，一些重要的异常处理类，一些为处理异常预留的对象，以及一些正在执行类加载的自定义的类加载器。但是具体有哪些前面提到的对象依赖于具体的JVM实现。

### 如何处理

基于引用对象遍历的垃圾回收器可以处理循环引用，只要是涉及到的对象不能从GC Roots[强引用](http://droidyue.com/blog/2014/10/12/understanding-weakreference-in-java/)可到达，垃圾回收器都会进行清理来释放内存。

## 总结

基于引用计数的垃圾回收器无法处理循环引用导致的内存泄露问题，但是其在主流的JVM中很少，几乎所有的JVM都是采用引用对象遍历的方法，垃圾回收器都会处理循环引用潜在的问题。

具体可以参考这里的文章 [http://droidyue.com/blog/2015/06/05/how-garbage-collector-handles-circular-references/](http://droidyue.com/blog/2015/06/05/how-garbage-collector-handles-circular-references/)

请实现一个单例模式的类，要求线程安全

在C++之后，下面的实现是个线程安全的单例模式实现：
class Lock
{
private:      
    CCriticalSection m_cs;
public:
    Lock(CCriticalSection  cs) : m_cs(cs)
    {
        m_cs.Lock();
    }
    ~Lock()
    {
        m_cs.Unlock();
    }
};
 
class Singleton
{
private:
    Singleton();
    Singleton(const Singleton &);
    Singleton& operator = (const Singleton &);
 
public:
    static Singleton *Instantialize();
    static Singleton *pInstance;
    static CCriticalSection cs;
};
 
Singleton* Singleton::pInstance = 0;
 
Singleton* Singleton::Instantialize()
{
    if(pInstance == NULL)
    {   //double check
        Lock lock(cs);           //用lock实现线程安全，用资源管理类，实现异常安全
        //使用资源管理类，在抛出异常的时候，资源管理类对象会被析构，析构总是发生的无论是因为异常抛出还是语句块结束。
        if(pInstance == NULL)
        {
            pInstance = new Singleton();
        }
    }
    return pInstance;
}
 
/*class Singleton
{
private: static Singleton* instance;  Singleton();
 Singleton(const Singleton &s);
 Singleton& operator=(const Singleton &s);
public:
 static Singleton* GetInstance()
 {
  static Singleton instance;
  return &instance;
 }
};*/

如何定义一个只能在堆上（栈上）生成对象的类?

   在C++中，类的对象建立分为两种，一种是静态建立，如A a；另一种是动态建立，如A* ptr=new A；这两种方式是有区别的。

        静态建立一个类对象，是由编译器为对象在栈空间中分配内存，是通过直接移动栈顶指针，挪出适当的空间，然后在这片内存空间上调用构造函数形成一个栈对象。使用这种方法，直接调用类的构造函数。

        动态建立类对象，是使用new运算符将对象建立在堆空间中。这个过程分为两步，第一步是执行operator new()函数，在堆空间中搜索合适的内存并进行分配；第二步是调用构造函数构造对象，初始化这片内存空间。这种方法，间接调用类的构造函数。

        那么如何限制类对象只能在堆或者栈上建立呢？下面分别进行讨论。

1、只能建立在堆上

        类对象只能建立在堆上，就是不能静态建立类对象，即不能直接调用类的构造函数。

        容易想到将构造函数设为私有。在构造函数私有之后，无法在类外部调用构造函数来构造类对象，只能使用new运算符来建立对象。然而，前面已经说过，new运算符的执行过程分为两步，C++提供new运算符的重载，其实是只允许重载operator new()函数，而operator()函数用于分配内存，无法提供构造功能。因此，这种方法不可以。

        当对象建立在栈上面时，是由编译器分配内存空间的，调用构造函数来构造栈对象。当对象使用完后，编译器会调用析构函数来释放栈对象所占的空间。编译器管理了对象的整个生命周期。如果编译器无法调用类的析构函数，情况会是怎样的呢？比如，类的析构函数是私有的，编译器无法调用析构函数来释放内存。所以，编译器在为类对象分配栈空间时，会先检查类的析构函数的访问性，其实不光是析构函数，只要是非静态的函数，编译器都会进行检查。如果类的析构函数是私有的，则编译器不会在栈空间上为类对象分配内存。

        因此，将析构函数设为私有，类对象就无法建立在栈上了。代码如下：

**[cpp]**

1.  class  A  
2.  {  
3.  public :  
4.  A(){}  
5.  void  destory(){ delete   this ;}  
6.  private :  
7.  ~A(){}  
8.  };  

        试着使用A a;来建立对象，编译报错，提示析构函数无法访问。这样就只能使用new操作符来建立对象，构造函数是公有的，可以直接调用。类中必须提供一个destory函数，来进行内存空间的释放。类对象使用完成后，必须调用destory函数。

        上述方法的一个缺点就是，无法解决继承问题。如果A作为其它类的基类，则析构函数通常要设为virtual，然后在子类重写，以实现多态。因此析构函数不能设为private。还好C++提供了第三种访问控制，protected。将析构函数设为protected可以有效解决这个问题，类外无法访问protected成员，子类则可以访问。

        另一个问题是，类的使用很不方便，使用new建立对象，却使用destory函数释放对象，而不是使用delete。（使用delete会报错，因为delete对象的指针，会调用对象的析构函数，而析构函数类外不可访问）这种使用方式比较怪异。为了统一，可以将构造函数设为protected，然后提供一个public的static函数来完成构造，这样不使用new，而是使用一个函数来构造，使用一个函数来析构。代码如下，类似于单例模式：

**[cpp]** 

1.  class  A  
2.  {  
3.  protected :  
4.  A(){}  
5.  ~A(){}  
6.  public :  
7.  static  A* create()  
8.  {  
9.  return   new  A();  
10.  }  
11.  void  destory()  
12.  {  
13.  delete   this ;  
14.  }  
15.  };  

        这样，调用create()函数在堆上创建类A对象，调用destory()函数释放内存。

2、只能建立在栈上

        只有使用new运算符，对象才会建立在堆上，因此，只要禁用new运算符就可以实现类对象只能建立在栈上。将operator new()设为私有即可。代码如下：

**[cpp]** 

1.  class  A  
2.  {  
3.  private :  
4.  void * operator  new ( size_t  t){}      // 注意函数的第一个参数和返回值都是固定的   
5.  void  operator  delete ( void * ptr){}  // 重载了new就需要重载delete   
6.  public :  
7.  A(){}  
8.  ~A(){}  
9.  };

下面的结构体大小分别是多大（假设32位机器）？

struct A {
char a;
char b;
char c;
};

struct B {
int a;
char b;
short c;
};

struct C {
char b;
int a;
short c;
};

pragma pack(2)

struct D {
char b;
int a;
short c;
};

结构体的大小问题在求解的时候要注意对齐：

A：对齐值为：1 。大小为：3

B：对齐值为：4 。 大小为：4+4 = 8（第一个4为int，第二个4为char 和 short ，要空余1个）

C：对齐值为：4。大小为：4+4+4 = 12（第一个为char ，空余3个，第二个为int ，第三个为char 空余3个）

D：指定对齐值为：2（使用了#pragma pack(2)） 。大小为2+4+2 = 8。（第一个char，空余1个，第二个为int ，4个，第3个位char，空余1个）。

引用和指针有什么区别？

本质：引用是别名，指针是地址，具体的： 
• 指针可以在运行时改变其所指向的值，引用一旦和某个对象绑定就不再改变 
• 从内存上看，指针会分配内存区域，而引用不会，它仅仅是一个别名 
• 在参数传递时，引⽤用会做类型检查，而指针不会 
• 引用不能为空，指针可以为空

const和define有什么区别？

本质：define只是字符串替换，const参与编译运行，具体的： 
• define不会做类型检查，const拥有类型，会执行相应的类型检查 
• define仅仅是宏替换，不占⽤用内存，⽽而const会占用内存 
• const内存效率更高，编译器通常将const变量保存在符号表中，而不会分配存储空间，这使得它成 为一个编译期间的常量，没有存储和读取的操作

define和inline有什么区别？

本质：define只是字符串替换，inline由编译器控制，具体的： 
• define只是简单的宏替换，通常会产生二义性；而inline会真正地编译到代码中 
• inline函数是否展开由编译器决定，有时候当函数太大时，编译器可能选择不展开相应的函数

malloc和new有什么区别？

1,malloc与free是C++/C语言的标准库函数，new/delete是C++的运算符。它们都可用于申请动态内存和释放内存。
2,对于非内部数据类型的对象而言，光用maloc/free无法满足动态对象的要求。对象在创建的同时要自动执行构造函数，对象在消亡之前要自动执行析构函数。由于malloc/free是库函数而不是运算符，不在编译器控制权限之内，不能够把执行构造函数和析构函数的任务强加于malloc/free。 
3,因此C++语言需要一个能完成动态内存分配和初始化工作的运算符new，以一个能完成清理与释放内存工作的运算符delete。注意new/delete不是库函数。
4,C++程序经常要调用C函数，而C程序只能用malloc/free管理动态内存。

5、new可以认为是malloc加构造函数的执行。new出来的指针是直接带类型信息的。而malloc返回的都是void指针。

C++中static关键字作用有哪些？

1、隐藏：当同时编译多个文件时，所有未加static前缀的全局变量和函数都具有全局可见性。
static可以用作函数和变量的前缀，对于函数来讲，static的作用仅限于隐藏.
2、static的第二个作用是保持变量内容的持久：存储在静态数据区的变量会在程序刚开始运行时就完成初始化，也是唯一的一次初始化。
共有两种变量存储在静态存储区：全局变量和static变量，只不过和全局变量比起来，static可以控制变量的可见范围，
说到底static还是用来隐藏的。虽然这种用法不常见
3、static的第三个作用是默认初始化为0（static变量）
4、C++中的作用
1）不能将静态成员函数定义为虚函数。   
2）静态数据成员是静态存储的，所以必须对它进行初始化。 （程序员手动初始化，否则编译时一般不会报错，但是在Link时会报错误）  
3）静态数据成员在<定义或说明>时前面加关键字static。

C++中const关键字作用有哪些？?

• 修饰变量 
• 修饰成员函数，表示该成员函数不会修改成员变量

C++中成员函数能够同时用static和const进行修饰？

否，因为static表⽰示该函数为静态成员函数，为类所有；而const是用于修饰成员函数的，两者相矛盾

下面三个变量分别代表什么含义？

const int* ptr;
int const* ptr;
int* const ptr;

前两个代表指向const变量的指针，即指针所指向的对象是const的，不能使用指针修改；最后一个代表const指针，即指针本身是const的，不能指向其他地址

C++中包含哪几种强制类型转换？他们有什么区别和联系？

• reinterpret_cast: 转换一个指针为其它类型的指针。它也允许从一个指针转换为整数类型,反之亦 然. 这个操作符能够在非相关的类型之间转换. 操作结果只是简单的从一个指针到别的指针的值的 二进制拷贝. 在类型之间指向的内容不做任何类型的检查和转换? 
class A{}; 
class B{}; 
A* a = new A;
B* b = reinterpret_cast(a); 
• static_cast: 允许执行任意的隐式转换和相反转换动作（即使它是不允许隐式的）,例如：应用到类 的指针上, 意思是说它允许子类类型的指针转换为父类类型的指针(这是一个有效的隐式转换), 同 时, 也能够执行相反动作: 转换父类为它的子类 
class Base {}; 
class Derive:public Base{}; 
Base* a = new Base; 
Derive *b = static_cast(a); 
• dynamic_cast: 只用于对象的指针和引用. 当用于多态类型时，它允许任意的隐式类型转换以及相 反过程. 不过，与static_cast不同，在后一种情况里（注：即隐式转换的相反过程）,dynamic_cast 会检查操作是否有效. 也就是说, 它会检查转换是否会返回一个被请求的有效的完整对象。检测在 运行时进行. 如果被转换的指针不是一个被请求的有效完整的对象指针，返回值为NULL. 对于引用 类型，会抛出bad_cast异常 
• const_cast: 这个转换类型操纵传递对象的const属性，或者是设置或者是移除,例如： 
class C{}; 
const C* a = new C; 
C *b = const_cast(a);

下面两段代码的输出分别是什么？
class Base{
public:
virtual void Print() const{
cout << "Print in Base" << endl;
}
};
class Derive::public base
{
public:
void Print() const{
cout << "Print in Derive" << endl;
}
};
void Print(const Base* base){
base->Print();
}
int main(){
Base b;
Derive d;
print(&b);
print(&d);
return 0;
}
class Base{
public:
void Print() const{
cout << "Print in Base" << endl;
}
};
class Derive::public base
{
public:
void Print() const{
cout << "Print in Derive" << endl;
}
};
void Print(const Base* base){
base->Print();
}
int main(){
Base b;
Derive d;
print(&b);
print(&d);
return 0;
}

考察对虚函数的基本理解 
第一个：Print in Base, Print in Derive 
第二哥：Print in Base, Print in Base

简述C++虚函数作用及底层实现原理

要点是要答出虚函数表和虚函数表指针的作用。C++中虚函数使用虚函数表和 虚函数表指针实现，虚函数表是一个类的虚函数的地址表，用于索引类本身以及父类的虚函数的地 址，假如子类的虚函数重写了父类的虚函数，则对应在虚函数表中会把对应的虚函数替换为子类的 虚函数的地址；虚函数表指针存在于每个对象中（通常出于效率考虑，会放在对象的开始地址处）， 它指向对象所在类的虚函数表的地址；在多继承环境下，会存在多个虚函数表指针，分别指向对应 不同基类的虚函数表。

一个对象访问普通成员函数和虚函数哪个更快？

访问普通成员函数更快，因为普通成员函数的地址在编译阶段就已确定，因此在访问时直接调 用对应地址的函数，而虚函数在调用时，需要首先在虚函数表中寻找虚函数所在地址，因此相比普 通成员函数速度要慢一些

在什么情况下，析构函数需要是虚函数？

若存在类继承关系并且析构函数中需要析构某些资源时，析构函数需要是虚函数，否则当使用父类指针指向子类对象，在delete时只会调用父类的析构函数，而不能调用子类的析构函数，造成内存泄露等问题

内联函数、构造函数、静态成员函数可以是虚函数吗？

都不可以。内联函数需要在编译阶段展开，而虚函数是运行时动态绑定的，编译时无法展开； 构造函数在进行调用时还不存在父类和子类的概念，父类只会调用父类的构造函数，子类调用子类 的，因此不存在动态绑定的概念；静态成员函数是以类为单位的函数，与具体对象无关，虚函数是 与对象动态绑定的，因此是两个不冲突的概念；

构造函数中可以调用虚函数吗？

可以，但是没有动态绑定的效果，父类构造函数中调用的仍然是父类版本的函数，子类中调用的仍然是子类版本的函数

简述C++中虚继承的作用及底层实现原理?

虚继承用于解决多继承条件下的菱形继承问题，底层实现原理与编译器相关，一般通过虚基类 指针实现，即各对象中只保存一份父类的对象，多继承时通过虚基类指针引用该公共对象，从而避 免菱形继承中的二义性问题。