在学习c++提高-STL总结了笔记，并分享出来。有问题请及时联系博主：Alliswell_WP，转载请注明出处。
05-c++STLday10
目录：一、STL概论1、STL基本概念2、STL六大组件简介3、STL优点二、STL三大组件1、容器2、算法3、迭代器练习：三大组件基本使用三、常用容器1、string容器(1)构造、赋值(2)练习string容器API(3)重新分配内存(4)练习——字母大小写更改2、vector容器(1)练习：容量动态改变(2)API测试》巧用swap收缩空间3、deque容器(1)测试API(2)排序——sort(3)作业——评委打分
一、STL概论
背景：
长久以来，软件界一直希望建立一种可重复利用的东西，以及一种得以制造出”可重复运用的东西”的方法,让程序员的心血不止于随时间的迁移，人事异动而烟消云散，从函数(functions)，类别(classes),函数库(function libraries),类别库(class libraries)、各种组件，从模块化设计，到面向对象(object oriented )，为的就是复用性的提升。
为了建立数据结构和算法的一套标准，并且降低他们之间的耦合关系，以提升各自的独立性、弹性、交互操作性(相互合作性,interoperability),诞生了STL。
1、STL基本概念
STL(Standard Template Library,标准模板库)，是惠普实验室开发的一系列软件的统称。现在主要出现在 c++中，但是在引入 c++之前该技术已经存在很长时间了。 STL 从广义上分为: 容器(container) 算法(algorithm) 迭代器(iterator),容器和算法之间通过迭代器进行无缝连接。STL 几乎所有的代码都采用了模板类或者模板函数，这相比传统的由函数和类组成的库来说提供了更好的代码重用机会。STL(Standard Template Library)标准模板库,在我们 c++标准程序库中隶属于 STL 的占到了 80%以上。
2、STL六大组件简介
STL提供了六大组件，彼此之间可以组合套用，这六大组件分别是:容器、算法、迭代器、仿函数、适配器(配接器)、空间配置器。
容器：各种数据结构，如vector、list、deque、set、map等,用来存放数据，从实现角度来看，STL容器是一种class template。
算法：各种常用的算法，如sort、find、copy、for_each。从实现的角度来看，STL算法是一种function tempalte.
迭代器：扮演了容器与算法之间的胶合剂，共有五种类型，从实现角度来看，迭代器是一种将operator* , operator-> , operator++,operator--等指针相关操作予以重载的class template. 所有STL容器都附带有自己专属的迭代器，只有容器的设计者才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。
仿函数：行为类似函数，可作为算法的某种策略。从实现角度来看，仿函数是一种重载了operator()的class 或者class template
适配器：一种用来修饰容器或者仿函数或迭代器接口的东西。
空间配置器：负责空间的配置与管理。从实现角度看，配置器是一个实现了动态空间配置、空间管理、空间释放的class tempalte.
STL六大组件的交互关系，容器通过空间配置器取得数据存储空间，算法通过迭代器存储容器中的内容，仿函数可以协助算法完成不同的策略的变化，适配器可以修饰仿函数。
3、STL优点
(1)STL 是 C++的一部分，因此不用额外安装什么，它被内建在你的编译器之内。
(2)STL 的一个重要特性是将数据和操作分离。数据由容器类别加以管理，操作则由可定制的算法定义。迭代器在两者之间充当“粘合剂”,以使算法可以和容器交互运作
(3)程序员可以不用思考 STL 具体的实现过程，只要能够熟练使用 STL 就 OK 了。这样他们就可以把精力放在程序开发的别的方面。
(4)STL 具有高可重用性，高性能，高移植性，跨平台的优点。
》高可重用性：STL 中几乎所有的代码都采用了模板类和模版函数的方式实现，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。关于模板的知
识，已经给大家介绍了。
》高性能：如 map 可以高效地从十万条记录里面查找出指定的记录，因为 map 是采用红黑树的变体实现的。
》高移植性：如在项目 A 上用 STL 编写的模块，可以直接移植到项目 B 上。
二、STL三大组件
1、容器容器，置物之所也。
研究数据的特定排列方式，以利于搜索或排序或其他特殊目的，这一门学科我们称为数据结构。大学信息类相关专业里面，与编程最有直接关系的学科，首推数据结构与算法。几乎可以说，任何特定的数据结构都是为了实现某种特定的算法。STL容器就是将运用最广泛的一些数据结构实现出来。
常用的数据结构：数组(array),链表(list),tree(树)，栈(stack),队列(queue),集合(set),映射表(map),根据数据在容器中的排列特性，这些数据分为序列式容器和关联式容器两种。
》 序列式容器强调值的排序，序列式容器中的每个元素均有固定的位置，除非用删除或插入的操作改变这个位置。Vector容器、Deque容器、List容器等。
》关联式容器是非线性的树结构，更准确的说是二叉树结构。各元素之间没有严格的物理上的顺序关系，也就是说元素在容器中并没有保存元素置入容器时的逻辑顺序。关联式容器另一个显著特点是：在值中选择一个值作为关键字key，这个关键字对值起到索引的作用，方便查找。Set/multiset容器 Map/multimap容器2、算法算法，问题之解法也。
以有限的步骤，解决逻辑或数学上的问题，这一门学科我们叫做算法(Algorithms).
广义而言，我们所编写的每个程序都是一个算法，其中的每个函数也都是一个算法，毕竟它们都是用来解决或大或小的逻辑问题或数学问题。STL收录的算法经过了数学上的效能分析与证明，是极具复用价值的，包括常用的排序，查找等等。特定的算法往往搭配特定的数据结构，算法与数据结构相辅相成。
算法分为:质变算法和非质变算法。质变算法：是指运算过程中会更改区间内的元素的内容。例如拷贝，替换，删除等等非质变算法：是指运算过程中不会更改区间内的元素内容，例如查找、计数、遍历、寻找极值等等‘’
再好的编程技巧，也无法让一个笨拙的算法起死回生。3、迭代器
迭代器(iterator)是一种抽象的设计概念，现实程序语言中并没有直接对应于这个概念的实物。在<<Design Patterns>>一书中提供了23中设计模式的完整描述，其中iterator模式定义如下：提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。
迭代器的设计思维-STL的关键所在，STL的中心思想在于将容器(container)和算法(algorithms)分开，彼此独立设计，最后再一贴胶着剂将他们撮合在一起。从技术角度来看，容器和算法的泛型化并不困难，c++的class template和function template可分别达到目标，如果设计出两这个之间的良好的胶着剂，才是大难题。
迭代器的种类:
| 输入迭代器 | 提供对数据的只读访问 | 只读，支持++、==、！= |
| 输出迭代器 | 提供对数据的只写访问 | 只写，支持++ |
| 前向迭代器 | 提供读写操作，并能向前推进迭代器 | 读写，支持++、==、！= |
| 双向迭代器 | 提供读写操作，并能向前和向后操作 | 读写，支持++、--， |
| 随机访问迭代器 | 提供读写操作，并能以跳跃的方式访问容器的任意数据，是功能最强的迭代器 | 读写，支持++、--、[n]、-n、<、<=、>、>= |
练习：三大组件基本使用
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<iostream>
3 #include<string>
4 using namespace std;
5
6 //容器vector
7 #include<vector>
8
9 //使用系统算法的头文件
10 #include<algorithm>
11
12 //迭代器，遍历功能，用指针理解
13 //普通指针也算一种迭代器
14 void test01()
15 {
16 int array[5] = { 1, 3, 5, 6, 8};
17
18 int* p = array;//指针指向数组首地址array[0]
19
20 for(int i = 0; i < 5; i++)
21 {
22 //cout << array[i] << endl;
23 cout << *(p++) << endl;
24 }
25
26 }
27
28 void myPrint(int v)
29 {
30 cout << v << endl;
31 }
32
33 void test02()
34 {
35 //声明容器
36 vector<int> v;//声明一个容器，这个容器中存放int类型数据，对象名称v
37 //向容器中加入数据
38
39 v.push_back(10);
40 v.push_back(20);
41 v.push_back(30);
42 v.push_back(40);
43
44 //遍历容器中的数据
45
46 /*
47 //第一种遍历
48
49 //利用迭代器
50 vector<int>::iterator itBegin = v.begin();//itBegin指向的是v容器中的起始位置
51
52 vector<int>::iterator itEnd = v.end();//itEnd指向v容器中最后一个位置的下一个地址
53
54 while(itBegin != itEnd)
55 {
56 cout << *itBegin << endl;
57
58 itBegin++;
59
60 }
61 */
62 /*
63 //第二种遍历方式
64 //for(int i = 0; i < 5; i++)//对比
65 for(vector<int>::iterator it = v.begin(); it != v.end(); it++)
66 {
67 cout << *it << endl;
68 }
69 */
70
71 //第三种遍历方式——利用算法
72 for_each(v.begin(), v.end(), myPrint);
73
74 }
75
76 //操作自定义的数据类型
77 class Person
78 {
79 public:
80 Person(string name, int age)
81 {
82 this->m_Name = name;
83 this->m_Age = age;
84 }
85
86 string m_Name;
87 int m_Age;
88 }
89
90 void test03()
91 {
92 vector<Person> v;
93 Person p1("大头儿子", 10);
94 Person p1("小头爸爸", 32);
95 Person p1("隔壁王叔叔", 30);
96 Person p1("围裙妈妈", 28);
97
98 v.push_back(p1);
99 v.push_back(p2);
100 v.push_back(p3);
101 v.push_back(p4);
102
103 //遍历
104 //注意：(*it)是<Person>，it是迭代器iterator，是一个指针
105 for(vector<Person>::iterator it = v.begin(); it != v.end(); it++)
106 {
107 cout << "姓名：" << (*it).m_Name << "年龄：" << it->m_Age << endl;
108 }
109
110 }
111
112 //存放自定义数据类型的指针
113 void test04()
114 {
115 vector<Person*> v;
116 Person p1("大头儿子", 10);
117 Person p1("小头爸爸", 32);
118 Person p1("隔壁王叔叔", 30);
119 Person p1("围裙妈妈", 28);
120
121 v.push_back(&p1);
122 v.push_back(&p2);
123 v.push_back(&p3);
124 v.push_back(&p4);
125
126 //遍历
127 //注意：(*it)是<Person*>
128 for(vector<Person*>::iterator it = v.begin(); it != v.end(); it++)
129 {
130 cout << "姓名：" << (*it)->m_Name << "年龄：" << (*it)->m_Age << endl;
131 }
132
133 }
134
135 //容器嵌套容器
136 void test05()
137 {
138 vector<vector<int>> v;
139
140 vector<int>v1;
141 vector<int>v2;
142 vector<int>v3;
143
144 for(int i = 0; i < 5; i++)
145 {
146 v1.push_back(i);
147 v2.push_back(i + 10);
148 v3.push_back(i + 100);
149 }
150 //将小容器放入到大容器中
151 v.push_back(v1);
152 v.push_back(v2);
153 v.push_back(v3);
154
155 //遍历所有数据
156 for(vector<vector<int>>::iterator it = v.begin(); it != v.end(); it++)
157 {
158 for(vector<int>::iterator vit = (*it).begin(); vit != (*it).end; vit++)
159 {
160 cout << *vit << endl;
161 }
162 cout << endl;
163 }
164
165 }
166
167
168
169 int main()
170 {
171 test01();
172
173 system("pause");
174 return EXIT_SUCCESS;
175 } 三、常用容器
1、string容器
C风格字符串(以空字符结尾的字符数组)太过复杂难于掌握，不适合大程序的开发，所以C++标准库定义了一种string类，定义在头文件<string>。
String和c风格字符串对比：
》Char*是一个指针，String是一个类
string封装了char*，管理这个字符串，是一个char*型的容器。
》String封装了很多实用的成员方法
查找find，拷贝copy，删除delete 替换replace，插入insert
》不用考虑内存释放和越界
string管理char*所分配的内存。每一次string的复制，取值都由string类负责维护，不用担心复制越界和取值越界等。
string和c-style字符串转换
在c++中存在一个从const char*到string的隐式类型转换，却不存在从一个string对象到C_string的自动类型转换。对于string类型的字符串，可以通过c_str()函数返回string对象对应的C_string.
通常，程序员在整个程序中应坚持使用string类对象，直到必须将内容转化为char*时才将其转换为C_string.
为了修改string字符串的内容，下标操作符[]和at都会返回字符的引用。但当字符串的内存被重新分配之后，可能发生错误.
(1)构造、赋值
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<iostream>
3 #include<string>
4 using namespace std;
5
6 /*
7 string 构造函数
8 string();//创建一个空的字符串 例如: string str;
9 string(const string& str);//使用一个string对象初始化另一个string对象
10 string(const char* s);//使用字符串s初始化
11 string(int n, char c);//使用n个字符c初始化
12
13 string基本赋值操作
14 string& operator=(const char* s);//char*类型字符串 赋值给当前的字符串
15 string& operator=(const string &s);//把字符串s赋给当前的字符串
16 string& operator=(char c);//字符赋值给当前的字符串
17 string& assign(const char *s);//把字符串s赋给当前的字符串
18 string& assign(const char *s, int n);//把字符串s的前n个字符赋给当前的字符串
19 string& assign(const string &s);//把字符串s赋给当前字符串
20 string& assign(int n, char c);//用n个字符c赋给当前字符串
21 string& assign(const string &s, int start, int n);//将s从start开始n个字符赋值给字符串
22 */
23
24 void test01()
25 {
26 string str;//默认构造
27 string str2(str);//拷贝构造
28 string str3 = str;//等价于上面的
29
30 string str4 = "abcd";
31 string str5(10, 'a');
32
33 cout << str4 << endl;
34 cout << str5 << endl;
35
36 //基本赋值
37 str = "hello";
38 str2 = str4;
39
40 //string& assign(const char *s);//把字符串s赋给当前的字符串
41 str3.assign("abcdef", 4);
42 cout << str3 << endl;
43
44 //string& assign(const string &s, int start, int n);//将s从start开始n个字符赋值给字符串
45 str6.assign(str, 1, 3);//ell?hel？从0索引
46 cout << str6 << endl;
47 }
48
49 int main()
50 {
51 test01();
52
53 system("pause");
54 return EXIT_SUCCESS;
55 } (2)练习string容器API
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<iostream>
3 #include<string>
4 using namespace std;
5 //系统标准异常头文件
6 #include<stdexcept>
7
8 /*
9 //string存取字符操作
10 char& operator[](int n);//通过[]方式取字符
11 char& at(int n);//通过at方法获取字符
12 */
13
14 void test01()
15 {
16 string s = "hello world";
17
18 for(int i = 0; i < s.size(); i++)
19 {
20 //cout << s[i] << endl;
21 cout << s.at(i) << endl;
22 }
23 //[]和at区别？访问越界，[]直接挂掉，at会抛出异常
24
25 try
26 {
27 //cout << s[100] << endl;
28 cout << s.at(100) << endl;
29 }
30 catch(out_of_range& e)
31 {
32 cout << e.what() << endl;
33 }
34 catch(...)
35 {
36 cout << "越界异常" << endl;
37 }
38 }
39
40 /*
41 //string拼接操作
42 string& operator+=(const string& str);//重载+=操作符
43 string& operator+=(const char* str);//重载+=操作符
44 string& operator+=(const char c);//重载+=操作符
45 string& append(const char *s);//把字符串s连接到当前字符串结尾
46 string& append(const char *s, int n);//把字符串s的前n个字符连接到当前字符串结尾
47 string& append(const string &s);//同operator+=()
48 string& append(const string &s, int pos, int n);//把字符串s中从pos开始的n个字符连接到当前字符串结尾
49 string& append(int n, char c);//在当前字符串结尾添加n个字符c
50
51 //string查找和替换
52 int find(const string& str, int pos = 0) const; //查找str第一次出现位置,从pos开始查找
53 int find(const char* s, int pos = 0) const; //查找s第一次出现位置,从pos开始查找
54 int find(const char* s, int pos, int n) const; //从pos位置查找s的前n个字符第一次位置
55 int find(const char c, int pos = 0) const; //查找字符c第一次出现位置
56 int rfind(const string& str, int pos = npos) const;//查找str最后一次位置,从pos开始查找
57 int rfind(const char* s, int pos = npos) const;//查找s最后一次出现位置,从pos开始查找
58 int rfind(const char* s, int pos, int n) const;//从pos查找s的前n个字符最后一次位置
59 int rfind(const char c, int pos = 0) const; //查找字符c最后一次出现位置
60 string& replace(int pos, int n, const string& str); //替换从pos开始n个字符为字符串str
61 string& replace(int pos, int n, const char* s); //替换从pos开始的n个字符为字符串s
62 */
63
64 void test02()
65 {
66 //拼接
67 string s1 = "我";
68 string s2 = "爱北京";
69 s1 += s2;
70 cout << s1 << endl;
71
72 s1.append("天安门");
73 cout << s1 << endl;
74
75 //查找
76 string s = "abcdefg";
77 int pos = s.find("bcf");//找不到返回是-1
78 cout << "pos = " << pos << endl;
79
80 int pos2 = s.rfind("bc");//rfind和find结果一样，内部查找顺序相反
81 cout << "pos2 = " << pos2 << endl;//2
82
83 //替换
84 string s3 = "hello";
85 s3.replace(1, 3, "1111");
86 cout << s3 << endl;//h1111o
87 }
88
89 /*
90 //string比较操作
91 compare函数在>时返回 1，<时返回 -1，==时返回 0。
92 比较区分大小写，比较时参考字典顺序，排越前面的越小。
93 大写的A比小写的a小。
94 int compare(const string &s) const;//与字符串s比较
95 int compare(const char *s) const;//与字符串s比较
96 */
97 void test03()
98 {
99 string s1 = "abc";
100 string s2 = "abcd";
101
102 if(s1.compare(s2) == 0)
103 {
104 cout << "s1等于s2" << endl;
105 }
106 else if(s1.compare(s2) == 1)
107 {
108 cout << "s1大于s2" << endl;
109 }
110 else
111 {
112 cout << "s1小于s2" << endl;
113 }
114 }
115
116 /*
117 //string子串
118 string substr(int pos = 0, int n = npos) const;//返回由pos开始的n个字符组成的字符串
119 */
120 void test04()
121 {
122 string s1 = "abcde";
123 string s2 = s1.substr(1, 3);
124 cout << s2 << endl;
125
126 //需求查找一个邮件的用户名
127 string email = "[email protected]";
128
129 int pos = email.find("@");//8
130 cout << "pos" << pos << endl;
131
132 string usrName = email.substr(0, pos);
133 cout << "用户名：" << usrName << endl;
134 }
135
136 /*
137 //string插入和删除操作
138 string& insert(int pos, const char* s); //插入字符串
139 string& insert(int pos, const string& str); //插入字符串
140 string& insert(int pos, int n, char c);//在指定位置插入n个字符c
141 string& erase(int pos, int n = npos);//删除从Pos开始的n个字符
142 */
143 void test05()
144 {
145 string s1 = "hello";
146 s1.insert(1, "111");
147 cout << s1 << endl;//h111ello
148
149 //删除
150 s1.erase(1, 3);
151 cout << s1 << endl;
152 }
153
154 /*
155 string和c-style字符串转换
156 */
157 void func(string s)
158 {
159 cout << s << endl;
160 }
161 void func2(const char* s)
162 {
163 cout << s << endl;
164 }
165
166 void test06()
167 {
168 string s = "abc";
169
170 //string -> const char*
171 const char* p = s.c_str();
172
173 func(p);//const char* 隐式类型转换为string
174
175 //const char* -> string
176 string s2(p);
177 //func2(s2);//string不能隐式类型转换为char*
178 }
179
180
181
182 int main()
183 {
184 test01();
185
186 system("pause");
187 return EXIT_SUCCESS;
188 } (3)重新分配内存
练习：
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<iostream>
3 #include<string>
4 using namespace std;
5
6 void test01()
7 {
8 string s = "abcdefg";
9 char& a = s[2];
10 char& b = s[3];
11
12 a = '1';
13 b = '2';
14
15 cout << s << endl;//ab12efg
16 cout << (int*)s.c_str() << endl;//输出地址
17
18 s = "pppppppppppppppppppppppp";//内存不够，重新分配内存，下边操作出错
19
20 //a = '1';
21 //b = '2';
22
23 cout << s << endl;
24 cout << (int*)s.c_str() << endl;
25
26
27 }
28
29 int main()
30 {
31 test01();
32
33 system("pause");
34 return EXIT_SUCCESS;
35 } (4)练习——字母大小写更改
写一个函数，函数内部将string字符串中的所有小写字母都变为大写字母
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<iostream>
3 #include<string>
4 using namespace std;
5
6 /*
7 写一个函数，函数内部将string字符串中的所有小写字母都变为大写字母
8 */
9
10 void test01()
11 {
12 string s = "abCdEfg";
13 for(int i = 0; i < s.size(); i++)
14 {
15 s[i] = toupper(s[i]);
16
17 //全变小写
18 //s[i] = tolower(s[i]);
19 }
20 cout << s << endl;
21
22
23 }
24
25 int main()
26 {
27 test01();
28
29 system("pause");
30 return EXIT_SUCCESS;
31 } 2、vector容器
vector的数据安排以及操作方式，与array非常相似，两者的唯一差别在于空间的运用的灵活性。Array是静态空间，一旦配置了就不能改变，要换大一点或者小一点的空间，可以，一切琐碎得由自己来，首先配置一块新的空间，然后将旧空间的数据搬往新空间，再释放原来的空间。Vector是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新元素。因此vector的运用对于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必害怕空间不足而一开始就要求一个大块头的array了。
Vector的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率，一旦vector旧空间满了，如果客户每新增一个元素，vector内部只是扩充一个元素的空间，实为不智，因为所谓的扩充空间(不论多大)，一如刚所说，是”配置新空间-数据移动-释放旧空间”的大工程,时间成本很高，应该加入某种未雨绸缪的考虑，稍后我们便可以看到vector的空间配置策略。
Vector维护一个线性空间，所以不论元素的型别如何，普通指针都可以作为vector的迭代器，因为vector迭代器所需要的操作行为，如operaroe*, operator->, operator++, operator--, operator+, operator-, operator+=, operator-=, 普通指针天生具备。Vector支持随机存取，而普通指针正有着这样的能力。所以vector提供的是随机访问迭代器(Random Access Iterators).
根据上述描述，如果我们写如下的代码：
Vector<int>::iterator it1;
Vector<Teacher>::iterator it2;
it1的型别其实就是Int*,it2的型别其实就是Teacher*.
vector的数据结构
Vector所采用的数据结构非常简单，线性连续空间，它以两个迭代器_Myfirst和_Mylast分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器_Myend指向整块连续内存空间的尾端。
为了降低空间配置时的速度成本，vector实际配置的大小可能比客户端需求大一些，以备将来可能的扩充，这边是容量的概念。换句话说，一个vector的容量永远大于或等于其大小，一旦容量等于大小，便是满载，下次再有新增元素，整个vector容器就得另觅居所。注意：
所谓动态增加大小，并不是在原空间之后续接新空间(因为无法保证原空间之后尚有可配置的空间)，而是一块更大的内存空间，然后将原数据拷贝新空间，并释放原空间。因此，对vector的任何操作，一旦引起空间的重新配置，指向原vector的所有迭代器就都失效了。这是程序员容易犯的一个错误，务必小心。
(1)练习：容量动态改变
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<iostream>
3 using namespace std;
4 //加入vector头文件
5 #include<vector>
6
7 void test01()
8 {
9 vector<int> v;
10 for (int i = 0; i < 10;i ++){
11 v.push_back(i);
12 cout << v.capacity() << endl; // v.capacity()容器的容量
13 }
14
15 }
16
17 int main()
18 {
19 test01();
20
21 system("pause");
22 return EXIT_SUCCESS;
23 } (2)API测试
测试1：
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<iostream>
3 using namespace std;
4 //加入vector头文件
5 #include<vector>
6
7 /*
8 //vector构造函数
9 vector<T> v; //采用模板实现类实现，默认构造函数
10 vector(v.begin(), v.end());//将v[begin(), end())区间中的元素拷贝给本身。
11 vector(n, elem);//构造函数将n个elem拷贝给本身。
12 vector(const vector &vec);//拷贝构造函数。
13
14 //例子 使用第二个构造函数 我们可以...
15 int arr[] = {2,3,4,1,9};
16 vector<int> v1(arr, arr + sizeof(arr) / sizeof(int));
17
18 //vector常用赋值操作
19 assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
20 assign(n, elem);//将n个elem拷贝赋值给本身。
21 vector& operator=(const vector &vec);//重载等号操作符
22 swap(vec);// 将vec与本身的元素互换。
23
24 //vector大小操作
25 size();//返回容器中元素的个数
26 empty();//判断容器是否为空
27 resize(int num);//重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
28 resize(int num, elem);//重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长>度的元素被删除。
29 capacity();//容器的容量
30 reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问。
31
32
33 */
34
35 void printVector(vector<int>& v)
36 {
37 for(vector<int>::iterator it = v.begin(); it != v.end(); it++)
38 {
39 cout << *it << " ";
40 }
41 cout << endl;
42 }
43
44 void test01()
45 {
46 vector<int> v;
47 int arr[] = {2,3,4,1,9};
48 vector<int> v1(arr, arr + sizeof(arr) / sizeof(int));
49
50 vector<int> v2(v1.begin(), v1,end());
51
52 printVector(v2);
53
54 vector<int>v3{10, 100};
55 printVector(v3);
56
57 //赋值使用
58 vector<int>v4;
59 v4.assign(v3.begin(), v3.end());
60 printVector(v4);
61
62 v4.swap(v2);
63 cout << "交换后的v4:" << endl;
64 printVector(v4);//2 3 4 1 9
65
66 cout << "v4容器的大小" << v4.size() << endl;//5
67
68 if(v4.empty())
69 {
70 cout << "v4空" << endl;
71 }
72 else
73 {
74 cout << "v4不空" << endl;
75 }
76
77 v4.resize(10);//第二个参数是默认值，默认是0
78 printVector(v4);//2 3 4 1 9 0 0 0 0 0
79
80 v4.resize(10, -1);
81 printVector(v4);//2 3 4 1 9 -1 -1 -1 -1 -1
82
83 v4.resize(3);
84 printVector(v4);//2 3 4
85
86 }
87
88 int main()
89 {
90 test01();
91
92 system("pause");
93 return EXIT_SUCCESS;
94 } 测试2：
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<iostream>
3 using namespace std;
4 //加入vector头文件
5 #include<vector>
6 //加入list头文件
7 #include<list>
8
9 /*
10 //vector构造函数
11 vector<T> v; //采用模板实现类实现，默认构造函数
12 vector(v.begin(), v.end());//将v[begin(), end())区间中的元素拷贝给本身。
13 vector(n, elem);//构造函数将n个elem拷贝给本身。
14 vector(const vector &vec);//拷贝构造函数。
15
16 //例子 使用第二个构造函数 我们可以...
17 int arr[] = {2,3,4,1,9};
18 vector<int> v1(arr, arr + sizeof(arr) / sizeof(int));
19
20 //vector常用赋值操作
21 assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
22 assign(n, elem);//将n个elem拷贝赋值给本身。
23 vector& operator=(const vector &vec);//重载等号操作符
24 swap(vec);// 将vec与本身的元素互换。
25
26 //vector大小操作
27 size();//返回容器中元素的个数
28 empty();//判断容器是否为空
29 resize(int num);//重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
30 resize(int num, elem);//重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长>度的元素被删除。
31 capacity();//容器的容量
32 reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问。
33
34 */
35
36 void printVector(vector<int>& v)
37 {
38 for(vector<int>::iterator it = v.begin(); it != v.end(); it++)
39 {
40 cout << *it << " ";
41 }
42 cout << endl;
43 }
44
45 void test01()
46 {
47 vector<int> v;
48 int arr[] = {2,3,4,1,9};
49 vector<int> v1(arr, arr + sizeof(arr) / sizeof(int));
50
51 vector<int> v2(v1.begin(), v1,end());
52
53 printVector(v2);
54
55 vector<int>v3(10, 100);
56 printVector(v3);
57
58 //赋值使用
59 vector<int>v4;
60 v4.assign(v3.begin(), v3.end());
61 printVector(v4);
62
63 v4.swap(v2);
64 cout << "交换后的v4:" << endl;
65 printVector(v4);//2 3 4 1 9
66
67 cout << "v4容器的大小" << v4.size() << endl;//5
68
69 if(v4.empty())
70 {
71 cout << "v4空" << endl;
72 }
73 else
74 {
75 cout << "v4不空" << endl;
76 }
77
78 v4.resize(10);//第二个参数是默认值，默认是0
79 printVector(v4);//2 3 4 1 9 0 0 0 0 0
80
81 v4.resize(10, -1);
82 printVector(v4);//2 3 4 1 9 -1 -1 -1 -1 -1
83
84 v4.resize(3);
85 printVector(v4);//2 3 4
86
87 }
88
89 //巧用swap收缩空间
90 void test02()
91 {
92 vector<int>v;
93 for(int i = 0; i < 100000; i++)
94 {
95 v.push_back(i);
96 }
97
98 cout << "v的容量：" << v.capacity() << endl;//大于100000
99 cout << "v的大小：" << v.size() << endl;//100000
100
101 v.resize(3);
102 cout << "v的容量：" << v.capacity() << endl;//大于100000
103 cout << "v的大小：" << v.size() << endl;//3
104
105 //巧用swap收缩空间
106 vector<int>(v).swap(v);
107 //vector<int>(v)利用v初始化匿名对象，swap交换指针
108
109 cout << "v的容量：" << v.capacity() << endl;//3
110 cout << "v的大小：" << v.size() << endl;//3
111 }
112 //reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问
113 void test03()
114 {
115 vector<int>v;
116
117 v.reserve(100000);//预留空间
118
119 int* p = NULL;
120 int num = 0;
121 for(int i = 0; i < 100000; i++)
122 {
123 v.push_back(i);
124 if(p != &v[0])
125 {
126 p = &v[0];
127 num++;
128 }
129 }
130 cout << num << endl;//放置100000个数据开辟过多少次空间
131 }
132
133 /*
134 //vector数据存取操作
135 at(int idx); //返回索引idx所指的数据，如果idx越界，抛出out_of_range异常。
136 operator[];//返回索引idx所指的数据，越界时，运行直接报错
137 front();//返回容器中第一个数据元素
138 back();//返回容器中最后一个数据元素
139
140 //vector插入和删除操作
141 insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素ele.
142 push_back(ele); //尾部插入元素ele
143 pop_back();//删除最后一个元素
144 erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素
145 erase(const_iterator pos);//删除迭代器指向的元素
146 clear();//删除容器中所有元素
147
148 */
149
150 void test04()
151 {
152 vector<int>v;
153 v.push_back(10);
154 v.push_back(30);
155 v.push_back(20);
156 v.push_back(50);
157
158 cout << "v的front为：" << v.front() << endl;//10
159 cout << "v的front为：" << v.back() << endl;//50
160
161
162 v.insert(v.begin(), 2, 100);//参数1：迭代器；参数2：个数N；参数3：具体插入的内容
163 printVector(v);//100 100 10 30 20 50
164
165 v.pop_back();//尾删
166 printVector(v);//100 100 10 30 20
167
168 v.erase(v.begin());
169 printVector(v);//100 10 30 20
170
171 v.erase(v.begin(),v.end());
172 //v.clear();//清空所有数据
173 if(v.empty())
174 {
175 cout << "v为空" << endl;
176 }
177
178 }
179
180 void test05()
181 {
182 //逆序遍历
183 vector<int>v;
184 for(int i = 0; i < 10; i++)
185 {
186 v.push_back(i);
187 }
188 //printVector(v);//0 1 ... 9
189
190 //reverse_iterator逆序迭代器
191 for(vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); it++)
192 {
193 cout << *it << " ";
194 }
195 cout << endl;
196
197 //vector迭代器是随机访问的迭代器，支持跳跃式访问
198 vector<int>::iterator itBegin = v.begin();
199 itBegin = itBegin + 3;
200 //如果上述写法不报错，这个迭代器是随机访问迭代器
201
202 list<int>l;
203 for(int i = 0; i < 10; i++)
204 {
205 l.push_back(i);
206 }
207 list<int>::iterator lIt = l.begin();
208 //lIt = lIt + 1;//list不支持随机访问
209
210 }
211
212 int main()
213 {
214 test01();
215
216 system("pause");
217 return EXIT_SUCCESS;
218 } 3、deque容器
deque容器基本概念
Vector容器是单向开口的连续内存空间，deque则是一种双向开口的连续线性空间。所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作，当然，vector容器也可以在头尾两端插入元素，但是在其头部操作效率奇差，无法被接受。
Deque容器和vector容器最大的差异，一在于deque允许使用常数项时间对头端进行元素的插入和删除操作。二在于deque没有容量的概念，因为它是动态的以分段连续空间组合而成，随时可以增加一段新的空间并链接起来，换句话说，像vector那样，”旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”这样的事情在deque身上是不会发生的。也因此，deque没有必须要提供所谓的空间保留(reserve)功能.
虽然deque容器也提供了Random Access Iterator,但是它的迭代器并不是普通的指针，其复杂度和vector不是一个量级，这当然影响各个运算的层面。因此，除非有必要，我们应该尽可能的使用vector，而不是deque。对deque进行的排序操作，为了最高效率，可将deque先完整的复制到一个vector中，对vector容器进行排序，再复制回deque. deque容器实现原理
Deque容器是连续的空间，至少逻辑上看来如此，连续现行空间总是令我们联想到array和vector,array无法成长，vector虽可成长，却只能向尾端成长，而且其成长其实是一个假象，事实上 (1) 申请更大空间 (2)原数据复制新空间 (3)释放原空间 三步骤，如果不是vector每次配置新的空间时都留有余裕， 其成长假象所带来的代价是非常昂贵的。
Deque是由一段一段的定量的连续空间构成。一旦有必要在deque前端或者尾端增加新的空间，便配置一段连续定量的空间，串接在deque的头端或者尾端。Deque最大的工作就是维护这些分段连续的内存空间的整体性的假象，并提供随机存取的接口，避开了重新配置空间，复制，释放的轮回， 代价就是复杂的迭代器架构。
既然deque是分段连续内存空间，那么就必须有 中央控制，维持整体连续的假象，数据结构的设计及迭代器的前进后退操作颇为繁琐。Deque代码的实现远比vector或list都多得多。
Deque采取一块所谓的map (注意，不是STL的map容器)作为主控，这里所谓的map是一小块连续的内存空间，其中 每一个元素(此处成为一个结点)都是一个指针，指向另一段连续性内存空间，称作
缓冲区。缓冲区才是deque的存储空间的主体。
(1)测试API
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<iostream>
3 using namespace std;
4 //加入deque头文件
5 #include<deque>
6
7 /*
8 //deque构造函数
9 deque<T> deqT;//默认构造形式
10 deque(beg, end);//构造函数将[beg, end)区间中的元素拷贝给本身。
11 deque(n, elem);//构造函数将n个elem拷贝给本身。
12 deque(const deque &deq);//拷贝构造函数。
13
14 //deque赋值操作
15 assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
16 assign(n, elem);//将n个elem拷贝赋值给本身。
17 deque& operator=(const deque &deq); //重载等号操作符
18 swap(deq);// 将deq与本身的元素互换
19
20 //deque大小操作
21 deque.size();//返回容器中元素的个数
22 deque.empty();//判断容器是否为空
23 deque.resize(num);//重新指定容器的长度为num,若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
24 deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，则以elem值填充新位置,如果容器变短，则末尾超出容器长度的元素被删除。
25
26
27 */
28
29 void printDeque(const deque<int>& d)
30 {
31 //iterator 普通迭代器；reverse_iterator 逆序迭代器；const_iterator 只读迭代器
32 for(deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
33 {
34 //*it = 10000;//能修改，为避免修改，参数加入const，并把迭代器更改为只读迭代器
35 cout << *it << " ";
36 }
37 cout << endl;
38 }
39
40 void test01()
41 {
42 deque<int>d;
43
44 d.push_back(10);
45 d.push_back(40);
46 d.push_back(30);
47 d.push_back(20);
48
49 printDeque(d);//10 40 30 20
50
51 deque<int>d2(d.begin(), d.end());
52 d2.push_back(10000);
53
54 //交换
55 d.swap(d2);
56 printDeque(d);//10 40 30 20 10000
57
58 if(d1.empty())
59 {
60 cout << "d1为空" << endl;
61 }
62 else
63 {
64 cout << "d1不为空，大小为：" << d1.size() << endl;
65 }
66 }
67
68 /*
69 //deque双端插入和删除操作
70 push_back(elem);//在容器尾部添加一个数据
71 push_front(elem);//在容器头部插入一个数据
72 pop_back();//删除容器最后一个数据
73 pop_front();//删除容器第一个数据
74
75 //deque数据存取
76 at(idx);//返回索引idx所指的数据，如果idx越界，抛出out_of_range。
77 operator[];//返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。
78 front();//返回第一个数据。
79 back();//返回最后一个数据
80
81 //deque插入操作
82 insert(pos,elem);//在pos位置插入一个elem元素的拷贝，返回新数据的位置。
83 insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
84 insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
85
86 //deque删除操作
87 clear();//移除容器的所有数据
88 erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
89 erase(pos);//删除pos位置的数据，返回下一个数据的位置。
90
91 */
92
93 void test02()
94 {
95 deque<int>d;
96 d.push_back(10);
97 d.push_back(30);
98 d.push_back(20);
99 d.push_front(100);
100 d.push_front(200);
101
102 printDeque(d);//200 100 10 30 20
103
104 //删除 头删 尾删
105 d.pop_back();
106 d.pop_front();
107 printDeque(d);//100 10 30
108
109 cout << "front为：" << d.front() << endl;//100
110 cout << "back为：" << d.back() << endl;//30
111
112 //插入
113 deque<int>d2;
114 d2.push_back(50);
115 d2.push_back(60);
116
117 d2.insert(d2.begin(), d.begin(), d.end());
118 printDeque(d2);//100 10 30 50 60
119
120 }
121
122 int main()
123 {
124 test01();
125
126 system("pause");
127 return EXIT_SUCCESS;
128 } (2)排序——sort
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<iostream>
3 using namespace std;
4 //加入deque头文件
5 #include<deque>
6 //加入算法
7 #include<algorithm>
8
9 void printDeque(const deque<int>& d)
10 {
11 //iterator 普通迭代器；reverse_iterator 逆序迭代器；const_iterator 只读迭代器
12 for(deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
13 {
14 //*it = 10000;//能修改，为避免修改，参数加入const，并把迭代器更改为只读迭代器
15 cout << *it << " ";
16 }
17 cout << endl;
18 }
19
20 //排序规则
21 bool myCompare(int v1, int v2)
22 {
23 return v1 > v2;
24 }
25
26
27 //排序 sort
28 void test01()
29 {
30 deque<int>d;
31 d.push_back(5);
32 d.push_back(15);
33 d.push_back(3);
34 d.push_back(40);
35 d.push_back(7);
36
37 printDeque(d);
38
39 //排序
40 sort(d.begin(), d.end());
41 printDeque(d);
42
43 //从大到小
44 sort(d.begin(), d.end(), myCompare);
45 printDeque(d);
46 }
47
48
49
50 int main()
51 {
52 test01();
53
54 system("pause");
55 return EXIT_SUCCESS;
56 } (3)作业——评委打分
有5名选手：选手ABCDE，10个评委分别对每一名选手打分，去除最高分，去除评委中最低分，取平均分。
//1. 创建五名选手，放到vector中
//2. 遍历vector容器，取出来每一个选手，执行for循环，可以把10个评分打分存到deque容器中
//3. sort算法对deque容器中分数排序，pop_back pop_front去除最高和最低分
//4. deque容器遍历一遍，累加分数，累加分数/d.size()
//5. person.score = 平均分
1 #define _CRT_SECURE_NO_WARNINGS
2 #include<iostream>
3 using namespace std;
4 #include<vector>
5 #include<deque>
6 #include<algorithm>
7 #include<string>
8
9 /*
10 有5名选手：选手ABCDE，10个评委分别对每一名选手打分，去除最高分，去除评委中最低分，取平均分。
11 //1. 创建五名选手，放到vector中
12 //2. 遍历vector容器，取出来每一个选手，执行for循环，可以把10个评分打分存到deque容器中
13 //3. sort算法对deque容器中分数排序，pop_back pop_front去除最高和最低分
14 //4. deque容器遍历一遍，累加分数，累加分数/d.size()
15 //5. person.score = 平均分
16 */
17
18
19
20 //排序 sort
21 void test01()
22 {
23 //1. 创建五名选手，放到vector中
24 vector<char>vPerson{ 'A', 'B', 'C', 'D', 'E' };
25 //2. 遍历vector容器，取出来每一个选手，执行for循环，可以把10个评分打分存到deque容器中
26 deque<int>dScore;
27 for (vector<char>::iterator it = vPerson.begin(); it != vPerson.end(); it++)
28 {
29 cout << "为选手" << *it << "打分" << endl;
30 for (int num = 1; num < 11; ++num)
31 {
32 cout << "第" << num << "个评委" << "为选手" << *it << "打分为：" << endl;
33 int Score;
34 //判断分数的合法性
35 while (true)
36 {
37 cin >> Score;
38 //if (Score >= 0 && Score <= 100)
39 //{
40 // dScore.push_back(Score);
41 // break;
42 //}
43 if (cin.fail())
44 {
45 cout << "对不起，请输入正确的分数：" << endl;
46 //重置标志位
47 cin.clear();
48 char buf[1024];
49 cin.getline(buf, 1024);
50 //cin.sync();//清空缓冲区
51 }
52 else if (Score >= 0 && Score <= 100)
53 {
54 dScore.push_back(Score);
55 break;
56 }
57
58 }
59
60 }
61 //3. sort算法对deque容器中分数排序，pop_back pop_front去除最高和最低分
62 sort(dScore.begin(), dScore.end());
63 dScore.pop_back();
64 dScore.pop_front();
65 double sumScore = 0;
66 double avgScore = 0;
67 //4. deque容器遍历一遍，累加分数，累加分数/d.size()
68 for (deque<int>::const_iterator itd = dScore.begin(); itd != dScore.end(); itd++)
69 {
70 sumScore = sumScore + *itd;
71 }
72 //5. person.score = 平均分
73 avgScore = sumScore / dScore.size();
74
75 //清空容器dScore
76 dScore.clear();
77 //清空屏幕
78 system("cls");
79
80 //显示A的分数
81 cout << "选手" << *it << "平均分为：" << avgScore << endl;
82 }
83
84
85 }
86
87
88
89 int main()
90 {
91 test01();
92
93 system("pause");
94 return EXIT_SUCCESS;
95 }