C++ 基础函数的介绍及使用(Vector+deque+STL)

Vector

介绍

Vector是一个动态数组，它提供了随机访问和在末尾插入/删除的高效操作。

创建Vector

使用如下代码创建一个Vector：

#include <vector>
vector<int> nums;

此时，nums为空Vector。

返回Vector的大小

使用size()函数可以返回Vector中元素个数。如下代码：

cout << nums.size() << endl;

在Vector中插入元素

使用push_back()函数可以向Vector中插入元素。如下代码：

nums.push_back(10); // 向nums中插入元素10

遍历Vector

如下代码遍历 Vector 中的所有元素：

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

示例1：将Vector中的元素排序

#include <algorithm> // 引入sort函数
vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
sort(nums.begin(), nums.end());   // 对 nums 进行排序
for (int i = 0; i < nums.size(); i++) {
    cout << nums[i] << endl;
}

输出结果：

1
1
2
3
3
4
5
5
5
6
9

deque

介绍

deque是双端队列，它支持在头部和尾部插入/删除元素。

创建deque

使用如下代码创建一个deque:

#include <deque>
deque<int> nums;

此时，nums为空 deque。

返回deque的大小

使用size()函数可以返回 deque 中元素个数。如下代码：

cout << nums.size() << endl;

在deque中插入元素

使用push_back()函数向deque的尾部插入元素，使用push_front()函数向头部插入元素。

遍历deque

如下代码遍历 deque 中的所有元素：

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

示例2：使用deque模拟“滑动窗口”算法

题目描述：给定一个大小为n的数组和一个整数k，滑动窗口从数组的最左侧移动到最右侧，每次窗口向右移动k个元素，返回每个窗口内的最大值。

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]

实现代码如下：

#include <deque>
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> win; // 模拟滑动窗口
    vector<int> res; // 存放最大值
    for (int i = 0; i < nums.size(); i++) {
        // 删除队列中不在窗口内的值
        if (!win.empty() && win.front() == i - k) {
            win.pop_front();
        }
        // 删除队尾比新元素小的值
        while (!win.empty() && nums[win.back()] < nums[i]) {
            win.pop_back();
        }
        // 新元素插入队尾
        win.push_back(i);
        // 记录窗口内最大值
        if (i >= k - 1) {
            res.push_back(nums[win.front()]);
        }
    }
    return res;
}

STL

介绍

STL是Standard Template Library的缩写，是一组C++标准库函数模板和类模板，用于实现常用数据结构和算法。

STL的三大组件

STL由三大组件组成：容器、算法和迭代器。

容器：包括vector、deque等数据结构，用于存放和处理数据。

算法：包括sort、max等函数模板，用于实现常用算法。

迭代器：用于遍历容器中的元素。

容器

容器是STL的基础组件，包括：

1. 序列式容器：vector、deque、list、queue等。

记录元素间的线性关系，通过指针或者迭代器实现元素的快速访问。

1. 关联式容器：set、map、multiset等。

使用二叉树实现元素的排序和查找。

如下是使用list（序列式容器）和set（关联式容器）的示例。

示例3：使用list实现双向队列

#include <list> // 引入list头文件
list<int> nums;
nums.push_back(1);
nums.push_back(2);
nums.push_back(3);
nums.push_front(4);  // 在队列头部插入元素
nums.pop_front(); // 删除队首元素
for (auto it = nums.begin(); it != nums.end(); it++) {
    cout << *it << endl;    // 输出整个队列
}

输出结果：

4
1
2
3

示例4：使用set完成整数集合操作

#include <set> // 引入set头文件
set<int> nums;
nums.insert(1);
nums.insert(2);
nums.insert(3);
nums.erase(2);  // 删除元素2
cout << nums.count(2) << endl;  // 0，元素2不存在
cout << nums.count(3) << endl;  // 1，元素3存在

输出结果：

0
1