今天读文献读到一个计算出租车距离计算，

Driving distances are approximated by multiplying the Euclidean distance between origin and destination by a factor of α = 1.4, to reflect the “taxicab geometry” of typical driving grids; since the greatest possible upscale is α = √2 —which would reflect the diagonal of a square with available roads only on a right-angled grid pattern—the proportionality factor of 1.4 represents an upper bound.

曼哈顿距离 (Manhattan Distance) 也叫做计程车几何(Taxicab geometry)，也就是欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。下图A到B直线就是欧式距离，紫色线就是曼哈顿距离。如下图所示：

但是实际道路可能并不如上图都是直角转弯，也可能有弯曲的地方，那样子路线长度就比曼哈顿距离短，所以存在上文引用中所写的：the proportionality factor of 1.4 represents an upper bound.

Reference

Kang N, Feinberg F M, Papalambros P Y. Autonomous electric vehicle sharing system design[J]. Journal of Mechanical Design, 2017, 139(1).

[toc]

Course Introduction

Welcome to the Course - 3 min

1. What is motion planning?

the motion planning problem is the task of generating the path and velocities required to get the autonomous car from point A to point B.

2. decompose the motion planning into smaller sub-problems

Module 1: The Planning Problem

Lesson 1: Driving Missions, Scenarios, and Behaviour

关键概念

• Explain what the autonomous driving high-level mission entails.
  navigate from current position to a destination.
• Recall the set of important basic driving scenarios.
  road structure (turns, lane changes) , obstacles
• Develop a set of driving behaviours to handle most basic driving scenarios.
  Speed Tracking, Decelerate to Stop, Stay Stopped, Yield, Emergency Stop
• Recognize important constraints for autonomous driving motion planning.
• Explain the functionality of each step in a hierarchical motion planner.
• List some variants of each step of a hierarchical motion planner.

• The motion planning problem is the task of navigating the ego vehicle to its destination in a safe and comfortable manner while following the rules of the road.

Autonomous Driving Mission：目标找出最高效的路

为了更高效，抽象了许多底层的变量，但是这些底层的很重要定义了不同的驾驶场景

Road Structure Scenario:

• 保持车道lane maintenance，目标偏离中心线最小 但要保证速度
• 变道lane change
• 转弯
• 掉头U-turn

Obstacle Scenarios

• static
• dynamic:Different dynamic obstacles in the scenario have different characteristics and behaviours

Behavior

• Speed Tracking
• Decelerate to Stop
• Stay Stopped
• Yield
• Emergency Stop
  (Not an exhaustive list)

Challenges

• 许多违反交规的行为难以预测

Hierarchical Planning Introduction

• motion planning是一个复杂问题，将其分层优化，如下图
  
  每一个子优化问题有自己的目标和限制

Lesson 2: Motion Planning Constraint

Bicycle Model

• 路径上的曲率要注意最大曲率限制

• 是一个non-holonomic约束（不仅取决于当前状态，也取决于如何到达该状态）

  通俗地讲, holonomic constraint是configuration space上的约束,它告诉你哪里不能走, nonholonomic constraint是速度(广义坐标的微分)上的约束,它告诉你哪些方向不能走,但是你依然能想去哪里去哪里。

• 曲率计算：
  

Vehicle Dynamics

• 横向和纵向的加速限制（摩擦力椭圆）
• 在非紧急情况下，更有用的限制是乘客对加速度的容忍度（下图矩形所示）
  
  因此速度受限于加速度和曲率$v^{2}\leq \frac{a}{\kappa }$

Static obstacles

• 使用线束或一系列近似车身的圆去做碰撞检测

Dynamic Obstacles

• 涉及到障碍物行为的预测。如果预测所有，就太过保守无意义，做aggressive和conservative之前的tradeoff——热点研究

Rules of the road and regulatory elements

• 车道线和一些标识

• time gap

  the amount of time that it would take for the ego vehicle to reach the leading vehicles current position while traveling at the ego vehicle’s current speed

Lesson 3: Objective Functions for Autonomous Driving

• 曲率

$\int_{0}^{s_{f}}\|\kappa(s)\|^{2} d s$

既要保持速度，又让乘客舒适

Lesson 4: Hierarchical Motion Planning

分层以后每一层计算会快，但同时每一层会损失其他层的信息。和不分层比存在一个trade off

Mission Planner

地图级别的导航，最短路Dijkstra，A*

Behavioural Planner

• 如何考虑周围并产生行为

• 有限状态机，无记忆——转换只和输入和当前状态有关

• Rule-based

  • 多个规则同时符合的话，高优先级的规则先应用

• 基于机器学习

Local Planner

产生避免碰撞的路线和舒适的velocity profile，分两部分

• 路线方面：

1. sampling based planner
   
2. Variation Planner 将路径和速度产生合并在一起 chomp Algorithm
   
3. lattice planner
   

• 速度产生：

Lesson 3中对速度的一些优化作为目标限制，凸优化

• 小鹏汽车与Tesla不同的一点特别关注对驾驶员行为的检测，如果天气不好路况复杂，对驾驶员的检测会更加严格
• 行为和轨迹的预测，边缘的场景感知不好至少要自己知道
• 技能：模型训练 框架pytorch等；c++编程；加速框架，英伟达、高通的加速框架
• 前融合、后融合
• 数据回传靠某种情况处罚
• 端到端自动驾驶，从坐入车到下车，车库里、城区上阶段打通，无缝的体验
• 融合算法提高精度为主

我们在用动态内存分配时，经常是用new来定义一块内存空间，比如说 int* p = new int(1)；这时会在堆上分配一块内存，当作int类型使用，内存中存储的值为1并将内存地址赋值给在栈中的int*类型的p。（注意：p只是一个变量，就像是int a=1中的a一样，不过a是整形变量，而p是指针变量）当我们不用p指针时，往往需要用delete p将其释放，我们需要注意的是释放一个指针p（delete p;）实际意思是删除了p所指的目标（变量或对象），释放了它所占的堆空间，而不是删除p本身（指针p本身并没有撤销，它自己仍然存在，该指针所占内存空间并未释放，指针p的真正释放是随着函数调用的结束而消失），释放堆空间后，p成了"空指针"。如果我们在delete p后没有进行指针p的制空（p=NULL)的话，其实指针p这时会成为野指针，为了使用的安全，我们一般在delete p之后还会加上p=NULL这一语句。

tinyhttpd涉及到一些准备知识，可以参考这篇博文

Tinyhttpd简介

Tinyhttpd 是J. David Blackstone在1999年写的一个不到 500 行的超轻量型 Http Server，用来学习非常不错，可以帮助我们真正理解服务器程序的本质

Tinyhttpd下载

可以直接下载github上的代码（
https://github.com/TronYY/Tinyhttpd），下载后解压在自己的目录下。

安装perl

测试时需要本机安装perl(mac和Ubuntu默认已装)可以在终端输入which perl判断perl是否已经安装，如果提示类似

1

/usr/bin/perl

则说明已安装上。如果没有则要自行安装。

安装perl-cgi

• 执行perl -MCPAN -e shell
• 执行install CGI.pm

可以在终端里执行perl -MCGI -e 'print "CGI.pm version $CGI::VERSION\n";' 这条命令来验证是否安装成功

如果出现　CGI.pm version 4.26　这种显示CGI版本的文本，说明安装成功。

注释和修改

• 打开下载的Tinyhttpd中的httpd.c做如下修改：

1. Comment out the #include <pthread.h> line.
2. Comment out the line that defines the variable newthread.
3. Comment out the two lines that run pthread_create().
4. Uncomment the line that runs accept_request().

• 打开同一个目录中的Makefile文件，去除掉"-lsocket"
• 在终端输入which perl记录下perl 的路径如/usr/bin/perl
  输入打开Tinyhttpd的子文件夹htdocs，将其中的check.cgi和color.cgi的首行都改为

  1	#!/usr/bin/perl -Tw

权限设置

在服务器运行以后，我遇到一个问题就是浏览器一直无输出页面，找了很久，发现是这个页面对应的文件index.html的读写权限问题，在Tinyhttpd的子文件夹htdocs下用以下命令修改文件权 限

1

sudo chmod 600 index.html

make和运行

在Tinyhttpd目录下打开终端输入make进行编译（如果提make: Nothing to be done for all’.则输入命令make clean后再输入make即可）

在终端在输入./httpd

1

httpd running on port 4000

随机端口号显示为4000，打开浏览器，输入http://127.0.0.1:4000即可出现如下网页，说明运行成功

[toc]

第2章 变量与基本类型

2.2.1 变量定义

• 如果是内置类型的变量未被显示初始化，它的值由定义的位置决定:定义于任何函数体之外的变量被初始化为0;定义于函数体内部的内置类型变量将不被初始化
• 不提供显式的值也能初始化——零初始化
  • 全局变量p
  • 静态变量
  • 类内静态变量

1
2
3
4
5

{//在一个块中
    int i;//默认初始化，不可直接使用
    int j=0;//值初始化
    j=1;//赋值
}

• 绝大多数类都支持无须显示初始化而定义对象，如std::string empty;//empty非显示地初始化为一个空串
• 默认构造函数：A default constructor is a constructor which can be called with no argument

声明： 在环境/上下文中指定一个变量的名字。也就是说，声明仅仅是让编译器知道，而没有实际分配空间。
初始化：给一个声明后尚未初始化的变量一个有意义的初始值。
赋值 ： 销毁一个变量原来的值，并赋予一个新值。相当于改变了一个变量的状态

• 值初始化： 值初始化是定义对象时，要求初始化，但没有给出初始值的行为。
  int i{};
  new int();
  new int{}; //C++11
  （1）在数组初始化的过程中，如果提供的初始值数量少于数组的大小，剩下的元素会进行值初始化；
  （2）静态static变量、定义在块作用域外的全局变量，如果没有显式的初始值，将执行值初始化；
  （3）当我们通过书写形如T()的表达式（例如 int()）显式地请求值初始化时;
  默认初始化：默认初始化是定义对象时，没有使用初始化器，也即没有做任何初始化说明时的行为。如：
  int i;
  vector v;
  new T;
  （1）当我们在块作用域内（类内也属于块作用域内）不使用任何初始值定义一个非静态变量时；
  （2）当一个类本身含有类类型成员且使用合成的默认构造函数时；
  （3）当类类型的成员没有在构造函数初始值列表中显式地初始化时;

• 默认构造函数是编译器自动合成的，默认初始化之前先进行零初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
 
struct foo
{
 foo() = default;
 int a;
};
 
struct bar
{
 bar();
 int b;
};
 
bar::bar() = default;
 
int main()
{
 foo a{};
 bar b{};
 
 std::cout << a.a << '\t' << b.b;
}

答案是a.a是0，b.b是不确定，foo的构造函数在起初声明时是要求默认合成，而不是我们自定义提供的，因此它属于编译器合成的默认构造函数。而bar的构造函数则不同，它是在定义时被要求合成，因此它属于我们用户自定义的默认构造函数。

• 函数内的初始化，初始化数组 和 指针

1
2
3
4
5
6
7
8

bool flag[12];
memset(flag, true, sizeof(flag));	
/**
当初始化一个字节单位的数组时，可以用memset把每个数组单元初始化成任何你想要的值 ，
但是不是一个字节单位时一般只能0 或 -1
*/
bool *flag=new bool[12];
memset(flag, false, 12*sizeof(bool));

2.2.2 变量声明和定义的关系

1
2

extern int i;//声明i，没有定义i
int j;//声明且定义了j

• 变量能且只能被定义一次，但是可以被多次声明。因此，变量的定义只能出现在一个文件中，其他用到该变量的文件必须对其进行声明

2.3 复合类型

2.3.2 指针

• 实现了对其他对象的间接引用。本身就是一个对象，允许赋值和拷贝，生命周期内可以先后指向多个不同的对象。其二 无须在定义时赋值
• 空指针 nullptr/0
• 建议初始化所有的指针。尽量等先定义了对象再定义指向它的指针
• void*可以用于存放任意对象的地址。能做的事情比较有限——拿他与别的指针比较、作为函数的输入输出、赋值给另外的void *指针。不能直接操作void * 所指的对象(包括访问)
• 指针和引用的主要区别：

  definition:
  the pointer is “points to” any other type.
  the reference is “another name” of an object.
  key difference:
  (1) a reference is another name of an already existing object. a pointer is an object in its own right.
  (2) Once initialized, a reference remains bound to its initial object. There is no way to rebind a reference to refer to a different object. a pointer can be assigned and copied.
  (3)a reference always get the object to which the reference was initially bound. a single pointer can point to several different objects over its lifetime.
  (4)a reference must be initialized. a pointer need not be initialized at the time it is defined.

-给定一个指针，无法知道是否指向了一个合法的对象

2.3.3 理解复合类型的声明

• 指向指针的引用

1
2
3
4

int *p;  
int *&r = p;//r 是一个对指针p的引用。要理解r的类型是什么，最简单的方法时从右往左阅读r 的含义。离变量名最近的符号对变量的类型有最直接的影响  
r = &i;//令p指向i
*r = 0;//解引用r得到i，这句将i值改为0

2.4 const限定符

• const对象必须初始化
• const对象仅在文件内有效：编译器在编译过程中把用到该变量的地方都替换成对应的值，因此需要在编译阶段 用到了const的文件都必须能访问到它的初始值，即 需要该文件中有对const对象的定义。默认下，const对象被设定为仅在文件内有效。想在多个文件之间共享const对象，必须在变量的定义之前添加extern对象

2.4.1 const的引用

• 不能让一个非常量引用指向一个常量对象。常量引用可以绑定非常量对象，但是不允许通过该引用修改原对象——指向常量对象的也必须是常量引用

1
2
3
4
5
6

const int ci = 1024;
int &r2 = ci;//错误

int i = 42;
const int &r3 = i;
r3 = 0;//错误

• 引用的类型必须与其所引用对象的类型一致。但是两个例外:
  (1) 初始化常量引用时，允许用任意表达式作为初始值，只要该表达式结果能转换成引用的类型； (常量引用是对const的引用）

1
2
3
4

int i = 42;
const int &r2 = 42;
const int &r3 = r1 * 2;
int &r4 = r1 * 2;//错误 r4非常量引用

1
2

double dval = 3.14;
const int &ri = dval;

等价于

1
2
3

double dval = 3.14;
const int temp = dval;//临时量
const int &ri = temp;

(2) 如果ri不是常量引用，就允许对ri赋值，会改变ri所引用的对象的值——临时量，但是闲着没事干改临时量干什么，改了temp也不会对应改到dval，所以ri不是常量引用的话就会出错了

2.4.2 指针和const

-指向常量的指针

1

const double *cprt = π//cptr是指向双精度常量的指针，不能通过该指针修改所指对象的值，但是cprt可以指向其他的双精度

const放在最前边表示指向的是一个const对象

• const指针
  必须初始化

1
2
3
4
5

int errNumb = 0;
int *const curErr = &errNumb; //const前加*表示指针是一个常量，存的地址不能变了

const double pi = 3.1415;
const double *const pip = π//第一个const表示指向的对象是一个常量，不能通过改指针修改所指对象的值；第二个const表示该指针是个const指针，不能指向其他对象

2.4.3 顶层const

• const expression是指值不会改变并且在编译过程中就能得到计算结果的表达式
  如 int s = 27与const int sz =get_size()都不是const expression，前者值不是 const 后者值要到运行时才能知道
  -顶层const表示本身是个常量；底层const表示所指的是个常量（写在最前面的const）

2.4.4 constexpr

• constexpr 初始值必须是存储于某个固定地址中的对象(函数体外的变量 或函数体内局部静态变量)

2.5 处理类型

2.5.1 类型别名

1
2
3

typedef char *pstring;//pstring的基本数据类型是指针
const pstring cstr = 0;//cstr 是指向char的常量指针
const char *cstr = 0;//声明了一个指向const char的指针  所以不能错误地长是把类型别名替换成它本来的样子

2.5.2 auto

• auto定义的变量必须有初始值
• auto会忽略掉顶层const，底层const会被保留下来

2.5.3 decltype类型指示符

1
2

const int ci = 0;
decltype(ci) x = 0; // x的类型是const int

1
2

int i = 42, *p = &i;
decltype(*p) 结果是引用类型。解引用指针可以得到指针所指的对象，而且还能给这个对象赋值，因此decltype(*p) 结果是int& 并非int

• decltype((variable))的结果永远是引用，decltype(variable)只有当variable本身就是一个引用时才是引用

2.6 自定义数据结构

• #ifdef 当且仅当变量已经定义时为真， #ifndef当且仅当变量未定义时为真。一旦检查结果为真，则执行后续操作直到遇到#endif为止

第3章 字符串、向量和数组

3.1 命名空间的using声明

• 头文件不应包含using声明

3.2 标准库类型string

• 读取string时，会自动忽略开头的空白（包括换行符制表符），并从第一个真正的字符开始读起，直到遇到下一处空白
• C++输出十六进制是cout〈〈hex〈〈 a；而八进制是cout〈〈 ocx〈〈 a;二进制则没有默认的输出格式，需要自己写函数进行转换
• cin完，再getline 此时读完的还是只有第一行

3.2.2 string对象上的操作

• getline遇到换行符结束，读入的不含那个换行符
• size函数返回的是一个无符号整型数，比较得和无符号数比较
• 当吧string对象和字符字面值及字符串字面值混在一条语句中时，必须确保每个加法运算符两侧的运算对象至少一个string。注意字符串字面值与string是不同的类型
• string 到 int的 转换 stoi(44)
• 使用for语句改变字符串中的字符

1
2

for (auto &c : s)
    c = toupper(c);//对于s中每个字符使用引用，转换成大写

• str.size() str.size() str.append(8-str.size(),‘0’) string pp(kk.end() - kk.begin(), ‘0’); string pp(kk.end() - kk.begin(), ‘0’);
• 逆转 reverse()&reverse_copy()

1
2
3

#include <algorithm>
reverse(a,a+10);   
reverse_copy(a,a+10,b); //倒序放入b数组中

1
2
3
4
5
6
7
8
9

template <class BidirectionalIterator>
void reverse (BidirectionalIterator first, BidirectionalIterator last)
{
    while ((first!=last)&&(first!=--last))
    {
        std::iter_swap (first,last);
        ++first;
    }
}

3.3 标准库类型vector

3.3.1 定义和初始化vector对象

• vector 是模版而非类型
• 引用不能作为vector包含的元素，因为所包含的必须是对象
• 列表初始化（用花括号扩起来，里面填上0个或多个元素赋给对象）,花括号里的值必须和元素类型相同 vector v8{10, “hi”}不是列表初始化,编译器尝试用默认值初始化vector对象——v8有10个值为"hi"的元素。 vector v7{10} v7有10个默认初始化的元素
• map<char, int> mp; mp[c] = 5;
• list l; l.erase(迭代器)
• 如果vector对象的元素是内置类型，如int，则元素的初始值自动设为0；如果元素是某种类型，比如string，则元素由类默认初始化

3.3.2 向vector对象中添加元素

• v.push_back(i) 插到尾端

1
2

vector<int>::size_type;//vector对象的类型总是包含着元素的类型
vector::size_type;//错误

• 到中间一个数为止（总数是奇数，过了中间一个数为止；总数是偶数，到前半部分为止），<(size() + 1) / 2

3.4 迭代器介绍

• 所有的标准库容器对象都可以使用迭代器，但是其中少数才同时支持下标运算符。严格来说string对象不属于容器类型，但是string支持很多与容器类型类似的操作
• 使用容器养成使用迭代器和== !=的习惯
• 能进行算术运算的迭代器只有随即访问迭代器，要求容器元素存储在连续内存空间里，vector，string，deque的迭代器是有加减法的，但是map，set，multimap,multiset的迭代器是没有加减法的，list也不可以。map等的迭代器不支持加减操作，仅有++itr，–-itr这些操作来进行选择
• 不要在循环中判断不等于end()

3.4.1 使用迭代器

• auto e = v.end();//e表示v尾元素的下一位置
  v.begin() == v.end() 表示v为空，返回的都是尾后迭代器

1
2
3
4
5
6
7
8
9

//把string对象的第一个单词改写为大写形式
for (auto it = s.begin(); it != s.end() && !isspace(*it); ++it)
    *it = toupper(*it);// *it返回的是it所指元素的引用
    
for (auto &c : s)
    c = toupper(c);//对于s中每个字符使用引用，转换成大写
    
for (auto i : v) cout << i << " ";
//注意使用迭代器时用引用还是直接里面的对象。要修改则用引用&如② 或 解引用如①

• 迭代器类型

1
2
3
4
5

vector<int>::iterator it;
string::iterator it2;

vector<int>::const_iterator it3;//只能读
string::const_iterator it4;//只能读

• 为了便于得到const_iterator类型 auto it3 = v.cbegin(); cend()
• 检查it所指字符串是否为空 (*it).empty() 而不是 *it.empty()
• 箭头运算符 把解引用和成员访问两个操作结合在一起 it->men 同 (*it).mem
• 凡是使用了迭代器的循环体，都不要向迭代器所属的容器添加元素

3.4.2 迭代器运算

• vector与string迭代器支持的运算+n -n +=n -=n - > < >= <=, 其中- 得出的类型是difference_type 带符号整型数

3.5 数组

• 引用不能作为数组包含的元素，因为所包含的必须是对象
• 不能用数组为其他数组赋值 如a2 = a，数组首元素是个常量指针const char* ;错误 （但是Java里a2 = a可以的，是一种浅层复制，把数组的引用指向了a2，a2一变a也会变）
• 数组的维度必须是constexpr（指值不会改变并且在编译过程中就能得到计算结果的表达式）
• *与[]后者优先，理解数组声明最好从数组的名字开始按照由内向外的顺序阅读
  int *(&array)[10] = ptrs;//array 是一个含有10个int型指针的数组的 引用
• 不能直接把数组作为返回值 见剑指offer网 序列化二叉树

3.5.2 访问数组元素

• 数组下标类型size_t 无符号类型
• 遍历数组时，最好的方法也是使用for御语句

1

for (auto i : score)

3.5.3 指针和数组

1
2

int ia[] = {0, 1, 2};
auto ia2(ia);//ia是一个整型数组指向ia的第一个元素 实际上编译器中发生的是auto ia2(&ia[]);  当使用decltype关键字时，这个转换不会发生，ia2将是数组

• 指向数组ia首元素的指针 int *beg = begin(ia); 尾元素后一位置的指针 end(ia)
• 两个指针相减类型 ptrdiff_t类型

1
2
3

int ia[] = {0, 2, 4, 6, 8}
int *p = &ia[2];
int k = p[-2];//标准库类型如string 和vector限定下标必须是无符号类型，内置的下标运算则无此要求

• 数组元素是否相等要一个个比较，两个vector对象是否相等可以直接==比较
• 判断数组为空用nullptr，如果一位数组arr不为空，sizeof(arr)/sizeof(arr[0)就可以用来计算数组长度，但是如果arr是作为形参传入函数体，arr是一个指针，sizeof(arr) 是为8，不是数组总大小；同样地end(arr) - begin(arr) 当arr是传入参数时也不可以使用可以用nullptr、sizeof(arr) == 0来判断

3.5.5 与旧代码的接口

• 不能用string对象初始化char*
• 不允许用vector初始化数组，不允许数组初始化数组，但是允许数组初始化vector，如

1
2

vector<int> ivec(begin(int_arr), end(int_arr));
vector<int> ivec(int_arr + 1, int_arr + 4);//三个元素，分别为int_arr[1]、[2]、[3];

• 尽量使用vector和迭代器，避免使用内置数组和指针，尽量使用string避免使用c风格的基于数组的字符串

3.6 多维数组

• 对每个元素赋值

1
2
3
4
5
6
7
8
9
10

/**
row要写成引用，row的类型是含有4个整数的数组的引用。
如果row不写成引用类型，编译无法通过——外层要遍历一个个大小为4的数组，row不是引用类型的话，编译器初始化row时会自动将这些数组元素转换成指向该数组首元素的指针.
这样row的类型就是int*  内层循环就不合理了
*/
for (auto &row : ia) 
    for (auto &col : row) {
        col = cnt;
        cnt++;
    }

• 使用for循环语句处理多维数组，除了最内层的循环外，其他所有循环的控制变量都应该是引用类型

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
26
27
28
29

#include <iostream>
using std::cout; using std::endl;

int main()
{
    int arr[3][4] = 
    { 
        { 0, 1, 2, 3 },
        { 4, 5, 6, 7 },
        { 8, 9, 10, 11 }
    };

    // range for
    for (const int(&row)[4] : arr)
        for (int col : row) cout << col << " ";
    cout << endl;

    // for loop
    for (size_t i = 0; i != 3; ++i)
        for (size_t j = 0; j != 4; ++j) cout << arr[i][j] << " ";
    cout << endl;

    // using pointers.
    for (int(*row)[4] = arr; row != arr + 3; ++row)
        for (int *col = *row; col != *row + 4; ++col) cout << *col << " ";
    cout << endl;

    return 0;
}

第4章 表达式

4.1 基础

4.1.1 基本概念

• 当一个对象被当做右值的时候，用的是对象的值（内容），当对象被当做左值的时候，用的是对象的身份（在内存中的位置）
• 取地址符得到的结果是右值。解引用、下标运算符的结果是左值
• 表达式求值结果是左值（如解引用），decltype以后得到一个引用类型。取地址运算符生成右值，所以decltype(&p) 结果是int*，（p是 int*类别）
• 优先级 去掉一个最高的，去掉一个最低的，剩下的是一、二、三、赋值。双目运算符中，顺序为算术、关系和逻辑，移位和逻辑位插入其中。

4.5 递增和递减运算符

• 递增后置版本，先将变量的值+1，再返回变量初始值的副本

4.9 sizeof运算符

• sizeof并不实际计算其运算对象的值。对解引用指针执行sizeof运算的带指针所指对象所占空间的大小，指针不需要有效。sizeof（数组）是计算整个数组所占空间的大小，不会把数组当成指针来处理

第6章 函数

6.1 函数基础

6.1.1 局部对象

• 自动对象：只存在于块执行期间的对象称为自动对象，比如里面的a，还有我们的形参，都是自动对象。
  局部静态对象在程序执行路径第一次经过对象定义语句时初始化，知道程序终止才被销毁（只被定义初始化一次，可以一直用它）static int cnt = 0；如果静态变量没有显式的初始值，它将执行默认初始化。

6.1.2 函数声明

• 函数三要素（返回类型，函数名，形参类型）描述了函数接口
  //也就是说明了调用该函数所需的全部信息
• 定义函数的源文件还要把含有函数声明的头文件包含进来

6.2 参数传递

6.2.1 传值参数

• 指针形参，拷贝的是指针的值

6.2.2 传引用参数

• 一个函数只能返回一个值，然而有时候函数需要同时返回多个值，考虑引用参数

6.2.3 const形参和实参

• 顶层const，即对象本身是常量，int 可以直接赋值给const int（只是不能通过后者修改；反过来不行）我们在拷贝时会忽略顶层const。void f(const int i){}和void f(int i){}属于重复定义
  注意与下面第二章的区别“不能让一个非常量引用指向一个常量对象。常量引用可以绑定非常量对象，但是不允许通过该引用修改原对象——指向常量对象的也必须是常量引用”

• 可以用非常量初始化一个底层const对象（所指向的是个常量），反过来不行

• 尽量使用常量引用

只要不需要改变形参的值，都尽量用常量，理由有两点：
- 该用常量而不用常量，会给函数的调用者一种误导，即函数可以改变它的实参的值
- 使用引用而非常量引用会限制函数所能接受的实参类型。刚刚就学过，我们不能把const给非const的，但可以把非const的给const。

6.2.4 数组形参

数组不允许被拷贝：所以无法使用值传递
使用数组名时会将其转换为指针

• 只会检查传入的参数是不是const int*类型

1
2
3
4
5
6

//以下三个函数声明等价（还记得函数声明吧）
void f(const int*);
void f(const int[]); //数组名转换为数组首元素指针
void f(const int[5]); //我们期望它有五个元素，其实都行

1
2

int *m[10];//10个指针构成的数组
int （*matrix)[10];//指向含有10个整数的数组的指针

• void print(const int ia[10]) 与const int*一样，不会去管里面几个。如果要传10个，应写成const int (&a)[10]

6.2.5 main:处理命令行选项

• 省略符形参

1
2
3
4
5
6
7
8

void f(int a, ...){}
int main()
{
 int a = 5;
 f(a,6);
 f(a, "a"); //懂了吧~
 return 0;
}

6.3.3 返回数组指针

• 因为数组不能被拷贝，所以函数不能返回数组，只能返回数组的指针或者引用。

int (*f())[10]; //函数返回的是指针，指向一个大小为10的int数组

• 因为这样看起来比较麻烦，我们可以用之前学过的类型别名：

1
2

using arr = int[10];  
arr* f(); //这样的声明就比较简洁了

• 除了使用类型别名外，C++还有一种方法：尾置返回类型，顾名思义，就是把返回类型放后面：

1

auto f() -> int(*)[10]

别忘了我们还有一个神器，decltype：

1
2
3

int a[] = {1,2,3};
decltype(a) *arrp(){} //返回类型是指针，且指向的类型与a一致
//使用它的前提是我们知道返回的指针指向什么类型的数组。

6.4 函数重载

• 重载和const形参
  一句话概括：顶层const（本身为常量）重载不行的，会被忽略，什么意思呢，看代码：

1
2

int f(int);
int f(const int); //重复声明，顶层const会被忽略

底层const重载是可行的：

1
2
3
4
5

int f(int&);
int f(const int&) //重载，常量引用都是底层const

int f(int *a);
int f(const int *a); //重载，指向常量的指针

6.4.1 重载与作用域

• 如果在内层作用域中声明名字，它将隐藏外层作用域中的同名实体。在不同的作用域中无法重载函数名
• 一旦某个形参被赋予了默认值，它后面的所有形参都必须有默认值。尽量让不怎么使用默认值的形参出现在前面，而让那些经常使用默认值的形参出现在后面。

第7章 类

7.1 定义抽象数据类型

• 一个函数 AcGePoint3dstartPoint() const; const放在后面跟前面有区别么
  ==>
  准确的说const是修饰this指向的对象的
  譬如，我们定义了
  classA{
  public:
  f(int);
  };
  这里f函数其实有两个参数，第一个是A*const this, 另一个才是int类型的参数
  如果我们不想f函数改变参数的值，可以把函数原型改为f(constint),但如果我们不允许f改变this指向的对象呢？因为this是隐含参数，const没法直接修饰它，就加在函数的后面了，表示this的类型是constA *constthis。
  const修饰*this是本质 该成员函数成为常量成员函数， this 指向对象，对象是常量对象
• 加了const 表明在函数体内，不能修改对象的数据成员，且只能调用常量成员函数
• 常量对象，以及常量对象的引用或者指针都只能调用常量成员函数
• 调用total.isbn() 编译器实际上将该调用重写成了Sales_data::isbn(&total)
• void fun(int a，int b) const{}
  void const fun(int a,int b){}，const都是在修饰this，与const所写的位置无关。

7.1.3 定义类相关的非成员函数

• IO类型属于不能被拷贝的类型，所以IO类型作为参数时，需要用引用
• 拷贝类的对象实际上拷贝的是对象的数据成员
• 非成员函数（个人觉得就是如果定义写在类外，定义时有没有加所属的类名）。另外，如果是非成员函数，其定义一般与声明写在一个头文件中

1
2
3
4
5
6
7

class A{
public:
    void f1(){}; // 这个就是成员函数。
    void f2(); // 这个也是成员函数声明，其实现在类的外部。
};
void A::f2(){} // 这个是成员函数的实现。
void f3(){}; // 这个就是非成员函数，它不属于A，也不属于任何一起其他的类。

1
2
3
4
5
6
7
8

istream &read(istream &is, Sales_data &item)
{
    double price = 0;
    is >> item.bookNo >> item.units_sold >> price;
    item.revenue = price * item.units_sold;
    return is;
}
//print自己写

7.1.4 构造函数

• 构造函数不能被声明成const（常量成员函数）
• 编译器只有在我们没有定义构造函数时，才会生成默认构造函数，也就是说，如果我们定义了一个构造函数，且它不是默认构造函数，那我们就没有默认构造函数可以使用了。
• 
• 最好把默认构造函数加上
• Sales_data() = default;= //default的意思是，我们要求编译器生成构造函数。= default在类内部是内联，在类外部不是内联。
• 构造函数初始值列表。当某个数据成员被构造函数初始值列表忽略时，它将以与合成默认构造函数相同的方式隐式初始化

1
2
3

Sales_data(const string &s, unsigned n, double p) :
            (bookNo(s), units_sold(n), revenue(p*n)) {};

7.2 访问控制与封装

• struct和class的唯一的区别是默认访问权限不太一样。
  struct：定义在第一个访问说明符之前的成员是public
  class：定义在第一个访问说明符之前的成员是private

7.2.1 友元

• 类可以允许其他类或者函数访问它的非公有成员，方法是令其他类或者函数成为它的友元（与成员函数权利一样） 加friend

1
2
3
4

struct Sales_data
{
    friend istream &read(istream&, Sales_data&);
}

• 友元声明只能卸载类定义的内部，具体位置不限。友元不受它所在区域访问控制级别的约束。
• 友元的声明仅仅指定了访问的权限，而非一个通常意义上的函数声明。所以需要在友元声明之外再专门对函数进行一次声明

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
26
27
28

struct Sales_data
{
    friend istream &read(istream&, Sales_data&);

private:
    //数据成员
    string bookNo; //书号
    unsigned units_sold = 0; //售出册数
    double revenue = 0; //总销售收入

public:
    //成员函数
    string isbn() const //返回书本isbn号，这里的const待会解释
    {
        return bookNo;
    }
    Sales_data& combine(const Sales_data&); //函数声明
    double avg_price() const; //返回售出书籍的均价，这里的const也待会解释
}
istream &read(istream&, Sales_data&) //声明在类外且无作用域符号，为非成员函数
{
    double price = 0;
    is >> item.bookNo >> item.units_sold >> price;
    item.revenue = price * item.units_sold;
    return is;
}

7.3 类的其他特性

7.3.1 类成员再探

• 定义在类内部的成员函数是自动inline的。最好只在类外部定义的地方说明inline，更好理解。inline函数放在头文件中
• 可变数据成员加mutable， 永远不是const，即使他是const对象的成员，一个宠上天成员函数也可以改变一个成员的值

1
2
3
4
5
6
7

class Window_mgr
{
private:
    vector<Screen> screens{ Screen(24, 80, ' ') }
}
//我们用了列表初始化去初始screens这个Window_mgr类的类内成员变量，
//在列表初始化内容中，我们调用了Screen类的构造函数去实例化一个匿名对象。

基于const的重载

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Screen
{
public:
    Screen &display()
    {
        //this指针隐式地传递给do_display()，从指向非常量的指针转换成指向常量的指针
        do_display();
        return *this;
    }
    const Screen &display()//重载函数
    {
        do_display();
        return *this;
    }
private:
    void do_display() const
    {
        cout << this->contents << endl;
    }
};

• 当我们在某个对象上调用display时，该对象是否是const决定了应该调用display哪个版本

7.3.3 类类型

• 即使两个类的成员完全一样，也是不同的类型
• 类的声明
  class Screen;
  向程序中引入名字Screen并且指明它是一种类类型，但是我们不知道它里面有什么。
  对于一个类来说，我们必须定义它之后再去创建它的对象，不然编译器不知道给你这个对象分配多少内存。
  得到一个结论，一个类的成员类型不能是它自己，但是可以是它的指针或者引用。

7.3.4 友元再探

• 友元函数能定义在类的内部，这样的函数是隐式内联的

• 友元关系不存在传递性

• 类之间的友元

1
2
3
4
5

class Screen
{
    friend class Window_mgr;    
    //Window_mgr可以访问Screen所有成员
}

• 令成员函数成为友元
  这个之前引出友元概念的时候就介绍了：

1
2
3
4
5

class Screen
{
    friend void Window_mgr::clear();    
    //这里是跟人家的成员函数做朋友
}

• Screen类要把Window_mgr类的clear()设为友元
  声明____________定义_____________声明
  定义 __________________________ 友元声明、定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Screen;//1.声明Screen

//2. 定义Window_mgr类，其中声明clear函数，但不定义它
class Window_mgr {
public:
    using ScreenIndex = std::vector<Screen>::size_type;
    inline void clear(ScreenIndex);
private:
    std::vector<Screen> screens;
};

//3.定义Screen，包括对clear的友元声明
class Screen {
    friend void Window_mgr::clear(ScreenIndex);
}


//4 定义clear
inline void Window_mgr::clear(ScreenIndex i)
{ 
    if (i >= screens.size()) return;    // judge for out_of_range.
    Screen &s = screens[i];
    s.contents = std::string(s.height * s.width, ' ');
}

7.4.1 名字查找与定义域

• 类的定义分两步处理：编译器处理完类中的全部声明后才会处理成员函数的定义。遇到声明，都是去看本作用块中到此为止以前部分。
• 对于成员函数：成员函数体直到整个类可见后才会被处理，所以它能使用类中定义的任何名字

用于类成员声明的名字查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14

typedef double Money;
string bal = "a";
class Accout
{
public:
    Money balance()//使用的是外层的Money，**因为编译器只考虑Account中在实验Money前出现的声明**
    {
        return bal;
    }
private:
    Money bal = 1;
    typedef double Money; //这样不行的，重新定义类型不能覆盖，是错误的行为
    //但是编译器并不会报错，所以要自己小心
};

• 总结
  查找本区域中；找不到找外围作用域中；当成员定义在类的外部时，名字查找的第三步要考虑成员出现之前的全局作用域

Exercise 7.35

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

typedef string Type;
Type initVal(); // use `string`
class Exercise {
public:
    typedef double Type;
    Type setVal(Type); // use `double`
    Type initVal(); // use `double`
private:
    int val;
};

Type Exercise::setVal(Type parm) {  // first is `string`, second is `double`
    val = parm + initVal();     // Exercise::initVal()
    return val;
}

fixed

changed

1
2
3
4

Type Exercise::setVal(Type parm) {
    val = parm + initVal();
    return val;
}

to

1
2
3
4

Exercise::Type Exercise::setVal(Type parm) {
    val = parm + initVal();
    return val;
}

and Exercise::initVal() should be defined.

7.5 构造函数再探

7.5.1 构造函数初始化列表

• 初始化和赋值区别，前者直接初始化数据成员，后者则先初始化再赋值。建议使用构造函数初始值
• 成员的初始化顺序与它们在类定义中的出现顺序一致，而与初始化列表无关
• 默认实参和构造函数
  通常，我们说默认构造函数是没有参数的，但我们也可以这么干：

1
2
3
4
5

class Sales_data
{
public:
    Sales_data(string s = "") : bookNo(s){}
}

你可能觉得这个函数是一个普通的构造函数，但是，其实它是这个类的默认构造函数，它用到了默认实参，这么写的好处是，你可以不传参数，也能调用（不就相当于默认构造函数了吗），你不传参数的时候，它就用空字符串s去初始化bookNo，(类比下默认参数的情况)传的话就按照传的来，一式两用，还是很不错的。

• 如果一个构造函数为所以的参数都提供了默认实参，则它实际上也定义了默认构造函数

7.5.2 委托构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

    class Sales_data
{
public:
    //这是函数一，是一个普通的构造函数
    Sales_data(string s, unsigned cnt, double price) : bookNo(s), units_sold(cnt), revenue(cnt*price){}

    //接下来就是各种偷懒方法了，注意看
    Sales_data(): Sales_data("", 0, 0){} //函数二是默认构造函数，委托函数一帮忙初始化，也可以认为是调用了函数一
    Sales_data(string s): Sales_data(s, 0, 0){} //函数三接受一个string参数，委托函数一帮忙初始化
    Sales_data(istream &is): Sales_data()
    {
        read(is, *this);
    }
    //函数四复杂些，它先委托函数二，就是默认构造函数，函数二去委托函数一，这些函数执行完成后，再执行函数四的函数体
    //调用read函数读取给定的istream
};

7.5.3 使用默认构造函数

Sales_data obj; //注意不要加括号啊，加了括号就成了函数声明了.本意是想定义一个使用默认构造函数进行初始化的对象

7.5.4 隐式的类类型转换

• 如果构造函数只接受一个实参，那它实际上定义了一种隐式转换机制，什么意思呢，以Sales_data为例，该类有一个只接受一个string的构造函数，所以啊，我们可以把string转换为Sales_data类的对象：

1
2
3

Sales_data b;
string a = "1";
b.combine(a); //这里a被转换为Sales_data对象，编译器创建了一个临时对象

这种只带一个参数的构造函数，我们也把它称为转换构造函数。

但是我们只允许一步类类型转换，举个例子：

1
2
3
4
5
6

item.combine("1");
//这样是错的，因为字符串常量到string是一步，string到类对象时一步，两步不行的
//不过我们可以用显式地写
item.combine(string("1"));
item.combine(Sales_data("1"))
//总之，隐式的只能帮你一步

7.6 类的静态成员

• 因为静态成员函数不与任何对象绑定，所以没有this指针，不能声明为const的。
• 在类外部定义静态成员时，不能重复static关键字，该关键字只能出现在类内部的声明语句。在类内部不要定义、初始化静态成员
• 我们来定义一个在类内已经声明的static成员：

1
2
3

double Account::interestRate = initRate();
//为什么不用在initRate函数前面加Account::呢
//因为从类名开始，剩下的部分都处于类的作用域之内了。

静态成员能用于某些场景，而普通成员不能

1
2
3
4
5
6

class Bar
{
    private:
        static Bar m1; //这个逆天吧，可以自己的类型;静态成员可以是不完全类型
        statuc int &m2; //逆天吧，未初始化的引用；
};

主要是因为，静态成员一般在外面定义初始化，所以，在类内可以是不完全类型，胡作非为。

还有一个区别是，静态成员可以作为默认实参，666

1
2
3
4
5
6
7

class Screen
{
public:
    Screen& clear(char = bkground); //666
private:
    static const char bkground; 
};

非静态数据成员不能作为默认实参，因为它是属于对象的，你用对象的值去作为默认实参，结果是无法真正提供一个对象来获取成员的值，会引发错误。

第9章 顺序容器

9.1 顺序容器概述

• vector、deque、list（双向链表）、
  forward_list、array、 string
• list、forward_list都没有size操作
• 使用原则

  除非有很好的理由选择其他，否则选择vector
  要随机访问，选择deque或vector，要中间插入或删除元素，用list或forward_list
  既要随机访问，又需要中间插入，看哪个用的多

• 假设noDefault是一个没有默认构造函数的类型，则

1
2

vector<noDefault> v1(10, init);//正确
vector<noDefault> v1(10);//错误，必须提供一个元素出

9.2.1 迭代器

• forward_list不支持–运算符
• 双向链表的两个迭代器不能用<、<=等比较，因为节点不一定连续

9.2.2 容器类型成员

• 的size函数返回的是一个xx::size_type配套类型，这些配套类型体现了标准库类型与机器无关的特性。索引下标也是xx::size_type

9.2.3 begin和end成员

• begin end 不以c开头的都是被重载过的
• auto it7 = a.begin();//仅当a是const时，it7是const_iterator

9.2.4 容器定义和初始化

• C c = {a, b, c,…} 任何遗漏的元素都进行值初始化
• C c(b, e); array不适用
• 顺序容器（array除外）还提供另一个构造函数，接受一个容器大小的和一个可选的元素初始值。如果不提供元素初始值则标准库会创建一个值初始化器——内置类型或具有默认构造函数就能自设初始值
• 内置数组不能拷贝或赋值，array可以

1
2
3
4
5

int digs[10] = {0,1};
int cpy[10] = digs;//错误

array<int, 10> digits = {0,1};//注意要同时指定类型和大小
array<int,10> copy = digs;//正确

• array不支持的地方：(迭代器1，迭代器2)初始化，assign(assign不支持关联容器、array)、insert（push_back）、resize
• 只有顺序容器的构造函数才接受大小参数，关联容器不支持

9.2.5 assign和swap

1
2

names.assign(oldstyle.cbegin(),oldstyle.cend())
slist1.assign(10,"Hi");//assign的两个版本

• 赋值操作导致左边容器内部的迭代器、引用、指针失效

1
2
3

vector<string> vec1(10);
vector<string> vec2(24);
swap(vec1,vec2);//交换两个相同类型容器的内容，元素不移动，只是交换了两个容器的内部结构，因此可以在常数时间内完成迭代器、引用、指针失效。 array用swap会真正交换元素，时间正比于元素个数，迭代器、引用、指针所绑定的元素不变

9.2.6 容器大小操作

9.2.6 关系运算符（> < >= <= ==）

• 除了无序关联容器关系运算符都支持比较， 类似string

9.3 顺序容器操作

9.3.1 向顺序容器添加元素

• c.insert(p,t)
  c.emplace(p,args)
  在迭代器p指向的元素之前创建一个值为t或由agrs创建的元素(把参数传递给容器的元素类型的构造函数)，返回指向新添加的元素的迭代器
• c.insert(c.end(),10,“Anna”);//在末尾插入
• 向vector、string、deque插入元素后（deque首尾插入、list、forward_list没关系）会使得插入元素后面的指向容器的迭代器、引用、指针失效。若扩容了原先的都会失效
• 容器元素是原对象值的拷贝
• vector、string不支持push_front和emplace_front，deque支持 但是可以用insert实现对应的功能

1
2
3
4
5
6
7

void double_and_insert(std::vector<int>& v, int some_val)
{
    auto mid = [&]{ return v.begin() + v.size() / 2; };//lamda表达式
    for (auto curr = v.begin(); curr != mid(); ++curr)
        if (*curr == some_val)
            ++(curr = v.insert(curr, 2 * some_val));
}

9.3.2 访问元素

• c.back(),c.front() ,返回首尾元素的引用(c[n],c.at(n)也是引用)
• c.at()：at会进行下标越界检查，越界时抛出out_of_range异常。因此更安全

9.3.3 删除

• c.pop_back()：forward_list不支持。返回void
  c.pop_front()：vector,string不支持。返回void
• c.erase§：删除迭代器p指定的元素，返回被删除元素后元素的迭代器。若p是尾元素，则返回尾后迭代器；若p是尾后迭代器，结果未定义；​
• c.erase(b,e)：删除迭代器b、e范围间的元素，e不会删除。返回最后一个被删除元素后一个元素的迭代器。调用结束后，b == e​
• c.clear()：删除所有
  返回void
• 除了deque删除首尾元素，指向vectorhe和string中删除点之后的迭代器、引用和指针都会失效，list、forward_list没关系
• vector和string不支持push_front()、pop_front()

9.3.4 forward_list操作

• 插入 在迭代器p之后的位置插入元素，返回指向最后一个插入元素的迭代器。注意其他顺序容器插入后是返回指向第一个新添加的元素的迭代器，且是往迭代器之前插

1
2
3
4
5
6

lis.before_begin()//首前迭代器
lis.insert_after(p,t)
lis.insert_after(p,n,t)
lis.insert_after(p,b,e)
lis.insert_after(p,il)
lis.emplace_after(p,args)

• 删除：返回被删除之后元素的迭代器。如果p指向尾元素或是一个尾后迭代器，结果未定义.

1
2

lis.erase_after(p)：删除迭代器p之后的元素
lst.erase_after(b,e)：不包含迭代器b指向的元素

9.5.2 改变string的其他方法

• s.insert(11,“fifth”)
• s.replace(11,3,“fifth”)
• s.erase(11,3)

9.5.3 string搜索操作

• 搜索的返回值string::size_type 搜索失败返回string::npos

compare函数

• s.compare(s2)

9.5.5 数值转换

• to_string(i) // 整数i转换为字符表示形式
• stod(s) //字符串s转换为浮点数 第一个字符可以是+—数字
• stoi(s) //转为整型

9.6 容器适配器

• stack queue基于deque实现的，priority_queue是在vector上实现的

第10章 泛型算法

10.1 概述

• find
  vector 的 find：
  vector<int>::iterator it = find(vec.begin(), vec.end(), 6); 查找6,找到返回第一个的迭代器，找不到返回尾后迭代器
  数组的find：

1
2
3
4
5
6
7
8
9

int myints[] = { 10, 20, 30, 40 };
    int * p;
    
    p = find (myints, myints+4, 30);  //返回查找到的元素的物理地址
    cout<<p<<"\n";
    if (p != myints+4)
        cout << "Element found in myints: " << *p << '\n';
    else
        cout << "Element not found in myints\n";

• 泛型算法本身不会执行容器的操作，只会运行与迭代器之上，执行迭代器的操作。算法永远不会改变底层容器的大小。
• 标准库定义了特殊的迭代器，称为插入器，当给这类迭代器赋值时，他们会在底层的容器上执行插入操作。即算法执行迭代器，迭代器完成向容器添加元素的效果，但算法自身永远不会做这样的操作。

10.2 初识泛型算法

10.2.1 只读算法

accumulate

对元素求和int sum = accumulate(vec.cbegin(), vec.cend(), 0);第三个参数是和的初始值
string sum = accumulate(vec.cbegin(), vec.cend(), string("")); accumulate第三个参数的类型决定了函数中使用哪个加法运算符以及返回值的类型。

1
2

string sum = accumulate(vec.cbegin(), vec.cend(), "");
//错误，如果传递一个字符串字面值，用于保存和的对象类型是const char*，这种类型上没有定义+运算符

操作两个序列的算法 equal

• equal(vec1.cbegin(), vec1.cend(), vec2.cbegin());//接收三个迭代器，前两个（与以往一样）表示第一个序列中的元素范围，第三个表示第二个序列的首元素
• 元素类型也不必一样，只要我们能用==来比较两个元素类型（其实视情况而定，c风格的字符串比较比较的是字符串的指针。但是呢，对于相同的字符串，编译器会把他们存在相同的地址里面，详见P339 ex10.5）
• 这些只接受一个单一迭代器来表示第二个序列的算法，都假定第二个序列至少与第一个序列一样长

第11章 关联容器

11.1 使用关联容器

• map
• set
• multimap
• multiset

1
2
3
4
5

//求最大的k个元素
    int findKthLargest(vector<int>& nums, int k) {
        
        if (k < 1 || k > nums.size()) return -1;
        multiset<int,less<int>> largestK;//小顶堆（根小于等于儿子），less<int>是默认的

• unordered_map
• unordered_set
• unordered_multimap
• unordered_multiset
• map元素是pair类型的对象，first, second两个数据成员
• set中 exclude.find(word) 调用返回迭代器，如果给定关键字在set中，迭代器指向该关键字。否则，find返回尾后迭代器

1
2
3
4
5
6

pair<T1,T2> p //数据成员值初始化
pair<T1,T2> p = p2
pair<T1,T2> p(v1,v2)
pair<T1,T2> p{v1,v2}
//与上面等价
makepair(v1,v2)

• pair比较大小，先比较第一个的

11.3 关联容器操作

1
2
3
4
5

key_type：关键字类型
mapped_type (仅map)：关键字关联的类型（即值的类型）
value_type
    map：pair<const k,v>，关键字为const意味着不能修改
    set：与key_type相同​

11.3.1 关联容器迭代器

1
2
3

map<int,int>::iterator mpIt;
for(mpIt = mp.begin(); mpIt != mp.end(); mpIt++);
    cout << mpIt->first << " " << mpIt->second << endl;

• 一个map的value_type是一个pair，我们可以改变pair的值，但不能改变关键字成员的值
• set的迭代器都是const的。不能修改元素的值
• 添加单一元素的insert和emplace版本返回一个pair，pair的first是一个迭代器，指向具有关键字的元素；second成员是一个bool值，告诉我们插入成功还是已经存在于容器中。（false插入失败，已经有值）

1
2
3
4
5
6
7

map<string, size_t> word_count;
string word;
while(cin >> word)
{
    auto ret = word_count.insert({word, 1}); //不在里面，值就是1
    if(!ret.second){ ++( (ret.first)->second ); } //已在里面，递增计数器
}

11.3.3 删除元素

1
2
3

c.eraser(k)	从c中删除每个关键字为k的元素，返回一个size_type值，即删除元素的数量
c.eraser(p)	从c中删除迭代器p指定的元素（必须存在），返回p之后元素的迭代器
c.eraser(b, e)	删除迭代器b和e之间的元素，返回e

11.3.3 map的下标操作

• 只有map有下标，set类型没有是因为人家就一个键，没有值，下标谁去，multimap没有是因为可能有多个值跟键相关。有两种方式c[k]和c.at(k)，都是有就返回值（类型为mapped_type），没有就插入
• C++ map中key值存在情况判定

count函数
count函数用于统计key值在map中出现的次数，map的key不允许重复，因此如果key存在返回1，不存在返回0

1
2

if (testMap.count(key) == 0)
    cout << "no this key" << endl;

11.3.5 访问元素

1
2
3
4
5
6
7
8
9

set<int> iset = {0, 1, 2, 3, 4};
iset.find(1); //返回一个指向1的迭代器
iset.find(-1); //返回一个指向iset.end()的迭代器
iset.count(1); //返回1，返回该元素的数量
iset.count(11); //返回0

iset.lower_bound(2); //返回一个迭代器指向第一个不小于2的元素，就是2
iset.upper_bound(2); //返回一个指向第一个大于2的元素迭代器，3
iset.equal_range(2); //返回一个迭代器pair，表示键等于2的元素范围，没有就返回一对end

set的查找

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

## 11.3.6 单词转换的map
```cpp
作者：苍井玛利亚
链接：https://www.nowcoder.com/discuss/20296
来源：牛客网

//函数word_transform
void word_transform(ifstream &map_file, ifstream &input)
{
    auto trans_map = buildMap(mapfile); 
    string text; //保存输入中的每一行
    while(getline(input, text))
    {
        istringstream stream(text); //读取每个单词,忽略空格
        string word;
        bool firstword = true; //控制是否打印空格
        while(stream >> word)
        {
            if(firstword){firstword = false;}
            else{cout << " ";}
            cout << transformm(word, trans_map); //打印输出
        }
        cout << endl; //完成一行
    }
}

//函数buildMap
map<string, string> buildMap(ifstream &map_file)
{
    map<string, string> trans_map;
    string key;
    string value;
    while(map_file >> key && getline(map_file, value)) //取一行，分别作为键值
    {
        if( value.size()>1 ) //确保有转换内容
        {
            trans_map[key] = value.substr(1); //跳过单词和转换内容之间的空格，因为getline不会跳过前导空格
        }
        else
        {
            throw runtime_error("no rule for " + key);
        }
    }
    return trans_map;
}

//函数transform
const string& transform(const string &s, const map<string, string> &m)
{
    auto map_it = m.find(s);
    if(map_it != m.cend())
    {
        return map_it->second;
    }
    else
    {
        return s;
    }
}

• trans_map[key] = value.substr(1)和trans_map.insert({ key, value.substr(1) })区别？
  如果出现多次，下标法插入最后一个，insert插入第一个

11.4无序容器

• 用hash来种植元素

第12 章 动态内存

12.1 动态内存与智能指针

• 通过不同方式定义的变量类型在内存中的存储位置也不同，分以下三种情况：
  • 静态内存：保存局部static对象、类static数据成员、定义在任何函数之外的变量
  • 栈内存：保存定义在函数内的非static对象
  • 堆：存储动态分配的对象，当动态对象不再使用时，我们必须显式地销毁它们
• 智能指针的行为类似常规指针，重要的区别是它负责自动释放所指向的对象。两种智能指针管理底层指针的方式不同：
  • shared_ptr允许多个指针指向同一个对象
  • unique_ptr独占所指向的对象
  • weak_ptr，弱引用，指向shared_ptr所管理的对象
    以上三种类型都定义在memory头文件中。

12.1.1 shared_ptr类

• 类似vector，智能指针也是模板：

1
2

shared_ptr p1; //shared_ptr, 指向string
shared_ptr> p2; //shared_ptr, 指向list

• 默认初始化的智能指针中保存着一个空指针。 智能指针的使用方式与普通指针类似，解引用一个智能指针返回它指向的对象：

1
2
3
4

if(p1 && p1->empty()) //如果指针本身不为空（有所指对象），且指针所指对象为空
{
    *p1 = "hi";
}

make_shared()

• 传递的参数必须能用来初始化所指对象

1
2

shared_ptr<int> p1 = make_shared<int>(42); //指向int42的share_ptr
shared_ptr<string> p2 = make_shared<string>(5,'9'); //指向"99999"的share_ptr

• 不传递参数时，对象就会进行值初始化

1

shared_ptr<int> p0 = make_shared<int>(); //指向值初始化的int0的share_ptr

shared_ptr的拷贝与赋值

• 当进行拷贝或赋值操作时，每个shared_ptr都会记录有多少个其他shared_ptr指向相同的对象：

1
2

auto p = make_shared<int>(42); //p指向的对象只有p一个引用者
auto q(p); //p和q指向相同对象，此对象有两个引用者

• 引用计数： 无论何时我们拷贝一个shared_ptr，都会递增计数器，举些不那么明显的拷贝例子
  • 用一个shared_ptr初始化另一个shared_ptr
  • 将它作为参数传递给一个函数
  • 作为函数的返回值
• 递减计数器：
  • 给shared_ptr赋予一个新值
  • shared_ptr被销毁（例如一个局部的shared_ptr离开其作用域）
• 一旦一个shared_ptr的计数器变为0，它就会自动释放自己所管理的对象：

1
2
3
4

auto r = make_shared(42); //r指向的int只有一个引用者
r = q; 
//1：给r赋新值，让它指向新地址；2：递增q指向对象的引用计数；
//3：递减r原来指向的对象的引用计数；4：r原来指向的对象已没有引用者，会自动释放

• 程序使用动态内存出于以下三种原因之一：

  • 程序不知道自己要使用多少对象（比如容器类）
  • 程序不知道所需对象的准确类型（15章再学）
  • 程序需要在多个对象间共享数据（接下来介绍）

• 对const 重载，返回类型、this都加

12.1.2 直接管理内存

• 动态分配内存的对象是默认初始化的，这意味着内置类型或组合类型的对象的值是未定义的，而类类型对象将用默认构造函数进行初始化

1
2
3
4

string *ps1 = new string; //默认初始化为空string 
string *ps2 = new string(); //值初始化为空string
int *pi1 = new int; //默认初始化：*p1未定义 
int *pi2 = new int(); //值初始化为0，pi2指向的内存值为0

• 神器auto在这种初始化方式下有所限制：

1
2
3

auto p1 = new class(T); //p指向一个与T类型相同的对象，该对象用T进行初始化
auto p2 = new class{a, b, c}; //这样不行，括号中只能有单个初始化器，
//因为你这样让auto无法判断p2是什么类型

• 动态分配的const对象

1
2

const int *pci = new const int(24);
const string *pcs = new const string; //和其他const对象一样，一个动态分配的const必须被初始化

• 内存耗尽:在C++中，如果new不能分配所要求的内存空间，它会抛出一个类型为bad_alloc的异常，不过，我们可以阻止它抛出异常：

1
2

int *p1 = new int; // 如果失败就会抛出异常
int *p2 = new (nothrow) int; //分配失败只会返回一个空指针

• 释放动态内存

1
2

int *p1 = new int(24); 
delete p1; //分两步：销毁p1指向的对象，释放对应内存

• 释放空指针合法

1
2

int * pi = nullptr;
delete pi;

1
2
3
4
5
6

bool b() {
    int* p = new int;
    // ...
    return p;
}
//The p will convert to a bool , which means that the dynamic memory allocated has no chance to be freed. As a result, memory leakage will occur.

12.1.3 shared_ptr和new结合使用

• 智能指针的构造函数是explicit的（禁止隐式转换），所以必须使用直接初始化形式

1
2

shared_ptr p1(new int(24)); //我们知道这样是对的，直接初始化
shared_ptr p2 = new int(24); //错误，不能使用拷贝初始化，因为不能进行内置指针到只能指针间的隐式转换

不要混合使用普通指针和智能指针

错误例子

1
2
3
4

void process(shared_ptr ptr){}
int *x(new int(24));
process(shared_ptr(x));//调用结束时，所指向的对象也就是x被释放了
int j = *x; //x是空悬指针

• 使用内置指针来访问一个智能指针所负责的对象是很危险的，因为我们无法知道对象何时被销毁

也不要使用get初始化另一个智能指针或为智能指针赋值（也是不要混合使用普通指针和智能指针，赋值是推荐make_shared而不是new）

1
2
3
4
5
6
7

shared_ptr p(new int(42));

{
    shared_ptr(p.get()); //两个独立的智能指针指向相同的内存块（要出事情），此时形成的参数并不是对p的拷贝，而是一个独立的指针。改成shared_ptr(p)就没事情
} //q指向的内存被销毁
int foo = *p; //p是空悬指针，报错。

12.1.4 智能指针和异常

• 使用智能指针的好处：即便代码出现没有catch到的异常，还是能保证内存的释放：

1
2
3
4
5

void f()
{
    shared_ptr sp(new int(42));
    //假设之后的代码出现了没有捕捉到的异常
} //在函数结束时，shared_ptr还是会自动释放内存

• 用智能指针管理，并且定义一个函数（删除器）用来代替delete函数：
  shared_ptr p(q,d);//p接管了内置指针q所指向的对象的所有权。q必须能够转化为T*类型。p将使用可调用对象d

1
2
3
4
5
6

void end_connect(connect *p){ disconnetc(*p); } //定义了删除器（调用了一个函数）
void f()
{
    connect c;
    shared_ptr p(&c, end_connect); //用p来管理c的内存
}//退出后c就会被正确关闭销毁

12.1.5 unique_ptr

• 必须采用直接初始化形式。unique_ptr不支持普通的拷贝或赋值

1
2

unique_ptr p1;
unique_ptr pt(new int(42));

c++ 11 新特性

• 尾随返回类型 P233 ex7.5

华为机试

购物单

• 有依赖的分组背包问题
• set的使用
• memeset 要加头文件#include

坐标移动

• string 迭代器与自增 *(itFront++) 先访问*itFront再让itFront加
• isalnum© 字母或数字 isalpha©字母 isdigit© 数字 islower isupper
• 字符串常用操作取子串string str =“Hello”；
  str.substr(0,4)=“Hell”,0是起始位置，4是要复制的长度
• s.substr(5); //只有一个数字5表示从下标为5开始一直到结尾

1
2
3

string ss = "aa";
cout << ss.substr(2);//√
cout << ss.substr(3);

• 删除最后一个 s.pop_back();

• 排序降序 #include sort(a,a+20,greater());//第三个参数可以不写 默认从小到大排序

1
2
3
4
5
6
7
8
9

sort(a, a+n, cmp);
cmp也可以自己写
static bool cmp(node a, node b)//要加static https://blog.csdn.net/u010982765/article/details/79021426
{
    if(a.w < b.w ) //按照w的值进行的是：升序排列 ！
        return true;
    else
        return false;
}

vector的排序 sort(po.begin(), po.end(), cmp);

• string find

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int left=0,right=s.size()-1;
    while(left<right)
        {
            left=s.find_first_of("aeiouAEIOU",left);//从left位置开始 找到aeiouAEIOU里一个即可
            right=s.find_last_of("aeiouAEIOU",right);
            if(left<right)
            {
                swap(s[left++],s[right--]);
            }
        }
```  
s.rfind(args)查找s中args最后一次出现的位置  
s.find_last_of(args)查找s中args里面任何一个字符最后一次出现的位置  
s.find_first_not_of  
str1.find(str2,5);//   从str1的第5个字符开始查找str2,找不到返回-1

- vector 的 find：
    `vector<int>::iterator it = find(vec.begin(), vec.end(), 6);` 查找6


### 删除字符串中出现次数最少的字符

it2 = str.erase(it2);//it2是string迭代器，返回指向删除字符的后一字符位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

```cpp
for (it = str.begin(); it < str.end(); it++)
    {
        if (*it == ch)
        {
            str.erase(it);
            it--;
            /*
            it--很重要，因为使用erase()删除it指向的字符后，后面的字符就移了过来，
            it指向的位置就被后一个字符填充了，而for语句最后的it++，又使it向后移
            了一个位置，所以就忽略掉了填充过来的这个字符。在这加上it--后就和for
            语句的it++抵消了，使迭代器能够访问所有的字符。
            */
        }
    }

函数不要返回指向栈的内存地址，切记，是地址，别被吓的所有的函数内的变量都不敢返回，只要不是栈的内存地址，你尽管放心的返回。

旋转数组返回最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        int mid;
        while (l < r) {//考虑只有一元素，如果是等于就会一直循环
            if (nums[l] < nums[r]) break;//最左边小于最右边 直接返回最左边
            mid = l + ((r-l)>>1);
            if (nums[l] <= nums[mid]) l = mid + 1;
            else r = mid;
        }
        return nums[l];

    }
};

BFS

• BFS的问题一般都会选用队列方式实现；
• 代码模板如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void BFS()
{
    定义队列;
    定义备忘录，用于记录已经访问的位置；

    判断边界条件，是否能直接返回结果的。

    将起始位置加入到队列中，同时更新备忘录。

    while (队列不为空) {
        获取当前队列中的元素个数。
        for (元素个数) {
            取出一个位置节点。
            判断是否到达终点位置。
            获取它对应的下一个所有的节点。
            条件判断，过滤掉不符合条件的位置。
            新位置重新加入队列。
        }
    }

}

• 二分查找
  lower_bound(val):返回容器中第一个值【大于或等于】val的元素的iterator位置。
  upper_bound(val): 返回容器中第一个值【大于】

第二课：高精度地图

高精度地图

• 厘米级进度。交通灯、限速、路标等信息
• 搜集的信息与高精度题图匹配——预处理、坐标转换、数据融合——以便知道自己处于什么位置
• 高精度地图作用，传感器有距离限制，这种情况下由高精度地图提供位置。另一个好处减小传感器检测范围——集中检查感兴趣区域ROI，提高速度进度 减小计算资源。规划软件也需要 靠近中心线，帮助减少决策空间
• Apollo高精度地图采用了OpenDRIVE格式，行业制图标准
• 高精度地图5个过程：数据采集（众包采集）、数据处理、目标检测、手动验证、地图发布

第三课 定位

• GPS进度在1-3米，在信号不好的地方，可以达到数十米。转换坐标系、由传感器得到的标示与 在全局地图上的位置进行匹配

GPS（GNSS）

• 三角定位（三个圆交点），GPS传送距离
• gps 卫星、地面的控制站 监视和控制卫星、GPS接收器（手机上、汽车上）。每次至少接收4颗。时间乘以光速（原子钟）。 RTK纠错发给gps接收器。 gps缺点受遮挡物干扰、更新频率低

惯性导航

• 三轴传感器测加速度。 螺旋仪。 IMU短时间内定位，频率高，短时间定位。要与gps结合。但是仍旧不精确 因为gps有些地形下失效

激光雷达定位

• 点云匹配——迭代最近点法，点云旋转 减小误差，匹配，传感器得到的位置转化为全局
• LiDAR：滤波算法；消除冗余，最小平方误差。 卡尔曼滤波，预测新位置，用传感器测量新位置纠正。优点稳健性，只要有高精度地图+传感器更正。难点 地图不可能保持最新

图像定位

• 粒子滤波（概率）。对车道线拍照。优点 图像数据容易得到。缺点：缺乏三维信息和对三维地图的依赖

第四课 感知

• 4个核心人物检测：找出位置，分类、跟踪、语义分割
• 分类器：接收输入，预处理（标准化，调大小、旋转）、提取特征
• 摄像头图像：RGB图像
• LiDAR图像：雷达发射，点云
  
• 机器学习：使用数据。监督式学习、半监督、无监督。强化学习
• 神经网络：调整某些特征的权重，得到最终结果
• 反向传播
• CNN：接收多维输入。标准神经网络的弄成一维，打破了图像中嵌入的空间信息。在整个图像上对一个过滤器进行卷积操作>

  （什么是卷积：图像中不同数据窗口的数据和卷积核（一个滤波矩阵）作内积的操作叫做卷积。其计算过程又称为滤波（filter)，本质是提取图像不同频段的特征。）

• 检测与分类：CNN中找出图像中对象的位置、定位，发给另一个CNN进行分类，或者直接一个CNN完成。R FastRCNN FasterRCNN ，YOLO SSD
• 跟踪：解决遮挡物、追踪可以保留身份。前后两帧中对象匹配。计算机视觉可以计算出复杂的图像特征，如局部二值模式和方向梯度直方图。连续帧中，两个障碍物之间的位置和速度
• 分割：确定汽车可行驶的位置。FCN，每一层都是卷积层。CNN最后输出比原图像小得多。为了分割图像，输出尺寸必须与原始图像的尺寸相匹配，中间输出进行上采用处理。 前半部分encoder对输入图像的特征进行了提取和编码。后半部分解码器对特征进行解码 用于输出。

  上采样可以用来进行图像放大，多采用内插方法，即在原有图像像素的基础上在像素点之间采用合适的插值算法插入新的元素

• 传感器融合

• 激光雷达、雷达，用于融合输出的主要算法是卡尔曼滤波——两个步骤

1. 预测状态
2. 更新测量结果（同步异步）

第五课：预测（移动路径）

• 实时性、准确性。5m内没东西。用多源的数据预测

• 两种类型：基于模型的（直观，结合了人的物理知识、交通法规）、数据驱动的（数据越多 越准确）

• 基于车道序列的预测：将道路分成多个区域，车辆如何在这些车道间变换，将车辆的运动描述为一组序列
  

• 障碍物状态：车道段内情况 到车道线的横向纵向距离、之前时间间隔的状态信息

• 预测目标车道：预测问题转为选择问题。通过计算每个车道的概率来选择

• 递归神经网络RNN：利用时间序列特征。传统神经网络 多层感知网络MLP。RNN中每个MLP单元将序列的一个元素作为输入，并预测序列的下一个元素作为输出。为了对元素之间的顺序关系建立模型，在每个单元之间建立一个额外的连接——意味着每个单元根据原始输入 和 前一个单元的输出进行预测
  

• 为车道序列提供一个RNN模型，为相关对象状态提供了一个RNN模型。Apollo连接这两个RNN的输出并将他们馈送到另一个神经网络，该神经网络估计每个车道序列的概率，具有最高概率的车道序列就是最终预测

• 轨迹生成：设置约束条件，去除大多数预选轨迹，考虑速度、加速度进一步去除。注意车辆在原始、结束状态的位置和速度，用这两个条件拟合多项式模型

第六课：规划

• 规划：路线导航。轨迹由一系列点组成，点还包括速度、何时抵达
• 通络搜索查找路线：将地图转化为图
  
• A*算法，起始节点-候选节点 + 候选节点-目的节点

轨迹

• 从路由到轨迹：从出发点-目的地——高等级地图（路由）。一条路段上行驶，需要低等级（轨迹）
• 轨迹生成：生成一系列路径点定义的轨迹，让一条曲线去和路径点拟合，生成轨迹的几何表征
  
  这些时间戳创建了一个三维轨迹2D position + time，每个点还有速度
• 轨迹的约束：防止碰撞、变化平滑、不能违法
• 评估轨迹：成本最低的轨迹，成本有惩罚组成（deviation、collisions、speed limit、comfort），不同场景成本函数不同
• Frenet坐标：笛卡尔坐标系的替代方案
  
• 路径 - 速度解耦规划：路径规划 成本函数 选出成本最低的路径；下一步 确定速度速度规划 与路径点相关点一系列速度——速度曲线。合起来就是行驶轨迹
• 在路径-速度解耦规划中生成候选路径：将路段分割成单元格，对单元格中的点随机采样。创多条候选路径，用成本函数选路。成本函数可以考虑的因素
  

速度

• ST图：选择好路径的下一步，是选择与该路径关联的速度曲线。S纵向位移，T时间，斜率速度
  
• 速度规划（有障碍物怎么处理、或其他限制）：为了构建最佳速度曲线，把ST离散为多个单元格，每个单元格内速度不变，可以简化。可以将障碍物绘制为在特点时间段内，阻挡道路的某些部分的矩阵
  
  使得速度曲线不与矩形相交即可

–

• 到目前为止因为路径选择是将道路划分为单 元格、速度曲线是把ST图划分为单元格，都是离散的。为了使曲线平滑，可以用二次规划将平滑的非线性曲线与这些分段式线性段拟合——生成路径-速度曲线

• Lattice规划的轨迹生成方法：三维的规划问题变化为两个二维的优化问题，S-T、L-S图，通过对预选模式中的多个候选最终状态进行采样，生成多组轨迹，来选择最终车辆状态？？是在检测是否到达终止状态吗？？，使用成本函数来对这些轨迹进行评估选择最好的轨迹

• ST轨迹的终止状态：巡航、跟随和停止。
  巡航：完成规划步骤后定速行驶，在对地图上的点进行抽样？？？，所有最终状态的加速符为0.
  跟随模式：对位置和时间状态进行采样，尝试在时间t出现在某辆车后面跟随车辆时，保持安全距离，速度和加速度取决于前车
  停车：对汽车何时何地停止进行抽样，速度加速度都为0

• SL曲线的终止状态：最终要与车道中心线一致。采样的是道路上相邻车道中心线周围的位置
  车的朝向和位置的一阶二阶导数都为0——既不是横向移动的也不是横向加速的
  

• Lattice规划的轨迹生成：转为笛卡尔
  

第七课：控制

• 不要偏离预定轨道、可行性、舒适性、控制要连续性不要突然制动或加速或转向
• 输入：由规划模块给出的目标轨迹，
  每个轨迹点有一个位置和参考速度，每个时间步都对轨迹进行更新。要通过自身传感器了解自身状态，来计算实际与目标的偏差
• 输出：转向、加速度、制动
• PID依赖于实时误差测量

现在分析一下常见的排序算法的稳定性，每个都给出简单的理由。
(1)冒泡排序
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改 变，所以冒泡排序是一种稳定排序算法。
(2)选择排序
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个 元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么 交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
(3)插入排序
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开 始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相 等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳 定的。
(4)快速排序
快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。 交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11， 现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。
(5)归并排序
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有 序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定 性。那么，在短的有序序列合并的过程中，稳定是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结 果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。
(6)基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优 先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。
(7)希尔排序(shell)
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元 素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
(8)堆排序
我们知道堆的结构是节点i的孩子为2i和2i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n /2-1, n/2-2, …1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没 有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。
综上，得出结论: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。