植物大战 vector——C++
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
剖析STL库中的vector源代码对其模仿进行简单实现。
猛戳订阅🍁🍁 👉 [C++详解专栏] 👈 🍁🍁
这里是目录标题
vector的使用
template < class T,
class Alloc = allocator<T> >
class vector;
vector用的是类模板和string不同。
vector不仅可以存储intdouble类型也可以存储string类型。
vector里面可以存储任意类型的数据。
可以直接插入zhangsan等字符串的原因是因为他支持单参数的隐士类型转换。
本质是构造临时对象然后再push_back
vector<string> v;
v.push_back("zhangsan")
v.push_back("李四")
vector的遍历
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
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;
reserve增容
在vs的平台下是1.5倍的扩容而在Linux下是两倍的扩容。
单次增容越多插入n个值增容次数越少效率就越高。但可能浪费的空间也越多。
vector模拟实现
模拟实现的意义是加深对vector这个容器的理解。
首先了解一下vector的源代码。源代码也就500行
所有的容器都用了空间配置器STL申请内存用的是空间配置器。咱们模拟实现直接向堆申请就可以。
看源代码首先看框架不要细看。
匿名对象
T()是匿名对象对于内置类型来说也有构造函数int是0double是0.0。
析构函数
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endofstoage = nullptr;
}
}
迭代器区间构造
vector是一个类模板我们还可以在类模板中继续增加参数。这个参数是给整个类用的。
我们可以声明一个 再模板 供给这个迭代器函数用这个 再模板的好处是可以接收不同容器的迭代器比如string list 等等。
1.类模板里面还可以再声明模板参数
2.目的是只为了让这个函数用。不用在第一个类模板中加入。
3.声明成模板的原因是不仅是vector的迭代器可以调用list的迭代器也可以调用string的也行。
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}
拷贝构造
void swap(vector<T>& v)
{
//调用库里的swap现代写法简洁
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstoage, v._endofstoage);
}
//拷贝构造
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
赋值构造
//赋值构造
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
//int到无符号整型size_t发生类型转换。
vector(/*size_t*/int n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
insert迭代器失效问题
说明迭代器失效问题在下面的vector模拟是实现的源代码中有实例。
注意迭代器失效问题对于野指针失效在不同平台下结果不同Linux下不不会崩溃报错对于vs来说会出现崩溃报错。
所以越界不一定报错
1.在扩容后pos还指向原空间**pos是野指针这时候pos已经释放掉。**所以才导致迭代器失效pos就是迭代器。
所以pos需要更新可以算出来pos-_start的相对距离。
这时候只是改变了函数内部的pos。但是形参的改变不会影响实参所以需要return 返回pos。
2.以在偶数前面插入10为例此时会扩容it传给pos是值传递pos的改变不会影响it导致it失效。
3.针对第2种情况即使不需要扩容空间足够it每次++指向的位置不对会导致这个程序持续插入10也会导致迭代器失效。
解决方法让其insert插入后函数内返回新的pos函数外然后重新定义变量进行接收pos值。
vector的insert的返回值是返回新插入元素的迭代器。
erase迭代器失效问题
到底有没有实效还是看平台。不同平台下结果不同。反正要按照最坏的情况下来看。
erase函数有两个删除pos位置的值。和迭代器区间删除。
一般vector删除数据都不考虑缩容。**缩容是以时间换空间**因为现在空间很大。现在比较关注时间效率。
返回值返回的是刚删除的位置pos。
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish)
iterator it = pos + 1;
while(it != _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
erase的实效都是意义变了或者不在有效访问数据的有效范围了。因为不考虑缩容的情况(缩容需要开新空间拷贝数据)所以不会存在野指针的实效。
1.第一种失效原因是因为删除的vector中的最后一个值然后返回了当前删除的位置虽然访问没有造成野指针但是在vs下访问该pos位置的值也会报错。但是在Linux下不会检查报错。
2.假如删除连续的偶数就会出现意义变了的迭代器失效。
或者刚好最后一个数是偶数这时候it++后it和end()错位了所以也导致一些问题。
深浅拷贝问题
在vector中当T是涉及深浅拷贝的类型时。
如string/vector等等我们扩容使用memcpy拷贝数据存在浅拷贝问题可能导致两个指针指向同一块内存。
vector模拟实现源代码
#pragma once
#include<assert.h>
namespace cao
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{}
//类模板里面还可以再声明模板参数
//目的是只为了让这个函数用。不用在第一个类模板中加入。
//声明成模板的原因是不仅是vector的迭代器可以调用list的迭代器也可以调用string的也行。
template<class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}
void swap(vector<T>& v)
{
//调用库里的swap现代写法简洁
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstoage, v._endofstoage);
}
//拷贝构造
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
//赋值构造
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
//int到无符号整型size_t发生类型转换。
vector(/*size_t*/int n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
~vector()
{
if (_start)
{
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)
{
size_t sz = size();
if (n > capacity())
{
T* tmp = new T[n];
if (_start)
{
for (size_t i = 0; i < size(); i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
}
//更新_finish和_endofstoage
_finish = _start + sz;
_endofstoage = _start + n;
}
//扩容+初始化
void resize(size_t n, T val = T())
{
if (n > capacity())
{
reserve(n);
}
if (n > size())
{
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
//缩容
else
{
_finish = _start + n;
}
}
//返回引用是为了可读可写
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
void push_back(const T& x)
{
/*if (_finish == _endofstoage)
{
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
}
*_finish = x;
++_finish;*/
insert(end(), x);
}
void pop_back()
{
if (_finish > _start)
{
--_finish;
}
}
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
//扩容以后pos就失效了需要更新pos
if (_finish == _endofstoage)
{
size_t n = pos - _start;//计算相对位置
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
pos = _start + n;//更新pos
}
//挪动数据
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator it = pos + 1;
while (it != _finish)
{
*(it - 1) = *it;
++it;
}
//假如it走到finish或者it就是finish则直接减减就可以尾删。
--_finish;
return pos;
}
private:
iterator _start;
iterator _finish;
iterator _endofstoage;
};
void test1()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.pop_back();
v.pop_back();
vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
for (size_t i = 0; i < v.size(); ++i)
{
cout << v[i] << " ";
}
cout << endl;
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
//测试insert
void test2()
{
/*vector<int> v;
v.resize(10, -1);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;*/
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;
}
//测试insert迭代器失效
void test3()
{
//在所有偶数前面插入2
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
vector<int>::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.insert(it,20);
++it;
}
++it;
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
//测试erase的迭代器失效
void test4()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(4);
v.push_back(5);
cout << v.size() << ":" << v.capacity() << endl;
auto pos = find(v.begin(), v.end(), 4);
if (pos != v.end())
{
v.erase(pos);
}
cout << *pos << endl;
*pos = 10;
cout << *pos << endl << endl;
cout << v.size() << ":" << v.capacity() << endl;
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
void test5()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
vector<int> v1(v.begin(), v.end());
std::string s("hello");
vector<int> v2(s.begin(), s.end());
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
vector<int> v3(v);
for (auto e : v3)
{
cout << e << " ";
}
cout << endl;
v1 = v2;
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
void test6()
{
// 排除法
vector<int> v1(10, 2);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
vector<char> v2(10, 'x');
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
}
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> vv;
vv.resize(numRows);
for (size_t i = 0; i < vv.size(); ++i)
{
// 杨辉三角每行个数依次递增
vv[i].resize(i + 1, 0);
// 第一个和最后一个初始化成1
vv[i][0] = 1;
vv[i][vv[i].size() - 1] = 1;
}
for (size_t i = 0; i < vv.size(); ++i)
{
for (size_t j = 0; j < vv[i].size(); ++j)
{
if (vv[i][j] == 0)
{
// 中间位置等于上一行j-1 和 j个相加
vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];
}
}
}
for (size_t i = 0; i < vv.size(); ++i)
{
for (size_t j = 0; j < vv[i].size(); ++j)
{
cout << vv[i][j] << " ";
}
cout << endl;
}
cout << endl;
return vv;
}
};
void test7()
{
vector<vector<int>> ret = Solution().generate(5);
for (size_t i = 0; i < ret.size(); ++i)
{
for (size_t j = 0; j < ret[i].size(); ++j)
{
cout << ret[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
}