手撕vector容器

一、vector容器的介绍

vector是表示可变大小数组的序列容器。就像数组一样，vector也采用的连续存储空间来存储元素，但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。

总结：vector是一个动态数组，能高效的随机下标访问。
 

二、主要接口

(constructor)构造函数声明	接口说明
vector()（重点）	无参构造
vector（size_type n, const value_type& val = value_type()）	构造并初始化n个val
vector (const vector& x); （重点）	拷贝构造
vector (InputIterator first, InputIterator last);	使用迭代器进行初始化构造

iterator的使用	接口说明
begin + end（重点）	获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置 的iterator/const_iterator
rbegin + rend	获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的 reverse_iterator

容量空间	接口说明
size	获取数据个数
capacity	获取容量大小
empty	判断是否为空
resize（重点）	改变vector的size
reserve （重点）	改变vector的capacity

vector增删查改	接口说明
push_back（重点）	尾插
pop_back （重点）	尾删
find	查找。（注意这个是算法模块实现，不是vector的成员接口）
insert	在position之前插入val
erase	删除position位置的数据
swap	交换两个vector的数据空间
operator[] （重点）	像数组一样访问

三、模拟实现

1.vector 的对象

iterator _start ：                指向第一个元素的迭代器

iterator _finish:                  指向最后一个元素下一个位置的迭代器

iterator _endOfStorage ：指向动态空间最后一个位置的迭代器

namespace N
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endOfStorage = nullptr;};
}

模板命名T vector迭代器的本质是指针  

【C++11】关于成员对象给缺省，在构造函数调用初始化列表的时候，会选择用上缺省值

 2.迭代器成员函数begin()和end()

begin():返回指向容器的起始位置的迭代器（非const）

end():返回指向容器的最后位置的下一个位置迭代器（非const）

cbegin():返回指向容器的起始位置的常属性迭代器（const）

cend():返回指向容器的最后位置的下一个位置常属性迭代器（const）

iterator begin(){return _start;
}iterator end(){return _finish;
}const_iterator cbegin()const {return _start;
}const_iterator cend() const
{return _finish;
}

区别：

非const的版本函数返回的迭代器可以用来访问，修改元素

而const版本只能用来访问元素，不准修改

3.容量空间

1)size()：返回数据个数

        元素首位迭代器的相减返回个数  （前开后闭返回区间个数）

2）capacity()

        元素容量与头元素迭代器的相减

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

3）reserve(size_t  n) :改变vector的capacity

如果vector 的capacity大于n ，不进行操作

n>=capacity，扩容，拷贝，释放原空间

同时更新_start    _finish     _endofstorage

void reserve(size_t n)
{if (n <= capacity()){return;}T* tmp = new T[n];size_t sz = size();if (_start){for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[]_start;}_start = tmp;_finish = _start + sz;_endOfStorage = _start+n;
}

4)resize :改变vector的size

n<size() 改变_finishi

n>=size() reserve空间，size后面的数依次赋值

void resize(size_t n, const T& value = T())
{if (n <= size()){_finish = _start + n;return;}reserve(n);while (_finish < n + _start){*_finish = value;++_finish;}
}

关于默认参数 ：

匿名对象T()生命周期只有这一行

const修饰匿名对象 延长生命周期 value销毁时匿名对象才销毁

4.vector增删查改

1）push_back():尾插

检查容量，不够就reserve扩容  _finish位置插入数据 ++_finish

void push_back(const T& x)
{if (_finish == _endOfStorage)//扩容{reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;
}

2)pop_back()：尾删

--_finish

void pop_back()
{_finish--;
}

3)insert(): pos位置之前插入val

检查pos合法

检查是否扩容，注意保存pos的位置，(求出pos-_start)

从最后一个数据往前挪动数据，插入val

更新_finish

iterator insert(iterator pos, const T& x)
{assert(pos>=_start);assert(pos <= _finish);int len = pos - _start;if (_finish == _endOfStorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}pos = _start + len;//移动数据iterator end = _finish-1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;
}

关于迭代器失效：

如果扩容后，原来的空间会被释放掉，那么pos会变成野指针,如果继续使用迭代器，会使用一块已经释放的空间，导致程序可能崩溃。

会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等
 

4）earse()：删除pos的值

检查pos的合法 _start<=pos<=_finish

从前往后挪数据

更新_finish

iterator erase(iterator pos)
{assert(pos >= _start);assert(pos <= _finish);iterator cur = pos+1;while (cur != _finish){*(cur - 1) = *cur;++cur;}--_finish;return pos;
}

涉及迭代器失效问题：

当earse最后一个位置时，迭代器失效，vs上认为使用earse后，不管删除哪个位置迭代器都失效

5）swap ：交换俩个vector的数据空间

如果发生赋值，会极大降低效率，因此在vector容器的交换，交换各自的迭代器对象

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

6）operator [ ] ：下标访问修改

返回指定空间的引用

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

关于const版本和非const版本：
const只读不可改，非const版本可读可改

5.(constructor)构造函数声明

1)无参构造函数：

        不用写具体内容，因为在C++11支持成员变量给缺省，会自动进入初始化列表

2）vector（size_type n, const value_type& val = value_type()） N个value构造

        先开空间，附用reverse函数，尾插

vector(int n, const T& value = T())
{reserve(n);for (int i = 0; i < n; i++){push_back(value);}
}

3）vector(InputIterator first, InputIterator last)：迭代器区间构造

定义迭代器模板，依次尾插

vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);++first;}
}

4)vector (const vector &x)：拷贝构造

开空间，尾插

vector(const vector<T>& v)
{reserve(v.capacity());for (auto e : v){push_back(e);}
}

5）operator =：赋值

拷贝构造临时空间，交换

vector<T>& operator= (vector<T> v)
{swap(v);return *this;
}

6）析构函数

释放空间

总结：

源代码：

STL/vector.h · L_may/C++Study - 码云 - 开源中国 (gitee.com)

本文模拟实现vector容器，在insert和erase中涉及迭代器失效的问题，要多加注意。

作者能力有限，希望对大家有所帮助。