剖析STL库中的vector源代码，对其模仿进行简单实现。
猛戳订阅🍁🍁 👉 [C++详解专栏] 👈 🍁🍁
vector的使用
template < class T,
class Alloc = allocator<T> >
class vector;
vector用的是类模板，和string不同。
vector不仅可以存储int，double类型，也可以存储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是0，double是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;
}
}
转载：https://blog.csdn.net/qq2466200050/article/details/128750249
查看评论