C++标准库与泛型编程学习笔记

感谢侯捷老师

基础知识

  1. 六大部件

    • 容器(containers):数据存放在里面
    • 分配器(Allocators):支持容器的内存管理
    • 算法(Algorithms):一个个模板函数
    • 迭代器(Iterators):泛化的指针
    • 适配器(Adapters):有容器/迭代器/仿函数适配器，可以帮他们进行转换

    • 仿函数(Functors):相似于函数

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      #include<vector>
      #include<algorithm>
      #include<functional>
      #include<iostream>
      ........
      int main(){
      	int ia[6]={27,210,....};
      	vector<int,allocator<int>>vi(ia,ia+6);//分配器不写会默认帮你搞好;vi是iterator;
      	cout<<count_if(vi.begin(),vi.end(),notl(bind2nd(less<int>(),40)));//count_if 是算法,not1是function adapter(negator)，表示否定，大于等于40;bind2nd是function adapter(binder),绑定第二参数,这里的作用是有没有小于40;less是function object 仿函数;not1(....)这行称作predicate
      }

  2. 复杂度 略

  3. “前闭后开”区间：标准库用 c.begin()指的是头,c.end()指向尾巴的后面一个,因此是[);所以*(c.end())是不行的;

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    Container<T> c;
    ....
    Container<T>::iterator ite=c.begin();
    for(;ite!=c.end();++ite){
    	.....
    }
    //range-based for statement C++11
    for(decl:coll){
        statement;
    }
    //例子:
    std::vector<double>vec;
    ...
    for(auto elem:vec){
        std::cout<<elem;
    }
    for(auto& elem:vec){
        elem*=3;//使用引用才能变;
    }
    //auto的使用;
    list<string>c;
    list<string>::iterator ite;
    ite=::find(c.begin(),c.end(),target);
    //等价于
    auto ite=::find(c.begin(),c.end(),target);

容器测试

  1. 分类:

    1. Sequence Containers(序列式):

      Array:固定元素大小的数组

      Vector:末端可以扩张的数组

      Deque(/dek/):前后可以扩张的数组,双向队列

      List:双链

      Forward-List:单链,内存小于前者

    2. Associative Containers(关联式):

      适合查找

      Set/Multiset:集合,底部用红黑树做;Multiset可以重复

      Map/Multimap:有序的键/值对,后者的key可以重复,底部用红黑树做;

    3. Unordered Containers(不定序的元素):

      Unordered set/Multiset:集合,底部基于哈希-拉链法

      Unordered Map/Multimap:有序的键/值对,底部基于哈希-拉链法

  2. 容器速率直观比较:

    (单位是毫秒)

    • Array:47,187(项目:50万随机数for循环赋值时间和排序+二分查找时间)

    • Vector:3063,2765(项目:100万随机数for循环push_back和排序+二分查找时间）a.size()=1000000,a.capacity()=1048576,因为vector增加的时候会预留空间,长着长着开一个两倍的空间复制进去;这个例子里面用find找元素比排序+二分快,0毫秒

    • List:3265,2312,16(项目:100万随机数for循环push_back和排序+二分查找时间和find的时间),list自带sort

    • forward_list:3204,15,2656(项目:100万随机数,find的时间,sort的时间) ，它也自带sort

    • slist:非标准库里面,#include<ext\slist>里面有;和forward_list使用差不多;

    • deque:2704,15,3110(项目:100万随机数push_back,find函数,使用全局sort)deque的连续是一种假象;它是分段连续,分成一个个buffer,由指针指着;如果buffer用完了就再申请一块buffer;

    • stack: deque其实涵盖了stack和queue;它们两个的底层都是deque;812(项目:30万随机数push)

    • queue:890(项目:30万随机数push)

      因为stack,queue是由deque实现的,所以也被称为容器适配器

    • multiset:6609,203,0(项目:100万随机数insert放进去和全局find和自己的find)关联式容器找东西非常快

    • multimap:4812,0(项目:<index,100万随机数> insert放进去和自己的find)

    • unordered_multiset:4406,109,0(项目:100万随机数insert进去和全局find和自带find) ;bucket_count()可以看出篮子的个数,篮子一定比元素多;load_factor()可以看出负载因子;

    • unordered_multimap:4313,0(项目:100万随机数insert进去和自带的find)

    • set:3922,0,0(项目:100万随机数insert进去和全局find和自带find)

    • map:4890,0(项目:100万放进去和自带的find)；multiset不能用c[i]=string(buf)只能用insert函数插入,但是map可以；

    • unordered_map,unordered_set:略

    • 一些老版本的容器比如slist,hash_set,hash_map.hash_multiset,hash_multimap要另外include;

分配器测试:

下面都是GNU-C里面的:

  1. 分类器使用示例: 

    1
    template<typename_Tp,typename_Alloc=std::allocator<_Tp>>class vector:protected_Vector_base<_Tp,_Alloc>

  1. 不同分配器的使用示例:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    //使用std::allocator意外的allocator需要自行#include<ext\....>
    #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\new_allocator.h>

    ....
    list<string,allocator<string>> c1;
    list<string,__gnu_cxx::malloc_allocator<string>> c2;
    list<string,__gnu_cxx::new_allocator<string>> c3;
    list<string,__gnu_cxx::__pool_allocator<string>> c4;
    list<string,__gnu_cxx::__mt_allocator<string>> c5;
    list<string,__gnu_cxx::bitmap_allocator<string>> c6;

  1. 分配器可以分配内存，但是不如malloc/free;new/delete舒服，释放内存很麻烦;比如:

    1
    2
    3
    4
    int*p;
    allocator<int>alloc1;
    p=alloc1.allocate(1);
    alloc1.deallocate(p,1);