概念

1. **运输层协议为运行在不同主机上的应用进程提供了逻辑通信的功能。**从应用程序的角度来看，通过逻辑通信，运行不同进程的主机好像直接相连在一起。
2. 运输层协议是在端系统而不是在网络路由器中实现的。
3. 运输层为主机上的应用程序提供直接的通信服务，接受网络层提供的服务。

运输层

运输层和网络层的关系

**运输层为运行在不同主机上的进程提供了逻辑通信，而网络层提供了主机之间的逻辑通信。**从应用程序的角度来看，通过逻辑通信，运行不同进程的主机好像直接相连在一起。
**运输层协议是在端系统而不是在网络路由器中实现的。运输层协议只工作在端系统，中间路由器和交换机既不处理也不识别运输层加在应用层的任何报文。**运输层协议将来自应用进程的报文划分成报文段，封装后交付网络层，或者将网络层的报文段，重新装配成报文交给应用层的应用进程。但是，对于这些报文在网络中怎么移动的不做任何规定。

运输层和网络层概述

网络层协议有一个名字叫IP，网际协议。IP为主机之间提供了逻辑通信，IP的服务模型是尽力而为交付服务。它不能保证报文段的交付，顺序和完整性，所以被称为不可靠服务。
TCP/IP网络为应用层提供了两种运输层协议TCP和UDP：
UDP为调用它的应用程序提供了不可靠的无连接的服务；
TCP为调用它的应用程序提供了可靠的面向链接的服务。
UDP和TCP的最基本任务是将两个端系统之间IP的交互服务扩展为运行在两个端系统上的进程之间的交付服务。**进程间数据交付和差错检查是两种最低限度的运输层服务，也是UDP能提供的仅有的两种服务。**UDP也是一种不可靠的服务。UDP和TCP还可以在报文段的首部上添加差错检测字段而提供完整性检查。TCP为应用程序提供了几种附加服务：提供可靠数据传输，和拥塞控制。

多路复用和多路分解

1. 进程有一个或者多个socket，它是网络和进程之间交互的通道。将运输层报文段中的数据交付到正确的套接字的过程叫做多路分解；从源主机的不同套接字中手机数据块，封上首部信息生成报文段，将报文段传输到网络层的过程叫做多路复用。
   多路复用和多路分解将主机到主机之间的交互服务扩展为运行在两个主机上的进程之间的交付服务。
2. socket，套接字是应用程序进程和运输层协议之间的应用程序编程接口。套接字在应用层有一部分，在传输层也有一部分，应用程序开发者可以控制套接字在应用层的所有东西，但是对于套接字在传输层的东西几乎没有控制。
3. 一个UDP套接字由一个包含目的IP地址和目的端口号的IP地址的二元组进行标识的，一个TCP套接口由源IP地址，源端口号，目的IP地址，目的端口号的四元组进行标识。
4. UDP和TCP报文中都有源端口号和目的端口号，接收端从报文段中提取源端口号作为回传的目的端口号。

UDP

UDP相对于TCP的优势：

1. 应用层能更好的控制要发送的数据和发送时间。
2. 无需连接建立。
3. 无连接状态。
4. 分组首部开销小。TCP报文段有20字节的首部开销，而UDP只有8字节的开销。

UDP报文段结构

UDP报文段的首部共8个字节，64位，每个字段8位，共4个字段，：

1. 16位源端口号，16位目的端口号
2. 16位长度字段，16位检验和

长度字段包含了首部在内的UDP报文段的长度（以字节为单位）。
检验和提供了差错检测功能，但是不能进行差错恢复。

可靠数据传输的原理

TCP

TCP报文段由首部字段和一个数据字段组成。

1. 16位源端口号，16位目的端口号；
2. 32位序号；
3. 32位确认号；
4. 4位首部长度字段，6位标志地钻，16位接收窗口；
5. 16位互联网校验和，16位紧急数据指针。

参考文献

1.《计算机网络自顶向下》

应用层协议原理

网络应用程序体系结构

BS架构和P2P架构。

进程通信

BS架构中，如WEB服务，浏览器进程是客户机，WEB服务器进程是服务器。
P2P架构中，发起通信的进程被称为客户机，在会话开始时等待联系的进程是服务器。
进程通过套接字(socket)的接口在网络上发送和接收报文，套接字是一个软件接口。
套接字是应用程序和网络之间的应用编程接口(API)。应用程序开发者可以控制套接字在应用层的所有内容，但是对于套接字在运输层的部分，开发者只能控制：

1. 选择运输层协议，
2. 设定几个运输层参数。

仅此而已，一旦运输层协议确定之后，应用程序就建立在该协议提供的运输层服务之上。

应用层需要的服务种类

1. 可靠数据传输。
2. 吞吐量。
3. 定时。
4. 安全性。

TCP/IP网络提供的运输层协议

1. 提供面向连接和可靠数据传输服务的TCP协议。TCP还有拥塞控制机制。
2. 提供无连接的和不可靠的数据传输服务的UDP协议。UDP没有拥塞控制机制。
3. TCP和UDP都没有加密。SSL是TCP的加强，是在应用层上实现的。
4. 上面说的应用层可能需要的服务种类，1和4可以通过TCP,UDP和SSL实现，而2和3其实还没有运输层协议实现。
5. 端口号用来做进程寻址，IP地址用于做网络中主机的寻址。

应用层协议

应用层协议定义了运行在不同端系统上的应用程序进程如何相互传递报文。
应用层协议和网络应用的区别，应用层协议是网络应用的一部分。比如HTTP协议是Web应用的一部分。

HTTP协议和Web应用

Web应用的应用层协议是HTTP协议。HTTP协议由两部分组成，一个客户机程序和一个服务器程序，它们运行在不同的端系统中，通过交换HTTP报文进行会话。
HTTP定义了Web客户机如何向Web服务器请求Web页面，以及服务器如何将Web页面传送给客户机。HTTP使用TCP而不是UDP作为它的运输层协议，TCP为HTTP提供可靠数据传输服务，客户机进程和服务器进程之间的每一个报文都能到达目的地。HTTP协议不用担心数据丢失，也不用担心TCP是如何从网络的数据丢失和乱序故障中恢复的，这是TCP和更底层协议栈的工作。
HTTP服务器并不保存关于客户机的任何信息，所以说它是一个无状态协议。

非持久连接和持久连接

当客户机和服务器长时间通信时，客户机发出一系列请求，服务器对于每个请求进行响应。如果每一个请求/响应对都有一个单独的TCP连接发送的，叫做非持久连接，如果所有的请求/响应经过同一个TCP连接发送，就做持久连接。
HTTP既可以使用持久连接也可以使用非持久连接。默认情况下使用持久连接。

HTTP报文格式

HTTP请求报文

一个请求行，
多个首部行，
空行，
实体主体

HTTP响应报文

一个状态行，
多个首部行，
空行，
实体主体

用户和服务器的交互：cookie

HTTP协议是无状态的，使用cookie可以用来识别用户。
cookie的组成部分：

1. 在HTTP相应报文中有一个cookie首部行。
2. 在HTTP请求报文中有一个cookie首部行。
3. 在用户端系统有一个cookie文件，由用户的浏览器管理。
4. Web站点有一个后台数据库。

Web缓存

条件GET

FTP协议和文件服务器

FTP使用两个并行的TCP来传输文件，一个是控制连接，一个是数据连接。控制连接用于在两个主机之间传输控制信息，数据连接用于实际传输一个文件。
因为FTP使用一个分离的控制连接，也称FTP的控制信息是带外传送的。而HTTP协议在传输文件的TCP连接中发送请求和响应首部行的，所以HTTP也可以说是带内发送控制信息的。
FTP的控制连接是持久的，而数据连接是非持久的。每传输一个文件，都需要打开一个数据连接。
FTP必须在整个会话期间保留用户的状态信息，而HTTP是无状态的。

DNS

因特网上的主机通过IP地址被识别，也可以通过主机名(hostname)被识别。主机名是不定长的，路由器很难处理，而IP地址是定长的，但是全是数字，不方便记忆。

什么是DNS

域名系统(Domain Name System)进行主机名到IP地址转换的目录服务。DNS是：

1. 一个分层的DSN服务器实现的分布式数据库
2. 一个允许主机查询分布式数据库的应用层协议。

DNS的解析流程

DNS运行在UDP上，使用53号端口。DNS通常由其他应用层协议使用，将用户提供的主机名解析为地址。当某个用户主机上的浏览器请求www.baidu.com时，具体的流程：

1. 同一台用户主机上运行着DNS应用的客服端。
2. 浏览器从url中取出主机名，将它传给DNS应用的客户端。
3. DNS客户端向DNS服务器发送一个包含主机名的请求。
4. DNS客户端接收一份回答报文，上面包含有对应主机名的IP地址。
5. 浏览器接收到IP地址后，向IP地址指定的HTTP服务器发起一个TCP连接。

DNS的功能

1. 向主机名转换为IP地址。
2. 主机别名，给一个主机名起一个别名，原来的主机名叫做规范主机名。主机别名通常比规范主机名更好记。
3. 邮件服务器别名。
4. 负载分配。DNS可以用于冗余的服务器之间进行负载分配。

DNS工作原理

1. 分布式，层次数据库
   有三种类型的DNS服务器，根DNS服务器，顶级域DNS服务器和权威DNS服务器。在因特网上有13个DNS服务器；顶级域服务器，负责顶级域名(com,org, net, edu, gov)和国家的顶级域名（uk, fr, ca和jp)；权威DNS服务器，将在因特网上拥有公共可访问主机的组织机构的主机名字映射为IP地址，权威DNS服务器负责保存这些记录。
   此外，还有本地DNS服务器，它不属于DNS服务器的层次结构，但是对于DNS层次结构很重要。
   DNS查询可以是迭代查询也可以是递归查询。
   迭代查询的过程，主机向本地DNS服务器请求某个域名的ip地址，本地DNS服务器依次向DNS服务器，顶级DNS服务器，权威DNS服务器发送请求。权威DNS服务器将目标主机的ip返回给本地DNS服务器，本地DNS服务器再将IP地址返回给主机。
   递归查询的过程，主机向本地DNS服务器请求，本地DNS服务器向根域名服务器请求，根域名服务器向顶级域名服务器发送请求，顶级域名服务器向权威域名服务器发送请求，返回再依次递归返回。
2. DNS缓存。当一个DNS服务器接收到一个DNS回答时，DNS服务器能将回答中的信息缓存在本地存储器。当下次有相同的请求时，这个DNS服务器可以直接返回缓存的结果而不需要请求上层DNS服务器，但是主机，主机名和IP之间的映射不是永久的，DNS服务器通常会在一段时间内丢弃缓存的信息。

电子邮件

参考文献

1.《计算机网络自顶向下》

lambda

lambda是一种可调用对象，它具有如下的形式：

1

[](param list)->return type {function body};

其中[]叫做capture list，(param list)是参数列表，return type是返回值类型，{function body}是函数体。
capture list和function body不能忽略，其他的部分都可以忽略。

向lambda传递参数

capture list和param list可以传递参数。capture list传递的是当前函数内的局部变量，表示lambda未来会使用这些变量，param list是lambda接受的参数。
capture list内可以是value capture，也可以是reference capture。它们的区别？

1. value capture需要变量可以拷贝，而且是在lambda创建时拷贝，而不是调用时。在创建后对变量的修改，不会改变lambda内对应的值。
2. reference capture实际上使用的是引用绑定的对象，需要注意，在调用时，要保证这个引用所绑定的变量是存在的。

隐式capture

capture list中指定=或者&可以自动推断lambda中可能用到的局部变量。隐式capture和显式capture可以同时存在。

指定返回类型

如果lambda中包含超过一个return之外的语句，编译器假定它返回void，然后就不会return了。lambda可以指定返回类型：

1

[](param list)->return type {function body};

参考文献

1.《C++ Primer》第五版中文版

C++ 中有四种可调用对象(callable object)。

1. 函数；
2. 函数指针；
3. 重载了函数调用运算符的类；
4. lambda表达式。

线程和进程的区别和联系

每个线程都包含有执行环境所必须的信息，包括进程中标识线程的线程ID，一组寄存器值，栈，调度优先级和策略，signal屏蔽字，errno变量和线程私有数据。
一个进程的所有信息对该进程的所有线程都是共享的，包括可执行程序的代码，程序的全局内存，堆内存，栈和文件描述符。

线程ID

线程ID只有在它所在的上下文才有意义。线程ID用pthread_t数据类型表示，实现的时候用一个结构体表示，所以不能把它当做整数处理。
在pthread_t的具体实现上，Linux使用无符号长整形表示（这个值看起来也像指针，但是不是指针），Solaris用无符号整形表示，FreeBSD和Mac OS X用指向pthread结构的指针表示。

创建线程

使用pthread_create进行。如果失败，返回错误码，而不是设置errno。

线程终止的方式

如果一个线程调用了exit, Exit或者_Exit，那么整个进程都会终止。
或者信号的默认动作是终止进程，那么发送到线程的信号就会终止整个进程。
单个线程可以通过三种方式退出。

1. 线程从启动例程返回。
2. 被同一进程中的其他线程cancel。
3. 调用pthread_exit

互斥锁

1. 互斥量有两种状态，要不加锁，要不就是不加锁。
2. 一次只有一个线程能够加锁。
3. 互斥锁是协作性锁，也就是说，比如共享数据是一个链表，那么操作该链表的所有操作都必须在实际操作前获取该互斥锁，但是！没有办法防止某个线程不首先获取该互斥锁就操作该链表。

生产者和消费者问题

一个或者多个生产者产生数据，一个或者多个消费者使用数据。
linux中shell管道就是一个生产者消费者问题，比如cat /etc/serveices|more，生产者的写和消费者的读，如果管道满了，就让生产者sleep，如果管道为空，就让消费者sleep。

当使用共享内存用做生产者和消费者的IPC时，它们必须执行某种显式的同步。

避免死锁

超时锁

读写锁

读写锁有三种状态：
读锁，写锁，不加锁。
一次只有一个线程可以占有写锁，但是多个线程可以同时占有读锁。读锁和写锁不能同时存在。

带有超时的读写锁筛选条件

筛选条件

条件变量

条件变量和互斥量的区别[2]。
mutex只是让我们阻塞直到lock可用。
而condition variable让我们阻塞到某个用户定义的条件可用。

自旋锁

mutex在阻塞的时候是sleep。
而自旋锁在阻塞的时候是占用cpu。

屏障

pthread_join就是一种barrier。
只不过pthread_barrier_wait() wait的是所有count个线程都要调用pthread_barrier_wait()。
而pthread_join() wait的是线程的返回值。
如果其他线程没有结束，主线程中没有调用pthread_join()获得这些线程的返回值。则主线程可能结束的比这些线程早，从而使得这些进程尚未完成就退出了（因为主进程会return或者调用exit)。

pthread_wait()的返回值，总共有count个线程调用，只有一个返回PTHREAD_BARRIER_SERIAL_THREAD，其他都返回0。

线程限制

线程属性

同步属性

重入

线程和特定数据

取消选项

线程和fork

线程和IO

函数

pthread_self

获得当前进程ID

pthread_equal

判断两个进程ID是否相等，返回值是0表示不相等

pthread_create

创建线程，返回值是0表示正常退出。

pthread_exit

终止当前线程，设置的retval可以被pthread_join得到。

1

void pthread_exit(void *retval);

此外，可以直接return一个void *类型的值结束当前线程。

pthread_join

pthread_join可以通过pthread_获得一个终止线程（通过pthread_exit结束或者return的void*的值）的exit code。

1

int pthread_join(pthread_t thread, void **retval);

pthread_cancel

给一个线程发送一个取消请求。

1

int pthread_cancel(pthread_t thread);

pthread_cleanup_push和pthread_cleanup_pop

线程处理程序，和atexit类似。它们都操作的是thread-cancellation clearn-up handlers的调用栈。当一个thread被cancelled时，自动执行一个clean-up handler函数。
pthread_clean_push将一个清理函数routinepush到clean-up hanlers栈的最上面，当routine随后被调用的时候，传递arg参数给它。
pthread_clean_pop从clean-up栈的栈顶将routine移除，如果execute位不为0的话执行它。

在以下情况下，一个cancellation clean-up handler从栈中弹出，并执行：

1. 一个thread被canceled，弹出所有clean-up handlers。
2. 一个thread被调用pthread_exit终止，弹出所有的clearn-up handlers。
3. 一个thread调用pthread_clean_push，并且参数excute为非0值，弹出栈定的clean-up handlers。

总结

pthread_create,pthread_exit和pthread_join它们的void *类型的参数可以传递的值不止一个，还可以传递结构的地址，但是需要注意的是，这个结构所在的内存在调用者完成调用之后必须还是有效的（如果是当前线程在栈上分配的内存的话，返回值这个地址就无效了）。

参考文献

1.《APUE》第三版
2.https://stackoverflow.com/questions/4742196/advantages-of-using-condition-variables-over-mutex

主机（端系统）

各种终端设备，笔记本，手机，等等。

通信链路和分组交换机(packet switch)

端系统通过通信链路和分组交换机连接在一起。
路由器和链路层交换机都是分组交换机。

公共因特网

公共因特网是指一个特定的网络，通常被称为因特网。

因特网服务提供商(ISP)

主机通过Internet Service Provider(ISP)接入因特网，ISP提供的是链路接入，不提供内容。

协议(Protocol)

定义了在两个或者多个通信实体之间交换报文的格式和次序，以及在报文传输/接收或其他方面上所采取的动作。

传输控制协议(TCP)

Transmission Control Protocol，

网际协议(IP)

Internet Prococol，定义了在路由器和端系统中发送和接收的packet的格式。

RFC(Request For Comment)

RFC是一个标准文档，其中包含很多协议的制定。

分组(packet)交换

应用程序之间叫交换报文(message)，通常源主机会将message划分为更小的分组(packet)。在源主机和目的主机之间，每个packet都通过通信链路和packet交换机传送。

存储转发传输和输出缓存

多数分组交换机在链路的输入端使用存储转发传输(store-and-forward-tranmission)，在交换机开始向输出链路传送该packet的第一个bit之前，它必须接收到整个packet。这个过程存在一个存储转发时延。
每个交换机都有多条链路和它相连，对于每条相连的链路，这个分组交换机有一个输出缓存(output buffer)，也叫输出队列(output deque)，用于存放路由器准备发往的那条链路的packet。如果这个输出链路被其他packet占用了，这个packet需要等待。这个过程存在一个排队时延。

这些时延的变换和网络用塞水平相关，如果输出缓存满了，就会出现丢包(packet loss)。

时延

除了存储转发时延（传输时延），排队时延，还有节点处理时延，和传播时延，这些时延加起来是节点总时延。

TCP/IP模型

应用层
传输层
网络层
网络接口层

五层因特网协议栈

应用层
传输层
网络层
链路层
物理层

七层ISO OSI参考模型

应用层
表示层
会话层
运输层
网络层
链路层
物理层

应用层

应用层的信息分组被称为报文（message）。
常见的如FTP, SMTP, HTTP。

运输层

运输层的信息分组被称为报文段（segment）。
两个运输层协议：TCP和UDP。
运输层提供了在应用程序之间传送报文段的服务。

网络层

网络层的信息分布被称为数据报（datagram）。
IP。
将数据报从一台主机移动到另一台主机。

链路层

传输的是帧（frame）。
链路层的任务是将帧从一个网络元素移动到邻近的一个网络元素。

物理层

物理层传输的是比特（bit）。
物理层的任务是将比特从一个节点移动到下一个节点。

报文，报文段，数据报，帧

应用层叫报文。
运输层叫报文段。应用层报文加上运输层的附加信息就得到了报文段。
网络层叫数据报。运输层报文段加上网络层的附加信息得到数据报。
链路层叫帧。网络层数据报加上链路层的附加信息就得到了帧。
物理层是比特。
当然实际上，并不是一个上层的报文对应一个下层的封装后的报文，上层的报文可能被拆分成多个底层的报文。
如下图所示，路由器实现了协议栈的网络层，链路层和物理层，而分组交换机只实现了链路层和物理层，主机实现了五层协议栈的所有层。

套接字

套接字是一个同一台主机内应用层和网络层之间的接口。由于套接字是在网络上建立网络应用程序的可编程接口，所以也把套接字称为应用程序和网络之间的应用编程接口。

参考文献

1.《计算机网络自顶向下》

简介

参考文献

1.《UNP》第三版卷一

概念

• 协议protocol
• 守护进程daemon
• 客户端client
• 服务端server
• 异步回调asynchronous callback
• 应用协议，应用层
• 传输控制协议TCP，传输层
• 用户数据报协议UDP，传输层
• 网际协议IP，网络层，就是IPv4和IPv6。
• 以太网协议Internet protocol，数据链路层
• 局域网local area network
• 广域网wide area network
• 因特网Internet，最大的广域网

参考文献

1.《UNP》第三版卷一

Standard Template Library

STL，是标准模板库(Standard Template Library)的简称。除此之外，还会有C++ 标准库(C++ Standard Library)。C++ 标准库包含STL，STL和其他一些内容共同组成了C++ 标准库。
STL有六大部件：

• 容器(Containers)
• 分配器(Allocators)
• 算法(Algorithms)
• 迭代器(Iterators)
• 适配器(Adapters)
• 仿函式(Functors)

容器

容器分为两类，一类叫做顺序容器，一类叫做关联容器，关联容器又可以分为有序和无序的关联容器。
关于容器的详细介绍，可以查看。

分配器

算法

适配器

迭代器

仿函式

迭代器

C++ 定义了许多容器，包括vector，list，map等等，这些容器中，只有少部分支持[]运算符，其他的都不支持，为了访问这些容器，C++ 提供了迭代器访问这些容器，迭代器和指针类似，提供了对对象的间接访问。
注意string不是容器，但是它支持很多和容器类型的操作。

迭代器和其他组件之间的关系

STL的核心思想，将数据容器和算法分开，彼此独立设计，然后再将他们组合在一起。
算法不依赖于容器，所以就不同的容器就可以使用同一个算法，迭代器就起到让不同的容器使用同一个算法的作用，相当于提供了一个统一的接口。
虽然算法不依赖于容器，但是它依赖于迭代器指向元素的类型。所以这也是为什么要有itreator_traits的原因，给出一个容器的迭代器，算法能够从中获得迭代器指向元素的类型。
iterator_traits的作用，STL的advance操作，对于不同的迭代器，可以使用不同的版本，如果没有iterator_category这个类型的话，只有在执行器进行判断（影响效率），可以利用iterator_traits实现重载。（或者总结一下，实现模板参数相同情况下的重载。）

迭代器范围

所有容器都支持迭代器，通过解引用迭代器访问容器中的元素。一个迭代器范围由一对迭代器构成，两个迭代器分别指向同一个容器中的元素或者是尾元素之后的位置，通常一个被称为begin，一个被称为end。如何获取迭代器：
- c.begin()和c.end()，返回指向c的首元素和尾后元素的迭代器
- c.rbegin()和c.rend()，返回指向c的尾元素和首元素之前的反向迭代器
- c.cbegin()和c.cend()，返回指向c的首元素和尾后元素的const_iterator
- c.crbegin()和c.crend()，返回指向c的尾元素和首元素之前的const_reverse_iterator

当`auto`和`begin`，`end`结合使用时，获得的迭代器类型依赖于容器的类型。只有当容器本身是const时，才能够得到`const_iterator`。

而auto和cbegin和cend使用时，获得的迭代器类型和容器类型无关，一直都是const_iterator。

和迭代器相关的类型

迭代器有const和非const之分。此外，大多数容器还提供反向迭代器，两个类型相减得到difference_type类型。它们通过如下方式定义：

1
2
3
4
5
6
7

vector<int>::iterator it;   //非const迭代器，可读和可写
string::iterator it2;

vector<int>::const_iterator it3;    //const迭代器，只是可读
vector<int>::const_iterator it4;

vector<int>::difference_type count;

begin和end获得迭代器

拥有迭代器的类型（string和容器等）也拥有返回迭代器的成员函数，如begin和end，begin返回指向容器第一个元素或string第一个字符的迭代器，而end返回容器或者string的最后一个元素的下一个位置，是一个根本不存在的元素，通常把这个迭代器称为尾后迭代器。
如果容器（string)为空，begin和end返回的是同一个迭代器，都是尾后迭代器。
如果对象是常量，begin和end返回const_iterator，否则返回iterator。
而cbgein和cend无论对象是否是常量，都返回const_iterator。

迭代器失效

1. 范围for语句会使迭代器失效
2. 任何一种可能改变vector对象容量的操作，如push_back，都会使得vector对象的迭代器失效。

迭代器运算符

迭代器支持的运算有：

• *iter，表示返回迭代器iter所指元素的引用
• iter->num，解引用iter并且获得该元素中名为num的成员，等价于(*iter).mem，即箭头运算符把解引用和成员访问两个操作结合在了一起。
• ++iter，让iter指向容器中的下一个元素
• --iter，让iter指向容器中的上一个元素
• iter1==iter2
• iter1!=iter2，判断两个迭代器是否相等，即是否指向同一个元素或者指向同一个容器的尾后迭代器。

注意，forward_list没有--操作。
尽量使用!=而不是使用<，因为所有的标准容器和string都定义了==和!=，而只有部分容器和string定义了<，所以==和!=是比较通用的。

解引用和成员访问操作相结合

1
2

(*it).empty()
it->empty()

迭代器运算

vector和string, deque和``的迭代器提供了更多的运算符，这些运算被称为迭代器运算。如下所示：

• iter+n
• iter-n
• iter+=n
• iter-=n，
• iter1-iter2，
• >, >=, <=, <

iter1-iter2是两个迭代器之间的距离，iter和iter2必须是同一个容器中的迭代器。可以使用这些运算符进行二分搜索。

insert iterator

iostream iterator

reverse iterator

move iterator

迭代器是一种智能指针

迭代器是一种智能指针，而指针最常见的成员访问和解引用操作，迭代器一定要实现，所以迭代器一定要重载这两个运算符。
为什么每一个STL容器都要有一个专属迭代器？将容器的实现细节封装起来，不被使用者看到。比如说list节点中的next指针，在设计迭代器的时候就会暴露出来，而我们实际上使用list时，并不会知道next指针。

迭代器相关的类型

在使用迭代器的时候，可能会用到迭代器指向对象的类型，比如算法中声明一个迭代器指向对象类型的变量。
而我们不能直接获得一个对象的类型，比如find：

1
2

template<typename InputIterator, class T>
InputIterator find(InputIterator first, InputerIterator last, const T&value);

在find中，我们想要声明一个InputIterator指向类型的变量（不一定是T!!!它们没关系，可能碰巧一样）。怎么做到？函数模板的参数推导？可以做到，但是需要做一个转换。
如果要用InputIterator指向的类型作为返回值类型怎么办？
这样子很麻烦，而且常用的类型有以下五种：

1. value type
2. pointer
3. reference
4. difference type
5. iterator_category

需要一个更全面的方法。

Traits

使用Traits来获得上面介绍的五种类型！
traits是怎么被发明的呢？一步一步来？
如果想要获得迭代器指向对象的类型，最直接的想法是声明内嵌：

1
2
3
4
5
6
7

template <typename T>
class MyIter
{
public:
    typedef T value_type;   //类型声明

};

其他人想要使用迭代器指向对象的类型时，可以使用以下方式进行访问：

1
2

template <typename I>
typenme I::value_type func(I ite);

在使用的时候，要加上typename，因为I是一个模板参数，I::value_type到底是个类型，成员函数，还是数据成员。加上typename告诉编译器这是一个类型。
**但是并不是所有迭代器都是class type，比如说指针也是迭代器，但是它不是类类型，所以就没有办法为它定义内嵌类型，但是STL必须能够把指针当做迭代器。**这时就可以使用偏特化（个数的偏，类型的偏）解决问题，比如：

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

template<typename I>
struct iterator_traits
{
    typedef typename I::value_type value_type;
}

// 注意这里为什么加上const，如果不加const，会推导出顶层const，使得我们声明的变量，无法被修改。
template<typename I>
struct iterator_traits<const I*>
{
    typedef typename I value_type;
}

// I可以是指针，也可以是迭代器。。。
template<class I>
typename iterator_traits<I>::value_type func(I ite)
{
    return *ite;
}

最常用的迭代器的类型有五种：value_type, reference, pointer, difference_type，iterator_category。如果要定义我们自己的迭代器，最好要定义这五个类型，这样子能够和算法相结合。

1
2
3
4
5
6
7
8
9

template<typename T>
struct iterator_traits
{
    typedef T::value_type value_type;
    typedef T::pointer pointer;
    typedef T::reference reference;
    typedef T::difference_type difference_type;
    typedef T::iterator_category iterator_category;
};

此外，需要对指针和指向常量的指针进行偏特化。

value_type

迭代器指向对象的类型。

difference_type

表示两个迭代器之间的距离。

reference

如果C++函数要返回左值，需要返回引用。

pointer

1
2
3

// Item &是引用，而Item*是指针。
Item& operator*() const {return *ptr;}
Item* operator->() const {return ptr;}

iterator_category

根据迭代器的移动特性和操作，可以把它们分成五类：

• 输入迭代器，不允许外界改变，只读。
• 输出迭代器，只写
• 前向迭代器，允许读写操作。
• 双向迭代器，可双向移动。
• 随机访问迭代器，随机存储。

这五种迭代器之中，支持的指针算术运算的能力不同。前三种支持operator++，第四种还支持operator–，第五种涵盖了所有指针运算p+n, p1 < p2，p[n]等。
如果算法中能使用上面层次中的迭代器，那么下面层次中的迭代器也一定能使用，但是效率不一定最好，这里说的效率不一定最好，指的是下层迭代器本来可以访问的更快，偏偏让它一步一步走。所以有一些函数会针对于每一类迭代器实现一个版本，然后根据iterator_category调用相应的版本。
为什么要定义这个类型？因为我们想要根据不同的迭代器类型，判断要执行哪个函数，而且不是运行期执行判定，而是编译器判断！！！这样速度快。通过引入几个空的类型tag，让编译器可以进行识别，从而根据函数重载调用相应的函数。
**为什么用类定义迭代器的分类标签？**一方面可以促成重载机制的成功运作，执行重载解析，另一方面不用再写做传递调用的函数。

STL的算法以它能接受的最低阶的迭代器类型，为迭代器类型参数命名。

继承iterator类

为了确保所有编写的迭代器都能有这个类型定义，和STL其他组件兼容，可以让新设计的迭代器继承iterator类。
这个类除了类型定义之外，没有任何其他操作。此外，还需要继承一个类型的tag。

__type_traits

__type_traits前面加了双下划线，SGI使用双下划线前缀表示这是SGI STL内部使用的东西，不在标准范围内。
iterator_traits萃取了迭代器的特性，而__type_traits萃取type的特性，比如这个type是否有non-trivial的构造，拷贝构造，拷贝赋值，和析构函数。如果没有这些non-trivial的操作，就可以采取最有效的策略（比如不调用那些函数，直接进行内存操作），获得最高的效率。
编译器只有面对class object形式的参数时，才会做参数推导。

参考文献

1.《C++ Primer第五版》