二、容器
1. 顺序容器
所谓的顺序容器指的是，在容器的内部，元素的摆放是有顺序的。通常 vector已经足以满足大部分开发了。
| 容器 |
描述 |
| string |
与vector相似，尾部插入|删除速度快 |
| array |
固定大小数组，支持快速随机访问，不能添加和删除 |
| vector |
可变大小数组，支持快速随机访问，在尾部之外的位置插入和删除 速度慢 |
| deque |
双端队列，支持快速随机访问，两端插入和删除速度快 |
| forward_list |
单向链表、只支持单向顺序访问，插入和删除快，查询和更新慢 |
| 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 | #include <deque>
#include <iostream>
using namespace std;
int main(){
deque<int> deque;
deque.push_back(10);
deque.push_back(20);
deque.push_back(30);
cout <<"第一个是：" <<deque.front() << endl;
cout <<"最后一个是："<< deque.back()<<endl;
cout <<"长度是：" << deque.size() <<endl;
cout << deque[0] << " " << deque.at(1) << endl;
deque.at(0) = 100;
for(int i :deque){
cout <<" --> " << i <<endl;
}
return 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 | #include <forward_list>
#include <iostream>
using namespace std;
int main(){
forward_list<int> flist{80, 70, 90};
//1. 添加:: 只能在头的位置追加
flist.push_front(100);
//2. 添加:: 在第一个位置的后面，插入一个新的元素。 需要使用迭代器来完成
flist.insert_after(flist.begin() , 35);
//3. 删除:: 直接给元素值即可
flist.remove(70);
//4. 修改元素值： 也可以使用迭代器的方式修改值
flist.front() = 10;
*flist.begin() = 20;
cout <<"第一个元素是：" << flist.front() << endl;
cout << "排序后打印：" << endl;
flist.sort();
for(auto i = flist.begin() ; i != flist.end() ; i++){
cout << "--->" << *i << endl;
}
return 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 | #include <list>
#include <iostream>
using namespace std;
int main(){
list<int> list1{80, 70, 90};
//添加数据
list1.push_front(10);
list1.push_back(20);
//删除元素
list1.remove(70);
//修改元素
list1.front() = 10;
cout << "第一元素：" <<list1.front() << endl;
*list1.end() = 20 ;
cout << "第一元素：" <<list1.back() << endl;
//遍历链表：
for (auto i = list1.begin(); i != list1.end() ; i++) {
cout <<" ---> "<< *i << endl;
}
return 0 ;
}
|
2. 迭代器
早前访问数组、vector、字符串时，都可以使用索引下标的方式访问，实际上还有一种更为通用的机制 ： 迭代器 。所有标准库中的容器都可以使用迭代器，但是只有少数几个支持下标索引的方式。与指针相似，迭代器也能对对象进行间接访问，但是不能简单认为，指针就是对象，也不能直接认为迭代器就是对象。只是可以通过迭代获取到对象。
1. 迭代器介绍
迭代器通常都是靠容器的 begin() 和 end() 函数获取。 其中begin 返回的是指向第一个元素的迭代器， 而end函数返回的值指向最后一个元素的下一个位置，也就是指向容器里面不存在的尾后元素。所以一般end（）返回的迭代器仅是一个标记而已，并不用来获取数。
2. 迭代器运算
由于begin() 的返回值只会指向第一个元素，若想获取到后面的元素，可以对迭代器进行运算，它的用法和指针的运算是一样的。通过 + - 的操作，来让返回前后元素对应的迭代器。 在迭代器的内部，重载了*运算符函数。通过它可以直接获取到数据
3. 使用迭代器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | #include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> s{88,85,90,95,77};
cout <<*s.begin() << endl; //88
cout <<*(s.begin()+1) << endl; //85
//...
cout <<*(s.end()-1) << endl;//77
//遍历容器
for(auto i = s.begin() ; i != s.end() ; i++){
cout << *i << endl;
}
return 0 ;
}
|
3. 关联容器
关联容器和顺序容器有很大的不同，顺序容器的元素在容器中是有顺序的（按照添加先后计算） ， 而关联容器并不计较顺序的概念，因为他们是按照关键字来访问元素的。C++中常用的关联容器有两个：map 和 set , map 有点类似 python 里面的字典，使用键值对的形式来存储
1. pair介绍
pair定义在头文件#include 中，一个pair保存两个数据成员，它是类模板，所以在创建对象的时候，需要添加泛型参数，以用来表示所保存的数据类型。
| #include <iostream>
#include <utility>
#include <string>
using namespace std;
int main(){
pair<string ,int> p("张三",17) ;
cout << p.first << p.second <<endl;
return 0 ;
}
|
2. map操作
map 只允许产生一对一的关系，也就是一个关键字对应一个值，如生活中大多数人，一人一套房差不多。但是也有人是名下多套房，这时候可以使用multimap, 它允许一个关键字对应多个值。 它们都定义在头文件 #include 中。
a. 添加
不允许key 有重复的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | #include <iostream>
#include <map>
#include <string>
using namespace std;
int main (){
map<string , string> address_map ;
//匹配可变参数列表
address_map.insert({"张三" , "星湖花园1号"});
address_map.insert(make_pair("李四" , "星湖花园1号"));
address_map.insert(pair<string ,string>("王五" , "星湖花园1号"));
//有疑问
address_map.insert({"张三" , "星湖花园2号"}); //与第一个同关键字，会覆盖原有数据
return 0 ;
}
|
b. 访问
map可以使用【】的方式来获取指定的元素，要求传递进来的是key关键字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | #include <iostream>
#include <map>
#include <string>
using namespace std;
int main(){
//访问指定元素
string address = address["张三"] ;
cout << address << endl;
//使用at函数访问
string address2 = map.at("张三2")
cout << address2 << endl;
return 0 ;
}
|
c. 删除
除了能使用迭代器的方式删除之外，关联容器由于使用了关键了记录数据，所以删除的时候也可以根据关键字来删除数据。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | #include <iostream>
#include <map>
#include <string>
using namespace std;
int main(){
//迭代器方式删除。
for(auto i = address_map.begin() ; i != address_map.end() ; i++){
cout <<i->first << " = "<< i->second << endl;
if(i->first == "李四"){
address_map.erase(i);
}
}
//使用关键字删除
address_map.erase("王五");
//清空整个map
address_map.clear();
return 0 ;
}
|
d. 修改
修改其实就是替换，但是如果还是用insert 是无法起作用的，因为它会执行唯一检查。使用 at函数，对某一个特定关键字的位置修改值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | #include <iostream>
#include <map>
#include <string>
using namespace std;
int main(){
map<string , int> map;
map.insert( {"张三1" ,18});
map.insert( {"张三2" ,28});
map.insert( {"张三3" ,38});
cout <<map["张三1"] << endl; //18
map.at("张三1") = 99;
cout <<map["张三1"] << endl; //99
return 0 ;
}
|
判断是否为空、获取大小、判断是否存在key
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>
#include <map>
#include <string>
using namespace std;
int main(){
map<string , int> map;
map.insert( {"张三1" ,18});
//判断是否为空
bool empty = map.empty();
cout <<"empty = " << empty << endl;
//获取大小
int size = map.size();
cout <<"size = " << size << endl;
//查询该key在map中的个数，可用来判断是否存在该key
int count = map.count("张三1");
cout <<"count = " << count << endl;
return 0 ;
}
|
3. set操作
set就是关键字的简单集合，并且容器内部元素不可重复且有顺序。当只是想知道一个值是否存在时，set是最有用的。 set 为不可重复容器，而multiset为可重复容器。
在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序。set中元素的值不能直接被改变。set内部采用的是一种非常高效的平衡检索二叉树：红黑树，也称为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树。使用set需要导入头文件 #include
a. 添加元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | #include <set>
using namespace std;
int main(){
//创建空白set容器
// set<int>s ;
//创建容器并初始化，可变参数往里面赋值，但是这里添加了重复的3. 后面的3不会被添加进去。
set<int> s1{3,4,5,6,3};
s.insert(16);
s.insert({7,8,9,10}); //也可以接收可变参数
return 0 ;
}
|
b. 遍历set
遍历的逻辑和其他含有迭代器的容器一样。
1
2
3
4
5
6
7
8
9
10
11
12 | #include <set>
#include <iostream>
using namespace std;
int main(){
set<int> s1({3,4,5,6,3});
for(auto p = s1.begin(); p != s1.end() ; p++){
cout <<*p << endl;
}
return 0 ;
}
|
c. 删除指定元素
还是使用erase 函数删除 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | #include <set>
#include <iostream>
using namespace std;
int main(){
set<int> s1({3,4,5,6,3});
for(auto p = s1.begin(); p != s1.end() ; p++){
cout <<*p << endl;
if(*p == 4){
s1.erase(p);
}
}
//清空这个容器
s1.clear();
return 0 ;
}
|
判断是否为空、获取大小、判断是否存在key
1
2
3
4
5
6
7
8
9
10
11
12
13 | set<int> s1({3,4,5,6});
//判断是否为空
bool empty = s1.empty();
cout <<"empty = " << empty << endl;
//获取大小
int size = s1.size();
cout <<"size = " << size << endl;
//查询该key在map中的个数，可用来判断是否存在该key
int count = s1.count("张三1");
cout <<"count = " << count << endl;
|
4. 常用容器函数
到目前为止，容器的操作基本上也就包含了增删改查这些基本的功能，但是有时候可能会面临一些特殊的操作，比如：查找特定元素、替换或删除特定值、对容器进行重新排序等等。标准库并未给每个容器实现这些操作的函数，而是定义一组泛型算法 。 算法大部分包含在 #include | #include
1. 只读函数
这一类算法只会读取元素，并不胡改变元素。常见的有 ： find | cout | accumulate
它定义在头文件#include 中，所以不要忘记了导入头文件，它的功能是对一个容器的所有元素取和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | #include <numeric>
#include <iostream>
#include <set>
using namespace std;
int main (){
set<int> s1({3,4,5,6});
//参数一：求和的起始范围 迭代器
//参数二：求和的结束范围 迭代器
//参数三：最初的求和值，
int a = accumulate(s1.begin(), s1.end() , 0 );
cout <<a << endl;
//cbegin() 和 cend() 的 c 其实是const的意思。
int a2 = accumulate(s1.begin(), s1.end() , 0 );
cout << a2 << endl;
return 0 ;
}
|
比较两个不同类型的容器是否保存了相同的值，比较的是里面保存的值，容器里面的元素类型要一样。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | #include <numeric>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
int main (){
set<int> s1{1,2,3,4,5};
vector<int> v1{1,2,3,4,5};
bool flag = equal(s1.begin(), s1.end(),v1.begin());
cout <<"flag = " <<flag <<endl;
return 0 ;
}
|
2. 写入函数
给定一个范围，把这个范围的元素全部替换成指定的值。实际上也是填充的意思。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | #include <vector>
#include <iostream>
using namespace std;
int main(){
vector<int> scores {10,20,30,40,50,60,70};
fill(scores.begin() ,scores.end() , 0 ); //从起始到结束，全部用0替换。
//fill(scores.begin()+1 ,scores.end() , 0 ); //从第一个元素后面开始替换成0
for(int score :scores){
cout <<"score = " << score <<endl;
}
return 0 ;
}
|
由于数组是不允许拷贝的，若要对数组进行一次拷贝，通常使用copy 函数来实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | #include <iostream>
using namespace std;
int main(){
int scores[] {66,77,88,99,100};
int size = sizeof(scores) / sizeof(int);
int scores2[ size ];
//参数一，表示起始位置，参数二： 结束为止，参数三：拷贝的目标位置
copy(begin(scores), end(scores) , scores2);
for(int i = 0 ; i < size; i++){
cout << i << " = " << scores2[i] << endl;
}
return 0 ;
}
|
对一个容器中，某一段范围的某一个指定元素，替换成指定的值。 需导入头文件#include
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | #include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
vector<int> scores {30,20,30,40,30,60};
//把容器中，从开始到结束为止，所有的30，替换成100.
replace(scores.begin(),scores.end(),30 , 100);
for(int score : scores){
cout << " ===> " <<score <<endl;
}
return 0 ;
}
|
有时候有些容器在存储数据时，并没有排序的概念，如果要排序使之输出有一定的格式，可以选择使用sort对容器进行排序 需导入头文件#include
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
vector<string> scores{"ab","bc","aa","abc","ac"};
//默认使用字母表顺序排序
sort(scores.begin(),scores.end());
for(int score : scores){
cout << " ===> " <<score <<endl;
}
return 0 ;
}
|
除了set不接受重复元素之外，其他容器都可以接收重复元素，当然map稍微特殊一点，因为它是键值对形式存储，要求的是key不允许重复，值实际上可以重复。
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 | #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> stu_vector{ 100,90,88,75,90,88,90};
//如果是我们自己做。遍历 ---> 不重复的元素，装到一个vector，然后返回vector
sort(stu_vector.begin() , stu_vector.end());
//先排序，然后确定唯一值，所有不重复的值先放前面， 重复的值放后面， 这个end就是指向了
//最后一个不重复的值位置
auto end = unique(stu_vector.begin() , stu_vector.end());
//删除从最后不重复位置开始一直删除到vector的末尾位置，
//因为所有的重复元素都已经赶到了末尾。 其实并不是删除，只是隐藏了而已。
stu_vector.erase(end , stu_vector.end());
for (int a : stu_vector){
cout << a << "\t";
}
cout <<"vector的长度是：" <<stu_vector.size() << endl;
cout << "vector的下标4的元素是："<< stu_vector[4] << endl;
cout << "vector的下标5的元素是："<< stu_vector[5] << endl;
return 0;
}
|
默认情况下容器中的排序算法是按照字母表顺序排序，但有时候，我们希望按照自己定义的规则排序，比如我们希望字数多的字符串排在后面，而不是看字母表顺序。mysort 的参数位置还要一个好听的名字，叫做“谓词” ，一元谓词表示这个函数接收一个参数，二元谓词表示接收两个参数，这个函数还要求有一个返回值，以方便底层排序获取我们的定义的排序规则。
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 | #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
//回调函数，由sort内部调用，并且要求返回结果。
bool mysort(const string& a , const string& b){
return a.size() < b.size();
}
vector<string> vv{"ab","bc","aa","abc","ac"};
//默认使用字母表顺序排序 按照我们规定的排序算法排序
sort(vv.begin(),vv.end() , mysort);
//如果字数一样，长度一样，那么再按字母表顺序排序，可以使用stable_sort
stable_sort(vv.begin(),vv.end() , mysort);
for(string ss :vv){
cout <<"===>" << ss <<endl;
}
return 0 ;
}
|