C++stl

三十一章 STL 容器

1. 顺序容器

   1. vector<T, A=std::allocator>
   2. list<T,A>
   3. forward_list<T,A>
   4. deque<T,A>

2. 优先选用vector，除非有其他特殊理由

3. 有序关联容器,C是比较类型，A是分配器类型，用平衡二叉树（通常是红黑树）实现

   1. map<K,V, C=std::less , A=std::allocator<std::pair<const K,V>>>
   2. multimap<K,V,C,A>
   3. set<K,C, A=st::allocator>
   4. multiset<K,C,A>

4. 无序关联容器：H是哈希函数类型，E是相等性测试，用溢出链表法的哈希表实现

   1. unordered_map<K,V, H=std::hash , E=std::equal_to,A>
   2. unordered_multimap<K,V,H,E,A>
   3. unordered_set<K,H,E,A>
   4. unordered_multiset<K,H,E,A>

5. 容器适配器，C是容器类型

   1. priority_queue<T, C=std::deque ,Cmp=std::less >：T的优先队列，Cmp是优先级函数类型
   2. queue<T, C=std::vector>
   3. stack<T, C=std::vector>

6. 拟容器：具有标准容器大部分特性，但非全部

   1. T[N], 内置数组
   2. array<T,N>
   3. basic_string<C,Tr,A>： Tr表示字符萃取
   4. valarray: 数值向量，支持向量运算，适合大量向量运算情形
   5. bitset: N个二进制位集合，支持集合操作
   6. vector: vector特例化版本，紧凑保存二进制

7. 对元素的要求：对象类型必须允许容器拷贝、移动以及交换元素。

8. 若对象无法拷贝，替换方案是把对象的指针保存在容器中

9. 关联容器要求元素能够排序，排序标准必须定义一个严格弱序

10. 构造函数、析构函数、赋值操作

    1. C c{}

    2. C c{a} //a,分配器

    3. C c(n) //关联容器不适用

    4. C c(n,x)//x的n个拷贝，关联容器不适用

    5. C c{elem}//用elem初始化c，如C有初始化器列表构造函数，优先使用

    6. C c{c2}

    7. C c{move(c2)}

    8. C c{{elem},a}

    9. C c{b,e}// [b,e)

    10. C c{b,e,a}

    11. c.~C()

    12. c2=c

    13. c2=move(c)

    14. c={elem}

    15. c.assign(n,x)//关联容器不适用

    16. c.assign(b,e)

    17. c.aasign({elem})

        赋值操作不会拷贝或移动分配器

11. 容器通常都很大，一般以引用或移动来传递实参和返回值

12. 大小和容量

    1. c.size()
    2. c.empty()
    3. c.max_size() //c的最大可能元素数目
    4. c.capacity() //vector, string
    5. c.reserve(n) //vector, string， 提高性能可预测性和避免迭代器失效的方式
    6. c.resize(n) //增加的元素是默认值，适用于顺序容器和string
    7. c.reserve(n,v) //增加的元素初始化位v，顺序容器和string
    8. c.shrink_to_fit(). //capacity==size, vector deque string
    9. clear()
    10. 改变大小和容量时，注意迭代器可能会失效。关联容器元素的迭代器只有当元素被删除时才失效

13. 迭代器

    begin() ,end() ,cbegin() ,cend() ,rbegin() ,rend() ,crbegin() ,crend()

14. 元素访问

    1. c.front() //首元素，关联容器不适用
    2. c.back() //尾元素，forwart_list 和关联容器不适用
    3. c[i] //不做范围检查，链表和关联容器不适用
    4. c.at(i) //若i超出范围，抛出out_of_range异常，链表和关联容器不适用
    5. c[k] //若未找到则插入(k,mapped_type{}),只适用于map和unordered_map
    6. c.at(k)//若未找到抛出out_of_range异常，只适用于map和unordered_map

15. 栈操作

    1. c.push_back(x) //使用拷贝或移动
    2. c.pop_back() //删除尾元素，不返回值
    3. c.emplace_back(args) //用args构造一个元素添加到c的尾元素之后

16. 列表操作

    1. q=c.insert(p,x) //x插入到p之前，使用拷贝或移动
    2. q=c.insert(p,n,x) //p之前插入x的n个拷贝，若c为关联容器，p不是插入位置，而是提示搜索开始位置
    3. q=c.insert(p,first,last) //p之前插入[first,last)，不适用关联容器
    4. q=c.insert(p,{elem})//与2类似
    5. q=c.emplace(p, args) //不适用于关联容器
    6. q=c.erase(p)
    7. q=c.erase(first, last) //删除[first, last)
    8. c.clear()
    9. insert系列函数返回结果q指向插入的最后一个元素，erase的q指向删除的最后一个元素之后的位置
    10. forward_list 使用insert_after, 无序容器使用emplace_hint()

17. 其他操作

    c1==c2, c1!=c2, c1<c2, c1<=c2, c1>c2, c1>=c2 //比较元素

    c1.swap(c2) //交换元素和分配器，不抛出异常

    swap(c1,c2)

18. vector

    1. 元素紧凑存储，所有元素不存在额外内存开销，大致为sizeof(vecor) + vec.size()*sizeof(X)
    2. 遍历特别快，没有间接寻址开销
    3. 高效的随机访问

19. list，forward_list

1. 插入，删除高效，不影响其他元素迭代器
2. 每个list元素占有更多空间，通常每个元素至少多4个字
3. 遍历慢，间接寻址
4. forward_list 看作为空链表和很短的链表的优化

1. list forward_list 共同操作

   1. lst.push_front(x)//插入首元素之前，使用移动或者拷贝
   2. lst.pop_front()//删除首元素
   3. lst.emplace_front(args)//将T{args}添加到首元素之前
   4. lst.remove(x)//删除所有等于x的元素
   5. lst.remove_if(f) //删除所有满足f(x)==true的元素
   6. lst.unique() //删除所有相邻重复元素
   7. lst.unique(f) //与6相同，用f判断
   8. lst.merge(lst2) //合并有序链表lst和lst2，用<确定序，将lst2合并入lst，lst2被情况，稳定算法
   9. lst.merge(lst2, f)//与8相同，用f确定序
   10. lst.sort()//排序，用<确定序
   11. lst.sort(f) //排序，用f确定序
   12. lst.reverse()//反转lst中的元素，不抛出异常

2. list 操作

   1. lst.splic(p, lst2) //将lst2插入到p之前，lst2变为空
   2. lst.splice(p, lst2, p2) //将p2指向的lst2的元素插入到p之前，该元素从lst2中删除
   3. lst.splice(p, lst2, b, e) //将[b,e)指向的元素插入p之前，这些元素从lst2删除

3. forward_list无法访问迭代器之前的元素，emplace, insert, erase, splice都作用于迭代器之后的位置:

   1. p2=lst.emplace_after(p, args)
   2. p2=lst.insert_after(p,x)
   3. p2=lst.insert_after(p, n, x)
   4. p2=lst.insert_after(p, b, e)
   5. p2=lst.insert_after(p, {elem})
   6. p2=lst.erase_after(p) //删除p之后的元素，p2指向p之后的元素或lst.end()
   7. p2=lst.erase_after(b,e)//删除[b,e)间的原属，p2指向e
   8. lst.splice_after(p, lst2)
   9. lst.splice_after(p, b, e)
   10. lst.splice_after(p, lst2, p2)
   11. lst.splice_after(p, lst2, b, e)

4. map<K, T, C, A>构造函数： cmp是比较器，a是分配器

   1. map m{cmp, a}
   2. map m{cmp}
   3. map m{}
   4. map m{b,e,cmp,a}
   5. map m{b,e,cmp}
   6. map m{b,e}
   7. map m{m2} //拷贝和移动构造函数
   8. map m{a}
   9. map m{m2, a}
   10. map m{ {elem}, cmp, a}
   11. map m{ {elem}, cmp}
   12. map m{ {elem} }

5. 关联容器操作

   1. p=c.lower_bound(k) //p指向关键字>=k的第一个元素或c.end()(未找到)，只适用于有序容器
   2. p=c.upper_bound(k) //p指向关键字>k的第一个元素或c.end()(未找到)，只适用于有序容器
   3. pair(p1, p2)=c.equal_range(k) // p1=c.lower_bound(k), p2=c.upper_bound(k)
   4. pair(p,b)=c.insert(x)//x是一个value_type或能拷贝入一个value_type的某种东西(如一个双元素的tuple)。若x成功插入，则b为true；若容器中已有元素与x关键字相同，b为false；p指向关键字与x相同的（可能是新的）元素
   5. p2=c.insert(p, x) //x与4相同，p提示从哪里开始搜索关键字与x相同的元素；p2指向关键字与x相同的元素
   6. c.insert(b,e) //对[b,e)间的每个p，执行c.insert(*p)
   7. c.insert({args}) // 将initializer_list args中的每个元素插入容器，元素类型为pair<key_type, mapped_type>
   8. p=c.emplace(args)//从args构造类型为value_type的对象，插入c，p指向该对象
   9. p=c.emplace_hint(h, args) //与8相同，h为c中迭代器，用来指示从哪里开始搜索新元素存放位置
   10. r=c.key_comp()//r是关键字比较对象的一个拷贝，只适用于有序容器
   11. r=c.value_comp()//r是值比较对象的一个拷贝， 只适用于有序容器
   12. n=c.count(k) //n为关键字等于k的元素数目

6. 关联容器中元素的关键字是不可变的。

7. unordered_map<K,T,H,E,A>构造函数

   1. unordered_map m{n, hf, eql, a}; //构造n个桶的m，哈希函数hf，相等比较函数eql，分配器为a
   2. unordered_map m{n, hf, eql}
   3. unordered_map m{n, hf}
   4. unordered_map m{n}
   5. unordered_map m{}
   6. unordered_map m{b, e, n, hf, eql, a}// 初始元素[b,e)
   7. unordered_map m{b, e, n, hf, eql}
   8. unordered_map m{b, e, n, hf}
   9. unordered_map m{b, e, n}
   10. unordered_map m{b, e}
   11. unordered_map m{ {elem}, n, hf, eql, a} //初始元素{elem}
   12. unordered_map m{ {elem}, n, hf, eql}
   13. unordered_map m{ {elem}, n, hf}
   14. unordered_map m{ {elem}, n}
   15. unordered_map m{ {elem}}
   16. unordered_map m{m2}
   17. unordered_map m{a}
   18. unordered_map m{m2, a}

8. 哈希和相等判定函数：函数对象，lambda，特例化标准库hash和equal_to模版

9. 哈希策略

   1. h=c.hash_function()//h为c的哈希函数
   2. eq=c.key_eq()//eq是c的相等性检测函数
   3. d=c.load_factor() //d是元素数除以桶数：double(c.size())/c.bucket_count(),不抛出异常
   4. d=c.max_load_factor()//最大装载因子，不抛出异常
   5. c.max_load_factor(d)//将c的最大装载因子设置为d，若c的装载因子已经接近其最大装载因子，c将改变哈希表大小（增加桶数）
   6. c.rehash(n)//令c的桶数>=n
   7. c.reserve(n)//留出能容纳n个表项的空间（考虑装载因子）：c.rehash(ceil(n/c.max_load_factor()))

10. 用异或操作组合标准哈希函数得到的哈希函数通常有很好的性能

11. 70%的装载因子通常是一个好选择

12. 桶相关接口

    1. n=c.bucket_count(). //c的桶数n，noexcept
    2. n=c.max_bucket_count()//一个桶中最大元素数n，noexcept
    3. m=c.bucket_size(n)//第n个桶中元素数m
    4. i=c.bucket(k) //关键字k的元素在第i个桶中
    5. p=c.begin(n)//p指向桶n中首元素
    6. p=c.end(n) //p指向桶n中尾元素之后的位置
    7. p=c.cbegin(n) //与5同，const迭代器
    8. p=c.cend(n) //与6同，const迭代器

13. 容器适配器提供受限的特殊接口，不直接访问底层容器，不提供迭代器和下标操作

14. stack，queue， priority_queue

三十二章 STL 算法

1. 不修改序列的算法

   1. f=for_each(b, e, f) //对[b,e)中的每个元素x执行f(x);返回f
   2. 序列谓词
      1. all_of(b,e,f) // [b,e)中所有x都满足f(x)?
      2. any_of(b,e,f)// [b,e)中某个x都满足f(x)?
      3. none_of(b,e,f)// [b,e)中所有x都不满足f(x)?
   3. count
      1. x=count(b,e,v)//x为 *p==v的元素数量
      2. x=count_if(b,e,f) //满足f(*p)的元素数量
   4. find搜索具有特定值或令谓词为真的元素
      1. p=find(b,e,v) //p指向[b:e)中第一个满足*p==v的元素
      2. p=find_if(b,e,f) //与1同， f(*p)
      3. p=find_if_not(b,e,f) //与2同，!f(*p)
      4. p=find_first_of(b,e,b2,e2) //第一个满足 *p==*q, q指向[b2:e2)中的某个元素
      5. p=find_first_of(b,e,b2,e2,f) //与4同，f(*p,*q)
      6. p=adjacent_find(b,e) //第一个满足*p==*(p+1)
      7. p=adjacent_find(b,e,f) //与6同， f(*p, *(p+1))
      8. p=find_end(b,e,b2,e2) //最后一个满足*p == *q, q指向第二个序列中的某个元素
      9. p=find_end(b,e,b2,e2,f) // 与8同，f(*p, *q)
   5. equal和mismatch
      1. equal(b,e,b2) //所有元素相等v==v2?
      2. equal(b,e,b2,f) //所有元素满足f(v,v2)?
      3. pair(p1,p2) = mismatch(b,e,b2) //p1指向第一个满足!(*p1==*p2)的元素，否则p1==e
      4. pair(p1,p2) = mismatch(b,e,b2,f)//与3同，!f(*p1, *p2)
   6. search()查找给定序列是否是另一个序列的子序列
      1. p=search(b,e,b2,e2)//p指向[b:e)中第一个满足[p:p+(e2-b2)) 等于[b2:e2)的*p
      2. p=search(b,e,b2,e2,f) // 与1同，使用f比较
      3. p=search(b,e,n,v) //p指向[b:e) 中第一个满足[p:p+n)间所有元素值均为v的位置
      4. p=search(b,e,n,v,f)//与3同，使用f(*p, v)比较

2. 修改序列的算法

   1. p=transform(b,e,out,f)//对每个元素应用f，写到out, p==out+(e-b)

   2. p=transform(b,e,b2,out,f)//对两个序列的元素应用f(*p1,*p2), 结果写入out， p==out+(e-b)

   3. copy()：只有当两个序列不重叠或输出序列的末尾位于输入序列内部时，才可以使用copy

      1. p=copy(b,e,out) //拷贝所有元素到out; p==out+(e-b)
      2. p=copy(b,e,out,f) //将满足f(x)的元素x拷贝到[out:p)
      3. p=copy(b,n,out) //拷贝n个元素，p==out+n
      4. p=copy_backward(b,e,out) //与1同，从尾元素开始拷贝
      5. p=move(b,e,out)//与1同，使用移动操作
      6. p=mov_backward(b,e,out) //与5同，从尾元素开始移动

   4. unique

      1. unique(b,e)//移动[b,e)中的一些元素，是的[b,p)中无连续重复元素
      2. unique(b,e,f) //与1同，使用f(*p,*(p+1))判断是否重复
      3. unique_copy(b,e,out) //拷贝元素到out，不拷贝连续重复元素
      4. unique_copy(b,e,out,f)//与3同，不拷贝连续重复元素，使用f(*p, *(p+1))判断重复

   5. remove， replace

      1. p=remove(b,e,v) //删除值为v的元素
      2. p=remove_if(b,e,f) //删除满足f(*p)的元素
      3. p=remove_copy(b,e,out,v) //拷贝不为v的元素
      4. p=remove_copy_if(b,e,out,f) //拷贝不满足f(*p)的元素
      5. reverse(b,e) //逆序排列
      6. reverse_copy(b,e,out) //逆序拷贝
      7. replace(b,e,v,v2)
      8. replace(b,e,f,v2)
      9. p=replace_copy(b,e,out,v,v2)
      10. p=replace_copy_if(b,e,out,f,v2)

   6. rotate(), random_shuffle, portition()

      1. p=rotate(b,m,e) //循环左移：将[b:e)看作一个环，*(b+i)移动到、*((b+(i+(e-m))%(e-b))
      2. p=rotate_copy(b,m,e,out):循环左移拷贝到out
      3. random_shuffle(b,e) //洗牌b,e中的元素，使用默认随机数发生器
      4. random_shuffle(b,e,f) //使用随机数发生器f
      5. shuffle(b,e,f) //使用均匀分布随机数发生器f
      6. p=partition(b,e,f)//满足f(*p)的元素置于区间[b:p), 其他元素置于[p:e)
      7. p=stable_partition(b,e,f)//与6同，保持相对顺序
      8. pair(p1,p2)=partion_copy(b,e,out1,out2,f)//满足f(*p)的元素拷贝到[out1:p1), 否则拷贝到[out2:p2)
      9. p=partition_point(b,e,f) //p指向满足all_of(b,p,f)且none_of(p,e,f)
      10. Is_partition(b,e,f) // 满足f(*p)的元素都在!f(*p)之前吗？

   7. 排列：生成一个序列的所有排列，若next_*或prev_*操作成功返回true，否则返回false

      1. x=next_permutation(b,e)//将[b,e)变换为字典序上的下一个排列
      2. x=next_permutation(b,e,f)//与1同，用f比较元素
      3. x=prev_permutation(b,e) //前一个排列
      4. x=prev_permutation(b,e,f)//使用f比较元素
      5. is_permutation(b,e,b2) //判断b2序列是否是[b,e)的一个序列
      6. is_permutation(b,e,b2,f)//与5同，用f比较

   8. fill 向序列元素赋值和初始化元素

      1. fill(b,e,v) //赋值
      2. fill_n(b,n,v)
      3. generate(b,e,f)//将f()赋予每个元素， 赋值
      4. p=generate_n(b,n,f) // p==b+n
      5. uninitialized_fill(b,e,v) //初始化
      6. p=uninitialized_fill_n(b,n,v) // p==b+n
      7. p=uninitialized_copy(b,e,out) // 用b,e中的元素初始化out序列元素，p==out+(e-b)， 目标元素必须是内置类型或未初始化的
      8. p=uninitialized_copy_n(b,n,out) //p=out+n

   9. swap

      1. swap(x,y)
      2. swap_ranges(b,e,b2)//对每个元素调用swap(v,v2)
      3. Iter_swap(p,q) // swap(*p,*q)

   10. 排序和搜索, sort要求随机访问迭代器

       1. sort(b,e)

       2. sort(b,e,f)

       3. stable_sort(b,e) //保持相等元素相对顺序

       4. stable_sort(b,e,f)

       5. partial_sort(b,m,e) //部分排序，[b,m)有序即可

       6. partial_sort(b,m,e,f)

       7. partial_sort_copy(b,e,b2,e2)//部分排序[b,e), 排好前e2-b2个元素，拷贝到[b2,e2); p为e2和b2+(e-b)的较小者

       8. partial_sort_copy(b,e,b2,e2,f)//同7

       9. is_sorted(b,e)

       10. is_sorted(b,e,f)

       11. p=is_sorted_until(b,e) //p指向第一个不符合升序的元素

       12. p=is_sorted_until(b,e,f)

       13. nth_element(b,n,e)//*n的位置恰好是[b,e)排序后它应处的位置,即[b,n)中的元素都<=*n, 且[n,e)中的元素都>=*n

       14. nth_element(b,n,e,f)

       15. 排序C风格字符串需要一个显示的比较标准

   11. 二分搜索，提供有序序列上的二分搜索，只需要前向迭代器

       1. p=lower_bound(b,e,v)//p指向v首次出现的位置，如果没有找到，p指向第一个大于v的元素或者e
       2. p=lower_bound(b,e,v,f)
       3. p=upper_bound(b,e,v)//p指向第一个大于v的元素
       4. p=upper_bound(b,e,v,f)
       5. binary_search(b,e,v) //v在有序序列[b,e)中吗？
       6. binary_search(b,e,v,f)
       7. pair(p1,p2)=equal_range(b,e,v)//[p1,p2)是值为v的子序列，通常用二分搜索查找v
       8. pair(p1,p2)=equal_range(b,e,v,f)

   12. merge，将两个有序序列合并为一个,可接受不同类别的序列和不同类型的元素：

       1. p=merge(b,e,b2,e2,out)

       2. p=merge(b,e,b2,e2,out,f)

       3. inplace_merge(b,m,e)//原址合并，将两个有序序列[b,m), [m,e)合并为有序序列[b,e)

       4. inplace_merge(b,m,e,f)

       5. 例子：

          vector v{3,1,2,4};

          list lst{0.5, 1.5, 2, 2.5}

          sort(v.begin(), b.end());

          Vector_double v2;

          merge(v.begin(), v.end(), lst.begin(), lst.end(), back_inserter(v2));

   13. 集合算法

       1. includes(b,e,b2,e2). //b,e中的所有元素都在b2,e2中？
       2. includes(b,e,b2,e2,f)
       3. p=set_union(b,e,b2,e2,out)//创建一个有序序列[out,p),包含两个序列所有元素
       4. p=set_union(b,e,b2,e2,out,f)
       5. p=set_intersection(b,e,b2,e2,out)//同3，包含两个序列共同元素
       6. p=set_intersection(b,e,b2,e2,out,f)
       7. p=set_difference(b,e,b2,e2,out)//同3，在b,e中但不在b2,e2中的元素
       8. p=set_difference(b,e,b2,e2,out,f)
       9. p=set_symmetric_difference(b,e,b2,e2,out)//同3，在b,e或b2,e2 中，但不同在两者中
       10. p=set_symmetric_difference(b,e,b2,e2,out,f)

   14. 堆—>最大值优先

       1. make_heap(b,e)
       2. make_heap(b,e,f)
       3. push_heap(b,e)//将*(e-1)添加到堆[b,e-1),是的b，e还是一个堆
       4. push_heap(b,e,f)
       5. pop_heap(b,e) // 删除最大值，[b,e-1)仍然是堆
       6. pop_heap(b,e,f)
       7. sort_heap(b,e) //排序堆
       8. sort_heap(b,e,f)
       9. is_heap(b,e)
       10. is_heap(b,e,f)
       11. is_head_until(b,e)//p是满足[b,p)是堆的最大位置
       12. is_heap_until(b,e,f)

   15. 最大值和最小值

       1. x=min(a,b), max(a,b)
       2. x=min(a,b,f), max(a,b,f)
       3. x=min({elem}), max({elem})
       4. x=min({elem},f), max({elem},f)
       5. pair(x,y)=minmax(a,b)
       6. pair(x,y)=minmax(a,b,f)
       7. pair(x,y)=minmax({elem})
       8. pair(x,y)=minmax({elem},f)
       9. p=min_element(b,e)
       10. p=min_element(b,e,f)
       11. p=max_element(b,e)
       12. p=max_element(b,e,f)
       13. pair(x,y)=minmax_element(b,e) //x,y为迭代器
       14. pair(x,y)=minmax_element(b,e,f)

三十三章 迭代器

1. 迭代器类别

   1. 输入迭代器：istream : ++, *, ==, !=, ->, 单一读
   2. 输出迭代器：ostream: ++, *， 单一写
   3. 前向迭代器：forward_list： ++， *, ->, ==, !=, 反复读写
   4. 双向迭代器: list, map, set： ++， - -， *, ->, ==, !=
   5. 随机访问迭代器： vector: [], +, +=, -, -=, <, <=, >, >=,++, - -, *, ->, == , !=

2. 迭代器萃取

   1. iterator_traits //非指针Iter的萃取类型

   2. iterator_traits<T*> //指针T*的萃取类型

   3. input_iterator_tag //输入迭代器类型

   4. output_iterator_tag //输出迭代器类型

   5. forward_iterator_tag //派生自input_iterator_tag

   6. bidirectional_iterator_tag //派生自forward_iterator_tag

   7. random_access_iterator_tag //派生自bidirectional_iterator_tag

   8. tag的本质是类型，可用于标签分发，如：

      template< typename Iter>

      void advance_helper(Iter p, int n, random_access_iterator_tag){

      ​ p += n;

      }

      template< typename Iter>

      void advance_helper(Iter p, int n, forward_iterator_tag){

      ​ if(0<n)

      ​ while(n—) ++p;

      ​ else if(n<0)

      ​ while(n++) —p;

      }

      template< typename Iter>

      void advance(Iter p, int n){. //使用最优算法

      ​ return advance_helper(p, n, iterator_traits< Iter>::iterator_category{});

      }

3. 迭代器操作

   1. p++
   2. ++p
   3. *p
   4. –p
   5. p–
   6. p[n]
   7. p->m
   8. p==q
   9. p!=q
   10. p<q
   11. p<=q
   12. p>q
   13. p>=q
   14. p+=n
   15. p-=n
   16. q=p+n
   17. q=p-n
   18. advance(p,n) //p+=n,p至少是一个输入迭代器
   19. x=distance(p,q)// x=q-p,p至少是一个输入迭代器
   20. q=next(p,n) //p至少是一个前向迭代器，q=p+n
   21. q=next(p) // q=p+1
   22. q=prev(p,n)// q = p-n,p至少是一个双向迭代器
   23. q=pre(p)// q = p-1

4. 迭代器适配器

   1. reverse_iterator //反向遍历
   2. back_insert_iterator //尾部插入
   3. front_insert_iterator //头部插入
   4. insert_iterator //任意位置插入
   5. move_iterator // 移动而非拷贝
   6. raw_storage_iterator //写入未初始化的存储空间

5. 一个反向迭代器与其底层迭代器之间的根本关系：&*(reverse_iterator(p)) == &*(p-1)， 可理解为反向迭代器使用正向迭代器实现

6. 对一个reverse_iterator，ri.base()返回一个iterator，指向ri之后的位置；即prev(ri.base())与ri指向相同的元素

7. 插入迭代器，当写数据时，插入器将新元素插入序列而不是覆盖已有元素，防止溢出。

8. 插入器构造函数

   1. ii=inserter(c,p) //ii是一个insert_iterator，指向容器c中的p，在p之前插入
   2. ii=back_inserter(c) //ii是back_insert_iterator, 指向c的back()
   3. ii=front_inserter(c)//ii是front_insert_iterator, 指向c的front()

9. 一个插入器是一个输出迭代器，不能通过插入器读取数据, insert_iterator 操作：

   1. insert_iterator p{c, q}// 为容器c构造一个插入器，指向*q, q必须指向c
   2. insert_iterator p{q} //拷贝构造函数
   3. p=q
   4. p=move(q)
   5. ++p //令p指向下一个元素
   6. p++
   7. *p=x //在p之前插入x
   8. *p++=x //在p之前插入x，然后递增p

10. 移动迭代器：通过移动迭代器读取元素时会移动元素而非拷贝元素，其构造函数：

    mp=make_move_iterator(p)//mp是一个移动迭代器，指向p所指元素

    移动迭代器的operator*()简单返回元素的右值：std::move(q). 例如：

    vector read_strings(istream&);

    auto vs = read_strings(cin);

    vector vs2, vs3;

    copy(vs, back_inserter(vs2)) //从vs向vs2拷贝元素

    copy(vs2, make_move_iterator(back_inserter(vs3)))//从vs2向vs3移动元素

11. 范围访问函数：标准库为容器提供了非成员版本的begin(), end()

    1. p=begin(c) //p是指向容器c的首元素的迭代器，c是一个数组或具有c.begin()
    2. p=end(c)//p是指向容器c的尾后位置的迭代器，c是一个数组或具有c.end()
    3. 只要通过#include 包含了, 具有begin(),end()成员的用户自定义容器就会自动获得非成员版本

12. 函数对象，在< functional>中，标准库提供了若干常用函数对象

    1. equal_to(x,y). // x==y
    2. not_equal_to(x,y). //x!=y
    3. greater(x,y). //x>y
    4. less(x,y). //x<y
    5. greater_equal(x,y) //x>=y
    6. less_equal(x,y). // x<=y
    7. logical_and(x,y)// 总是对两个参数都求值， x&&y
    8. logical_or(x,y) // 总是对两个参数都求值， x||y
    9. logical_not(x) // !x
    10. bit_and(x,y) // x & y
    11. bit_or(x,y) // x|y
    12. bit_xor(x, y) // x^y
    13. f=plus(x, y). //x+y
    14. f=minus(x,y). //x-y
    15. f=multiplies(x,y). //x*y
    16. f=divides(x,y). //x/y
    17. f=modulus(x,y). //x%y
    18. f=negate(x). //. -x

13. 函数适配器：接受一个函数参数，返回一个可用来调用该函数的函数对象

    1. g=bind(f,args)//g(args2) 等价于f(args3)， args3使用args2中的实参替换args中对应的占位符(如_1, _2, _3)得到的,占位符在namespace placeholders中
    2. g=mem_fn(f)//若p是一个指针，g(p,args)表示p->f(args), 否则表示p.mf(args),args可能为空
    3. g=not1(f) // g(x) == !f(x)
    4. g=not2(f) // g(x,y) == !f(x,y)

14. bind()

    1. 重载函数的绑定需要指定绑定的是哪个函数：

       int pow(int, int)

       double pow(double, double)

       auto pow2 = bind(pow, _1,2) //错误, 绑定哪个pow？

       auto pow = bind((double(*)(double, double))pow, _1, 2)

    2. bind接受普通表达式作为参数，对引用参数而言，bind看到他们之前已被解引用。可使用ref(t), cref(t)传递引用参数

15. mem_fn(mf)生成一个函数对象，可以作为非成员函数调用，面向对象调用到函数式调用风格的映射。

    void user(Shape* p){

    ​ p->draw();

    ​ auto draw = mem_fn(&Shape::draw);

    ​ draw(p);

    }

16. function, 是一种类型，可以保存能用调用元算符()调用的任何对象，如普通函数，函数对象，lambda等