stl源码剖析

发表于 更新于 分类于

使用一个东西，却不明白它的道理，不高明！

C++Standard Library vs. Standard Template Library

C++ Standard Libaray是C++ 标准库

Standard Template Library是STL，标准模板库

标准库以header files形式呈现

  • C++标准库的header files不带副档名（.h）（文件扩展名extension filename）例如 #include <vector.>//忽略.
  • 新式C header files 不带有副档名.h，例如#include<cstdio.>//忽略.
  • 旧式的C header files（带有复文档名.h）仍然可用，例如#include<stdio.h>
  • 新式headers内的组件封装在namespace“std”
  • ->using namespace std;//完全打开
  • -> using std::cout;//部分打开
  • 旧式的头文件内的组件不被封装在namespace “std”里

STL六大部件

与面向对象的设计方式不同，oo是将数据以及函数都放在类里

  • 容器（Contaniners）：容器负责处理将数据放在内存里
  • 分配器（Allocators）：支持容器
  • 算法（Algorithms）：操作数据
  • 迭代器（Iterators）：作为算法操作容器的桥梁，泛化的指针
  • 适配器（Adapters）：可以将容器、仿函数、迭代器做一些转换
  • 仿函数（Functors）：作用像函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<vector>
#include<algorithm>
#include<functional>
#include<iostream>
using namespace std;
int main()
{
    int ia[6]={27,210,12,47,109,83};
    vector<int,allocator<int>>vi(ia,ia+6);//vector是容器，allocator是适配器（如果不写，编译器会写一个默认的），正常第二个大多数人不会这样写，vector是一个模板需要指定类型，allocator也是，所以后面尖括号要写类型
    //vector后面跟了一个变量（对象），初始方法有很多（要查手册），现在vector里有六个元素了
    cout<<count_if(vi.begin(),vi.end(),//algorithm（算法）count_if作用是给他一个条件，判断有几个元素符合条件
                   					//基本所有的元素都有begin和end函数，获得头和尾泛化指针iterator
                 noti(bind2nd(less<int>(),40)));//adapter（适配器） bind2nd绑定第二参数，仿函数less<int>判断两个整数类型的数据是否满足小于的关系，满足返回ture，反之返回flash，经过adapter（适配器）之后变为比较和40的大小。
    //在这些之前又加了not1（not one）否定的意思
    //所以整个语句的判断的条件是大于等于40
    return 0;
}

“前闭后开”区间

指标准库规定，begin指向头第一个元素，end的泛化指针指向的是最后一个元素的下一个位置

不一定是连续的空间（链表之类）

注意结尾尾处end打了个叉，表示的是这里取出的地址并不是容器里的最后一个地址，这是危险的操作。

1
2
3
4
5
6
//遍历
Container<T> c;//随便哪个容器都可
...//一些元素
Contaniner<T>::iterator ite=c.begin();//每一个容器都有它的iterator（泛化指针）
for(;itr!=c.end();++ite)//这就是泛化指针的用处，可以将不连续的空间视为连续的来使用，我是这样理解的
    ...

range-based for statement(since C++11)

C++的一个版本

1
2
3
4
//示例
for (decl:coll){//decl是声明，coll是容器（集合体）,decl类似引用，是一个别名，只是类似
    sattement
}
1
2
3
for(int i:{2,3,5,7,9,13,17,19}){//c++11的新语法，可以在后面放所有stl的容器
    std::cout<<i<<std::endl;
}//这个操作就可以把他们依次输出
1
2
3
4
5
6
7
8
9
10
//实例
std::vector<double>vec;
...
for(auto elem:vec){//这个auto是新规定的，它的作用等同于Contaniner<T>::iterator（上面的例子）但是他为了书写方便，让编译器来推导这里需要什么类型
    //但是并不建议所有的类型都用auto来写，不是一个好习惯，熟悉每一种类型是程序员应该知道的
    std::cout<<elem<<std::endl;
}
for(auto& elem:vec){//这里加了引用，为了下面的计算会作用到原本数据
    elem*=3;
}

auto keyword（since C++11）

1
2
3
4
list<string> c;
...
list<string>::iterator ite;
ite=find(c.begin(),c.end(),target);

用了auto之后

1
2
3
list<string>c;
...
auto ite=::find(c.begin(),c.end(),target);//编译器会根据等号右边，判断出左边也是这种类型，目前我还看不懂这是啥

容器–结构与分类

Sequence Containers循序容器

Array数组前后封口

Vector向量，后端开口，可增长

Deque双向队列，两端可进可出

List链表，每一个元素不一定连续，用指针连接（双向的）

Foward-List单向链表

List一定比Foward-List占用内存多

Associative Containers关联容器（有一个key和数据，查找时快）

Multi表示多，选择使用set/map表示key不能重复，而选择Multiset/Multimap则可以重复使用key

Set/Multiset叫集合（但是不是集合）：它的key就是value，value就是key

Map/Mutimap：它的每个元素会有两个部分，一个key与一个value

例如要统计学校学生信息，建议选择map，将学号或身份证号作为key，住址电话之类作为value

两个内部都是由红黑树写的（未规定用什么来实现，但是它很好用）

红黑树：高度平衡二分树，他会自动的分配，让两侧的长度基本相同，这样在查找的时候就不会出现一边特别长的情况

Unordered Containers（是一种关联式容器）不定序容器（元素没有次序，可能会改变）

Unordered Set/Multiset

Unordered Map/Multimap

元素是分散的，所使用的数据结构叫做HashTable

目前最好的C++在用的叫Separate Chaining

它是一个有一排篮子的数据结构（我们暂时称它为篮子），每个篮子里有多少个元素，要看它后面指针指向的链表有多少个元素，一个篮子对应一个链表

hashtable的故事：最开始，有二十个存储位置，有abced元素，他们经过一些计算决定，a放在第三个位置，b也要放在第三个位置，那么，就会发生碰撞，这是我们不想看到的，所以人们设计了一些函数来分开碰撞的元素，但是这很麻烦，最终演变成Separate Chaining，即碰撞在一起的就做成链表。

在进行二分查找之前一定要进行排序否则不可以，很好理解没排序数据是无序的，没办法进行二分查找

测试程序的编写的一些建议：

对于一种容器的测试的代码写在一起，当然所有的测试程序放在一个里，不然测试有些麻烦，多使用namespace来写测试程序。将测试本容器所需要include的头文件放在测试代码上方，这会导致重复引入，但是没有关系，头文件有防卫式声明。这会方便你查看这个测试代码用到了哪些库。

定义声明变量，在你要使用它的时候再去定义，突排的方式（好找）

用于测试代码的编写方式

vector

vector的增长方式：长度不够时，扩充方式是两倍增长，例：一开始是0，放一个，分配器分配一个空间，再放第二个时，一个变两个，再放第三个时，两个变四个当放到第五个时，四变八。

注意翻倍不一定是在这个位置成长两倍，它一定要在一个有这么大的空间去成长为两倍，然后再把原来的数据一个一个的放进去。这个过程很缓慢

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <vector>
#include <stdexcept>
#include <string>
#include <iostream>
#include <ctime>
#include <cstdio>   // snprintf()
#include <cstdlib>  // abort()
#include <algorithm>

#include "pub.h"

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::exception;
using std::find;

namespace jj02
{
	void test_vector(long& totalCount)
	{
		cout << "\ntest_vector()......... \n";

	    vector<string> c;
	    char buf[10];
		//srand((unsigned)time(NULL));
	    clock_t timeStart = clock();
		for (long i = 0; i < totalCount; ++i) 
		{
		    try {//try catch防止发生申请不到内存的情况
			snprintf(buf, 10, "%d", rand() % 65535);
			c.push_back(string(buf));//这里是获取尾部，填充字符串，存的是指针
		    } catch(std::exception& e) {

			cout << "i=" << i << e.what() << endl;
			// 曾经最高 i=58389486 then std::bad_alloc/
			abort();//发生异常退出程序
		    }
		}

		cout << "milli-seconds:" << (clock() - timeStart) << endl;
		cout << "vector.size()= " << c.size() << endl;//返回内部真正的元素个数
		cout << "vector.front()= " << c.front() << endl;
		cout << "vector.back()= " << c.back() << endl;
		cout << "vector.data()= " << c.data() << endl;
		cout << "vector.capacity()= " << c.capacity() << endl;//返回它申请的空间个数

	    string target = get_a_target_string();//问寻找哪一个字符串
		{//这里是第一次查找，循序查找
		timeStart = clock();
	    auto pItem = ::find(c.begin(), c.end(), target);//这里用了auto，原本类型应该是iterator
		cout << "::find(), mill-seconds: " << (clock()-timeStart) << endl;//输出特地加了：：来表示全局函数

		if (pItem != c.end())
		    cout << "found, " << *pItem << endl;//找到了，输出的内容是通过寻找返回的地址输出出来的
		else
		    cout << "not found! " << endl;
		}	

		{//这里进行了第二次查找
		timeStart = clock();
		
		sort(c.begin(), c.end());//进行了排序，为下面二分查找做准备，c++提供的
		
	    string* pItem = (string*)bsearch(&target, (c.data()), c.size(), sizeof(string), compareStrings);//bsearch（binary search）二分查找，这个是c就有的
		cout << "sort()+bsearch(), milli-seconds: " << (clock() - timeStart) << endl;
		
		if (pItem != NULL)
			cout << "found, " << *pItem << endl;
		else
			cout << "not found!" << endl;
		}
	}
}

结果是循序查找比二分查找更快，因为二分查找要先排序，sort用的时间比较多。

list

使用方法

1
2
3
4
5
6
7
#include<iostream>
#include<list>
using namespace std;
int main() {
	list <int> mylist(10);
    return 0;
}

开辟出来的内容都是0

1
2
3
4
5
6
7
8
9
#include<iostream>
#include<list>
using namespace std;
int main() {
	//list <int> mylist(10);
	int ar[10] = { 0,1,2,3,4,5,6,7,8,9 };
	list<int> mylist(ar, ar + 10);//这里的意思是从ar到ar+10，作为初始化链表的内容，ar是从0开始索引的，ar+10对应的应该是第十一个元素
	return 0;
}

因为前闭后开的特性，不包括终止迭代器指向对元素，当将代码修改为

1
list<int> mylist(ar, ar);

时

链表为空

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
#include <list>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <algorithm> //find()
#include <iostream>
#include <ctime> 
namespace jj03
{
void test_list(long& value)
{
	cout << "\ntest_list().......... \n";
     
list<string> c;//创建一个string类型的链表
char buf[10];
			
clock_t timeStart = clock();							
    for(long i=0; i< value; ++i)
    {
    	try {//这个try防止分配不到内存
    		snprintf(buf, 10, "%d", rand());
        	c.push_back(string(buf));    	
		}
		catch(exception& p) {
			cout << "i=" << i << " " << p.what() << endl;	
			abort();
		}
	}
	cout << "milli-seconds : " << (clock()-timeStart) << endl;		
	cout << "list.size()= " << c.size() << endl;
	cout << "list.max_size()= " << c.max_size() << endl;    //357913941，不同电脑不一样，这个会在后面说为啥会有最大值
	cout << "list.front()= " << c.front() << endl;	
	cout << "list.back()= " << c.back() << endl;		
		//下面是开始查找
string target = get_a_target_string();		
    timeStart = clock();		
auto pItem = ::find(c.begin(), c.end(), target);//find是标准库的循序查找,前面有::表示全局
	cout << "std::find(), milli-seconds : " << (clock()-timeStart) << endl;		
	
  	if (pItem != c.end())
    	cout << "found, " << *pItem << endl;
  	else
    	cout << "not found! " << endl;	
    	
    timeStart = clock();		
	c.sort();//这里用的sort排序算法是自己写的，当一个容器自己带了一个sort时，当然要用自带的，比较快	
	cout << "c.sort(), milli-seconds : " << (clock()-timeStart) << endl;		    	
    	
	c.clear();
	test_moveable(list<MyString>(),list<MyStrNoMove>(), value);								
}	
}

forward_list

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
#include <forward_list>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime> 
namespace jj04
{
void test_forward_list(long& value)
{
	cout << "\ntest_forward_list().......... \n";
     
forward_list<string> c;  	
char buf[10];
			
clock_t timeStart = clock();								
    for(long i=0; i< value; ++i)
    {
    	try {
    		snprintf(buf, 10, "%d", rand());
        	c.push_front(string(buf));//前面都是push_back,它是push_front，而且它没有push_back	//似乎它的front是变化的，所以只提供了简单的方法
		}
		catch(exception& p) {
			cout << "i=" << i << " " << p.what() << endl;	
			abort();
		}
	}
	cout << "milli-seconds : " << (clock()-timeStart) << endl;	
	cout << "forward_list.max_size()= " << c.max_size() << endl;  //536870911
	cout << "forward_list.front()= " << c.front() << endl;	//不提供最后一个元素，因为很慢，单向的


string target = get_a_target_string();	
    timeStart = clock();			
auto pItem = ::find(c.begin(), c.end(), target);//还是标准库的循序查找（觉得不太对，标准库的find怎么什么类型都能找，或许写了重载）
	cout << "std::find(), milli-seconds : " << (clock()-timeStart) << endl;		
	
	if (pItem != c.end())
    	cout << "found, " << *pItem << endl;
  	else
    	cout << "not found! " << endl;	
    	
    timeStart = clock();		
	c.sort();//这个是自带的排序，后面没写查找		
	cout << "c.sort(), milli-seconds : " << (clock()-timeStart) << endl;		
	
	c.clear();	 
}											 
}

slist

这个也是单项链表，和forward_list一样，区别在于，slist是devc++外挂的一个非标准的库，而forward_list是c++11规定的

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
#include <ext\slist>//这个表示的是这个库在ext文件夹下的
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime> 
namespace jj10
{
void test_slist(long& value)
{
	cout << "\ntest_slist().......... \n";
     
	__gnu_cxx::slist<string> c;  	
	char buf[10];
			
    clock_t timeStart = clock();								
    for(long i=0; i< value; ++i)
    {
    	try {
    		snprintf(buf, 10, "%d", rand());
        	c.push_front(string(buf));     		
		}
		catch(exception& p) {
			cout << "i=" << i << " " << p.what() << endl;	
			abort();
		}
	}
	cout << "milli-seconds : " << (clock()-timeStart) << endl;			
}															
}

deque

队列是一个连续的前后开口的容器

在说向量vector的时候说过，他在成长的时候是二倍增长而且需要换位置，那deque队列是怎么做到连续的呢。

其实队列也是不连续的，只是伪装成连续的供用户使用

看下面这张图，是deque的结构

队列是由许多段（buffer）构成的，每个段多大后面说，当iterator泛化指针++后“走到悬崖边”时，它会自动跳到下一个段，怎么跳的，用的++，运算符重载，还是后面说。

这样整个deque就时有序的了

当buffer不够用时，deque就会再分配一个buffer。

对比其他的容器

array数组不可增长，vector向量二倍增长（不完全是）会造成很大的浪费，list链表每次扩充会增长一个结点 ，但是查找慢

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
#include <deque>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime> 
namespace jj05
{
void test_deque(long& value)
{
	cout << "\ntest_deque().......... \n";
     
deque<string> c;//string类型的deque
char buf[10];
			
clock_t timeStart = clock();								
    for(long i=0; i< value; ++i)
    {
    	try {
    		snprintf(buf, 10, "%d", rand());
        	c.push_back(string(buf));//先转成字符串再存入 			 		
		}
		catch(exception& p) {
			cout << "i=" << i << " " << p.what() << endl;	
			abort();
		}
	}
	cout << "milli-seconds : " << (clock()-timeStart) << endl;		
	cout << "deque.size()= " << c.size() << endl;
	cout << "deque.front()= " << c.front() << endl;	
	cout << "deque.back()= " << c.back() << endl;	
	cout << "deque.max_size()= " << c.max_size() << endl;	//1073741821	
	
string target = get_a_target_string();	
    timeStart = clock();			
auto pItem = ::find(c.begin(), c.end(), target);//用全局的	
	cout << "std::find(), milli-seconds : " << (clock()-timeStart) << endl;	
	
	if (pItem != c.end())
    	cout << "found, " << *pItem << endl;
  	else
    	cout << "not found! " << endl;	
    	
    timeStart = clock();		
	::sort(c.begin(), c.end());//使用的是全局的sort，他自己没写
	cout << "sort(), milli-seconds : " << (clock()-timeStart) << endl;		
	
	c.clear();
	test_moveable(deque<MyString>(),deque<MyStrNoMove>(), value);		 						
}															
}

stack&queue

栈和堆（但是我记得堆是heap）

他俩是依靠deque为底层支持的容器

stack

deque和stack的结构

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
#include <stack>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime> 
namespace jj17
{
void test_stack(long& value)
{
	cout << "\ntest_stack().......... \n";
     
stack<string> c;  	
char buf[10];
			
clock_t timeStart = clock();								
    for(long i=0; i< value; ++i)
    {
    	try {
    		snprintf(buf, 10, "%d", rand());
        	c.push(string(buf));//放元素是push			 		
		}
		catch(exception& p) {
			cout << "i=" << i << " " << p.what() << endl;
			abort();
		}
	}
	cout << "milli-seconds : " << (clock()-timeStart) << endl;	
	cout << "stack.size()= " << c.size() << endl;
	cout << "stack.top()= " << c.top() << endl;	
	c.pop();//这里用pop出栈一次
	cout << "stack.size()= " << c.size() << endl;
    cout << "stack.top()= " << c.top() << endl;
}
}

queue

结构比较，queue是先进先出，一端进一端出。

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
#include <queue>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime> 
namespace jj18
{
void test_queue(long& value)
{
	cout << "\ntest_queue().......... \n";
     
queue<string> c;  	
char buf[10];
			
clock_t timeStart = clock();								
    for(long i=0; i< value; ++i)
    {
    	try {
    		snprintf(buf, 10, "%d", rand());
        	c.push(string(buf));//也是push 			 		
		}
		catch(exception& p) {
			cout << "i=" << i << " " << p.what() << endl;
			abort();
		}
	}
	cout << "milli-seconds : " << (clock()-timeStart) << endl;	
	cout << "queue.size()= " << c.size() << endl;
	cout << "queue.front()= " << c.front() << endl;	
	cout << "queue.back()= " << c.back() << endl;		
	c.pop();//也是pop
	cout << "queue.size()= " << c.size() << endl;
	cout << "queue.front()= " << c.front() << endl;	
	cout << "queue.back()= " << c.back() << endl;	
}
}

上面两种容器其实从技术上来说属于容器适配器（container adapters），叫容器也可以

betset

位图

每个元素只能是0或1

1
2
3
4
5
6
7
8
9
10
11
#include<iostream>
#include<bitset>
using namespace std;
int main(){
    bitset<10> bt;
    cout<<bt<<endl;
    cout<<size(bt)<<endl;
    cout<<sizeof(bt)<<endl;
    cout<<bt.count()<<endl;
    return 0;
}

默认的初始化都是0

size是大小，10

bt.count()是查找里面几个1

set

高效检索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<set>
using namespace std;
int main(){
int ar[]={12,23,54,233,45,323,56};
set<int> s;
for(int i=0;i<sizeof(ar)/sizeof(int);++i){
    s.insert(ar[i]);
}
set<int>::iterator it=s.begin();
    while(it!=s.end()){
        cout<<*it<<" ";
        ++it;
    }
    cout<<endl;
    return 0;
}

可以看到输出的是排好序的

set是在插入的时候就排好序的，还有去重

multiset

排序，可以重复

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<set>

using namespace std;
int main() {
	int ar[] = { 12,12,12,45,414,66,23,65,87 };
	multiset<int> s;
	for (int i = 0; i < sizeof(ar) / sizeof(int); ++i) {
		s.insert(ar[i]);
	}
	multiset<int>::iterator it = s.begin();
	while (it != s.end()) {
		cout << *it << " ";
		++it;
	}
	cout << endl;

	cout << "count = " << s.count(12) << endl;

	return 0;
}

s.count(12)查看12的数量

OOP(Object-Oriented programming) vs. GP(Generic Programming)

OOP企图将datas和methods关联在一起

为什么list不能使用::sort()（全局的sort，算法库里的sort）排序？

看图片，::sort()需要的iterator要满足可以加减除运算的指针，这种指针则是需要内存空间连续，换句话说迭代器是随机访问迭代器。

而链表不是连续的，他只能一个一个的移动，因此不满足全局sort的要求，只能使用自己写的sort

在第一讲里也说过如果容器提供了sort，就必须使用自带的sort

GP却是将datas和methods分开来

采用GP：

  • Containers和Algorithms团队可各自“闭门造车”，其间以Iterators贯通即可。

    标准库源码

    min函数依靠<来比较，有时会需要类里对<进行重载

  • Algorithms通过Iterators确定操作范围，并通过Iterators取用Container元素

所有algorithms，其内最终涉及元素本身的操作，无非就是比大小。

图片中写了两种max函数

一种是默认的就是上面的max

第二种多了一个参数，参数是执行的动作，比较大小还有啥动作呢？

有的，此处以字符串为例，函数上方就是测试程序

第一次测试就是常用的依次比较字符大小，返回的就是zoo

第二次测试多加了一个strLonger参数，调用的就是第二种max函数，意思是比较两字符串的长度，返回的是hello

操作符重载和类模板的复习

Operator Overloading，操作符重载

有四个操作符不可以被重载(需要时找，不用记)

::,.,.*,?:

不全写了就

Class Templates ，类模板

Function Templates,函数模板

右侧上方定义了min函数，且使用了模板的方式

整个调用流程：

左侧上方程序调用了min函数，编译器会进行实参推导，推导出参数的类型是石头（设计的类），去调用石头类的min函数，进入函数后，在<处会去找是否对<进行了重载，找到也就是左侧下方的函数。

Member Templates，成员模板

有这个类，很复杂，我们不会遇到。。。

Specialization，特化

所给的例子本身在做什么事情，现在可以不用去管他

泛化就是正常的类模板，<class T>这个T写什么都可

特化就是一些特殊的情况，当遇到这些情况时，用特化的方法更快或更好，将泛化中的type设置为某一个类型，template<>尖括号里就是空的了。

泛化的hash定义的是空的

图中的__STL_TEMPLATE_NULL是type define 就是template<>

当然特化不止这些

Partial Specialization，偏特化

有人把特化叫做全特化

虽然都是局部特化，偏特化也分种类

一种是左侧这种的个数的偏特化，泛化时尖括号里输入两个东西，而在偏特化中确定了其中一个的类型

另一种是右边的这种的范围的偏特化，右上部分是泛化，可以输入任何的类型，中间部分是当选择的类型是指针的情况，下边部分是指针指向const类型

分配器allocators

学了之后不建议直接使用，因为分配器是分配空间给容器的，我们不需要自己去调用

关于分配的函数最终都可以追溯到malloc

在vc6下的标准库，其allocator部分源码如图

可以直接调用分配器，进行分配内存

1
int *p=allocator<int>().allocate(512,(int*)0);

这句，创建了一个临时对象，用这个临时对象分配内存，对应的是类定义中pointer allocator(size_type _N,const coid*)函数，第二个参数是什么都可以，这里没有细说

在释放内存的时候同样先创建一个临时对象

其他版本的allocator

BC

G2.9

最后一个G2.91是后面将要剖析的源码。

总结以上三版本的allocator的定义，得出他们都是使用了malloc和free进行内存分配的

但是在G2.9的allocator文件里有这样一段注释（图片右下角），他说不要使用这个文件，SGI STL 使用了不同的allocator，这个文件没有被含入到任何其他的地方去。

意思是虽然他写了一个符合标准的分配器，但是它的容器从来不用这个文件

如图所示，使用的分配器的名字是alloc

在之前内存分配处就讲过分配一块内存需要额外分配空间（最重要的是cookie）

在分配给容器内存的时候每个元素都加上cookie，太浪费了

gnuc就从这里入手，尽量减少malloc的使用

它设计了0-15一共十六条链表，分别负责不同大小的内存

从0号链表开始，负责大小是8字节，依次类推第15号链表也就是第十六个链表负责16*8=128字节的内存

对应的，容器在要内存的时候，会根据大小分配对应的内存块，并且容器的大小也会被修改为8的倍数

当链表中没有相应的大小的内存时，allocator才会跟操作系统使用malloc要一大块内存，要来之后进行切割，切出来的内存用单向链表串起来

这里说这个分配器还是有一点缺点，但是这里不说，等到内存分配里说

到了G4.9版本时，使用的分配器不是alloc，而是其他的，这是为什么呢？

会不会是因为之前说的小缺陷呢，制作团队没有说

allocator依靠两个函数allocate和deallocate（一个分配，一个释放）

之前的G2.9版本的alloc可不可以用呢，可以的，G4.9有扩充的allocator，那里有G2.9的alloc，只不过名字变了

不过这个文件不是在std命名空间下的，是在__gnu_cxx下的，直接使用的语法是

1
vector<string,__gnu_cxx::__pool_alloc<string>>vec;

没有文档记载了它的位置，这个是看了源码才知道的

容器，结构与分类

上图是G2.9和G4.9的比较

这张图用缩进的方式介绍了各种容器之间的关系（衍生）

衍生出来的容器使用的是复合而非继承

图中的heap并不是我们说的堆，而是一种容器的名字

rb_tree是红黑树，高度平衡二叉树

G4.9将之前非标准的slist改名为froward_list

在写stl时衍生的容器尽量用复合的方式来写

容器list

看右侧源码

分配器用的是alloc，实际数据只有node这一个，node是什么类型？link_type，这是什么？往上找，程序将list_node*定义为type_link，那list_node又是什么？同样往上找，找到__list_node<T>，再去看这是什么，是一个我们常用的结点类型。

在结构体中，指针的类型被设置为了void*类型，写的不太好，这个虽然能用，但是需要经过转型，正常我们也是把指针写成自己结构体的类型。在G4.9版本中对此处做了修改。

list使用了iterator，可以叫他智能指针，它肯定是一个结构体或者是类，才足以实现模拟指针并达到智能指针的效果。接下来看他是如何使用以及实现的

会有一堆typedef，和一堆的函数（操作符重载函数）

以前置加加和后置加加为例

1
self operator++(int) {self tmp = *this; ++*this; return tmp; }

看到*this以为会调用那个打了×的箭头所指向的重载星号的函数，但是并不是

1
tmp=*this;

这句是一个拷贝构造函数，所以*this已经变成了拷贝构造的参数了

后面的也是同样，后置加加中还调用了前置加加

真的是太仔细了，后置加加的返回值类型不是reference，而前置加加的返回值是reference，为什么呢？

我们重载++这个操作符，要向整数int类型看齐，c++不允许后置加加连续++操作，而允许前置加加进行连续++操作，原因我们不知道，下面是尝试，可以看到有标红报错。

模拟指针还要有提取数据的能力，比如*和->这两个操作符

G4.9相较于G2.9的改进，iterator中的next指针类型改为了结构体的类型，并且在传参数时也从原来的直接传三个变为了传一个而后再生成两个

也有改复杂的地方，以我的水平是看不出这样改有什么好处和坏处，但是能看出比2.9复杂了许多，并且里面的容器类还继承了分配器类，这有点破坏了各部件之间的分离性

G2.9的循环链表，为了达成前闭后开区间的容器，最后一个元素后面还有一个不属于容器的元素

当返回end时就是返回这个还不属于容器的元素

之前比较G2.9和G4.9的时候有，list的大小有变化

从下往上看继承关系，list继承了

1
_List_base<_Tp,_A>

其中有_M_node ,这个里又有两个指针，一个是前，一个是后

而G2.9是一个指针指向一个地方，这个地方是这两个指针

iterator需要遵循的原则

在算要进行一些操作时，需要问迭代器，传过来的迭代器都有哪些性质

以rotate函数为例

函数体

其中包含difference_type和value_type

value_type就是指这个iterator所指向的内容是什么类型

difference_type是指两个iterator之间的距离应该用什么type来表现（int，char，…）

如果使用unsigned integer（无符号整型）那么两个iterator之间最大的距离就是 2的32次方（0~2的32次方-1）

同时调用了标蓝色的函数

其中高亮句返回了iterator_category即iterator的分类

这个分类指的是iterator的移动类型：有的iterator只能一直往前走（只能++），有的iterator还可以–，有的还可以跳着移动（iterator+=3之类）

rotate函数可能是为了了解iterator的分类以便采取最佳的使用方式

从语言表述上来说就是algorithms来提问（iterator的性质），iterator来回答

Iterator必须提供的5种associated types（联系类型）

大多数的difference_type的类型是ptrdiff_t，这个类型是某个头文件的define，暂时不管它

算法在问的时候是怎么问的呢？

类型后加两个冒号再加上要的东西

但是，如果iterator并不是个class呢？例如native pointer（指针，它被视为一种退化的iterator）

算法问问题的时候怎么回答？这时人为制作了Traits（特性、特征、特质）

Traits 特性、特征、特质

人为的萃取机

Iterator Traits用来分离class iterators和non-class iterators

解决计算机问题的尚方宝剑：加一个中间层

对比间接问（使用Traits做中间层）和直接问的提问方式

使用Traits的回答方式：如果是一个class iterators就去问这个迭代器要答案，得到答案再返回给算法；如果是non-class iterators就直接返回这个指针所指向的value的type给算法

对于non-class iterators使用偏特化的方式进行分类

需要注意：类型是T或const T的返回类型都是T，为什么呢？

value_type的主要目的是用来声明变量，而声名一个无法被赋值的变量没什么用，所以iterator（即便是constant iterator）的value type不能加上const。

完整的iterator_traits

各式各样的Traits

总结一下

一个形象的比喻：算法问Traits问题（五个性质），Traits去问iterator，iterator回答Traits，Traits回答算法，如果iterator是一个指针，那么Traits替iterator回答（两种偏特化）

容器

容器vector（可变数组）

假设vector原来有八个，当输入到第九个时，容器会去找另一块两倍于当前数组大小的内存进行”成长“，经过多次两倍大，最后找不到一块两倍大的内存的话容器生命期就结束了。

vector依靠三根指针（起始位置、结束位置（当前）、容器底）来”管理“存储数据。

部分源码：

所以当使用sizeof时，vector的大小就三个指针。

1
2
size_type size()const
{return size_type(end()-begin());}//这里选择了调用end和begin函数来获取指针，不太理解，如果指针是属于私有成员的话可以理解，但是这个是保护成员

如果是有连续空间的（至少人看起来是）容器，就需要重载操作符[]

1
2
reference operator[](size_type n)
{return *(begin()+n);}

因为要像数组一样用，array[i]之类

vector二倍成长的操作

右侧有注释，先判断是否有位置，如果没了就进入else中的函数

会发现这里的判断重复了，这是因为insert_aux(end(),x)这个函数不知应用于此处还用到别的地方，有需要它的情况。

进行元素的拷贝

最开始的位置的三目运算是为了防止容器大小为0的情况

中间绿色框里的不仅复制了安插点之前的元素也复制了安插点之后的元素，因为可能被insert函数调用，那样的话安插点之后也有原来的元素

最后还要释放之前的旧的容器

vector’s iterator

和链表类似，使用traits做中间层。

4.9版本的vector

大小是12（一个指针是4，有3个指针）

4.9版本的vector’iterator

图中的箭头尾端是父类，多重继承的关系，最后

1
_M_curent:_Base::pointer---->_M_current:_Tp*

与2.9版的效果是一样的iterator的类型是*T（模板）

萃取机上面部分是2.9版本，下面部分是4.9版本

容器array

为了array能不独立于六大部件，也对其进行了完善做为容器中的一种，以使其能够得到stl的便利

长度不可变数组，在创建时需指定长度。

TR1（介于c++1.0和c++2.0之间的版本）

注意数组没有构造函数和析构函数

数组的迭代器就是指针，通过萃取机完成对算法的回答

G4.9的版本

容器forward_list

单向链表，和之前的双向链表类似。

容器deque

在C++里说过这个容器，它给使用者一种连续数组的感觉，但是其实不连续。

以buffer（缓冲区）为单位，每个buffer有八个元素位置，这些单位通过iterator组成的vector连起来

deque的iterator是class，其中data有四个：作用分别是：（图中从左到右），指向此iterator对应的buffer中的某一个元素（可以按照偏移量来理解）、指向此iterator对应的buffer的第一个元素、指向此iterator对应的buffer的最后一个元素之后的位置（满足前闭后开）、指向map（所有buffer的vector）

上图是源代码，map是一个二重指针，它指向的元素都是指针（iterator）。

在template处有三个参数，第三个参数的默认参数是0（第三个参数是设置buffer内元素个数的），他咋能是0呢？

看上面的源码和注解，这里用了两个

1
n!=0?n:(sz<512?size_t(512/sz):size_t(1));

n不等于0吗？如果n不等于0返回n

如果n等于0，再问这个元素是否比512字节小？如果元素比512小，返回size_t(512除元素)这里是类型转换，如果元素比512字节大，返回1，同样进行了类型转换。

deque’iterator

deque的迭代器类型是可以跳跃的

deque<T>::insert()

向一个连续存储区域中插入一个元素，部分其他元素就要移动，这样就分向前移动和向后移动了（当前插入位置前后不一样长的时候，尽量选择移动元素数量少的方法）

这页先写了两种简单的情况：插入位置是开始位置和插入位置是结束位置的情况

这页的辅助函数对剩余的情况进行处理，先计算插入位置到头的距离，再将此距离与中点进行比较，小于就是向头部方向进行搬数据，大于就是向尾部进行搬数据，搬完将要插入的数据存到插入位置。

deque 如何模拟连续空间

都是iterator的功效

front函数返回start，back函数返回finish，size函数返回容器长度（尾减头，减号做了重载），empty函数判断容器是否为空。

上图是重载减号的函数，它的计算方式是：先计算buffer规定有多少元素，再去求整个的buffer有几个，两个相乘，再与首尾的不完整buffer中的元素个数进行相加。

对于前置++的重载：先++cur（前置++比较快嘛），为什么这里的cur也是指针却可以++呢？因为cur是指向buffer里的元素的，而buffer是连续的，因此++不会产生错误。再进行判断cur是否到了末尾边界，如果到了就跳至下一块buffer，设置iterator内各种值返回当前iterator，没到边界就不用跳直接返回结束后的iterator。

对于前置–的重载：先判断是否到达起始边界，到达就跳至前一个buffer，设置iterator内各种值，返回当前iterator，没到边界就不跳直接返回当前iterator。

后置++和后置–则是在函数体中调用了前置的函数。

+=的重载：先判断+=之后还在不在当前缓冲区，如果在直接+=就好，如果不在，切换至正确的缓冲区，再切换正确的元素。这里的+=参数可以是负数

所以-=的重载是

在之前说过map是一个vector，vector的增长方式是二倍增长再拷贝数据，map在进行拷贝时他是将数据拷贝到新开辟出来的空间的中间部分，以保证在先前和向后增加缓冲区时方便。

容器queue

它以deque为底层容器禁用了一些deque的功能实现了新的容器，又称适配器。

这是一种复合，在c++用法那篇笔记里有写。

要实现某种功能时就利用底层函数调用其函数实现自己的功能。

容器stack

queue和stack的iterator

他们都没有iterator，因为他们不允许遍历，公认的stack先进后出，queue先进先出，如果允许遍历或者插入就会怕破坏这种性质。

如果此时使用者尝试使用他们的iterator编译器就会报错，说没有这个成员。

queue和stack的底层容器

这两个适配器都可以用list（双向链表）做底层容器，其中stack还可以用vector做他的底层容器，而queue不可。

可以看到使用vector做queue的底层容器时只有pop功能不能正常使用，如果不用编译器是不会报错的，这里给我们提了一个醒，对于模板，只有我们使用时编译器才会帮我们检查是否有问题，我的意思是编译器不会做一个全面的检查。

stack和queue都不可以用set和map做底层容器

容器rb_tree

和目前数据结构学到的平衡二叉树有些像（树本身就排好顺序），在查找和插入的时候很快

不建议我们使用iterator对树上的元素进行修改，那样会破坏树的已经排好序的特性，编程上没有禁止这一点。

红黑树是set和map的底层结构，map允许元素data被改变不允许key被修改。

rb_tree的两种插入：insert_unique():key不能重复（此时如果插入一个已经存在的key什么都不会发生）

insert_equal():key可以重复

对于这节课而言我们规定key+data=value

template模板要求5个参数

1
2
3
4
5
<class Key，//key的类型
 class Value,//value的类型
 class KeyOfValue,//value获取key的方式
 class Compare,//比较的方式
 class Alloc = alloc >//分配器

对于这个class的数据：

1
2
3
4
size_type node_count;//rb_tree中元素个数 		  大小4字节
link_type header;//一个指针指向root      			 大小4字节
Compare key_compare;//key的大小比较原则，是一个仿函数 大小为0字节，但是实际上是1字节
//总字节数 9->12 需填充

左上角的参数中：第三个是value得到key的方式这里是identiity<⁢int>对应代码在左下角，传入什么返回什么

他是一个结构体，其中进行了操作符重载，作用像函数，所以叫它仿函数（但是我觉得重载也是函数啊）

第四个参数的作用是提供比较两个key的大小的规则，本例使用的是标准库的less

上图是一个测试程序，首先创建了一棵树

接着看树是不是空的（返回值1），查看树内元素个数（返回值0），使用insert_unique()插入方式依次插入3、8、5、9、13、5，第二次插入5时无事发生，再次询问树是否为空（返回值0），树内元素个数（返回值5），查询树内key为5的元素个数（返回值1），使用insert_equal()插入方式插入两次5，查看树大小（返回值7），查询树内key为5的个数（返回值3）。

G4.9版本和G2.9版本的变化

在4.9版本中_Rb_tree同样采用了多重继承的关系，学到这里介绍一种oo（面向对象）的一种有名的（我没查到）写法叫做handle body（句柄-身体），这种写法想要实现一中只用一个class这个class中一个指针就能表现这个目标的性质（不知道我说的是否准正确）。

其中三个指针一个color（这个color是枚举，大小是12字节），总共是24字节

chatGPT对于枚举的解释：

1
2
3
4
5
枚举（Enumeration）是一种在编程中用于定义一组有限命名值的数据类型。它允许程序员定义一系列命名的常量，这些常量通常代表一个特定的有序集合
1、提高可读性： 枚举为常量赋予了有意义的名字，这使得代码更易于阅读和理解。相对于使用数字或字符串表示常量，使用枚举可以使代码更加自解释。
2、类型安全： 枚举可以提供一定程度的类型安全，因为它们的取值是预先定义的，而不是任意的数字或字符串。这可以帮助捕获一些常见的错误，如拼写错误或使用未定义的常量。
3、限定取值范围： 枚举可以限定一个变量只能取枚举中定义的值，避免了使用无效或不合理的值。
4、迭代： 枚举可以被迭代，这使得遍历枚举中的所有值变得更加容易。

容器set、multist

set和multiset是key=value的容器，因此他们禁止使用者修改元素值，这样会修改key即破坏了红黑树的排序结构。

图片最下两行指出了这两个容器的区别，即key可不可以重复。

使用set时，对应的参数传递在右侧三个方框

之前说过set设计为不能使用iterator修改元素值，这是怎么办到的？

代码中的rep_type t；就是set底层的红黑树，我们在取itertaor时设置为了const，从而使其无法修改元素值。

set也是所有操作转调用底层容器的函数，所以set在技术上被视为适配器。

VC6编译器不提供identity()，因为idientity是gnuc提供的，那么set和map如何使用RB-tree？

在传递identity这个参数时，vc6自己写了一个有这样功能的东西（机构体？）

测试程序之前说过了。

容器map ,multimap

同样以rb_tree作为底层容器，允许使用iterator修改data禁止修改key。

创建一个map容器，第一个参数是key第二个参数是data第三个比较key的方法第四个是分配器。

在class中又用pair（pair是啥不知道）将key和data包装成value作为rb_tree的第二个参数，注意此处的key在包装时是const的（不可以修改），这里解释了map可以修改data却不可以修改key的原因。

在rb_tree的第三个参数是select1st,意为选择第一个，（value中第一个是key），下一页ppt会介绍这个仿函数。

VC6不提供select1st()，map使用RB_tree的方法：

他自己写一个_Kfn这个仿函数，就相当于右侧的select1st

pair组合的数据中将key和data命名为first和second，select1st返回的就是first即key

multimap测试

在multimap测试中，不能使用[]使用对应的元素，因为muktimap中的key是可以重复的

如果输入的key不存在，就会以输入的key为key创建新的结点

map测试

通过重载[]这个操作符，在创建新对象时达到了一种更直观的效果（比较像赋值），当然这样会比直接调用insert更慢。

容器hashtable

这个容器的数学成分少，多是经验。

在之前的笔记中提起过，最终发展为Separate Chaining（一个vector，每个元素（bucket）里一个指针，指向链表，链表中放着碰撞在一起的数）

在数据结构中也见过，经过运算（简单的是取余数的运算）。

但这样还是有问题，当某个链表过长的时候，在搜寻的时候会浪费很多时间。

解决方法是vector增长（不一定是二倍），将链表打散（散列表嘛），人们一般会使用素数作为vector的长度（如53），当vector要扩建的时候会选择53的倍数附近的素数。（在图片右上角是gnuc的规定）

vector增长并打散链表的方式叫做rehashing。rehashing的条件（元素个数大于篮子个数）

源代码

需要传入的六个参数class：value（key+data），key，散列方式（元素获取其号码的方式），提取key的方式，比较key的方式，分配器。

大小：三个仿函数（结构体或class）理论大小0实际大小1，总计3字节，

一个vector，vector有三根指针，每个指针4，总计12字节，

一个size_t 此处是int，大小4，总计4字节，

加一起19字节，对齐为20字节。所以一个hashtable大小为20字节。

node是hashtable的bucket下的node，结构在右上角。

hashtable的iterator设计的和deque类似，它可以在一条链表到末尾时自动返回篮子去寻找下一个链表。上图中中间部分是itertaor的简略版，其中的cur指向的是一个node，上图画错了。

另一个指针ht指向的hashtable本身（对应篮子）

我们自己使用一次hashtable试试

value类型设置为char*（c语言中的字符串），key也设置为此类型，获取存储号码方式设置为

1
hash<const char*>//是什么后面说

获取key方式为identity（返回本身）说名key=value，key的比较方式设置为eqstr在图片下半部分。

eqstr是自己写上去的，标准库里没带，他是一个仿函数，重载了（）操作符，类型是bool，而c语言的比较函数strcmp返回值是int，所以在return处加上了一层==用来返回一个bool。

这里说hash是啥

他是一个仿函数，函数体是空的，有一堆偏特化，都是操作符重载，类型是整数型的数值。

这些hash通过一些计算，将字符串映射成一个数字即hash code，这个计算得出的数字应该尽量“乱一些”减少重复的概率。

对于c语言的字符串标准库里直接有对应的函数，而c++的string标准库里没有。

modulus运算

就是mod，求余数的运算。

unordered容器

G4.9版本把hash名字改成了unordered

篮子的数量一定比元素个数多，因为每次两者相等的时候就会进行rehashing.

迭代器

迭代器的分类

指迭代器的可以移动的方式

左下角是左上角类的继承关系，

random_access_iterator_tag是可以跳跃的

bidirectional_iterator_tag是双向的

farwad_iterator_tag是单向的

当遇到一个容器的时候要知道它的迭代器是什么类型的。

这是人为写的一个测试程序，用来看各种容器的iterator是什么类型的。

在绿色箭头处是程序的开始：

将各种容器的临时对象作为参数传给display_category函数，这个函数进行”提问“，提问迭代器的类型

提问本身就是答案（指创建出来的cagy），这个提问我们在之前讲过。

而后根据提问所得到的答案的类型编译器就会去找要调用的函数。

如果按照分类写（1，2，3，4。。。之类），就不能写的这么美观（原因之一）

提一下红黑树是双向的，哈希表是单向的，istream是之前类型里的input_iterator_tag,ostream是之前类型里的output_iterator_tag。

使用官方提供的打印类型名称的方式：

需要include<⁢typeinfo>，使用typeid这个函数，但是你会发现右侧的输出的类型里面除了正常的类型前后还有其他的东西，这是编译导致的，虽然名字不一样但是他们还是那个class。

istream_iterator的iterator_category

G4.9继承了中间偏右的代码块，这个代码块中只有五个typedef，那这么做的好处是什么呢？让下面的class拥有这五个typedef，少打几个字。（哈哈哈哈哈）

从G2.9到G4.9，做法有变化，但是接口是没有变的。

ostream_iterator的iterator_category

与上一张图片几乎一样

两者想说的就是他们的iterator_category是input_iterator_tag或output_iterator_tag（通过typedef)

iterator_category对算法的影响

第一个例子

distance函数是计算两根iterator距离的函数，一般是给其他算法使用的。

这个函数的类型是

1
iterator_traits<InputIterator>::difference_type

在之前的笔记中提到过traits是啥

可知返回值是一个difference_type，distance函数有两个版本，一种是首尾iterator可以直接相减的（random_iterator_tag)，一种是不能相减只能一个一个加的（input_iterator_tag）。

在distance函数里的return处调用了_distance函数，第三个参数是临时对象，要注意这种语法。

函数根据iterator的类型确定调用哪个版本的_distance。

第二个例子

advance函数，增加的意思，也是给其他算法使用的一个函数。

图片右侧中减代码是它的辅助函数，用来获取传入iterator的category，使用临时对象作为返回值。

advance函数有三个版本，分别是可以直接加（random_itertaor_tag），可以加或减（bidirectional_iterator_tag），只能一个一个加（input_iterator_tag）。

iterator_category和type traits对算法的影响

这个例子是copy复制函数，根据传入参数的的类型的不同进行多种不同的处理方式

目的是提高效率，比如：最右面说的是如果是可以跳跃式移动的iterator，for循环中的限制条件就可以用n<首尾之差的方式，与另一种情况相比可能会快吧（右上，是根据指针是否到达末尾来决定是否退出循环，每次需要对比一次）

trivial意思是不重要的

什么是不重要呢

举个例子

复数类，不需要写拷贝构造、拷贝赋值、析构函数（编译器会有一个默认的）

默认的那个是什么都不做的，是不重要的

算法的效率和它能不能判断迭代器的种类有关系

算法

斜体字只是一个例子，一般都是传入iterator

图中两个例子，我们可以把下面的称作上面的第二版本，就像之前的sort排序，加上一个“准则”就改变了比较方式。

算法例子

accumulate

先说左侧的算法，这是一个算法的两种版本，该算法意为累计，左上版本有三个参数，分别是首，位和初值，它会由首至尾一次累加求和，

在它下面的版本里多了一个参数，binary_op意为二元的（需要两个操作数的）

这个位置的东西我们叫它可以被调用的东西（可以是一个函数，也可以是像函数的东西），会在进行累计时调用指定的方法。

根据右侧测试函数，该方法可以是使用者自己写的仿函数，也可以是标准库中的仿函数。

minus是减法的意思。

另外，这里使用的是数组调用这个累计函数，注意首尾是前闭后开（num，num+3）

for_each

该函数意为对每一个元素进行一个操作

有三个参数，第三个参数是要进行的操作

可以理解为以每一个元素作为参数进行循环调用了操作

左下角的用法在第一部分说过，是一种遍历方式（在Java里也有，记得是这个i是前面不能用过的）

replace , replace_if , replace_copy

举这个例子目的是了解一下命名方式

replace意为取代

replace函数有四个参数，对容器中的元素依次判断，如果有元素和指定的旧值相等则将该位置的值替换为新值

replae_if函数加了一个判断的操作（东西），没有旧值这个参数，这个东西有两种两种情况（1或0）

replace_copy函数有一个目标地址这个参数，作用是将符合旧值的元素将新值放入目标地址，其他值照常复制到目标地址。注意这个是复制。

count、count_if

计数器

版本一:遍历容器查找对应元素，有则+1，无则继续遍历

版本二：加一个判断条件

右侧列出了那些容器自己写了count函数那些没有单独写

可以把是否有单独写了count函数看作是否有特化，没写的看作泛化。

在有特别写了count函数的容器时，建议使用他们自己的函数，那样效率高一点

find ,find_if

find是循序查找的，也有两个版本

sort

给出的是测试程序，展示了多种排序方式

为什么sort函数在这8个容器中没有单独写呢？

因为这八个容器中的数据本身就是排好序的。所以不要对这些容器的元素进行sort

为什么list和forward_list自己单独写了一个sort呢？

因为正常的排序算法要求迭代器可以跳跃式移动，而链表的迭代器是不可以跳跃移动的，如果拿这i两个容器使用泛化的sort会报错

因次要记住，标准库的算法并不是对所有的容器都适用

经过这三个函数，注意到有8个容器总是在一起，究其原因是他们是关联式容器，相当于一个小型的数据库，有key的。他们是用红黑树、散列表哈希表做出来的。

关于reverse iterator,rbegin(),rend()

这张图解释了上一个图的sort中调用的rbegin和rend

二分查找，返回值是真或者假

二分查找的数据一定是排序过的

该函数所进行的操作大部分是由lower_bound完成的

lower_bound，也是按照二分法的方式找的，该函数的源码在右侧，他的作用是以二分法的方法找目标数据，发现有多个目标数据，返回该数据在相同数据的前面的（最低点）位置

要是没有目标数据，那么就会指向容器的end了

还有一个upper_bound函数，一样的操作，区别是该函数返回相同数据在后面的（最高点）位置

binary_search对返回值进行判断，所得的迭代器所指向的位置不是数据末尾且查找的目标数据比首地址元素大（首地址元素是最小的）意味着容器中有目标数据。

左下角有一个说明，认为在进行lower_bound之前进行一次判断会更有效率，判断查找的数据是否比容器中首个元素大，如果大的话就不需要进行查找了，会节省时间。

仿函数functors

只为算法服务

当使用者需要算法进行一些特殊的方式（如比较方式）时通过仿函数实现。

主要分为三类：

算数类：进行加或减运算等

逻辑运算类：两个东西和运算，与预算，异或等

相对关系类：比较大小、相等等

都是以类（结构体与类同等地位）的形式存在，以重载操作符()的方式实现要求

这里感觉真妙，这样能把一种操作当作class（就行java里的静态类直接使用类名使用类中函数）传入函数中，而且时按照需求进行使用，给用户一种修改算法的错觉（这么说也不对。

这张图中的三个仿函数在之前使用过，

identity作用是返回一个本身，select1st作用是选择第一个，select2nd作用是选择第二个

select1st和select2nd针对pair（配对，是类，里面有两个东西，分别是first、second）讲容器map是提到过这些。

pair的定义在图片右侧。

在g4.9时修改了他们的名字

这张图写以算法sort为例介绍仿函数使用方式

第一种：没有写仿函数的那个参数，使用的默认的排序方式

第二种：使用的是函数作为参数

第三种：使用的是一个对象（注意不是class而是object）

第四种：使用仿函数，与第一种效果一样，可以说是第一种的显式使用

第五种：使用仿函数，与第一种效果相反，排序后是从大到小

我们自己写的对象或者函数，也能用，但是会有一些情况用不了，因为没有继承那个仿函数应该继承的类（这个是有关仿函数的规定的类），没有融入stl

仿函数functors的可适配（adaptable）条件

unary_function、binary_function

这两个是可以由仿函数继承的类，前几个介绍的仿函数都是继承的第二个

第一个是指有一个操作数，第二个指有两个操作数，作用是将传进去的参数改了个名字。

因为这两个类中没有data，所以继承到子类之后大小是0

可适配的意思是可以被适配器修改

就像之前算法向迭代器问问题一样，适配器会问仿函数一些问题

标注处就是说的提问，问第二个操作数，这句话同时就是答案。

仿函数是唯一一个用户自己可以写并加入stl中的部件

适配器adapter

通常他们的作用是修改一个函数的名字，或者将三个参数改成两个参数

adapter不像其他部件一样，它比较分散，针对不同部件有不同的适配方式，同时又有共性

假设一个东西b无法被其他的部件直接使用，这时用适配器进行适配之后会产生一个a，a面向其他部件，而a的所有的操作都由b来完成。

要实现这种情况（a使用b的功能）有两种方法，一是继承，二是复合。

一个是（is a），一个是（have a），这样说可能好理解

在stl种适配器使用的是第二种方法，就是内含一个对象的方式。

图片右上角是iterator的适配器中必须有的五个typedef，右下角是仿函数适配器必须有的三个（或者两个，取决于仿函数有几个参数）typedef

容器适配器：stack、queue

底层容器都是c，借助c完成自己容器的工作，将函数名修改，也算作一种改造.

函数适配器：binder2nd

右上角：

1
count<<count_if(vi.begin(),vi.end(),not1(bind2nd(less<int>(),40)))

这是在第一讲里提到过的一段代码，这句代码中使用到了适配器，就是bind2nd

这是依据判断语句，符合条件的元素会被选中，经过迭代器修饰之后条件变成了比40小的数据被选中

要说明的是：

1
less<int>()

是一个object（临时对象）而不是函数调用

根据图片他的源码在左上角，是一个辅助函数，真正使用的是binder2nd，为了方便使用者，写了一个辅助函数

它和40被分别存储在binder2nd里的op和value，传入的地方是先写好的模板，编译器会推出来他的类型

正常来说类模板是不会有实参的，那编译器是怎么推到实参类型的呢，借助辅助函数，辅助函数推出实参的类型再传入binder2nd。

适配器适配一个仿函数，它就要表现成一个仿函数，要适配一个容器就要表现成容器，之前提到的用a实现b。ab应该是同一种东西才可以被正常使用。

count_if函数源代码在左下角，第三个参数是条件(pred)，这个条件会使程序去执行写好的操作符重载函数（看图片上的箭头），这里才调用了op（注意op是一个仿函数对象）

写一个辅助函数的原因：要将操作的类型保存起来，很多人是不知道他的类型是什么的，所以设计了辅助函数让 编译器来帮人分析出他的类型，正常typename后面加一个小括号是生成一个临时对象，这个临时对象的类型就是typename。

辅助函数会调用binder2nd类的构造函数，参数是临时对象和40

编译器可能会问的问题：1、第一实参是什么类型？

2、第二实参是什么类型？

3、二者比完之后又是什么type?

能回答这三个问题的仿函数才能被适配：之前提到过的可适配的。

在编写代码的过程中使用了Operator::second_argument_type、Operator::first_argument_type、Operator::result_type分别来提问和回答三个问题。

再仔细看，每一个长长的名字前面会有一个typename，这是为什么呢？

因为在编译过程中，我们使用的是模板参数，所以在实参传入之前我们不知道op和40的类型，编译器在编译的时候就会“犹豫”，此时就会有可能出现错误的编译和无法编译的情况（不同编译器不一样），为了避免这些情况，在这些长长的名字前面写上typename来告诉编译器他们是一个typename

如果被修饰的后的适配器（也可以叫适配之前的东西，仿函数）还要被适配的话，那他也要被问这些问题，所以适配器对象也要继承一个仿函数应该继承的类，之前提到的unary_function和binary_function

函数适配器:not1

上一张图是没有考虑not1的流程，这张图是加上了not1的流程，将prep取否，

新型适配器 bind since C++11

std::bind可以绑定：

1、functions //一个函数

2、function objects //一个仿函数（函数对象）

3、member functions，_1 必须是某个object地址 //成员函数

4、data members，_1 必须是某个object地址 //成员变量

_1是占位符后面还会有

_2

右侧是以my_divide函数为例的测试程序，divide作用是除法

右侧上方第一个测试代码段，将my_divide函数的两个参数分别绑定为10和2，所以在其下方调用函数fn_five()时不用写参数

第二个测试代码段，将my_divide函数的第二个参数绑定为2，第一个参数空着(这里用_1占位置)，所以下面调用half(10)写了一个参数，这个是my_divide的第一个参数

要使用占位符，在前面要写作用域std::placeholders

第三个测试代码段，将my_divide函数的两个参数的位置换了一下，就是说下面的函数输入的是10，2但是进入my_divide函数时是2，10，所以结果是0.2

第四个测试代码段，将my_divide函数的返回值类型绑定为了int，所以结果输入是3

接下来测试绑定成员函数和变量

c++11新的创建对象方式，在对象名后面加大括号里面放对应参数。

测试程序中将适配后的东西的类型写为了auto，让编译器去推类型

在测试成员函数是有一个注释：成员函数有一个实参，this

因此在绑定函数时要预留一个参数位置给this

接下来的调用就需要给一个该类的对象

也可以直接绑定对象，那样在调用的时候就不用给参数

下面是绑定成员变量的例子，同样可以选择绑定对象还是先空出来。

绑定成员变量的效果就是调用该函数时打印出成员变量的值

最下面写了一个容器测试bind的使用

count_if计数，not1取否，bind2nd绑定第二参数，less<.int>()为小于

整句话意思是计算容器中不小于50的数有几个。

接着下面的是小于50的数有几个。

结束