【算法】C++常见容器使用集合
in 博客目录
本文介绍了C++常见的一些数据容器及其常用函数
C++ 提供了多种数据结构，每种都有其特定的用途和优势。以下是常见的 C++ 数据结构及其简单示例：
数组 (Array)
最基本的线性数据结构，元素在内存中连续存储。
#include <iostream>
using namespace std;
int main() {
int arr[5] = {1, 2, 3, 4, 5};
for(int i = 0; i < 5; i++) {
cout << arr[i] << " ";
}
return 0;
}
向量 (Vector)
动态数组，可以自动调整大小。
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> vec = {1, 2, 3};
vec.push_back(4); // 添加元素
vec.pop_back(); // 移除最后一个元素
for(int num : vec) {
cout << num << " ";
}
return 0;
}
链表 (Linked List)
包括单向链表、双向链表和循环链表。
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
int main() {
Node* head = new Node{1, nullptr};
head->next = new Node{2, nullptr};
head->next->next = new Node{3, nullptr};
Node* current = head;
while(current != nullptr) {
cout << current->data << " ";
current = current->next;
}
return 0;
}
栈 (Stack)
后进先出(LIFO)的数据结构。
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
while(!s.empty()) {
cout << s.top() << " ";
s.pop();
}
return 0;
}
除了pop,push,empty,top之外，还有size()用于查看元素个数，swap用于置换两个栈道内容。
swap()
• 功能：交换两个栈的内容。 • 示例代码：
#include <vector>
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> stack1;
stack1.push(10);
stack1.push(20);
stack<int> stack2;
stack2.push(30);
stack2.push(40);
stack1.swap(stack2);
// 输出交换后 stack1 的栈顶元素
cout << "交换后 stack1 的栈顶元素: " << stack1.top() << endl;
return 0;
}
队列 (Queue)
先进先出(FIFO)的数据结构。
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
while(!q.empty()) {
cout << q.front() << " ";
q.pop();
}
return 0;
}
优先队列 (Priority Queue)
元素按优先级出队。
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
pq.push(2);
while(!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
return 0;
}
队列有front,back,empty,push,pop,size等常用函数。
集合 (Set)
存储唯一元素的有序集合，基于红黑树，可以自动排序，且元素唯一。重复添加相同元素，只有第一个可以成功添加。 常用方法有：insert，erase, clear, find寻找元素；count返回集合元素数量（0或1）,
find()
• 功能：查找指定元素，若找到则返回指向该元素的迭代器，未找到则返回 end() 迭代器。 • 实例代码：
#include <set>
#include <iostream>
int main() {
std::set<int> intSet = {3, 7, 10, 15};
auto it = intSet.find(7);
if (it != intSet.end()) {
std::cout << "找到元素: " << *it << std::endl;
} else {
std::cout << "未找到元素" << std::endl;
}
return 0;
}
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s = {3, 1, 4, 1, 5, 9};
for(int num : s) {
cout << num << " ";
}
return 0;
}
映射 (Map)
键值对集合。
#include <iostream>
#include <map>
using namespace std;
int main() {
map<string, int> ages;
ages["Alice"] = 25;
ages["Bob"] = 30;
for(const auto& pair : ages) {
cout << pair.first << ": " << pair.second << endl;
}
return 0;
}
哈希表 (Unordered Map)
基于哈希表的键值对集合。
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<string, int> ages;
ages["Alice"] = 25;
ages["Bob"] = 30;
for(const auto& pair : ages) {
cout << pair.first << ": " << pair.second << endl;
}
return 0;
}
树 (Tree)
包括二叉树、二叉搜索树、AVL树等。
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void inorder(TreeNode* root) {
if(root == nullptr) return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
inorder(root);
return 0;
}
图 (Graph)
可以使用邻接表或邻接矩阵表示。
#include <iostream>
#include <vector>
using namespace std;
class Graph {
int V;
vector<vector<int>> adj;
public:
Graph(int V) : V(V), adj(V) {}
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u); // 无向图
}
void print() {
for(int i = 0; i < V; i++) {
cout << "顶点 " << i << " 的邻居: ";
for(int neighbor : adj[i]) {
cout << neighbor << " ";
}
cout << endl;
}
}
};
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.print();
return 0;
}
堆 (Heap)
用于实现优先队列的完全二叉树。
#include <iostream>
#include <queue>
using namespace std;
int main() {
// 最大堆
priority_queue<int> max_heap;
// 最小堆
priority_queue<int, vector<int>, greater<int>> min_heap;
max_heap.push(3);
max_heap.push(1);
max_heap.push(4);
cout << "最大堆: ";
while(!max_heap.empty()) {
cout << max_heap.top() << " ";
max_heap.pop();
}
min_heap.push(3);
min_heap.push(1);
min_heap.push(4);
cout << "\n最小堆: ";
while(!min_heap.empty()) {
cout << min_heap.top() << " ";
min_heap.pop();
}
return 0;
}
另外还有unordere*系列的容器，摈弃了自动排序，在时间复杂度上有了提升，像 unordered_map 等。
还有multi系列，让一些不可重复存储的容器，比如map和set，支持重复存储相同元素，就可以顺带使用其排序功能，快速实现一些功能。
这些数据结构是C++编程中常用的基础，STL(标准模板库)为许多数据结构提供了现成的实现，但在某些情况下，了解如何手动实现这些数据结构也是非常重要的。
