C++——vector的使用及其模拟实现

vector的使用及其模拟实现

本章思维导图：
注：本章思维导图对应的 .png文件已同步导入至 资源，可免费下载查阅。

1. vector的使用

template < class T, class Alloc = allocator<T> > class vector; // generic template

• vector也是STL中的一大容器
• 可以将vector视为C语言的顺序表
• 他是一个类模板，因此在使用之前需要先用一个具体的类型对其进行实例化。例如vector<int>、vector<string>

1.1 构造函数construct

以下三种构造方式较为常用：

//用n个value构造
explicit vector (size_type n, const value_type& val = value_type(),
                 const allocator_type& alloc = allocator_type());

//用一段迭代器区间构造
template <class InputIterator>
         vector (InputIterator first, InputIterator last,
                 const allocator_type& alloc = allocator_type());

//用另一个vector拷贝构造
vector (const vector& x);

注：

迭代器是一个用来访问容器数据的对象，其提供了统一的方式来遍历容器中的数据

• 对于vector类，我们可以将迭代器看成一个指针，其指向vector对象存储的某个数据
• 我们可以通过迭代器来访问或者修改容器中的数据

使用示例：

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int a[] = { 1,2,3,4,5 };

	vector<int> v1(a, a + 5);	//可以认为只想一段连续空间的指针也是一个迭代器
	vector<string> v2(3, "111");	//三个字符串"111"构造
	vector<int> v3(v1);		//v1拷贝构造v3

	cout << "v1: ";
	for (auto& e : v1)
		cout << e << " ";
	cout << endl;

	cout << "v2: ";
	for (auto& e : v2)
		cout << e << " ";
	cout << endl;

	cout << "v3: ";
	for (auto& e : v3)
		cout << e << " ";
	cout << endl;

	return 0;
}

output:

v1: 1 2 3 4 5
v2: 111 111 111
v3: 1 2 3 4 5

1.2 获取当前存储的数据个数size()和最大容量capacity()

size_type size() const;	//获取存储的数据个数

size_type capacity() const;	//获取最大容量

例如：

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> v(5, 1);

    cout << "size: " << v.size() << endl;
    cout << "capacity: " << v.capacity() << endl;

	return 0;
}

output:

size: 5
capacity: 5

1.3 访问

1.3.1 operator[]运算符重载

      reference operator[] (size_type n);	//返回数据的引用
const_reference operator[] (size_type n) const;

• 有了[]这个运算符的重载，我们就可以像利用下标访问数组那样来访问vector容器的数据了
• 同时对于非const对象，我们还可以在访问的同时对其进行修改

例如：

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> v({1,2,3});

	for (int i = 0; i < v.size(); i++)
		cout << ++v[i] << " ";
	cout << endl;

	return 0;
}

output:

2 3 4

1.3.2 迭代器访问

• 由于vector存储的是一段连续的地址空间，因此我们可以将他的迭代器看作是一个指针
• 同其他容器一样，vector也有正向迭代器和反向迭代器

正向迭代器：

      iterator begin();
const_iterator begin() const;

      iterator end();
const_iterator end() const;

• begin()返回的迭代器指向vector存储的第一个元素，end()返回的迭代器返回指向vector存储的最后一个元素的后一个位置
• 所以，begin(), end()包含的空间实际上是一个左闭右开的区间

例如：

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> v({ 1,2,3 });

	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		(*it)++;
		cout << *it << " ";
		it++;
	}
	cout << endl;

	return 0;
}

反向迭代器：

      reverse_iterator rbegin();
const_reverse_iterator rbegin() const;

      reverse_iterator rend();
const_reverse_iterator rend() const;

• rbegin()返回的迭代器指向vector存储的最后一个元素，rend()返回的迭代器指向vector存储的第一个元素的前一个位置
• rbegin(), rend()同样也是一个左闭右开区间

例如：

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> v({ 1,2,3 });

	vector<int>::reverse_iterator it = v.rbegin();
	while (it != v.rend())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

	return 0;
}

output:

3 2 1

1.3.3 范围for

范围for的内核实际上就是迭代器访问，只是书写起来较为方便简洁

例如：

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> v({ 1,2,3 });

	for (auto& e : v)
		cout << e << " ";
	cout << endl;

	return 0;
}

output:

1 2 3

1.4 容量相关reserve()和resize()

void reserve (size_type n);

void resize (size_type n, value_type val = value_type());

这里需要注意区分这两者的区别（VS 2019下）：

reserve：

• 如果n < capacity，那么该函数将不会做任何处理
• 如果n > capacity，reserve()只会为该容器重新开辟一块大小为n的空间，并将原来的capacity置为n，但并不会实际的创建对象（插入数据），即既不会改变原来的数据也不会加入新的数据。

resize：

• 如果n < size，那么该函数就会只保留容器的前n个数据，但并不会影响capacity
• 如果n > size && n <= capacity，那么该函数就会将后面n - size个空间初始化为val
• 如果n > capacity，那么该函数首先会将capacity置为n，再进行初始化

例如：

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> v(5, 1);

    for (auto& e : v)
        cout << e << " ";
    cout << endl;
    cout << "size: " << v.size() << endl;
    cout << "capacity: " << v.capacity() << "\n\n";

    v.reserve(1);
    cout << "after reserve(1)" << endl;
    cout << "size: " << v.size() << endl;
    cout << "capacity: " << v.capacity() << "\n\n";

    v.reserve(9);
    cout << "after reserve(9)" << endl;
    for (auto& e : v)
        cout << e << " ";
    cout << endl;
    cout << "size: " << v.size() << endl;
    cout << "capacity: " << v.capacity() << "\n\n";

    v.resize(1);
    cout << "after resize(1)" << endl;
    for (auto& e : v)
        cout << e << " ";
    cout << endl;
    cout << "size: " << v.size() << endl;
    cout << "capacity: " << v.capacity() << "\n\n";

    v.resize(11, 8);
    cout << "after resize(1)" << endl;
    for (auto& e : v)
        cout << e << " ";
    cout << endl;
    cout << "size: " << v.size() << endl;
    cout << "capacity: " << v.capacity() << "\n\n";
    return 0;
}

output:

1 1 1 1 1
size: 5
capacity: 5

after reserve(1)
size: 5
capacity: 5

after reserve(9)
1 1 1 1 1
size: 5
capacity: 9

after resize(1)
1
size: 1
capacity: 9

after resize(1)
1 8 8 8 8 8 8 8 8 8 8
size: 11
capacity: 13

1.5 增（插入数据）

1.5.1 push_back() 尾插

void push_back (const value_type& val);

vector的尾插就和顺序表的尾插一样，就是在最后面新增一个数据

例如：

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);

	for (auto& e : v)
		cout << e << " ";
	cout << endl;

	return 0;
}

output:

1 2 3

1.5.2 insert() 随机插入

iterator insert (iterator position, const value_type& val);

• 这里需要注意，和顺序表不同的是，position表示插入的位置，但是这里不是一个整数，而是一个迭代器。

例如：

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> v(5, 1);
	v.insert(v.begin() + 1, 22);

	for (auto& e : v)
		cout << e << " ";
	cout << endl;

	return 0;
}

output:

1 22 1 1 1 1

1.6 删（删除数据）

1.6.1 pop_back() 尾删

void pop_back();

• 该函数功能十分简单，就是删除vector的最后一个数据

例如：

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> v({ 1,2,3 });
	v.pop_back();

	for (auto& e : v)
		cout << e << " ";
	cout << endl;

	return 0;
}

output:

1 2

1.6.2 erase() 随机删除

iterator erase (iterator position);

• 和insert一样，position表示要删除的元素的位置，同样是一个迭代器

例如：

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> v({ 1,2,3 });
	v.erase(v.begin() + 1);

	for (auto& e : v)
		cout << e << " ";
	cout << endl;

	return 0;
}

output:

1 3

2. 模拟实现

2.1 vector的内部结构

• 和C语言的顺序表不同，vector的内部并不是由一个指针start再加上两个整数size和capacity来实现的
• 实际上，vector是靠三个迭代器来实现对数据的维护的：

template<class T>
class vector
{
private:        
    iterator _start = nullptr; // 指向数据块的开始
    iterator _finish = nullptr; // 指向有效数据的尾
    iterator _endOfStorage = nullptr; // 指向存储容量的尾
}

2.2 部分细节的说明

2.2.1 C++对内置类型的”升级“

在模拟实现中，在写插入函数的形参时，一般会这样写：

void push_back(const T& x = T())

我们知道，T()这样的对象我们称其为匿名对象。但是有些小伙伴就会有疑惑了：

vector、string这种自定义类型好说，他们有构造函数，但如果T是int这种内置类型呢，难道它们也有自己的构造函数吗？

答案确实如此，为了适应类和对象，我们可以认为C++对内置了类型进行了”升级“，使它们也有自己的构造函数。

例如：

#include <iostream>
using namespace std;

int main()
{
	int a = int();
	double b = double();

	cout << a << endl;
	cout << b << endl;

	return 0;
}

output:

0
0

2.2.2 迭代器失效

首先，让我们先来看看reserve()的模拟实现：

void reserve(size_t n)
{
    if (n > capacity())
    {
        int length = size();

        T* tmp = new T[n];
        for (int i = 0; i < length; i++)
        {
            tmp[i] = *(_start + i);
        }
        delete[] _start;

        _start = tmp;
        _finish = _start + length;
        _endOfStorage = _start + n;
    }
}

可以看到，这段代码的逻辑是：先new一块大小为n的空间，再将原来的数据复制过来，最后再释放原来的空间。如图：

接着，我们再来看看insert()的模拟实现：

iterator insert(iterator pos, const T& x = T())
{
    assert(pos <= end());
    assert(pos >= begin());

    //如果满了，就进行扩容
    if (_finish == _endOfStorage)
    {
        size_t len = pos - begin();
        reserve(capacity() == 0 ? 1 : 2 * capacity());
        pos = begin() + len;
    }
	
    //将pos及其之后的元素向后移动一个
    auto end = _finish;
    while (end > pos)
    {
        *end = *(end - 1);
        end--;
    }
	
    //插入
    *pos = x;
    _finish++;

    return pos;
}

可能有小伙伴对扩容部分的代码不是很理解：

扩容就扩容，为什么还要改变pos呢？

这里就涉及到迭代器失效的问题了：

pos是一个迭代器，其指向原始数据的某一个位置。但是如果要进行扩容操作，由上面的分析可以知道，如果要进行扩容，那么原始数据就会被释放，这就会导致pos这个迭代器就会变成一个野指针。

因此，需要先记录pos和_start的相对位置，扩容之后再对pos进行更新。

如果你认为这样就万无一失，那就大错特错了，我们可以来看一看下面的代码，看看结果如何：

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> v({ 1,2,3,4 });
	vector<int>::iterator it = v.begin();

	cout << v.capacity() << "\n";
	v.insert(it, 100);
	cout << v.capacity() << "\n";

	cout << *it << "\n";
	return 0;
}

我们来进行调试：

可以发现，竟然还是有错误。并且，这也是一个迭代器失效的问题，也就说it这个迭代器失效了。为什么？

其实原因和上面所说的pos类似，因为扩容之后原来的空间和数据都被释放了，指向原来数据的迭代器it也就成为了野指针。

事实上，函数erase()也可能存在和insert()类似的迭代器失效的问题。因此，为了避免迭代器失效带来的影响，我们得遵循以下原则

凡是insert()或者erase()过的迭代器都不要使用

2.2.3 memcpy的浅拷贝问题

继续回到函数reserve()的实现：

void reserve(size_t n)
{
    if (n > capacity())
    {
        int length = size();

        T* tmp = new T[n];
        for (int i = 0; i < length; i++)
        {
            tmp[i] = *(_start + i);
        }
        delete[] _start;

        _start = tmp;
        _finish = _start + length;
        _endOfStorage = _start + n;
    }
}

有同学会问：

for (int i = 0; i < length; i++) tmp[i] = *(_start + i);这段代码我可以用库函数memcpy()来替换吗

答案是不行。

假设替换为memcpy()，那我们来看下面代码的运行结果：

void reserve(size_t n)
{
    if (n > capacity())
    {
        int length = size();

        T* tmp = new T[n];
        memcpy(tmp, _start, sizeof(T) * length);
        delete[] _start;

        _start = tmp;
        _finish = _start + length;
        _endOfStorage = _start + n;
    }
}
void push_back(const T& x = T())
{
    if (_finish == _endOfStorage)
    {
        reserve(capacity() == 0 ? 1 : 2 * capacity());
    }

    *_finish = x;
    _finish++;
}

int main()
{
    vector<string> v2;
    v2.push_back("111");
    v2.push_back("111");
    v2.push_back("111");
    v2.push_back("111");
    v2.push_back("111");

    for (auto& e : v2)
        cout << e << " ";
    cout << endl;
    
    return 0;
}

我们来进行调试：

竟然在插入的时候就出问题了，这是为啥？

让我们来进行分析：

• 众所周知，一个string对象可以由三部分构成：指向存储的字符序列的指针str、size、capacity
• memcpy()拷贝的方式，是将每个字节的内容从源拷贝到目的地，是一种浅拷贝方式
• 对于两个整数size和capacity自然没有大碍。但是对于一个指向了具体内容的指针，发生浅拷贝就意味着两个指针会指向相同的区域
• 而扩容后原来的空间及其数据就会销毁，这就会使新的str成为野指针。之后当进行delete[]操作时就会触发释放野指针这一操作，从而报错。

2.3 模拟实现代码：

如有错误，欢迎指正

#pragma once
#include <iostream>
#include <vector>
#include <assert.h>

using namespace std;

namespace TEST
{
    template<class T>
    class vector
    {
    public:
        // Vector的迭代器是一个原生指针
        typedef T* iterator;
        typedef const T* const_iterator;
        iterator begin()
        {
            return _start;
        }
        iterator end()
        {
            return _finish;
        }
        const_iterator begin() const
        {
            return _start;
        }
        const_iterator end() const
        {
            return _finish;
        }

        // construct and destroy
        vector(){}
        vector(int n, const T& value = T())
        {
            resize(n, value);
        }

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

        vector(const vector<T>& v)
        {
            reserve(v.size());
            for (auto& e : v)
            {
                push_back(e);
            }
        }
        
        vector<T>& operator= (vector<T> v)
        {
            swap(v);

            return *this;
        }
        ~vector()
        {
            delete[] _start;
        }

        // capacity
        size_t size() const
        {
            return _finish - _start;
        }
        size_t capacity() const
        {
            return _endOfStorage - _start;
        }
        void reserve(size_t n)
        {
            if (n > capacity())
            {
                int length = size();

                T* tmp = new T[n];
                for (int i = 0; i < length; i++)
                {
                    tmp[i] = *(_start + i);
                }
                delete[] _start;

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

        ///access///
        T& operator[](size_t pos)
        {
            assert(pos < size());

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

            return _start[pos];
        }
        

        ///modify/
        void push_back(const T& x = T())
        {
            if (_finish == _endOfStorage)
            {
                reserve(capacity() == 0 ? 1 : 2 * capacity());
            }

            *_finish = x;
            _finish++;
        }
        void pop_back()
        {
            assert(_start != _finish);

            _finish--;
        }
        void swap(vector<T>& v)
        {
            std::swap(v._start, _start);
            std::swap(v._finish, _finish);
            std::swap(v._endOfStorage, _endOfStorage);
        }
        iterator insert(iterator pos, const T& x = T())
        {
            assert(pos <= end());
            assert(pos >= begin());

            size_t len = pos - begin();
            if (_finish == _endOfStorage)
            {
                reserve(capacity() == 0 ? 1 : 2 * capacity());
                pos = begin() + len;
            }

            auto end = _finish;
            while (end > pos)
            {
                *end = *(end - 1);
                end--;
            }

            *pos = x;
            _finish++;

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

            _finish--;

            return pos;
        }

    private:        
        iterator _start = nullptr; // 指向数据块的开始
        iterator _finish = nullptr; // 指向有效数据的尾
        iterator _endOfStorage = nullptr; // 指向存储容量的尾
    };
}