数据结构 动态顺序表-vector

一、创建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);
}