C++ STL --＞模拟实现vector

这篇文章将模拟实现vector类的常用函数

vector类的函数接口

namespace ding
{
	template<class T>
	class vectot
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
                
		//Member functions
		vector();                                      
		vector(size_t n, const T& val);             
		template<class InputIterator>
		vector(InputIterator first, InputIterator last);   
		vector(const vector<T>& v);                       
		vector<T>& operator=(const vector<T>& v);           
		~vector();  
                
		//Iterators:
		iterator begin();
		iterator end();
		const_iterator begin()const;
		const_iterator end()const;

		//Capacity:
		size_t size()const;
		size_t capacity()const;
		void reserve(size_t n);
		void resize(size_t n, const T& val = T());
		bool empty()const;

		//Element access:
		T& operator[](size_t i);
		const T& operator[](size_t i)const;

		//Modifiers:
		void push_back(const T& x);
		void pop_back();
		iterator insert(iterator pos, const T& x);
		iterator erase(iterator pos);
		void swap(vector<T>& v);
		
	private:
		iterator _start;
		iterator _finish;
		iterator _end_of_storage;
	};
}

使用三个指针来维护vector容器，让_start指向容器的头，_finish指向有效数据的尾，
_end_of_storage指向容器的尾。

Member functions

成员函数

构造函数

无参构造函数

构造一个空的容器，让三个成员变量都置为空指针即可

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

带参构造函数

用n个val去构造初始化vector，首先开够n个元素的空间

然后让_finish从头到尾遍历进行赋值即可

vector(size_t n, const T& val)
    :_start(nullptr)
    ,_finish(nullptr)
    ,_end_of_storage(nullptr)
{
    //开空间
    _start = new T[n];
    _finish = _start;
    _end_of_storage = _start + n;
    //赋值
    while (_finish != _end_of_storage)
    {
            *_finish = val;
            ++_finish;
    }
}

迭代器构造

//模板函数
template<class InputIterator>
vector(InputIterator first, InputIterator last)
    :_start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
{
    //开空间
    int n = last - first;
    _start = new T[n];
    _finish = _start;
    _end_of_storage = _start + n;
    //赋值
    while (first != last)
    {
            *_finish = *first;
            ++first;
            ++_finish;
    }
}

注意:

• 这里迭代器构造是模板函数，如果使用这个代码vector<int> v1(10, 1);实例化对象v1。
• 本意是去调用vector(size_t n, const T& val)这个构造函数去实例化对象v1。
• 但是编译器的匹配原则，实参10是字面量，默认是int类型，而带参构造函数是size_t类型，则会调迭代器构造函数。就会导致对int类型进行解引用操作，导致程序出错。

解决办法:

• 重载一份带参构造函数，第一个参数设置成为int即可vector(int n, const T& val)

拷贝构造函数

这里要自己实现，编译器默认生成的拷贝构造是浅拷贝，这里需要深拷贝实现。
开一块与源容器空间大小一样的空间，然后将源容器中的数据拷贝过来即可

vector(const vector<T>& v)
        :_start(nullptr)
        , _finish(nullptr)
        , _end_of_storage(nullptr)
{
        size_t capacity = v._end_of_storage - v._start;//v的容量
        size_t size = v._finish - v._start;//v的元素个数
        _start = new T[capacity];
        memcpy(_start, v._start,sizeof(T)*size);//将源容器的数据拷贝过来。
        _finish = _start + size;
        _end_of_storage = _start + capacity;
}

注意：
如果使用memcpy进行实现，对于内置类型是没有任何问题的，但是对于自定义类型，会出错
比如下面的代码

vector<std::string> v4(3,"Hello World");
vector<std::string> v5(v4);

• v4中存放的是4个string类型,每一个sting分别指向对应得地址空间

• 执行vector<std::string> v5(v4),用v4构造v5.
• v5会开辟一块和v4一样大小得空间地址
  
• memcpy拷贝得时候会把v4中得string原封不动按字节依次拷贝下来，这里就会出现问题。
• v4和v5 虽然是不同的空间地址，但是里面的string却是同一块地址。就会导致string调用析构函数时会被析构两次，就会出错。
  

解决方法:

• 不要使用memcpy进行拷贝数据，memcpy本身就是浅拷贝。调用string类的赋值运算符重载函数进行深拷贝。

vector(const vector<T>& v)
    :_start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
{
    size_t capacity = v._end_of_storage - v._start;//v的容量
    size_t size = v._finish - v._start;//v的元素个数
    _start = new T[capacity];
    for (size_t i = 0; i < size; i++)
    {
         _start[i] = v._start[i];
    }
    _finish = _start + size;
    _end_of_storage = _start + capacity;
}

• 这里对于内置类型来说直接赋值，没有任何问题，对于自定义类型，会调用自己的赋值运算符重载函数进行深拷贝
• 拷贝之后的示意图 每个对象之间指向不同地址空间，互不影响。

总结：拷贝数据对于内置类型和自定义类型的浅拷贝来说使用memcpy进行拷贝没有任何问题，但是涉及到自定义类型的深拷贝，memcpy是完成不了的。
浅拷贝：两个对象会指向同一块地址空间，一个的改变会影响到另一个
深拷贝：两个对象分别指向不同的地址空间，彼此之间互不影响

赋值运算符重载

赋值运算符重载函数的实现也要实现深拷贝，实现思路和拷贝构造一样。
唯一需要注意的就是防止自己给自己赋值和返回值问题

vector<T>& operator=(const vector<T>& v)
{
   if (this != &v)//防止自己给自己赋值
   {
           size_t capacity = v._end_of_storage - v._start;//v的容量
           size_t size = v._finish - v._start;//v的元素个数
           delete[] _start;
           _start = new T[capacity];
           for (size_t i = 0; i < size; i++)
           {
                   _start[i] = v._start[i];
           }
           _finish = _start + size;
           _end_of_storage = _start + capacity;
   }
   return *this;
}

如果自己给自己赋值，delete后，自己的数据已经没了，在进行拷贝赋值，则会出错。
返回*this是为了支持连续赋值。

析构函数

_start、_finish、_end_of_storage指向的是同一块地址空间，析构_start，让其它置空即可。

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

写到这回头看代码，除了析构函数其他的这是什么鬼东西，代码冗余度太高了。重复的代码太多了。
解决这个问题等后面的iterator 和capacity是实现完就可以解决了。简单来说就是把重复出现的代码封装成一个函数，函提函数复用即可。

Iterators

迭代器的模拟实现 主要实现正向迭代器。

begin && end

begin()返回容器的首地址，end()返回容器当中有效数据的下一个数据的地址
如下图所示

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

capacity

size && capacity

• size 返回返回容器当中有效数据的个数
• capacity 返回容器的最大容量
  

size_t size()
{
    return _finish - _start;
}
size_t capacity()
{
    return _end_of_storage - _start;
}
//const版本
size_t size()const
{
    return _finish - _start;
}
size_t capacity()const
{
    return _end_of_storage - _start;
}

reserve

reserve函数的规则:

• 当n大于对象当前的capacity时，将capacity扩大到n或大于n。
• 当n小于对象当前的capacity时，什么也不做。即不会缩容

void reserve(size_t n)
{
    if (n > capacity())
    {
            size_t sz = size();//记录当前容器当中有效数据的个数
            T* tmp = new T[n];
            for (size_t i = 0; i < sz; i++)
            {
                    tmp[i] = _start[i];
            }
            delete[] _start;
            _start = tmp;
            _finish = _start + sz;
            _end_of_storage = _start + n;
    }
}

注意：

• 这里也不能使用memcpy进行拷贝数据，如果是内置类型没有问题，一但是自定义类型，就会是浅拷贝，在析构时会出错。
• 这里需要提前记录一下容器的数据个数，如果代码这样写

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

• 12行代码去调用size函数，此时size函数中的_start已经是新空间的地址，而_finish还是旧空间的地址，在物理空间上已经不连续了，让两个指针进行相减是拿不到元素个数的。
• 解决这个问题只能先记录元素个数，在让新空间的_start加上元素个数就是_finish的地址空间了。

resize

resize()规则：

• 当n大于当前的size时，将size扩大到n，扩大的数据为val，若val未给出，则默认为容器所存储类型的默认构造函数所构造出来的值。
• 当n小于当前的size时，将size缩小到n

void resize(size_t n, const T& val = T())
{
    if (n < size())
    {
            _finish = _start + n;
    }
    else
    {
            if (n > capacity())
            {
                    reserve(n);
            }
            //填数据
            while (_finish != _start + n)
            {
                    *_finish = val;
                    ++_finish;
            }
    }
}

empty

判断容器是否为空，这个很简单，直接比较_start 和 _finish即可

bool empty()const
{
    return _start == _end_of_storage;
}

这里的empty函数定义成const成员函数更合理 const修饰类的成员函数实际上是修饰该成员函数隐含的this指针，表明在该成员函数中不对类的任何成员进行修改。还能防止写错写成赋值，写错编译器也能找出问题。

Element access

[]重载

T& operator[](size_t i)
{
    //检查下标合法性
    assert(i < size());
    return _start[i];
}
const T& operator[](size_t i)const
{
    assert(i < size());
    return _start[i];
}

Modifiers

push_back

尾插 首先考虑容器是否已满，若容量已满应先进行扩容操作，在插入数据。

void push_back(const T& x)
{
    //检查容量
    if (_finish == _end_of_storage)
    {
            //扩容
            size_t capacity = capacity() == 0 ? 2 : capacity() * 2;//对空容器进行判断
            reserve(capacity);
    }
    *_finish = x;
    ++_finish;
}

如果容器为空不加以判断，reserve(0)没意义，导致尾插失败

pop_back

为删时则应该考虑容器是否为空，对空容器进行检查，在删除数据
删除数据直接对_finish指针自减即可。

void pop_back()
{
    assert(!empty());
    --_finish;
}

insert

void insert(iterator pos, const T& x)
{
    if (_finish == _end_of_storage)
    {
            //扩容
            size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;//对空容器进行判断
            reserve(newcapacity);
    }
    //挪动数据插入
    iterator end = _finish -1 ;
    while (end >= pos)
    {
            *(end + 1) = *end;
            --end;
    }
    *pos = x;
    ++_finish;
}

注意：

• insert如果按照上述的逻辑写，如果不发生扩容，没有问题，一旦在insert时发生扩容就会出问题。
• 一旦发生扩容10行代码中的_finish已经是扩容后新空间的地址，而pos还是旧空间的地址，让end和pos去比较，没有任何意义。

解决方法：
扩容前记录pos到_start 的距离 扩容后更新pos

void insert(iterator pos, const T& x)
{
    if (_finish == _end_of_storage)
    {
            //记录pos到_start的距离
            size_t len = pos - _start;
            size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;
            reserve(newcapacity);
            //扩容完更新pos
            pos = _start + len;
    }
    //挪动数据插入
    iterator end = _finish -1 ;
    while (end >= pos)
    {
            *(end + 1) = *end;
            --end;
    }
    *pos = x;
    ++_finish;
}

erase

iterator erase(iterator pos)
{
    assert(!empty());
    iterator start = pos + 1;
    while (start != _finish)
    {
            *(start - 1) = *start;
            ++start;
    }
    --_finish;
    return pos;
}

成员函数重构

//带参构造函数
vector(size_t n, const T& val)
        :_start(nullptr)
        , _finish(nullptr)
        , _end_of_storage(nullptr)
{
        reserve(n);
        for (int i = 0; i < n; ++i)
        {
                push_back(val);
        }
}
//迭代器构造函数
template<class InputIterator>
vector(InputIterator first, InputIterator last)
        :_start(nullptr)
        , _finish(nullptr)
        , _end_of_storage(nullptr)
{
        //开空间
        while (first != last)
        {
                push_back(*first);
                ++first;
        }
}
//拷贝构造函数
vector(const vector<T>& v)
        :_start(nullptr)
        , _finish(nullptr)
        , _end_of_storage(nullptr)
{

        _start = new T[v.capacity()];
        for (size_t i = 0; i < v.size(); i++)
        {
                _start[i] = v._start[i];
        }
        _finish = _start + v.size();
        _end_of_storage = _start +v.capacity();
}
//赋值运算符重载
vector<T>& operator=(const vector<T>& v)
{
    if (this != &v)//防止自己给自己赋值
    {

            delete[] _start;
            _start = new T[v.capacity()];
            for (size_t i = 0; i < v.size(); i++)
            {
                    _start[i] = v._start[i];
            }
            _finish = _start + v.size();
            _end_of_storage = _start + v.capacity();
    }
    return *this;
}