對于現(xiàn)在的計算機編程語言來說熄阻，語言和庫已經(jīng)形成了兩大體系滋戳。只學一門語言可以實現(xiàn)自己想要的功能钻蔑，也可以寫出各式各樣的程序，但是奸鸯，不得已需要提一句咪笑，對于現(xiàn)在技術的發(fā)展速度來說，開發(fā)的效率變得尤為重要娄涩。而僅僅會一門編程語言窗怒，在現(xiàn)階段其實已經(jīng)成為了一件無意義的事。那么拿語言和數(shù)據(jù)結(jié)構(gòu)來舉例蓄拣，他們倆已經(jīng)是兩個獨立的體系了扬虚，而數(shù)據(jù)結(jié)構(gòu)對于開發(fā)而言，基本的代碼實現(xiàn)都是差不多的球恤。那么辜昵，開發(fā)不同的系統(tǒng)，意味著會有巨大的重復過程要做咽斧，而這類重復過程其實也就是不斷的*** 造 輪 子 ***的過程路鹰。先拋開贷洲，自己制造的輪子的開發(fā)效率問題不談收厨，那么自己制造的輪子晋柱，也不一定有在市場上購買的輪子質(zhì)量過硬。那么诵叁，在很多時候雁竞，自造輪子，其實是一件得不償失的事拧额，因此：
*** 1.開發(fā)效率變慢 2. 且質(zhì)量不一定是最好的 ***

那么語言學中碑诉，重要的一點就是庫的學習。那么侥锦，現(xiàn)在來說进栽，每種語言，在各自的特定領域都會有特定的庫來實現(xiàn)想要的功能恭垦。比如Python的爬蟲領域就有requests庫等快毛，深度學習算法領域常用到Caffe、Tensorflow庫等等番挺。這些呢其實已經(jīng)是一些專用的庫唠帝，可以實現(xiàn)一些特定需求中的特定功能，而無需自己從0開始寫玄柏。而這些庫其實是一些功能庫襟衰，但再往底層查看，***程序最根本的目的是為了操作一些數(shù)據(jù) *粪摘。而這限額護具的組織方式其實是一件十分重要的是瀑晒，記得我在前面說過關于一個 鑰匙和箱子的故事 **，這里面詳細說明了徘意，當數(shù)據(jù)量足夠大的時候苔悦，出現(xiàn)的一些問題，其實也就是數(shù)據(jù)結(jié)構(gòu)的問題映砖，而數(shù)據(jù)結(jié)構(gòu)其實多于每個程序來說都是必須要面對的间坐。那么每個語言非常重要的是要有一套面向底層數(shù)據(jù)的庫，而在c++中就是標準庫（c++ Standard Library）邑退。
引用下面圖片中這本書的一句話：

不會使用標準庫的C++程序員算不上是一個有開發(fā)效率的程序員

那么說了這么多竹宋，今天的主要目的就是初步的來看看標準庫的那些事。

C++標準庫的體系結(jié)構(gòu)

C++標準庫的設計思想

• C++標準庫地技，主要使用的是泛型編程（Generic Programming）的思想蜈七，而不是采用了面向?qū)ο蟮牡闹饕枷搿?/li>

C++ Standard Library Vs. Standard Template Library

• 標準庫中包含STL
• STL主要由六大部件組成（后續(xù)詳談）

程序中標準庫的引用

• C++標準庫的header files不包括擴展名（.h），例如#include <vector>
• 新式的C header files不帶擴展名莫矗，前面需要添加c飒硅，例如#include <cstdlib>
• C語言中引入的方式依然可以用砂缩，例如#include <stdlib.h>

C++標準庫的命名空間

• C++標準庫的命名空間全部是std
• 如果使用C語言中的庫，不封裝在std的命名空間中
• 打開方式
  • 統(tǒng)一打開
    using namespace std;
  • 逐條打開
    using std::cout; using std::cin;

C++標準庫的資料庫

• Cplusplus
• CppReference
• gcc

STL的六大部件

組建之間的關系

C++標準庫中的組件之間的關系圖

• 操作容器中的數(shù)據(jù)的算法是獨立存在的
• 容器和算法之間的橋梁是迭代器（一種泛化的指針）
• 分配器負責給容器分配三娩、釋放內(nèi)存空間
• 仿函數(shù)庵芭，模仿函數(shù)一樣的對象
• 適配器，實現(xiàn)一些轉(zhuǎn)換

//六大部件的使用
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>

using namespace std;

int main()
{
    int ia[6] = {27, 210, 12, 47, 109, 83};
    vector<int, allocator<int>> vi(ia, ia+6);
    //vector:Container
    //allocator<int>：Allocator雀监，不寫使用默認的
    
    cout << count_if(vi.begin(), vi.end(), not1(bind2nd(less<int>(), 40)));
    // count_if(...): Algorithm
    // not1(...): Function adapter(gegator)
    // bind2nd(....): function adapter(binder)
    // less<int>: function object

    return 0;
}

• 關于算法的復雜度
  • 時間復雜度

時間復雜度與元素數(shù)量關系

1.可見隨著元素數(shù)量增加双吆，對算法要求越高，否則算法不合理會導致得不到結(jié)果
2.對于同樣的元素數(shù)量会前，不同的算法之間的差別也比較大
3.在數(shù)據(jù)量很小的情況下好乐，復雜度體現(xiàn)不出太大的差別
當發(fā)現(xiàn)算法的時間復雜的大于O(n^2)時，應勁量降低時間復雜度

• 關于復雜度的問題瓦宜，屬于基本的數(shù)據(jù)結(jié)構(gòu)話題蔚万，可以參見文章
  算法復雜度分析
  圖片來自該博客，如果侵權(quán)临庇，聯(lián)系我刪除】

容器（Container）

• 容器的分類
  • 順序容器
    • array（C++11）
      • 底層數(shù)據(jù)結(jié)構(gòu)：數(shù)組
        
        array內(nèi)存圖
      • 創(chuàng)建時反璃，需要制定大小array<long, 100> a
      • 可以使用a[x]來為元素賦值
      • 常用函數(shù)
        • a.size()：返回數(shù)組大小
        • a.front()：返回第一個元素
        • a.back()：返回最末位的元素
        • a.data()：返回起點的地址
      • 排序
        • 使用cstdlib中的qsort

void qsort (void* base, size_t num, size_t size,
int (compar)(const void,const void*));

      - 查找
        - 使用`algorithm`中的find
      ```
template <class InputIterator, class T>
   InputIterator std::find (InputIterator first, InputIterator last, const T& val);
      ```
       - 使用`cstdlib`中的`bsearch`(需要先排序)

void* bsearch (const void* key, const void* base,
size_t num, size_t size,
int (compar)(const void,const void*));

    - vector 
      - 底層數(shù)據(jù)結(jié)構(gòu)：***動態(tài)數(shù)組***
      - 僅能夠向后增長，成長過程相對較慢[ 因為苔巨，需要在空間中找到新位置版扩，再將元素搬移過去 ]
      - 兩倍擴充，容易浪費空間
![vector內(nèi)存圖](http://upload-images.jianshu.io/upload_images/5688965-c00c7322cf6e8818.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
    - 常用函數(shù)
      - `push_back()`：添加元素
      - `size()`：獲取元素數(shù)量
      - `front()`：獲取前端元素
      - `back()`：獲取后方元素
      - `data()`：獲取起始點的地址
      - `capacity()` ：獲取容器大小
    - 查找
      - 使用`algorithm`中的find
      ```
template <class InputIterator, class T>
   InputIterator std::find (InputIterator first, InputIterator last, const T& val);
      ```
      - 使用`cstdlib`中的`bsearch`(需要先排序)

void* bsearch (const void* key, const void* base,
size_t num, size_t size,
int (compar)(const void,const void*));

    - 排序
        - 使用`cstdlib`中的`qsort`   
        ```
void qsort (void* base, size_t num, size_t size,
            int (*compar)(const void*,const void*));

- deque
  - 底層數(shù)據(jù)結(jié)構(gòu)：***數(shù)組們的數(shù)組***

deque的內(nèi)存圖

- 雙向開口侄泽，可進可出的容器
- 每一個空間都指向一個buffer礁芦，buffer中的元素有順序

deque的結(jié)構(gòu)圖

• 常用函數(shù)

  • push_back()：添加元素

  • size()：獲取元素數(shù)量

  • max_size()：最大容量

  • back()：獲取后方元素

  • list

    • 底層數(shù)據(jù)結(jié)構(gòu)：雙向循環(huán)鏈表
      
      list內(nèi)存圖

  • 每次擴充一個節(jié)點

  • 查找速度比較慢

  • 常用函數(shù)

    • push_back()：添加元素
    • size()：獲取元素數(shù)量
    • max_size()：最大容量
    • front()：獲取前端元素
    • back()：獲取后方元素
    • sort()：自帶排序（不是algorithm中的）

  • forward-list

    • 底層數(shù)據(jù)結(jié)構(gòu)：單向列表
      
      forward-list

  • 常用函數(shù)

    • push_front()：添加元素
    • max_size()：最大容量
    • front()：獲取前端元素
    • sort()：自帶排序（不是algorithm中的）

  • slist（非標準的，gnu實現(xiàn)的）

    • 底層數(shù)據(jù)結(jié)構(gòu)：單向鏈表
    • 頭文件在ext\slist中悼尾，#include <ext/slist>
      
      slist的內(nèi)存圖
    • 使用和forward-list相同

  • stack（可理解為容器的adapter）

    • 底層數(shù)據(jù)結(jié)構(gòu)：deque

    • 先進后出

      
      
      stack結(jié)構(gòu)圖
    • 常用函數(shù)
    • size()：元素數(shù)量
    • pop()：彈出棧頂元素
    • push()：添加元素
    • 沒有iterator的操作

  • queue（可理解為容器的adapter）

    • 底層數(shù)據(jù)結(jié)構(gòu)：deque

    • 先進先出

      
      
      queue的結(jié)構(gòu)圖
    • 常用函數(shù)
      • size()：元素數(shù)量
      • front()：隊首元素
      • back()：隊尾元素
      • push()：添加元素
      • pop()：取出元素
      • 沒有iterator的操作

  • prority_queue

    • 底層數(shù)據(jù)結(jié)構(gòu)：vector
    • 適配器柿扣，它可以將任意類型的序列容器轉(zhuǎn)換為一個優(yōu)先級隊列，一般使用vector作為底層存儲方式闺魏。
    • 只能訪問第一個元素未状，不能遍歷整個priority_queue。
    • 第一個元素始終是優(yōu)先級最高的一個元素析桥。

• 關聯(lián)容器

  • set

    
    
    set的內(nèi)存圖
    • 鍵和值實際為同一個
    • 底層實現(xiàn)為：紅黑樹
    • 元素插入后司草，會放在對應的位置，不能手動操作
    • 插入慢泡仗，查找快
    • set中不能有重復的元素
    • 常用函數(shù)
      • size()：元素數(shù)量
      • max_size()：最大空間
      • insert()：添加元素
      • find()：查找元素

  • multiset

    • 和set基本相同埋虹，卻別在于可以有重復元素

  • map

    • 底層實現(xiàn)為：紅黑樹
      
      map的內(nèi)存圖
    • 存入的為鍵值對（pair<xx, yy）>(key, value)）
    • key不重復，所以可以使用iMap[key]來查詢元素
    • 常用函數(shù)
      • size()：元素數(shù)量
      • max_size()：最大空間
      • insert()：添加元素
      • find()：查找元素

  • multimap

    • 和map基本相同娩怎，卻別在于可以有重復元素
    • 因為key可以重復搔课，所以不可以使用iMap[key]來查詢元素

  • unordered_map(C++11)

    • 底層實現(xiàn)為：Hash Table

    • GNU以前提供的為：hash_map

      
      
      unordered_map的內(nèi)存圖
      
      
      hash表示意圖

• 常用函數(shù)
  - size()：元素數(shù)量
  - max_size()：最大空間
  - insert()：添加元素
  - find()：查找元素
  - bucket_count()：籃子的數(shù)量（籃子：hash 表中的格子有多少）
  - load_factor()：載重因子
  - max_load_factor()：最大載重因子
  - max_bucket_count()：最大的籃子的數(shù)量

• unordered_multimap(C++11)

  • 和unordered_map相同，除了可以存放key相同的元素意外
    • GNU以前提供的為：hash_multimap

• unordered_set(C++11)

  • 底層實現(xiàn)為：Hash Table

  • GNU以前提供的為：hash_set

    
    
    unordered_set的內(nèi)存圖

  • unordered_multiset(C++11)

    • 和unordered_set相同截亦，除了可以存放相同的元素意外
    • GNU以前提供的為：hash_multiset

  • 常用函數(shù)

    • size()：元素數(shù)量
    • max_size()：最大空間
    • insert()：添加元素
    • find()：查找元素
    • bucket_count()：籃子的數(shù)量（籃子：hash 表中的格子有多少）
    • load_factor()：載重因子
    • max_load_factor()：最大載重因子
    • max_bucket_count()：最大的籃子的數(shù)量

• 關于容器特性的總結(jié)

  
  
  容器特性總結(jié)

分配器（Allocators）

• 使用容器時爬泥，不指定柬讨，會自動使用默認的分配器（std::allocator<_Tp>）

以GNU的allocator為例

#include <list>
#include <stdexcept>
#include <string>
#include <cstdlib>      //abort()
#include <cstdio>       //snprintf()
#include <algorithm>    //find()
#include <iostream>
#include <ctime> 

#include <cstddef>
#include <memory>   //內(nèi)含 std::allocator  
    //欲使用 std::allocator 以外的 allocator, 得自行 #include <ext\...> 
#ifdef __GNUC__     
#include <ext\array_allocator.h>
#include <ext\mt_allocator.h>
#include <ext\debug_allocator.h>
#include <ext\pool_allocator.h>
#include <ext\bitmap_allocator.h>
#include <ext\malloc_allocator.h>
#include <ext\new_allocator.h>  
#endif

namespace jj20
{
//pass A object to function template impl()，
//而 A 本身是個 class template, 帶有 type parameter T,  
//那麼有無可能在 impl() 中抓出 T, 創(chuàng)建一個 list<T, A<T>> object? 
//以下先暫時迴避上述疑問.
    
void test_list_with_special_allocator()
{
#ifdef __GNUC__ 
    cout << "\ntest_list_with_special_allocator().......... \n";
     
    //不能在 switch case 中宣告袍啡，只好下面這樣.               //1000000次 
    list<string, allocator<string>> c1;                     //3140
    list<string, __gnu_cxx::malloc_allocator<string>> c2;   //3110
    list<string, __gnu_cxx::new_allocator<string>> c3;      //3156
    list<string, __gnu_cxx::__pool_alloc<string>> c4;       //4922
    list<string, __gnu_cxx::__mt_alloc<string>> c5;         //3297
    list<string, __gnu_cxx::bitmap_allocator<string>> c6;   //4781                                                      
     
int choice;
long value;     

    cout << "select: "
         << " (1) std::allocator "
         << " (2) malloc_allocator "
         << " (3) new_allocator "
         << " (4) __pool_alloc "
         << " (5) __mt_alloc "
         << " (6) bitmap_allocator ";
    
    cin >> choice;
    if ( choice != 0 ) {
        cout << "how many elements: ";
        cin >> value;       
    }
            
char buf[10];           
clock_t timeStart = clock();                                
    for(long i=0; i< value; ++i)
    {
        try {
            snprintf(buf, 10, "%d", i);
            switch (choice) 
            {
                case 1 :    c1.push_back(string(buf));  
                            break;
                case 2 :    c2.push_back(string(buf));  
                            break;      
                case 3 :    c3.push_back(string(buf)); 
                            break;      
                case 4 :    c4.push_back(string(buf));  
                            break;      
                case 5 :    c5.push_back(string(buf));      
                            break;      
                case 6 :    c6.push_back(string(buf));  
                            break;              
                default: 
                    break;      
            }                   
        }
        catch(exception& p) {
            cout << "i=" << i << " " << p.what() << endl;   
            abort();
        }
    }
    cout << "a lot of push_back(), milli-seconds : " << (clock()-timeStart) << endl;    
    
     
    //test all allocators' allocate() & deallocate();
    int* p;     
    allocator<int> alloc1;  
    p = alloc1.allocate(1);  
    alloc1.deallocate(p,1);     
                        
    __gnu_cxx::malloc_allocator<int> alloc2;  
    p = alloc2.allocate(1);  
    alloc2.deallocate(p,1);     
        
    __gnu_cxx::new_allocator<int> alloc3;   
    p = alloc3.allocate(1);  
    alloc3.deallocate(p,1);     
        
    __gnu_cxx::__pool_alloc<int> alloc4;    
    p = alloc4.allocate(2);  
    alloc4.deallocate(p,2);     //我刻意令參數(shù)為 2, 但這有何意義!! 一次要 2 個 ints? 
        
    __gnu_cxx::__mt_alloc<int> alloc5;  
    p = alloc5.allocate(1);  
    alloc5.deallocate(p,1);     
            
    __gnu_cxx::bitmap_allocator<int> alloc6;    
    p = alloc6.allocate(3);  
    alloc6.deallocate(p,3);     //我刻意令參數(shù)為 3, 但這有何意義!! 一次要 3 個 ints? 
#endif          
}                                                           
}

迭代器（Iterators）

• 迭代器的范圍：前閉后開區(qū)間

迭代器的前閉后開區(qū)間

Container<T> c;
.....
Container<T>::iterator ite = c.begin();
for(; ite != c.end(); ite++){
......}

算法（Algorithms）踩官、 適配器（Adapters）、（Functors）

參見：
(Boolan) C++ STL與泛型編程——算法葬馋、仿函數(shù)卖鲤、Adapter