STL之vector

vector模拟实现

一. vector的基本框架

template<typename T>
class vector
{
public:typedef T* iterator;private:iterator _start;iterator _finish;iterator _end_of_storage;
}

---

使用库中的string类需要包含头文件#inlcude<vector>，并且使用std::命名空间

_start：指向起始元素的地址； _finish：指向最后一个元素的下一个地址； _end_of_storage：指向所申请空间结尾的下一个位置地址

其底层是将数据顺序存储的，即使用一段连续的空间。

二. 常用方法及实现

以实现的顺序来依次进行介绍

1.初始化和清理

a. 默认构造函数

vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr)
{}

b. 析构函数

~vector()
{delete[] _start;_start = _finish = _end_of_storage = nullptr;
}

2. 迭代器

vector是顺序存储的结构，因此可以用T*(原生指针)当做其迭代器

typedef T* iterator;
typedef const T* const_iterator;

a. begin

iterator begin()
{return _start;
}
const_iterator begin() const
{return _start;
}

b. end

iterator end()
{return _finish;
}
const_iterator end() const
{return _finish;
}

3.数据访问

a. size

size_t size() const
{return _finish - _start;
}

b. capacity

size_t capacity() const
{return _end_of_storage - _start;
}

指针相减，得到的是其中该类型元素的个数

c. operator[]

const T& operator[](size_t pos) const
{assert(pos < size());return *(_start + pos);
}
T& operator[](size_t pos)
{assert(pos < size());return *(_start + pos);
}

d. front

T& front()
{assert(size() > 0);return *_start;
}
const T& front() const
{assert(size() > 0);return *_start;
}

c. back

const T& back() const
{assert(size() > 0);return *(_finish - 1);
}

4.增删查改操作

a. reserve

void reserve(size_t n)
{if (n > capacity()){T* temp = new T[n];//将原空间的数据拷贝到新空间中size_t sz = size();for (size_t i = 0; i < sz; ++i){temp[i] = *(_start + i);}delete[] _start;_start = temp;_finish = _start + sz;_end_of_storage = _start + n;}
}

申请n个元素的空间，如果n<原有空间，则不做操作

b. resize

void resize(size_t n, const T& val = T())
{if (n < size()){//保留前n个元素_finish = _start + n;}else{//申请n个元素空间reserve(n);//新增的元素赋valiterator cur = _finish;_finish = _start + n; while (cur != _finish){*cur = val;++cur;} }
}

调整元素个数为n个，如果n<size，只保留前n个元素；如果n>size，新增的元素为val。

其中如果没有传val参数，则使用缺省值T()：T类型的匿名对象（内置类型，如：int() = 0)

c. insert

iterator insert(iterator pos, const T& val)
{assert(pos >= _start);assert(pos <= _finish);//如果空间满了就扩容if (_finish == _end_of_storage){//扩容后,可能使用新的空间，pos指向改变size_t s = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + s;}//将pos位到最后元素都向后移动1位iterator cur = _finish - 1;while (cur >= pos){*(cur+1) = *cur;--cur;}*pos = val;++_finish;return pos;
}

扩容操作可能使用新空间，所以要更新迭代器

d. push_back

void push_back(const T& val)
{insert(_finish, val);
}

尾插，在最后一个元素的下一个位置(_finish)存放val

e. erase

iterator erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);//将pos后的元素都向前移动1位iterator cur = pos + 1;while (cur < _finish){*(cur - 1) = *cur;++cur;}--_finish;return pos;
}

删除pos指向的元素，并返回删除位置的下一个位置的迭代器

f. pop_back

void pop_back()
{erase(_finish - 1);
}

删除最后一个元素

5.构造函数

a.迭代器区间构造

template<class InputIterator>
vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{while (first != last){push_back(*first);++first;}
}

通过传入的迭代器区间，来根据其区间的值来创建vector对象

b. swap

void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}

交换两个同类型vector对象的内容，通过作用域限定符::来调用库函数中的swap函数，完成对内置类型的成员变量的交换。

c. 拷贝构造

传统写法：

vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{//提前申请空，减少扩容reserve(v.size());for (const auto& e : v){push_back(e);}
}

现代写法：

通过一个局部对象，和swap来完成

vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{//调用迭代器区间来构造temp对象vector<T> temp(v.cbegin(),v.cend());swap(temp);
}

通过初始化列表，对成员变量进行初始化，然后和经迭代器区间构造函数得到的temp对象进行交换内容，完成拷贝构造。该函数调用结束，局部对象temp会自动调用析构函数，并销毁。

d. operator=

//赋值运算符重载，非构造函数
vector<T>& operator= (vector<T> v)
{swap(v);return *this;
}

传参时，会调用拷贝构造函数完成对局部对象v的初始化，然后交换*this和v的内容，完成对自身对象的赋值。

c.n个val的构造

vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{reserve(n);for (size_t i = 0; i < n; ++i){push_back(val);}
}/*定义时，n应该是非负数的，所以使用size_t,但传参时，通常传入的数字是int类型的，
例如：vector<int> v(5,0);(构造含5个0的v对象)，此时参数类型是：(int,int)
无法做到和上面(size,int)的精准匹配，编译器会选择根据
//template<class InputIterator>
//vector(InputIterator first, InputIterator last)
生成调用(int,int)的区间构造构造函数，从而发生错误
所以加入下面的函数
*/
vector(int n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{reserve(n);for (int i = 0; i < n; ++i){push_back(val);}
}

构造的vector对象含n个val元素。其中如果没有传val参数，则使用缺省值T()：T类型的匿名对象（内置类型，如：int() = 0)

三.小结

1.代码结构

vector代码代码，可以放在自己的命名空间中，避免冲突

#include <iostream>
#include <assert.h>namespace yyjs
{   template<typename T>class vector{public:typedef T* iterator;typedef const T* const_iterator;...};}

上述的成员函数都是放在class vector类体中，并public修饰

2.迭代器失效

a.插入时

扩容操作可能使用新空间，所以要更新迭代器，如果只是进行扩容，迭代器pos所指向的可能就是野指针，因此会产生迭代器失效因此的程序崩溃

b.删除时

在删除vi对象中一个奇数后，迭代器依旧指向被删除元素的位置，然后++，向下一个位置移动

由于erase()操作需要将元素向前挪动，所以之前的迭代器实际上是失效的，因此导致$5$被错过

3.迭代器操作

由于vector是顺序存储的，所以直接使用其元素指针做其迭代器：typedef T* iterator;

因此，对于iterator的操作，如*(解引用)、++、>等，实际上使用的底层库函数已经实现的对指针（内置类型）的操作符