写在前面
C++ STL（标准模板库）是一套功能强大的 C++ 模板类，提供了通用的模板类和函数，这些模板类和函数可以实现多种流行和常用的算法和数据结构，如向量、链表、队列、栈。
STL库之容器类
参考文章
https://blog.csdn.net/weixin_43150428/article/details/82469933
# vactor
用法
vector(向量): C++中的一种数据结构,确切的说是一个类.它相当于一个动态的数组,当程序员无法知道自己需要的数组的规模多大时,用其来解决问题可以达到最大节约空间的目的.
用法整理如下：
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
| 声明一个int向量以替代一维的数组:vector <int> a;
1.push_back 在数组的最后添加一个数据
2.pop_back 去掉数组的最后一个数据
3.at 得到编号位置的数据
4.begin 得到数组头的指针
5.end 得到数组的最后一个单元+1的指针
6.front 得到数组头的引用
7.back 得到数组的最后一个单元的引用
8.max_size 得到vector最大可以是多大
9.capacity 当前vector分配的大小
10.size 当前使用数据的大小
11.resize 改变当前使用数据的大小，如果它比当前使用的大，者填充默认值
12.reserve 改变当前vecotr所分配空间的大小
13.erase 删除指针指向的数据项
14.clear 清空当前的vector
15.rbegin 将vector反转后的开始指针返回(其实就是原来的end-1)
16.rend 将vector反转构的结束指针返回(其实就是原来的begin-1)
17.empty 判断vector是否为空
18.swap 与另一个vector交换数据
c.clear() 移除容器中所有
c.empty() 判断容器是否为
c.erase(pos) 删除pos位置的
c.erase(beg,end) 删除[beg,end)区间的
c.front() 传回第一个
c.insert(pos,elem) 在pos位置插入一个elem
c.pop_back() 删除最后一个
c.push_back(elem) 在尾部加入一个
c.resize(num) 重新设置该容器的
c.size() 回容器中实际数据的个
c.begin() 返回指向容器第一个元素的迭代
c.end() 返回指向容器最后一个元素的迭代器
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| vec.begin()//指向迭代器中第一个元素。
vec.end()//指向迭代器中末端元素的下一个，指向一个不存在元素。
vec.push_back(elem) //在尾部加入一个数据。
vec.pop_back() //删除最后一个数据。
vec.capacity() //vector可用空间的大小。
vec.size()//返回容器中数据个数。
vec.empty() //判断容器是否为空。
vec.front() //传回第一个数据。
vec.back() //传回最后一个数据，不检查这个数据是否存在。
vec.at(index) //传回索引idx所指的数据，如果idx越界，抛出out_of_range。
vec.clear() //移除容器中所有数据。
vec.erase(iterator) //删除pos位置的数据，传回下一个数据的位置。
vec.erase(begin,end) //删除[beg,end)区间的数据，传回下一个数据的位置。注意：begin和end为iterator
vec.insert(position,elem) //在pos位置插入一个elem拷贝，传回新数据位置。
vec.insert(position,n,elem) //在pos位置插入n个elem数据，无返回值。
vec.insert(position,begin,end) //在pos位置插入在[beg,end)区间的数据，无返回值。
|
1
2
3
4
5
6
7
| void assign(const_iterator first,const_iterator last); //功能：将区间[first,last)的元素赋值到当前的vector中，当前vector会清除掉容器中之前的内容。
void assign(size_type n,const T& x = T()); //功能：赋n个值为x的元素到当前vector中，当前vector会清除掉容器中之前的内容
vec.rbegin()//传回一个vector的最后一个数据的指针。
vec.rend()// 传回一个vector的第一个数据前一个位置的指针。
vec.resize(num)//重新指定vector的长度。
vec.resize(num,value)//重新指定vector的长度。并设定新增的元素的值
|
测试代码(可略过
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
#include<vector>
#include<iostream>
using namespace std;
int main()
{
vector<int> vec(3,0);
vector<int>::iterator iter;
vector<int>::iterator begin=vec.begin();
vector<int>::iterator end=vec.end();
cout<<"vec:";
for(iter=begin; iter!=end; iter++)
{
static std::size_t i=0;
cout<<*iter<<",";
i++;
}
cout<<endl;
cout<<"size:"<<vec.size()<<endl;
cout<<"capacity:"<<vec.capacity()<<endl;
//
cout<<endl;
vec.push_back(1);
vec.push_back(2);
begin=vec.begin();
end=vec.end();
cout<<"push back 1 and 2 based on above;vec:";
for(iter=begin; iter!=end; iter++)
{
static std::size_t j=0;
cout<<*iter<<",";
j++;
}
cout<<endl;
cout<<"size:"<<vec.size()<<endl;
cout<<"capacity:"<<vec.capacity()<<endl;
//
cout<<endl;
vec.pop_back();
begin=vec.begin();
end=vec.end();
cout<<"pop one element based on above;vec:";
for(iter=begin; iter!=end; iter++)
{
static std::size_t k=0;
cout<<*iter<<",";
k++;
}
cout<<endl;
cout<<"size:"<<vec.size()<<endl;
cout<<"capacity:"<<vec.capacity()<<endl;
/
begin=vec.begin();
end=vec.end();
cout<<endl;
if(vec.empty())
{
cout<<"vec is empty"<<endl;
}
else
{
cout<<"vec is not empty"<<endl;
}
/
cout<<endl;
cout<<"based on the above:"<<endl;
cout<<" vec.front():"<<vec.front()<<endl;
cout<<" vec.back():"<<vec.back()<<endl;
begin=vec.begin();
end=vec.end();
cout<<" size:"<<vec.size()<<endl;
cout<<" capacity:"<<vec.capacity()<<endl;
cout<<"vec:";
for(iter=begin; iter!=end; iter++)
{
static std::size_t l=0;
cout<<*iter<<",";
l++;
}
cout<<endl;
cout<<endl;
cout<<"call at(),based on the above:"<<endl;
cout<<" vec.at():"<<vec.at(3)<<endl;
begin=vec.begin();
end=vec.end();
cout<<" size:"<<vec.size()<<endl;
cout<<" capacity:"<<vec.capacity()<<endl;
cout<<"vec:";
for(iter=begin; iter!=end; iter++)
{
static std::size_t m=0;
cout<<*iter<<",";
m++;
}
cout<<endl;
//
cout<<endl;
cout<<"call clear(),based on the above:"<<endl;
vec.clear();
begin=vec.begin();
end=vec.end();
cout<<" size:"<<vec.size()<<endl;
cout<<" capacity:"<<vec.capacity()<<endl;
cout<<"vec:";
for(iter=begin; iter!=end; iter++)
{
static std::size_t m=0;
cout<<*iter<<",";
m++;
}
cout<<endl;
//
cout<<endl;
for(int i=1;i<8;i++)
{
vec.push_back(i);
}
cout<<"push_back 1,2,3,4,5,6,7 based on above;vec:";
begin=vec.begin();
end=vec.end();
for(iter=begin; iter!=end; iter++)
{
static std::size_t m=0;
cout<<*iter<<",";
m++;
}
cout<<endl;
vec.erase(vec.begin()+2);
cout<<"call vec.erase(3),vec:";
begin=vec.begin();
end=vec.end();
for(iter=begin; iter!=end; iter++)
{
static std::size_t m=0;
cout<<*iter<<",";
m++;
}
cout<<endl;
cout<<" size:"<<vec.size()<<endl;
cout<<" capacity:"<<vec.capacity()<<endl;
//
cout<<endl;
vec.erase(vec.begin()+1,vec.begin()+3);
cout<<"call vec.erase(1,3),vec:";
begin=vec.begin();
end=vec.end();
for(iter=begin; iter!=end; iter++)
{
static std::size_t m=0;
cout<<*iter<<",";
m++;
}
cout<<endl;
cout<<" size:"<<vec.size()<<endl;
cout<<" capacity:"<<vec.capacity()<<endl;
return 1;
|
#set
TODO
STL库之algorithm库
Swap方法
简单来说，就是进行两个变量数值的调换，源码定义如下：
1
2
3
4
| template <class T> void swap ( T& a, T& b )
{
T c(a); a=b; b=c;
}
|
但在对大量数据进行调换的情形下，这个方法可能不满足性能的需求，我们可以通过异或运算来快速完成变量的调换，首先复习一下C++的异或运算：
- a^a=0
- a^b=a+b
- a^0=a
- 异或运算满足结合律
我们可以基于以上的特性，编写异或运算代码，实现数值调换，测试代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
| #include <iostream>
using namespace std;
int main()
{
int a = 9;
int b = 4;
a = a^b;
cout<<a<<endl;
b = a^b;
a = a^b;
cout<<a<<"\t"<<b;
}
|
在一般ccf的题目中，使用swap方法可以节省时间，非常棒！
reverse方法
用于数组的逆序，源码定义如下：
1
2
3
4
5
6
7
8
| template <class BidirectionalIterator>
void reverse (BidirectionalIterator first, BidirectionalIterator last)
{
while ((first!=last)&&(first!=--last)) {
std::iter_swap (first,last);
++first;
}
}
|
迭代调用swap方法实现逆序
sort方法
基于快速排序
1
2
| template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
|
可以自己定制比较的方法
1
2
3
4
5
6
7
8
9
10
11
| bool bigger(struct a, struct b)
{
return (a.score > b.score);
}
struct student{
string name;
char gender;
int score;
};
vector<student> v;
sort(v.begin(), v.end(), bigger);
|
STL库之迭代器类
TODU
