前言:
本章我们将学习STL中另一个重要的类模板vector…
- vector是表示可变大小数组的序列容器。
- 就像数组一样，vector也采用的连续存储空间来存储元素。但是又不像数组，它的大小是可以动态改变的
- 本质讲，vector使用动态分配数组来存储它的元素
- vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。
能不能用vector来替代string呢？
- 可以是可以，但是有区别的，string的部分功能vector实现不了,比如：流插入>>和流提取 <<
- string比较大小是按照ASCII码比较，但是vector的规则就不一样了。
- Vector 是没有重载<< 和>>操作符的 find( )，以及以下使用情况，
vector < char> T；
string str ； // 数据结尾\0 、+=、find、比较大小、to_string、<< 、>>等等
// vector < char> 无法替代string
目录
1. vector的使用
1.1 vector的构造：
在我们使用vector之前我们需要先包一下头文件#include< vector >
int main ()
{
// constructors used in the same order as described above:
std::vector<int> first; // empty vector of ints
std::vector<int> second (4,100); // four ints with value 100
std::vector<int> third (second.begin(),second.end()); // iterating through second
std::vector<int> fourth (third); // a copy of third
// the iterator constructor can also be used to construct from arrays:
int myints[] = {16,2,77,29};
std::vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );
}
1.2 vector的迭代器：
用法和string中的迭代器一样.
void test_vector2()
{
//遍历
vector<int> 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<int>::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;
}
1.3 vector的内存管理：
STL中vector每次扩容的规律：
void test_vector3()
{
//vector<int> v;
//cout << v.max_size() << endl;
//Capicity容量测试 -- VS是PJ版本 大概是1.5倍增容，Linux是SGI版本 是2倍增容
size_t sz;
vector<int> v;
sz = v.capacity();
cout << "making v grow:\n";
for (int i = 0; i < 100; ++i)
{
v.push_back(i);
if (sz != v.capacity())
{
sz = v.capacity();
cout << "capacity changed: " << sz << '\n';
}
}
}
内存管理数据分析：
- 单次增容越多，插入N个值，增容次数越少，效率就越高
- 单次增容越多，造成空间浪费。
reserve / resize 的使用：
- reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
- resize在开空间的同时还会进行初始化，影响size
| 容量空间 | 接口说明 |
|---|---|
| resize（重点） | 改变vector的size |
| reserve （重点 | 改变vector的capacity |
void tese_vector4()
{
vector<int> countV;
//resize 开空间 + 初始化
countV.resize(100, 1);
countV.resize(10);
countV.reserve(1000);
//sting 和 vector等都有一个特点，删除数据，一般不会主动缩容的
countV.shrink_to_fit();
cout << countV.size() << endl;
cout << countV.capacity() << endl;
cout << endl << endl;
//操作系统的空间不允许一部分一部分还
//vector没有头插头删，效率比较低
}
insert / erase 的使用：
void test_vector5()
{
//遍历
vector<int> 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, 3000);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
v.erase(v.begin());
v.erase(v.begin());
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
1.4 迭代器可以访问容器：
void test_vector6()
{
vector<int> v;
//auto pos = find(v.begin(), v.end(), 3);
vector<int>::iterator pos = find(v.begin(), v.end(), 3);
if (pos != v.end())
{
cout << "找到了" << endl;
v.erase(pos);
}
else
{
cout << "没有找到" << endl;
}
for (auto ch : v)
{
cout << ch << " ";
}
cout << endl;
v.push_back(0);
v.push_back(9);
v.push_back(3);
v.push_back(1);
//默认是升序
//sort(v.begin(), v.end()); // <
//排降序，使用仿函数greater
//关于仿函数，先记住这个用法，具体后面学习队列细学
sort(v.begin(), v.end(), greater<int>()); // > ，greater<int>()匿名对象
}
- 仿函数我们后期会学，先包一下头文件:#include< functional> – 仿函数
- vector和list没有find，没有查找函数，我们需要包一个算法的头文件 #include< functional >
2. vector的模拟实现
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
//构造函数1
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{}
//给一个迭代器的区间去构造2
template<class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{
while (first != last)
{
push_back(*first);
first++;
}
}
//用n个val初始化3
vector(size_t n, const T& val = T())
: _start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
//重载一个int n （逻辑和上面一样）
vector(int n, const T& val = T())
: _start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstoage, v._endofstoage);
}
//拷贝构造--现代写法1
vector(const vector<T>& v)
//vector(const vector& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{
//拷贝构造中调用一个构造函数，构造一个tmp出来
vector<T> tmp(v.begin(), v.end());
//通过this指针调用该对象的成员函数
this->swap(tmp);
}
//-----现代写法2
vector<T>& operator=(vector<T> v)
{
this->swap(v);
return *this;
}
}
C++中，内置类型也可以认为，有构造函数和析构函数
原因在于：1.这样可以更好支持模板 2.void resize(size_t n, T val = T()) 与类的对象使用方法一样：
int i=0;
int j= int(1)
int m(1);
//资源清理
~vector()
{
if (_start != nullptr)
{
delete[] _start;
_start = _finish = _endofstoage = nullptr;
}
}
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endofstoage - _start;
}
void reserve(size_t n)
{
//这里存在start更新之后就算不准的现象
size_t sz = size();
if (n > capacity())
{
T* tmp = new T[n];
if (_start != nullptr)
{
//memcpy(tmp, _start, size() * sizeof(T));
//这里是浅拷贝，所以会有问题
for (size_t i = 0; i < size(); i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
}
_finish = _start + sz;
_endofstoage = _start + n;
}
注意：
- 一开始的时候 _finish 和 _start 都是0空指针nullptr
- _start被更新了，要是这样：_finish = _start + size();
- 不能用size( )，要是这样：_finish = _start + _finsih - _start;
//生成T类型的匿名对象，C++内置类型也有默认构造函数
//分3种情况：
1.n>capacity 需要扩容+初始化
2.n>size && n<=capacity 初始化
3.n<size 删除数据
void resize(size_t n, const T& val = T())
{
if (n > capacity())
{
reserve(n);
}
if (n > size())
{
while (_finish < _start + n)
{
*_finish = val;
_finish++;
}
}
else
{
_finish = _start + n;
}
}
void push_back(const T& x)
{
/*if (_finish == _endofstoage)
{
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
}
*_finish = x;
_finish++;*/finish代表最后一个，所以要加一个
insert(end(), x);
}
void pop_back()
{
/*if (_finish > _start)
{
_finish--;
}*/
//返回的临时对象不能改变，不能++(自增)和--(自减)
erase(end() - 1);
}
T& operator[](size_t pos)
{
assert(pos <= size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
2.1 迭代器失效问题
两种迭代器失效原因：
- 1.野指针
- 2.意义变了
与vector类似, string在插入+扩容操作+ erase之后,迭代器也会失效
1.在迭代器位置P插入数据以后，不要访问P了，因为P可能失效了
auto p=find(v.begin( ),v.end( ),3);
if（p!=v.end( ))
{
v.insert（p,30);
cout<<*p<<endl;
//这里最好就不要使用了，迭代器P已经失效了，如果必须要有，要接收返回值，对P重新赋值
v.insert（p,30);
}
- 总结一下,如果必须要用，为了防止迭代器失效,在使用迭代器前,对迭代器重新赋值即可
结论：insert/erase pos位置后，不要直接访问pos.一定要更新，因为直接访问，可能会出现各种出乎意料的结果，这就是所谓的迭代器失效
演示代码1：
void test_vector2()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.insert(v.begin(), 0);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
迭代器失效问题，是因为pos是不更新的。
- 当reserve扩容之后，如果是新空间，_start和_finish更新了，pos（就是v.begin()）还指向旧空间
- 但是旧空间被释放了，这个问题就是迭代器失效，pos为野指针
- 所以就插入失败了
- 迭代器发生了野指针的问题
insert函数中的内部pos指针更新了，但是形参的改变不会影响实参，pos指针是一个传值传参
//pos前一个位置插入（之前是void,所以错误）
iterator insert(iterator pos, const T& x)
{
//检查Pos位置是否合理
assert(pos >= _start && pos <= _finish);
//扩容
//扩容以后pos就失效了，需要更新一下
if (_finish == _endofstoage)
{
size_t n = pos - _start;
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
//更新迭代器的位置，做返回
pos = _start + n;
}
//挪动数据
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = x;
_finish++;
return pos;
}
**//有返回值是防止STL库里面有缩容的情况,不知道怎么实现的**
//如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是,没有元素的，那么pos就失效了
iterator erase(iterator pos) %-**-返回删除位置的下一个位置**
{
assert(pos >= _start && pos < _finish);
iterator begin= pos + 1;
while (begin != _finish)
{
*(begin - 1) = *begin;
begin++;
}
_finish--;
return pos;
}
void clear()
{
_finish = _start;
}
private:
iterator _start;
iterator _finish;
iterator _endofstoage;
};
//类外定义拷贝构造-模板写法：
template<typename T>
vector<T>::vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
this->swap(tmp);
}
2.1.1 Insert 和 Erase 迭代器失效的讨论：
vector<int>::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
//错误写法：
v.insert(it, 20)
//正确写法：
it = v.insert(it, 20);
it++;
}
it++;
}
(1)Insert 扩容的情况：（野指针）
- 如果扩容的话，迭代器将it指向原来的空间，原来的空间已经被释放了
- 当再次进入Insert时，it变成野指针。
(2) Insert 不扩容的情况：（意义变了）
insert以后虽然没有扩容，it不是野指针，但是it指向位置的意义变了
it++之后一直指向20，导致了我们这个程序重复插入20
不是it是野指针失效的，而是it指向的位置意义变了
也叫作迭代器失效
(3)Erase 缩容的情况：（野指针）
- STL里对erase的实现，有可能存在缩容实现，就会出问题
- 当再次进入erase时，it变成野指针。
(4) Erase不扩容的情况：（意义变了）
- erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效。
- 但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了
解决方案：
- 采取返回指针的话可以完美避开上述所有问题
- 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等
2.2 深浅拷贝问题
以杨辉三角为例：
vector<vector< int>> vv;
- vector<vectot< int >>表示里面的每个数据存的都是vector的对象
- 外面vector的是深拷贝，里面的Vector 使用的是memcpy( )做的是浅拷贝， 导致delete析构的时候，指向同一个空间，出现问题
- vector里面的T类型有可能是自定义类型，使用Memcpy( )就是浅拷贝，所以里面也要做深拷贝。
**结论：**如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃
尾声
看到这里，相信大家对这个C++有了解了。
如果你感觉这篇博客对你有帮助，不要忘了一键三连哦