【C++数据结构】STL标准库学习_vector模拟实现

淩亂°似流年 2024-03-22 03:36 99阅读 0赞

**目录**

【3.1.1】 结构框架

【3.1.2】构造函数Vector()

【3.1.3】构造函数Vector(inputIterator begin, inputIterator end)

【3.1.4】构造函数Vector(int n, const T& val = T())

【3.1.5】 拷贝构造Vector(const Vector& v)

【3.1.6】 析构函数~Vector()

【3.2.6】返回容量capacity()

【3.2.7】返回容量size()

【3.6.8】 判空Empty()

【3.6.9】 清空Clear()

【3.6.10】 交换Swap(Vector& v)

【3.2.11】尾插push\_back(const value\_type& val)

【3.2.12】扩容Reserve(size\_t n)

【3.2.13】调整finist大小Resize(size\_t n ,const T val = 0)

【3.2.14】迭代器iterator

【3.2.15】取位置数据operator\[\]

【3.2.16】尾删pop\_back()

【3.2.17】指定位置插入Insert(iterator pos, const T& val)

【3.2.18】指定位置删除Erase(iterator pos)

【3.1.19】赋值拷贝operator=

【3.1.20】辅助->杨辉三角测试用例

【3.1.21】vector模拟实现完整代码

--------------------

### 【3.1.1】 结构框架 ###

模拟实现方式为个人练习所用，理解底层的实现方式：由于和STL的官方库会冲突，所以代码我们卸载Vector.h中的ShaXiang命名空间下，这样方便测试，也不会和标准的官方库发生冲突。

![0995d1e426f84663b1a45f04eb7e9f1c.png][]

#include <iostream>
    using namespace std;
    
    namespace ShaXiang {
        template<class T>
        class vector {
        // 公有：类型
        public:
            // 泛型T类型->typedef(iterator)
            typedef T* iterator;
            
        // 私有：成员变量
        private:
            iterator _start;        // 存储指针.
            iterator _finish;       // 大小指针.
            iterator _endofstorage; // 容量指针.
    
        // 公有：构造/析构
        public:
            // 无参构造
            vector() : _start(nullptr), _finish(nullptr), _endofstorage(nullptr) {};
        };
    }

### 【3.1.2】构造函数Vector() ###

/* 无参构造函数 */
    // Vector()
    Vector()
        :_start(nullptr)
        ,_finish(nullptr)
        ,_endofstorage(nullptr)
    {
        // ..
    }

### 【3.1.3】构造函数Vector(inputIterator begin, inputIterator end) ###

/* 使用迭代器的构造函数 */
    template <class inputIterator>
    Vector(inputIterator begin, inputIterator end)
        :_start(nullptr)
        ,_finish(nullptr)
        ,_endofstorage(nullptr)
    {
        while (begin < end)
        {
            pushBack(*begin);
            ++begin;
        }
    }

### 【3.1.4】构造函数Vector(int n, const T& val = T()) ###

/* 使用迭代器的构造函数 */
    Vector(int n, const T& val = T())
        :_start(nullptr)
        , _finish(nullptr)
        , _endofstorage(nullptr)
    {
        // 先开辟指定的空间，虽然并不能提高多少效率。
        Reserve(n);
        for (int i = 0; i < n; ++i)
        {
            PushBack(val);
        }
    }

### 【3.1.5】 拷贝构造Vector(const Vector<T>& v) ###

/* 拷贝构造 */
    Vector(const Vector<T>& v)
        :_start(nullptr)
        , _finish(nullptr)
        , _endofstorage(nullptr)
    {
        // 开辟一块新的空间，将数据拷贝到新的空间中，函数体内为this
        _start = new T[v.Capacity()];
        memcpy(_start, v._start, sizeof(T) * v.Size());
    
        _finish = _start + v.Size();
        _endofstorage = _start + v.Capacity();
    }
    
    // 拷贝构造->传统写法
    vector(const vector<T>& v) 
        : _start(nullptr)
        , _finish(nullptr)
        , _endofstorage(nullptr) 
    {       
        this->reserve(v.capacity());
        for (auto& e : v) {
            this->push_back(e);
        }
    }
    
    /* 拷贝构造现代写法 */
    Vector(const Vector<T>& v)
        :_start(nullptr)
        , _finish(nullptr)
        , _endofstorage(nullptr)
    {
        // 利用构造函数构造一个函数
        Vector<T> cv(v.begin(), v.end());
        Swap(cv);   // cv是局部的变量 ，出函数就会调用自己的析构，所以不需要做处理。
    }

### 【3.1.6】 析构函数~Vector() ###

// 析构
    ~vector() {
        delete[] _start;
        _finish = _endofstorage = nullptr;
    }

### 【3.2.6】返回容量capacity() ###

size_type capacity() const;
    // 返回容量
    size_t capacity() const {
        return _endofstorage - _start;
    }

### 【3.2.7】返回容量size() ###

size_type size() const;
    // 返回大小
    size_t size() const {
        return _finish - _start;
    }

### 【3.6.8】 判空Empty() ###

/* 判断容器是否为空 */
    bool Empty()
    {
    	return _start == _finish;
    }

### 【3.6.9】 清空Clear() ###

/* 清空容器 */
    void Clear()
    {
    	_finish = _start;
    }

### 【3.6.10】 交换Swap(Vector<T>& v) ###

/* 交换容器 */
    void Swap(Vector<T>& v)
    {
    	std::swap(_start, v._start);
    	std::swap(_finish, v._finish);
    	std::swap(_endofstorage, v._endofstorage);
    }

### 【3.2.11】尾插push\_back(const value\_type& val) ###

先做出尾插函数方便后面测试，要不然都测试不效果..............我这里直接测试我已经写好的，里面相关的代码这一块都会进行解析，如果看不明白就继续往下看：

/* 尾插 */
    // void push_back (const value_type& val);
    void PushBack(const T& val)
    {
    	// 检查扩容.
    	if (_finish == _endofstorage)
    	{
    		// 扩容：我们不知道要扩容多少，这里我们写一个判断：
    		size_t newCapacity = Capacity() == 0 ? 4 : Capacity() * 2;
    		Reserve(newCapacity);
    	}
    
    	// 程序走到这里说明：扩容完成，即扩容成不成功在Reserve中进行判断。
    	// 直接插入到_finish位置数据，让_finish++
    	*_finish = val;
    	++_finish;
    }

### 【3.2.12】扩容Reserve(size\_t n) ###

vector的扩容是一个很让人烦的函数，我们这个函数会实现好几遍：因为随着程序不断加大功能，普通的扩容是不能满足当前的需求的，这里会涉及到深浅拷贝的问题：当然代码就是最后一个版本的函数~动动手往下翻翻哦

// 版本一：
    /* 扩容 */
    void reserve(size_t n) {
    	if (n > capacity()) {
    		// 开辟新的空间.
    		T* temp = new T[n];
    		// 记忆原有的大小.
    		size_t OldSize = size();
    
    		// 判断一下_start是不是空，如果是空，不需要拷贝数据.
    		if (_start != nullptr) {
    			// 拷贝数据，并且销毁原来的空间.
    			memcpy(temp, _start, sizeof(T) * OldSize);
    			delete[] _start;
    		}
    
    		// 空间开辟完成，转移数据.
    		_start = temp;
    		_finish = temp + OldSize;
    		_endofstorage = _start + n;
    	}
    }
    // 这个版本的程序我们直接运行会发现系统出现了访问错误的问题：那我们看看究竟是怎么回事：

题目链接：[118. 杨辉三角 - 力扣（Leetcode）][118. _ - _Leetcode]

通过上面的杨辉三角题目，我对代码进行了调试，这里我观察到\_finish这个指针出现了问题：然后我更改了一个版本进行解决！

![d72aa8334f8e4c31808d589b850a742f.png][]

/* 扩容 */
    void Reserve(size_t n)
    {
    	if (n > Capacity())
    	{
    		// 更改：需要记录下_finish的位置，更新完容量后_finish也需要更新位置。
    		size_t memaryFinishPos = Size();
    
    		// No.1 先开辟新的空间.
    		T* temp = new T[n];
    
    		// 如果是空的容器，不需要进行拷贝，直接使用指针就可以啦
    		if (_start != nullptr)
    		{
    			// No.2 将原有的数据拷贝到新的内存空间中.
    			// memcpy(temp, _start, sizeof(T) * memaryFinishPos);
    			// 更改为深拷贝！
    			for (size_t i = 0; i < memaryFinishPos; ++i)
    			{
    				temp[i] = _start[i];
    			}
    
    			// No.3 销毁掉之前的空间.
    			delete[] _start;
    		}
    		// No.4 使用新的空间
    		_start = temp;
    		_finish = _start + memaryFinishPos;
    		_endofstorage = _start + n;
    	}
    	
    }

### 【3.2.13】调整finist大小Resize(size\_t n ,const T val = 0) ###

void resize (size_type n, value_type val = value_type());
    // 扩容 或 扩充数据 或 删除数据。
    // n > endofstorage				扩容+填数据.
    // finish < n <= endofstorage	填数据.
    // n <= endofstorage			删数据.
    void Resize(size_t n ,const T val = 0)
    {
    	// 扩容的大小比原来的容量大->扩容
    	if (n > Capacity())
    	{
    		// 扩容
    		Reserve(n);
    	}
    
    	// 这里是需要填充数据的，但是不要担心容量不足，因为上面已经会进行判断扩容啦
    	// 这里如果没有执行上面的if语句，说明n肯定是小于容量的。
    	if (n > Size())
    	{
    		while (_finish < _start + n)
    		{
    			*_finish = val;
    			++_finish;
    		}
    	}
    	else
    	{
    		_finish = _start + n;
    	}
    }

### 【3.2.14】迭代器iterator ###

打印方式我写了三种：是怎么实现的呢？

这里看一下迭代器和operator\[\]取位置数据<就可以明白了>

// No.1 打印方式一
    for (size_t i = 0; i < iVector.Size(); ++i)
    {
    	cout << iVector[i] << " ";
    }
    cout << endl;
    
    // No.2 打印方式二
    for (auto v : iVector)
    {
    	cout << v << " ";
    }
    cout << endl;
    
    // No.3 打印方式三
    Vector<int>::iterator itBegin = iVector.begin();
    while (itBegin < iVector.end())
    {
    	cout << *itBegin << " ";
    	++itBegin;
    }
    cout << endl;
    /* 迭代器：返回容器第一个位置的指针 */
    iterator begin()
    {
    	return _start;
    }
    const_iterator begin() const
    {
    	return _start;
    }
    
    /* 迭代器：返回容器最后一个位置的指针 */
    iterator end()
    {
    	return _start + Size();
    }
    const_iterator end() const
    {
    	return _start + Size();
    }

### 【3.2.15】取位置数据operator\[\] ###

这个代码就先不解释了，返回pos位置的别名，别名的使用一定注意：使用别名要确保空间还是存在的，否则就会和野指针一样！当然野引用和野指针是两个概念，但是意思是一致的。

/* 返回指定位置的数据 */
    T& operator[](size_t pos)
    {
        assert(pos < size());
    	return _start[pos];
    }
    const T& operator[](size_t pos) const
    {
        assert(pos < size());
    	return _start[pos];
    }

### 【3.2.16】尾删pop\_back() ###

void pop_back();
    // 成员函数：尾删
    void pop_back() {
    	assert(!empty());
    	--_finish;
    }

### 【3.2.17】指定位置插入Insert(iterator pos, const T& val) ###

这个程序是错的，下面图解后才是对的！

/* 在pos位置插入 */
    // iterator insert (iterator position, const value_type& val);
    iterator Insert(iterator pos, const T& val)
    {
    	// 检查pos的位置是否正确
    	assert(pos >= _start);
    	assert(pos <= _finish);
    
    	// 检查是否需要扩容
    	if (_finish == _endofstorage)
    	{
    		// 扩容：我们不知道要扩容多少，这里我们写一个判断：
    		size_t newCapacity = Capacity() == 0 ? 4 : Capacity() * 2;
    		Reserve(newCapacity);
    	}
    
    	// 挪动数据。
    	iterator end = _finish - 1;
    	while (end >= pos)
    	{
    		*(end + 1) = *end;
    		--end;
    	}
    
    	// 数据挪动完了，后将这个位置插入数据。
    	*(end + 1) = val;
    	++_finish;
    
    	return pos;  // 返回pos位置的数据，
    }

/* 在pos位置插入 */
    // iterator insert (iterator position, const value_type& val);
    iterator Insert(iterator pos, const T& val)
    {
    	// 检查pos的位置是否正确
    	assert(pos >= _start);
    	assert(pos <= _finish);
    
    	// 检查是否需要扩容
    	if (_finish == _endofstorage)
    	{
    		// 更改：我们需要记录pos原本在容器上是哪一个位置，然后在让他指向新开辟的容器上。
    		size_t memaryPos = pos - _start;
    
    		// 扩容：我们不知道要扩容多少，这里我们写一个判断：
    		size_t newCapacity = Capacity() == 0 ? 4 : Capacity() * 2;
    		Reserve(newCapacity);
    
    		// 恢复pos原本指向的位置！
    		pos = _start + memaryPos;
    	}
    
    	// 挪动数据。
    	iterator end = _finish - 1;
    	while (end >= pos)
    	{
    		*(end + 1) = *end;
    		--end;
    	}
    
    	// 数据挪动完了，后将这个位置插入数据。
    	*(end + 1) = val;
    	++_finish;
    
    	return pos;  // 返回pos位置的数据，
    }

### 【3.2.18】指定位置删除Erase(iterator pos) ###

![7cf40d24e2a5403a9e798c7efe0065a6.png][]

/* 在pos位置删除 */
    // iterator erase (iterator position);
    iterator Erase(iterator pos)
    {
    	// 检查pos的位置是否正确
    	assert(pos >= _start);
    	assert(pos < _endofstorage);
    
    	if (!Empty())
    	{
    		// 迭代
    		iterator itBegin = pos;
    		while(itBegin < _finish)
    		{
    			*itBegin = *(itBegin + 1);
    			++itBegin;
    		}
    	}
    
    	--_finish;
    	return pos;
    }

### 【3.1.19】赋值拷贝operator= ###

/* 赋值 */
    Vector<T> operator=(Vector<T> v)		//函数正确
    {					// 这里需要更改：所以不能用const
    	Swap(v);
    	return *this;
    }

###  ###

### 【3.1.20】辅助->杨辉三角测试用例 ###

class Solution {
    public:
    	vector<vector<int>> generate(int numRows)
    	{
    		// 定义二维的vector ：就等于是二维数组。
    		vector<vector<int>> vv;
    		vv.resize(numRows);    // 开辟外围vector<>的容量空间。
    
    		// 开辟内层vector<vector<int>>的容量。
    		for (size_t i = 0; i < vv.size(); ++i)
    		{
    			// 初始化每一个vector<int>的数据，第一个和最后一个初始化为1.
    			vv[i].resize(i + 1, 0);
    			vv[i][0] = vv[i][vv[i].size() - 1] = 1;
    		}
    
    		// 杨辉三角的计算
    		for (size_t i = 0; i < vv.size(); i++)
    		{
    			for (size_t j = 0; j < vv[i].size(); j++)
    			{
    				if (vv[i][j] == 0)
    					vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
    			}
    		}
    
    		return vv;
    	}
    };
    
    void VectorTest() {
    	Solution s;
    	vector<vector<int>> vv = s.generate(10);
    
    	for (size_t i = 0; i < vv.size(); i++)
    	{
    		for (size_t j = 0; j < vv[i].size(); j++)
    		{
    			cout << vv[i][j];
    		}
    		cout << endl;
    	}
    }

### 【3.1.21】vector模拟实现完整代码 ###

#include <iostream>
    #include <cstring>
    #include <cassert>
    using namespace std;
    
    namespace ShaXiang {
        template<class T>
        class vector {
        // 公有：类型
        public:
            // 泛型T类型->typedef(iterator)
            typedef T* iterator;
            typedef const iterator const_iterator;
    
        // 私有：成员变量
        private:
            iterator _start;        // 存储指针.
            iterator _finish;       // 大小指针.
            iterator _endofstorage; // 容量指针.
    
        // 公有：构造/析构
        public:
            // 无参构造
            vector() : _start(nullptr), _finish(nullptr), _endofstorage(nullptr) {};
    
            // n个值构造
            vector(int n, const T& val = T()) : _start(nullptr), _finish(nullptr), _endofstorage(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), _endofstorage(nullptr) {
                while (first != last) {
                    push_back(*first);
                    ++first;
                }
            }
    
            // 拷贝构造->传统写法
            //vector(const vector<T>& v) : _start(nullptr), _finish(nullptr), _endofstorage(nullptr) {
            //  // 开辟新的空间.
            //  _start = new T[v.capacity()];
            //  // 将数据拷贝到新空间上
            //  memcpy(_start, v._start, sizeof(T) * v.size());
            //  // 释放就空间.
            //  _finish = _start + v.size();
            //  _endofstorage = _start + v.capacity();
            //}
    
            // 拷贝构造->传统写法
            //vector(const vector<T>& v) : _start(nullptr), _finish(nullptr), _endofstorage(nullptr) {      
            //  this->reserve(v.capacity());
            //  for (auto& e : v) {
            //      this->push_back(e);
            //  }
            //}
    
            // 拷贝构造->现代写法
            vector(const vector<T>& v) : _start(nullptr), _finish(nullptr), _endofstorage(nullptr) {
                vector<T>temp(v.begin(), v.end());
                swap(temp);
            }
    
            // 析构
            ~vector() {
                delete[] _start;
                _finish = _endofstorage = nullptr;
            }
    
        // 公有：迭代器
        public:
            // 成员函数：迭代器first
            iterator begin() {
                return _start;
            }
    
            // 成员函数：迭代器end
            iterator end() {
                return _finish;
            }
    
            // 成员函数：迭代器first const
            const_iterator begin() const {
                return _start;
            }
    
            // 成员函数：迭代器end const
            const_iterator end() const {
                return _finish;
            }
    
        // 共有：成员函数
        public:
            // 成员函数：返回大小
            size_t size() const {
                return _finish - _start;
            }
    
            // 成员函数：返回容量
            size_t capacity() const {
                return _endofstorage - _start;
            }
    
            // 成员函数：判空
            bool empty() {
                return _finish == _start;
            }
    
            // 成员函数：清空
            void clear() {
                _finish = _start;
            }
    
            // 成员函数：交换
            void swap(vector<T>& v) {
                std::swap(_start, v._start);
                std::swap(_finish, v._finish);
                std::swap(_endofstorage, v._endofstorage);
            }
    
            // 成员函数：扩容
            void reserve(size_t n) {
                if (n > capacity()) {
                    // 开辟新的空间.
                    T* temp = new T[n];
                    // 记忆原有的大小.
                    size_t OldSize = size();
    
                    // 判断一下_start是不是空，如果是空，不需要拷贝数据.
                    if (_start != nullptr) {
                        // 拷贝数据，并且销毁原来的空间.
                        // memcpy(temp, _start, sizeof(T) * OldSize);
                        for (size_t i = 0; i < OldSize; i++) {
                            temp[i] = _start[i];
                        }
                        delete[] _start;
                    }
    
                    // 空间开辟完成，转移数据.
                    _start = temp;
                    _finish = temp + OldSize;
                    _endofstorage = _start + n;
                }
            }
    
            // 扩容 或 扩充数据 或 删除数据。
            // n > endofstorage             扩容+填数据.
            // finish < n <= endofstorage   填数据.
            // n <= endofstorage            删数据.
            void resize(size_t n, const T val = T()) {
                // 扩容的大小比原来的容量大->扩容
                if (n > capacity()) {
                    reserve(n);
                }
    
                // 这里是需要填充数据的，但是不要担心容量不足，因为上面已经会进行判断扩容啦
                // 这里如果没有执行上面的if语句，说明n肯定是小于容量的。
                if (n > size()) {
                    while (_finish != _start + n) {
                        *_finish = val;
                        ++_finish;
                    }
                }
                else { // 删除数据
                    _finish = _start + n;
                }
    
            }
    
            // 成员函数：尾插
            void push_back(const T& val) {
                // 检查扩容
                if (_finish == _endofstorage) {
                    // 扩容：我们不知道要扩容多少，这里我们写一个判断
                    size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
                    reserve(newCapacity);
                }
                // 程序走到这里说明：扩容完成，即扩容成不成功在Reserve中进行判断。
                // 直接插入到_finish位置数据，让_finish++
                *_finish = val;
                ++_finish;
            }
    
            // 成员函数：尾删
            void pop_back() {
                assert(!empty());
                --_finish;
            }
    
            // 成员函数：指定位置插入
            iterator insert(iterator pos, const T& val) {
                // 检查pos的位置是否正确
                assert(pos >= _start);
                assert(pos <= _finish);
    
                // 检查是否需要扩容
                if (_finish == _endofstorage) {
                    // 记录pos指针的相对位置
                    size_t memaryPos = pos - _start;
    
                    // 扩容：我们不知道要扩容多少，这里我们写一个判断
                    size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
                    reserve(newCapacity);
    
                    // 恢复pos原本指向的位置！
                    pos = _start + memaryPos;
                }
    
                // 挪动数据。
                iterator end = _finish - 1;
                while (end >= pos) {
                    *(end + 1) = *end;
                    --end;
                }
    
                // 数据挪动完了，后将这个位置插入数据。
                *(end + 1) = val;
                ++_finish;
    
                return pos;
            }
    
            // 成员函数：指定位置删除
            iterator erase(iterator pos) {
                assert(pos >= _start);
                assert(pos < _finish);
    
                // vector不能为空！
                if (!empty()) {
                    iterator begin = pos;
                    while (begin < _finish) {
                        (*begin) = *(begin + 1);
                        ++begin;
                    }
                    --_finish;
                }
                
                return pos;
            }
    
        // 公有：运算符重载
        public:
            // 运算符重载：[]
            T& operator[](size_t pos) {
                assert(pos < size());
                return _start[pos];
            }
            
            // 运算符重载：[] const
            const T& operator[](size_t pos) const {
                return _start[pos];
            }
    
            // 运算符重载：=
            vector<T>& operator=(vector<T> v) {
                swap(v);
                return *this;
            }
        };
    
        class Solution {
        public:
            vector<vector<int>> generate(int numRows)
            {
                // 定义二维的vector ：就等于是二维数组。
                vector<vector<int>> vv;
                vv.resize(numRows);    // 开辟外围vector<>的容量空间。
    
                // 开辟内层vector<vector<int>>的容量。
                for (size_t i = 0; i < vv.size(); ++i)
                {
                    // 初始化每一个vector<int>的数据，第一个和最后一个初始化为1.
                    vv[i].resize(i + 1, 0);
                    vv[i][0] = vv[i][vv[i].size() - 1] = 1;
                }
    
                // 杨辉三角的计算
                for (size_t i = 0; i < vv.size(); i++)
                {
                    for (size_t j = 0; j < vv[i].size(); j++)
                    {
                        if (vv[i][j] == 0)
                            vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
                    }
                }
    
                return vv;
            }
        };
    
        void VectorTest() {
            Solution s;
            vector<vector<int>> vv = s.generate(10);
    
            for (size_t i = 0; i < vv.size(); i++)
            {
                for (size_t j = 0; j < vv[i].size(); j++)
                {
                    cout << vv[i][j];
                }
                cout << endl;
            }
        }
    }

[0995d1e426f84663b1a45f04eb7e9f1c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/21425660c8e448928c61aec4008089c4.png
[118. _ - _Leetcode]: https://leetcode.cn/problems/pascals-triangle/description/
[d72aa8334f8e4c31808d589b850a742f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/a9a8038e974c4e3e8ef1d6d0c7193aed.png
[7cf40d24e2a5403a9e798c7efe0065a6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/6ed1f01bf7d44410a958e00da49f3207.png