MyNote

[TOC]

STL ​

  1. STL是generic programming，强调data和method分开
    和oop不一样
  2. 六大组件：容器，迭代器，算法，分配器，适配器，仿函数
    container，iterator，algorithm，allocator，adapter，functor
  3. Algorithm通过iterator确定container的范围，取container的元素
  4. 为什么list不能用::sort()来排序？ 因为::sort()的源码里对迭代器进行了first+(last+first)/2这样的操作，这种操作只支持random access iterator
  5. 所有的algorithm最终涉及元素本身的操作都是比大小
  • template
    1. 类模板
    2. 函数模板
      类模板需要<>声明是什么类，函数模板不需要，他会进行argument deduction
    3. member template
    4. 模板特化specialization、partial specialization
      • 偏特化有两种，一种是个数上偏。两个泛化参数，只特化一个
      • 另一种是范围上偏。T*或const T*这样的偏特化

容器 &#8203;

顺序容器 &#8203;

string &#8203;

迭代器返回最后一个元素的下一个元素
string重新申请空间时，迭代器会失效
std::sort(str.begin(), str.end(), greater<char>());
greater<char>()是一个仿函数，表示从大到小排序

数组 &#8203;

vector &#8203;

vector 的reserve增加了vector的capacity，但是它的size没有改变！而resize改变了vector的capacity同时也增加了它的size！ 原因如下：

  1. reserve是容器预留空间，但在空间内不真正创建元素对象，所以在没有添加新的对象之前，不能引用容器内的元素。加入新的元素时，要调用push_back()/insert()函数。
  2. resize是改变容器的大小，且在创建对象，因此，调用这个函数之后，就可以引用容器内的对象了，因此当加入新的元素时，用operator[]操作符，或者用迭代器来引用元素对象。此时再调用push_back()函数，是加在这个新的空间后面的。

array &#8203;

valarray &#8203;

双端队列 &#8203;

  1. dequeue是分段连续
  2. insert(pos,val)的时候会先判断pos距离哪一段比较近
  3. dequeue的迭代器会模仿连续空间
  4. stack和queue都不允许遍历，所以不提供迭代器
  5. stack和queue也能以list为底层结构实现
  6. queue不可用vector实现，因为vector没有pop_front;stack可以
  7. stack和queue都不能选set或map做底层

queue &#8203;

stack &#8203;

链表 &#8203;

list &#8203;

list和vector的区别

  1. vector是动态数组，查找快，尾添加在不申请内存的情况下也快；插入删除慢
  2. list是双向循环链表，随机访问慢，插入删除快

forward_list &#8203;

关联容器 &#8203;

有序容器(红黑树) &#8203;

  1. rbTree自动按顺序排列的，我们不应该用iterator改变树的节点的值，会破坏树的结构。但是map的data是可以改的，key不可改
  2. rbTree提供两种insert。insertUnique()和insertEqual()
  3. 仿函数的大小是0，编译器对于大小为0的class，实例化的对象大小为1
  4. 红黑树是双向的, 平衡排序二叉树

map &#8203;

  • 无法用set或multiset的iterator改变元素的key，可改变data
  • map可以用[]直接插入，内部调用lower_bound()和insert()

multimap &#8203;

  • multimap不可用[]实现insertion

set &#8203;

  • 无法用set或multiset的iterator改变元素的值
  • 因为set的key就是value
  • algorithm提供了find(), set自己也提供了find，用后者

multiset &#8203;

无序容器(散列表Boost) &#8203;

hashtable:
bucket一般比元素个数多。
当检测到bucket的个数==元素个数时，会自动倍增到质数bucket的个数
并把原来的元素打散重新放rehash,放的位置等于这个数%bucket的个数

  • bucket_count()
  • max_bucket_count()
  • load_factor()
  • max_load_factor()这个值固定是1

unordermap &#8203;

unordermultimap &#8203;

unorderset &#8203;

unordermultiset &#8203;

hash_map &#8203;

算法 &#8203;

  • container是class template
  • algorithm是function template
  • 算法看不到容器，只看到iterator
  • 算法通常有两个版本，其中一个允许加入自己的运算规则
  • accumulate
  • function object函数对象，class或struct里只重载()
  • for_each replace() replace_if() replace_copy()
  • count() count_if()
    • 不带count的容器arry,forward_list,vector,list,dequeue
    • Assiciated container都自带count
  • find()
    算法里的find是循序查找
    Associated container都有自己的find
  • sort
    Associated container都没有sort
    sort要求random access iterator，给list和forward_list会出错
  • rbegin() rend()
  • bool binary_search() 里面调用lower_bound()

迭代器 &#8203;

  • array和vector的迭代器是random access
  • dequeue也是，queue和stack没有迭代器
  • list是bidirectional
  • forward list是forward
  • map和set是bidirectional
  • unordered_map set是bidirectional或者forward
  • istream_iterator是input iterator
  • istream_iterator是output iterator
  • 不同类型的迭代器之间有继承关系
  • 可以直接继承struct，里面只有几个typedef

分配器 &#8203;

  1. 在vc里的Allocator只是通过::operator new和::operator delete完成allocate和deallocate

  2. gunc2.9的alloc则不一样，它要尽量减少malloc的次数。一共16条链表负责n*8字节大小的申请。容器的大小会被调整到8的倍数，分到相应的链表那里，直接malloc一大块。然后再分块切割，切割出来的内存用链表串起来

  3. gun4.9又改回普通的，alloc被保存在extension alloctors里的__pool_alloc。想用旧版：

    vector<string, __gun_cxx_::__pool_alloc<string>> vec

仿函数 &#8203;

  • functor只为algorithm服务
  • 就是一个class里重载了()，是函数对象
  • 分类
    • logical逻辑运算类
    • Arithmetic算术运算类
    • relational关系运算类
  • 仿函数适配算法需要继承binary_function或者union_function

适配器 &#8203;

  • functor adapter bind2nd() not1()
  • iterator adapter
  • container adapter stack，queue