【Boolan】第六周笔记

1.C++标准库和STL

C++标准库以header files形式呈现：
（1）C++标准库的header files不带副档名（.h），例如#include <vector>
（2）新式C header files 不带副档名.h，例如#include<cstdio>
（3）旧式C header files （带有副档名.h）仍然可用，例如#include <stdio.h>
（4）新式headers内的组件封装于namespace “std” 
          using namespace std；或者以 using std::cout;的形式
（5）旧式headers 内的组件不封装于namespace "std"
         在标准库中，标准模板库STL（Standard Template Library），占据了标准库70%，80%以上的内容。
         STL的核心思想是泛型编程（Generic Programming）。

重要资源：
网站：
*   http://en.cppreference.com/w/
*   http://www.cplusplus.com/
*   https://gcc.gnu.org/

书籍：
*   The C++ standard Library second edition；
*   STL 源码剖析

2.STL 六大部件

image.png

提到算法容器会涉及到复杂度的问题，也就是Big-oh问题：

image.png

3.容器的相关知识
3.1容器的结构与分类
容器按在内存中的存储结构分为三种：顺序容器（Sequence Container）、关联容器（Associative Container）、和无序容器（Unordered Container）。其中的无序容器是C++ 11提出的，实际上无序容器也属于关联容器，使用哈希表构成。

image.png

3.2顺序容器
顺序容器：它将单一类型元素聚集起来成为容器，然后根据位置来存储和访问这些元素。
标准库提供了一下几种顺序容器：array、vector、list、forward_list、slist、deque、stack和queue，他们的差别在于访问元素访问元素的方式，以及添加或删除元素相关操作的运行代价。array是C++11的新内容，功能比内置数组更加强大，可以以对象为单位存储数据，vector支持快速随机访问，list支持快速插入/删除，deque是一个双端队列，queue和stack在STL中都是基于deque来实现。

vector:可变大小数组；支持快速随机访问；在尾部之外的位置插入或删除元素可能很慢； 
deque:双端队列；支持快速随机访问；在头尾位置插入/删除速度很快；
list:双向链表；只支持双向顺序访问；在list中任何位置进行插入/删除操作速度都很快；
forward_list:单向链表；只支持单向顺序访问；在链表任何位置进行插入/删除操作速度都很快；
array:固定大小数组；支持快速随机访问；不能添加或删除元素；
string:与vector相似的容器，但专门用于保存字符；随机访问快；在尾部插入/删除速度快；

3.2.1顺序容器的常用操作

容器定义的操作非常少，只定义了构造函数、添加或删除元素的操作、设置容器长度的操作以及返回指向特殊元素的迭代器的操作。其他一些有用的操作，如排序、查找，则不是由容器类型定义，而是由标准算法定义。

（1）begin和end成员

begin 和 end 操作产生指向容器内第一个元素和最后一个元素的下一位置的迭代器，这两个迭代器通常用于标记包含容器中所有元素的迭代器范围。

image

（2）添加元素

image

（3）大小操作

image

（4）访问元素

image

（5）删除元素

image

（6）swap交换操作

swap 操作实现交换两个容器内所有元素的功能。要交换的操作数必须是相同类型的容器，而且所存储的元素类型也必须相同。调用了 swap 函数后，右操作数原来存储的元素被存放在左操作数中，反之亦然。

该操作不会删除或插入任何元素，而且保证在常量时间内实现交换。由于容器内没有移动任何元素，因此迭代器不会失效。

根据课程举几个使用例子：

image image image image

3.3关联容器

在STL中关联容器使用红黑树来实现，因为不是顺序结构，因而不能使用上面提到的push和pop函数，使用insert和erase函数来实现元素的插入删除操作。

关联容器支持通过键来高效地查找和读取元素，两个基本的关联容器类型是map和set。map的元素以键-值（key-value）对的形式组织：键用于元素在map中的索引，而值则表示所存储和读取的数据。set仅包含一个键，并有效地支持关于某个键是否存在的查询。map可理解为字典，set可理解为一类元素的集合。

关联容器和顺序容器的本质差别在于：关联容器通过键（key）存储和读取元素，而顺序容器则通过元素在容器中的位置顺序存储和访问元素。

et 和 map 类型的对象所包含的元素都具有不同的键，不允许为同一个键添加第二个元素。如果一个键必须对应多个实例，则需使用 multimap 或 multi set，这两种类型允许多个元素拥有相同的键。

根据课程举几个例子：

image image

3.4无序容器

严格意义上讲，无序容器也属于关联容器。

根据课程举两个例子：

image image image