【C++】vector的模拟实现 | 使用memcpy拷贝时的问题 | 实现深拷贝

目录

基本框架及接口

构造函数

无参构造

迭代器区间构造

初始化构造

析构函数

size() | capacity()

扩容的reserve()

使用memcpy拷贝的问题

改变大小的resize()

operator[]

迭代器的实现

vector的增删

尾插push_back()

尾删pop_back()

借insert和erase谈迭代器失效的问题

insert()

erase()

深拷贝的实现

拷贝构造函数

赋值operator=

---

上一篇我们说到了vector，它是一个类模板，能够容纳各种类型的对象作为其元素，并且可以动态地调整大小。可以理解为动态数组。

这篇我们就亲自实现一下 简易版的vector，这能大大加深我们对vector的理解！

而因为vector的实现和string有很多相似之处，所以实现过程中的一些细节便不再详述。

基本框架及接口

📁vector.h：

#pragma once
namespace jzy   //为了和STL库里的vector区分，我们就把它放进自定的命名空间里
{
    template<typename T>
    class vector
    {
    public:
        typedef T* iterator;   
        
    private:
        iterator _start;
        iterator _finish;     //finish表示最后一个位置的后一个位置
        iterator _end_of_storage;
    };
}

这里的三个成员变量，是参照了《STL源码剖析》，按照STL 3.0版本实现的。

这样的话，想要知道 _size或者 _capacity，就用成员变量相减的方式。

构造函数

无参构造

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

迭代器区间构造

通过传迭代器的起、始区间（左闭右开）来构造。

vector(InputIterator first, InputIterator last)
        {
            InputIterator it = first;
            int num = 0;       //统计个数
            while (it != last)
            {
                it++;
                num++;
            }
​
            _start = new T[num];
            for (int i = 0; i < num; i++)
            {
                _start[i] = *first++;
            }
            _finish = _start + num;
            _end_of_storage = _start + num;
        }

初始化构造

构造的同时能将对象初始化，使之含n个val值。

vector(int n, const T& val = T())   //注意：这里不能给size_t！
        {
            _start = new T[n];
            for (int i = 0; i < n; i++)
            {
                _start[i] = val;
            }
            _finish = _start + n;
            _end_of_storage = _start + n;
        }

为什么n的类型不能是size_t？

如果是size_t，当传的两个参数都是int类型时，测试出的结果为：

void test7()
{
    vector<int> v1(5,1);  
    for (auto& e : v1)
    {
        cout << e << " ";
    }
}

原因：

我们知道，v1在匹配构造函数时，是根据参数的类型来匹配的。

size_t与int并不能很好地匹配，而InputIerator却可以匹配上int类型，因为InputIerator本身就是个模板，int无需转化就能匹配上。

所以v1调用的构造函数是 vector(InputIterator first, InputIterator last); ,

在这个函数里，要对int进行解引用，所以报错：非法的间接寻址。

析构函数

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

size() | capacity()

目前的三个成员变量不能直观地表示出 容量和大小，因此，我们需要亲自实现出来。

size_t size()
{
    return _finish - _start;   
}
​
size_t capacity()
{
    return _end_of_storage - _start;
}

扩容的reserve()

扩容的思路是：

先开新空间，再把数据都拷到新空间里去，然后释放旧空间，让指针指向新空间。

未经修正版的reserve：

void reserve(size_t n)
        {
            if (n > capacity())
            {
                size_t sz = size();
​
                T* tmp = new T[n];
                int a = size();
                if (_start)
                {
                    memcpy(tmp, _start, sz* sizeof(T)); 
                    delete[] _start;
                }
                _start = tmp;
                _finish = _start + sz;
                _end_of_storage = _start + n;
            }
        }

来测试下：

void test10()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
​
    for (auto& e : v)
    {
        cout << e << " ";
    }
    cout << endl;
}

看起来搞定了。但真的OK吗？

如果我们用自定义类型，如vector来测试：

void test9()
{
    vector v;
    v.push_back("happy");
    v.push_back("happy");
    v.push_back("happy");
    v.push_back("happy");
    v.push_back("happy");
​
    for (auto& e : v)
    {
        cout << e << " ";
    }
    cout << endl;
​
}

程序居然崩溃了！

其实，这都是memcpy惹的祸。

使用memcpy拷贝的问题

⭐memcpy只能进行浅拷贝，所以，如果是拷内置类型，那很乐于用memcpy。

如果是自定义类型 且 涉及资源管理的，就不能用memcpy了，不然可能会引起内存泄漏甚至程序崩溃。

现在来解释vector用例崩溃的原因：

在调用push_back时，空间不够的话，push_back内部会调用reserve开空间，问题就出在这个reserve。来看看reserve是咋实现的：

void reserve(size_t n)
        {
            if (n > capacity())
            {
                size_t sz = size();
​
                T* tmp = new T[n];
                int a = size();
                if (_start)
                {
                    memcpy(tmp, _start, sz* sizeof(T));    //拷数据时用memcpy
                    delete[] _start;
                }
                _start = tmp;
                _finish = _start + sz;
                _end_of_storage = _start + n;
            }
        }

可以看到，reserve是调memcpy拷数据的，拷完就释放了_start。

memcpy拷贝的原理就是浅拷贝，直接把值给复制过去。如果vector里的元素是int、char这种，那直接复制没问题。但此时vector里的是string，我们知道，要想找到字符串，得知道首元素地址。所以vector容器里存着的是一个个首元素地址，此时浅拷贝，就会是这种场景：

tmp 的内容是由memcpy值拷贝来的，和_start指向同一块空间。当_start被delete，那tmp的空间同样也被释放了。

所以说，如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，还是得自己老老实实地拷贝。

➡️修改后的reserve：

void reserve(size_t n)
        {
            if (n > capacity())
            {
                //开空间
                T* tmp = new T[n];
                //拷数据
                iterator begin = _start;
                int i = 0;
                while (begin != _finish)
                {
                    tmp[i++] = *begin++;
                }
                //释放、赋值
                delete[] _start;
                _start = tmp;
                _finish = tmp + i;
                _end_of_storage = tmp + n;
            }
        }

此时再测试：

改变大小的resize()

void resize(size_t n , T val = T())
        {
            if (n < size())
            {
                _finish = _end_of_storage = _start + n;
            }
            else
            {
                reserve(n);
                for (int i = size(); i < n; i++)
                {
                    _start[i] = val;
                }
                _finish = _start + n;
            }
        }

operator[]

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

迭代器的实现

普通迭代器的begin() | end()：

typedef T* iterator;
iterator begin()
{
    return _start;
}
​
iterator end()
{
    return _finish;
}

const迭代器的begin() | end()：

被const修饰以后，只能读，不能写。

typedef const T* const_iterator;
const_iterator begin() const
{
    return _start;
}
​
const_iterator end() const
{
    return _finish;
}

关于范围for：

只要实现了迭代器，那范围for不用特意去实现，就已经能用了：

void test1()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
​
    for (auto e : v)    //用范围for遍历
    {
        cout << e << " ";
    }
    cout << endl;
}

实际上范围for的底层原理 就是迭代器。它依靠begin()、end()来实现，且只认识begin()和end()。

假如我把begin()的名称改成Begin()，那迭代器照样能用，而范围for就用不了了：它不认识Begin()。。。

vector的增删

尾插push_back()

void push_back(const T& val)  
{
    //先考虑容量够不够
    if (size() == capacity())
    {
        reserve(capacity() == 0 ? 4 : 2 * capacity());
    }
​
    *_finish = val;
    _finish++;
}

这里要注意：形参得被const修饰，并且传引用过去。

传引用的话更省力，不然深拷贝代价大；有了const，形参才能接收常量字符串。

尾删pop_back()

void pop_back()
{
    assert(_start<_finish);
    _finish--;
}

借insert和erase谈迭代器失效的问题

insert()

void insert(iterator pos, const T& val)
        {
            assert(pos >= _start);
            assert(pos <= _finish);
            //先考虑空间够不够
            if (_finish == _end_of_storage)
            {
                reserve(capacity() == 0 ? 4 : 2 * capacity());
            }
            //挪动数据
            iterator end = _finish - 1;
            while (end >= pos)
            {
                *(end + 1) = *end;
                end--;
            }
            //插入
            *pos = val;
            _finish++;
        }

这样写其实还不够，一旦涉及扩容就会出现问题。我们来测试一下：

void test2()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.pop_back();
    v.insert(v.begin(), 10);
    v.insert(v.begin(), 11);
    v.insert(v.begin(), 12);
​
    for (auto e : v)  
    {
        cout << e << " ";
    }
    cout << endl;
}

出现了随机值！

究其原因，其实是reserve扩容 那步出了疏漏，使迭代器pos失效了。

这就是迭代器失效问题。

也就是说，在扩容后，迭代器pos需要被更新一下：让原本指向旧空间的pos，现在指向新空间的同样位置。

修改后：

void insert(iterator pos, const T& val)
        {
            int flag_pos = pos - _start;   //先记录下pos的相对位置，以便之后更新pos
​
            assert(pos >= _start);
            assert(pos <= _finish);
            //考虑空间够不够
            if (_finish == _end_of_storage)
            {
                reserve(capacity() == 0 ? 4 : 2 * capacity());
                pos = _start + flag_pos;     //根据刚刚记录的位置，更新pos
            }
​
            //挪动数据
            iterator end = _finish - 1;
            while (end >= pos)
            {
                *(end + 1) = *end;
                end--;
            }
            //插入
            *pos = val;
            _finish++;
        }

现在可以成功插入了：

拓展思考：若将v.begin()传给pos时，采用引用传参，可行吗？

void insert(iterator& pos, const T& val);

不可行。这个问题很考验我们在类和对象那块的基础知识。

我们来看看begin()：

iterator begin()
        {
            return _start;
        }

它采用传值返回，返回的不是_start，而是它的拷贝出来的临时对象。

临时对象是具有常性的，所以pos没法作它的别名，我们只能拷贝一份它，存进pos里。

erase()

void erase(iterator pos)
        {
            assert(pos >= _start && pos < _finish );  //这里注意：不能<=_finish！因为它指向的是最后一个元素的后一个位置
            
            iterator begin = pos + 1;
            while (begin < _finish)
            {
                *(begin - 1) = *begin;
                begin++;
            }
            
            _finish--;
        }

但是！看似平静无澜的erase()，其实暗含隐患：erase也会有迭代器失效的问题。

现在我们用一个例子来展示出它的问题：现要求删除所有的偶数。

v分两组，分别是A：{1,2,3,4,5}; B：{1,2,3,4}。

A：

void test3()
{
    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>::iterator it = v.begin();
    while (it != v.end())
    {
        if (*it % 2 == 0)
        {
            v.erase(it);
        }
        it++;
    }
    for (auto e : v)
    {
        cout << e << " ";
    }
    cout << endl;
}

删除成功了。但如果v中是1 2 3 4，就不行。

B：

void test3()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    ……
}  

程序崩溃了：

这是因为迭代器失效了，我们用图来说明原因：

而{1,2,3,4,5}仅仅是碰巧，被删的偶数后面正好跟着奇数，所以没有暴露错误。

那对于erase中迭代器失效的情况，写C++的大佬是怎么处理的呢？

处理的思路是：将返回值由void 改为iterator，返回删除后pos的位置。这样的话，删完后迭代器还是指向pos，就不会错过pos位置的比较。

修改后的erase：

iterator erase(iterator pos)
        {
            assert(pos >= _start && pos < _finish );  //这里注意：不能<=_finish！因为它指向的是最后一个元素的后一个位置
            
            iterator begin = pos + 1;
            while (begin < _finish)
            {
                *(begin - 1) = *begin;
                begin++;
            }
            
            _finish--;
            return pos;
        }

测试：

void test3()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
​
    //要求删除所有的偶数
    vector<int>::iterator it = v.begin();
    while (it != v.end())
    {
        if (*it % 2 == 0)   //用if else语句，删完以后迭代器仍停在pos位置，而不会自增
        {
            it = v.erase(it);
        }
        else 
        {
            it++;
        }
    }
    for (auto e : v)
    {
        cout << e << " ";
    }
    cout << endl;
}

注意这里测试的写法！！v.erase()后，要用迭代器去承接它的返回值，并且用if  else语句使it增长。这样才能防止 因访问失效的迭代器，而导致程序崩溃。

如果还是这个写法：

void test5() {
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
 
	vector<int>::iterator it = v1.begin();
	while (it != v1.end()) {
		if (*it % 2 == 0) {
			v1.erase(it);
		}
		it++;
	}
	for (auto e : v1) {
		cout << e << " ";
	}
}

那仍会使程序崩溃！！

其实迭代器失效是不会报错的，报错是因为访问了失效的迭代器。

所以说，用erase时一定要小心。

要想程序正常运行，一是 底层实现时，得返回iterator；

二是用erase时，用if  else语句，并且用iterator去承接函数的返回值。

迭代器失效的笔试题

运用刚刚学过的知识，来解答这个问题吧！

下面的程序运行结果是？

int main()
{
	int ar[] ={1,2,3,4,0,5,6,7,8,9};
	int n = sizeof(ar) / sizeof(int);
	vector<int> v(ar, ar+n);
	vector<int>::iterator it = v.begin();
	while(it != v.end())
	{
		if(*it != 0)
			cout<<*it;
		else
			v.erase(it);
		it++;
	}
	return 0;
}

A.程序运行崩溃
B.1 2 3 4 5 0 6 7 8 9
C.1 2 3 4 5 6 7 8 9
D.1 2 3 4 6 7 8 9

我们刚刚强调了，用erase时，写法是很讲究的。if  else语句+用迭代器承接返回值 才能让程序正常运行。这样写，会因访问失效的迭代器而使程序崩溃。选A。

深拷贝的实现

拷贝构造函数

如果我们用默认的拷贝构造函数，进行vector的浅拷贝的话：

void test4()
{
    vector<int> v1;
    vector<int> v2(v1);
}

这是因为，浅拷贝仅能复制值，而不能复制一份同样的空间。

这样v1、v2就指向了同一块空间，析构v1、v2时，同一块空间被析构了两次，所以程序崩溃了。

所以，我们要手动实现vector的拷贝构造，实现深拷贝。

➡️Way1 传统写法：老老实实地开空间、拷数据。

vector(vector& v)
            :_start(new T[v.capacity()])
            , _finish(_start + v.size())
            , _end_of_storage(_start + v.capacity())
        {
            memcpy(_start, v._start, sizeof(T) * v.size());
        }

➡️Way2 现代写法：本质是复用现成的代码，“构造新对象+将自己和新对象进行swap”。

vector(const vector& v)   
            :_start(nullptr)
            , _finish(nullptr)
            , _end_of_storage(nullptr)
        {
            vector tmp(v.begin(), v.end());
            swap(_start, tmp._start);
            swap(_finish, tmp._finish);
            swap(_end_of_storage, tmp._end_of_storage);
        }

赋值operator=

vector& operator=(vector v)    //因为是传值传参，v就已经是实参的拷贝了，所以不需要再构造tmp
        {
            swap(_start, v._start);
            swap(_finish, v._finish);
            swap(_end_of_storage, v._end_of_storage);
            return *this;
        }