C++STL 学习笔记

STL补充

List 链表

list<int> mylist = { }链表定义和初始化
void push_front(const T & val) 将 val 插入链表最前面
void pop_front() 删除链表最前面的元素
list.push_back() 增加一个新的元素在 list 的尾端
list.pop_back() 删除 list 的最末个元素
void sort() 将链表从小到大排序
reverse()反转链表
list.empty() 若list内部为空，则回传true值
list.size() 回传list内实际的元素个数
list.front() 存取第一个元素
list.back() 存取最末个元素
mylist.begin() 首位迭代器
mylist.end()末位迭代器
常见for循环
- for (auto it = mylist.begin(); it != mylist.end(); ++it)
  
  cout << *it << " ";
- it是迭代器指针，不能赋值，不能运算（+=不行），只能++
- list的迭代器只支持双向访问，不支持随机访问，因此不能直接进行加减操作（和vector等区别）
advance(it, n); 将迭代器it向前移动n个位置
mylist.insert(it, k); 向第it位迭代器位置插入新元素k（it之前）
mylist.erase(it); 删除第it位迭代器位置所指元素
mylist.erase(it, it + n); 删除第it位到第it+n位元素（一共删除从it开始到it+n的n个元素）
next(it,n)函数是C++ STL中的一个函数，它的作用是返回一个新的迭代器，该迭代器指向原始迭代器向前或向后移动指定距离后的位置，被用来移动it迭代器到下n位

vector 存放任意类型的动态数组

vector<T>(nSize,t)创建一个vector，元素个数为nSize,且值均为t
vector.push_back(k) 在vector尾部插入元素k
vector.insert(vector.begin() + 1, 2) 在vector的第2个位置插入一个元素2
vector.pop_back() 删除vector尾部的一个元素
vector.erase(v.begin() + 1) 删除vector的第2个元素
erase()方法接受两个迭代器参数，表示要删除的区间的起始位置和结束位置。被删除的区间包括起始位置的元素，但不包括结束位置的元素。
vector.[0]; 访问vector的第1个元素，可进行赋值等操作
vector.at(0); /访问vector的第1个元素，如果越界会抛出异常
for (int i = 0; i < v.size(); i++) { cout << v[i] << " "; } 遍历vector
vector.resize() 改变实际元素的个数，新添加的元素会被默认初始化
vector.size() 获取vector的大小，这是当前存储的元素数量
vector.capacity()返回当前容量，这是目前容器最多储存的元素数量
vector.front() 返回第一个元素的引用
vector.back()返回最后一个元素的引用
vector.begin()返回指向容器中第一个元素的迭代器
vector.end()返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用
vector.empty()判断一个vector是否为空

STL容器适配器

stack

stack<T> 创建栈对象
push(element)：将元素压入栈顶
pop()：弹出栈顶元素
top()：返回栈顶元素
empty()：返回栈是否为空
size()：返回栈中元素的数量

清空栈操作： while (!myStack.empty()) { myStack.pop(); }

queue

queue <int> 创建queue对象
push(element)：将元素添加到队列的末尾
pop()：从队列的头部取出元素，并将其从队列中删除
front()：返回队列头部的元素，但不将其从队列中删除
back()：返回队列末尾的元素，但不将其从队列中删除
size()：返回队列中元素的数量
empty()：判断队列是否为空

priority_queue

push(element)：将元素添加到优先队列中，根据优先级顺序排列。
pop()：从优先队列中取出优先级最高的元素，并将其从队列中删除。
top()：返回优先队列中优先级最高的元素，但不将其从队列中删除。
size()：返回优先队列中元素的数量。
empty()：判断优先队列是否为空
priority_queue<int, std::vector<int>, std::less<int>> myMaxHeap;创建大顶堆
less<int>是priority_queue的默认比较函数，因此在创建大顶堆时可以省略第三个参数。以下是更简洁的表达式：priority_queue<int> myMaxHeap;
priority_queue<int, vector<int>, greater<int>> myMinHeap; 创建小顶堆

priority_queue<int, vector<int>,greater<int>> 指定了使用greater<int> 作为比较函数，因此创建的优先队列是升序的，即优先级数值小的元素排在队列前面。如果想要创建降序的优先队列，可以使用 less<int> 作为比较函数，例如 priority_queue<int, vector<int>, less<int>>

EG: 优先队列实现滑动窗口求最大值

int main() {
    int k; // 滑动窗口大小
    int n;
    cin >> n >> k;
    vector<int> nums(n); // 输入数组
    priority_queue<pair<int, int>> pq; // 定义优先队列，存放数值和下标

    for (int i = 0; i < nums.size(); i++)
        cin >> nums[i];

    // 先将前 k 个元素加入优先队列
    for (int i = 0; i < k; i++) {
        pq.push({ nums[i], i });
    }

    // 输出第一个滑动窗口的最大值
    cout << pq.top().first << " ";

    // 滑动窗口向右移动，每次加入一个新元素，弹出一个旧元素
    for (int i = k; i < nums.size(); i++) {
        pq.push({ nums[i], i }); // 加入新元素
        while (pq.top().second <= i - k) { // 弹出旧元素
            pq.pop();
        }
        cout << pq.top().first << " "; // 输出当前滑动窗口的最大值
    }

    return 0;
}

deque

push_back(element)：在队尾插入一个元素。
pop_back()：删除队尾元素。
push_front(element)：在队头插入一个元素。
pop_front()：删除队头元素。
front()：返回队头元素，但不删除。
back()：返回队尾元素，但不删除。
empty()：如果队列为空，返回true，否则返回false。
size()：返回队列中元素的个数。

heap

make_heap(first, last)：将[first, last)区间内的元素转换为堆。
push_heap(first, last)：将[first, last-1)区间内的元素插入堆中。
pop_heap(first, last)：将堆顶元素移动到[last-1]位置，并重新构建堆。
sort_heap(first, last)：将[first, last)区间内的元素排序，使其满足堆的性质。
is_heap(first, last)：如果[first, last)区间内的元素满足堆的性质，返回true，否则返回false。
push()：将元素添加到堆中。
pop()：从堆中移除根节点元素。
top()：返回堆中的根节点元素。
empty()：检查堆是否为空。
size()：返回堆中元素的数量。

STL中，堆是通过vector容器实现的，因此要声明一个堆对象，需要先声明一个vector容器，然后使用make_heap()函数将其转换为堆

~~不如手搓~~

pair

template<class T1, class T2> struct pair;其中，T1和T2表示两个不同的类型。std::pair类包含了两个公有成员变量first和second，分别表示这两个值。可以通过以下方式创建和访问std::pair对象：

编译器并不会对std::vector<std::pair<int, int>>中的元素顺序进行任何假设或者判断。它只会根据你的代码中对这个std::vector对象的使用来确定元素顺序。

例如，如果你在代码中使用v[i].first来访问第i个元素的第一个元素，编译器就会认为第一个元素表示数值，第二个元素表示下标。如果你使用v[i].second来访问第i个元素的第二个元素，编译器就会认为第一个元素表示下标，第二个元素表示数值。

迭代器类型补充

在C++中，STL容器的迭代器可以分为5种类型，分别是：

输入迭代器（Input Iterator）：只读，只能单向移动，每个元素只能被访问一次。例如istream_iterator。
输出迭代器（Output Iterator）：只写，只能单向移动，每个元素只能被赋值一次。例如ostream_iterator。
前向迭代器（Forward Iterator）：可读写，只能单向移动，每个元素可以被访问或赋值多次。例如forward_list。
双向迭代器（Bidirectional Iterator）：可读写，可以双向移动，每个元素可以被访问或赋值多次。例如list。
随机访问迭代器（Random Access Iterator）：可读写，可以随机访问，支持加减运算，可以跳跃式访问容器中的元素。例如vector、deque。

因此，可以根据迭代器的类型来判断容器是否支持随机访问。以下是一些常见的STL容器及其迭代器类型：

vector：支持随机访问迭代器。
deque：支持随机访问迭代器。
list：支持双向迭代器。
forward_list：支持前向迭代器。
set：支持双向迭代器。
map：支持双向迭代器。
unordered_set：支持前向迭代器。
unordered_map：支持前向迭代器。

迭代器类型的不同，使得for循环的操作写法不同

支持随机访问的可以使用熟悉的写法，对元素进行操作；不支持的如双向迭代器要对迭代器进行操作

需要注意的是，对于容器的不同操作，可能需要不同类型的迭代器。例如，对于list容器，如果需要在容器中间插入或删除元素，需要使用双向迭代器；而如果只是进行遍历，可以使用前向迭代器。

而且，要注意的是

stack是STL中的一个容器适配器，它并不是一个容器，因此没有迭代器。stack只提供了很少的操作，主要包括push()、pop()、top()、empty()和size()等方法，这些方法都是直接对栈顶元素进行操作，不需要使用迭代器来遍历栈中的元素。因此，stack并不属于任何一种迭代器类型。

STL对于空间大小的规定

STL（标准模板库）中的容器分为两类：

顺序容器（Sequence Containers）：这些容器按照元素在容器中的位置来组织和存储元素。顺序容器包括vector、deque、list、forward_list、array。
- vector、deque、array需要在创建容器对象时指定容器的大小，因为它们使用连续的内存存储元素，所以需要预先分配足够的内存空间。
- list、forward_list不需要指定容器大小，它们使用链表存储元素，可以动态地分配和释放内存。
关联容器（Associative Containers）：这些容器按照元素的键值来组织和存储元素。关联容器包括set、multiset、map、multimap。
- 关联容器不需要在创建容器对象时指定容器的大小，它们使用树形结构存储元素，可以动态地分配和释放内存。

此外，还有另一种容器叫做stack和queue，它们是容器适配器（Container Adaptors），是在顺序容器的基础上提供了特定的接口，使其按照一定的规则进行操作。stack和queue都是基于顺序容器实现的，但是它们不需要指定容器的大小，因为它们使用的是顺序容器的默认构造函数，自动创建一个空的容器对象。

总之，顺序容器中的vector、deque和array需要指定容器大小，而list和forward_list不需要。关联容器和容器适配器都不需要指定容器大小。