C++基础知识09.STL容器
## STL容器标准模板库（Standard Tem plate Library，STL）是所有 C++ 编译器和操作系统平台都支持的一种模板库。STL 提供了大量的复用软件组织，能让 C++ 程序设计者快速而高效地进行开发。
STL 是惠普实验室开发的一系列标准化组件的统称。1994 年，STL 被纳入 C++ 标准，成为 C++ 库的重要组成部分。
### 介绍
STL主要由六个部分组成：空间配置器（Allocator）、适配器（Adapters）、容器（Containers）、迭代器（Iterator）、仿函数（Functors）和算法（Algorithm）。STL 的一个基本理念就是将数据和操作分离，数据由容器加以管理，操作则由可定制的算法完成，迭代器在两者之间充当“黏合剂”。
> 空间配置器
C++ 标准库采用了空间配置器实现对象内存空间的分配和归还，空间配置器是特殊的内存模型。例如，使用 vector 容器，存储数据的空间由空间配置器完成内存的分配和资源回收。空间配置器本质上是对 new 和 delete 运算符再次封装而成的类模板，对外提供可用的接口，实现内存资源的自动化管理。
> 适配器
适配器主要指容器适配器。容器适配器也是一类容器，它除了能存储普通数据，还可以存储 list、vector、deque 等容器。容器适配器采用特定的数据管理策略，能够使容器在操作数据时表现出另一种行为。例如，使用容器适配器 stack 封装一个 `vector<int>` 容器，使 `vector<int>` 容器在处理数据时，表现出栈这种数据结构的特点（先进后出）。STL 提供了三个容器适配器：stack（栈）、queue（队列）和 priority_queue（优先队列）。适配器体现了 STL 设计的通用性，极大提高了编程效率。
> 迭代器
迭代器是 STL 提供的用于操作容器中元素的类模板，STL 算法利用迭代器遍历容器中的元素，迭代器本身也提供了操作容器元素的方法，使容器元素访问更便捷。迭代器将容器与算法联系起来，起到了“黏合剂”的作用，STL 提供的算法几乎都通过迭代器实现元素访问。STL 提供了输入迭代器、输出迭代器、正向迭代器、双向迭代器和随机访问迭代器五种类型的迭代器，使用迭代器访问容器元素更简单、易用，且代码更加紧凑、简洁。
> 仿函数
仿函数通过重载(）运算符实现，使类具有函数一样的行为。仿函数也称为函数对象，是 STL 很重要的组成部分，它使 STL 的应用更加灵活方便，增强了算法的通用性。大多数 STL 算法可以使用一个仿函数作为参数，以达到某种数据操作的目的。例如，在排序算法中，可以使用仿函数 less 或 greater 作为参数，以实现数据从大到小或从小到大的排序。
> 算法
算法是 STL 定义的一系列函数模板，是 STL 非常重要的一部分内容。算法可以对容器中的元素施加特定操作。STL 算法不依赖于容器的实现细节，只要容器的迭代器符合算法要求，算法就可以通过迭代器处理容器中的元素。（典型的迭代器设计模式）
> STL 容器分类
| 序列容器 | 关联容器 | 无序容器 |
| --------------------- | ---------- | ---------------------------- |
| vector | set | unordered_set (C++11) |
| list | multiset | unordered_multiset (C++11) |
| deque | map | multiset_map (C++11) |
| array(C++11) | multimap | unordered_multimap (C++11) |
| forward_list(C++11) | | |
### 序列容器
- vector，与 Java 的 ArrayList 类似。也有扩容机制，不过这个扩容一般是变为原先的 2 倍。不同版本的 STL 的具体实现也不一样。
#### vector
> 创建容器
vector 模板中定义了多个重载构造函数，因此 vector 容器的创建与初始化也有多种方式。vector 容器的创建方式主要有四种。
```c++
#include <iostream>
#include <vector>
using namespace std;
int main(){
// 创建初始容量为 5 的 vector
vector<int> v1(5);
// 容量为 5，并且有五个初始值为 -1 的元素。
vector<int> v2(5,-1);
// 列表初始化
vector<string> v3 = {"a","aa","aaa"};
// 空初始化，不指定容量
vector<int> v4;
return 0;
}
```
> 获取容量和已有元素个数
capacity，vector 可以容纳多少元素
size，目前已有的元素个数
```cpp
#include <iostream>
#include <vector>
using namespace std;
void get(){
vector<int> v1(2,0);
cout<<v1.size()<<endl;
cout<<v1.capacity()<<endl;
for (size_t i = 0; i < 10; i++){
v1.push_back(i+10);
cout<<"当前元素的数量："<<v1.size()<<"总共可容纳的数量"<<v1.capacity()<<endl;
/* code */
}
}
int main(){
get();
return 0;
}
/*
2
2
当前元素的数量：3总共可容纳的数量4
当前元素的数量：4总共可容纳的数量4
当前元素的数量：5总共可容纳的数量8
当前元素的数量：6总共可容纳的数量8
当前元素的数量：7总共可容纳的数量8
当前元素的数量：8总共可容纳的数量8
当前元素的数量：9总共可容纳的数量16
当前元素的数量：10总共可容纳的数量16
当前元素的数量：11总共可容纳的数量16
当前元素的数量：12总共可容纳的数量16
*/
```
> 访问元素
可以像数组一样访问，也可以用 at 函数访问。
```cpp
void visited(){
vector<int> v1;
int count = 10;
for (int i = 0; i < count; i++){
v1.push_back(i+4);
}
for (int i = 0; i < count; i++){
cout<<v1<<"=="<<v1.at(i)<<endl;
}
}
```
> 元素重新赋值
- 单个元素的赋值，`v = 10`
- 批量的元素赋值，
```cpp
void assignTest(){
vector<int> v1;
int count = 10;
for (size_t i = 0; i < count; i++){
v1.push_back(i);
}
v1 = 100;
cout<<v1<<endl; // 100
// ssign(n,element) 将 n 个 element 赋值给 vector
v1.assign(5,-1);
cout<<v1<<":"<<v1<<endl; // -1,6
}
```
> 获取头尾元素，从尾部插入删除元素
| 方法 | 说明 |
| ------------------- | -------------- |
| void push_back | 尾部插入元素 |
| void push_back | 尾部删除元素 |
| reference front() | 获取头部元素 |
| reference back()| 获取尾部元素 |
```cpp
void op(){
vector<int> v1;
int count = 5;
for (size_t i = 1; i <= count; i++){
v1.push_back(i); // 向尾部添加元素。
}
// 删除尾部元素
v1.pop_back();
// 头部元素1-尾部元素4
cout<<"头部元素"<<v1.front()<<"-尾部元素"<<v1.back()<<endl;
}
```
> 容器迭代
vector 容器提供了迭代器，通过迭代器可以访问、修改容器中的元素。
| 迭代器 | 说明 |
| ------------------------ | ---------------------------------------------------------------------------- |
| iterator | 正向遍历容器元素 |
| reverse_iterator | 反向遍历容器元素 |
| const_iterator | 正向遍历容器元素，但通过 const_iterator 只能访问容器元素，不能修改元素的值 |
| const_reverse_iterator | 反向遍历容器元素，但通过只能访问容器元素，不能修改元素的值。 |
| 函数 | 说明 |
| ----------- | ----------------------------------------------------------------------------------------- |
| begin() | 返回容器的<b>起始位置</b>的迭代器 iterator |
| end() | 返回容器的<b>结束位置</b>的迭代器 iterator |
| rbegin()| 返回以容器<b>结束位置作为起始位置</b>的反向迭代器 reverse_iterator |
| rend() | 返回以容器<b>起始位置作为结束位置</b>的反向迭代器 reverse_iterator |
| cbegin()| 返回容器的<b>起始位置</b>的常量迭代器 const_iterator，不能修改迭代器指向的内容（C++11） |
| cend() | 返回容器的<b>结束位置</b>的常量迭代器 const_iterator，不能修改迭代器指向的内容（C++11） |
| crbegin() | 返回以容器<b>结束位置作为起始位置</b>的反向迭代器 const_reverse_iterator |
| crend() | 返回以容器<b>起始位置作为结束位置</b>的反向迭代器 const_reverse_iterator |
```cpp
void iter(){
vector<int> c = {1,2,3};
vector<int>::iterator iter;
// 正向迭代
for (iter = c.begin(); iter != c.end(); iter++){
cout<<*iter<<"\t";
}
cout<<""<<endl;
vector<int>::reverse_iterator riter;
// 反向迭代
for (riter = c.rbegin(); riter!=c.rend(); riter++){
cout<<*riter<<"\t";
}
}
/*
1 2 3
3 2 1
*/
```
<span style="color:red">迭代器失效：vector 容器是一个顺序容器，在内存中是一块连续的内存，当插入或删除一个元素后，内存中的数据会移动，从而保证数据的连续。当插入或删除数据后，其他数据的地址可能会发生变化，迭代器获取容器位置信息的数据不正确，即迭代器失效，会导致访问出错</span>
> 任意位置插入数据 - 只能基于迭代器，不能用纯粹的数字
| 函数 | 说明 |
| ------------------------- | ------------------------------------------- |
| insert(pos, elem) | 在 pos 位置上插入元素 elem |
| insert(pos, n, elem) | 在 pos 位置插入 n 个 elem |
| insert(pos, begin, end) | 在 pos 位置插入 区间的数据★ |
| earse(pos) | 删除 pos 位置的元素 |
| earse(begin, end) | 删除 区间的数据 |
```cpp
void randomInsert(){
vector<char> v1;
v1.insert(v1.begin(),'d');
v1.insert(v1.begin(),'c');
v1.insert(v1.begin(),'b');
v1.insert(v1.begin(),'a');
for (size_t i = 0; i < v1.size(); i++){
cout<<v1<<"\t";
}
cout<<""<<endl;
// 在 1 位置插入 5 个 ‘0’
v1.insert(v1.begin()+1,5,'0');
for (size_t i = 0; i < v1.size(); i++){
cout<<v1<<"\t";
}
cout<<""<<endl;
// 擦除起始到结束的所有数据
v1.erase(v1.begin(),v1.end());
for (size_t i = 0; i < v1.size(); i++){
cout<<v1<<"\t";
}
cout<<""<<endl;
}
/*
a b c d
a 0 0 0 0 0 b c d
*/
```
#### deque
双端队列，用法与 vector 一样，区别在于，deque 容器不支持 vector 容器的 reserver 函数、capacity 函数和 data 函数，但是新增了 pop_front 和 push_front 函数。
#### array(c++11)
array 大小固定，存储结构和数组的存储结构一样，但是比数组有更多的方法。
```cpp
#include<iostream>
#include<array>
using namespace std;
int main(){
// 使用时需要声明空间大小
array<int,10> arr;
cout<<arr.size()<<endl;
// 用 10 填充容器
arr.fill(10);
arr = 20;
cout<<arr<<endl;
// 用迭代器进行迭代
array<int,10>::iterator pos;
for (pos = arr.begin(); pos != arr.end(); pos++){
cout<<*pos<<endl;
}
}
```
#### list
双链表实现。用法与 vector 类似。
| 函数 | 说明 |
| --------------------------- | --------------------------------------------------- |
| list\<T\> lt; | 创建一个空 list |
| list\<T\> lt(n); | 创建一个初始容量为 n 的 list |
| list\<T\> lt(n, elem); | 创建一个包含 n 个 elem 的 list |
| list\<T\> lt(begin, end); | 创建一个 list，用 区间的值为元素赋值 |
| list\<T\> lt(lt1); | 用 lt1 初始化一个 list |
赋值操作也 vector 一致，插入删除与 vector 一致
#### forward_list
C++11 提供，单链表实现。不支持 insert() 函数和 erase() 函数，但它提供了 insert_after() 函数和 erase_after() 函数用于插入和删除元素
### 关联容器
关联容器中的元素是按关键字来保存和访问的，典型的关联容器有 set 集合和 map 集合。map 与 set 的功能与 Java 中 map、set 的功能基本一致。
C++ 标准库提供了 8 个关联容器。名字包含 multi 的允许重复的关键字，没有包含的则不允许包含重复的关键字。不保持关键字按顺序存储的容器的名字都以单词 unordered 开头。例如：unordered_multi_set 是一个允许重复关键字，元素无序保存的集合。
类型 map 和 multimap 定义在头文件 map 中；set 和 multiset 定义在头文件 set 中；无序容器则定义在头文件 unordered_map 和 unordered_set 中。
| <b>按关键字有序保存元素</b> | - |
| ----------------------------- | ----------------------------- |
| map | 关联数组：保存 key-value 对 |
| set | 只保存关键字 |
| multimap | key 可重复的 map |
| multiset | 关键字（key）可重复的 set |
| <b>无序集合</b> | - |
| unordered_map | 哈希函数组织的 map |
| unordered_set | 哈希函数组织的 set |
| unordered_multimap | 关键字可重复出现的 set |
| unordered_multiset | 关键字可重复出现的 map |
#### 简单示例
<b>set 和 multiset</b>
set 与 multiset 都是集合，用于存储一组相同数据类型的元素。两者的区别是 set 用来存储一组无重复的元素，而 multiset 允许存储有重复的元素。集合支持插入、删除、查找等操作，但集合中的元素值不可以直接修改，因为这些元素都是自动排序的，如果想修改其中某一个元素的值，必须先删除原有的元素，再插入新的元素。
<b>map 和 multimap</b>
map 是单重映射，multimap 是多重映射。map 的一个 key 只能对应一个 value，而 multimap 一个 key 可以对应多个 value.
```cpp
#include<iostream>
#include<map>
using namespace std;
int main(){
map<char,int> m;
m['a'] = 1;
m['a'] = 2;
// 2, 原先的值 1 被覆盖了。
cout<<m['a']<<endl;
}
```
map 和 multimap 插入元素的方法与其他容器不太一样。每次插入的是一对元素，参数中的 elem 指的是一对元素。在插入元素时，使用 pair<> 语句或 make_pair() 函数创建一个 pair 对象，将 pair 对象作为 insert() 函数的参数，插入容器中。
```cpp
#include<iostream>
#include<map>
using namespace std;
int main(){
map<char,int> m;
m['a'] = 1;
m['a'] = 2;
// 2, 原先的值 1 被覆盖了。
cout<<m['a']<<endl;
multimap<char, int>mm;
mm.insert(make_pair('a',1));
mm.insert(make_pair('a',11));
mm.insert(make_pair('a',1));
auto iter = mm.find('a');
// 同一个 key 的 value 遍历到了末尾值会变成 mm.end()
for (auto itr = mm.find('a'); itr != mm.end(); itr++){
cout << itr->first << '\t' << itr->second << '\n';
}
}
/*
2
a 1
a 11
a 1
*/
```
#### 使用关联容器
> 使用 map 对字符出现的次数进行计数
当从 map 中提取一个元素时，会得到一个 pair 类型的对象。pair 是一个模板类型，保存两个名为 first 和 second 的（公有）数据成员。map 所使用的 pair 用 first 成员保存关键字，用 second 成员保存对应的值。因此，输出语句的效果是打印每个字符及其关联的计数器。
```cpp
void count(){
// map 统计字符计数。
string content = "Hello Hello ollo";
map<char, int> word_count;
for (size_t i = 0; i < content.length(); i++){
++word_count];
}
for(const auto &w: word_count){
cout<<w.first<<":"<<w.second<<endl;
}
}
/*
:2
H:2
e:2
l:6
o:4
*/
```
> 使用 set 统计未在 set 中出现的字符
```cpp
void count(){
string content = "Hello oollH";
map<char, size_t> word_count;
set<char> exclude = {' ', 'H'};
for (size_t i = 0; i < content.size(); i++){
if(exclude.find(content) == exclude.end()){
// 不存在则统计
++word_count];
}
}
for (const auto &w : word_count){
cout<<w.first<<":"<<w.second<<endl;
}
}
/*
e:1
l:4
o:3
*/
```
#### 关联容器概述
> 定义关联容器
定义一个 map/set 时，必须既指明数据类型。每个关联容器都定义了一个默认构造函数，它创建一个指定类型的空容器。我们也可以将关联容器初始化为另一个同类型容器的拷贝，或是从一个值范围来初始化关联容器，只要这些值可以转化为容器所需类型就可以。在新标准下，我们也可以对关联容器进行值初始化：
```cpp
map<char, int> word_count; // 空容器
set<string> exclude = {'H', ' '};
map<string, string> authors = {
{"name", "Jack"},
{"age", "18"}
};
```
当初始化一个 map 时，必须提供关键字类型和值类型。将每个 key-value 对包围在花括号中 `{key, value}`
> 初始化 multimap/multiset
map/set 的关键字唯一，而 multimap/multiset 的关键字可以有多个。比如 multimap 可以同时保存。
```cpp
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main(){
multimap<string,string> map;
map.insert(make_pair("name","kkx"));
map.insert(make_pair("name","kkx2"));
map.insert({"name","kkx3"});
for(auto const &w : map){
cout<<w.first<<":"<<w.second<<endl;
}
}
/*
name:kkx
name:kkx2
name:kkx3
*/
```
也可以使用其他容器的内容来进行初始化，此处就用 set 作为示例。multiset 也是一样的。
```cpp
#include<iostream>
#include<vector>
#include<set>
using namespace std;
void test(){
vector<int> vec;
for (size_t i = 0; i < 10; i++){
vec.push_back(i);
}
set<int> unique(vec.begin(),vec.end());
multiset<int> no_unique(vec.begin(),vec.end());
for(auto const &w : no_unique){
cout<<w<<endl;
}
}
```
> 习题
- 定义一个 map，关键字是家庭的姓，值是一个 vector，保存家中孩子的名。编写代码，实现添加新的家庭以及向已有家庭中添加新的孩子。
- 编写一个程序，在一个 vector 而不是一个 set 中保存不重复的单词。使用 set 的优点是什么？
#### 关联容器操作
> 获取关联容器的 keyType 和 valueType
```cpp
void getType(){
map<string,int>::key_type mpaKeyType;
map<string,int>::value_type mpaKeyType;
map<string,int>::mapped_type mapType;
}
```
好好学习！！！
页:
[1]