Xander's Wiki


  • Home

  • Tags

  • Categories

  • Archives

  • Search

33.public继承:is-a关系

Posted on 2018-04-16 | In Effective C++

前言

 
以c++进行面向对象编程时,最重要的一条规则是:public inheritance意味着is-a的关系。


is-a关系

 
如果你令class d public derived from class b,你等于在同时告诉c++编译器以及代码读者,每一个类型为d的对象同时也是一个类型为b的对象,反之不成立。
这也可以表示为“每一个需要b对象的地方,d对象也同样适用”,因为每一个d对象也是一个b对象。
该定义只对public继承有效,private继承的意义与此完全不同(详见Effective C++ 40),至于protected继承,其意义十分暧昧。


问题实例

 
大多数人都认为is-a关系十分简单,但实际并非如此,因为直觉容易误导我们。

鸟与企鹅

企鹅是一种鸟,这是再自然不过的。鸟可以飞,这也是符合直觉的。于是…

1
2
3
4
5
6
7
8
class Bird{
public:
virtual void fly();//鸟会飞
...
};
class Penguin:public Bird{//企鹅是一种鸟
...
};

实际上企鹅不会飞,但企鹅却继承了fly接口,这明确表明当前继承体系存在问题。

重塑继承体系

你或许会意识到这是因为不严谨的语言表述导致我们吃了大亏。实际上是这样的:企鹅是鸟,但不是所有鸟都会飞,有的会有的不会。所以这才是正确的继承体系:

1
2
3
4
5
6
class bird {...};
class flyingbird:public bird{
public:
virtual void flying();
};
class penguin:public bird {};

这种写法针对fly这个接口无疑是成功的,但实际上对于某些软件系统而言,它根本不用去关心鸟会不会飞,此时建立一个flyingbird无疑是不明智的。这引出了一个事实:
世界上并不存在一个完美适用于所有软件的完美设计。所谓的最佳设计,取决于系统现在以及未来所关注的重点。

运行期报错处理

有人会为企鹅重新定义一个fly函数,令其产生一个运行期错误:

1
2
3
4
5
6
​class penguin:public bird{
public:
virtual void fly(){
error(“can not fly”);
}
};

这种写法是失败的,它等于在说:企鹅会飞,但是一飞就报错。这违背了我们的设计理念:让接口易于使用,不被误用。(Effective C++ 19)


矩形与正方形

squre应该public derived from rectangle吗?也许你会毫不犹豫地肯定这一观点,“正方形必然是矩形,但反之不成立”。请考虑如下程序:

1
2
3
4
5
6
class Rectangle{
public:
virtual void setHeight(int newHeight);
...//setWidth
};
class Square:public Rectangle {...};

Square继承了setHeight等接口,也就是说,我们可以通过调用成员函数,导致正方形长宽不等,那这种对象还能被称为正方形吗。(实际上,在正方形的接口中我们必须确保setHeight之后必须执行setWidth)


classes之间的关系

 
is-a并非是classes之间唯一的关系,另外两个常见的是has-a与is-implemented-in-terms-of。


总结

 
public继承意味着is-a,is-a意味着适用于base对象身上的每一件事情一定也适用于derived对象身上,因为每一个derived对象也一定是一个base对象。

34.了解算法对容器的要求

Posted on 2018-04-16 | In Effective STL

前言

 
并非所有算法都可以用于任意区间。如果你违背了算法要求,编译器会提供给你一个复杂且难以理解的报错信息。


有序区间算法

 
以下算法只能作用于有序区间:

  • binary_serach
  • lower_bound upper_bound equal_range
  • set_union set_intersection set_difference seT_symmetric_difference
  • merge inplace_merge
  • includes

另外,unique与unique_copy一般作用于有序区间,虽然它们对此不作要求。

为何需要有序区间

(建议阅读数据结构·向量篇,其练习几乎解答了下述所有问题)

  • binary_search,lower_bound,upper_bound以及equal_range
    上述算法均基于二分查找,因此必须提供有序区间。
    其具体效率实际上取决于迭代器。如果不支持随机访问,其效率会由对数时间退化至线性时间。
  • set_union,set_intersection,set_difference,set_symmetric_difference
    如果不提供有序区间,则它们无法在线性时间内完成工作。
  • merge与inplace_merge
    提供了单遍合并排序。
  • includes
    检测是否一个区间的所有对象也在另一个区间中,有序保证了其线性时间的效率
  • unique
    其功能是去重,但为了保证元素值唯一,你必须保证这些相似的元素一个接着一个,这也就是排序的一种弱化形式。(22211333)

确保算法的排序方式与容器的排序方式相同

反例

1
2
3
vector<int> v;
sort(v.begin(), v.end(), greater<int>());//降序排列
bool a5Exists = binary_search(v.begin(), v.end(), 5);//binary_search默认升序排列

这段代码将直接导致未定义行为。

正确使用方式

1
bool a5Exists =binary_search(v.begin(), v.end(), 5. greater<int>());

判同验证

 
所有需要有序区间的算法通过等价来判断两个值是否相同,类似于关联容器。unique系列通过相等来判断。

32.降低文件间的编译依存关系

Posted on 2018-04-16 | In Effective C++

前言

 
某一天你对某个class中的部分实现文件做了些许更改,注意,改的不是接口,仅仅是实现,并且是private部分。当你按下build之后你估计大概要等几秒,但实际上。。。。你发现整个世界都被重新编译和连接了。


问题实例

 
上述问题出在C++对“将接口从实现中分离”完成得不好。class的定义式不仅仅描述了接口,还包括了实现细目:

1
2
3
4
5
6
7
8
class Person{
public:
...
private:
//以下均为实现细目
string theName;
Address theAddress;
}

如果编译器没有取得上述程序所用到的string,Date等定义式,它就无法编译。​
当然,我们肯定会使用
1
2
#include <string>
#include "Address.h"

不幸的是,这样一来便是在Person定义文件和其含入文件间形成了一种compilation dependency。
如果这些头文件中有任何一个被改变,或这些头文件所依赖的其他头文件有任何改变,那么每一个#include "Person.h"的文件都必须重新编译,任何使用了Person对象的文件也必须重新编译。


前置声明

有人会好奇为何不使用前置声明分开实现细目:

1
2
3
4
5
6
7
8
9
10
namespace std{
class string;//前置声明
}
class Address;//前置声明
class Person{
public:
...
private:
...
}

如果这样能够完成,那么仅有Person被改过之后客户才需要重新编译。

前置声明的问题

  1. string并不是class
    string并不是一个class,它是一个typedef。并且我们不应该尝试手工声明一部分STL,而是应该使用include完成目的,标准头文件不会成为编译瓶颈。
  2. 编译器必须在编译期间知道对象的大小
    1
    2
    3
    4
    int main(){
    Person p(args);
    ...
    }
    当编译器看到Person p(args),它必须明确一个Person对象需要分配多少内存,该问题的答案只有通过询问class定义式才能得到。然而如果class可以合法地不列出实现细目,编译器如何知道该分配多少空间?

接口与实现分离

 
前置声明的第二个问题在Java中根本不是问题,因为它在定义对象时编译器只分配足够空间给一个指针。也就是说,其具体实现效果大概是这样:

1
2
3
int main(){
Person *p;
}

pimpl设计模式

当然,我们也能在c++中这么做,将对象实现细目隐藏于一个指针背后。

pimpl实例

举例而言,对于Person我们可以:把person分割为两个classes,一个只提供接口,另一个负责实现该接口。其具体实现类名为PersonImpl。

1
2
3
4
5
6
7
8
9
10
11
#include <string>
#include <memroy>

class PersonImpl;
class Address;
class Person{
public:
...
private:
shared_ptr<PersonImpl> pImpl;
};

pimp分析

Person内部只含有一个指针成员指向实现类,这种设计被称为pimpl idiom(pointer to implementation)在这种设计下,Person的客户完全与Address以及Persons的实现细目分离。

该分离的关键在于以“声明的依存性”代替了“定义的依存性”,而这正是编译依存性最小化的本质:让头文件尽可能自我满足,否则就让它与其他文件内的声明式(而非定义式)相互依存。其设计策略大致有三:

  • 如果使用object references或者object pointers就可以完成任务,就不要使用objects。
    当你使用后者时,必须使用该类型的定义式。
  • 在条件允许的情况下,尽量用class声明式替换class定义式。
  • 为声明式和定义式提供不同的头文件。
    为了维持上述的两个准则,我们会定义两个一致的头文件,一个用于声明(Person.h),一个用于定义(PersonImpl.h)。客户程序显然总是应该#include声明文件而非前置声明若干函数。

Handle class

handle class 工作原理

像person这样使用pimpl idiom的classes往往被称为handle classes.其工作方法之一是把所有函数都转交给相应的实现类并由后者完成实际工作,如下所示

1
2
3
4
5
6
7
8
9
10
//"Person.cpp"
#include "Person.h"
#include "PersonImpl.h"

Person::Person(const string&name,const Address& addr)
:pImpl(new PersonImpl(name,addr)) {}//调用PersonImpl构造函数

const Address Person::getAddress() const{
return pImpl->address();
}

这里需要注意的是,Person以new调用PersonImpl的构造函数,任何操作都在调用PersonImpl对象的相关函数。让一个class变为handle class并不会改变它做的事,只会改变它做事的方法。

Interface class

除了使用pimpl,另一种制作handle class的方法是令Person成为一种特殊的abstract base class,我们称其为Interface class.
这种class的目的是详细描述derived classes的接口,因此它通常没有成员变量和构造函数,只有一个virtual析构函数以及一组pure virtual函数,用来叙述整个接口。
C++ 中的Interface class类似于java的Interfaces,但是略有不同,比如c++不禁止在interface内部实现成员变量或non-virtual成员函数。

Interface class实例

仍以Person为例:

1
2
3
4
5
6
7
class Person{
public:
virtual ~Person();
virtual const string getName() const = 0;
virtual const Address getAddress() const = 0;
...
}

该class的用户必须以指向Person的指针和或eference来编写应用程序,因为该类无法具现出实体。正如handle class的客户一样,除非interface class的接口发生改变,否则无需重新编译。

Interface class与对象构造

如何为Interface class创建新对象?
一般而言,我们会选择调用一个特殊函数,此函数扮演“真正将被具现化”的那个derived classes的构造函数角色。
这种函数通常称为factory函数或者virtual构造函数(详见More Effective C++ 25)其返回一个指针(或者智能指针)指向动态分配所得对象,而该对象又支持interface class的接口。此类函数一般被声明为static:

1
2
3
4
class person{
public:
static shared_ptr<person> create(const string &name,const Address &addr);
};

客户的使用操作如下所示:
1
2
3
4
5
string theName;
Address theAddress;
shared_ptr<person> pp(person::create(name,addr));//构建对象
cout << pp->getName();
//当pp离开作用域,对象自动删除

当然,支持Interface class接口的那个conrete class必须被定义出来,且真正的构造函数必须被调用。举例而言,我们现有一个具象类RealPerson继承自Person:
1
2
3
4
5
6
7
8
9
class RealPerson::public Person{
public:
RealPerson(const string& name,const Address& addr)
:theName(name),theAddr(addr) {}
...
private:
string theName;
Address theAddr;
}

那么create的定义式应当类似于如下形式(暂且忽略factory塑造不同类型对象的特性,仅仅把关注点置于构造)::
1
2
3
    shared_ptr<person> person::create(const string &name,const Addresss &addr){
return shared_ptr<person>(new realperson(name,addr));
}

handle class成本及风险

  • 在handle class中,成员函数必须通过一个implementation pointer取得对象数据,这无疑增加了访问的间接性。另外,implementation pointer必须初始化(在handle class内)指向一个动态分配的implementation object,所以我们还得承受动态分配和释放所带来的开销,以及遭遇bad_alloc的尴尬。
  • Interface class的每一个函数都是virtual,所以每一次函数使用都是一次间接函数指针访问,并且interface class派生的对象一定会含有一个vptr,这无疑增大了内存需求。(详见More Effective C++ 24)
  • handle class 与Interface class 都需要inline的支持。

总结

  1. 编译依存性最小化的一般构想:依赖于声明式而非定义式。基于此构想的两个实现分别是Handle class与Interface class.
  2. 程序库头文件应该有且仅有声明式,无论其是否涉及template。

33.在容器元素为指针时谨慎使用remove

Posted on 2018-04-16 | In Effective STL

问题实例

 
假设我们在管理一些动态分配的Widgets*:

1
2
3
4
5
6
7
8
class Widget{
public:
...
bool isCertified() const;//是否达标
...
};
vector<Widget*> v;
v.push_back(new Widget);//在容器中存放指针

最终需要删除所有没有通过检测的widget,所以下述写法似乎是十分自然的:
1
2
//关于谓词使用,详见Effective STL 41
v.erase(remove_if(v.begin(), v.end(),not1(mem_fun(&Widget::isCertified))), v.end());

Effective STL 7 告诉过我们删除容器内部的指针其实并没有析构对象本身,那是对的,但在这里内存泄漏在调用remove时就已经发生了。


问题剖析

 
假设在未调用remove_if之前,容器构成如下:
image_1cb5uru2u1ft11g8v1s3nm5h1h1l9.png-43kB
那么在调用之后,容器变成了这样:
image_1cb5utkms19gu1r2lfl71lm61h5tm.png-44.7kB
其实在这里我们就可以清楚地看到,我们再也无法通过某个指针来获取BC了,原本指向它们的指针被覆盖,BC将永远无法释放。
在调用erase之后,容器变成了这样:
image_1cb5uva5s1req8537v7blb1m2013.png-28.4kB
一般来说,在含有指针的容器中使用remove,remove_if或者unique不太合适。partition算法比较适合这类场景。(因为不存在覆盖的情况)


问题解决

依然erase_remove

我们可以先删除所有要删除的指针,并把它们设置为空,然后再抹除元素内所有空指针:

1
2
3
4
5
6
7
8
void delAndNullifyUncertified(Widget*& pWidget) {
if (!pWidget->isCertified()) {
delete pWidget;
pWidget = nullptr;
}
}
for_each(v.begin(), v.end(),delAndNullifyUncertified);
v.erase(remove(v.begin(), v.end(),[](Widget* pWidget){return pWidget;}),v.end());

智能指针

通过智能指针我们可以直接erase_remove:

1
2
3
4
typedef shared_ptr<Widget> SPW; // RCSPW = “RCSP to Widget”
vector<SPW> v;
v.push_back(RCSPW(new Widget));
v.erase(remove_if(v.begin(), v.end(),not1 (mem_fun(&Widget::isCertified))), v.end());

上述程序通过编译的前提是你的智能指针类型就必须可以隐式转换为相应的raw pointer。因为容器持有智能指针,但被调用的成员函数需要的是raw pointer。

31.inline函数剖析

Posted on 2018-04-15 | In Effective C++

前言

 
inline函数无论是看起来还是用起来都比宏更像函数而且更好用,调用它们又无需承受函数调用的额外开销。另外,编译器会对不含函数调用的程序执行语境相关最优化。然而,inline函数并不是完美无缺的。


inline的成本

 
inline的本质是“对函数的每一个调用”都以函数本体替换,这无疑增加了目标码(object code)大小,过度热衷inline可能会导致程序体积太大,随之导致额外的换页行为(page过多)。但是,如果inline函数很小,可能“函数本体”比“函数调用”所产出的代码更小,那当然是再好不过了。


inline申请

 
inline只是对编译器提出的申请。这个申请可以显式提出也可以隐式提出。

隐式inline

隐式就是把函数定义在class内部。一般而言这种隐式申请都是成员函数,不过friend函数也能被定义在class内(Effective C++ 47),如果真是那样,那它们也被隐式声明为inline.

显式inline

显式声明方法是在函数定义式前加上inline。以<algorithm>中的max template为例:

1
2
3
4
template<typename T>
inline const T& max(const T& a,const T& b){
return a<b?b:a;
}


inline与template

 
inline函数和template函数通常都会被定义在头文件中,所以有人会误以为function template一定是inline.这一点是错误的。
inline放在头文件的原因很简单,编译器需要在编译期将某个“函数调用”替换为“被调用函数的本体”。
template通常也放在头文件里,因为它一旦被使用,编译器为了具现化必须知道它的样子。
总之,template的具现化与inlining无关,如果你觉得所有据此template产生的function应该inline,那就声明它为inline,否则不必如此。


编译器决定是否inline

 
编译器拒绝将过于复杂的函数inline(带有循环或者递归),并且任何virtual函数的调用也会使inline落空。这是十分显然的,因为virtual意味着运行时才知道调用哪个函数,inline却是在编译期就必须确定。不过幸运的是,如果编译器拒绝了你的inline请求,会反馈一个警告信息。

有时候虽然编译器愿意inlining某个函数,但还是可能为该函数生成一个函数本体。
举例而言,如果某个函数需要取某一个inline函数的地址,那编译器会生成一个outlined函数本体,毕竟编译器无法去提出一个指针指向一个不存在的函数。

1
2
3
4
5
inline void f() {..};
void (*pf)() = f;//pf指向f
...
f();//确实inline
pf();//生成了函数实体并产生了调用


inline与构造、析构函数

 
假设有base class与derived class如下:

1
2
3
4
5
6
7
8
9
10
11
class Base{
public:
...
private:
string str;
};
class Derived::public Base{
public:
Derived() {}//空构造函数
...
};

Derived::Derived()看起来似乎很适合被inline,因为它根本不含任何代码,但实际并非如此。
构造或者析构函数内部存在着大量处理异常的程序,并且肯定存在着Base类的构造函数或者Derived析构函数。对这些函数的调用影响了编译器是否会对此空白函数inlining.
此外,这些代码如果被inline,那他们必然化身为object code充斥着各类Derived class.
总而言之,构造函数和析构函数不适合被声明为inline.


inline与程序库

 
程序库设计者使用inline之前必须考虑其影响性:inline无法随着程序库升级而升级。也就是说如果一旦某一个inline函数被改写,所有用到它的客户端程序都要重新编译。如果是non-inline,那用户只需要重新连接就好了。


inline与debug

 
我们无法在inline函数中设置断点,因为实际上并不存在这个函数。


总结

 

  1. 将inline函数限制在小型、频繁调用的函数身上,这会使潜在的代码膨胀问题最小化,程序速度提升机会最大化。
  2. 不要因为function template出现在头文件就把它声明为inline,这二者并不相关。

32.erase_remove惯用法

Posted on 2018-04-15 | In Effective STL

remove无法删除元素

 
remove的声明如下:

1
2
template<class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last,const T& value);

显然,remove算法操作迭代器而非容器,就像别的算法一样.
如果我们想从容器中去除某个元素,必然需要使用容器的成员函数erase,因为remove无法知道它正在操作的容器———因此有结论,从一个容器中remove元素不会改变元素个数。
1
2
3
4
5
6
7
8
9
vector<int> v;
v.reserve(10);
for (int i = 1; i <= 10; ++i) {
v.push_back(i);
}
cout << v.size();
v[3] = v[5] = v[9] = 99;
remove(v.begin(), v.end(), 99);
cout << v.size();//仍然是10

我们需要了解并记住的是:remove并不“真的”删除东西,因为它做不到。


remove的具体实现

 
remove移动指定区间中的元素,直到所有不需要“删除”的元素在区间开头,并且返回区间的“新逻辑终点”。一图胜千言:

  1. 调用remove之前
    image_1cb48ijia793d6a1smfgv539j9.png-16.5kB
  2. 执行remove
    1
    vector<int>::iterator newEnd(remove(v.begin(), v.end(), 99));
    image_1cb48kk5jh151qlf2iv1br2sb4m.png-19.1kB

然而,因为remove本质上并不是在改变区间元素顺序,所以?处仍然存在值,一般而言,真正的remove之后结果如下所示:
image_1cb4a9i721jea2001a4t1agn13i413.png-18.8kB
这是由于remove的实现所决定的,你可以想象remove完成了一种压缩去,被删除的值表演了被填充的角色,具体而言,其执行方略如下:

  1. remove检测v[0],发现无需删除,然后向后移动
  2. v[3]应该删除,于是记录v[3]需要被覆盖,移动到v[4]
  3. v[4]无需删除,将v[4]赋予v[3],记录v[4]应该被覆盖,移动到v[5]
  4. v[5]应该被删除,所以忽略并移动到6,此时记得4、5都应该被填充
  5. 诸如此类,移动过程如下图所示

image_1cb4ah4ep164kjup1jpns06hg31g.png-13.2kB


erase_remove惯用法

 
erase与remove是一对好搭档,我们应该很自然的配合使用:

1
2
vector<int> v;
v.erase(remove(v.begin(), v.end(), 99),v.end());

list是一个意外,它的remove综合了remove与erase的功能.
除此之外,remove_if与unique行为类似于remove,所以记得它们也应该配合erase使用。

30.为异常安全而努力

Posted on 2018-04-15 | In Effective C++

问题实例

 
假设存在一个class表示具备背景图案的GUI菜单。该class作用于多线程环境下,所以它有一个互斥器(mutex)作为并发控制(concurrency control)之用:

1
2
3
4
5
6
7
8
9
10
class PrettyMenu{
public:
...
void changeBackground(istream& imgSrc);
...
private:
Mutex mutex;
Image* bgImage;//原始图片资源
int imageChanges;//改变次数
};

下面是PrettyMenu的changeBackgroun的可能实现(糟糕实现):
1
2
3
4
5
6
7
void PrettyMenu:changeBackground(istream& imgSrc){
lock(&mutex);
delete bgImage;
++imageChanges;
bgImage = new Image(imgSrc);
unlock(&mutex);
}

异常安全有两个条件,而该函数没有满足其中任何一个条件。


异常安全的条件

 
当异常被抛出时,带有异常安全性的函数必须:

  1. 不泄露任何资源
    上述实例中如果new操作抛出异常,那么资源无法被unlock,也就是无法得到释放
  2. 不允许数据破坏
    上述实例中如果new抛出异常,bgImage将永久性地空悬。

确保异常安全

确保资源不被泄露

确保资源不被泄露的最佳方式是以RAII。(详见Effective C++ 资源管理篇)

确保数据不被破坏

异常安全保证

在解决数据破坏问题之前,必须要了解一些相关术语。首先是异常安全保证。


异常安全提供以下三个保证之一:

  • 基本承诺
    如果异常被抛出,程序的任何事物仍然保持有效状态。没有任何对象和数据结构因此遭到破坏,所有对象均满足内部前后一致(class约束条件仍然有效),但程序的现实状态不可预料。
    以实例为背景,我们可以确保在更换背景时如果抛出异常,对象会拥有原背景图案,或者对象会更改为某个默认背景图案,用户无法预期究竟会发生哪种情况。
  • 强烈保证
    如果运行期间存在异常被抛出,程序状态不改变。也就是说,运行成功则完全成功,失败则函数调用前的状态。
    这比基本承诺所提供的性能要强,因为它确保了程序只有两种状态(调用成功,调用前),而基本承诺具备多个多态的可能(调用成功,调用前,以及任一合法状态)。
  • nothrow保证(C++11引入noexcept修饰符)
    最高异常安全保证,确保程序在运行期间不会抛出任何异常,永远可以完成预期功能。所有内置类型都提供了nothrow保证(这也就是Effective C++ 26中认为swap处理内置类型及等价为异常安全的原因)。
    也许有人会认为具备空白异常明细(empty exception specification)者必为nothrow函数,其实并非如此,举例而言:
    int dosth() throw();
    这并非是说dosth不会抛出异常,而是说如果dosth抛出异常,将会执行set_unexpected函数(对程序而言是严重错误)。函数的声明(包括异常明细)并不能提供任何异常保证,所有性质均由实现来决定。

Exception-safe code必须提供上述三种保证之一,否则则不具备异常安全性。


异常安全保证的选择

nothrow自然是异常安全的最高追求,但很难做到。因为只要我们使用了动态内存,则不可避免地会接触bad_alloc异常。对于大部分函数而言,我们往往只在基本保证和强烈保证之间。


异常安全实例

仍以changeBackground为例,我们提供强烈保证只需要完成以下两点:

  1. 改用RAII
  2. 重排语句次序,保证对象的状态只会在过程确实完成后才会被改变。
1
2
3
4
5
6
7
8
9
10
class PrettyMenu{
...
shared_ptr<Image> bgImage;
...
}
void PrettyMenu::changeBackground(istream& imgSrc){
Lock m1(&mutex);
bgImage.reset(new Image(imgSrc));
++imageChanges;
}

值得注意的是,这里无需手动delete,且reset中delete执行依赖于新图像的成果创建。也就是说如果new跑出了异常,原本的资源不会遭到破坏,程序依然维持着执行前的状态。


强烈保证的设计策略(copy and swap)

copy and swap能够很轻松的实现强烈保证,其原理很简单:当为你所需要修改的对象构造一份副本,然后在副本上执行修改,修改完成后swap副本与原件。如果在修改期间发生了异常,我们可以保证原件并没有遭到破坏。
其具体实现手法是:将所有“隶属于对象的数据”从原对象放入另一个对象,然后赋予原对象一个指针指向具体实现对象。(pimpl设计模式,详见Effective C++ 32)。对于PrettyMenu而言,其具体写法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct PMImpl{
shared_ptr<Image> bgImage;
int imageChanges;
};
class PrettyMenu{
...
private:
Mutex mutex;
shared_ptr<PMImpl> pImpl;
};
void PrettyMenu::changeBackground(istream& imgSrc){
using std::swap;//详见Effective C++ 26
Lock m1(&mutex);
shared_ptr<PMimpl> pNew(new PMImpl(*pImpl));//构造副本
pNew->bgImage.reset(new Image(imgSrc));//修改副本
++pNew->imageChanges;
swap(pImpl,pNew);//置换
}

以下逐步分析本例中copy and swap的具体操作:

  1. RAII要求了原始资源Image需要被一个智能指针所持有,所以bgImage是一个智能指针对象。
  2. 与PrettyMenu直接有关的数据除了背景图之外,还有背景图变换次数int imageChanges。
  3. 将bgImage与imageChanges打包,封装成为一个新的具体实现对象PMimpl。
  4. 在PrettyMenu中存有指向具体实现的指针shared_ptr pImpl.具体实现对象PMimpl同样是一种资源,所以再次使用了RAII,该指针pImpl为private。
  5. pImpl的私有性保证了PMImpl无法被客户直接访问,因此将其设为strcut并不影响数据封装性。
  6. 在copy动作中,最先执行的是new PMimpl(*pImpl)语句。该语句在heap上建立了一个PMImpl对象,调用了PMImpl默认拷贝构造函数。
  7. PMImpl的默认拷贝构造函数对于int数据采取了逐bit拷贝,对于shared_ptr对象则调用了其默认拷贝构造函数。
  8. shared_ptr<Image>默认拷贝构造函数执行,计数器自增,此时有两个智能指针指向原始图像资源。至此,PMImpl构造完毕。
  9. pNew执行构造函数,接受一个指向heap中的PMImpl对象,RAII执行完毕,资源被封存入pNew中进行管理。
    pNew作为原有数据的副本,其raw pointer指向PMImpl对象,PMImp对象内部存有一个int与一个shared_ptr,该智能指针指向原始图像资源,该资源的引用计数为2。
  10. 通过new Image语句构造了一个位于heap中的Image对象,将其作为reset的实参。
  11. pNew通过解引用访问PMimpl对象的bgImage,对bgImage执行reset操作。
  12. bgImage并非唯一指向原始资源的智能指针,因此原始图像资源并未析构,计数器自减。bgImage指向新构造的Image对象。
  13. pNew中的背景更换次数自增,执行swap(pImpl,pNew);
  14. pImpl和pNew交换了彼此所指向的对象,此时pImpl指向了一个位于heap中的PMImpl对象,其bgImage指向了新构建的Image对象,且其int数据已发生过自增。
  15. 控制流离开changeBackground程序块,位于stack中的pNew对象开始析构。由于pNew是唯一指向原有PMImpl对象的智能指针,原有PMImpl执行析构函数。
  16. 原有PMImpl中的int内置类型没有析构函数,bgImage开始析构。
  17. bgImage为唯一指向原有原始图像资源的智能指针,原有原始图像资源析构。至此copy and swap执行完毕。

强烈保证的连带效应

使用copy and swap能够做到令对象状态保证“成功或回退”,但一般而言它并不保证整个函数具备强烈保证,举例而言,假设Func是一个执行了copy and swap的函数:

1
2
3
4
5
6
void Func(){
...
f1();
f2();
...
}

显然,如果f1或者f2其异常安全性低于强烈保证,那么很难保证Func具备强烈保证。就算f1与f2都具备强烈保证,Func也未必具备强烈保证。举例而言,假若f1成功执行,f2执行失败,对象状态回退至f1执行之后f2执行之前,显然此时Func不具备强烈保证。


copy and swap引发的效率问题

copy and swap的精要在于copy被修改的对象,为此我们需要付出构造与析构的成本。pimpl模式下的copy and swap消耗极低,但这并不意味着你每一次都只是构造一个指针而已。


基本保证

 
当强烈保证不切实际之时,我们应该考虑基本保证。基本保证是异常安全的最后一道屏障,如果无法满足则无法被称为异常安全。
异常安全并没有局部与整体的概念,只要某一处不具备异常安全性,即可视作整个程序不具备异常安全性。


总结

  1. 异常安全函数即使发生异常也不会导致资源泄露或者数据破坏。其函数提供分为三种可能的保证:基本、强烈、不抛异常。
  2. copy and swap可能实现强烈保证,但其并非对所有函数都可实现或具备实现意义。
  3. 异常安全具备全局性,其等于最弱的局部异常保证。

31.了解各类排序算法

Posted on 2018-04-15 | In Effective STL

前言

 
绝大多数人在听到排序之后只会想到sort,当然,sort是一个优秀的算法,只是我们有时候不一定非要用它。


部分排序

 
假设当前我们只需要找出某堆Widget中前20个质量最好的,剩下的不用管它,那么这个时候执行全排无疑是不必要的,我们所需要的仅仅只是partial_sort:

1
2
3
4
5
6
bool qualityCompare(const Widget& lhs, const Widget& rhs){
//返回lhs的质量是不是比rhs的质量好
}
...
//把质量最好的20个Widget按顺序放在容器前端
partial_sort(widgets.begin(), widgets.begin() + 20,widgets.end(),qualityCompare);


无需有序排列的部分排序

 
有时候需求比部分排序还要少,我们只需要找出前20个质量好的,根本不要求它们被找到后依次排好序,此时我们可以调用这个算法nth_element。
nth_element排序一个区间,在ri(用户指定)位置的元素是如果区间被完全排序会出现的元素,当nth_element返回时,在n以上的元素必然就是全排之后的前n个.具体使用如下:

1
nth_element(widgets.begin(), widgets.begin() + 19, widgets.end(), qualityCompare);

我怀疑partial_sort内部调用了nth_element,然后再对前n个进行了排序。

稳定性

这两种算法均不具备稳定,如果你需要稳定性,请使用stable_sort。STL并不包含partial_sort和nth_element的稳定版本。

nth_element的额外用途:查找

nth_element不仅仅能够帮我们找到区间顶部的n个元素,还能够轻易找出区间中值或者在指定百分点的元素:

1
2
3
4
5
vector<Widget>::iterator begin(widgets.begin()); 
vector<Widget>::iterator end(widgets.end());
vector<Widget>::iterator goalPosition;
goalPosition = begin + widgets.size() / 2;
nth_element(begin, goalPosition, end,qualityCompare);//此时goalPosition指向中值

原理很简单,上文已经提及:在调用算法后,在ri(用户指定)位置的元素是如果区间被完全排序会出现的元素。


分割容器

 
有时候我们并不需要排序,我们只需要简单粗暴的根据某一个判定依据,把元素分成一堆,和另外一堆,这个时候partition来了,它重排区间中的元素,使满足某个标准的元素都在区间的开头。

1
2
3
4
5
bool hasAcceptableQuality(const Widget& w){
//返回w质量等级是否是2或更高;
}
//返回指向第一个不符合条件元素的迭代器
auto goodEnd =partition(widgets.begin(), widgets.end(), hasAcceptableQuality);

如果你需要稳定性,记得使用stable_partition.


上述算法对迭代器的要求

 
算法sort,partial_sort,stable_sort和nth_element需要随机访问迭代器,那也就是说只能用于vector、string、deque与array。
list的sort是稳定的,但如果想使用partial_sort或者nth_element,只能间接完成:

  • 拷贝list到一个vector或者别的支持随机访问迭代器的容器中
  • 建立一个list::iterator的容器,对该容器使用算法,通过迭代器访问元素。(算法谓词完成解引用)

partition与stable_partition只需要双向迭代器,所以可以在任何容器上使用。


算法性能比较

 
以上算法性能由高到低可以排序为:
partition>stable_partition>nth_element>partial_sort>sort>stable_sort

29.避免返回指向对象内部成分的handles

Posted on 2018-04-15 | In Effective C++

问题实例

 
假设存在一个矩形类,以左上角和右下角的一个坐标表示其形状。为了让该类尽可能小,我们决定将定义矩形的点移出该类,放在一个辅助的struct中,再用Rectangle指向它:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Point{
public:
Point(int x,int y);
...
void setX(int newVal);
void setY(int newVal);
...
}
Struct RectData{
Point ulhc;//upper left-hand corner
Point lrhc;//lower right-hand corner
};
class Rectangle{
...
private:
shared_ptr<RectData> pData;
}

显然,用户需要了解矩形的范围,因此矩形类有成员函数如下:
1
2
3
4
class Rectangle{
Point& upperLeft() const {return pData->ulhc;}//返回引用
Point& lowerRight() const {return pData->lrhc;}
}

这种设计是错误的,因为存在自我矛盾。


案例分析

bitwise constness

在上述代码中,我们用const修饰函数,因为我们希望该函数不能修改point。但是事实上,尽管该函数并未修改数据,但是我们却可以通过其返回值修改对象的private数据,从而丧失了const性质。(详见Effective C++ 4 bitwise constness与logical constness)

指向对象内部成分的handles

这个案例提供了两个教训:

  1. 成员变量的封装性最多只等于返回其reference的函数的访问级别
    在上述代码中,尽管ulhc与lrhc被声明为private,但它们实际上是public,因为我们可以通过public成员函数获取其reference。
  2. 如果const函数返回了一个reference,那么该函数的调用者可以修改数据,不受const的制约。
    这个道理很简单,函数本身受到了const制约,但其返回值却可以自由修改。

handles定义

并非仅有reference是handles,指针、迭代器都属于handles,它们都具备返回一个“代表对象内部数据”的能力。

对象内部成分

不仅仅成员变量才算是某个对象的内部成分,被声明为protected与private的成员函数同样算是对象的内部成分,注意不要返回它们的handles,因为如果你这么做了,后者的访问级别可能会得到提高。(不再受到protected、private的保护,而是可能任由客户调用)


解决方案

 
为了避免封装性遭到大幅度破坏,我们针对此案例的解决方法是:使用const来修饰返回的handles。我们出让了对象内部的读取权,写入仍然是被禁止的。

空悬handle

但即使如此,返回对象内部成分的handles还有可能造成其他问题,比如dangling handles(所指向的对象不复存在)。其最常见翻车现场就是函数返回值。
假设某个函数返回一个GUI对象的外框,其外框是一个矩形:

1
2
class GUIObject{...};
const Rectangle boundingBox(const GUIObject& obj);

客户可能会这么使用它:
1
2
3
GUIobject *pgo;
...
const Point* pUpperLeft = &(boundingBox(*pgo).upperLeft());

在本次使用中,boundingBox函数建立了一个局部无名的Rectangle对象,并将其内部handles绑定到了一个指针中。关键在于,当该语句执行结束后,无名对象被销毁,可pUpperLeft仍然指向着其内部成分,也就是说,pUpperLeft成为了一个空悬指针。


总结

 
函数返回一个指向对象内部成分的handle总是带有风险的,但这并不意味着你绝不可以返回handle,比如operator[]总是返回容器内部元素的reference.但这样的函数终究是例外而非常态。
如果无法避免的话,记得为const成员函数的返回值也添上const属性。

30.使用算法前确保目标区间足够大

Posted on 2018-04-15 | In Effective STL

问题实例

 
我们习惯了STL容器的自动扩张,因此可能会写下一些愚蠢的程序,举例而言:

1
2
3
4
5
6
int transmogrify(int x);//产生一个自变量是x的因变量
vector<int> values;
... // 把数据放入values
vector<int> results;
//对values中的所有元素使用函数,将结果插入res尾部
transform(values.begin(), values.end(),results.end(),transmogrify);

在本例中,transform调用了*res.end(),也就是说我们试图对一个不存在的对象赋值。


解决方案

插入迭代器

插入于结尾处

transform的结果放入结尾应该使用back_inserter来产生指向res末尾的迭代器:

1
2
vector<int> results; 
transform(values.begin(), values.end(), back_inserter(results), transmogrify);

插入于最前端

如果你试图在最前端插入,当然可以用front_inserter,只是这样支持的容器只剩了list与deque.
如果依次添加到最前面,那么最终顺序与values对应的顺序不一致(正好相反),解决方法也简单,调用反向迭代器即可:

1
2
list<int> results;
transform(values.rbegin(), values.rend(),front_inserter(results), transmogrify);

在任意位置插入

inserter迭代器允许你强制算法把结果插入在任何位置:

1
2
vector<int> results;// results已经有一些数据
transform(values.begin(), values.end(), inserter(results, results.begin()+results.size()/2), transmogrify);

提高效率

每一次都只插入了一个对象,因此可能会造成线性表频繁的复制与扩容。对于复制没有什么优化思路,但至少可以使用reserve来减少再分配所带来的开销:

1
2
3
4
5
6
7
vector<int> values; 
vector<int> results;
...
results.reserve(results.size() + values.size());
transform(values.begin(), values.end(),
inserter(results, results.begin() + results.size() / 2),
transmogrify); //无需扩容

替换而非插入

有时候我们要做的操作并不是插入而是替换,但这并不影响我们是否需要判断results的大小,解决方法要么resize,要么clear之后使用插入迭代器:

1
2
3
4
5
6
7
8
9
//resize法
if (results.size() < values.size()){ //确保大小
results.resize(values.size());
}
transform(values.begin(), values.end(),results.begin(), transmogrify);
//clear之后插入
results.clear();
results.reserve(values.size()); // 扩容优化
transform(values.begin(), values.end(),back_inserter(results),transmogrify);


总结

 
当我们使用一个要求指定目的区间的算法时,务必要确保目的区间已经足够大或者在算法执行时可以增加大小。如果需要增加大小,记得使用插入迭代器。

<i class="fa fa-angle-left"></i>1…202122…27<i class="fa fa-angle-right"></i>

xander.liu

266 posts
11 categories
36 tags
RSS
GitHub E-Mail
© 2024 xander.liu
Powered by Hexo
|
Theme — NexT.Pisces v5.1.4