. STL简介

• 定义：STL（Standard Template Library）是C++标准库的重要组成部分，是一个可复用的组件库，包含数据结构和算法的软件框架。

• 版本：

  • 原始版本：由Alexander Stepanov和Meng Lee在惠普实验室完成，开源，允许任意使用和修改。

  • P. J. 版本：由P. J. Plauger开发，继承自HP版本，被Windows Visual C++采用，不可公开或修改，可读性低。

  • RW版本：由Rouge Wage公司开发，继承自HP版本，被C++ Builder采用，不可公开或修改，可读性一般。

  • SGI版本：由Silicon Graphics Computer Systems, Inc公司开发，继承自HP版本，被GCC (Linux)采用，可移植性好，可公开、修改甚至贩卖，阅读性高。

2. STL的六大组件

• 容器：存储数据的结构，如vector, list, map等。

• 迭代器：提供访问容器中元素的接口，如iterator, reverse_iterator等。

• 算法：对容器中的数据进行操作的函数，如sort, find, copy等。

• 函数对象：用于封装函数的类，如plus, multiplies等。

• 配接器：用于扩展容器或迭代器的功能，如stack, queue, priority_queue等。

• 存储器：管理内存分配和释放，如allocator。

1. 二叉树层序打印

问题描述：给定一个二叉树，按照层序遍历的顺序打印节点值。

解决方案：

• 使用std::queue实现层序遍历。

• #include <iostream>
  #include <queue>
  using namespace std;struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  };void levelOrder(TreeNode* root) {if (!root) return;queue<TreeNode*> q;q.push(root);while (!q.empty()) {TreeNode* node = q.front();q.pop();cout << node->val << " ";if (node->left) q.push(node->left);if (node->right) q.push(node->right);}
  }

2. 重建二叉树

问题描述：给定二叉树的前序遍历和中序遍历结果，重建二叉树。

解决方案：

• 使用std::map存储中序遍历的索引，方便快速查找。

• #include <iostream>
  #include <map>
  using namespace std;struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  };TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {map<int, int> inorderMap;for (int i = 0; i < inorder.size(); ++i) {inorderMap[inorder[i]] = i;}return buildTreeHelper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, inorderMap);
  }TreeNode* buildTreeHelper(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd, map<int, int>& inorderMap) {if (preStart > preEnd || inStart > inEnd) return nullptr;TreeNode* root = new TreeNode(preorder[preStart]);int inRootIndex = inorderMap[root->val];int leftTreeSize = inRootIndex - inStart;root->left = buildTreeHelper(preorder, preStart + 1, preStart + leftTreeSize, inorder, inStart, inRootIndex - 1, inorderMap);root->right = buildTreeHelper(preorder, preStart + leftTreeSize + 1, preEnd, inorder, inRootIndex + 1, inEnd, inorderMap);return root;
  }

3. 两个栈实现一个队列

问题描述：使用两个栈实现一个队列的功能，支持入队和出队操作。

解决方案：

• 使用std::stack实现队列的入队和出队操作。

• #include <iostream>
  #include <stack>
  using namespace std;class MyQueue {stack<int> inStack, outStack;
  public:void push(int x) {inStack.push(x);}void pop() {if (outStack.empty()) {while (!inStack.empty()) {outStack.push(inStack.top());inStack.pop();}}outStack.pop();}int top() {if (outStack.empty()) {while (!inStack.empty()) {outStack.push(inStack.top());inStack.pop();}}return outStack.top();}bool empty() {return inStack.empty() && outStack.empty();}
  };