C++学习笔记-标准模板库和新特性

标准模板库(STL)

C++11所有容器类型: deque, list, queue, priority_queue, stack, vector, map, multimap, set, multiset, bitset(比特级处理数据的容器), forward_list(单向链表), unordered_map, unordered_multimap, unordered_set, unordered_multiset.
- vector是数组的一种表示, 提供了内存自动管理功能, 随着元素的增减而变化大小.
  在尾部添加或删除元素时间是固定的, 但在头部或中间添加或删除元素需要线性复杂度的时间
  vector 是序列也是可反转容器, 类方法rbegin()返回一个指向反转序列的第一个元素的迭代器, 因此可以用for_each( dice.rbegin(), dice.rend(), Show) 可以逆序输出vector对象dice.
  从vector中间插入删除元素, 迭代器指向的元素会变化
- list 是双向链表, 与vector的关键区别在于, list在链表中的任意位置插入或删除时间都是固定的, 但不支持数组表示法和随机访问. 从链表中间插入删除元素, 迭代器指向的元素不变
  注意, 若list容器内装的是自定义类, 则上述几个函数都需要一个用来比较的函数作为参数
- stack 栈, 底层类为vector, 不允许随机访问或遍历
- queue 队列, 不允许随机访问或遍历
  注意pop是一个删除数据而不是检索数据(因为无返回值)的方法, 如要使用队列中的值应先使用front()检索再使用pop()删除
- deque是双端队列, 在STL中实现类似于vector容器, 也支持随机访问(访问中间元素)
  主要区别: deque在队列头部或尾部(除了中间)插入删除元素时间也是固定的, 因此如果多数操作发生在队列头部或尾部则用deque
- priority_queue优先队列模板类, 以vector为底层类, 与queue的主要区别在于, 最大(或最小)的元素被移到队首, 可以用构造函数 priority_queue pq(greater); 来构造一个最大元素…的优先队列, 其中greater<>()函数是一个预定义的函数对象
- 关联容器(set, map, multiset, multimap)基于树结构, 无序关联容器(unordered_set, unordered_multiset, unordered_map, unordered_multimap)基于哈希表结构, 提高了添加和删除元素的速度以及查找效率(散列查找)
- 注意array<>并非STL容器, 长度是固定的, 因此没有调整容器大小的操作(如push_back()和insert())

自定义类型要存入map, set等内部需要按序存储的容器时, 需要重载 < 运算符:

  friend bool operator<(const Point & p1, const Point & p2) {
      if ( p1.x != p2.x ) return p1.x < p2.x;
      else if ( p1.y != p2.y ) return p1.y < p2.y;
      else return p1.k < p2.k;
  }

但是不能够简单写成

  return (p1.x < p2.x && p1.y < p2.y && p1.k < p2.k);

这样写会导致map搜索元素时会把两个不完全相同的元素也认为是同一个元素

不能随便使用指针栈(如stack<char[40]>), 原因: Stack模板类中的操作对类型有所要求
如果指针采用 char str[40]的形式存储, 由于传进Stack的Pop函数中的是char[40]类型的引用, 无法给str即数组名赋值, 因此将会无法Pop; 如果指针采用动态内存分配(new)存储, 即char* str = new char[40]; 则str存储的地址是固定的, 因此每次读取一个字符串进来都会在上一个字符串的地址重新覆盖原来读取的字符串, 因此每次压入栈的地址值都是一样的, 无意义
解决方法: (调用者)用一个指针数组(字符串数组)存储每一次读进来的字符串)
容器的迭代器是一个容器内定义的成员类, 类似于循环中的循环变量, 如链表结构是以节点为单位的, 迭代器就是一个个节点(一般是一个指针), 迭代器进行自加运算则可以将迭代器指向下一个节点, 即iterator++ 被重载为了 iterator = iterator->next; 如vector类是数组实现的, 迭代器就是一个个指向数组某一个元素的指针, 迭代器++(即指针++)就可以将迭代器(指针)指向下一个元素
迭代器应该满足的特点:
- 可以对迭代器执行解除引用操作, 具有*运算符重载
- 可以赋值, 具有赋值函数
- 可以比较看是否相等, 具有!=或==运算符重载
- 可以遍历容器中的所有元素, 具有++运算符重载(或可以实现+1效果的函数)
迭代器的种类:
- 随机访问迭代器:
  - 正向迭代器
    - 输入迭代器(只读)
    - 输出迭代器(只写)
  - 反向迭代器
    - 输入迭代器(只读)
    - 输出迭代器(只写)
erase()函数删除vector中指定区间之间的元素, 如
```
  vec.erase(vec.begin()+2,vec.begin()+3)
```
删除第二个元素, 即半开半闭区间[2,3)

insert()函数将一个vec中的区间插入到另一个vec的某一个元素前面, 如

  // 将new_v的第二,三个元素插入到old_v第一个元素前面
  old_v( old_v.begin(), new_v.begin()+1, new_v.begin()+3)

模板使得算法独立于存储的数据类型, 迭代器使得算法独立于存储的容器类型(vector, map, set等等)
copy(arr, arr+10, new_vec)的前两个迭代器(最好是输入迭代器)参数限定复制的范围, 第三个迭代器参数(最好是输出迭代器)说明复制到的位置(覆盖). 注意目标容器必须足够大, 因此不能用copy()把数据放到空vector中
输入输出流也有迭代器(类型为ostream_iterator和istream_iterator), 可以使用copy函数来完成输入和输出
函数符(也叫函数对象, 仿函数), 是可以以函数方式与()结合使用的任意对象, 包括函数名, 函数指针和重载了括号运算符的类对象(即定义了函数operator()()的类)。
函数符相关概念：
- 生成器(generator)，是不用参数就可以调用的函数符。
- 一元函数(unary function)，是用一个参数可以调用的函数符(例如提供给for_each()的函数符应当是一元函数，因为它每次用于一个容器元素)。
  - 返回bool值的一元函数是断言 (predicate)。
- 二元函数(binary function)，是用两个参数可以调用的函数符。
  - 返回bool值的二元函数是二元断言 (binary predicate)。
std::less 是一种函数对象类型, 该类型所实例化得到的对象是类型T的 operator< 方法
complex 头文件中包含了complex类, 用于表示复数
valarray 容器是专门用于处理数值运算(不是专门用于存储)的数组类型, 重载了加减乘除, 以及一些数学库内的数学函数(如log)。例如：
- 对于valarray对象vint, vint = log(vint);或者vint.apply(log);语句可以使得vint数组内的每个元素都分别进行一次log运算；
- vint = vint * vint; 可以使得该数组内所有元素自乘一次. 但valarray不提供像vector那样的push_back等函数(因为其大小和array一样也是固定的)
slice 是用作数组下标索引的一个对象, 构造方式为slice slice1(1, 4, 3); 其中1是起始下标, 4是索引数(选择的元素数), 3是跨度, ar[slice1]就表示ar[1], ar[1+3], ar[1+6], ar[1+9] 这四个元素.

C++11允许容器类用initializer_list(这是一种类型)作为参数构造对象, 如

  set<string> set1 = { "ad", "zxc", "asd" };     //注意这里必须用大括号, 大括号与其中的元素统称initializer_list

要注意使用这种方式初始化, 不能隐式地窄转换, 即不能够用

  vector<int> vec = { 1, 2, 3.5 } // 3.5->3为窄转换

序列性容器(vector, string, list等) 使用erase(iterator)之后, 不仅使所有指向被删元素的迭代器失效, 而且使被删元素之后的所有迭代器失效(因为它们都是顺序存储的), 所以不能使用erase(iter++)的方式.
可用方法:
- erase的返回值为下一个有效的迭代器, 所以在erase后, 可用原迭代器接受返回值(若不erase则还是++)
```
for(string::iterator it=str.begin(); it!=str.end(); ){
  if( !isalpha(*it) ){
      it = str.erase(it);    // 也可以写成str.erase(it++);
  }else{
      it++;
  }
}
```
- 在erase掉之后, 可以用迭代器自减来使迭代器返回被erase掉的上一个迭代器位置(仍要接受erase返回值), 即
```
for(string::iterator it=str.begin(); it!=str.end(); it++){
  if( !isalpha(*it) ){
      it = str.erase(it);
      it--;
  }
}
```
  而对于关联性容器(map,set等) 使用erase只是使得被删元素的迭代器失效, 而且erase函数返回void, 因此需要用erase(iter++)的方式来删除迭代器.
  注: list容器两种方式都可以正常工作
unique() 的返回值为指向处理完的容器的超尾元素( 即end() )的迭代器(若处理数组则为指向最后一个元素的下一个元素的指针), 因此可以用形如 unique(arr, arr+n) - arr 的表达式获得处理完的数组的大小
实际上unique不会把元素erase掉, 只是遇到重复的元素就把后面的元素往前移
想要用Unique删除重复元素的标准用法:
```
  // 用erase + unique方法
  sort (Nodes.begin ( ), Nodes.end ( ));
  Nodes.erase (unique (Nodes.begin ( ), Nodes.end ( )), Nodes.end ( ));
  // 用s的构造函数 + vector.assign()方法
  set<int> s( vec.begin(), vec.end() );
  vec.assign( s.begin(), s.end() );
```
类似地, lower_bound(arr, arr+n, targ)返回值也是指向目标元素的地址或迭代器

STL Allocator:

  1) alloc: 默认的分配器, 线程安全, 效率通常比较高
  2) pthread_alloc : 首先要知道pthread指的是POSIX线程, 即线程的POSIX标准, 定义了创建和操作线程的一套API
  同样是一个线程安全的分配器, 并且对于不同的线程使用不同的内存池, 使用前提是所在系统提供了pthreads
  通常比alloc要快, 尤其是在多处理器的系统中. 然而该分配器可能会引起资源碎片化 : 因为在一个线程中deallocated(即free掉的)内存是无法被其他线程来使用的.
  3) single_client_alloc : 快速但不保证线程安全的分配器, 因此只适用于单线程的程序中, 可能比alloc更快

malloc_alloc : 该分配器是用标准库的malloc函数来分配内存的, 保证线程安全但通常比较慢, 主要用于调试时

模板

template<typename T, int n>
其中T为类型参数, n称为非类型参数
非类型模板参数(类似于模板类的静态常量)规定的类型只能传入常量, 允许的类型包括
- 整型和枚举类型
- 对象或函数的指针
- 对象或函数的左值引用
- 成员指针
- nullptr_t
  因此不能是某个类类型, 即便是string类型也不能作为非类型模板参数的类型, 即
```
<string str>
void func(){}
```
  是无法通过编译的
在代码中包含函数模板本身并不会生成函数定义, 它只是一个用于生成函数定义的方案; 编译器使用模板为特定类型生成函数定义时, 得到的是模板实例
显式具体化(explicit specialization): 也称显式特化, 在使用模板时, 对于某些特定的类型, 需要提供一个不同于一般类型的具体化函数定义, 称为显式具体化. 当编译器找到与函数调用匹配的具体化定义时, 将使用该定义, 而不再寻找模板。
显式具体化的原型和定义应以template <>开头, 并在后面通过名称来指出类型, 如以下定义:
```
  template <> swap<job>(job &, job &){};     // 显式具体化swap<T>模板函数
  // 也可以简写成template <> swap(job &, job &){};
```
注意：
1. 具体化优先于常规模板, 而非模板函数优先于具体化和常规模板
2. 具体化(特化, specialization)和实例化(instantiation)的区别
  “具体化”指的是存在具体类型的函数定义(非声明), “实例化”指的是函数被实际地调用了, 如显式实例化:
```
swap<job>(a,b); // Swap为模板函数
```
在一个模板函数(或模板类的方法定义)中, 形如vector<T>::iterator it;这样的声明无法通过编译,而vector<int>::iterator it;这样的声明却可以通过.
这是因为在vector未实例化之前是一个dependent scope而非一个类型, 即是一个需要depend on instantiation的scope(其实关键在于特化, 因为如果没有指明T是哪个具体的类型, 编译器就无法确定vector这个模板是否有被这种类型特化, 并在特化的scope中把iterator这个关键字重新定义为其他变量);
而vector是一个实例化了的具体的类型, 因此编译器无法确定在这个vector这个scope中iterator这个名称指的是一个成员变量还是类型(编译器会优先认为是变量), 却可以确定vector这个类型中的iterator是一个类型

智能指针

野指针(悬挂指针): 指向一个已删除的对象或未申请访问受限内存区域的指针。成因:
- 指针变量未初始化
- 指针释放后之后未置空
- 指针操作超过变量作用域
- realloc函数使用不当:
```
  #include<malloc.h>
  int main(){
      char *p, *q;
      p = (char*)malloc(10);
      q = p;
      p = (char*)realloc(q, 20);
      //…………………………
  }
```
  在这段程序中我们用q记录原来的内存地址p。这段程序可以编译通过，但在执行到realloc(q, 20)时，若原内存后面没有足够空间来将原有空间扩展成一个连续的新大小，那么realloc函数会从堆中重新找一块30字节大小的内存，并把原来（通过调用malloc函数得到的）内存空间中的内容复制到这块新内存中，此时数据发生了移动，那么q所指向（通过调用malloc函数得到的）的内存空间实际上已经放回到堆上了，这样就会产生q指针的指针悬挂
常规指针不能隐式地转换为智能指针, 因为智能指针的构造函数的声明是explicit的
错误的用法:
```
  string str("this is a test");
  auto_ptr<string> ptr(&str);
```
原因: 智能指针指向的内存是存放于堆区的(静态变量), 一般情况下应该用new来动态内存分配
但是这里的str显然是存放于栈区的, 该段代码结束后会自动释放, 而同样在栈区的智能指针析构时也会释放, 造成二次释放
(同样也不能使得两个智能指针指向同一个地址, 也会造成二次释放)
上述语句可以改用 auto_ptr<string> ptr(new string("this is a test"));来实现
shared_ptr和unique_ptr都解决了上述auto_ptr导致的多重所有权多次释放的问题
unique_ptr允许语句 unique_ptr p2 = unique_ptr( new string("this") );
即若unique_ptr是一个临时右值, 则允许两个unique_ptr临时指向同一个地址
但不允许将悬挂的unique_ptr赋值给其他的unique_ptr, 如
```
  unique_ptr p1(new string("this"));    // 创建了一个悬挂的unique_ptr
  unique_ptr p2 = p1;
```
这是无法通过编译的
实际上unique_ptr禁止一切按值传递操作, 要想转移所有权, 必须通过std::move()或unique_ptr::release(), reset()等其他函数
unique_ptr比auto_ptr还有一个优点, 可以与new []一起使用, 因为auto_ptr只有delete一个版本而没有delete [], 而unique_ptr具有两个版本, 如可以使用
unique_ptr pda(new double(5));
智能指针的选择:
如果程序要使用多个指针同时指向一个对象, 则用shared_ptr, 否则用unique_ptr

STL string类的COW(copy-on-write)特性:

  string str1 = "hello world"; 
  string str2 = str1; 
  printf ("Sharing the memory:\n"); 
  printf ("\tstr1's address: %x\n", str1.c_str() ); 
  printf ("\tstr2's address: %x\n", str2.c_str() ); 
  str1[1]='q'; 
  str2[1]='w'; 
  printf ("After Copy-On-Write:\n"); 
  printf ("\tstr1's address: %x\n", str1.c_str() ); 
  printf ("\tstr2's address: %x\n", str2.c_str() );

输出:

  Sharing the memory: 
  str1's address: 343be9 
  str2's address: 343be9 
  After Copy-On-Write: 
  str1's address: 3407a9 
  str2's address: 343be9

实现原理 : 引用计数

Lambda表达式

Lambda的组成部分:
- Capture 子句（在 C++ 规范中也称为 lambda 引导。）
- 参数列表（可选）。（也称为 lambda 声明符)
- 可变规范（可选）。
- 异常规范（可选）。
- 尾随返回类型（可选）。
- “lambda 体”
常见的语言（如C#）会自动为Lambda捕获当前上下文的所有变量，但C++要求我们在Lambda的捕获子句里显式指定想要捕获的变量以及捕获的形式(按值和引用)，否则无法在函数体里使用这些变量。如果捕获子句里面什么都不写，编译器会认为我们不需要捕获任何变量
如果希望按引用传递捕获当前上下文的所有变量，可以把捕获子句写成[&]；如果你希望按值传递捕获当前上下文的所有变量，可以把捕获子句写成[=]。
如果希望把按引用传递设为默认的传递方式，同时指定个别变量按值传递，可以把捕获子句写成[&, a, b]
按值传递在声明Lambda的那一刻就已经确定变量的值了，无论之后外面怎么修改，里面只能访问到声明时传过来的版本；而按引用传递则刚好相反

只有两种情况可以省略lambda表达式的返回值:

  1. 无返回值
  2. 函数体只包含一条返回语句

用lambda实现递归函数时, 需要把定义和声明语句分开写, 并在capture子句中捕获该变量:

  std::function< void(std::vector<T> &, int, int) > quickSort;
  quickSort =
      [&quickSort] (std::vector<T> & arr, int left, int right) {
      // ...
      quickSort(arr, left, li - 1);
      quickSort(arr, li + 1, right);
  };

应用场景示例: map 容器根据value值排序:

  vector< pair<char, int> > tmpVec(myMap.begin(), myMap.end());
  sort(tmpVec.begin(), tmpVec.end(), 
  [=](const pair<char, int> & p1, const pair<char, int> & p2){            // 传入匿名函数作为比较器
      return p1.second > p2.second; 
  } );

其他

四种新的类型转换操作符(称为标准转换运算符, 主要用于类指针的转换):
- static_cast
  (expression) :
  - 把expression转换为new_type类型, 但没有运行时类型检查来保证安全性(安全性指的是, 若转换一个指针后得到的新指针指向的内存宽度与原来的不同, 安全的类型转换会自动将新指针置为nullptr, 而不安全的类型转换就不会管这个, 从而对新指针指向的某些成员进行访问时就可能会造成访问越界 (比如把基类指针转换为子类指针时就可能出现这个问题) )
  - 也可以用于基本数据类型之间的转换, 此时相当于C风格的强制转换
  - static_cast不能转换掉expression的const、volitale、或者__unaligned属性。
- dynamic_cast
  (expression) :
  - 较常用, 与static_cast相对的一个操作符, 保证安全性, 若转换后有可能出现不安全的访问则将返回nullptr(因此也可以用于判断类之间是否可相互转换)
  - new_type和expression必须是有关联的, 如new_type是指针/引用, expression也必须为指针/引用..(否则无法通过编译)
    - reinterpret_cast(expression)
  - type-id必须是一个指针、引用、算术类型、函数指针或者成员指针。
  - 可以把一个指针转换成一个整数(即地址值)，也可以把一个整数转换成一个指针（先把一个指针转换成一个整数，再把该整数转换成原类型的指针，还可以得到原先的指针值）。
    - const_cast(expression)
  - 该运算符用来修改类型的const或volatile属性。除了const 或volatile修饰之外， type_id和expression的类型是一样的。
左值引用, 右值引用
概念理解:l-value可以理解为location-value, 在内存中拥有固定地址的东西, 包括所有类型的变量或变量表达式(如 i = 0 这个表达式)
右值可以理解为readonly-value 即除了左值以外的, 一个临时的值, 包括所有字面量(常量及常量字符串)和常量表达式(如1+2), 以及临时对象:如用 myClass() 产生的临时对象