目录
一.vector的定义
1.vector构造函数
2.vector遍历
3.vector的增容
（1）两种版本下的扩容
（2）单次增容增多少的问题分析:（不用考虑内存对齐）
（3）vector开空间用reserve还是resize？——用reserve
（4）string vector等都有一个特点，删除数据，一般是不会主动缩容
4.vector的几个常用函数
（1）insert，erase
（2）swap
（3）clear
（4）vector中没有find函数，要用算法中的find函数
（5）算法中的排序 sort
一.vector的定义
定义：可以动态增长的数组
1.vector构造函数
size_type 就是被typedef的size_t
#include#include using namespace std; void test_vector1() { vector v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); vector v2; v2.push_back(1.1); v2.push_back(2.2); v2.push_back(3.3); vector v3; v3.push_back("李白"); //单参数的构造函数支持隐式类型转换： v3.push_back("杜甫"); //string s="hello world";先构造再拷贝构造 v3.push_back("苏轼"); v3.push_back("白居易"); vector v4(10, 5); vector v5(++v3.begin(), --v3.end()); //迭代器，此处是"杜甫"，"苏轼" string s = "hello world"; vector v6(s.begin(), s.end()); }
2.vector遍历
与string遍历大致相同
void test_vector2()
{
// 遍历
vector v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
// 1、下表+[]
for (size_t i = 0; i < v.size(); ++i)
{
v[i] += 1;
cout << v[i] << " ";
}
cout << endl;
// 2.迭代器
vector::iterator it = v.begin();
while (it != v.end())
{
*it -= 1;
cout << *it << " ";
++it;
}
cout << endl;
// 3.范围for
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
3.vector的增容
（1）两种版本下的扩容
vs下面-- PJ版本——1. 5倍增容
linux g++ SGI版本——2倍增容
（2）单次增容增多少的问题分析:（不用考虑内存对齐）
即为什么vs下扩容按1.5倍扩容，linux的g++扩容按2倍扩容？
单次增容越多，插入N个值，增容次数越少，效率就越高，但是浪费空间就越多；
单次增容越少，浪费空间就少了，但是会导致频繁增容，效率低下。
因此不一定是1.5倍或者2倍，也可能是3,4倍，只是1.5或2倍是一个比较平衡的值。
（3）vector开空间用reserve还是resize？——用reserve
如果知道要开多大空间，就用reserve提前开好。
如果用resize就是开空间并初始化，比如foo.resize(100); 开100个int空间，全部初始化成0，如果再foo.push_back(i); 就是在这100个空间以后再加数据，因为前100个已经有数据了
void test_vector3()
{
//vector v;
//cout << v.max_size() << endl;
size_t sz;
std::vector foo;
foo.reserve(100); //如果知道要开多大空间，就用reserve提前开好
//foo.resize(100);
sz = foo.capacity();
std::cout << "making foo grow:n";
for (int i = 0; i < 100; ++i) {
foo.push_back(i);
if (sz != foo.capacity()) {
sz = foo.capacity();
std::cout << "capacity changed: " << sz << 'n';
}
}
}
（4）string vector等都有一个特点，删除数据，一般是不会主动缩容
若非要缩容，那就用函数 shrink_to_fit() ，但是要慎用，少用，表面是缩容_capacity——>_size，实际它的底层是开辟一块_size的空间，并把内容拷贝过来，实际上是用时间换空间了，但是我们一般是不差空间的，而且通常是用空间换时间，所以说不建议时间换空间的做法，即：少用 shrink_to_fit() 函数。
void test_vector3()
{
//vector v;
//cout << v.max_size() << endl;
size_t sz;
std::vector foo;
foo.reserve(100);
//foo.resize(100);
sz = foo.capacity();
std::cout << "making foo grow:n";
for (int i = 0; i < 100; ++i) {
foo.push_back(i);
if (sz != foo.capacity()) {
sz = foo.capacity();
std::cout << "capacity changed: " << sz << 'n';
}
}
//vector countV;
//countV.resize(100, 1);
//countV.resize(10);
// string vector等都有一个特点，删除数据，一般是不会主动缩容
foo.resize(10);
cout << foo.size() << endl;
cout << foo.capacity() << endl;
// 慎用、少用
foo.shrink_to_fit();
cout << foo.size() << endl;
cout << foo.capacity() << endl;
}
4.vector的几个常用函数
（1）insert，erase
他们都是不支持下标增加或删除的，都是用的迭代器
返回值是iterator是为了解决迭代器失效，这个后面再详细说。
void test_vector4()
{
// 遍历
vector v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.insert(v.begin(), -1);
v.insert(v.begin(), -2);
v.insert(v.begin(), -3);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
v.insert(v.begin()+7, 300);
//v.insert(v.begin()+8, 300);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
v.erase(v.begin());
v.erase(v.begin());
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
（2）swap
交换两个vector类对象指向的空间，例如：v1.swap(v2);
（3）clear
清掉全部数据
（4）vector中没有find函数，要用算法中的find函数
algorithm——算法 #include
void test_vector5()
{
// 遍历
vector v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
//vector::iterator pos = find(v.begin(), v.end(), 3);
auto pos = find(v.begin(), v.end(), 3); //类型太长可以用auto
if (pos != v.end())
{
cout << "找到了" << endl;
v.erase(pos);
}
else
{
cout << "没有找到" << endl;
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
（5）算法中的排序 sort
#include
sort默认是升序
void test_vector5()
{
// 遍历
vector v;
v.push_back(1);
v.push_back(2);
v.push_back(4);
v.push_back(0);
v.push_back(9);
v.push_back(3);
v.push_back(1);
// 默认是升序
sort(v.begin(), v.end()); // <
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
排降序，仿函数
关于仿函数，大家先记住这个用法，具体我们后面讲队列再详细讲
void test_vector5()
{
// 遍历
vector v;
v.push_back(1);
v.push_back(2);
v.push_back(4);
v.push_back(0);
v.push_back(9);
v.push_back(3);
v.push_back(1);
// 默认是升序
//sort(v.begin(), v.end()); // <
// 排降序，仿函数
// 关于仿函数，大家先记住这个用法，具体我们后面讲队列再详细讲
// sort(v.begin(), v.end(), greater()); // >
greater g;
sort(v.begin(), v.end(), g); // >
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
5.题目：杨辉三角
118. 杨辉三角
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1 输出: [[1]]
解法：
