STL使用上的更多细节

| 分类 c/c++之STL  c/c++之多线程  | 标签 c++  多态  继承  异常  shared_ptr  操作符重载  STL  delphi  算法  数据结构  函数  函数对象  面向对象  封装  模板  智能指针  Boost  字符串  引用计数  标准 

一直以来我使用C++的语法集就是C - 宏 + 面向对象,对于更多的C++的高级语法,比如模板、智能指针、STL等都完全没有用到,或者说我在刻意规避这些语法,因为具有较高的复杂性,不易理解和使用,而且很依赖于不同的C++编译器实现、不同的STL库实现,所以如果既在Windows下用VC++开发,又在Linux下用GUN g++开发,可能会有一些令人困惑的差异

无奈,可能会发生的事情终会发生,C++的高级语法的应用还是无法规避,比如STL对数据结构和算法的封装确实在编程中使用起来带来了较大的方便,省得自己再编写基础的代码了!下面通过参考诸多资料整理STL使用上的一些注意事项

STL中包括四大部分:容器、迭代器、算法、函数对象

关于STL用法的总结,其实就是处处对于C++语法、时间复杂度、空间复杂度的思考与权衡

STL容器是基于拷贝的

比如下面这份代码

class Base{
protected:
    int i;
public:
    ...
    Base(const Base&);            //拷贝构造函数
    Base& operator=(const Base&); //拷贝赋值操作符
    ...
};

这里面我显式声明了拷贝构造函数、拷贝赋值操作符,如果程序员在设计类的时候没有显式给定拷贝构造函数和拷贝赋值操作符,那么编译器会为你声明

比如像下面这样往容器中放入该类的对象时

vector<Base> vb;
Base b;
vb.push_back(b);

那么其是这样的运行效果:一个对象被保存到容器中,它会经过进一步被拷贝,也就是说,并不是将上面的这个b对象本身放到vector中,而是对b进行一次拷贝,将拷贝得到的对象放到vector中。STL的容器通过在堆内存上对元素进行管理,vector是根据需要动态申请/释放连续内存、list是根据需要动态申请/释放节点

很明显,这里存在一个问题,假如Base类很大,那么每次将Base对象放到容器中都要经过拷贝,那么明显会成为程序的一个性能瓶颈

下面再看一个实例程序:

class Derived: public Base{
protected:
    float f;    //相比于父类多了一个float f成员
    ...
};

vector<Base> vb;
Derived d;
vb.push_back(d);

上面这段代码存在一个让人意外的问题:因为vector<Base>声明的是基于Base的容器,而d是Derived的,所以将d拷贝到vector<Base>的过程中,它的派生类特有部分会丢失,那么面向对象的多态性质在这种情况下就丢失了

很简单的一个向容器中放入数据的动作就存在这么多令人意外的细节。其实也有办法来避免这些问题,就是使用对象指针而不是对象本身,这样既可以提升拷贝的速度(此时拷贝的是对象指针,而不是对象本身了)、而且多态性质也保持住了(其实多态的基础是父类的指针指向子类的对象实体,必须是依赖于指针的。比如Python中因为没有指针,所以是没有多态机制的)

vector<Base *> vb;         //声明一个vector容器
Base *b = new Derived();   //创建一个子类对象,通过父类指针指向它
b = NULL;
vb.push_back(b);           //将指针放入容器(拷贝指针)

//中间是对容器的管理、读写等操作
....

//最后释放资源
vector<Base *>::iterator it;
for(it = vb.begin(); it != vb.end(); it++)
    delete *it;
vb.clear();

上面的代码在使用完vector之后,没有忘记因为vector中存放的是对象指针,所以要进行delete防止资源泄露

但是问题总是一个接着一个:如果在使用的过程中出现了异常,导致delete的逻辑被跳过了,那还不是会出现资源泄露?

C++不像C,还有异常这么个鬼东西可能影响程序的运行逻辑,那也只能祭出智能指针这个神器了,shared_ptr具有引用计数机制,可以很好的实现对内存的有效管理

typedef boost::shared_ptr<Base> SPB;  //SPB是指向Base的shared_ptr
vector<SPB> vspb;
//往容器中放入数据
vspb.push_back(SPB(new Derived));     //可以关注一下这里智能指针的用法

//中间是对于容器的管理、使用等操作
...

//最后不需要显式释放资源

当使用指针的容器,而其中的指针应该被删除时,为了避免因为编码遗漏或者异常导致的资源泄漏,应该使用引用计数形式的智能指针对象代替普通指针!

如果不用引用计数的智能指针,那么就需要在代码中考虑到异常的可能性,比如在Delphi中,使用异常保护机制,在finally代码块中释放资源,保证在出现异常的情况下也一定能释放资源

try
    try
        //可能有异常的代码块
        //...
    except
        on E: Exception do
        begin
            //异常处理
        end;
    end;
finally
    //资源释放
end;

但是在标准C++中并没有finally代码块(__try、__except、__finally是Windows的SEH机制,并不是C++标准)

try{
    //可能有异常的代码块
}
catch(int){
    cout << "Error Int" << endl;
}
catch(MyException e){
    cout << "MyException" << endl;
}
catch(...){
    cout << "Other Exception" << endl;
}

所以C++中还是使用智能指针来管理更稳妥一点,除非你保证利用上面C++支持的异常处理机制,保证在不管是否出现异常的情况下都能正确释放资源,不过这确实有难度!

序列容器

数据结构中的序列容器可以按照如此方式分类:连续内存容器和基于节点的容器

连续内存容器(也称基于数组的容器)把它的元素存放在一块或多块(动态分配的)内存中,每块内存中存有多个元素。当有新元素插入或已有元素被删除时,同一内存块中的其他元素都要向前或向后移动,以便为新元素让出空间,或者填充被删除元素留下的空隙。这种移动影响到效率和异常安全性。在STL中标准的连续内存容器有vector、string、deque,非标准的rope也是一个连续内容容器

典型的连续内存容器就是C++中的原始数组

image

基于节点的容器在每一个(动态分配的)内存块中只存放一个元素。容器中元素的插入和删除只影响到指向节点的指针,而不影响节点本身的内容,所以当有插入和删除操作时,元素的值不需要移动。表示链表的容器,如list是基于节点的,所有标准的关联容器,比如map也是基于节点的(通常使用平衡树、或红黑树实现)

典型的基于节点的容器就是下面这种链表实现

image

连续内存容器的特点是可以实现随机读取、修改,但新增和删除的时间复杂度就很高,因为需要内存块中的其他节点因为新节点插入或老节点删除而向前或向后移动;而基于节点容器则可以快速实现新增和删除,因为不需要移动其他节点,只需要调整前后节点的指针即可,但在搜索节点时就比较慢了,需要从第一个节点开始向后逐个和要搜索的对象进行对比

上面讲到连续内存容器和基于节点的容器在时间复杂度上各自的优势和缺陷。世上事情总是这样,甲、乙,往往只能是甲在A方面很极致,在B方面比较弱,而乙在A方面比较弱,却在B方面比较极致,最后为了平衡,总是将甲和乙做结合,得到一个各方面都比较适中的、中庸的解决方案。比如很多产品中将连续内存方案和基于节点的方案结合起来得到下面这样的数据结构

image

当然如果你的程序大部分操作是新增和删除操作,而没有搜索,那么就直接选择基于节点的数据结构。总之还是要根据自己的实际需求选择最适合的数据结构

关联容器

上面讲的是线性结构(序列容器),使用树形结构或其他结构(比如STL中map之类的关联容器)按照一定的规则组织数据的话,实现搜索会快很多,可是因为如此性能是建立在严格的结构规则上的,在新增或删除节点时,为了维持原有的结构规则,往往需要对其他节点做调整,这时就无法像线性结构一样有O(1)的时间复杂度了。比如大顶堆在新增和删除元素时,不能直接新增或删除,必须要继续按照大顶堆的结构规则做调整

STL中的容器多是基于平衡树或红黑树实现的!

二叉查找树是一个二叉树结构,对于这个二叉树中的每个节点X,它的左子树中的节点都小于X节点的关键字值,而右子树中的节点都大于X节点的关键字值

平衡二叉树也称AVL树,它本质上也是二叉查找树,只是它比较特殊,要求树中任何节点的两个子树的高度差最大为1

红黑树也是一种二叉查找树,但在每个节点上都增加了一个颜色属性(红或黑),它有五个属性:

  1. 每个节点要么是红要么是黑
  2. 根节点是黑的
  3. 所有的叶子节点都是黑节点
  4. 红节点的字节点一定是黑节点
  5. 从任何一个节点到叶子节点所有路径上的黑节点数目相同

通过这5条性质,对红黑树的每个节点的着色方式进行了限制,这样红黑树没有一条路径会比其他路径长2倍,因此红黑树是接近于平衡的

字符串string

通过《C++对象内存模型:C++的string和Delphi的string》《标准C++类std::string的内存共享和Copy-On-Write技术》等文章可以知道Delphi6中的string是使用引用计数实现的,而C++ STL中的string大部分实现方式也都是使用了引用计数机制的!

如果在你的程序中不介意引用计数机制,那么字符串类型直接选择使用std::string即可,但如果介意使用引用计数,那么就要避免使用std::string了,可以选择使用vector<char>来表示字符串

string的引用计数并不是绝对的。这就涉及到软件工程中常说的接口和实现有关,不同的STL实现对外的接口是按照一个固定标准的,但其内部实现可能不同的STL有自己不同的选择,有的用引用计数,有的则不用。所以接口是标准,实现不是标准

不同的STL实现中,有的使用了引用计数机制,有的没有使用,而且不同的STL实现中,对于string的内存模型的设计也可能是天差地别的!

使用锁的一种技巧

在Delphi编码中,习惯于像下面这样进行锁的使用,保证在出现异常的情况下也能释放锁

Lock();
try
    //同步保护的区域
finally
    UnLock();
end;

上面省略了异常捕获和异常处理的部分,因为这里只展示finally的用法!

正如前面所提到的,C++标准中并没有finally语法,怎么保证使用标准C++进行加锁时,就算出现异常也会释放掉锁呢?其实可以利用C++中对象的生命周期来实现!

//定义一个为容器获取和释放互斥体的模板
template<typename Container>
class Lock(){
public:
    //在构造函数中获取锁
    Lock(const Container & container):c(container){
        getMutexFor(c);
    }
    //在析构函数中释放锁
    ~Lock(){
        releaseMutexFor(c);
    }
private:
    const Container& c;
};


//下面是利用对象的生命周期来巧妙的管理锁
vector<int> v;
...
{//创建新的代码块
    Lock<vector<int> > lock(v);  //声明类,其实这里有调用构造函数,所以就获得了锁
    vector<int>::iterator it;
    for(it = v.begin(); it != v.end(); it++){
        //...
    }
}//代码块结束。lock对象生命期结束,这里调用析构函数,所以就释放了锁

详细的解释已经在上述代码中体现出来了。就算在代码块之间出现异常,C++也能保证只要跳出代码块就结束该对象的生命!

函数对象

函数和类似于函数的对象(函数子)在STL中到处都可以看到。关联容器利用它们为元素进行排序、find_if使用它们来控制算法的行为。如果不知道如何编写行为良好的函数子,那么想有效的使用STL也是不大可能的

在Python、Lisp这些支持函数式编程的语言中,可以直接把函数作为参数传给另一个函数,而在C、C++中是不允许将一个函数作为参数传递给另一个函数的,只允许你传递函数指针

STL中的函数对象是函数指针的一种抽象和建模形式,所以,按照惯例,在STL中,函数对象在函数之间来回传递的时候也是按值传递(被复制)的。标准库中的for_each算法需要一个函数对象作为参数,同时其返回值也是一个函数对象,而且都是按值传递的,声明如下

template<class InputIterator, class Function>
Function                         //返回值按值返回
for_each(InputIterator first, 
         Inputiterator last, 
         Function f)             //参数按值传递

因为在STL中函数对象是按值传递的,所以在设计函数对象的时候必须时刻考虑到这一点

注意是for_each()等函数中传入参数和返回值时要求函数对象参数按值传入和返回,而不是要求函数对象的operator()重载定义时按值传入和返回的。这是两个不同层次的概念

由于函数对象是按值传递和返回,所以,你必须确保你编写的函数对象在经过了传递之后还能正常工作。所以:

  • 你的函数对象最好是尽可能小,否则复制的开销会很昂贵
  • 函数对象必须是单态的(不是多态的),也就是说,它们不能使用虚函数。如果参数的类型是父类,而传入的实参是派生类,那么在传递的过程中会剥离掉派生类部分,仅保留基类部分,这个在本文的第一部分讲容器的拷贝机制的时候有讲到

STL中函数对象是必须要进行按值返回与按值传递的、如果又想使用多态,那么如何解决这个矛盾?

解决方法其实也很简单:将需要的数据和虚函数从函数之类中分离出来,放到一个新的类中,然后在函数子类中包含一个指针,指向这个新类的对象

例如,如果你希望创建一个包含大量数据并且使用了多态性的函数子类:

template<typename T>
class BPFC: public unary_function<T, void>{
private:
    Base b;    //该类包含大量数据,所以传值效率很低
    int x;
    ...
public:
    virtual void operator()(const T& val) const;   //这是一个虚函数,所以存在剥离问题
    ...
};

可以修改为这样的方式:创建一个小巧的、单态的类,其中包含一个指针,指向另一个实现类,并且将所有的数据和虚函数都放在实现类中:

template<typename T>
class BPFCImpl: public unary_function<T, void>{
private:
    //原来BPFC中的数据都放在这里
    Base b;
    int x;
    ...
    virtual ~BPFCImpl();      //多态类需要虚函数
    virtual void operator()(const T& val) const;

friend class BPFC<T>;         //允许BPFC访问内部数据
};

//新的BPFC类:短小、单态
template<typename T>
class BPFC: public unary_function<T void>{
private:
    BPFCImpl<T> *pImpl;       //BPFC唯一的数据成员
public:
    //现在这是唯一的非虚函数,将调用转到BPFCImpl中
    void operator()(const T& val) const
    {
        pImpl->operator()(val);
    }
};

使用短小的、单态的函数对象对庞大的、多态的函数对象做一个转换!

相等 VS 等价

何谓相等性?何谓等价性?

在STL中,对两个对象进行比较,看它们的值是否相等,像这样的操作随处可见,比如当通过find在某个区间寻找一个等于某个值的元素,find必须能够比较两个对象,看一个对象的值是否等于另一个对象的值。与此类似,当试图把一个新元素插入到set中是,set::insert必须能够确定元素的值是否已经在该set中

find算法和set的insert成员函数只是两个有代表性的函数,在STL中有许多这样的函数,它们需要确定两个值是否相同。但这些函数以不同的方式来判断两个值是否相同。find对“相同”的定义是相等,是以operator==为基础的。set::insert对“相同”的定义是等价,是以operator<为基础的。因为两个定义不同,所以,有可能用一个定义断定两个对象有相同的值,而用另一个定义断定它们的值不相同。这样导致的后果是,如果你要有效地使用STL,就要理解“相等”和“等价”的区别

相等的概念是基于operator==的,如果表达式x == y返回true,则x和y相等,否则就不相等。这个很直接明了

等价关系是在关联容器中的概念

而等价关系是以“在已排序的区间中对象值的相对顺序”为基础的。如果从每个标准关联容器(set、map、multiset、multimap)的排列顺序来考虑等价关系,那么将是有意义的。对于两个对象x、y,如果按照关联容器c的排列顺序,每个都不在另一个的前面,那么称这两个对象按照c的排列顺序有等价的值。比如set s,如果Base b1, b2,在s的排列顺序中那个也不在另一个的前面,那么b1和b2对于s而言是等价的值。set的默认比较函数是less,而在默认情况下less只是简单的调用Base的operator<,所以,如果下面的表达式为真,则b1和b2对于operator<有等价的值

(!(b1 < b2)) && (!(b2 < b1))

表示如果两个值中的任意一个(按一定的排列准则)都不在另一个的前面,那么这两个值(按照这一准则)就是等价的

一般情况下,一个关联容器的比较函数并不是operator<,甚至也不是less,而是用户自定义的判别式。每个标准关联容器都通过key_comp成员函数使排列判别式可以被外部使用,所以,如果下面的表达式为true,则按照关联容器c的排序准则,两个对象x和y有等价的值

!c.key_comp()(x, y) && !c.key_comp()(y, x)

其中key_comp是一个函数类,调用key_comp()会返回一个函数对象,并以x和y作为传入参数!

在STL的算法实现中,count和find使用相等性进行搜索,而binary_search、lower_bound()、upper_bound()和equal_range()则使用了等价性

在第一部分讲到为了避免拷贝的性能消耗和保持面向对象的多态性质,最好使用普通指针或智能指针放到容器,那就又存在了一个问题,默认的比较函数就无法使用了!所以就需要为包含指针的容器指定比较类型!

算法调用优先于手写的循环

首先列举一下使用算法比程序员自己写循环的诸多好处:

  • 效率:算法通常比程序员自己写的循环效率更高
  • 正确性:自己写循环比使用算法更容易出错
  • 可维护性:使用算法的代码通常比手写循环的代码更加简洁明了

因为STL算法内部实现都是循环,而STL算法涉及面很广,所以这就意味着你本该编写循环完成的任务完全可以用STL算法实现

比如一个这样的类:

class Base{
public:
    ...
    void doSomeThing() const;
    ...
};

如果要循环调用list中所有Base对象的doSomeThing的时候,可以自己写循环完成

list<Base> lb;
...
for(list<Base>::iterator it = lb.begin(); it != lb.end(); it++){
    it->doSomeThing();
}

另外完全可以使用for_each算法实现

for_each(lb.begin(), lb.end(), 
         mem_fun_ref(&Base::doSomeThing));

简单的分析。自己写的循环中,每次迭代都要检查it是否为end(),而使用for_each()则只需要调用一次,这也是使用STL算法性能更好的原因之一;而且很明显,后一种代码风格简洁清晰多了!

怎么选择算法

和上面提到我们在选择序列容器时是选择连续内存的序列容器还是基于节点的序列容器,并没有一套绝对的答案,只有适合二字。在选择算法时也是一样,首先要弄清楚我们要解决什么样的问题,然后再确定该选择什么方案

最好的方案就是刚刚好满足解决问题需求的算法,不少做也不多做

不少做可以理解,因为少做了功能性的需求就不能达到了。不多做则是在进行算法选择、性能调优时的一个核心指标。比如我们要判断容器是否为空,就应该选择调用empty()判断,而不应该调用0 == size()来判断,因为前者不多不少正好满足了需求,而调用0 == size()则多做了很多事情,它要先去获取容器中具体有多少个元素,对于有的容器实现,可能专门设计一个成员变量存储元素的个数,那么直接调用size()就是一个O(1)的操作,而还有一些实现方式因为种种限制,可能在调用size()的时候,需要从头开始遍历获取元素的个数,那么时间复杂度就是O(N)了,明显性能更差了。当然实际远不止这一个例子!如何选择不多不少的合适的算法方案,就要求开发者对于算法和数据结构本身的熟悉度了!

STL实现了70多个算法,每种算法的原理、什么情形下适用什么算法……还需要更多的实践总结经验!

STL的其他部分

上面讲了不少东西,但没讲到的东西更多

STL是以泛化原则为基础的:数组被泛化为“以其包含的对象的类型为参数”的容器;函数被泛化为“以其使用的迭代器的类型为参数”的算法;指针被泛化为“以其指向的对象的类型为参数”的迭代器。关于泛化的思想,目前也无力讲明白

关于string的各种不同实现的不同内存布局、string的引用计数机制,这里不做讲解,大多数的原理和Delphi 的string是一致的

文中提到的宏、C++中的函数对象等内容其实和Lisp函数式编程思想都能产生一些联系,这里因为自己接触不深,所以目前也没有办法做过多的讨论

对线性结构通过图形等方式做了详细的描述,但是树形结构只是简单的提一下概念!

除了标准的序列容器、关联容器,其实还有非标准的散列容器,关于其中的散列算法、散列函数、桶等概念和细节,本文也没有涉及

再给出一些STL使用上的建议

  • 当效率至关重要时,需要在map::operator[]与map::insert()之间谨慎做选择
  • iterator优先于const_iterator、reverse_iterator和const_reverse_iterator
  • 对于逐个字符的输入考虑使用istreambuf_iterator
  • 确保less和operator<具有相同的语义
  • 容器的成员函数优先于同名的算法。几乎可以肯定的说,成员函数的性能更为优越,而且它们更能与容器的一贯行为保持一致

推荐一些相关的Web站点




如果本篇文章对您有所帮助,您可以通过微信(左)或支付宝(右)对作者进行打赏!


上一篇     下一篇