「X02笔记」STL（标准模板库)
2023-08-12 21:36:02
发布于：浙江
5阅读
0回复
0点赞
STL（标准模板库），从广义上分为：容器，算法，迭代器，容器和算法之间通过迭代器进行无缝连接。在 c++ 标准种，STL被组织成以下13个头文件：
#include <algorithm>
#include <deque>
#include <functional>
#include <iterator>
#include <vector>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <stack>
#include <utility>
容器总体分为两种：
序列式容器：容器的元素的位置是由进入容器的时机和地点来决定的。
关联式容器：容器已经有规则，进入容器的元素的位置不是由进入容器的时机和地点来决定的。容器是可以嵌套使用的，也就是容器可以装容器。
迭代器起到指针的作用，对指针的操作基本都可以对迭代器操作。实际上，迭代器式一个类，这个类封装一个指针。
算法，通俗的解释，就是通过优先步骤，解决一个问题。
下面给出一个简单的示例，通过这个示例，我们可以很直观的看到容器、迭代器、算法之间的密不可分的关系：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void Vector(int v) {
cout << v << " ";
}
int main(){
//容器
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
//迭代器
vector<int>::iterator Begin = v.begin();
vector<int>::iterator End = v.end();
//算法
for_each(Begin, End, Vector);
return 0;
}
2. string 容器
2.1 简要说明
封装了很多成员方法。
**自动管理char内存，不用主动定义字符串的长度。 基本没用
string是一个类，内部封装了char*，是一个char*型的容器。
string 和 char 可以互相转换：**
//string 转 char*
string str = "itcast";
const char* cstr = str.c_str();
//char* 转 string
const char* s = "itcast";
string sstr(s);
2.2 string 常用 API
（1）构造函数
（2）赋值
assign()
=
（3）取值
[]
at()
两者的区别：[]方式如果访问越界，直接挂了，at()方式如果访问越界，抛出异常。
（4）拼接
“+”
“+=”
str.append()
（5）查找和替换
find()：查找第一次出现的位置
rfind()：查找最后一次出现的位置
replace()：把给定一段区间替换成别的字符串
（6）比较
compare()
（7）子串
substr()
（8）插入和删除
insert()
erase()
3. vector 容器
3.1 简要说明
vector 容器是动态数组。
单口容器，即从尾部插入（push_back）和删除（pop_back）的效率更高。从其他位置插入删除会引起其他元素的移动，从而效率低下。
提供insert()来从指定位置插入。
用begin()和end()标识指向第一个元素和最后一个元素的下一个位置，用rbegin()和rend()标识指向最后一个元素和第一个元素的上一个位置。
支持随机访问。
随机访问的概念：迭代器支持加减一个数的操作，比如v.begin() + 2
3.2 vector 常用 API
（1）构造函数
（2）赋值
assign()
=
swap()
（3）大小
size()
empty()
resize()：重新指定容器的长度，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
capacity()
reserve()：预留容器的容量，但不初始化，元素不可访问。
（4）取值
at()：若超出范围，抛异常
[]：若超出范围，不抛异常，直接挂
front()：返回第一个元素
back()：返回最后一个元素
（5）插入和删除
push_back()
insert()
pop_back()
emplace()
emplace_back()
erase()
c++ 11中，针对顺序容器（如vector、deque、list），新标准引入了三个新成员，emplace_front()、emplace_back()、emplace()，分别对应push_front()、push_back()、insert()，允许我们将元素放置在容器头部、容器尾部或一个指定位置之前，但emplace_front()、emplace_back()、emplace()的效率更高。
（6）用swap()缩减容量
int main(){
vector<int> vec;
for (int i = 0; i < 1000; i++) {
vec.push_back(i);
}
cout << vec.size() << endl;//1000
cout << vec.capacity() << endl;//1066
vec.resize(10);
cout << vec.size() << endl;//10
cout << vec.capacity() << endl;//1066
vector<int> v(vec);
cout << v.size() << endl;//10
cout << v.capacity() << endl;//10
//结论：resize只影响vector的元素的数量，但不会影响vector的容量，但vector的拷贝构造函数会使容量等于元素数量
//因此可以用匿名对象 + swap来缩小容量，swap的功能是交换两个对象
vector<int>(vec).swap(vec);
cout << v.size() << endl;//10
cout << v.capacity() << endl;//10
return 0;
}
4. deque 容器
4.1 简要说明
双端数组，可以从头部和尾部进行插入和删除，push_back(), pop_back(), push_front(), pop_front()。
begin()返回一个迭代器，指向第一个元素，end()返回一个迭代器，指向最后一个元素的下一个位置，front()返回第一个元素，back()返回最后一个元素。
insert()可以指定位置插入，但会导致元素移动，降低效率。
可随机存取，效率高。
4.2 deque 常用 API
（1）构造函数
（2）赋值
assign()
=
swap()
（3）大小操作
size()
empty()
resize()
（4）插入和删除
push_back()
push_front()
pop_back()
pop_front()
insert()
erase()
emplace()
emplace_back()
emplace_front()
（5）存取
at()
[]
front()
back()
5. stack 容器
5.1 简要说明
先进后出，通过压栈push()从栈顶增加元素，通过出栈pop()从栈顶删除元素。
不能遍历（不提供迭代器），不支持随机存取。只能通过top()访问栈顶元素。
5.2 stack 常用 API
（1）构造函数
（2）插入和删除
push()
pop()
（3）取值
top()
6. queue 容器
6.1 简要说明
先进先出，通过入队push()从队尾增加元素，通过出队pop()从队头删除元素。
front()返回队头元素，back()返回队尾元素。
不能进行遍历（不提供迭代器），不支持随机访问。
6.2 queue 常用 API
（1）构造函数
（2）存取、插入、删除
push()
pop()
back()
front()
（3）赋值
=
（4）大小
empty()
size()
7. list 容器
7.1 简要说明
双向链表，每个结点由data、prev指针和next指针构成，头节点的prev指针指向null，尾节点的next指针指向null。
通过push_back()和pop_back()从尾部添加和删除元素，通过push_front()和pop_front()从头部添加和删除元素。通过insert()从给定位置之前插入元素。
begin()返回指向链表头的迭代器，end()返回指向链表尾的迭代器。
不支持随机访问，只能迭代器++或–。
7.2 list 常用 API
（1）构造函数
（2）插入和删除
push_back()
pop_back()
push_front()
pop_front()
insert()
clear()
erase()
remove(elem)：删除容器中所有与值elem匹配的元素。
（3）大小
size()
empty()
resize()
（4）赋值
assign()
=
swap()
（5）取值
front()
back()
（6）翻转链表
reverse()
sort()
这是list中自带的reverse和sort，不是算法中的reverse和sort。算法中的只支持可随机访问的容器。
8. set/multiset 容器
8.1 简要说明
set/multiset的特性是所有元素会根据元素的值自动进行排序，默认升序排序。set/multiset是以红黑树尾底层机制，其查找效率非常好。set容器中不允许重复元素，multiset允许重复元素。
通过insert()插入数据，自动排序。
可以遍历（提供迭代器），不支持随机存取。
set/multiset不能通过迭代器改变元素的值，因此这样会打破set/multiset的排序规则。
8.2 set/multiset 常用 API
（1）构造函数
（2）赋值
=
swap()
（3）大小
size()
empty()
（4）插入和删除
insert()
clear()
erase()
（5）查找
find(key)：返回迭代器
lower_bound(keyElem)：返回第一个key>=keyElem元素的迭代器
upper_bound(keyElem)：返回第一个key>keyElem元素的迭代器
equal_range(keyElem)：返回lower_bound和upper_bound的两个迭代器，数据结构是pair(iterator, iterator)。
8.3 自定义set/multiset的排序规则
我们可以使用仿函数来定义，仿函数是一个类，在这个类中我们重载()运算符。
//仿函数
class mycompare { //用struct定义也可以
public:
bool operator()(const int& v1, const int& v2) const {
return v1 > v2;
}
};
int main()
{
set<int, mycompare> s;
s.insert(1);
s.insert(2);
s.insert(-1);
s.insert(5);
for (auto it = s.begin(); it != s.end(); it++) {
cout << *it << endl;
}
return 0;
}
9. pair（对组）容器
9.1 简要说明
pair 将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用pair的两个共有函数first()和second()访问。
可以通过pair的构造函数创建队组，也可以通过make_pair()函数创建队组。
10. map/multimap 容器
10.1 简要说明
map相对于set，具有key 和 value，所有元素根据key自动排序。pair的第一元素被称为键值，第二元素被称为实值。map也是以红黑树为底层实现机制。
map的元素是pair
key不能修改，value可以修改
10.2 map/multimap 常用 API
（1）构造函数
（2）赋值
=
swap()
（3）大小
size()
empty()
（4）插入和删除
insert(pair<int,int>(1,2))
insert(make_pair(1,2))
emplace(1,2)
clear()
erase()
（5）查找
find(key)：返回迭代器
lower_bound(keyElem)：返回第一个key>=keyElem元素的迭代器
upper_bound(keyElem)：返回第一个key>keyElem元素的迭代器
equal_range(keyElem)：返回lower_bound和upper_bound的两个迭代器，数据结构是pair(iterator, iterator)。
11. unordered_set/unordered_multiset 容器
11.1 简要说明
无序 set/multiset 容器，和 set/multiset 容器很像，唯一的区别就在于 set 容器会自行对存储的数据进行排序，而 unordered_set 容器不会。
不再以键值对的形式存储数据，而是直接存储数据的值。
容器内部存储的各个元素的值不能被修改。
不会对内部存储的数据进行排序，因为底层采用哈希表结构存储数据。
unordered_set 容器的类模板定义如下：
template < class Key, //容器中存储元素的类型
class Hash = hash<Key>, //确定元素存储位置所用的哈希函数
class Pred = equal_to<Key>, //判断各个元素是否相等所用的函数
class Alloc = allocator<Key> //指定分配器对象的类型
> class unordered_set;
可以看到，以上 4 个参数中，只有第一个参数没有默认值，这意味着如果我们想创建一个 unordered_set 容器，至少需要手动传递 1 个参数。事实上，在 99% 的实际场景中最多只需要使用前 3 个参数（各自含义如表 1 所示），最后一个参数保持默认值即可。
12. unordered_map/unordered_multimap 容器
12.1 简要说明
无序 map/multimap 容器，和 map/multimap 容器很像，唯一的区别就在于，map 容器中存储的数据是有序的，而 unordered_map 容器中是无序的。
底层采用的是哈希表存储结构，该结构本身不具有对数据的排序功能，所以此容器内部不会自行对存储的键值对进行排序。
unordered_map 容器模板的定义如下所示：
template < class Key, //键值对中键的类型
class T, //键值对中值的类型
class Hash = hash<Key>, //容器内部存储键值对所用的哈希函数
class Pred = equal_to<Key>, //判断各个键值对键相同的规则
class Alloc = allocator< pair<const Key,T> > // 指定分配器对象的类型
> class unordered_map;
以上 5 个参数中，必须显式给前 2 个参数传值，并且除特殊情况外，最多只需要使用前 4 个参数，各自的含义和功能如表 1 所示。
这里空空如也
有帮助，赞一个