C++11在時空性能方面的改進

這篇我們聊聊C++11在時間和空間上的改進點；

主要包括以下方面：

新增的高效容器：array、forward_list以及unordered containers；

以及常量表達式、靜态斷言和move語義；

大小固定容器 array

std::array是一個支援随機通路且大小（size）固定的容器，它是c++11中新增的容器。它有如下特點：

不預留多餘空間，隻配置設定必須空間（譯注：size() == capacity()）。
可以使用初始化表（initializer list）的方式進行初始化。
儲存了自己的size資訊。
不支援隐式指針類型轉換。

可以認為它是一個很不錯的内建數組類型。示例：

array<int,6> a = { 1, 2, 3 };
a[3]=4;
int x = a[5];    // array的預設資料元素為0，是以x的值變成0
int* p1 = a; // 錯誤: std::array不能隐式地轉換為指針
int* p2 = a.data(); // 正确，data()得到指向第一個元素的指針

可以認為array是一個緊縮版的vector，它比vector高效（沒有自動空間配置設定），但缺少了push_back這樣的神器，使得它的使用場景一般是用來替換c++内建的數組類型，而不是vector；

前向清單 forward_list

c++11新增的容器：前向清單 forward_list

前向清單是一個能夠在任意位置快速插入和删除的容器（清單都這特性，前向清單當然也具有這特性），但不支援快速随機存取。

它是用單向連結清單實作的，相比較于它的C實作而言沒有什麼額外開銷。相較于std::list而言，此容器耗費的空間更少，因為它是單向的，不是雙向的。

std::forward_list<int> mylist (3,5);   // 3 ints with value 5
for (int& x : mylist ) std::cout << " " << x;

哈希表[無序容器] unordered containers

hash容器在很多之前的編譯器中就包含進來了；比如gcc 較早的版本中，它存在于tr1命名空間中；

以unordered_map為例，unordered_map基于散清單實作，元素之間無序存儲；

而map基于紅黑樹實作，元素之間有序（通過operator< 進行比較）；

hash版本的查找時間複雜度為O(1),在資料量很大時，比紅黑樹的版本效率高很多；

對比在C++11中和之前使用上的差別：

// c++0x中：
#include <tr1/unordered_map>
std::tr1:: unordered_map< char,int >  map1;
map1.insert(std::pair<char,int>('a',100) );

// C++11中：
#include <unordered_map>
std::unordered_map< char,int >  map1;
map1.insert(std::pair<char,int>('a',100) );

常量表達式 constexpr

編譯期計算（Compile-time evaluation）：常量表達式

在程式中，有些計算是與運作時無關的；每次執行都是相同的結果；

常量表達式允許讓這些計算發生在編譯時，而不是在運作時；

這樣利用編譯時的計算能力，将顯著提升程式執行時的效果；

eg:對函數申明為constexpr

constexpr int multiply (int x, int y)
{
    return x * y;
}

// 将在編譯時計算
const int val = multiply( 10, 10 );
cin >> x;
// 由于輸入參數x隻有在運作時确定，是以以下這個不會在編譯時計算，但執行沒問題
const int val2 = mutliply（x,x);

靜态斷言 static_assert

static_assert提供一個編譯時的斷言檢查。如果斷言為真，什麼也不會發生。如果斷言為假，編譯器會列印一個特殊的錯誤資訊。由于是在編譯期間執行的，是以它不會影響運作時的性能；

expression在編譯期進行求值，當結果為false（即：斷言失敗）時，将string作為錯誤消息輸出。例如：

static_assert(sizeof(long) >= 8,
   “64-bit code generation required for this library.”);
struct S { X m1; Y m2; };
static_assert(sizeof(S)==sizeof(X)+sizeof(Y), ”unexpected padding in S”);

static_assert在判斷代碼的編譯環境方面十分有用，比如判斷目前編譯環境是否64位。但需要注意的是，由于static_assert在編譯期進行求值，它不能對那些依賴于運作期計算的值的進行檢驗。例如：

int f(int* p, int n)
{
      //錯誤：表達式“p == 0”不是一個常量表達式
      static_assert(p == 0,
          “p is not null”);
}

正确的做法是在運作期進行判斷，假如條件不成立則抛出異常；

下面這段代碼原本期望隻做用于整數類型。

template <typename T1, typename T2>
auto add(T1 t1, T2 t2) -> decltype(t1 + t2)
{
return t1 + t2;
}

但是如果有人寫出如下代碼，編譯器并不會報錯

std::cout << add(1, 3.14) << std::endl;
std::cout << add("one", 2) << std::endl;

程式會列印出4.14和”e”。但是如果我們加上編譯時斷言，那麼以上兩行将産生編譯錯誤。

template <typename T1, typename T2>
auto add(T1 t1, T2 t2) -> decltype(t1 + t2)
{
   static_assert(std::is_integral<T1>::value, "Type T1 must be integral");
   static_assert(std::is_integral<T2>::value, "Type T2 must be integral");

   return t1 + t2;
}

error C2338: Type T2 must be integral
see reference to function template instantiation 'T2 add<int,double>(T1,T2)' being compiled
   with
   [
      T2=double,
      T1=int
   ]
error C2338: Type T1 must be integral
see reference to function template instantiation 'T1 add<const char*,int>(T1,T2)' being compiled
   with
   [
      T1=const char *,
      T2=int
   ]

move語義和右值引用

move語義和右值介紹

左值就是一個有名字的對象，而右值則是一個無名對象（臨時對象）。move語義允許修改右值（以前右值被看作是不可修改的，等同于const T&類型）。

void incr(int& a) { ++a; }
int i = 0;
incr(i);    // i變為1
//錯誤：0不是一個左值
incr(0);
// 0不是左值，無法直接綁定到非const引用：int&。
// 假如可行，那麼在調用時，将會産生一個值為0的臨時變量，
// 用于綁定到int&中，但這個臨時變量将在函數傳回時被銷毀，
// 因而，對于它的任何更改都是沒有意義的，
// 是以編譯器拒絕将臨時變量綁定到非const引用，但對于const的引用，
// 則是可行的
”&&”表示“右值引用”。右值引用可以綁定到右值（但不能綁定到左值）：

X a;
X f();
X& r1 = a;        // 将r1綁定到a(一個左值)
X& r2 = f();    // 錯誤：f()的傳回值是右值，無法綁定
X&& rr1 = f();    // OK：将rr1綁定到臨時變量
X&& rr2 = a;    // 錯誤：不能将右值引用rr2綁定到左值a

考慮如下函數：

template<class T> swap(T& a, T& b) // 老式的swap函數
    {
        T tmp(a);// 現在有兩份"a"
        a = b;      // 現在有兩份"b"
        b = tmp;    // 現在有兩份tmp(值同a)
    }

如果T是一個拷貝代價相當高昂的類型，例如string和vector，那麼上述swap()操作也将煞費氣力；我們的初衷其實并不是為了把這些變量拷來拷去，我是僅僅想将變量a,b,tmp的值做一個“移動”（即通過tmp來交換a,b的值）。

移動指派操作背後的思想是，“指派”不一定要通過“拷貝”來做，還可以通過把源對象簡單地“偷換”給目标對象來實作。例如對于表達式s1=s2，我們可以不從s2逐字拷貝，而是直接讓s1“侵占”s2内部的資料存儲；

我們可以通過move()操作符來實作源對象的“移動”：

template <class T>
void swap(T& a, T& b)  //“完美swap”（大多數情況下）
{
      T tmp = move(a);  // 變量a現在失效（譯注：内部資料被move到tmp中了）
      a = move(b);      // 變量b現在失效（譯注：内部資料被move到a中了，變量a現在“滿血複活”了）
      b = move(tmp);    // 變量tmp現在失效（譯注：内部資料被move到b中了，變量b現在“滿血複活”了）
}

move(x) 意味着“你可以把x當做一個右值”，把move()改名為rval()或許會更好，但是事到如今，move()已經使用很多年了。在C++11中，move()模闆函數以及右值引用被正式引入。

将拷貝改進成移動操作，減少建立不必要的對象，節省了對象的空間配置設定消耗和構造析構的調用；

move對算法中的改進

基于move的std::sort()和std::set::insert()要比基于copy的對應版本快15倍以上。不過它對标準庫中已有操作的性能改善不多，因為它們的實作中已經使用了類似的方法進行優化了（例如string，vector使用了調優過的swap操作來代替copy了）。當然如果你自己的代碼中包含了move操作的話，就能自動從新标準庫中獲益了。

move對容器的改進

在C++11的标準庫中，所有的容器都提供了移動構造函數和移動指派操作符，那些插入新元素的操作，如insert()和push_back(), 也都有了可以接受右值引用的版本。最終的結果是，在沒有使用者幹預的情況下，标準容器和算法的性能都提升了，而這些都應歸功于拷貝操作的減少。

以vector為例，定義“移動構造函數(move constructors)”和“移動指派操作符(move assignments”來“移動”而非複制它們的參數：

template<class T> class vector {
        // …
        vector(const vector&);  // 拷貝構造函數
        vector(vector&&);   // 移動構造函數
        vector& operator= (const vector&); // 拷貝指派函數
        vector& operator =(vector&&);  // 移動指派函數
}; //注意：移動構造函數和移動指派操作符接受
// 非const的右值引用參數，而且通常會對傳入的右值引用參數作修改

容器新增了move版的構造和指派函數後，它最重要的内涵就是允許我們高效的從函數中傳回一個容器：

vector<int> make_random(int n)
        {
            vector<int> ref(n);
            // 産生0-255之間的随機數
                for(auto x& : ref) x = rand_int(0,255);

                return ref;
        }

        vector<int> v = make_random(10000);
        for (auto x : make_random(1000000)) cout << x << '\n';

上邊代碼的關鍵點是vector沒有被拷貝操作(vector ref的記憶體空間不會在函數傳回時被stack自動回收了，move assignment通過右值引用精巧的搞定了這個問題)。對比我們現在的兩種慣用法：在自由存儲區來配置設定vector的空間，我們得負擔上記憶體管理的問題了；通過參數傳進已經配置設定好空間的vector，我們得要寫不太美觀的代碼了。

原地安置操作 Emplace operations

在大多數情況下，push_back()使用移動構造函數（而不是拷貝構造函數）來保證它更有效率，不過在極端情況下我們可以走的更遠。為何一定要進行拷貝/移動操作？為什麼不能在vector中配置設定好空間，然後直接在這個空間上構造我們需要的對象呢？做這種事兒的操作被叫做”原地安置”（emplace，含義是：putting in place）。

舉一個emplace_back()的例子：

vector<pair<string,int>> vp;
string s;
int i;
while(cin>>s>>i) vp.emplace_back(s,i);

emplace_back()接受了可變參數模闆變量并通過它來構造所需類型。至于emplace_back()是否比push_back()更有效率，取決于它和可變參數模闆的具體實作。如果你認為這是一個重要的問題，那就實際測試一下。否則，就從美感上來選擇它們吧。

參考

http://www.stroustrup.com/C++11FAQ.html

https://www.chenlq.net/books/cpp11-faq

Posted by: 大CC | 07SEP,2015

部落格：blog.me115.com [訂閱]

Github：大CC

C++11在時空性能方面的改進

C++11在時空性能方面的改進

大小固定容器 array

前向清單 forward_list

哈希表[無序容器] unordered containers

常量表達式 constexpr

靜态斷言 static_assert

move語義和右值引用

move語義和右值介紹

move對算法中的改進

move對容器的改進

原地安置操作 Emplace operations

參考

繼續閱讀

Qt5 lambda表達式連接配接QTcpServer信号槽ProblemSolutionAppendix Qt Lambda表達式

C++11 FAQ中文版：傳回值類型後置文法

C++11 FAQ中文版：繼承的構造函數

C++11基于範圍的for循環1 .基于範圍的for循環2.基于範圍的for循環特點3.基于範圍的for循環使用的要求及依賴條件

C++11 FAQ中文版：類成員的内部初始化

C++11之for循環

C++11 FAQ中文版：Lambda表達式

[C++11]委托構造函數

C++11之清單初始化統一的初始化使用細節初始化清單

[modern c++] std::function的使用

c++11 tuple元組

C++智能指針使用總結 C++智能指針使用總結

C++11 多線程學習----std::thread類的簡單使用

c++11：智能指針之std::unique_ptr、std::shared_ptr、std::weak_ptr1、std::unique_ptr2、std::shared_ptr3、std::weak_ptr

c++11總結12——四個智能指針：shared_ptr、uinque_ptr、weak_ptr和auto_ptr前言1. unique_ptr2. shared_ptr3. weak_ptr

C++11新特性之九：strongly-typed enums