C++ —— vector1
(constructor)构造函数的声明接口说明vector()（重点）无参构造构造并初始化n个valvector(const vector& x)（重点）拷贝构造使用迭代器进行初始化构造int main()return 0;
1.vector的介绍及使用
1.1vector的介绍
1.2vector的使用
vector的学习和string的学习是一样的，一定要学会查看文档，在实际中我们熟悉常见的接口就好了，下面列出重点的接口：
1.2.1 vector的定义
| (constructor)构造函数的声明 | 接口说明 |
| vector()（重点） | 无参构造 |
| vector(size_type n,const value_type&val=value_type()) | 构造并初始化n个val |
| vector(const vector& x)（重点） | 拷贝构造 |
| vector(Inputlterator first,InputIterator last) | 使用迭代器进行初始化构造 |
支持以下这样的方式去初始化：
int main()
{
vector<int> v3{ 0,10,20,30,40,50 };
for (auto e : v3)
{
cout << e << " ";
}
cout << endl;
return 0;
}运行结果：
1.2.2 vector iterator 的使用
| iterator的使用 | 接口说明 |
| begin+end(重点) | 获取第一个数据位置的 iterator/const_iterator,获取最后一个数据的下一个位置的iterator/const_iterator |
| rbegin+rend | 获取最后一个数据位置的reverse_iterator,获取第一数据前一个位置的reverse_iterator |
1.2.3 vector空间增长问题
| 容量空间 | 接口说明 |
|
size |
获取数据个数 |
| capacity | 获取容量大小 |
| empty | 判断是否为空 |
| resize（重点） | 改变vector的size |
| reserve（重点） | 改变vector的capacity |
vector扩容机制：
vs下：
void TestVectorExpand()
{
size_t sz;
vector<int> v;
sz = v.capacity();
cout << "making v grow:\n";
for (size_t i = 0; i < 100; i++)
{
v.push_back(i);
if (sz != v.capacity())
{
sz = v.capacity();
cout << "capacity changed:" << sz << '\n';
}
}
}运行结果：
从运行结果上来看vs下是1.5倍的扩容
linux下：
同样的代码拿到Linux下去运行
运行结果：
从运行结果来看Linux是2倍的扩容
如何进行减少扩容呢？
添加上代码：
v.reserve(100);void TestVectorExpand()
{
vector<int> v;
size_sz = v.capacity();
v.reserve(100); //提前将容量设置好，可以避免频繁的扩容
cout << "making v grow:\n";
for (size_t i = 0; i < 100; i++)
{
v.push_back(i);
if (sz != v.capacity())
{
sz = v.capacity();
cout << "capacity changed:" << sz << '\n';
}
}
}- capacity的代码在vs和g++分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。不要固化的认为，vector增容都是2倍，具体增长多少看具体的需求定义。vs是PJ版本STL，g++是SGI版本STL。
- reserve只负责开辟空间，如果确定知道需要多少空间，reserve可以缓解vector增容的代价缺陷问题。
- resize在开空间的同时还会进行初始化，影响size。
1.2.4 vector 增删查改
| vector 增删查改 | 接口说明 |
| push_back（重点） | 尾插 |
| pop_back（重点） | 尾删 |
| find | 查找。（这个是算法模块实现的，不是vector的接口） |
| insert | 在position之前插入value |
| erase | 删除position位置的数据 |
| swap | 交换两个vector的数据空间 |
| operator[]（重点） | 像数组一样访问 |
insert的使用:
int main()
{
vector<int> v1 = { 11,22,33,44,55 };
//insert尽可能少用，因为头插的话就会设计将数据整体向后挪动，效率非常低
v1.insert(v1.begin(), 1);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
//想在第三个位置之前进行插入数据
v1.insert(v1.begin()+3, 1);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
return 0;
}运行结果：
vector是不支持流插入流提取的，因为string是一个串，可以输入一个串，可以输出一个串，vector可以用迭代器或者是范围for来控制输入和输出就没有支持流插入和流提取
vector<char>和string的区别：
vector<char> v2 = { 'a','b','c' };
string s1("abc");不能用vector<char>来替换string，原因：
1.看起来都是存储“abc”三个字符的数组，但是 string s1("abc");是含有 ‘\0’ 的，有 ‘\0’ 才能兼容C语言；vector<char> v2 = { 'a','b','c' };没有 '\0'，不兼容C语言。
2.string有一些专用的接口是vector没有的，string不仅尾插一个值甚至还尾插一个串之类的，所以vector<char>无法替代string
1.2.5 vector跟算法的关系：
1.2.5.1 push_back
int main()
{
vector<int> v1; //int的顺序表
vector<string> v2; //string的顺序表——对象数组
vector<vector<int>> v3; //vector<int>就是一个二维数组
//单参数构造支持隐式类型转化
string name1 = "张三";
v2.push_back(name1); //有名对象
v2.push_back(string("李四")); //匿名对象
v2.push_back("小二");
for (const auto& e : v2) //v2中的每个对象string给e是一个深拷贝
{
cout << e << " ";
}
cout << endl;
return 0;
}上述是一个更加安全的范围for的一个写法，如果上述类型是内置类型，可以不用加上引用，但是向v2中每个对象都是string的话，给e的话就会涉及深拷贝，所以建议加上引用，如果不涉及修改的话也将const加上。
容器和算法是通过迭代器来访问的：
1.2.5.2 find：
int main()
{
vector<int> v1 = { 1,2,3,4,5 };
list<int> It1 = { 6,7,8,9,10 };
vector<string> v2;
vector<vector<int>> v3;
string name1 = "张三";
v2.push_back(name1);
v2.push_back(string("李四"));
v2.push_back("小二");
for (const auto& e : v2)
{
cout << e << " ";
}
cout << endl;
int x = 0;
cin >> x;
//vector<int>::iterator it1 = find(v1.begin(), v1.end(), x);
auto it1 = find(v1.begin(), v1.end(), x);
if (it1 != v1.end())
{
cout << x << "找到了" << endl;
}
cin >> x;
auto it2 = find(It1.begin(), It1.end(), x);
if (it2 != It1.end())
{
cout << x << "找到了" << endl;
}
return 0;
}1.2.5.3sort：
int main()
{
vector<int> v1 = { 1,20,-23,4,15 };
list<int> It1 = { 6,7,8,9,10 };
vector<string> v2;
vector<vector<int>> v3;
sort(v1.begin(), v1.end());
for (const auto& e : v1)
{
cout << e << " ";
}
cout << endl;
return 0;
}运行结果：
默认排的是升序。
list迭代器不支持用sort。
降序的实现：
sort(v1.begin(), v1.end(), greater<int>());
for (const auto& e : v1)
{
cout << e << " ";
}
cout << endl;运行结果：
1.2.5.4 vector底层的实现：
1.简单功能的实现
namespace ysy
{
template<class T>
class vector
{
public:
typedef T* iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
vector()
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{}
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t oldsize = size();
T* tmp = new T[n];
memcpy(tmp, _start, sizeof(T) * oldsize);
delete[] _start;
_start = tmp;
_finish = _start + oldsize;
_end_of_storage = _start + n;
}
}
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
reserve(capacity() = 0 ? 4 : capacity() * 2);
}
*_finish = x;
_finish++;
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
#include"vector.h"
int main()
{
ysy::vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
for (const auto& e : v1)
{
cout << e << " ";
}
cout << endl;
return 0;
运行结果：
string和vector都不直接提供头删和头插，会影响效率，但是insert和erase都间接的提供。vector最简单的迭代器是指针，迭代器可以理解为是像指针的一样的东西，也可以不是指针。vector和string在这里选择了用指针来实现，但是也不一定用指针来实现。库里面的迭代器就没有用指针包括Linux也没有用指针来实现
int main()
{
std::vector<int> v;
cout << typeid(std::vector<int>::iterator).name() << endl;
return 0;
}
可以从上面的运行结果看出：迭代器的类型不是指针，但是迭代器的类型可以是指针，总的来说：迭代器的行为像指针一样。
2.resize的实现：
void reszie(size_t n, const T& val = T())
{
if (n < size())
{
_finish = start + n;
}
else
{
reserve(n);
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}int main()
{
ysy::vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(30);
v1.push_back(4);
v1.push_back(5);
for (const auto& e : v1)
{
cout << e << " ";
}
cout << endl;
v1.resize(8, 10);
for (const auto& e : v1)
{
cout << e << " ";
}
cout << endl;
v1.resize(20, 10);
for (const auto& e : v1)
{
cout << e << " ";
}
cout << endl;
v1.resize(5);
for (const auto& e : v1)
{
cout << e << " ";
}
cout << endl;
return 0;
}运行结果：
resize主要的的使用场景：将空间开好并将值放进去进行初始化：
ysy::vector<int> v2;
v2.resize(100, 1);
for (const auto& e : v2)
{
cout << e << " ";
}
cout << endl;运行结果：
3.vector的拷贝构造：
//vector的拷贝构造
int main()
{
ysy::vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(30);
v1.push_back(4);
v1.push_back(5);
ysy::vector<int> v2(v1);
//ysy::vector<int> v2 = v1; //也是拷贝构造
for (const auto& e : v2)
{
cout << e << " ";
}
cout << endl;
return 0;
}上面代码是有问题的：
浅拷贝存在的问题：
1.会析构两次
2.一个改变会影响另外一个
解决方法：写深拷贝（不一定要实现一个一个的开空间，可以复用现有的接口来完成）
//v2(v1) 拷贝构造
//类里面支持不写<T>,但是类外面是一定要写<T>,但是建议类里面还是写上
//vector(const vector& v)
vector(const vector<T>& v)
{
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}
运行结果：
4.赋值操作的实现：
4.1 传统写法：
//v1=v3 赋值
vector<T> operator=(const vector<T>& v)
{
if (this!=&v)
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}
return *this;
} //赋值
ysy::vector<int> v3;
v3.resize(100, 1);
v1 = v3;
for (const auto& e : v3)
{
cout << e << " ";
}
cout << endl;
运行结果：
4.2 现代写法：（只要拷贝构造写的没有问题）
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
//v1=v3 赋值 现代写法
vector<T>& operator=( vector<T> v)
{
swap(v);
return *this;
}
构造函数在这里什么都没写，可以删掉吗？
——不可以，虽然看起来什么都没写，但是却有意义，因为_start、_finish、_end_of_storage给了缺省值，不写的话编译器会在初始化列表阶段会自动初始化，不是不写会自动生成一份默认构造吗？对应内置类型or自定义类型，声明的时候给了缺省值，但是拷贝构造也是一个构造，构造的定义只要你写了构造（拷贝构造），默认构造就不会再生成了，拷贝构造也是会影响默认构造的生成。所以这里的默认构造即使没有任何的内容，也是要写上的。
运行结果：
int main()
{
ysy::vector<string> v1;
v1.push_back("11111111111111111111111111111111");
v1.push_back("11111111111111111111111111111111");
v1.push_back("11111111111111111111111111111111");
v1.push_back("11111111111111111111111111111111");
for (const auto& e : v1)
{
cout << e << " ";
}
cout << endl;
return 0;
}运行结果：（没问题）
但是再多插入一行时就会出现问题：
运行结果：（出现乱码：野指针、内存问题）
猜测应该是扩容的问题，调试一下（先走粗线条）：
执行完reserve出现问题，在reserve那行打断点，进入内部（F11）去查看：
注意：当前位置出问题不一定是当前位置的错，同城情况下delete不一定会出错，delete出现错误一般是：不匹配 or 释放的位置不对。这里的问题是memcpy的浅拷贝导致的。
_start 和 tmp 指向的是同一块空间：
delete[] _start; - > n个对象调用n次析构函数
所以前4个数据由于delete了多次，前4个数据就是有问题的，第5个新插入的是没有问题的。前4个释放掉了，相当于是野指针。
如何解决呢？—— 不用memcpy；完成深拷贝，各自指向各自的空间
void reserve(size_t n)
{
if (n > capacity())
{
size_t oldsize = size();
T* tmp = new T[n];
//memcpy(tmp, _start, sizeof(T) * oldsize); //会出现浅拷贝的问题
for (size_t i = 0; i < oldsize; i++)
{
//内置类型无问题，string类型完成深拷贝
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finish = _start + oldsize;
_end_of_storage = _start + n;
}
}运行结果：
1.2.6 vector 迭代器失效问题（重点）
迭代器的主要作用是让算法能够不用关心底层数据结构，其实底层结构就是一个指针，或者是对指针的进行了封装，比如：vector的迭代器就是原生态指针T*。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，，而使用一块已经被释放的空间，造成的后果就是程序崩溃（即如果继续使用已经失效的迭代器，程序就可能会崩溃）。
对于vector可能会导致其迭代器失效的操作有：
会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等等。先看看 insert 和 erase 的实现。
1.2.6.1 第一层（insert：野指针）的迭代器失效：
insert的实现：
void insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
//满了就扩容
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
}v1.insert(v1.begin(), 10);
for (const auto& e : v1)
{
cout << e << " ";
}
cout << endl;运行结果：
上述代码实际上是有问题的。
将插入数据5次变为插入数据4次：
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);此时的运行结果：
4次插入数据和5次插入数据有扩容的情况，推测应该就是扩容的问题。
_start和pos位置是一样的。
但是扩完容之后_start的位置改变了，但是pos的位置没有改变，这就导致while (end >= pos) end大于pos，不知道要循环多少次。
void insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
//满了就扩容,扩容导致pos失效，失效后不能使用，更新后才能使用
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
}
//Test.cpp
int main()
{
ysy::vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.insert(v1.begin(), 10);
func(v1);
v1.erase(v1.begin() + 2);
func(v1);
return 0;
}运行结果：
将上述的Test.cpp改为下面的代码：
int main()
{
ysy::vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
//v1.push_back(5);
func(v1);
int i = 0;
cin >> i;
auto it = v1.begin() + i;
v1.insert(it, 10);
v1.insert(v1.begin(), 10);
func(v1);
v1.erase(v1.begin() + 2);
func(v1);
return 0;
}上述代码中的 it 是不是已经失效了呢？
答案是：it 也是失效了的，不能再使用，加上代码：cout << *it << endl;
运行结果：（迭代器失效不一定会报错，具体看不同的编译器）
将pos位置改变之后，为什么还会出现错误：
因为 it 是形参，pos 是实参，形参的改变不会影响实参的改变，外面的迭代器依旧是失效的。
如果用 insert ，insert 之后默认迭代器都失效了，不能使用迭代器，迭代器后面的位置也是不能使用的，之前创建的迭代器也是不能使用的。
这里加上一个& 
之后，it 不失效了，但是这样是不行的，加上& 只能传左值，当我们传右值的时候，是不行的：
，（it+1） 可以理解为临时变量，因为临时变量具有常性，不能给给引用，权限被放大，那就再加上 const ，但是加上 const 不能修改 pos：
所以要使用只有更新之后才能使用，失效之后的迭代器不要访问。所以insert是会导致迭代器失效的，迭代器失效源自于扩容。
1.2.6.2 第二层（erase：强制检查的标记）的迭代器失效：
erase的实现：
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos + 1;
//挪动数据
while (begin < _finish)
{
*(begin - 1) = *begin;
++begin;
}
--_finish;
} v1.erase(v1.begin() + 2);
func(v1);运行结果：
其实上述代码是有问题的：
int main()
{
std::vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
//删除所有的偶数
auto it = v1.begin();
while (it != v1.end())
{
if (*it % 2 == 0)
{
v1.erase(it);
}
++it;
}
return 0;
}运行结果：（都不能跑）
将上面的代码放到g++下：（不同的平台有不同的效果）
改进之后的代码：（这个程序在Linux下是可以的，但是在vs下是不行的）
g++下：（没问题）
vs下：（不行）
vs对迭代器失效的检查非常严格。erase以后的迭代器他认为失效了，
不能访问马，失效的迭代器进行了标记，一访问就报错（如果不强制检查的话也是可以运行的）。
如何解决呢？—— 在使用前，对迭代器重新赋值即可。
int main()
{
std::vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(30);
v1.push_back(4);
v1.push_back(5);
for (const auto& e : v1)
{
cout << e << " ";
}
cout << endl;
//解决办法：更新了之后才能使用
auto it = v1.begin();
while (it != v1.end())
{
if (*it % 2 == 0)
{
it = v1.erase(it);
}
else
{
++it;
}
}
for (const auto& e : v1)
{
cout << e << " ";
}
cout << endl;
return 0;
}
运行结果：
所以引用自己的那套要增加一个返回值才可以用：
1.2.7 vector 在OJ中的使用
杨辉三角：
C语言的实现是比较麻烦的，开辟、释放的问题。
使用vector<vector<int>>就不用管释放的问题，用完之后编译器会自动调用析构函数。逻辑上虽然绕，但是用起来很方便。
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
17
0- 0
已为社区贡献2条内容
所有评论(0)