九章算法答案(上)

一

1. 实现一个memcpy函数。

//memcpy需要考虑内存重叠问题,memmove不需要考虑
void* memcpy(const void* src,void* dst,size_t size)
{
    assert(src!=NULL && dst!=NULL);
    if(size==0)
        return src;
    char* tmp=src;
    if(dst<=src || (char*)dst>((char*)src+size))//from left to right
    {
        while(size--)
        {
            *(char*)dst++=*(char*)src++;
        }
    }
    else//from right to left
    {
        src+=size-1;
        dst+=size-1;
        while(size--)
        {
            *(char*)dst--=*(char*)src--;
        }
    }
    return (void*)tmp;
}

2. STL中vector的实现原理（衍生：Map/Set的实现原理）

vector即一个对象，含有start,end和finish成员变量，这三个成员变量共同管理着一个堆上的数组空间。start指向数组头，end指向有效元素的尾部，finish指向整个空间的尾部。可以向其中插入，删除，移动元素等。插入时，如果有足够的空余空间，则予以插入；否则开辟一块新的空间(长度是原来2倍)，将所有元素移动过去，将以上三个指针指向新的空间并释放原有空间，然后再插入元素即可。

3. 给定N张扑克牌和一个随机函数，设计一个洗牌算法。

假设扑克牌有54张，存放在card数组中。我们要保证的是每张扑克牌被洗过一次后不会被再次洗牌。所以我们可以使变量i从1循环到54，每次从第i张牌到第54张牌中选取一张，与第i张交换。

代码如下：

void shuffle(int card[],size_t n)
{
    srand(time(NULL));//初始化随机数种子
    int i;
    int other;//另一张牌
    for(i=0;i<n;++i)
    {
        other=i+rand()%(n-i);
        std::swap(card[i],card[other]);
    }
}

4. 25匹马，5个跑道，最少比多少次能比出前3名？前5名？

先看选出前3的算法：
组别 第一名 第二名 第三名 第四名 第五名
A组 A1 A2 A3 A4 A5
B组 B1 B2 B3 B4 B5
C组 C1 C2 C3 C4 C5
D组 D1 D2 D3 D4 D5
E组 E1 E2 E3 E4 E5

此时A1为所有马中的第一名。同时，红色标注的马被淘汰，因为只能选出3匹，但他们明显进不了前三。

可以看出，选出前3匹马至少需要7场比赛。

选出前5的算法：
组别 第一名 第二名 第三名 第四名 第五名
A组 A1 A2 A3 A4 A5
B组 B1 B2 B3 B4 B5
C组 C1 C2 C3 C4 C5
D组 D1 D2 D3 D4 D5
E组 E1 E2 E3 E4 E5

此时A1为所有马中的第一名。同时，红色标注的马被淘汰，因为只能选出5匹，但他们明显进不了前五。

5.进程和线程有什么区别？

另一种答案：

进程和线程具有很多类似的性质，因此人们称线程为轻量级进程，也是CPU调度和分派的基本单元；而传统意义上的进程称为重量级进程，从现代的角度看，它就是指拥有一个线程的进程。如果进程有多个控制线程，它就能同时执行多个任务(并发/并行)。

下面主要从调度、并发性、系统开销、拥有资源等方面对进程和线程进行比较。

调度：在传统的操作系统中，CPU调度和分派的基本单位是进程。而在引入线程的系统中，则把线程作为CPU调度和分派的基本单位，进程则作为资源拥有的基本单位，从而使传统进程的两个属性分开，线程便能够轻装运行，这样可以显著地提高系统的并发性。同一进程中线程切换不会引起进程切换，从而避免了昂贵的系统调用开销。但是在由一个进程中的线程切换到另一个进程中的线程时，依然会引起进程切换。

并发性：在引入线程的操作系统中，不仅进程间可以并发执行，而且在一个进程中的多个线程之间也可以并发送执行，因而使操作系统具有更好的并发性，从而能够有效地使用系统资源和提高系统的吞吐量。例如一个未引入线程的单CPU系统中，若仅设置一个文件服务进程，当它由于某种原因被封锁时，便没有其他文件服务进程来提供服务。在引入线程的系统中，可以在一个文件服务系统中设置多个服务线程。当第一个线程等待是，文件服务进程中第二个线程可以继续运行；当第二个被封锁时，第三个可以继续执行，从而显著提高了文件服务的质量以及系统的吞吐量。

体统开销：不论是引入线程的操作系统，还是传统的操作系统，进程都是拥有系统资源的一个独立单位。一般地说，线程自己不拥有系统资源(也有一点必不可少的资源)，但它可以穿访问所隶属进程的资源。亦即一个进程的代码段、数据段以及系统资源(如打开的文件，I/O设备等)，可供同一进程的所有其他线程共享。

拥有资源：由于在创建或撤销进程时，系统都要为之分配或回收资源，如内存空间，I/O设备等。因此操作系统所付出的开销将显著大于在创建线程时的开销。类似地，在进行进程切换时，涉及到整个当前进程CPU环境的保存以及新调度进程CPU环境的加载。而线程切换时只需要保存和设置少量寄存器的内容，并不涉及存储器管理方面的操作。可见，进程切换的开销也远远大于线程切合的开销。此外，由于同一进程中多个线程具有相同的地址空间，致使它们之间同步和通信的实现也比较容易。在有的系统中，线程的切换、同步和通信都无需内核的干涉。

6. 100亿个整数，内存足够，如何找到中位数？内存不足，如何找到中位数？

若内存足够，可将100亿个数进行排序，快排，堆排均可，取其中间数字即可。或者将其构建出一个AVL树或红黑树，取其顶部数字即可。

若内存不足，则可采取分而治之的方法，将100亿个数按其前5位分成32个桶，若还是不足以放入内存就继续分。统计每个桶中数字的个数，就可以知道中位数一定出现在那个桶中，因为桶是按照32位数的前5位分的，桶之间是排好序的。并且还可以知道中位数是这个桶中第几大的数。然后将这个桶中的数字排序即可。

二

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

智能指针即一个对象，可以用来管理其他对象动态分配出来的指针，并在该对象生命期结束时调用其析构函数来释放它。智能指针分为autoptr,scopedptr,sharedptr,weakptr,instrusiveptr,scopedarray,sharedarray等。其中sharedptr使用引用计数的原理。当初始化对象时，将引用计数设为1，增加引用时，对其加1，减少引用时减1.当引用计数减少到0时，自动调用它所管理对象的析构函数来释放该对象。

模拟实现shared_ptr:

template<typename T>
class Shared_ptr {
public:
Shared_ptr(T* ptr=NULL)
:_ptr(ptr)
{
if (_ptr == NULL)
_count = new int(0);
else
_count = new int(1);
}
Shared_ptr(const Shared_ptr<T>&amp; other)
{
_ptr = other._ptr;
_count = other._count;
(*_count)++;
}
Shared_ptr&amp; operator=(const Shared_ptr<T>&amp; other)
{
_release();
_ptr = other._ptr;
_count = other._count;
(*_count)++;
return *this;
}
T&amp; operator*()
{
return *_ptr;
}
T* operator->()
{
retrn _ptr;
}
~Shared_ptr()
{
_release();
}
protected:
void _release()
{
if (--*_count == 0)
{
delete _ptr;
delete _count;
_ptr == NULL;
}
}
private:
T* _ptr;
int* _count;
};

2. 如何处理循环引用问题？

当可能会发生循环引用时，只需要让循环的一方持有弱指针，即weak_ptr即可。

3. 请实现⼀个单例模式的类，要求线程安全。

我的实现：

template<typename T>
class singleton {
public:
T* GetInstance()
{
if (_ptr == NULL)//加锁是个很耗时的过程，先判断可以减少加锁的次数
{
_lock.lock();//加锁
if (_ptr == NULL)
_ptr = new T();
_lock.unlock();//解锁
}
return _ptr;
}
static void DelInstance()
{
_lock.lock();
if (_ptr != NULL)
{
delete _ptr;
_ptr = NULL;
}
_lock.unlock();
}
private:
singleton();
static mutex _lock;//C++11 互斥锁 
static T* _ptr;//要求只能创建一个对象，所以需要将_ptr和_lock都设置为static
};

template<typename T>
mutex singleton<T>::_lock;
template<typename T>
T* singleton<T>::_ptr = NULL;

mutex g_lock;

void fun()
{
g_lock.lock();
cout << "thread1_id:" << this_thread::get_id() << endl;
g_lock.unlock();
singleton<int>* s=NULL;
int*p=s->GetInstance();
int i=0;
while (i++ < 5000)
{
g_lock.lock();
(*p)++;
g_lock.unlock();
}
g_lock.lock();
cout << "thread1:" << *p << endl;
g_lock.unlock();
s->DelInstance();
}
void fun1()
{
g_lock.lock();
cout << "thread2_id:" << this_thread::get_id() << endl;
g_lock.unlock();
singleton<int>* s=NULL;
int*p=s->GetInstance();
int i=0;
while (i++ < 5000)
{
g_lock.lock();
(*p)++;
g_lock.unlock();
}
g_lock.lock();
cout << "thread2:" << *p << endl;
g_lock.unlock();
s->DelInstance();
}

int main()
{
thread t(fun);
thread t1(fun1);
t.join();
t1.join();
return 0;
}

经典实现：

class Singleton
{
public:
    // 获取唯一对象实例的接口函数
    static Singleton* GetInstance()
    {
        // 使用双重检查，提高效率，避免高并发场景下每次获取实例对象都进行加锁
        if (_sInstance == NULL)
        {
            std::lock_guard<std::mutex> lck(_mtx);
            if (_sInstance == NULL)
                _sInstance = new Singleton();
        }
        return _sInstance;
    }

    // 删除实例对象
    static void DelInstance()
    {
        std::lock_guard<std::mutex> lck(_mtx);
        if (_sInstance)
        {
            delete _sInstance;
            _sInstance = NULL;
        }
    }

    void Print()
    {
        cout<<_data<<endl;
    }

private:
    // 构造函数定义为私有，限制只能在类内创建对象
    Singleton()
        :_data(0)
    {}

    // 指向实例的指针定义为静态私有，这样定义静态成员函数获取对象实例
    static Singleton* _sInstance;

    // 保证线程安全的互斥锁
    static mutex _mtx;

    // 单例类里面的数据
    int _data;
};

Singleton* Singleton::_sInstance = NULL;
mutex Singleton::_mtx;

void TestSingleton()
{
    Singleton::GetInstance()->Print();
    Singleton::DelInstance();
}

4.如何定义一个只能在堆上生成对象的类？

先来看看类对象的生成方式：

5.如何定义一个只能在栈上生成对象的类？

由上题可知，要使对象只能在栈上分配，需要限制其不能在堆上分配。可以从在堆上生成对象的两个步骤入手。

综上，可以将operator new()函数和operator delete()函数重载为类的私有成员函数，即可解决该问题。

6.下面的结构体大小分别是多大？(假设为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;
};

sizeof(A)=3;

sizeof(B)=8;

sizeof(C)=12;

sizeof(D)=8;

结构体内存对齐规则：

  1. 每个成员变量必须存放在整数倍于自己大小的内存地址处；

  2. 整个结构体的大小必须是最大字节的整数倍。

7.引用和指针的区别？

作为函数参数传递时，引用和指针都可以修改原对象。但指针传递的是指针本身的拷贝，而引用传递的是实参本身，因而使用引用做参数不仅可以节约时间，也可以节约空间。 * 引用在底层是使用指针实现的，二者在汇编层面上完全一致。如下

8.const和define的区别？

9.define与inline的区别？

10.malloc和new的区别？

11.C++中static关键字的作用？

  1. 声明函数或变量的可见性为本文件，即对外隐藏；
  2. 声明变量的存储类型为全局的，存储在全局数据区，即具有全局生存期；
  3. static变量和全局变量都默认初始化为0；
  4. 用于C++的类中时，static变量属于类而不属于对象，需要手动初始化；static函数没有this指针，所以只能访问类的static变量和static函数。

12.C++中const关键字的作用？

  1. 用于变量时，表明该变量时只读的；
  2. 用于函数时返回值和参数时，表明该值只读，不可改变；
  3. 用于成员函数时，表明该函数不改变类的成员变量；

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

三.C++基础(下)

1. 下面两段代码的输出分别是什么？

左边代码输出：

Print in Base

Print in Derive

右边代码输出:

Print in Base

Print in Base

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

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

普通成员函数更快。因为访问虚函数时，需要先根据虚表指针找到虚表，然后取其地址并访问。而普通成员函数没有这些步骤。

4.在什么情况下，析构函数需要使虚函数？

当该类作为基类被继承时，需要将析构函数设为虚函数，否则当使基类指针指向派生类时，通过该指针析构派生类对象，只能调用基类的析构函数，无法调用派生类析构函数。当在派生类中进行了内存分配、文件打开、资源获取、网络IO、数据库打开等操作时，会导致内存泄露或其他问题。而将基类的析构函数设为虚函数后，实际调用的是派生类的析构函数(派生类析构函数覆盖了基类的析构函数)，而要析构派生类，编译器会自动先调用基类的析构函数，然后再调用派生类的。所以此时不会有上述问题。

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

都不可以！

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

在语法层面可以调用，但强烈不建议这样做！根据《effective C++》条款9所言，如果在构造函数中调用了虚函数，且该类作为基类使用的话。在构造派生类对象时，会首先构造基类对象，而此时该对象的类型是基类类型，调用的是基类的虚函数。而虚函数的本意是想调用派生类的虚函数。

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

虚继承的出现，是为了解决菱形继承的问题的。所谓菱形继承，就是两个类都继承了同一个类，而这两个类又共同派生出一个类。如下：

class base{};
class base1:public base{};
class base2:public base{};
class derived:public base1,public base2{};

这样的话，base中的数据在derive的类中就存在了两份，这样不仅导致数据冗余，浪费空间，还有二义性的问题。

所以出现了虚继承，即在派生base1和base2时加一个virtual关键字而已。如下：

class base{};
class base1:public virtual base{};
class base2:public virtual base{};
class derived:public base1,public base2{};

具体细节和内存布局这里不讲，具体可参考我的另一篇博文:继承体系下的C++对象模型