6、常见STL详解

一、STL简要介绍

C++ STL（Standard Template Library）是C++标准库的一部分，是一组模板类和函数的集合，提供了许多常用的数据结构和算法，包括容器、迭代器、算法等。

STL的组成部分主要有三个：

容器（Containers）：用来存储和管理数据的类模板。包括vector、list、deque、set、map等。
迭代器（Iterators）：提供了一种遍历容器元素的方式，类似于指针，可用来访问容器中的元素。
算法（Algorithms）：提供了许多常用的算法，如查找、排序、合并、逆序等，能够作用于各种容器和迭代器上。

下面分别对STL的三个组成部分进行详细介绍：

1.容器

容器是STL的基础，主要用来存储和管理数据。容器可以分成以下四类：

序列容器：vector、list、deque、array等。这些容器存储元素，并支持随机访问、插入和删除操作。
关联容器：set、multiset、map、multimap等。这些容器存储键值对，并支持按照键进行查找、插入和删除操作。
无序关联容器：unordered_set、unordered_multiset、unordered_map、unordered_multimap等。这些容器与关联容器类似，但是它们没有保证元素的顺序。
容器适配器：stack、queue、priority_queue等。这些容器是在其他容器的基础上实现的，提供了特定的接口。

1、序列容器有以下几种：

vector：动态数组，支持随机访问和在末尾添加或删除元素，但在中间插入或删除元素代价较高。
list：双向链表，支持在任意位置插入或删除元素，但不支持随机访问。
deque：双端队列，支持在两端添加或删除元素，也支持随机访问。
array：固定大小的数组，支持随机访问，但不能改变大小。
forward_list：单向链表，与list类似，但只能从前往后遍历。

这些序列容器都提供了类似的操作接口，如访问元素、插入元素、删除元素等。此外，它们还提供了一些特定的操作，如vector和deque支持在任意位置插入或删除元素，而list和forward_list则支持将一个容器的元素移动到另一个容器中。

2、关联容器有以下几种：

set：集合，存储一组唯一不重复的元素，并按照元素大小自动排序。
multiset：多重集合，与set类似，但允许存储重复的元素。
map：映射，存储一组键值对，并按照键的大小自动排序。
multimap：多重映射，与map类似，但允许存储重复的键值对。

这些关联容器都基于红黑树实现，因此具有较高的效率和稳定的性能。它们提供了一系列的操作函数，如插入、查找、删除、遍历等，且大部分操作的时间复杂度为O(log n)。此外，关联容器还提供了一些特定的算法，如合并、交集、差集等，以方便用户进行集合操作。

3、无序关联容器有以下几种：

unordered_set：无序集合，存储一组唯一不重复的元素，并按照哈希值自动排序。
unordered_multiset：无序多重集合，与unordered_set类似，但允许存储重复的元素。
unordered_map：无序映射，存储一组键值对，并按照哈希值自动排序。
unordered_multimap：无序多重映射，与unordered_map类似，但允许存储重复的键值对。

这些无序关联容器都基于哈希表实现，因此具有较高的效率和稳定的性能。它们提供了一系列的操作函数，如插入、查找、删除、遍历等，且大部分操作的时间复杂度为O(1)。此外，无序关联容器也提供了一些特定的算法，如桶排序、哈希冲突解决等，以方便用户进行集合操作。

4、容器适配器有以下两种：

stack：栈，基于deque、list或vector实现。
queue：队列，基于deque或list实现。
priority_queue：优先队列，基于vector或deque实现。

这些容器适配器提供了一些操作函数，如入栈、出栈、入队、出队等。它们通常用于实现特定的数据结构，如深度优先搜索、广度优先搜索等算法。需要注意的是，栈和队列都是线性数据结构，并且具有不同的访问方式和调用规则。

2.迭代器

迭代器是STL中的一个重要概念，它是一种抽象的概念，类似于指针，可用来访问容器中的元素。STL中的迭代器分为五类：

输入迭代器（Input Iterator）：只能用来读取容器中的元素，不能修改。
输出迭代器（Output Iterator）：只能用来写入容器中的元素，不能读取。
前向迭代器（Forward Iterator）：可以向前遍历容器中的元素，但只能遍历一次。
双向迭代器（Bidirectional Iterator）：可以向前或向后遍历容器中的元素。
随机访问迭代器（Random Access Iterator）：可以任意跳转和遍历容器中的元素，类似于指针。

迭代器的用法也比较简单，可以使用自增运算符（++）进行遍历，也可以使用解引用运算符（*）访问元素。迭代器还提供了各种操作，如比较、移动、递增等。

3.算法

算法是STL中最重要的部分之一，它提供了大量的常用算法，如排序、查找、复制、合并、逆序等。这些算法可以作用于各种容器和迭代器上，使用方便、效率高。常见的算法有：

find：在容器中查找指定元素。
sort：对容器中的元素进行排序。
reverse：逆序容器中的元素。
copy：将容器中的元素复制到另一个容器中。
merge：将两个有序容器合并为一个有序容器。

使用算法时，只需要将容器或迭代器作为参数传递给算法即可，算法会自动根据容器或迭代器的类型进行相应的操作。

STL的优点：

代码复用性高：STL提供了大量的模板类和函数，可以大大减少代码量和开发时间。
算法效率高：STL提供了许多高效的算法和数据结构，可以大大提高程序的运行效率。
可移植性好：STL是C++标准库的一部分，可以在各种平台上运行，不需要考虑平台差异。
可扩展性强：STL提供了很好的接口和抽象，可以方便地扩展和修改。

总之，STL是C++中非常重要的一个部分，使用STL可以大大提高程序的效率和可维护性。对于C++的学习者来说，熟练掌握STL是非常重要的一步。

二、Vector的详细介绍

vector是C++ STL中最常用的容器之一，它是一个动态数组，能够自动扩容并支持随机访问。下面详细介绍一下vector的特点和使用方法。

1.特点

动态数组：vector内部使用动态数组来存储元素，因此支持随机访问，并且可以动态扩容以容纳更多的元素。
自动扩容：当vector内部的数组不够存储元素时，会自动分配一段更大的内存，并将原有的元素复制到新的内存中，再释放原来的内存。这个过程是自动进行的，对于程序员来说是透明的。
支持任意类型元素：vector支持存储任意类型的元素，包括内置类型、自定义类型和指针类型等。
尾部插入和删除高效：由于vector内部使用动态数组，因此在尾部插入和删除元素时效率很高，时间复杂度为常数级别。
随机访问高效：由于vector内部使用数组，因此可以通过下标访问元素，时间复杂度为常数级别。

2.使用方法

使用vector需要包含头文件< vector >，定义一个vector对象，指定存储的元素类型。下面是一个简单的例子：

C++
#include <vector>
#include <iostream>

using namespace std;

int main()
{
    vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);

    for (int i = 0; i < vec.size(); i++)
    {
        cout << vec[i] << " ";
    }

    return 0;
}

输出结果为：1 2 3。

上述代码中，定义了一个存储int类型元素的vector对象vec。使用push_back()函数向vec中添加元素，使用下标访问元素并输出。注意，vector中的元素是从0开始编号的，即第一个元素的下标为0。

3.vector类的所有成员函数及操作：

1、构造函数和析构函数

vector类提供了多个构造函数和析构函数，可以根据需要选择不同的构造函数来创建vector对象。

vector()：默认构造函数，创建一个空的vector对象。
vector(n)：创建一个包含n个元素的vector对象，元素的值都是类型的默认值。
vector(n, val)：创建一个包含n个元素的vector对象，每个元素的值都是val。
vector(const vector& x)：拷贝构造函数，创建一个与x相同的vector对象。
vector(iterator first, iterator last)：使用[first, last)区间内的元素创建一个新的vector对象。

vector类的析构函数会自动释放vector对象内部使用的内存。

2、容器大小

size()：返回vector中元素的个数。
max_size()：返回vector中最多可以容纳的元素数量。
resize(n)：将vector的大小改变为n，如果n比当前大小小，则多余的元素会被删除；如果n比当前大小大，则会自动添加默认值的元素，或者使用指定的值val来填充。
resize(n, val)：将vector的大小改变为n，并使用指定的值val来填充。
capacity()：返回vector内部当前分配的存储空间的大小，也就是可以容纳的元素的最大数量。
reserve(n)：将vector的容量改变为n，如果n比当前容量小，则不会有任何效果；如果n比当前容量大，则会重新分配内存，并将vector的容量增加到n。

3、元素访问

operator[]：通过下标访问vector中的元素，返回对应位置的元素的引用。
at()：通过下标访问vector中的元素，与operator[]类似，但是会进行越界检查，如果下标超出了范围，则会抛出异常。
front()：返回vector中的第一个元素的引用。
back()：返回vector中的最后一个元素的引用。
data()：返回指向vector中首元素的指针。

4、元素插入和删除

push_back(val)：在vector的尾部插入一个元素，其值为val。
pop_back()：删除vector的最后一个元素。
insert(pos, val)：在指定位置pos之前插入一个元素，其值为val，返回插入元素的迭代器。
insert(pos, n, val)：在指定位置pos之前插入n个元素，每个元素的值都是val，返回插入第一个元素的迭代器。
insert(pos, first, last)：在指定位置pos之前插入区间[first, last)内的所有元素，返回插入第一个元素的迭代器。
erase(pos)：删除指定位置pos上的元素，返回被删除元素的后一个元素的迭代器。
erase(first, last)：删除[first, last)区间内的所有元素，返回被删除元素的后一个元素的迭代器。
clear()：删除vector中的所有元素，使vector变为空的。

5、vector的比较

operator==：判断两个vector是否相等，即是否包含相同的元素。
operator!=：判断两个vector是否不相等。
operator<：按字典序比较两个vector，返回true如果第一个vector小于第二个vector，否则返回false。

6、其他操作

swap()：交换两个vector对象中的元素。
emplace()：在指定位置上构造一个元素，并将其插入到vector中。
emplace_back()：在vector的尾部构造一个元素，并将其插入到vector中。
shrink_to_fit()：要求vector减少其内部存储，以适应其当前元素数量。
get_allocator()：返回与vector关联的内存分配器的副本。

总结：

vector是一个非常常用的STL容器，它提供了丰富的成员函数和操作，可以用来管理动态数组。vector中的元素是连续存储的，可以通过下标访问，也可以通过迭代器来访问。它还提供了元素的插入、删除、大小调整等操作，方便用户进行动态管理。在使用vector时，需要注意其内存的管理和使用，以避免内存泄漏和访问越界等问题。

下面是一个使用 STL vector 的示例代码，其中包括创建 vector、添加元素、遍历 vector、访问 vector 中的元素等操作：

C++
#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 创建 vector 容器
    vector<int> v;

    // 向 vector 中添加元素
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);

    // 遍历 vector 中的元素
    cout << "Vector elements: ";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;

    // 修改 vector 中的元素
    v[1] = 4;

    // 访问 vector 中的元素
    cout << "Vector element at index 2: " << v.at(2) << endl;

    // 删除 vector 中的元素
    v.erase(v.begin() + 1);

    // 检查 vector 是否为空
    if (v.empty()) {
        cout << "Vector is empty." << endl;
    } else {
        cout << "Vector is not empty." << endl;
    }

    // 获取 vector 容器的大小
    cout << "Vector size: " << v.size() << endl;

    return 0;
}

运行上述代码后，输出结果应该如下：

C++
Vector elements: 1 2 3 
Vector element at index 2: 3
Vector is not empty.
Vector size: 2

可以看到，代码创建了一个空的 vector 容器，并使用 push_back() 方法向其中添加了三个整数。然后使用循环遍历 vector 中的元素，将它们打印到控制台上。接下来，代码使用 at() 方法访问 vector 中的元素，并将其中一个元素的值修改为 4。然后使用 erase() 方法删除 vector 中的第二个元素，再次检查 vector 是否为空，最后使用 size() 方法获取 vector 的大小并将其打印到控制台上。

三、List的详细介绍

STL（标准模板库）中的 list（双向链表）是一种常用的数据结构，提供了许多方法来操作列表中的元素。以下是 C++ STL list 的所有方法介绍：

1.构造函数

list(): 创建一个空的 list。
list(size_type n, const value_type& val = value_type()): 创建一个包含 n 个元素的 list，并将它们初始化为 val。
list(const list& x): 创建一个新 list，并将其初始化为 x。
list(list&& x): 创建一个新 list，并使用移动语义将其初始化为 x。
list(initializer_list<value_type> il): 创建一个包含初始化列表中元素的 list。

2.迭代器

begin(): 返回指向 list 第一个元素的迭代器。
end(): 返回指向 list 末尾元素下一个位置的迭代器。
rbegin(): 返回指向 list 最后一个元素的反向迭代器。
rend(): 返回指向 list 头部（首个元素前一个位置）的反向迭代器。

3.容量

empty(): 如果 list 为空，则返回 true；否则返回 false。
size(): 返回 list 中元素的数量。
max_size(): 返回 list 中元素的最大数量。

4.访问元素

front(): 返回 list 中第一个元素的引用。
back(): 返回 list 中最后一个元素的引用。

5.修改容器

assign(): 用新元素替换 list 中的元素。
push_back(): 在 list 的末尾添加一个元素。
pop_back(): 移除 list 的末尾元素。
push_front(): 在 list 的开头添加一个元素。
pop_front(): 移除 list 的开头元素。
insert(): 在指定的位置插入一个或多个元素。
erase(): 移除 list 中的一个或多个元素。
swap(): 交换两个 list 中的元素。
resize(): 改变 list 的大小。
clear(): 移除 list 中的所有元素。

6.操作

splice(): 将元素从一个 list 移动到另一个 list 中。
remove(): 移除 list 中所有等于指定值的元素。
remove_if(): 移除 list 中所有满足指定条件的元素。
unique(): 移除 list 中所有连续的重复元素。
merge(): 将两个已排序的 list 合并为一个已排序的 list。
sort(): 将 list 中的元素排序。
reverse(): 反转 list 中的元素。

下面是一个使用 STL list 的示例代码，其中包括创建 list、添加元素、遍历 list、访问 list 中的元素等操作：

C++
#include <iostream>
#include <list>
using namespace std;
int main() {
    // 创建 list 容器
    list<int> l;

    // 向 list 中添加元素
    l.push_back(1);
    l.push_back(2);
    l.push_back(3);

    // 遍历 list 中的元素
    cout << "List elements: ";
    for (auto it = l.begin(); it != l.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;

    // 修改 list 中的元素
    auto it = l.begin();
    it++;
    l.insert(it, 4);

    // 访问 list 中的元素
    cout << "List element at index 2: " << *next(l.begin(), 2) << endl;

    // 删除 list 中的元素
    l.pop_front();

    // 检查 list 是否为空
    if (l.empty()) {
        cout << "List is empty." << endl;
    } else {
        cout << "List is not empty." << endl;
    }

    // 获取 list 容器的大小
    cout << "List size: " << l.size() << endl;

    return 0;
}

运行上述代码后，输出结果应该如下：

C++
List elements: 1 2 3 
List element at index 2: 3
List is not empty.
List size: 2

可以看到，代码创建了一个空的 list 容器，并使用 push_back() 方法向其中添加了三个整数。然后使用循环遍历 list 中的元素，将它们打印到控制台上。接下来，代码使用 insert() 方法在 list 中添加一个新元素，并使用 next() 方法访问 list 中的第三个元素。然后使用 pop_front() 方法删除 list 中的第一个元素，再次检查 list 是否为空，最后使用 size() 方法获取 list 的大小并将其打印到控制台上。

四、deque的详细介绍

STL（标准模板库）中的 deque（双端队列）是一种常用的数据结构，提供了许多方法来操作队列中的元素。以下是 C++ STL deque 的所有方法介绍：

1.构造函数

deque(): 创建一个空的 deque。
deque(size_type n, const value_type& val = value_type()): 创建一个包含 n 个元素的 deque，并将它们初始化为 val。
deque(const deque& x): 创建一个新 deque，并将其初始化为 x。
deque(deque&& x): 创建一个新 deque，并使用移动语义将其初始化为 x。
deque(initializer_list<value_type> il): 创建一个包含初始化列表中元素的 deque。

2.迭代器

begin(): 返回指向 deque 第一个元素的迭代器。
end(): 返回指向 deque 末尾元素下一个位置的迭代器。
rbegin(): 返回指向 deque 最后一个元素的反向迭代器。
rend(): 返回指向 deque 头部（首个元素前一个位置）的反向迭代器。

3.容量

empty(): 如果 deque 为空，则返回 true；否则返回 false。
size(): 返回 deque 中元素的数量。
max_size(): 返回 deque 中元素的最大数量。
resize(): 改变 deque 的大小。

4.访问元素

at(): 返回指定位置元素的引用。
front(): 返回 deque 中第一个元素的引用。
back(): 返回 deque 中最后一个元素的引用。

5.修改容器

assign(): 用新元素替换 deque 中的元素。
push_back(): 在 deque 的末尾添加一个元素。
pop_back(): 移除 deque 的末尾元素。
push_front(): 在 deque 的开头添加一个元素。
pop_front(): 移除 deque 的开头元素。
insert(): 在指定的位置插入一个或多个元素。
erase(): 移除 deque 中的一个或多个元素。
swap(): 交换两个 deque 中的元素。
clear(): 移除 deque 中的所有元素。

6.操作

emplace(): 在指定位置构造新元素。
emplace_front(): 在 deque 的开头构造新元素。
emplace_back(): 在 deque 的末尾构造新元素。
resize(): 改变 deque 的大小，并用指定值填充新的位置。
shrink_to_fit(): 将 deque 的容量减小到与元素数量相同。
push_back() / pop_front(): 在 deque 的末尾添加/移除一个元素，以实现队列的功能。
push_front() / pop_back(): 在 deque 的开头添加/移除一个元素，以实现栈的功能。

下面是一个使用 STL deque 的示例代码，其中包括创建 deque、添加元素、遍历 deque、访问 deque 中的元素等操作：

C++
#include <iostream>
#include <deque>
using namespace std;
int main() {
    // 创建 deque 容器
    deque<int> d;

    // 向 deque 中添加元素
    d.push_back(1);
    d.push_back(2);
    d.push_front(3);

    // 遍历 deque 中的元素
    cout << "Deque elements: ";
    for (auto it = d.begin(); it != d.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;

    // 修改 deque 中的元素
    d[1] = 4;

    // 访问 deque 中的元素
    cout << "Deque element at index 2: " << d.at(2) << endl;

    // 删除 deque 中的元素
    d.pop_front();

    // 检查 deque 是否为空
    if (d.empty()) {
        cout << "Deque is empty." << endl;
    } else {
        cout << "Deque is not empty." << endl;
    }

    // 获取 deque 容器的大小
    cout << "Deque size: " << d.size() << endl;

    return 0;
}

运行上述代码后，输出结果应该如下：

C++
Deque elements: 3 1 2 
Deque element at index 2: 2
Deque is not empty.
Deque size: 2

可以看到，代码创建了一个空的 deque 容器，并使用 push_back() 和 push_front() 方法向其中添加了三个整数。然后使用循环遍历 deque 中的元素，将它们打印到控制台上。接下来，代码使用数组访问方式和 at() 方法修改和访问 deque 中的元素。然后使用 pop_front() 方法删除 deque 中的第一个元素，再次检查 deque 是否为空，最后使用 size() 方法获取 deque 的大小并将其打印到控制台上。

五、Stack的详细介绍

STL Stack 是一种基于 LIFO（Last In First Out）模式的容器，它允许用户在堆栈的顶部添加和删除元素。以下是 STL Stack 中可用的所有方法：

1.构造与析构

stack(): 创建一个空栈。
stack(const stack& other): 复制一个栈。
~stack(): 销毁栈。

2.元素访问

top(): 返回栈顶元素的引用。

3.容量

empty(): 如果栈为空则返回 true，否则返回 false。
size(): 返回栈中元素的个数。

4.修改容器

push(const T& element): 在栈顶添加元素。
pop(): 从栈顶移除元素。
swap(stack& other): 交换两个栈的元素。

下面是一个使用 STL stack 的示例代码，其中包括创建 stack、添加元素、遍历 stack、访问 stack 中的元素等操作：

C++
#include <iostream>
#include <stack>
using namespace std;
int main() {
    // 创建 stack 容器
    stack<int> s;

    // 向 stack 中添加元素
    s.push(1);
    s.push(2);
    s.push(3);

    // 遍历 stack 中的元素
    cout << "Stack elements: ";
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;

    // 检查 stack 是否为空
    if (s.empty()) {
        cout << "Stack is empty." << endl;
    } else {
        cout << "Stack is not empty." << endl;
    }

    // 获取 stack 容器的大小
    cout << "Stack size: " << s.size() << endl;

    return 0;
}

运行上述代码后，输出结果应该如下：

C++
Stack elements: 3 2 1 
Stack is empty.
Stack size: 0

可以看到，代码创建了一个空的 stack 容器，并使用 push() 方法向其中添加了三个整数。然后使用 while 循环遍历 stack 中的元素，将它们打印到控制台上。接下来，代码使用 empty() 方法检查 stack 是否为空，并使用 size() 方法获取 stack 的大小并将其打印到控制台上。最后，由于 while 循环中已经将 stack 中的所有元素弹出了，所以在打印 stack 的大小时，应该输出 0。

六、Queue的详细介绍

STL Queue 是一种基于 FIFO（First In First Out）模式的容器，它允许用户在队列的末尾添加元素，在队列的开头删除元素。以下是 STL Queue 中可用的所有方法：

1.构造与析构

queue(): 创建一个空队列。
queue(const queue& other): 复制一个队列。
~queue(): 销毁队列。

2.元素访问

front(): 返回队列的第一个元素的引用。
back(): 返回队列的最后一个元素的引用。

3.容量

empty(): 如果队列为空则返回 true，否则返回 false。
size(): 返回队列中元素的个数。

4.修改容器

push(const T& element): 在队列的末尾添加元素。
pop(): 从队列的开头删除元素。
swap(queue& other): 交换两个队列的元素。

下面是一个使用 STL queue 的示例代码，其中包括创建 queue、添加元素、遍历 queue、访问 queue 中的元素等操作：

C++
#include <iostream>
#include <queue>
using namespace std;
int main() {
    // 创建 queue 容器
    queue<int> q;

    // 向 queue 中添加元素
    q.push(1);
    q.push(2);
    q.push(3);

    // 遍历 queue 中的元素
    cout << "Queue elements: ";
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;

    // 检查 queue 是否为空
    if (q.empty()) {
        cout << "Queue is empty." << endl;
    } else {
        cout << "Queue is not empty." << endl;
    }

    // 获取 queue 容器的大小
    cout << "Queue size: " << q.size() << endl;

    return 0;
}

运行上述代码后，输出结果应该如下：

Text Only
Queue elements: 1 2 3 
Queue is empty.
Queue size: 0

可以看到，代码创建了一个空的 queue 容器，并使用 push() 方法向其中添加了三个整数。然后使用 while 循环遍历 queue 中的元素，将它们打印到控制台上。接下来，代码使用 empty() 方法检查 queue 是否为空，并使用 size() 方法获取 queue 的大小并将其打印到控制台上。最后，由于 while 循环中已经将 queue 中的所有元素弹出了，所以在打印 queue 的大小时，应该输出 0。

七、Set的详细介绍

STL Set 是一种基于红黑树的关联式容器，它可以存储一组按顺序排序的、独特的元素。以下是 STL Set 中可用的所有方法：

1.构造与析构

set(): 创建一个空的 set 容器。
set(const set& other): 复制一个 set 容器。
set(set&& other) noexcept: 移动构造函数。
set(initializer_list<T> init): 使用初始化列表创建一个 set 容器。
~set(): 销毁 set 容器。

2.迭代器

begin(): 返回指向 set 容器中第一个元素的迭代器。
end(): 返回指向 set 容器中最后一个元素后面的迭代器。
rbegin(): 返回指向 set 容器中最后一个元素的反向迭代器。
rend(): 返回指向 set 容器中第一个元素前面的反向迭代器。

3.容器大小

empty(): 如果 set 容器为空则返回 true，否则返回 false。
size(): 返回 set 容器中元素的数量。
max_size(): 返回 set 容器可以包含的最大元素数。

4.插入和删除元素

insert(): 在 set 容器中插入元素。
emplace(): 在 set 容器中就地构造元素。
erase(): 从 set 容器中删除一个元素或一段元素。
clear(): 删除 set 容器中的所有元素。

5.查找元素

find(): 查找指向特定元素的迭代器。
count(): 返回 set 容器中等于特定元素的元素数量。
lower_bound(): 返回第一个不小于给定值的元素的迭代器。
upper_bound(): 返回第一个大于给定值的元素的迭代器。
equal_range(): 返回指向与给定值相等的元素范围的两个迭代器。

下面是一个使用 STL set 的示例代码，其中包括创建 set、添加元素、遍历 set、访问 set 中的元素等操作：

C++
#include <iostream>
#include <set>
using namespace std;
int main() {
    // 创建 set 容器
    set<int> s;

    // 向 set 中添加元素
    s.insert(2);
    s.insert(1);
    s.insert(3);

    // 遍历 set 中的元素
    cout << "Set elements: ";
    for (auto it = s.begin(); it != s.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // 检查 set 是否为空
    if (s.empty()) {
        cout << "Set is empty." << endl;
    } else {
        cout << "Set is not empty." << endl;
    }

    // 获取 set 容器的大小
    cout << "Set size: " << s.size() << endl;

    // 在 set 中查找元素
    int x = 2;
    if (s.find(x) != s.end()) {
        cout << x << " is found in the set." << endl;
    } else {
        cout << x << " is not found in the set." << endl;
    }

    // 从 set 中删除元素
    s.erase(2);
    cout << "Set elements after erasing 2: ";
    for (auto it = s.begin(); it != s.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}

运行上述代码后，输出结果应该如下：

C++
Set elements: 1 2 3 
Set is not empty.
Set size: 3
2 is found in the set.
Set elements after erasing 2: 1 3 

可以看到，代码创建了一个空的 set 容器，并使用 insert() 方法向其中添加了三个整数。然后使用 for 循环遍历 set 中的元素，将它们打印到控制台上。接下来，代码使用 empty() 方法检查 set 是否为空，并使用 size() 方法获取 set 的大小并将其打印到控制台上。然后使用 find() 方法在 set 中查找元素 2，如果找到则打印它被找到，否则打印它未被找到。最后，代码使用 erase() 方法从 set 中删除元素 2，并使用 for 循环遍历 set 中的元素，将它们打印到控制台上。

八、Multiset 的详细介绍

STL Multiset 是一种基于红黑树的关联式容器，与 Set 容器不同的是，Multiset 容器中可以存储相同的元素。以下是 STL Multiset 中可用的所有方法：

1.构造与析构

multiset(): 创建一个空的 multiset 容器。
multiset(const multiset& other): 复制一个 multiset 容器。
multiset(multiset&& other) noexcept: 移动构造函数。
multiset(initializer_list<T> init): 使用初始化列表创建一个 multiset 容器。
~multiset(): 销毁 multiset 容器。

2.迭代器

begin(): 返回指向 multiset 容器中第一个元素的迭代器。
end(): 返回指向 multiset 容器中最后一个元素后面的迭代器。
rbegin(): 返回指向 multiset 容器中最后一个元素的反向迭代器。
rend(): 返回指向 multiset 容器中第一个元素前面的反向迭代器。

3.容器大小

empty(): 如果 multiset 容器为空则返回 true，否则返回 false。
size(): 返回 multiset 容器中元素的数量。
max_size(): 返回 multiset 容器可以包含的最大元素数。

4.插入和删除元素

insert(): 在 multiset 容器中插入元素。
emplace(): 在 multiset 容器中就地构造元素。
erase(): 从 multiset 容器中删除一个元素或一段元素。
clear(): 删除 multiset 容器中的所有元素。

5.查找元素

find(): 查找指向特定元素的迭代器。
count(): 返回 multiset 容器中等于特定元素的元素数量。
lower_bound(): 返回第一个不小于给定值的元素的迭代器。
upper_bound(): 返回第一个大于给定值的元素的迭代器。
equal_range(): 返回指向与给定值相等的元素范围的两个迭代器。

下面是一个使用 STL multiset 的示例代码，其中包括创建 multiset、添加元素、遍历 multiset、访问 multiset 中的元素等操作：

C++
#include <iostream>
#include <set>
using namespace std;
int main() {
    // 创建 multiset 容器
    multiset<int> ms;

    // 向 multiset 中添加元素
    ms.insert(2);
    ms.insert(1);
    ms.insert(3);
    ms.insert(2);

    // 遍历 multiset 中的元素
    cout << "Multiset elements: ";
    for (auto it = ms.begin(); it != ms.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // 检查 multiset 是否为空
    if (ms.empty()) {
        cout << "Multiset is empty." << endl;
    } else {
        cout << "Multiset is not empty." << endl;
    }

    // 获取 multiset 容器的大小
    cout << "Multiset size: " << ms.size() << endl;

    // 计算 multiset 中某个元素的个数
    int x = 2;
    cout << x << " occurs " << ms.count(x) << " times in the multiset." << endl;

    // 在 multiset 中查找元素
    if (ms.find(x) != ms.end()) {
        cout << x << " is found in the multiset." << endl;
    } else {
        cout << x << " is not found in the multiset." << endl;
    }

    // 从 multiset 中删除元素
    ms.erase(2);
    cout << "Multiset elements after erasing 2: ";
    for (auto it = ms.begin(); it != ms.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}

运行上述代码后，输出结果应该如下：

Text Only
Multiset elements: 1 2 2 3 
Multiset is not empty.
Multiset size: 4
2 occurs 2 times in the multiset.
2 is found in the multiset.
Multiset elements after erasing 2: 1 3 

可以看到，代码创建了一个空的 multiset 容器，并使用 insert() 方法向其中添加了四个整数，其中有两个元素的值为 2。然后使用 for 循环遍历 multiset 中的元素，将它们打印到控制台上。接下来，代码使用 empty() 方法检查 multiset 是否为空，并使用 size() 方法获取 multiset 的大小并将其打印到控制台上。然后使用 count() 方法计算 multiset 中元素 2 的个数，并将其打印到控制台上。接着使用 find() 方法在 multiset 中查找元素 2，如果找到则打印它被找到，否则打印它未被找到。最后，代码使用 erase() 方法从 multiset 中删除元素 2，并使用 for 循环遍历 multiset 中的元素，将它们打印出来。

九、Map的详细介绍

STL Map 是一种关联式容器，可以将一组键值对存储为一个元素，并根据键来访问元素。以下是 STL Map 中可用的所有方法：

1.构造与析构

map(): 创建一个空的 map 容器。
map(const map& other): 复制一个 map 容器。
map(map&& other) noexcept: 移动构造函数。
map(initializer_list<T> init): 使用初始化列表创建一个 map 容器。
~map(): 销毁 map 容器。

2.迭代器

begin(): 返回指向 map 容器中第一个元素的迭代器。
end(): 返回指向 map 容器中最后一个元素后面的迭代器。
rbegin(): 返回指向 map 容器中最后一个元素的反向迭代器。
rend(): 返回指向 map 容器中第一个元素前面的反向迭代器。

3.容器大小

empty(): 如果 map 容器为空则返回 true，否则返回 false。
size(): 返回 map 容器中元素的数量。
max_size(): 返回 map 容器可以包含的最大元素数。

4.插入和删除元素

insert(): 在 map 容器中插入元素。
emplace(): 在 map 容器中就地构造元素。
erase(): 从 map 容器中删除一个元素或一段元素。
clear(): 删除 map 容器中的所有元素。

5.查找元素

find(): 查找指向特定元素的迭代器。
count(): 返回 map 容器中等于特定键的元素数量。
lower_bound(): 返回第一个不小于给定键的元素的迭代器。
upper_bound(): 返回第一个大于给定键的元素的迭代器。
equal_range(): 返回指向与给定键相等的元素范围的两个迭代器。

6.访问元素

operator[]: 访问 map 容器中特定键对应的值。

下面是一个使用 STL map 的示例代码，其中包括创建 map、添加元素、遍历 map、访问 map 中的元素等操作：

C++
#include <iostream>
#include <map>
using namespace std;
int main() {
    // 创建 map 容器
    map<string, int> mp;

    // 向 map 中添加元素
    mp["Alice"] = 23;
    mp["Bob"] = 19;
    mp["Charlie"] = 30;

    // 遍历 map 中的元素
    cout << "Map elements: ";
    for (auto it = mp.begin(); it != mp.end(); ++it) {
        cout << it->first << " is " << it->second << " years old. ";
    }
    cout << endl;

    // 检查 map 是否为空
    if (mp.empty()) {
        cout << "Map is empty." << endl;
    } else {
        cout << "Map is not empty." << endl;
    }

    // 获取 map 容器的大小
    cout << "Map size: " << mp.size() << endl;

    // 在 map 中查找元素
    string name = "Bob";
    if (mp.find(name) != mp.end()) {
        cout << name << " is found in the map and is " << mp[name] << " years old." << endl;
    } else {
        cout << name << " is not found in the map." << endl;
    }

    // 从 map 中删除元素
    mp.erase(name);
    cout << "Map elements after erasing " << name << ": ";
    for (auto it = mp.begin(); it != mp.end(); ++it) {
        cout << it->first << " is " << it->second << " years old. ";
    }
    cout << endl;

    return 0;
}

运行上述代码后，输出结果应该如下：

Text Only
Map elements: Alice is 23 years old. Bob is 19 years old. Charlie is 30 years old. 
Map is not empty.
Map size: 3
Bob is found in the map and is 19 years old.
Map elements after erasing Bob: Alice is 23 years old. Charlie is 30 years old. 

可以看到，代码创建了一个空的 map 容器，并使用下标运算符向其中添加了三个键值对，其中键为字符串，值为整数。然后使用 for 循环遍历 map 中的键值对，将它们打印到控制台上。接下来，代码使用 empty() 方法检查 map 是否为空，并使用 size() 方法获取 map 的大小并将其打印到控制台上。然后使用 find() 方法在 map 中查找键为 "Bob" 的元素，如果找到则打印它的值，否则打印它未被找到。最后，代码使用 erase() 方法从 map 中删除键为 "Bob" 的元素，并使用 for 循环遍历 map 中的键值对，将它们打印到控制台上。

十、Multimap 的详细介绍

STL multimap 是一种关联式容器，可以将多个键值对存储为一个元素，并根据键来访问元素。以下是 STL multimap 中可用的所有方法：

1.构造与析构

multimap(): 创建一个空的 multimap 容器。
multimap(const multimap& other): 复制一个 multimap 容器。
multimap(multimap&& other) noexcept: 移动构造函数。
multimap(initializer_list<T> init): 使用初始化列表创建一个 multimap 容器。
~multimap(): 销毁 multimap 容器。

2.迭代器

begin(): 返回指向 multimap 容器中第一个元素的迭代器。
end(): 返回指向 multimap 容器中最后一个元素后面的迭代器。
rbegin(): 返回指向 multimap 容器中最后一个元素的反向迭代器。
rend(): 返回指向 multimap 容器中第一个元素前面的反向迭代器。

3.容器大小

empty(): 如果 multimap 容器为空则返回 true，否则返回 false。
size(): 返回 multimap 容器中元素的数量。
max_size(): 返回 multimap 容器可以包含的最大元素数。

4.插入和删除元素

insert(): 在 multimap 容器中插入元素。
emplace(): 在 multimap 容器中就地构造元素。
erase(): 从 multimap 容器中删除一个元素或一段元素。
clear(): 删除 multimap 容器中的所有元素。

5.查找元素

find(): 查找指向特定元素的迭代器。
count(): 返回 multimap 容器中等于特定键的元素数量。
lower_bound(): 返回第一个不小于给定键的元素的迭代器。
upper_bound(): 返回第一个大于给定键的元素的迭代器。
equal_range(): 返回指向与给定键相等的元素范围的两个迭代器。

6.访问元素

begin(): 返回指向 multimap 容器中第一个元素的迭代器。
end(): 返回指向 multimap 容器中最后一个元素后面的迭代器。
operator[]: 访问 multimap 容器中特定键对应的值。

下面是一个使用 STL multimap 的示例代码，其中包括创建 multimap、添加元素、遍历 multimap、访问 multimap 中的元素等操作：

C++
#include <iostream>
#include <map>
using namespace std;
int main() {
    // 创建 multimap 容器
    multimap<string, int> mp;

    // 向 multimap 中添加元素
    mp.insert(make_pair("Alice", 23));
    mp.insert(make_pair("Bob", 19));
    mp.insert(make_pair("Charlie", 30));
    mp.insert(make_pair("Alice", 20));

    // 遍历 multimap 中的元素
    cout << "Multimap elements: ";
    for (auto it = mp.begin(); it != mp.end(); ++it) {
        cout << it->first << " is " << it->second << " years old. ";
    }
    cout << endl;

    // 检查 multimap 是否为空
    if (mp.empty()) {
        cout << "Multimap is empty." << endl;
    } else {
        cout << "Multimap is not empty." << endl;
    }

    // 获取 multimap 容器的大小
    cout << "Multimap size: " << mp.size() << endl;

    // 在 multimap 中查找元素
    string name = "Alice";
    auto range = mp.equal_range(name);
    if (range.first != mp.end()) {
        cout << name << " is found in the multimap: ";
        for (auto it = range.first; it != range.second; ++it) {
            cout << it->second << " ";
        }
        cout << endl;
    } else {
        cout << name << " is not found in the multimap." << endl;
    }

    // 从 multimap 中删除元素
    mp.erase(name);
    cout << "Multimap elements after erasing " << name << ": ";
    for (auto it = mp.begin(); it != mp.end(); ++it) {
        cout << it->first << " is " << it->second << " years old. ";
    }
    cout << endl;

    return 0;
}

运行上述代码后，输出结果应该如下：

C++
Multimap elements: Alice is 23 years old. Alice is 20 years old. Bob is 19 years old. Charlie is 30 years old. 
Multimap is not empty.
Multimap size: 4
Alice is found in the multimap: 23 20 
Multimap elements after erasing Alice: Bob is 19 years old. Charlie is 30 years old. 

可以看到，代码创建了一个空的 multimap 容器，并使用 insert() 方法向其中添加了四个键值对，其中键为字符串，值为整数。然后使用 for 循环遍历 multimap 中的键值对，将它们打印到控制台上。接下来，代码使用 empty() 方法检查 multimap 是否为空，并使用 size() 方法获取 multimap 的大小并将其打印到控制台上。

十一、STL常用算法

STL 算法是基于迭代器（iterator）的，它们可以用于各种容器和数据结构，如 vector、list、map 等。

以下是一些常用的 STL 算法及其用法：

1.for_each：对容器中的每个元素执行同一个函数。

C++
vector<int> v{1, 2, 3};
for_each(v.begin(), v.end(), [](int x) { cout << x << endl; });

2.find：在容器中查找指定的元素。

C++
vector<int> v{1, 2, 3};
auto it = find(v.begin(), v.end(), 2);
if (it != v.end()) {
    cout << "Found " << *it << endl;
}

3.sort：对容器中的元素进行排序。

C++
vector<int> v{3, 1, 2};
sort(v.begin(), v.end());
for (int x : v) {
    cout << x << endl;
}

4.binary_search：在有序的容器中查找指定的元素。

C++
vector<int> v{1, 2, 3};
bool found = binary_search(v.begin(), v.end(), 2);
if (found) {
    cout << "Found" << endl;
}

5.copy：将容器中的元素复制到另一个容器中。

C++
vector<int> v1{1, 2, 3};
vector<int> v2(v1.size());
copy(v1.begin(), v1.end(), v2.begin());
for (int x : v2) {
    cout << x << endl;
}

6.transform：对容器中的每个元素执行一个操作，并将结果存储到另一个容器中。

C++
vector<int> v1{1, 2, 3};
vector<int> v2(v1.size());
transform(v1.begin(), v1.end(), v2.begin(), [](int x) { return x * 2; });
for (int x : v2) {
    cout << x << endl;
}

7.count：计算容器中指定元素的个数。

C++
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    vector<int> v {1, 2, 3, 2, 1};
    int count = count(v.begin(), v.end(), 2);
    cout << "count: " << count << endl; // 输出：count: 2
    return 0;
}

8.max_element：查找容器中的最大元素。

C++
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    vector<int> v {3, 2, 1, 4, 5};
    auto max_it = max_element(v.begin(), v.end());
    cout << "max element: " << *max_it << endl; // 输出：max element: 5
    return 0;
}

9.min_element：查找容器中的最小元素。

C++
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    vector<int> v {3, 2, 1, 4, 5};
    auto min_it = min_element(v.begin(), v.end());
    cout << "min element: " << *min_it << endl; // 输出：min element: 1
    return 0;
}

10.accumulate：对容器中的元素进行累加或累乘。

C++
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>

using namespace std;

int main() {
    vector<int> v {1, 2, 3, 4, 5};
    int sum = accumulate(v.begin(), v.end(), 0);
    cout << "sum: " << sum << endl; // 输出：sum: 15

    int product = accumulate(v.begin(), v.end(), 1, multiplies<int>());
    cout << "product: " << product << endl; // 输出：product: 120
    return 0;
}

11.fill：将容器中的元素全部设为指定值。

C++
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    vector<int> v(5);
    fill(v.begin(), v.end(), 10);
    for (int x : v) {
        cout << x << endl; // 输出：10 10 10 10 10
    }
    return 0;
}

十二、优先队列

C++中的优先队列（priority queue）是一种基于堆结构实现的数据结构，它允许在任何时刻访问并删除最高优先级的元素，同时保持其他元素的相对顺序不变。

优先队列的应用广泛，例如：

求解图论中的最短路径问题，使用Dijkstra算法时可以利用优先队列维护到起点距离最小的点。
在数据流中找到中位数或前k个最大/小元素等问题，可以用优先队列实现。
任务调度，根据任务的优先级将其加入优先队列，然后按照优先级依次处理。
哈夫曼编码，利用优先队列进行字符频率的统计和构建哈夫曼树。

优先队列定义在头文件中，其模板类定义如下：

C++
template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type>>
class priority_queue;

其中，T表示存储的元素类型，Container表示底层存储容器，默认为vector；Compare表示元素比较器，默认使用less进行小于比较。

STL的优先队列支持以下操作：

push(val)：将val插入到队列中，并调整为合法的堆结构。
pop()：移除队列中当前最高优先级的元素。
top()：返回队列中当前最高优先级的元素。
empty()：判断队列是否为空。

需要注意的是，在STL的优先队列中，top操作只返回当前最高优先级的元素，并不会将其从队列中删除。如果需要删除该元素，需要调用pop操作。此外，STL的优先队列还提供了size()操作来获取队列中元素的个数。

STL的优先队列具有自我调整平衡的特点，所有的操作时间复杂度都是O(log n)，因此在实际应用中非常高效。

默认情况下，STL中的priority_queue是按照元素的大小进行排序的，即大的元素优先级高。如果需要自定义优先级，可以通过重载运算符来实现。

C++
struct Node {
    int val;
    bool operator<(const Node& other) const {
        return val > other.val; // 按照val从小到大排序
    }
};

std::priority_queue<Node> q;

这里重载了小于号运算符，使得val小的Node对象优先级高。

下面是利用线性表（vector）实现优先队列的C++代码：

C++
#include <vector>
using namespace std;

class PriorityQueue {
private:
    vector<int> data;
public:
    void push(int val) {
        data.push_back(val);
    }
    void pop() {
        int maxIndex = 0;
        for (int i = 1; i < data.size(); i++) {
            if (data[i] > data[maxIndex]) {
                maxIndex = i;
            }
        }
        data.erase(data.begin() + maxIndex);
    }
    int top() {
        int maxIndex = 0;
        for (int i = 1; i < data.size(); i++) {
            if (data[i] > data[maxIndex]) {
                maxIndex = i;
            }
        }
        return data[maxIndex];
    }
    bool empty() {
        return data.empty();
    }
};

上述代码中，push操作向线性表尾部插入元素，pop操作找到当前最大元素并删除，top操作返回当前最大元素，empty操作判断线性表是否为空。由于每次pop和top操作都需要遍历整个线性表，时间复杂度较高，不够高效。

下面是利用堆（heap）实现优先队列的C++代码：

C++
#include <vector>
#include <algorithm>

using namespace std;

class PriorityQueue {
private:
    vector<int> data;
public:
    void push(int val) {
        data.push_back(val);
        push_heap(data.begin(), data.end());
    }
    void pop() {
        pop_heap(data.begin(), data.end());
        data.pop_back();
    }
    int top() {
        return data.front();
    }
    bool empty() {
        return data.empty();
    }
};

上述代码中，push操作将新元素插入到线性表尾部，然后调用STL库函数push_heap将其调整为合法的堆结构；pop操作先调用STL库函数pop_heap将当前最大元素移动到末尾，然后再从末尾删除该元素；top操作返回堆顶元素；empty操作判断堆是否为空。由于堆具有自我调整平衡的特点，push_heap和pop_heap操作的时间复杂度都是O(log n)，相比利用线性表实现的版本更加高效。

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用