实现内存复制函数

面试中面试官经常会让写程序,根据题目的难度会在算法和编程习惯上各有侧重。比如写一个memcpy函数,这个题算法简单明确,因此重点考察编程习惯、工程思想。
该题目的算法如下
0.1

  1. void  memcpy(void *dst, void *src, int count)
  2. {
  3.     while(count–)
  4.     {
  5.         *dst = *src;
  6.         dst++;
  7.         src++;
  8.     }
  9. }

问题是void*不能直接累加 *dst = *src也是不对的。
0.2

  1. void memcpy(void *dst, void *src, int count)
  2. {
  3.     unsigned char *pdst = (unsigned char *)dst;
  4.     unsigned char *psrc = (unsigned char *)src;
  5.     while(count–)
  6.     {
  7.         *pdst = *psrc;
  8.         pdst++;
  9.         psrc++;
  10.     }
  11. }

在32位系统中,可复制的最多内存是多少?类型会不会不够用?
内存复制不应该修改原始内存吧。
因此,函数声明修改如下
0.3

  1. void memcpy(void *dst, const void *src, size_t count)

这样就万事大吉了吗?
如果传入了空指针呢?
接着修改吧
0.4

  1. void memcpy(void *dst, const void *src, size_t count)
  2. {
  3.     assert(dst != NULL);
  4.     assert(src != NULL);
  5.     unsigned char *pdst = (unsigned char *)dst;
  6.     const unsigned char *psrc = (const unsigned char *)src;
  7.     while(count–)
  8.     {
  9.         *pdst = *psrc;
  10.         pdst++;
  11.         psrc++;
  12.     }
  13. }

如果有这样的数组
char ina[]={0,1,2,3,4,5,6,7,8,9,10,11};
进行如下调用
memcpy(&ina[1], &ina[0], 5);
会发生什么情况?
由于原始数据和目的数据在空间上存在重叠,这样导致复制过程中不可避免会对原始数据做修改。而这样的修改在函数的声明中是看不到的(const void *src)。如果降低要求,可以修改原始数据完成复制,那么这样的设计能实现么?因此
0.5

  1. void memcpy(void *dst, const void *src, size_t count)
  2. {
  3.     assert(dst != NULL);
  4.     assert(src != NULL);
  5.     unsigned char *pdst = (unsigned char *)dst;
  6.     const unsigned char *psrc = (const unsigned char *)src;
  7.     assert(!(psrc<=pdst && pdst<psrc+count));//判断是否有重叠
  8.     assert(!(pdst<=psrc && psrc<pdst+count));
  9.     while(count–)
  10.     {
  11.         *pdst = *psrc;
  12.         pdst++;
  13.         psrc++;
  14.     }
  15. }

到这里实现已经比较健壮了。有些人想要链式的调用函数,也就是复制完内存后,返回值直接当做其他函数的参数。

  1. void * memcpy(void *dst, const void *src, size_t count)

0.6因此最终版本为

  1. void* memcpy(void *dst, const void *src, size_t count)
  2. {
  3.     assert(dst != NULL);
  4.     assert(src != NULL);
  5.     unsigned char *pdst = (unsigned char *)dst;
  6.     const unsigned char *psrc = (const unsigned char *)src;
  7.     assert(!(psrc<=pdst && pdst<psrc+count));
  8.     assert(!(pdst<=psrc && psrc<pdst+count));
  9.     while(count–)
  10.     {
  11.         *pdst = *psrc;
  12.         pdst++;
  13.         psrc++;
  14.     }
  15.     return dst;
  16. }

最后,有网友做了性能测试,结论显示上面的实现达不到库函数的性能。个人认为库函数可能做了优化,例如使用mmx技术,使得一次复制一个字节到一次复制多个字节。

这个题目在面试出现的次数太频繁,能够比较正确的写出这个函数的能说明什么呢?
1.缺乏项目经验,对于面试因此复习的很到位。
2.有可能有丰富的项目经验,在项目中也这么做。
3.认为有较多项目经验,但是没有注意非功能性要求。等着杯具吧。

变长参数模板

C++03只有固定模板参数。C++11 加入新的表示法,允许任意个数、任意类别的模板参数,不必在定义时将参数的个数固定。

实参的个数也可以是 0,所以 tuple<> someInstanceName 这样的定义也是可以的。

若不希望产生实参个数为 0 的变长参数模板,则可以采用以下的定义:

变长函数参数包

除了在模板参数中能使用表示不定长模板参数外,函数参数也使用同样的表示法代表不定长参数。

其中,Params 与 parameters 分别代表模板与函数的变长参数集合, 称之为参数包 (parameter pack)。参数包必须要和运算符”…”搭配使用。

变长参数的使用

长参数模板中,变长参数包无法如同一般参数在类或函数中使用; 因此典型的手法是以递归的方法取出可用参数:

printf 会不断地递归调用自身:函数参数包 args... 在调用时, 会被模板类别匹配分离为 T value和 Args... args。 直到 args... 变为空参数,则会与简单的 printf(const char *s) 形成匹配,退出递归。

另一个例子为计算模板参数的个数,这里使用相似的技巧展开模板参数包 Args...

其它变长参数的展开形式

使用运算符”…”还能在代码各处对参数包施以更复杂的展开操作。举例来说,一个模板类的定义:

变长模板参数个数

变长参数的数量可以藉以下的语法得知:

typename和class的区别

在c++Template中很多地方都用到了typename与class这两个关键字,而且好像可以替换,是不是这两个关键字完全一样呢?相信学习C++的人对class这个关键字都非常明白,class用于定义类,在模板引入c++后,最初定义模板的方法为:template<class T>…… 在这里class关键字表明T是一个类型,后来为了避免class在这两个地方的使用可能给人带来混淆,所以引入了typename这个关键字,它的作用同class一样表明后面的符号为一个类型,这样在定义模板的时候就可以使用下面的方式了: template<typename T>……

在模板定义语法中关键字class与typename的作用完全一样。typename难道仅仅在模板定义中起作用吗?其实不是这样,typename另外一个作用为:使用嵌套依赖类型(nested depended name),如下所示:

class MyArray
{
public:
typedef int LengthType;
…..
}

template<class T>
void MyMethod( T myarr )
{
typedef typename T::LengthType LengthType;
LengthType length = myarr.GetLength;
}

这个时候typename的作用就是告诉c++编译器,typename后面的字符串为一个类型名称,而不是成员函数或者成员变量,这个时候如果前面没有typename,编译器没有任何办法知道T::LengthType是一个类型还是一个成员名称(静态数据成员或者静态函数),所以编译不能够通过。

weak_ptr

1、为什么需要weak_ptr?

在正式介绍weak_ptr之前,我们先来回忆一下shared_ptr的一些知识。我们知道shared_ptr是采用引用计数的智能指针,多个shared_ptr实例可以指向同一个动态对象,并维护了一个共享的引用计数器。对于引用计数法实现的计数,总是避免不了循环引用(或环形引用)的问题,shared_ptr也不例外。

我们先来看看下面这个例子:

#include <iostream>
#include <memory>
#include <vector>
using namespace std;

class ClassB;

class ClassA
{
public:
    ClassA() { cout << "ClassA Constructor..." << endl; }
    ~ClassA() { cout << "ClassA Destructor..." << endl; }
    shared_ptr<ClassB> pb;  // 在A中引用B
};

class ClassB
{
public:
    ClassB() { cout << "ClassB Constructor..." << endl; }
    ~ClassB() { cout << "ClassB Destructor..." << endl; }
    shared_ptr<ClassA> pa;  // 在B中引用A
};

int main() {
    shared_ptr<ClassA> spa = make_shared<ClassA>();
    shared_ptr<ClassB> spb = make_shared<ClassB>();
    spa->pb = spb;
    spb->pa = spa;
    // 函数结束,思考一下:spa和spb会释放资源么?
}

上面代码的输出如下:

ClassA Constructor...
ClassB Constructor...
Program ended with exit code: 0

从上面代码中,ClassA和ClassB间存在着循环引用,从运行结果中我们可以看到:当main函数运行结束后,spa和spb管理的动态资源并没有得到释放,产生了内存泄露。

为了解决类似这样的问题,C++11引入了weak_ptr,来打破这种循环引用。

2、weak_ptr是什么?

weak_ptr是为了配合shared_ptr而引入的一种智能指针,它指向一个由shared_ptr管理的对象而不影响所指对象的生命周期,也就是将一个weak_ptr绑定到一个shared_ptr不会改变shared_ptr的引用计数。不论是否有weak_ptr指向,一旦最后一个指向对象的shared_ptr被销毁,对象就会被释放。从这个角度看,weak_ptr更像是shared_ptr的一个助手而不是智能指针。

3、weak_ptr如何使用?

接下来,我们来看看weak_ptr的简单用法。

3.1如何创建weak_ptr实例

当我们创建一个weak_ptr时,需要用一个shared_ptr实例来初始化weak_ptr,由于是弱共享,weak_ptr的创建并不会影响shared_ptr的引用计数值。

示例:

int main() {
    shared_ptr<int> sp(new int(5));
    cout << "创建前sp的引用计数:" << sp.use_count() << endl;    // use_count = 1

    weak_ptr<int> wp(sp);
    cout << "创建后sp的引用计数:" << sp.use_count() << endl;    // use_count = 1
}

3.2如何判断weak_ptr指向对象是否存在

既然weak_ptr并不改变其所共享的shared_ptr实例的引用计数,那就可能存在weak_ptr指向的对象被释放掉这种情况。这时,我们就不能使用weak_ptr直接访问对象。那么我们如何判断weak_ptr指向对象是否存在呢?C++中提供了lock函数来实现该功能。如果对象存在,lock()函数返回一个指向共享对象的shared_ptr,否则返回一个空shared_ptr。

示例:

class A
{
public:
    A() : a(3) { cout << "A Constructor..." << endl; }
    ~A() { cout << "A Destructor..." << endl; }

    int a;
};

int main() {
    shared_ptr<A> sp(new A());
    weak_ptr<A> wp(sp);
    //sp.reset();

    if (shared_ptr<A> pa = wp.lock())
    {
        cout << pa->a << endl;
    }
    else
    {
        cout << "wp指向对象为空" << endl;
    }
}

试试把sp.reset()这行的注释去掉看看结果有什么不同。

除此之外,weak_ptr还提供了expired()函数来判断所指对象是否已经被销毁。

示例:

class A
{
public:
    A() : a(3) { cout << "A Constructor..." << endl; }
    ~A() { cout << "A Destructor..." << endl; }

    int a;
};

int main() {
    shared_ptr<A> sp(new A());
    weak_ptr<A> wp(sp);
    sp.reset(); // 此时sp被销毁
    cout << wp.expired() << endl;  // true表示已被销毁,否则为false
}

代码输入如下:

A Constructor...
A Destructor...
1

3.3如何使用weak_ptr

weak_ptr并没有重载operator->和operator *操作符,因此不可直接通过weak_ptr使用对象,典型的用法是调用其lock函数来获得shared_ptr示例,进而访问原始对象。

最后,我们来看看如何使用weak_ptr来改造最前面的代码,打破循环引用问题。

class ClassB;

class ClassA
{
public:
    ClassA() { cout << "ClassA Constructor..." << endl; }
    ~ClassA() { cout << "ClassA Destructor..." << endl; }
    weak_ptr<ClassB> pb;  // 在A中引用B
};

class ClassB
{
public:
    ClassB() { cout << "ClassB Constructor..." << endl; }
    ~ClassB() { cout << "ClassB Destructor..." << endl; }
    weak_ptr<ClassA> pa;  // 在B中引用A
};

int main() {
    shared_ptr<ClassA> spa = make_shared<ClassA>();
    shared_ptr<ClassB> spb = make_shared<ClassB>();
    spa->pb = spb;
    spb->pa = spa;
    // 函数结束,思考一下:spa和spb会释放资源么?
}

输出结果如下:

ClassA Constructor...
ClassB Constructor...
ClassA Destructor...
ClassB Destructor...
Program ended with exit code: 0

从运行结果可以看到spa和spb指向的对象都得到释放!

unique_ptr

unique是独特的、唯一的意思,故名思议,unique_ptr可以“独占”地拥有它所指向的对象,它提供一种严格意义上的所有权。这一点和我们前面介绍的shared_ptr类型指针有很大的不同:shared_ptr允许多个指针指向同一对象,而unique_ptr在某一时刻只能有一个指针指向该对象。unique_ptr保存指向某个对象的指针,当它本身被删除或者离开其作用域时会自动释放其指向对象所占用的资源。

下面,我们就来具体介绍一下unique_ptr的基本特性。

1、如何创建unique_ptr

unique_ptr不像shared_ptr一样拥有标准库函数make_shared来创建一个shared_ptr实例。要想创建一个unique_ptr,我们需要将一个new 操作符返回的指针传递给unique_ptr的构造函数。

示例:

int main() {
    // 创建一个unique_ptr实例
    unique_ptr<int> pInt(new int(5));
    cout << *pInt;
}

2、无法进行复制构造和赋值操作

unique_ptr没有copy构造函数,不支持普通的拷贝和赋值操作。

int main() {
    // 创建一个unique_ptr实例
    unique_ptr<int> pInt(new int(5));
    unique_ptr<int> pInt2(pInt);    // 报错
    unique_ptr<int> pInt3 = pInt;   // 报错
}

3、可以进行移动构造和移动赋值操作

unique_ptr虽然没有支持普通的拷贝和赋值操作,但却提供了一种移动机制来将指针的所有权从一个unique_ptr转移给另一个unique_ptr。如果需要转移所有权,可以使用std::move()函数。

示例:

int main() {
    unique_ptr<int> pInt(new int(5));
    unique_ptr<int> pInt2 = std::move(pInt);    // 转移所有权
    //cout << *pInt << endl; // 出错,pInt为空
    cout << *pInt2 << endl;
    unique_ptr<int> pInt3(std::move(pInt2));
}

4、可以返回unique_ptr

unique_ptr不支持拷贝操作,但却有一个例外:可以从函数中返回一个unique_ptr。

示例:

unique_ptr<int> clone(int p)
{
    unique_ptr<int> pInt(new int(p));
    return pInt;    // 返回unique_ptr
}

int main() {
    int p = 5;
    unique_ptr<int> ret = clone(p);
    cout << *ret << endl;
}

unique_ptr使用场景

1、为动态申请的资源提供异常安全保证

我们先来看看下面这一段代码:

void Func()
{
    int *p = new int(5);

    // ...(可能会抛出异常)

    delete p;
}

这是我们传统的写法:当我们动态申请内存后,有可能我们接下来的代码由于抛出异常或者提前退出(if语句)而没有执行delete操作。

解决的方法是使用unique_ptr来管理动态内存,只要unique_ptr指针创建成功,其析构函数都会被调用。确保动态资源被释放。

void Func()
{
    unique_ptr<int> p(new int(5));

    // ...(可能会抛出异常)
}

2、返回函数内动态申请资源的所有权

unique_ptr<int> Func(int p)
{
    unique_ptr<int> pInt(new int(p));
    return pInt;    // 返回unique_ptr
}

int main() {
    int p = 5;
    unique_ptr<int> ret = Func(p);
    cout << *ret << endl;
    // 函数结束后,自动释放资源
}

3、在容器中保存指针

int main() {
    vector<unique_ptr<int>> vec;
    unique_ptr<int> p(new int(5));
    vec.push_back(std::move(p));    // 使用移动语义
}

4、管理动态数组

标准库提供了一个可以管理动态数组的unique_ptr版本。

int main() {
    unique_ptr<int[]> p(new int[5] {1, 2, 3, 4, 5});
    p[0] = 0;   // 重载了operator[]
}

5、作为auto_ptr的替代品

shared_ptr

shared_ptr是一个引用计数智能指针,用于共享对象的所有权也就是说它允许多个指针指向同一个对象。这一点与原始指针一致。

先来一段简单的代码,看看shared_ptr的简单使用:

#include <iostream>
#include <memory>
using  namespace std;

class Example
{
public:
    Example() : e(1) { cout << "Example Constructor..." << endl; }
    ~Example() { cout << "Example Destructor..." << endl; }

    int e;
};

int main() {

    shared_ptr<Example> pInt(new Example());
    cout << (*pInt).e << endl;
    cout << "pInt引用计数: " << pInt.use_count() << endl;

    shared_ptr<Example> pInt2 = pInt;
    cout << "pInt引用计数: " << pInt.use_count() << endl;
    cout << "pInt2引用计数: " << pInt2.use_count() << endl;
}

程序输出如下:

Example Constructor...
pInt: 1
pInt引用计数: 1
pInt引用计数: 2
pInt2引用计数: 2
Example Destructor...

从上面这段代码中,我们对shared_ptr指针有了一些直观的了解。一方面,跟STL中大多数容器类型一样,shared_ptr也是模板类,因此在创建shared_ptr时需要指定其指向的类型。另一方面,正如其名一样,shared_ptr指针允许让多个该类型的指针共享同一堆分配对象。同时shared_ptr使用经典的“引用计数”方法来管理对象资源,每个shared_ptr对象关联一个共享的引用计数。对于“引用计数”的问题,这里就不展开介绍。有兴趣的同学可以上网查找资料。

对于shared_ptr在拷贝和赋值时的行为,《C++Primer第五版》中有详细的描述:

每个shared_ptr都有一个关联的计数值,通常称为引用计数。无论何时我们拷贝一个shared_ptr,计数器都会递增。
例如,当用一个shared_ptr初始化另一个shred_ptr,或将它当做参数传递给一个函数以及作为函数的返回值时,它
所关联的计数器就会递增。当我们给shared_ptr赋予一个新值或是shared_ptr被销毁(例如一个局部的
shared_ptr离开其作用域)时,计数器就会递减。一旦一个shared_ptr的计数器变为0,它就会自动释放自己所管理
的对象。

对比我们上面的代码可以看到:当我们将一个指向Example对象的指针交给pInt管理后,其关联的引用计数为1。接下来,我们用pInt初始化pInt2,两者关联的引用计数值增加为2。随后,函数结束,pInt和PInt2相继离开函数作用于,相应的引用计数值分别自减1最后变为0,于是Example对象被自动释放(调用其析构函数)。

接下来,我们完整地介绍一下shared_ptr的常见用法:

1、创建shared_ptr实例

最安全和高效的方法是调用make_shared库函数,该函数会在堆中分配一个对象并初始化,最后返回指向此对象的share_ptr实例。如果你不想使用make_ptr,也可以先明确new出一个对象,然后把其原始指针传递给share_ptr的构造函数。

示例如下:

int main() {

    // 传递给make_shared函数的参数必须和shared_ptr所指向类型的某个构造函数相匹配
    shared_ptr<string> pStr = make_shared<string>(10, 'a');
    cout << *pStr << endl;  //  aaaaaaaaaa

    int *p = new int(5);
    shared_ptr<int> pInt(p);
    cout << *pInt << endl;  // 5
}

2、访问所指对象

shared_ptr的使用方式与普通指针的使用方式类似,既可以使用解引用操作符*获得原始对象进而访问其各个成员,也可以使用指针访问符->来访问原始对象的各个成员。

3、拷贝和赋值操作

我们可以用一个shared_ptr对象来初始化另一个share_ptr实例,该操作会增加其引用计数值。

例如:

int main() {
    shared_ptr<string> pStr = make_shared<string>(10, 'a');
    cout << pStr.use_count() << endl;  //  1

    shared_ptr<string> pStr2(pStr);
    cout << pStr.use_count() << endl;  //  2
    cout << pStr2.use_count() << endl;  //  2
}

如果shared_ptr实例p和另一个shared_ptr实例q所指向的类型相同或者可以相互转换,我们还可以进行诸如p = q这样赋值操作。该操作会递减p的引用计数值,递增q的引用计数值。

例如:

class Example
{
public:
    Example(string n) : name(n) { cout << n << " constructor..." << endl; }
    ~Example() { cout << name << " destructor..." << endl; }

    string name;
};

int main() {

    shared_ptr<Example> pStr = make_shared<Example>("a object");
    shared_ptr<Example> pStr2 = make_shared<Example>("b object");
    cout << pStr.use_count() << endl;
    cout << pStr2.use_count() << endl;

    pStr = pStr2;   // 此后pStr和pStr指向相同对象
    cout << pStr->name << endl;
    cout << pStr2->name << endl;
}

输出如下:

a object constructor...
b object constructor...
1
1
a object destructor...
b object
b object
b object destructor...

4、检查引用计数

shared_ptr提供了两个函数来检查其共享的引用计数值,分别是unique()和use_count()。

在前面,我们已经多次使用过use_count()函数,该函数返回当前指针的引用计数值。值得注意的是use_count()函数可能效率很低,应该只把它用于测试或调试。

unique()函数用来测试该shared_ptr是否是原始指针唯一拥有者,也就是use_count()的返回值为1时返回true,否则返回false。

示例:

int main() {
    shared_ptr<string> pStr = make_shared<string>(10, 'a');
    cout << pStr.unique() << endl;  // true

    shared_ptr<string> pStr2(pStr);
    cout << pStr2.unique() << endl; // false;
}

mutable关键字

mutalbe的中文意思是“可变的,易变的”,跟constant(既C++中的const)是反义词。
在C++中,mutable也是为了突破const的限制而设置的。被mutable修饰的变量,将永远处于可变的状态,即使在一个const函数中。

我们知道,如果类的成员函数不会改变对象的状态,那么这个成员函数一般会声明成const的。但是,有些时候,我们需要在const的函数里面修改一些跟类状态无关的数据成员,那么这个数据成员就应该被mutalbe来修饰。

下面是一个小例子:

class ClxTest
{
public:
void Output() const;
};

void ClxTest::Output() const
{
cout << “Output for test!” << endl;
}

void OutputTest(const ClxTest& lx)
{
lx.Output();
}

类ClxTest的成员函数Output是用来输出的,不会修改类的状态,所以被声明为const的。

函数OutputTest也是用来输出的,里面调用了对象lx的Output输出方法,为了防止在函数中调用其他成员函数修改任何成员变量,所以参数也被const修饰。

如果现在,我们要增添一个功能:计算每个对象的输出次数。如果用来计数的变量是普通的变量的话,那么在const成员函数Output里面是不能修改该变量的值的;而该变量跟对象的状态无关,所以应该为了修改该变量而去掉Output的const属性。这个时候,就该我们的mutable出场了——只要用mutalbe来修饰这个变量,所有问题就迎刃而解了。

下面是修改过的代码:

class ClxTest
{
public:
ClxTest();
~ClxTest();

void Output() const;
int GetOutputTimes() const;

private:
mutable int m_iTimes;
};

ClxTest::ClxTest()
{
m_iTimes = 0;
}

ClxTest::~ClxTest()
{}

void ClxTest::Output() const
{
cout << “Output for test!” << endl;
m_iTimes++;
}

int ClxTest::GetOutputTimes() const
{
return m_iTimes;
}

void OutputTest(const ClxTest& lx)
{
cout << lx.GetOutputTimes() << endl;
lx.Output();
cout << lx.GetOutputTimes() << endl;
}

计数器m_iTimes被mutable修饰,那么它就可以突破const的限制,在被const修饰的函数里面也能被修改。

std::bind原理图释

(原文:http://blog.think-async.com/2010/04/bind-illustrated.html)

本文解释了bind 是如何工作的。为了清晰,我对图中的语法作了一些简化(例如,省略函数调用操作符的参数类型),并且简化了 bind 的实现.

1. bind 可以用来将用户提供的需要一个参数的函数转换成不需要参数的函数对象。绑定的值(在这个例子中是123)存储在函数对象内并且会被自动传递给用户指定的函数:

 

 

2. 参数绑定也可以用于将类成员函数转换成零参数的函数对象。猿类们都知道,非静态成员函数需要一个隐式的 this 参数。这意味着需要绑定一个合适的类实例指针到这个函数对象:

3. 相应地,隐式的 this 指针也可以显式地传递给需要一个参数的函数对象:

4. 函数对象经常同时使用提前绑定的参数和调用时才提供的参数。这个可以用成员函数来实现:

 

5. 当然也可以使用非成员函数:

 

6. 有些时候函数对象被调用时会提供多余的参数,而这些参数是目标函数不需要的。bind 会自动忽略这些多余的参数:

7. 这些多余的参数不需要一定在函数对象签名的最后:

 

8. 最后, bind 还允许重新组织函数对象的参数顺序: