数据结构 动态顺序表-vector

时间：2025-02-12 07:45:30

一、创建vector

#include <vector> // 头⽂件 
using namespace std;
const int N = 20;
struct node
{
 int a, b, c;
};
// 1. 创建 
void init()
{
 vector<int> a1; // 创建⼀个空的可变⻓数组 
 vector<int> a2(N); // 指定好了⼀个空间，⼤⼩为 N 
 vector<int> a3(N, 10); // 创建⼀个⼤⼩为 N 的 vector，并且⾥⾯的所有元素都是 10 
 vector<int> a4 = {1, 2, 3, 4, 5}; // 使⽤列表初始化，创建⼀个 vector 
 // <> ⾥⾯可以放任意的类型，这就是模板的作⽤，也是模板强⼤的地⽅ 
 // 这样，vector ⾥⾯就可以放我们接触过的任意数据类型，甚⾄是 STL 
 vector<string> a5; // 放字符串 
 vector<node> a6; // 放⼀个结构体 
 vector<vector<int>> a7; // 甚⾄可以放⼀个⾃⼰，当成⼀个⼆维数组来使⽤。并且每⼀维
都是可变的 
 
 vector<int> a8[N]; // 创建 N 个 vector 
}

二、size/empty

size ：返回实际元素的个数；
2. empty ：返回顺序表是否为空，因此是⼀个bool 类型的返回值。
a. 如果为空：返回true
b. 否则，返回false
时间复杂度：O(1) 。

// 2. size
void test_size()
{
 // 创建⼀个⼀维数组 
 vector<int> a1(6, 8);
 for(int i = 0; i < a1.size(); i++)
 {
 cout << a1[i] << " ";
 }
 cout << endl << endl;
 // 创建⼀个⼆维数组 
 vector<vector<int>> a2(3, vector<int>(4, 5));
 for(int i = 0; i < a2.size(); i++)
 {
 // 这⾥的 a2[i] 相当于⼀个 vector<int> a(4, 5) 
 for(int j = 0; j < a2[i].size(); j++)
 {
 cout << a2[i][j] << " ";
 }
 cout << endl;
 }
 cout << endl << endl;
}

三、begin/end

1. begin ：返回起始位置的迭代器（左闭）；
2. end ：返回终点位置的下⼀个位置的迭代器（右开）；
利⽤迭代器可以访问整个vector ，存在迭代器的容器就可以使⽤范围for 遍历。

// 3. begin/end
void test_it()
{
 vector<int> a(10, 1);
 // 迭代器的类型是 vector<int>::iterator，但是⼀般使⽤ auto 简化 
 for(auto it = a.begin(); it != a.end(); it++)
 {
 cout << *it << " ";
 }
 cout << endl << endl;
 // 使⽤语法糖 - 范围 for 遍历 
 for(auto x : a)
 {
 cout << x << " ";
 }
 cout << endl << endl;
}

四、push_back/pop_back

1. push_back ：尾部添加⼀个元素
2. pop_back ：尾部删除⼀个元素
当然还有insert 与erase 。不过由于时间复杂度过⾼，尽量不使⽤。
时间复杂度：O(1) 。

// 如果不加引⽤，会拷⻉⼀份，时间开销很⼤ 
void print(vector<int>& a)
{
 for(auto x : a)
 {
 cout << x << " ";
 }
 cout << endl;
}
// 4. 添加和删除元素 
void test_io()
{
 vector<int> a;
 // 尾插 1 2 3 4 5 
 a.push_back(1);
 a.push_back(2);
 a.push_back(3);
 a.push_back(4);
 a.push_back(5);
 print(a);
 // 尾删 3 次 
 a.pop_back();
 a.pop_back();
 a.pop_back();
 print(a);
}

五、front/back

1. front ：返回⾸元素；
2. back ：返回尾元素；
时间复杂度：O(1) 。

// 5. ⾸元素和尾元素 
void test_fb()
{
 vector<int> a(5);
 for(int i = 0; i < 5; i++)
 {
 a[i] = i + 1;
 }
 cout << a.front() << " " << a.back() << endl;
}

六、resize

• 修改vector 的⼤⼩。
• 如果⼤于原始的⼤⼩，多出来的位置会补上默认值，⼀般是0 。
• 如果⼩于原始的⼤⼩，相当于把后⾯的元素全部删掉。
时间复杂度：O(N) 。

// 如果不加引⽤，会拷⻉⼀份，时间开销很⼤ 
void print(vector<int>& a)
{
 for(auto x : a)
 {
 cout << x << " ";
 }
 cout << endl;
}
// 6. resize
void test_resize()
{
 vector<int> a(5, 1);
 a.resize(10); // 扩⼤ 
 print(a);
 a.resize(3); // 缩⼩ 
 print(a);
}

七、clear

• 清空vector 
底层实现的时候，会遍历整个元素，⼀个⼀个删除，因此时间复杂度：O(N) 。

// 如果不加引⽤，会拷⻉⼀份，时间开销很⼤ 
void print(vector<int>& a)
{
 for(auto x : a)
 {
 cout << x << " ";
 }
 cout << endl;
}
// 7. clear
void test_clear()
{
 vector<int> a(5, 1);
 print(a);
 a.clear();
 cout << a.size() << endl;
 print(a);
}

相关文章