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

vector的使用及其模拟实现

文章目录

  • vector的使用及其模拟实现
  • 1. vector的使用
    • 1.1 构造函数construct
    • 1.2 获取当前存储的数据个数size()和最大容量capacity()
    • 1.3 访问
      • 1.3.1 operator[]运算符重载
      • 1.3.2 迭代器访问
      • 1.3.3 范围for
    • 1.4 容量相关reserve()和resize()
    • 1.5 增(插入数据)
      • 1.5.1 push_back() 尾插
      • 1.5.2 insert() 随机插入
    • 1.6 删(删除数据)
      • 1.6.1 pop_back() 尾删
      • 1.6.2 erase() 随机删除
  • 2. 模拟实现
    • 2.1 vector的内部结构
    • 2.2 部分细节的说明
      • 2.2.1 C++对内置类型的”升级“
      • 2.2.2 迭代器失效
      • 2.2.3 memcpy的浅拷贝问题
    • 2.3 模拟实现代码:

本章思维导图:


在这里插入图片描述注:本章思维导图对应的
.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 > capacityreserve()只会为该容器重新开辟一块大小为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() << "

";

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

";

    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() << "

";

    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() << "

";

    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() << "

";
    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再加上两个整数sizecapacity来实现的
  • 实际上,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这种自定义类型好说,他们有构造函数,但如果Tint这种内置类型呢,难道它们也有自己的构造函数吗?

答案确实如此,为了适应类和对象,我们可以认为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() << "
";
	v.insert(it, 100);
	cout << v.capacity() << "
";

	cout << *it << "
";
	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; // 指向存储容量的尾
    };
}