C++STL

(Boolan) C++ STL与泛型编程

2017-05-25  本文已影响56人  故事狗

对于现在的计算机编程语言来说，语言和库已经形成了两大体系。只学一门语言可以实现自己想要的功能，也可以写出各式各样的程序，但是，不得已需要提一句，对于现在技术的发展速度来说，开发的效率变得尤为重要。而仅仅会一门编程语言，在现阶段其实已经成为了一件无意义的事。那么拿语言和数据结构来举例，他们俩已经是两个独立的体系了，而数据结构对于开发而言，基本的代码实现都是差不多的。那么，开发不同的系统，意味着会有巨大的重复过程要做，而这类重复过程其实也就是不断的*** 造 轮 子 ***的过程。先抛开，自己制造的轮子的开发效率问题不谈，那么自己制造的轮子，也不一定有在市场上购买的轮子质量过硬。那么，在很多时候，自造轮子，其实是一件得不偿失的事，因此：
*** 1.开发效率变慢 2. 且质量不一定是最好的 ***

那么语言学中，重要的一点就是库的学习。那么，现在来说，每种语言，在各自的特定领域都会有特定的库来实现想要的功能。比如Python的爬虫领域就有requests库等，深度学习算法领域常用到Caffe、Tensorflow库等等。这些呢其实已经是一些专用的库，可以实现一些特定需求中的特定功能，而无需自己从0开始写。而这些库其实是一些功能库，但再往底层查看，***程序最根本的目的是为了操作一些数据 *。而这限额护具的组织方式其实是一件十分重要的是，记得我在前面说过关于一个 钥匙和箱子的故事 **，这里面详细说明了，当数据量足够大的时候，出现的一些问题，其实也就是数据结构的问题，而数据结构其实多于每个程序来说都是必须要面对的。那么每个语言非常重要的是要有一套面向底层数据的库，而在c++中就是标准库（c++ Standard Library）。
引用下面图片中这本书的一句话：

不会使用标准库的C++程序员算不上是一个有开发效率的程序员

那么说了这么多，今天的主要目的就是初步的来看看标准库的那些事。

C++标准库的体系结构

C++标准库的设计思想

C++ Standard Library Vs. Standard Template Library

程序中标准库的引用

C++标准库的命名空间

C++标准库的资料库

STL的六大部件

组建之间的关系

C++标准库中的组件之间的关系图 
//六大部件的使用
#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;
}
时间复杂度与元素数量关系

1.可见随着元素数量增加，对算法要求越高，否则算法不合理会导致得不到结果
2.对于同样的元素数量，不同的算法之间的差别也比较大
3.在数据量很小的情况下，复杂度体现不出太大的差别
当发现算法的时间复杂的大于O(n^2)时，应劲量降低时间复杂度

容器（Container）

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 
      - 底层数据结构：***动态数组***
      - 仅能够向后增长，成长过程相对较慢[ 因为，需要在空间中找到新位置，再将元素搬移过去 ]
      - 两倍扩充，容易浪费空间
![vector内存图](https://img.haomeiwen.com/i5688965/c00c7322cf6e8818.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
    - 常用函数
      - `push_back()`：添加元素
      - `size()`：获取元素数量
      - `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
  - 底层数据结构：***数组们的数组***
deque的内存图

- 双向开口，可进可出的容器
- 每一个空间都指向一个buffer，buffer中的元素有顺序


deque的结构图

分配器（Allocators）

以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>   //內含 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, 創建一個 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);     //我刻意令參數為 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);     //我刻意令參數為 3, 但這有何意義!! 一次要 3 個 ints? 
#endif          
}                                                           
}

迭代器（Iterators）

迭代器的前闭后开区间 
Container<T> c;
.....
Container<T>::iterator ite = c.begin();
for(; ite != c.end(); ite++){
......}

算法（Algorithms）、 适配器（Adapters）、（Functors）

参见：
(Boolan) C++ STL与泛型编程——算法、仿函数、Adapter

上一篇下一篇

猜你喜欢

热点阅读