STL库

  C++ 的标准模板库（STL，Standard Template Library）是 C++ 标准库的一部分，提供了大量有用的模板类和函数，用于高效的容器管理、算法操作和迭代器操作。它使开发者能够快速构建强大、灵活和高效的程序，而不必从头实现常见的数据结构和算法。对于STL，学习起来并不复杂，掌握几种常用的容器，如vector、list、map、set、queue、stack等，以及一些常用的算法，如sort、find等，了解迭代器的使用，就可以满足大部分开发需求。
核心包括以下重要组件组件：

组件	描述
容器（Containers）	容器是 STL 中最基本的组件之一，提供了各种数据结构，包括向量（vector）、链表（list）、队列（queue）、栈（stack）、集合（set）、映射（map）等。这些容器具有不同的特性和用途，可以根据实际需求选择合适的容器。
算法（Algorithms）	STL 提供了大量的算法，用于对容器中的元素进行各种操作，包括排序、搜索、复制、移动、变换等。这些算法在使用时不需要关心容器的具体类型，只需要指定要操作的范围即可。
迭代器（iterators）	迭代器用于遍历容器中的元素，允许以统一的方式访问容器中的元素，而不用关心容器的内部实现细节。可以理解为指针。STL 提供了多种类型的迭代器，包括随机访问迭代器、双向迭代器、前向迭代器和输入输出迭代器等。
函数对象（Function Objects）	函数对象是可以像函数一样调用的对象，可以用于算法中的各种操作。STL 提供了多种函数对象，包括一元函数对象、二元函数对象、谓词等，可以满足不同的需求。
适配器（Adapters）	适配器用于将一种容器或迭代器适配成另一种容器或迭代器，以满足特定的需求。STL 提供了多种适配器，包括栈适配器（stack adapter）、队列适配器（queue adapter）和优先队列适配器（priority queue adapter）等。

1. 容器

STL 中的容器可以分为三类：

1. 顺序容器：存储元素的序列。
   • std::vector：动态数组，支持快速随机访问。
   • std::queue：单端队列，一种先进先出的数据结构
   • std::priority_queue：用于实现优先队列。
   • std::deque：双端队列，支持快速插入和删除。
   • std::stack：栈，一种后进先出的数据结构
   • std::list：链表，支持快速插入和删除，但不支持随机访问。
   • std::forward_list：单向链表
   • std::array：固定大小数组
   • std::string：字符串
2. 关联容器：存储键值对，每个元素都有一个键（key）和一个值（value），并且通过键来组织元素。
   • std::set：集合，不允许重复元素。
   • std::multiset：多重集合，允许多个元素具有相同的键。
   • std::map：映射，每个键映射到一个值。
   • std::multimap：多重映射，允许多个键映射到相同的值。
3. 无序容器（C++11 引入）：哈希表，支持快速的查找、插入和删除。
   • std::unordered_set：无序集合。
   • std::unordered_multiset：无序多重集合。
   • std::unordered_map：无序映射。
   • std::unordered_multimap：无序多重映射。

1.1. std::vector

vector 是基于数组的数据结构，但它可以自动管理内存，是一个动态数组，这意味着你不需要手动分配和释放内存。与 C++ 数组相比，vector 具有更多的灵活性和功能，使其成为 C++ 中常用的数据结构之一。
基本特性:

• 动态大小：vector 的大小可以根据需要自动增长和缩小。
• 连续存储：vector 中的元素在内存中是连续存储的，这使得访问元素非常快速。
• 可迭代：vector 可以被迭代，你可以使用循环（如 for 循环）来访问它的元素。
• 元素类型：vector 可以存储任何类型的元素，包括内置类型、对象、指针等。

使用场景：

• 当你需要一个可以动态增长和缩小的数组时。
• 当你需要频繁地在序列的末尾添加或移除元素时。
• 当你需要一个可以高效随机访问元素的容器时。

操作：

• 使用vector要引入<vector>头文件

  #include <vector>

• 声明 vector

  std::vector<int> myVector; // 创建一个存储整数的空 vector

  这将创建一个空的整数向量,也可以在创建时指定初始大小和初始值：

  std::vector<int> myVector(5); // 创建一个包含 5 个整数的 vector，每个值都为默认值（0）
  std::vector<int> myVector(5, 10); // 创建一个包含 5 个整数的 vector，每个值都为 10

  或：

  std::vector<int> vec; // 默认初始化一个空的 vector
  std::vector<int> vec2 = {1, 2, 3, 4}; // 初始化一个包含元素的 vector

• push_back 向 vector 中添加元素：

  myVector.push_back(7); // 将整数 7 添加到 vector 的末尾

• 使用下标操作符 [] 或 at()方法访问 vector 中的元素：

  int x = myVector[0]; // 获取第一个元素
  int y = myVector.at(1); // 获取第二个元素

• front() 和 back() 方法分别获取 vector 中的第一个和最后一个元素：

  int firstElement = myVector.front(); // 获取第一个元素
  int lastElement = myVector.back(); // 获取最后一个元素

• empty() 方法检查 vector 是否为空：

  bool isEmpty = myVector.empty(); // 检查 vector 是否为空

• capacity() 方法获取 vector 的容量（即在不重新分配内存的情况下可以存储的最大元素数量）：

  int capacity = myVector.capacity(); // 获取 vector 的容量

• size() 方法获取 vector 中元素的数量：

  int size = myVector.size(); // 获取 vector 中的元素数量

• erase() 删除vector 中的元素：

  myVector.erase(myVector.begin() + 2); // 删除第三个元素

• pop_back()移除尾部元素。

  myVector.pop_back(); // 移除 vector 中的最后一个元素

• clear() 清空 vector 中的所有元素：

  myVector.clear(); // 清空 vector

• 迭代访问，可以使用迭代器遍历 vector 中的元素：

  for (auto it = myVector.begin(); it != myVector.end(); ++it) {
      std::cout << *it << " ";
  }

  或者使用范围循环：

  for (int element : myVector) {
      std::cout << element << " ";
  }

• begin() 和 end() 方法返回指向 vector 中第一个和最后一个元素的迭代器：

  std::vector<int>::iterator it = myVector.begin(); // 获取指向第一个元素的迭代器
  std::vector<int>::iterator itEnd = myVector.end(); // 获取指向最后一个元素的迭代器

1.2. std::list

list 是 C++ STL 中的一种容器，表示一个双向链表（doubly linked list）。与 std::vector 不同，它不需要连续的内存存储，因此特别适合频繁的插入和删除操作。
特点:

• 双向链表：每个节点都存储一个元素，并有指向前后节点的指针。
• 高效的插入和删除：在任何位置插入或删除元素的复杂度为 O(1)，只需要调整指针。
• 线性访问时间：不像 std::vector，它不支持常数时间的随机访问（无法使用下标 []）。
• 动态大小：与 std::vector 一样，大小可以动态调整。

操作：

• 包含头文件：#include <list>
• 声明列表：std::list<T> mylist;，其中 T 是存储在列表中的元素类型。
• 初始化与vector类似。
• 在尾部插入元素：mylist.push_back(value);
• 在头部插入元素：mylist.push_front(value);
• 删除元素：mylist.pop_back(); 或 mylist.pop_front(); 或 mylist.erase(iterator);
• 插入元素：mylist.insert(iterator, value);
• 访问元素：mylist.front(); 和mylist.back();
• 遍历列表：使用迭代器 for (auto it = mylist.begin(); it != mylist.end(); ++it)
• 删除所有元素：mylist.clear();
• 检查列表是否为空：mylist.empty();
• 获取列表的大小：mylist.size();
• 对列表元素排序：mylist.sort();
• 将列表元素反转：mylist.reverse();

1.3. std::deque

deque一种双端队列容器，提供了灵活的双端操作，即可以高效地在容器的两端进行插入和删除操作。它的底层实现通常是一个分段的连续数组。
特点：

• 双端队列：可以在队列的两端进行插入和删除操作。
• 随机访问：支持使用下标操作符 [] 和 at() 方法进行随机访问。
• 动态大小：可以在运行时动态地增加或减少元素数量。

操作：

• 包含头文件：#include <deque>
• 声明 ：std::deque<T> myDeque;，其中 T 是存储在 deque 中的元素类型。
• 初始化：与 vector 类似，可以使用默认构造函数、指定大小和初始值、或使用初始化列表。
• 在尾部插入元素：myDeque.push_back(value);
• 在头部插入元素：myDeque.push_front(value);
• 删除尾部元素：myDeque.pop_back();
• 删除头部元素：myDeque.pop_front();
• 插入元素：myDeque.insert(iterator, value);
• 删除元素：myDeque.erase(iterator);
• 访问元素：myDeque.front(); （第一个元素）和 myDeque.back();（最后一个元素）和myDeque.at(index); 或 myDeque[index];
• 清空元素：myDeque.clear();
• 检查是否为空：myDeque.empty();
• 获取大小：myDeque.size();
• 获取容量：myDeque.capacity();

1.4. std::queue

queue用于实现队列数据结构，遵循先进先出（FIFO）的原则。它为用户提供了简单的接口，隐藏了底层的具体实现细节。底层容器通常默认使用std::deque，但也可以指定其他容器（如 std::list）。
特点：

• 先进先出（FIFO）：最先插入的元素最先被移除。
• 底层容器：默认使用 std::deque，也可以指定为 std::list 等。
• 受限操作：只允许访问队列的头部（front）和尾部（back），不支持随机访问。

操作：

• 包含头文件：#include <queue>
• 声明：std::queue<T> myQueue;，其中 T 是存储在队列中的元素类型。
• 初始化：与 vector 类似，可以使用默认构造函数、指定大小和初始值、或使用初始化列表。
• 在尾部插入元素：myQueue.push(value);
• 删除头部元素：myQueue.pop();
• 访问头部元素：myQueue.front();
• 访问尾部元素：myQueue.back();
• 判断队列是否为空：myQueue.empty();
• 获取队列大小：myQueue.size();

1.5. std::stack

stack 实现了一个后进先出（LIFO，Last In First Out）的数据结构。这种数据结构非常适合于需要”最后添加的元素最先被移除”的场景。它对外提供了简单的接口，用于管理一组元素，限制只能在栈顶插入或移除元素。

特点

• 后进先出（LIFO）：最后插入的元素最先被移除。
• 底层实现：默认使用 std::deque 作为底层容器，也可以指定 std::vector 或 std::list。
• 操作受限：只允许访问栈顶元素，不能遍历或随机访问。

操作

• push(): 在栈顶添加一个元素。
• pop(): 移除栈顶元素。
• top(): 返回栈顶元素的引用，但不移除它。
• empty(): 检查栈是否为空。
• size(): 返回栈中元素的数量。

1.6. std::string

string 是 C++ 标准库中用于处理字符串的头文件。在 C++ 中，字符串是由字符组成的序列。<string> 头文件提供了 std::string 类，它是对 C 风格字符串的封装，提供了更安全、更易用的字符串操作功能。
特点

• 动态长度：可以自动调整大小，不需要手动管理内存。
• 丰富的功能：提供了字符串拼接、查找、替换、比较、切片等多种操作。
• 支持范围操作：支持迭代器、范围 for 循环等现代 C++ 特性。

操作

• 包含头文件：#include <string>
• 声明：std::string myString;
• 初始化：

  默认构造，空字符串

  std::string s2("Hello");              // 使用 C 风格字符串初始化
  std::string s3(s2);                   // 拷贝构造
  std::string s4(s2, 1, 3);             // 从 s2 的第 1 个字符开始，取 3 个字符
  std::string s5(5, 'a');               // 重复 'a' 5 次，生成 "aaaaa"
  std::string s6{'H', 'e', 'l', 'l', 'o'}; // 列表初始化

• 字符串拼接：使用 + 或 += 运算符。
• 重新赋值字符串：myString.assign()
• 在末尾拼接字符串：myString.append()
• 访问元素：myString.at() 或 myString[]
• 字符串查找：使用 myString.find() 方法。
• 字符串替换：使用 myString.replace() 方法。
• 字符串比较：使用 ==、!=、<、<=、>、>= 运算符。
• 字符串切片：使用 myString.substr() 方法。
• 获取字符串长度：使用 myString.length() 或 myString.size() 方法。
• 清空字符串：使用 myString.clear() 方法。
• 判断字符串是否为空：使用 myString.empty() 方法。

1.7. std::set

set是一个关联容器，它存储了一组唯一的元素，并按照一定的顺序进行排序。set提供了高效的元素查找、插入和删除操作。它是基于红黑树实现的，因此具有对数时间复杂度的查找、插入和删除性能。

特点：

• 元素类型必须可以比较大小。
• 元素类型必须可以被复制和赋值。
• 元素唯一性：std::set 不允许存储重复元素。
• 自动排序：元素会根据其值自动排序。默认情况下，std::set 使用升序排序

操作：

• 包含头文件：#include <set>
• 声明：std::set<元素类型> 容器名;
• 插入元素：容器名.insert(元素);
• 删除元素：容器名.erase(元素); 或 容器名.erase(迭代器);删除指定位置的元素。
• 查找元素：auto it = 容器名.find(元素);，如果找到，it 是指向该元素的迭代器，否则 it 是 容器名.end()。
• 获取元素数量：容器名.size();
• 检查是否为空：empty()
• 清空集合：clear()
• 迭代器：容器名.begin() 和 容器名.end()，用于遍历集合中的元素。

1.8. std::map

map是一种关联容器，用于存储键值对（key-value pairs）。
map 容器中的元素是按照键的顺序自动排序的，这使得它非常适合需要快速查找和有序数据的场景。通过键访问值。

特性

• 键值对：map 存储的是键值对，其中每个键都是唯一的。
• 排序：map 中的元素按照键的顺序自动排序，通常是升序。
• 唯一性：每个键在map 中只能出现一次。
• 键不可修改：键是只读的，不能直接更改，只能通过删除后重新插入实现。
• 双向迭代器：map 提供了双向迭代器，可以向前和向后遍历元素。

操作

• 包含头文件：#include <map>
• 声明：std::map<键类型, 值类型> 容器名;
• 插入元素：容器名.insert(std::make_pair(键, 值)); 或 容器名[键] = 值;
• 删除元素：容器名.erase(键); 或 容器名.erase(迭代器);
• 查找元素：auto it = 容器名.find(键);，如果找到，it 是指向该键的迭代器，否则 it 是 容器名.end()。

2. 迭代器（iterators）

在C++ STL中，迭代器（Iterator） 是一种用于访问容器中元素的对象。通过迭代器，你可以逐个遍历容器中的元素，而不需要关心底层数据结构的具体实现。迭代器可以被视为指向容器中元素的指针，但它比指针更加灵活和强大。迭代器可以用于访问、修改容器中的元素，并且可以与 STL 算法一起使用。
迭代器的基本概念

1. 类型：迭代器的类型取决于容器，例如 std::vector<int>::iterator 是 std::vector<int> 的迭代器类型。
2. 操作：可以使用类似指针的操作符（如 * 解引用，++ 前进）来访问或操作容器中的元素。
3. 容器支持：几乎所有 STL 容器（vector, list, map, set, deque, 等）都支持迭代器。

迭代器的种类

根据功能和操作的不同，迭代器分为以下几种：

迭代器类型	支持的容器	特点和操作
输入迭代器	所有容器	只读，单向遍历，操作符：++，*。
输出迭代器	所有容器	只写，单向遍历，操作符：++，*。
前向迭代器	list	可读可写，单向遍历，支持：++，*。
双向迭代器	list, set, map	可读可写，双向遍历，支持：++，--，*。
随机访问迭代器	vector, deque	可读可写，支持随机访问，支持：++，--，+，-，[]。

迭代器的一些操作：
正向迭代器
所有 STL 容器都支持正向迭代器，通过 begin() 和 end() 获得迭代器范围。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {10, 20, 30, 40};

    // 正向遍历
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " "; // 输出：10 20 30 40
    }

    return 0;
}

逆向迭代器
通过 rbegin() 和 rend() 可以获得逆向迭代器，用于反向遍历。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {10, 20, 30, 40};

    // 反向遍历
    for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
        std::cout << *it << " "; // 输出：40 30 20 10
    }

    return 0;
}

常量迭代器
常量迭代器（const_iterator）用于只读操作，不能通过它修改容器中的元素。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {10, 20, 30, 40};

    // 使用常量迭代器
    for (std::vector<int>::const_iterator it = vec.cbegin(); it != vec.cend(); ++it) {
        std::cout << *it << " "; // 输出：10 20 30 40
    }

    return 0;
}

插入迭代器

插入迭代器用于在迭代过程中将元素插入到容器中，例如 std::back_inserter 或 std::inserter。

#include <iostream>
#include <vector>
#include <iterator>

int main() {
    std::vector<int> vec = {10, 20, 30};
    std::vector<int> result;

    // 使用 back_inserter 将 vec 中的元素复制到 result
    std::copy(vec.begin(), vec.end(), std::back_inserter(result));

    for (int val : result) {
        std::cout << val << " "; // 输出：10 20 30
    }

    return 0;
}

3. 算法(Algorithms)

C++ 标准库中的<algorithm>头文件提供了一组用于操作容器（如数组、向量、列表等）的算法。这些算法包括排序、搜索、复制、比较等，它们是编写高效、可重用代码的重要工具。
<algorithm>头文件定义了一组模板函数，这些函数可以应用于任何类型的容器，只要容器支持迭代器。这些算法通常接受两个或更多的迭代器作为参数，表示操作的起始和结束位置。

非修改序列操作
这些算法不会改变容器或范围中的数据内容。

算法	功能	示例
std::find	查找第一个等于指定值的元素	std::find(begin, end, val)
std::count	统计等于某值的元素个数	std::count(begin, end, val)
std::equal	判断两个范围是否相等	std::equal(b1, e1, b2)
std::mismatch	找出两个范围中第一个不相等的元素对	std::mismatch(b1, e1, b2)
std::search	查找子范围的起始位置	std::search(b1, e1, b2, e2)

---

修改序列操作
这些算法会更改容器或范围中的数据内容。

算法	功能	示例
std::copy	复制一个范围到另一个位置	std::copy(b1, e1, b2)
std::transform	按函数转换范围中的元素	std::transform(b1, e1, b2, func)
std::fill	用指定值填充范围	std::fill(begin, end, val)
std::replace	将范围中指定值替换为新值	std::replace(b, e, old, new)
std::remove	删除指定值并返回新范围的尾部（逻辑删除）	std::remove(b, e, val)

---

排序和排序相关操作
这些算法用于对范围进行排序或处理已排序的数据。

算法	功能	示例
std::sort	对范围进行升序排序	std::sort(begin, end)
std::stable_sort	保持相等元素的相对顺序进行排序	std::stable_sort(begin, end)
std::partition	将范围划分为满足某条件的两部分	std::partition(begin, end, pred)
std::lower_bound	找到第一个不小于指定值的位置（有序范围）	std::lower_bound(begin, end, val)
std::unique	去除相邻重复值（逻辑去重）	std::unique(begin, end)

---

数值操作
这些算法用于处理数值运算。

算法	功能	示例
std::accumulate	累加范围内的值	std::accumulate(b, e, init)
std::inner_product	计算两个范围的内积	std::inner_product(b1, e1, b2, init)
std::partial_sum	计算范围内的部分和	std::partial_sum(b, e, out)
std::adjacent_difference	计算相邻元素的差值	std::adjacent_difference(b, e, out)

常用算法举例：

1. 排序算法sort

   sort(container.begin(), container.end(), compare_function);

   其中 compare_function 是一个可选的比较函数，用于自定义排序方式。

   #include <algorithm>
   #include <vector>
   #include <iostream>
   
   int main() {
       std::vector<int> numbers = {5, 2, 9, 1, 5, 6};
       std::sort(numbers.begin(), numbers.end());
   
       for (int num : numbers) {
           std::cout << num << " ";
       }
       std::cout << std::endl;
   
       return 0;
   }

2. 搜索算法find

   auto it = find(container.begin(), container.end(), value);

   容器中查找与给定值匹配的第一个元素。如果找到，it 将指向匹配的元素；如果没有找到，it 将等于 container.end()。

   #include <algorithm>
   #include <vector>
   #include <iostream>
   
   int main() {
       std::vector<int> numbers = {1, 2, 3, 4, 5};
       auto it = std::find(numbers.begin(), numbers.end(), 3);
   
       if (it != numbers.end()) {
           std::cout << "Found: " << *it << std::endl;
       } else {
           std::cout << "Value not found." << std::endl;
       }
   
       return 0;
   }

3. 复制算法copy
   将一个范围内的元素复制到另一个容器或数组。

   #include <algorithm>
   #include <vector>
   #include <iostream>
   
   int main() {
       std::vector<int> source = {1, 2, 3, 4, 5};
       int destination[5];
       std::copy(source.begin(), source.end(), destination);
   
       for (int i = 0; i < 5; ++i) {
           std::cout << destination[i] << " ";
       }
       std::cout << std::endl;
   
       return 0;
   }

4. 函数对象（Function Objects, Functors）

STL 提供了许多可用于自定义操作的函数对象，比如比较函数、算术操作符等。C++11 引入了 Lambda 表达式，在很多场景中可以替代函数对象。推荐使用 Lambda 表达式

5. 适配器（Adapters）

适配器（Adapters） 是一种将已有的组件（如容器、函数对象、迭代器等）“适配”为另一种形式，以满足特定需求的工具。适配器在 STL 中被广泛使用，是增强泛型编程灵活性的重要部分。

5.1. 容器适配器（Container Adapters）

容器适配器是对某些序列容器（如 std::vector 或 std::deque）的封装，提供了更专注于特定用途的接口。

容器适配器	底层默认容器	功能说明
std::stack	std::deque	提供 LIFO（后进先出）功能
std::queue	std::deque	提供 FIFO（先进先出）功能
std::priority_queue	std::vector	提供基于优先级的队列，默认最大值优先（大顶堆）

5.2. 迭代器适配器（Iterator Adapters）

迭代器适配器用于改变迭代器的行为，如增加步长、改变访问权限等。

迭代器适配器	功能
std::reverse_iterator	反向迭代器
std::back_inserter	在容器末尾插入元素（需支持 push_back 的容器）
std::front_inserter	在容器头部插入元素（需支持 push_front 的容器）
std::inserter	在指定位置插入元素（需支持 insert 的容器）