STL之vector学习&模拟

我们string已经学习的差不多了，现在开始学习vector，我们这里会发现，STL的设计很相似，我们学习了一个，这里面就很简单了，我们简单的先看一下vector的使用，今天的重点是迭代器失效的问题和深层次的拷贝问题，这才是我们的难点。

vector 使用

vector可以理解为我们之前的动态的数组,也就是顺序表.它也是一个类模板.我们先看一下简单的使用.它的第一个参数模板是一个要存储的数据类型,第二个是向内存池开辟空间,如果你觉得库里面的内存池不够高效,也可以自己写一个,然后传过去,不过这不是我们要说的.

vector里面包含拷贝构造的的话共存在4个构造函数,我们这里一一简绍.


vector ();
vector (size_type n, const value_type& val = value_type());	构造 N 的 val的元素
vector (InputIterator first, InputIterator last);	迭代区间构造
vector (const vector& x);

我们这里还是自测试两个比较常用的

int main()
{
vector<int> v1;
vector<char> v2(10,'a');
return 0;
}

size() && capacity()

这个也是我们经常用到的函数,没有什么可以解释的.

int main()
{
vector<int> v1(20,15);
cout << "size: " << v1.size() << endl;
cout << "capacity: " << v1.capacity() << endl;
return 0;
}

reserve()

这个函数就是开辟空间的,和string那里是一样的,规则还是一样的.

int main()
{
vector<int> v1(20,15);
v1.reserve(10);
cout << "capacity: " << v1.capacity() << endl;

v1.reserve(100);
cout << "capacity: " << v1.capacity() << endl;
return 0;
}

resize()

没有什么新意,还是和之前一样.

int main()
{
vector<int> v1(20, 15);
v1.resize(10, 0);
cout << "size: " << v1.size() << endl;

v1.resize(100, 0);
cout << "size: " << v1.size() << endl;

return 0;
}

operator[]

这个的底层是一个连续的数组,所以这里我们最好支持下标访问.

int main()
{
vector<int> v1(20, 15);

for (int i = 0; i < v1.size(); i++)
{
cout << v1[i] << " ";
}
cout << endl;
return 0;
}

迭代器这里分为正向迭代器和反向迭代器,而且每种都有const修饰的,这里面我们不做太多的解释,用法和之前一样.

int main()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
cout << *it << " ";
it++;
}
cout << endl;
return 0;
}

push_back()

尾插一个数据,在尾部插入一个数据.

int main()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
for (int i = 0; i < v1.size(); i++)
{
cout << v1[i] << " ";
}
cout << endl;
return 0;
}

vector 实现

好了,总算是过了上面的认识阶段了,主要是我们没有什么可以说的,它和string几乎一摸一样,这还用说?现在我们要看的是他们的实现,这才是有意思的.

我们先来推一波vector的底层,应该会有一个size和一个capacity记录有效数据和容量,还应该有一个数组,来存放数据.我想这个应该没有什么可以质疑的,我们看看SGI版的的实现,它里面就存放了三个指针(typedef过的),这种方法也是可以的,而且还比我们的简便一些,就用这个来实现吧.

我们画一下它的物理图,这样大家可以好理解一点.

vector

现在我们就可以把框架搭出来了,我们搭个简便的.

template<class T>
class Vector
{
public:
typedef T* iterator; // 原生指针
typedef const T* const_iterator;

Vector()
:_start(nullptr)
, _finish(nullptr)
, _endOfStoage(nullptr)
{
}
private:
iterator _start;
iterator _finish;
iterator _endOfStoage;
}

vector和string是一样的,它们都是原生指针,所以这里面我们可以直接用.

iterator begin()
{
return _start;
}

const_iterator begin() const
{
return _start;
}

iterator end()
{
return _finish;
}

const_iterator end() const
{
return _finish;
}