c++標(biāo)準(zhǔn)庫體系結(jié)構(gòu)與內(nèi)核分析

第一講：示范運用STL各大部件 (components)蚯舱，并初步認識其體系結(jié)構(gòu)

1.認識headers陆赋、版本盒粮、重要資源

所謂generic programing偷仿，GP泛型編程烁焙，就是使用template模板為主要工具來編寫程序
根據(jù)源代碼分析c++STL之體系結(jié)構(gòu)
應(yīng)具備的基礎(chǔ)：c++基本語法抵蚊，包括如何正確使用模板templates
-level0：使用c++標(biāo)準(zhǔn)庫
-level1：深入認識c++標(biāo)準(zhǔn)庫施绎，清楚其在內(nèi)存中的結(jié)構(gòu)等
-level2：良好使用c++標(biāo)準(zhǔn)庫
-level3：擴充c++標(biāo)準(zhǔn)庫
c++標(biāo)準(zhǔn)庫與STL
-c++ standard library：目前c++中已給的頭文件
-standard template library：標(biāo)準(zhǔn)模板庫，分為六大部件贞绳，標(biāo)準(zhǔn)庫中大量存在STL
-標(biāo)準(zhǔn)庫以Header files形式呈現(xiàn)谷醉，所以源代碼可見
-headers中的組件封裝于namespace std
using namespace std;
using std::cout;

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

不同版本標(biāo)準(zhǔn)庫的用法基本相同
推薦網(wǎng)站：
-www.cplusplus.com
-en.cppreference.com
-gcc.gnu.org

2.STL體系結(jié)構(gòu)基礎(chǔ)介紹

STL六大部件：
-容器containers
-分配器allocators
-算法algorithms
-迭代器iterators
-適配器adapters
-仿函式functors
分配器用來支持容器存放
部分操作在容器本身操作另外部分放在算法操作
面向?qū)ο缶幊讨泄膭顚?shù)據(jù)及函數(shù)放在類中，與STL不同
容器用來存放要處理的數(shù)據(jù)熔酷，算法對容器中的數(shù)據(jù)進行處理
迭代器是數(shù)據(jù)與操作的橋梁孤紧，是一種泛化的指針
仿函數(shù)作用像函數(shù)一樣
適配器用來幫助轉(zhuǎn)換，迭代器適配拒秘、仿函數(shù)適配号显、容器適配

#include <vector>        //需要使用容器要引入對應(yīng)的頭文件
#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);
//容器↑       分配器↑
//模板：尖括號中第一個參數(shù)為類型，第二個參數(shù)允許放一個分配器幫助分配內(nèi)存躺酒，不寫的話使用默認
    cout<<count_if(vi.begin(),vi.end,not1(bind2nd(less<int>(),40)));   
//      算法↑ 迭代器↑           適配器↑       
//對數(shù)據(jù)的操作：需要用適配器來做容器和算法的接口
//predicate
    return 0;
}

復(fù)雜度complexity
-O（1）押蚤、O（c）：常數(shù)時間 constant time
-O（n）：線性時間 linear time
-O（log2n）：次線性實踐 sub-linear time
-O（n^2）：平方時間 quadratic time
-O（n^3）：立方時間 cubic time
-O（2^n）：指數(shù)時間 exponential time
-O（nlog2n）：介于線性及二次方成長的中間
“前閉后開”區(qū)間
標(biāo)準(zhǔn)庫規(guī)定，容器中頭指針指向第一個元素羹应，尾指針?biāo)笧槿萜髯詈笤氐南乱粋€位置
容器中的空間并不一定連續(xù)揽碘，也可能是鏈表或者哈希表

Container<T> c;
...
Container<T>::iterator ite = c.begin();
//容器都有其專屬的一個iterator，用其類型聲明頭指針
for(;ite!=c.end();ite++)
...
//對容器進行遍歷

c++11新功能：
-對容器進行遍歷
range-based "for" statement (since C++11)
for(decl:coll){statement}

for(int i : {2,3,5,7,9,13,17,19})
{
    std::cout<<i<<std::endl;
}

std::vector<double> vec;
for(auto elem : vec)
{
    std::cout<<elem<<std::endl;
}
for(auto& elem : vec)
{
    elem *= 3;
}

-auto keyword

list<string> c;
...
list<string>::iterator ite;
ite=::find(c.begin(),c.end(),/*target*/);

↓

list<string> c;
...
auto ite = ::find(c.begin(),c.end(),/*target*/);

3.容器之分類與各種測試

容器-結(jié)構(gòu)

-順序表
-鏈表
-樹
-堆
-哈希表

容器-分類

sequence containers
associative containers
unordered containers
hash table separate chaining
-array，固定大小雳刺，不可擴充
-vector劫灶，開頭固定，尾可擴充
-list掖桦，雙鏈表本昏，雙向都有指針
-forward_list，單鏈表枪汪，指針為單向
-slist
-deque涌穆，頭尾可擴充
-stack
-multiset，集合中元素可重復(fù)
-multimap
-unordered_multiset雀久，分散無序存放宿稀，
-unordered_multimap
-set，集合赖捌，一種平衡二叉樹祝沸，每個元素中key和value為同一個，集合中元素不可重復(fù)
-map巡蘸，圖奋隶，通常用紅黑樹，每個元素中key和value為不同變量
-unordered_set
-unordered_map
-hash_set悦荒，哈希結(jié)構(gòu)唯欣，目前最優(yōu)
-hash_multiset
-hash_multimap

四個函數(shù)
-輸入一個target
-輸入一個字符串target
-比較兩個long型大小
-比較兩個字符串大小

使用容器array

#include <array>
#include <iostream>
#include <ctime> 
#include <cstdlib> //qsort, bsearch, NULL

namespace jj01
{
void test_array()
{
    cout << "\ntest_array().......... \n";
     
array<long,ASIZE> c;    
            
clock_t timeStart = clock();                                    
    for(long i=0; i< ASIZE; ++i) {
        c[i] = rand(); 
    }
    cout << "milli-seconds : " << (clock()-timeStart) << endl;  //
    cout << "array.size()= " << c.size() << endl;       
    cout << "array.front()= " << c.front() << endl; 
    cout << "array.back()= " << c.back() << endl;   
    cout << "array.data()= " << c.data() << endl;   
    
long target = get_a_target_long();

    timeStart = clock();
    ::qsort(c.data(), ASIZE, sizeof(long), compareLongs);
long* pItem = (long*)::bsearch(&target, (c.data()), ASIZE, sizeof(long), compareLongs); 
    cout << "qsort()+bsearch(), milli-seconds : " << (clock()-timeStart) << endl;   //    
    if (pItem != NULL)
        cout << "found, " << *pItem << endl;
    else
        cout << "not found! " << endl;  
}
}

array
-尖括號中第一個參數(shù)為類型，第二個參數(shù)為容器大小

使用容器vector

#include <vector>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime> 
#include <algorithm>    //sort()
namespace jj02
{
void test_vector(long& value)
{
    cout << "\ntest_vector().......... \n";
     
vector<string> c;   
char buf[10];
            
clock_t timeStart = clock();                                
    for(long i=0; i< value; ++i)
    {
        try {
            snprintf(buf, 10, "%d", rand());
            c.push_back(string(buf));           
        }
        catch(exception& p) {
            cout << "i=" << i << " " << p.what() << endl;   
                 //曾經(jīng)最高 i=58389486 then std::bad_alloc
            abort();
        }
    }
    cout << "milli-seconds : " << (clock()-timeStart) << endl;  
    cout << "vector.max_size()= " << c.max_size() << endl;  //1073747823
    cout << "vector.size()= " << c.size() << endl;      
    cout << "vector.front()= " << c.front() << endl;    
    cout << "vector.back()= " << c.back() << endl;  
    cout << "vector.data()= " << c.data() << endl;
    cout << "vector.capacity()= " << c.capacity() << endl << endl;      

                                                                                
string target = get_a_target_string();
    {
    timeStart = clock();
auto pItem = find(c.begin(), c.end(), target);
    cout << "std::find(), milli-seconds : " << (clock()-timeStart) << endl;  
     
    if (pItem != c.end())
        cout << "found, " << *pItem << endl << endl;
    else
        cout << "not found! " << endl << endl;
    }

    {
    timeStart = clock();
    sort(c.begin(), c.end());
    cout << "sort(), milli-seconds : " << (clock()-timeStart) << endl; 
    
    timeStart = clock();        
string* pItem = (string*)::bsearch(&target, (c.data()), 
                                   c.size(), sizeof(string), compareStrings); 
    cout << "bsearch(), milli-seconds : " << (clock()-timeStart) << endl; 
       
    if (pItem != NULL)
        cout << "found, " << *pItem << endl << endl;
    else
        cout << "not found! " << endl << endl;  
    }
    
    c.clear();
    test_moveable(vector<MyString>(),vector<MyStrNoMove>(), value); 
}   
}

-tips：測試程序的每一段歸在一個namespace中
vector
-尖括號中的參數(shù)為類型

使用容器list

#include <list>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <algorithm> //find()
#include <iostream>
#include <ctime> 
namespace jj03
{
void test_list(long& value)
{
    cout << "\ntest_list().......... \n";
     
list<string> c;     
char buf[10];
            
clock_t timeStart = clock();                            
    for(long i=0; i< value; ++i)
    {
        try {
            snprintf(buf, 10, "%d", rand());
            c.push_back(string(buf));       
        }
        catch(exception& p) {
            cout << "i=" << i << " " << p.what() << endl;   
            abort();
        }
    }
    cout << "milli-seconds : " << (clock()-timeStart) << endl;      
    cout << "list.size()= " << c.size() << endl;
    cout << "list.max_size()= " << c.max_size() << endl;    //357913941
    cout << "list.front()= " << c.front() << endl;  
    cout << "list.back()= " << c.back() << endl;        
        
string target = get_a_target_string();      
    timeStart = clock();        
auto pItem = find(c.begin(), c.end(), target);                      
    cout << "std::find(), milli-seconds : " << (clock()-timeStart) << endl;     
    
    if (pItem != c.end())
        cout << "found, " << *pItem << endl;
    else
        cout << "not found! " << endl;  
        
    timeStart = clock();        
    c.sort();                       
    cout << "c.sort(), milli-seconds : " << (clock()-timeStart) << endl;                
        
    c.clear();
    test_moveable(list<MyString>(),list<MyStrNoMove>(), value);                             
}   
}

list
-尖括號參數(shù)為類型
循環(huán)存入數(shù)據(jù)

4.分配器之測試

使用分配器allocator

不同容器在聲明時候的分配方式
-尖括號第二位置的參數(shù)即是所選用的分配器

#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          
}                                                           
}