C++ STL基础了解
STL容器
vector：可变大小的数组，支持快速随机访问和尾部插入删除。适用于需要频繁在尾部插入删除，并且需要快速随机访问元素的场景。
deque：双端队列，支持在头尾插入删除，支持快速随机访问。适用于需要在头尾插入删除，并且需要快速随机访问元素的场景。
list：双向链表，支持在任意位置插入删除，不支持随机访问。适用于需要在任意位置插入删除元素的场景。
set/multiset：基于红黑树实现的有序集合，不允许重复元素。适用于需要有序存储数据，并且不允许重复元素的场景。
map/multimap：基于红黑树实现的映射表，支持按照key排序，并且不允许重复的key，每个key对应一个value。适用于需要映射关系，并且不允许重复key的场景。
unordered_set/unordered_multiset：基于哈希表实现的无序集合，允许重复元素。适用于需要快速存储和查找元素，并且不需要元素有序的场景。
unordered_map/unordered_multimap：基于哈希表实现的映射表，允许重复的key，每个key对应一个value。适用于需要快速存储和查找元素，并且不需要元素有序的场景。
STL算法
sort：排序算法，支持对数值型、字符串、结构体等类型排序。 unique：去重算法，对于有序或无序容器，去除相邻或所有相同的元素。
find：查找算法，支持查找元素是否在容器中，返回迭代器指向第一个找到的元素或容器尾部。 count：计数算法，支持计算指定元素的数量。
accumulate：累加算法，支持用二元函数对容器中的元素进行累加。 transform：转换算法，支持对容器中的元素进行函数式转换。
lower_bound/upper_bound：查找最接近指定元素值的元素迭代器，lower_bound返回大于等于指定值的第一个元素迭代器，upper_bound返回大于指定值的第一个元素迭代器。
使用STL需要包含头文件，例如包含vector头文件：
#include <vector>
完整的STL库头文件包括
<algorithm>, <array>, <bitset>, <complex>, <deque>, <exception>, <fstream>, <functional>, <iomanip>, <ios>, <iostream>, <istream>, <iterator>, <limits>, <list>, <locale>, <map>, <numeric>, <ostream>, <queue>, <set>, <sstream>, <stack>, <stdexcept>, <streambuf>, <string>, <tuple>, <typeinfo>, <unordered_map>, <unordered_set>, <utility>, <valarray>, <vector>。
C++标准模板库（STL）是一组提供了丰富通用功能的C++模板。它包含了多种容器类型（vector、list、set、map等）以及各种算法（排序、查找、统计等）。其中最常用的容器类型是vector和map。
以下是一些常见的STL函数的使用方法和功能：
1.容器类型
a.std::vector<T>
vector是一个动态数组容器类型，它可以自动扩展和缩小。可以使用以下函数：
- push_back(val)：在vector的末尾添加一个元素val。
- pop_back()：从vector的末尾移除一个元素。
- size()：返回vector的大小（即元素个数）。
- clear()：清空vector中的所有元素。
- begin()：返回一个指向vector第一个元素的迭代器。
- end()：返回一个指向vector最后一个元素的下一个位置的迭代器。
b.std::map<Key, Value>
map是一个关联式容器类型，它存储了一个key-value对，其中key是唯一的。可以使用以下函数：
- insert({key, value})：向map中插入一个key-value对。
- erase(key)：从map中删除一个指定key的key-value对。
- find(key)：返回一个指向key所在位置的迭代器。
- size()：返回map中key-value对的数量。
- clear()：清空map中的所有key-value对。
- begin()：返回一个指向map第一个key-value对的迭代器。
- end()：返回一个指向map最后一个key-value对的下一个位置的迭代器。
2.算法
a.sort(begin, end)
使用sort函数可以对一个数组或一个容器中的元素进行升序排序。例如：
std::vector<int> vec = {5, 2, 9, 4, 8};
std::sort(vec.begin(), vec.end());
这将对vector进行升序排序，vec将变为{2, 4, 5, 8, 9}。
b.binary_search(begin, end, val)
使用binary_search函数可以对一个容器或一个数组进行二分查找。例如：
std::vector<int> vec = {2, 4, 5, 8, 9};
bool is_found = std::binary_search(vec.begin(), vec.end(), 8);
这将在vec中查找值为8的元素，如果找到，is_found将为true，否则为false。
c.count(begin, end, val)
使用count函数可以计算一个容器或一个数组中值为val的元素数量。例如：
std::vector<int> vec = {2, 4, 5, 8, 8, 9};
int count_8 = std::count(vec.begin(), vec.end(), 8);
这将计算vec中值为8的元素数量，count_8将为2。
以上是一些常见的STL函数的使用方法和功能，还有很多其他STL函数可以使用。
C++STL（Standard Template Library）是一个强大的C++标准库，在C++开发中使用非常广泛。STL包含一系列的容器、算法和迭代器模板，可以加速程序开发，提高程序的可维护性和扩展性。下面是一份C++STL的小白教程，帮助您了解STL的基本语法和操作。
1. 常见的STL容器
STL容器是存储数据的对象，可以存储不同类型的数据。C++STL提供了多种容器，下面是一些常见的STL容器：
- vector：动态数组，可以自动扩容。
- list：双向链表。
- queue：先进先出队列。
- stack：后进先出堆栈。
- map：关联容器，提供键值对的映射功能。
- set：关联容器，提供自动排序和去重功能。
2. 容器的基本操作
STL容器提供了丰富的方法和操作，下面是一些常见的操作：
2.1. 容器的创建
使用STL容器需要先包含相应的头文件，然后通过容器类型来声明变量，如下：
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;vector<int> myVec; // 声明一个动态数组
list<double> myList; // 声明一个双向链表
queue<char> myQueue; // 声明一个字符型队列
stack<int> myStack; // 声明一个整型堆栈
map<string, int> myMap; // 声明一个键值对映射容器
set<int> mySet; // 声明一个自动排序和去重的容器
2.2. 容器的赋值和访问
STL容器提供了丰富的赋值和访问方法，下面是一些常见的操作：
myVec.push_back(10); // 在动态数组尾部插入一个元素10
myList.push_front(3.14); // 在双向链表头部插入一个元素3.14
myQueue.push('a'); // 在队列尾部插入一个字符a
myStack.push(100); // 在堆栈顶部插入一个整数100
myMap["apple"] = 5; // 在键值对容器中插入元素"apple-5"
mySet.insert(2); // 在自动排序和去重容器中插入元素2int num = myVec[0]; // 访问动态数组的第1个元素
double val = myList.front(); // 访问双向链表的第1个元素
char ch = myQueue.front(); // 访问队列的第1个元素
int top = myStack.top(); // 访问堆栈顶部的元素
int cnt = myMap["apple"]; // 根据键名获取键值对容器中的元素值
set<int>::iterator it = mySet.find(3); // 在自动排序和去重容器中查找元素3
2.3. 容器的遍历和删除
STL容器提供了丰富的遍历和删除方法，下面是一些常见的操作：
// 遍历动态数组
for (int i = 0; i < myVec.size(); i++) {int val = myVec[i];cout << val << " ";
}// 遍历双向链表
list<double>::iterator it = myList.begin();
while (it != myList.end()) {double val = *it;cout << val << " ";it++;
}// 遍历队列
while (!myQueue.empty()) {char ch = myQueue.front();cout << ch << " ";myQueue.pop(); // 删除队列头部的元素
}// 遍历堆栈
while (!myStack.empty()) {int top = myStack.top();cout << top << " ";myStack.pop(); // 删除堆栈顶部的元素
}// 遍历键值对映射容器
map<string, int>::iterator it = myMap.begin();
while (it != myMap.end()) {string key = it->first;int val = it->second;cout << key << "-" << val << " ";it++;
}// 遍历自动排序和去重容器
set<int>::iterator it = mySet.begin();
while (it != mySet.end()) {int val = *it;cout << val << " ";it++;
}// 删除自动排序和去重容器中的元素3
mySet.erase(3);
3. 常见的STL算法
STL算法是一系列针对容器的算法，提供了丰富的计算和操作方法，下面是一些常见的STL算法：
3.1. for_each
for_each是一种遍历容器元素的算法，可以对容器中的每个元素执行指定的操作，如下：
// 定义一个函数，输出容器元素
void print(int n) {cout << n << " ";
}// 声明一个动态数组
vector<int> myVec = {1, 2, 3, 4, 5};// 遍历动态数组，输出数组元素
for_each(myVec.begin(), myVec.end(), print);
3.2. sort
sort是一种排序算法，可以对容器中的元素进行排序，如下：
// 声明一个自动排序容器
set<int> mySet = {10, 5, 8, 1, 7};// 对自动排序容器中的元素进行排序
sort(mySet.begin(), mySet.end());// 遍历排序后的自动排序容器，输出容器元素
set<int>::iterator it = mySet.begin();
while (it != mySet.end()) {int val = *it;cout << val << " ";it++;
}
3.3. count
count是一种计数算法，可以统计容器中元素的个数，如下：
// 声明一个动态数组
vector<int> myVec = {1, 2, 1, 2, 3, 4, 1, 2};// 统计动态数组中元素1出现的次数
int cnt = count(myVec.begin(), myVec.end(), 1);// 输出元素1的出现次数
cout << cnt << endl;
以上是C++STL的基本语法和操作，希望对您有所帮助。如果您想进一步学习STL，可以参考其他高级教程。
1.使用队列实现栈 (题号：225)
C++基础：STL容器queue的使用。
使用两个队列来模拟栈的操作，保证只有一个队列非空，Push操作始终在非空队列中进行，Pop操作将非空队列中的元素逐一移动到另一个空队列中，直到队列只剩下一个元素就可以弹出。
2. 使用栈实现队列 (题号：232)
C++基础：STL容器stack的使用。
使用两个栈来模拟队列的操作，一个栈用于Push操作，一个栈用于Pop操作。Push操作直接在第一个栈中Push元素，Pop操作则需要将第一个栈中的所有元素依次Pop出到第二个栈中，再将第二个栈中的元素弹出。
3. 有效的括号 (题号：20)
C++基础：STL容器stack的使用，字符串操作。
使用栈来匹配括号，遍历字符串，如果遇到左括号，Push到栈中，如果遇到右括号，取出栈顶元素进行匹配。如果匹配成功，则弹出栈顶元素，否则返回false。
4. 设计循环队列 (题号：622)
C++基础：面向对象编程、数组的使用。
使用数组来存储队列元素，使用两个指针head和tail分别指向队头和队尾。如果tail指向数组最后一个位置，则重新指向头部，如果head和tail相同时表示队列为空，如果tail指向head的前一个位置，则表示队满。
6. 最小栈 (题号：155)
C++基础：STL容器stack的使用。
创建两个栈，一个用于正常操作，另一个用于保存每个操作后的最小值。Push操作时，将元素Push到正常栈中，并将此时栈中的最小值Push到最小值栈中，到了Pop操作时，两个栈中的元素同时Pop。
7. 基本计算器 II (题号：227)
C++基础：STL容器stack的使用，字符串操作，表达式求值。
使用栈来处理表达式，将每个数字Push到栈中，在遇到符号的时候进行运算，最终得出表达式的结果。
8. 简化路径 (题号：71)
C++基础：STL容器stack的使用，字符串操作。
使用栈来处理路径，对路径进行切割，如果遇到空路径或者".“表示当前目录，则忽略；如果遇到”…"表示上一级目录，则弹出栈顶元素；否则Push到栈中。最终栈中剩下的元素表示简化路径。
9. 二叉树的层序遍历 (题号：102)
C++基础：STL容器queue的使用，二叉树的遍历。
使用队列进行广度优先遍历，先将根节点Push到队列中，然后依次从队列中Pop出元素，将其子节点Push到队列中。每遍历完一层，将遍历结果Push到一个容器中，最终返回这个容器。
10. 合并K个排序链表 (题号：23)
C++基础：链表的操作，STL容器priority_queue的使用。
使用小根堆来合并K个已排序链表，将每个链表的头部元素Push到堆中，每次取出堆顶元素，将该元素所在链表的下一个元素Push到堆中，直到堆为空，这时所有链表被合并成一个新的有序链表。
11. 用堆实现排序 (题号：347)
C++基础：STL容器priority_queue的使用。
使用大根堆来实现排序，先将所有元素Push到堆中，然后依次取出堆顶元素，直到堆为空。每取出一个元素说明已经找到最大的元素，放到结果数组中即可。
12. 相交链表 (题号：160)
C++基础：链表的操作。
先分别遍历两个链表，记录链表长度。然后将长的链表的指针向后移动到和短的链表一样长的位置，再同步遍历两个链表，找到第一个相同的节点即为交点。
13. 排序链表 (题号：148)
C++基础：链表的操作，归并排序。
使用归并排序对链表进行排序，将链表拆分成两个子链表，分别对子链表进行排序，然后将两个已排序的子链表进行合并。
14. 反转链表 (题号：206)
C++基础：链表的操作。
遍历链表，用一个变量记录链表头，每遍历到一个节点，将其下一个节点指向链表头，并将链表头指向该节点，最终链表的头节点即为原链表的尾节点。
15.链表中倒数第k个节点 (题号：剑指Offer22)
C++基础：链表的操作。
使用快慢指针，先让快指针向前走k步，然后快慢指针同时向前直到快指针到达链表末尾，此时慢指针所指的节点即为链表中倒数第k个节点。
1. 使用队列实现栈 (题号：225)
class MyStack {
public:/** Initialize your data structure here. */MyStack() {}/** Push element x onto stack. */void push(int x) {q.push(x);for(int i=1; i<q.size(); i++){q.push(q.front());q.pop();}}/** Removes the element on top of the stack and returns that element. */int pop() {int x = q.front();q.pop();return x;}/** Get the top element. */int top() {return q.front();}/** Returns whether the stack is empty. */bool empty() {return q.empty();}
private:queue<int> q;
};
2. 使用栈实现队列 (题号：232)
class MyQueue {
public:/** Initialize your data structure here. */MyQueue() {}/** Push element x to the back of queue. */void push(int x) {while(!s1.empty()){s2.push(s1.top());s1.pop();}s1.push(x);while(!s2.empty()){s1.push(s2.top());s2.pop();}}/** Removes the element from in front of queue and returns that element. */int pop() {int x = s1.top();s1.pop();return x;}/** Get the front element. */int peek() {return s1.top(); }/** Returns whether the queue is empty. */bool empty() {return s1.empty();}
private:stack<int> s1,s2;
};
3. 有效的括号 (题号：20)
class Solution {
public:bool isValid(string s) {stack<char> stk;for(auto c : s){if(c == '(' || c == '[' || c == '{')stk.push(c);else{if(stk.empty())return false;char top = stk.top();stk.pop();if(c == ')' && top != '(')return false;if(c == ']' && top != '[')return false;if(c == '}' && top != '{')return false;}}return stk.empty();}
};
4. 设计循环队列 (题号：622)
class MyCircularQueue {
public:/** Initialize your data structure here. Set the size of the queue to be k. */MyCircularQueue(int k) {size = k;front = 0;rear = 0;data.resize(size);}/** Insert an element into the circular queue. Return true if the operation is successful. */bool enQueue(int value) {if(isFull()) return false;data[rear] = value;rear = (rear+1)%size;return true;}/** Delete an element from the circular queue. Return true if the operation is successful. */bool deQueue() {if(isEmpty()) return false;front = (front+1)%size;return true;}/** Get the front item from the queue. */int Front() {if(isEmpty()) return -1;return data[front];}/** Get the last item from the queue. */int Rear() {if(isEmpty()) return -1;return data[(rear-1+size)%size];}/** Checks whether the circular queue is empty or not. */bool isEmpty() {return front == rear;}/** Checks whether the circular queue is full or not. */bool isFull() {return (rear+1)%size == front;}
private:vector<int> data;int front, rear, size;
};
5. 用队列实现栈的操作 (题号：225）
class MyStack {
public:/** Initialize your data structure here. */MyStack() {}/** Push element x onto stack. */void push(int x) {q.push(x);for(int i=1; i<q.size(); i++){q.push(q.front());q.pop();}}/** Removes the element on top of the stack and returns that element. */int pop() {int x = q.front();q.pop();return x;}/** Get the top element. */int top() {return q.front();}/** Returns whether the stack is empty. */bool empty() {return q.empty();}
private:queue<int> q;
};
6. 最小栈 (题号：155)
class MinStack {
public:/** initialize your data structure here. */MinStack() {}void push(int x) {s.push(x);if(min_s.empty() || x <= min_s.top()) min_s.push(x);}void pop() {if(s.top() == min_s.top()) min_s.pop();s.pop();}int top() {if(!s.empty())return s.top();return -1;}int getMin() {if(!min_s.empty())return min_s.top();return -1;}
private:stack<int> s, min_s;
};
7. 基本计算器 II (题号：227)
class Solution {
public:int calculate(string s) {stack<int> stk;char sign = '+';int num = 0;// 对于最后一个操作数没有符号的情况s+="+";for(int i=0; i<s.size(); i++){char c = s[i];if(c>='0' && c<='9'){num = num*10 + (c-'0');}else if(c=='+' || c=='-' || c=='*' || c=='/'){if(sign=='+'){stk.push(num);}else if(sign=='-'){stk.push(-num);}else if(sign=='*'){int tmp = stk.top();stk.pop();stk.push(tmp*num);}else if(sign=='/'){int tmp = stk.top();stk.pop();stk.push(tmp/num);}sign = c;num = 0;}}int res = 0;while(!stk.empty()){res += stk.top();stk.pop();}return res;}
};
8. 简化路径 (题号：71)
class Solution {
public:string simplifyPath(string path) {stringstream ss(path);vector<string> stk;string cur;while(getline(ss, cur, '/')){if(cur=="" || cur==".")continue;if(cur == ".."){if(!stk.empty())stk.pop_back();}else{stk.push_back(cur);}}string res = "";for(auto str: stk)res += '/' + str;return res.empty() ? "/" : res;}
};
9. 二叉树的层序遍历 (题号：102)
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;if(!root){return res;}queue<TreeNode*> q;q.push(root);while(!q.empty()){int level_size = q.size();vector<int> level;for(int i=0; i<level_size; i++){TreeNode* node = q.front();q.pop();level.push_back(node->val);if(node->left){q.push(node->left);}if(node->right){q.push(node->right);}}res.push_back(level);}return res;}
};
10. 合并K个排序链表 (题号：23)
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {if(lists.empty()){return NULL;}while(lists.size()>1){ListNode* l1 = lists.back();lists.pop_back();ListNode* l2 = lists.back();lists.pop_back();lists.push_back(mergeTwoLists(l1, l2));}return lists.front();}
private:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2){ListNode* dummy = new ListNode(-1);ListNode* cur = dummy;while(l1 && l2){if(l1->val <= l2->val){cur->next = l1;l1 = l1->next;}else{cur->next = l2;l2 = l2->next;}cur = cur->next;}if(l1){cur->next = l1;}else{cur->next = l2;}return dummy->next;}
};
11. 用堆实现排序 (题号：347)
class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int, int> mp;for(auto num: nums){mp[num]++;}priority_queue<pair<int, int>> pq;for(auto m: mp){pq.push(make_pair(m.second, m.first));}vector<int> res;while(k-- > 0){res.push_back(pq.top().second);pq.pop();}return res;}
};
12. 相交链表 (题号：160)
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* l1 = headA;ListNode* l2 = headB;while(l1 != l2){l1 = l1 ? l1->next : headB;l2 = l2 ? l2->next : headA;}return l1;}
};
13. 排序链表 (题号：148)
class Solution {
public:ListNode* sortList(ListNode* head) {if(!head || !head->next){return head;}ListNode* slow = head, *fast = head->next;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}ListNode* mid = slow->next;slow->next = NULL;return merge(sortList(head), sortList(mid));}
private:ListNode* merge(ListNode* l1, ListNode* l2){ListNode* dummy = new ListNode(-1);ListNode* cur = dummy;while(l1 && l2){if(l1->val <= l2->val){cur->next = l1;l1 = l1->next;}else{cur->next = l2;