当前位置:   article > 正文

C++的营养——swap手法_c++swap复杂度

c++swap复杂度

C++的营养

莫华枫
    上一篇《C++的营养——RAII》中介绍了RAII,以及如何在C#中实现。这次介绍另一个重要的基础技术——swap手法。

swap手法

    swap手法不应当是C++独有的技术,很多语言都可以实现,并且从中得到好处。只是C++存在的一些缺陷迫使大牛们发掘,并开始重视这种有用的手法。这 个原本被用来解决C++的资源安全和异常保证问题的技术在使用中逐步体现出越来越多的应用,有助于我们编写更加简洁、优雅和高效的代码。
    接下来,我们先来和swap打个招呼。然后看看在C#里如何玩出swap。最后展示swap手法的几种应用,从中我们将看到它是如何的可爱。
    假设,我要做一个类,实现统计并保存一个字符串中字母的出现次数,以及总的字母和数字的个数。
         class  CountStr
        
{
        
public:
            
explicit CountStr(std::string const& val)
                :m_str(val), m_nLetter(
0), m_nNumber(0{
                do_count(val);
            }

            CountStr(CountStr 
const& cs)
                :m_str(cs.m_str), m_counts(cs.m_counts)
                , m_nLetter(cs.m_nLetter), m_nNumber(cs.m_nNumber)
            
{}
               
void swap(CountStr& cs) {
                   std::swap(m_str, cs.m_str);
                   m_counts.swap(m_str);
                   std::swap(m_nLetter, cs.m_nLetter);
                   std::swap(m_nNumber, cs.m_nNumber);
               }

        
private:
            std::
string m_str;
            std::map
<charint> m_counts;
            
int m_nLetter;
            
int m_nNumber;
        }
    在类CountStr中,定义了swap成员函数。swap接受一个CountStr&类型的参数。在函数中,我们可以看到一组函数调用,每一个 对应一个数据成员,其任务是将相对应的数据成员的内容相互交换。此处,我使用了两种调用,一种是使用std::swap()标准函数,另一种是通过 swap成员函数执行这个交换。一般情况下,std::swap()通过一个临时变量实现对象的内容交换。但对于string、map等非平凡的对象,这 种交换会引发至少三次深拷贝,其复杂度将是O(3n)的,性能极差。因此,标准库为这些类定义了swap成员函数,通过成员函数可以实现O(1)的交换操 作。同时将std::swap()针对这些拥有swap()成员函数的标准容器特化,使其可以直接使用swap()成员函数,而避免性能损失。但是,对于 那些拥有swap()成员,但没有被特化的用户定义,或第三方的类,则不应使用std::swap(),而改用swap()成员函数。所以,一般情况下, 为了避免混淆,对于拥有swap()成员函数的类,调用swap(),否则调用标准std::swap()函数。
    顺便提一下,在未来的C++0x中,由于引入了concept机制,可以允许一个函数模板自动识别出所有“具有swap()成员”的类型,并使用相应的特化版本。这样便只需使用std::swap(),而不必考虑是什么样的类型了。
    言归正传。这里,swap()成员函数有两个要求,其一是复杂度为O(1),其二是具备无抛掷的异常保证。前者对于性能而言至关重要,否则swap操作将 会由于性能问题而无法在实际项目中使用。对于后者,是确保强异常保证(commit or rollback语义)的基石。要达到这两个要求,有几个关键要点:首先,对于类型为内置类型或小型POD(8~16字节以内)的成员数据,可以直接使用 std::swap();其次,对于非平凡的类型(拥有资源引用,复制构造和赋值操作会引发深拷贝),并且拥有符合上述要求的swap()成员函数的,直 接使用swap()成员函数;最后,其余的类型,则保有其指针,或智能指针,以确保满足上述两个要求。
    听上去有些复杂,但在实际开发中做到并不难。首先,尽量使用标准库容器,因为标准库容器都拥有满足两个条件的swap()成员。其次,在编写的每一个类中 实现满足两个条件的swap()成员。最后,对于那些不具备swap()成员函数的第三方类型,则使用指针,最好是智能指针。(也就是Sutter所谓的 PImpl手法)。只要坚持这些方针,必能收到很好的效果。
    下面,就来看一下这个swap()的第一个妙用。假设,这个类需要复制。通常可以通过operator=操作符,或者copy(或其他有明确的复制含义 的)成员函数实现,这两者实际上是等价的,只是形式不同而已。这里选择operator=,因为它比较C++:)。
    最直白的实现方式是这样:
         class  CountStr
        
{
        
public:
            ...
            CountStr
& operator=(CountStr& val) {
                m_str
=val.m_str;
                m_counts
=val.m_counts;
                m_nLetter
=val.m_nLetter;
                m_nNumber
=val.m_nNumber;
            }

            ...
        }
    很简单,但是不安全,或者说没有满足异常保证。
    先解释一下异常保证。异常保证有三个级别:基本保证、强异常保证和无抛掷保证。基本保证是指异常抛出时,程序的各个部分应当处于有效状态,不能有资源泄 漏。这个级别可以轻而易举地利用RAII确保,这在前一篇已经展示过了。强异常保证则更加严格,要求异常抛出后,程序非但要满足基本保证,其各个部分的数 据应保持原状。也就是要满足“Commit or Rollback”语义,熟悉数据库的人,可以联想一下Transaction的行为。而无抛掷保证要求函数在任何情况下都不会抛出异常。无抛掷保证不是 说用一个catch(...)或throw()把异常统统吞掉。而是说在无抛掷保证的函数中的任何操作,都不会抛出异常。能满足无抛掷保证的操作还是很多 的,比如内置POD类型(int、指针等等)的复制,swap手法便以此为基础。(多说一句,用catch(...)吞掉异常来确保无抛掷并非绝对不行, 在特定情况下,还是可以偶尔一用。不过这等烂事也只能在西构函数中进行,而且也只有在迫不得已的情况下用那么一下)。
    如果这四个赋值操作 中,任意一个抛出异常,便会退出这个函数(操作符)。此时,至少有一个成员数据没有正确修改,而其他的则全部或部分地发生改变。于是,一部分成员数据是新 的,另一部分是旧的,甚至还有一些是不完全的。这在软件中往往会引发很多令人苦恼的bug。无论如何,此时应当运用强异常保证,使得数据要么是新的值,要 么没有改变。那么如何获得强异常保证?在swap()的帮助下,惊人的简单:
         class  CountStr
        
{
        
public:
            ...
            CountStr
& operator=(CountStr& val) {
                swap(CountStr(val)); 
// 或者CountStr(val).swap(*this);
                raturn *this;                    
            }

            ...
        }
    我想世上没有比这等代码更加漂亮的了吧!不仅仅具有简洁动人的外表,而且充满了丰富的内涵。这就叫优雅。不过,优雅之下还需要一些解释。在这两个版本中, 都是先用复制构造创建一个临时对象,这个临时对象同传入的参数对象拥有相同的值。然后用swap()成员函数将this对象的内容与临时对象交换。于是, this对象拥有了临时对象的值,也就是与传入的实参对象具有相同的值(复制)。当退出函数的时候,临时对象销毁,自然而然地释放了this对象原先的资 源(前提是CountStr类实现了RAII)。
    那么抛出异常的情况又是怎样的呢?
    先来看看operator=里执行了哪些步骤,并考察这些步骤的异常抛掷的情况。如果将代码改写成另一个等价的形式,就很容易理解了:
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/weixin_40725706/article/detail/1016531
推荐阅读
  

闽ICP备14008679号