【c++初阶】第九篇:vector(常用接口的使用 + 模拟实现)
文章目录
- vector介绍
- vector的使用
- vector的定义
- vector iterator(迭代器) 的使用
- begin和end
- rbegin和rend
- vector 空间增长问题
- size和capacity
- reserve和resize(重点)
- 测试vector的默认扩容机制
- empty
- vector的增删查改
- push_back和pop_back
- insert和erase
- find
- swap
- operator[] 元素访问(重点)
- vector 迭代器失效问题(重点)
- 迭代器失效问题举例
- 迭代器失效解决方法
- 总结
- vector的模拟实现
- vector当中的成员变量介绍
- vector模拟实现接口函数预览
- 默认成员函数
- 构造函数1
- 构造函数2
- 构造函数3
- 模拟实现构造函数调用不明确
- 拷贝构造函数
- 赋值运算符重载函数
- 析构函数
- 迭代器相关函数
- begin和end
- 访问容器相关函数
- operator[ ]
- 容量和大小相关函数
- size和capacity
- reserve
- resize
- empty
- 修改容器内容相关函数
- push_back
- pop_back
- insert
- erase
- swap
- 总结
vector介绍
- vector是表示可变大小数组的序列容器。
- vector就像数组一样,也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。
- 当新元素插入,vector需要重新分配大小时,其做法是,分配一个新的数组,然后将全部元素移到这个数组当中,并释放原来的数组空间。
- vector分配空间策略:vector会分配一些额外的空间以适应可能的增长,因此存储空间比实际需要的存储空间一般更大。不同的库采用不同的策略权衡空间的使用和重新分配,以至于在末尾插入一个元素的时候是在常数的时间复杂度完成的。
- 由于vector采用连续的空间来存储元素,与其他动态序列容器相比,vector在访问元素的时候更加高效,在其末尾添加和删除元素相对高效,而对于不在其末尾进行的删除和插入操作效率则相对较低。
vector的使用
vector底层是一个类模板,当我们定义的时候,需要显示实例化类型。
vector的定义
方式一: 构造一个某类型的空容器。
vector<int> v1; //构造int类型的空容器
方式二: 构造一个含有n个val的某类型容器。
vector<int> v2(10, 2); //构造含有10个2的int类型容器
方式三: 拷贝构造某类型容器。
vector<int> v3(v2); //拷贝构造int类型的v2容器
方式四: 使用迭代器拷贝构造某一段内容。
vector<int> v4(v2.begin(), v2.end()); //使用迭代器拷贝构造v2容器的某一段内容
注意:该方式也可用于拷贝其他容器的某一段内容。
string s("hello world");
vector<char> v5(s.begin(), s.end()); //拷贝构造string对象的某一段内容
vector iterator(迭代器) 的使用
begin和end
通过begin函数可以返回容器中第一个元素的迭代器,通过end函数可以返回容器中最后一个元素的后一个位置的迭代器。
我们这提前介绍一下push_back()
的使用。
通过push_back函数对容器进行尾插
void test_vector1()
{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()){cout << *it << " ";++it;}cout << endl;
}
rbegin和rend
通过rbegin函数可以得到容器中最后一个元素的反向迭代器,通过rend函数可以得到容器中第一个元素的前一个位置的反向迭代器。
注意:反向迭代器的书写:reverse_iterator
void test_vector2()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);//反向迭代器遍历容器vector<int>::reverse_iterator it = v.rbegin();while (it != v.rend()){cout << *it << " ";++it;}cout << endl;
}
vector 空间增长问题
size和capacity
通过size函数获取当前容器中的有效元素个数,通过capacity函数获取当前容器的最大容量。
void test_vector3()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);cout << v.size() << endl;//获取当前容器中的有效元素个数cout << v.capacity() << endl;//获取当前容器的最大容量
}
reserve和resize(重点)
通过reserve函数改变容器的最大容量(capacity),resize函数改变容器中的有效元素(size)个数。
reserve规则:
1、当所给值大于容器当前的capacity时,将capacity扩大到该值。
2、当所给值小于容器当前的capacity时,什么也不做。
resize规则:
1、当所给值大于容器当前的size时,将size扩大到该值,扩大的元素为第二个参数所给值,若未给出,则默认为0。
2、当所给值小于容器当前的size时,将size缩小到该值。(注意:不会改变capacity的大小,即不会缩容)
void test_vector4()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);cout << v.size() << endl;//5cout << v.capacity() << endl << endl;//6//reserve// 大于容器当前的capacity时v.reserve(10);cout << v.size() << endl;//size不变 5cout << v.capacity() << endl << endl; //改变容器的capacity为10,// 比当前容量小时,不缩容v.reserve(4);cout << v.size() << endl;//size不变 5cout << v.capacity() << endl << endl;//不变 10//resizev.resize(8);cout << v.size() << endl;//改变容器的size为8cout << v.capacity() << endl << endl;//10v.resize(15, 1);cout << v.size() << endl;//改变容器的size为15,扩大的元素用1初始化cout << v.capacity() << endl << endl;//15v.resize(3);//不會縮容cout << v.size() << endl;//size缩小到3cout << v.capacity() << endl << endl;//不变 15
}
测试vector的默认扩容机制
测试代码
void TestVectorExpand()
{size_t sz;vector<int> v;sz = v.capacity();cout << "making v grow:\n";for (int i = 0; i < 100; ++i){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}
在vs环境下运行结果:
在Linux环境下运行结果:
这段代码在vs和g++下分别运行会发现,vs下capacity是按大概1.5倍增长的,g++是按2倍增长的。
这个问题经常会考察,不要固化的认为,vector增容都是2倍,具体增长多少是根据具体的需求定义的。vs是PJ版本STL,g++是SGI版本STL。
reserve只负责开辟空间,如果确定知道需要用多少空间,reserve可以缓解vector增容的代价缺陷问题。
empty
通过empty函数判断当前容器是否为空。
#include <iostream>
#include <vector>
using namespace std;int main()
{vector<int> v(10, 2);cout << v.empty() << endl;return 0;
}
vector的增删查改
push_back和pop_back
通过push_back函数对容器进行尾插,pop_back函数对容器进行尾删。
void test_vector5()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (const auto& e : v){cout << e << " ";}cout << endl;v.pop_back();v.pop_back();v.pop_back();v.pop_back();for (const auto& e : v){cout << e << " ";}cout << endl;
}
insert和erase
通过insert函数可以在所给迭代器位置之前插入一个或多个元素,通过erase函数可以删除所给迭代器位置的元素,或删除所给迭代器区间内的所有元素(左闭右开)。
void test_vector6()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (const auto& e : v){cout << e << " ";}cout << endl;v.insert(v.begin(), 0); //在容器开头插入0v.insert(v.begin()+3, 5, 1); //在3位置之前插入5个1for (const auto& e : v){cout << e << " ";}cout << endl;v.erase(v.begin()); //删除容器中的第一个元素v.erase(v.begin()+2, v.begin() + 7); //删除在该迭代器区间内的元素(左闭右开)for (const auto& e : v){cout << e << " ";}cout << endl;
}
以上是按位置进行插入或删除元素的方式,若要按值进行插入或删除(在某一特定值位置进行插入或删除),则需要用到find函数。
find
功能: 查找。
注意: find函数是算法模块实现,不是vector的成员接口,vector的成员接口中没有find。
find函数共三个参数,前两个参数确定一个迭代器区间(左闭右开),第三个参数确定所要寻找的值。
find函数在所给迭代器区间寻找第一个匹配的元素,并返回它的迭代器,若未找到,则返回所给的第二个参数。
void test_vector7()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (const auto& e : v){cout << e << " ";}cout << endl;//在3位置之前插入一个30vector<int>::iterator it = find(v.begin(), v.end(), 3); //获取值为3的元素的迭代器if (it != v.end()){v.insert(it, 30);}for (const auto& e : v){cout << e << " ";}cout << endl;//删除30it = find(v.begin(), v.end(), 30); //获取值为30的元素的迭代器if (it != v.end()){v.erase(it);}for (const auto& e : v){cout << e << " ";}cout << endl;
}
swap
通过swap函数可以交换两个容器的数据空间,实现两个容器的交换。
void test_vector8()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);cout << "交换之前的v: ";for (const auto& e : v){cout << e << " ";}cout << endl;vector<int> v1;v1.push_back(10);v1.push_back(20);v1.push_back(30);cout << "交换之前的v1: ";for (const auto& e : v1){cout << e << " ";}cout << endl << endl;v1.swap(v);//交换v1,v的数据空间cout << "交换之后的v: ";for (const auto& e : v){cout << e << " ";}cout << endl;cout << "交换之后的v1: ";for (const auto& e : v1){cout << e << " ";}cout << endl;}
operator[] 元素访问(重点)
vector当中实现了 [ ] 操作符的重载,因此我们也可以通过“下标+[ ]”的方式对容器当中的元素进行访问。
void test_vector9()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//使用“下标+[]”的方式遍历容器for (size_t i = 0; i < v.size(); ++i){cout << v[i] << " ";}cout << endl;//使用“下标+[]”的方式遍修改容器内的数据for (size_t i = 0; i < v.size(); ++i){v[i]++;}cout << endl;//使用“下标+[]”的方式遍历容器for (size_t i = 0; i < v.size(); ++i){cout << v[i] << " ";}cout << endl;
}
vector 迭代器失效问题(重点)
迭代器的主要作用就是让我们在使用各个容器时不用关心其底层的数据结构,而vector的迭代器在底层实际上就是一个指针。迭代器失效就是指迭代器底层对应指针所指向的空间被销毁了,而指向的是一块已经被释放的空间,如果继续使用已经失效的迭代器,程序可能会崩溃。
迭代器失效问题举例
实例一:
void test_vector10()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);//v: 1 2 3 4 vector<int>::iterator pos = find(v.begin(), v.end(), 2); //获取值为2的元素的迭代器if (pos != v.end()){v.insert(pos, 10); //在值为2的元素的位置前插入10}//v: 1 10 2 3 4 v.erase(pos); //删除元素2 ???error(迭代器失效)//v: 1 2 3 4
}
在该代码中,我们本意是使用元素2的迭代器在原序列中2的位置插入一个10,然后将2删除,但我们实际上获取的是指向2的指针,当我们在2的位置插入10后,该指针就指向了10,所以我们之后删除的实际上是10,而不是2。
实例二:
void test_vector11()
{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) //删除容器当中的全部偶数{v.erase(it);}it++;}
}
该代码看上去实际上并没有什么错误,但如果你画图仔细分析,你就会发现该代码的问题所在,迭代器访问到了不属于容器的内存空间,导致程序崩溃。
不仅如此,而且在迭代器遍历容器中的元素进行判断时,并没有对3元素进行判断。
迭代器失效解决方法
使用迭代器时,永远记住一句话:每次使用前,对迭代器进行重新赋值。
实例一解决方案:
void test_vector10()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);//v: 1 2 3 4 vector<int>::iterator pos = find(v.begin(), v.end(), 2); //获取值为2的元素的迭代器if (pos != v.end()){v.insert(pos, 10); //在值为2的元素的位置前插入10}pos = find(v.begin(), v.end(), 2); //重新获取值为2的元素的迭代器v.erase(pos); //删除元素2//v: 1 10 3 4
}
对于实例一,我们在使用迭代器删除元素2时对其进行重新赋值便可以解决。
实例二解决方案:
void test_vector11()
{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) //删除容器当中的全部偶数{it = v.erase(it); //删除后获取下一个元素的迭代器}else{it++; //是奇数则it++}}
}
对于实例二,我们可以接收erase函数的返回值(erase函数返回删除元素的后一个元素的新位置),并且控制代码的逻辑:当元素被删除后继续判断该位置的元素(因为该位置的元素已经更新,需要再次判断)。
总结
以上就是对vector常用接口的使用的概述啦,其实学完string之后,我们对于vector的使用很快就会上手的。
vector的模拟实现
vector当中的成员变量介绍
在模拟实现string中,我们定义了以下三个成员变量
在vector当中也有三个成员变量_start
、_finish
、_endofstorage
。
他们的类型是一个迭代器如下:
他们与string中三个成员变量的对应关系如图:
vector模拟实现接口函数预览
namespace cl
{//模拟实现vectortemplate<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//迭代器相关函数iterator begin();iterator end();const_iterator begin()const;const_iterator end()const;//访问容器相关函数T& operator[](size_t i);const T& operator[](size_t i)const;//默认成员函数vector(); //构造函数vector(int n, const T& val = T()) //构造函数vector(size_t n, const T& val = T()); //构造函数template<class InputIterator> vector(InputIterator first, InputIterator last); //构造函数vector(const vector<T>& v); //拷贝构造函数vector<T>& operator=(const vector<T>& v); //赋值运算符重载函数~vector(); //析构函数//容量和大小相关函数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;//修改容器内容相关函数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);void clear()private:iterator _start; //指向容器的头iterator _finish; //指向有效数据的尾iterator _endofstorage; //指向容器的尾};
}
注: 为了防止与标准库当中的vector产生命名冲突,模拟实现时需放在自己的命名空间当中。
默认成员函数
构造函数1
vector首先支持一个无参的构造函数,对于这个无参的构造函数,我们直接将构造对象的三个成员变量都设置为空指针即可。
vector():_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{}
构造函数2
其次,vector还支持使用一段迭代器区间进行对象的构造。因为该迭代器区间可以是其他容器的迭代器区间,也就是说该函数接收到的迭代器的类型是不确定的,所以我们这里需要将该构造函数设计为一个函数模板,在函数体内将该迭代器区间的数据一个个尾插到容器当中即可。
template <class InputIterator>
vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{//将迭代器区间在[first,last)的数据一个个尾插到容器当中while (first != last){push_back(*first);++first;}
}
构造函数3
此外,vector还支持构造这样一种容器,该容器当中含有n个值为val的数据。对于该构造函数,我们可以先使用reserve函数将容器容量先设置为n,然后使用push_back函数尾插n个值为val的数据到容器当中即可。
//构造
vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(n);//调用reserve函数将容器容量设置为nfor (size_t i = 0; i < n; ++i){push_back(val);//尾插n个值为val的数据到容器当中}
}
注意:
- 该构造函数知道其需要用于存储n个数据的空间,所以最好用reserve函数一次性开辟好空间,避免调用push_back函数时需要增容多次,导致效率降低。
- 该构造函数还需要实现一个重载函数。
为什么还需要实现一个这种构造函数的重载函数呢?原因如下:
模拟实现构造函数调用不明确
1、问题描述
vector(size_t n, const T& val = T())//这里的形参用size_t就会引发这两个构造函数调用问题:_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(n);for (size_t 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;}
}
本意是想使用第一种构造方式,用5个6进行构造。编译器会根据形参调用最匹配的函数重载。
第三个构造函数的第一个形参是size_t,形参去匹配的话需要发生隐式类型转换。
但是这两个参数更匹配第二个构造函数(因为第二个模板可以为int,完全匹配),一旦走第二个构造函数,该构造函数内部是要对first进行解引用操作,所以编译器会报非法的间接寻址(解引用)错误。
2、解决调用不明确的方法
针对构造函数vector(size_t n, const T& val = T()),我们多重载一个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){push_back(val);}
}
拷贝构造函数
vector的拷贝构造函数涉及深拷贝问题,这里提供两种深拷贝的写法:
写法一:传统写法
拷贝构造的传统写法的思想是我们最容易想到的:先开辟一块与该容器大小相同的空间,然后将该容器当中的数据一个个拷贝过来即可,最后更新_finish和_endofstorage的值即可。
//传统写法
vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_endofstorage(nullptr)
{//开辟一块和容器v大小相同的空间_start = new T[v.capcity()];for (size_t i = 0; i < v.size(); ++i){_start[i] = v[i];}_finish = _start + v.size(); //容器有效数据的尾_endofstorage = _start + v.capacity(); //整个容器的尾
}
写法二:现代写法
拷贝构造函数的现代写法也比较简单,首先构造出一个tmp,然后将两者交换。
//拷贝构造
vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{vector<T> tmp(v.begin(), v.end());//利用v构造tmpswap(tmp);//交换
}
注意: 拷贝构造函数的现代写法也是进行的深拷贝,首先是调用第二类型的构造函数构造出一个新对象,然后在拷贝构造函数当中仅仅是将构造出来的新对象与左值进行了交换而已。
另一种写法:
vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(v.capacity()); //调用reserve函数将容器容量设置为与v相同for (const auto& e : v){push_back(e); //将容器v当中的数据一个个尾插过来}
}
赋值运算符重载函数
vector的赋值运算符重载当然也涉及深拷贝问题,我们这里也提供两种深拷贝的写法:
写法一:传统写法
首先判断是否是给自己赋值,若是给自己赋值则无需进行操作。若不是给自己赋值,则先开辟一块和容器v大小相同的空间,然后将容器v当中的数据一个个拷贝过来,最后更新_finish和_endofstorage的值即可。
//传统写法
vector<T>& operator=(const vector<T>& v)
{if (this != &v) //防止自己给自己赋值{delete[] _start; //释放原来的空间_start = new T[v.capacity()]; //开辟一块和容器v大小相同的空间for (size_t i = 0; i < v.size(); i++) //将容器v当中的数据一个个拷贝过来{_start[i] = v[i];}_finish = _start + v.size(); //容器有效数据的尾_endofstorage = _start + v.capacity(); //整个容器的尾}return *this; //支持连续赋值
}
写法二:现代写法
赋值运算符重载的现代写法非常精辟,首先在传参时并没有使用引用传参,因为这样可以间接调用vector的拷贝构造函数,然后将这个拷贝构造出来的容器v与左值(this)进行交换,此时就相当于完成了赋值操作,而容器v会在该函数调用结束时自动析构。
vector<T>& operator=(vector<T> v)//编译器接收传参的时候自动调用其拷贝构造函数
{swap(v); //交换这两个对象return *this;//支持连续赋值
}
注意: 赋值运算符重载的现代写法也是进行的深拷贝,只不过是调用的vector的拷贝构造函数进行的深拷贝,在赋值运算符重载函数当中仅仅是将深拷贝出来的对象与左值进行了交换而已。
析构函数
对容器进行析构时,首先判断该容器是否为空容器,若为空容器,则无需进行析构操作,若不为空,则先释放容器存储数据的空间,然后将容器的各个成员变量设置为空指针即可。
~vector()
{delete[] _start;//释放容器存储数据的空间_start = _finish = _endofstorage = nullptr;
}
迭代器相关函数
vector当中的迭代器实际上就是容器当中所存储数据类型的指针。
typedef T* iterator;
typedef const T* const_iterator;
begin和end
ector当中的begin函数返回容器的首地址,end函数返回容器当中有效数据的下一个数据的地址。
iterator begin()
{return _start;
}iterator end()
{return _finish;
}
我们还需要重载一对适用于const对象的begin和end函数,使得const对象调用begin和end函数时所得到的迭代器只能对数据进行读操作,而不能进行修改。
const_iterator begin() const
{return _start;
}const_iterator end() const
{return _finish;
}
此时再让我们来看看vector使用迭代器的代码也就一目了然了,实际上就是使用指针遍历容器。
vector<int> v(5, 3);
vector<int>::iterator it = v.begin();
while (it != v.end())
{cout << *it << " ";it++;
}
cout << endl;
现在我们实现了迭代器,实际上也就可以使用范围for遍历容器了,因为编译器在编译时会自动将范围for替换为迭代器的形式。
vector<int> v(5, 3);
//范围for进行遍历
for (const auto& e : v)
{cout << e << " ";
}
cout << endl;
访问容器相关函数
operator[ ]
vector也支持我们使用“下标+[ ]”的方式对容器当中的数据进行访问,实现时直接返回对应位置的数据即可。
//可读可写
T& operator[](size_t pos)
{assert(pos < size());return _start[pos];
}
//只读
const T& operator[](size_t pos) const
{assert(pos < size());return _start[pos];
}
注意: 重载运算符[ ]时需要重载一个适用于const容器的,因为const容器通过“下标+[ ]”获取到的数据只允许进行读操作,不能对数据进行修改。
容量和大小相关函数
size和capacity
对照着vector当中三个成员遍历各自的指向,我们可以很容易得出当前容器中的有效数据个数和最大容量。
由于区间是左闭右开的,所以两个指针相减的结果,就是这两个指针之间对应类型的数据个数,所以size可以由_finish - _start
得到,而capacity可以由_endofstorage - _start
得到。
size_t size() const
{return _finish - _start;//返回容器当中有效数据的个数
}size_t capacity() const
{return _endofstorage - _start;//返回当前容器的最大容量
}
reserve
reserve规则:
1、当n大于对象当前的capacity时,将capacity扩大到n或大于n。
2、当n小于对象当前的capacity时,什么也不做。
reserve函数的实现思路也是很简单的,先判断所给n是否大于当前容器的最大容量(否则无需进行任何操作),操作时直接开辟一块可以容纳n个数据的空间,然后将原容器当中的有效数据拷贝到该空间,之后将原容器存储数据的空间释放,并将新开辟的空间交给该容器维护,最好更新容器当中各个成员变量的值即可。
void reserve(size_t n)
{if (n > capacity())//判断是否需要进行操作{size_t oldSize = size();//记录当前容器当中有效数据的个数T* tmp = new T[n]; //开辟一块可以容纳n个数据的空间if (_start)//判断是否为空容器{for (size_t i = 0; i < oldSize; ++i){tmp[i] = _start[i]; //调用赋值运算符重载完成深拷贝}delete[] _start;}_start = tmp;_finish = tmp + oldSize;_endofstorage = _start + n;}
}
在reserve函数的实现当中有两个地方需要注意:
1)在进行操作之前需要提前记录当前容器当中有效数据的个数。
因为我们最后需要更新_finish指针的指向,而_finish指针的指向就等于_start指针加容器当中有效数据的个数,当_start指针的指向改变后我们再调用size函数通过_finish - _start计算出的有效数据的个数就是一个随机值了。
2)拷贝容器当中的数据时,不能使用memcpy函数进行拷贝。
可能你会想,当vector当中存储的是vector<int>
类型的时候,虽然使用memcpy函数reserve出来的容器与原容器当中每个对应的vector<int>
成员都指向同一个字符串空间,但是原容器存储数据的空间不是已经被释放了,相当于现在只有一个容器维护这这些字符串空间,这还有什么影响。
但是不要忘了,当你释放原容器空间的时候,原容器当中存储的每个vector<int>
在释放时会去调用vector<int>
的析构函数,将其指向的字符串也进行释放,所以使用memcpy函数reserve出来的容器当中的每一个vector<int>
所指向的字符串实际上是一块已经被释放的空间,访问该容器时就是对内存空间进行非法访问。
所以说我们还是得用for循环将容器当中的vector<int>
一个个赋值过来,因为这样能够间接调用vector<int>
的赋值运算符重载,实现vector<int>
的深拷贝。
resize
resize规则:
1、当n大于当前的size时,将size扩大到n,扩大的数据为val,若val未给出,则默认为容器所存储类型的默认构造函数所构造出来的值。
2、当n小于当前的size时,将size缩小到n。
根据resize函数的规则,进入函数我们可以先判断所给n是否小于容器当前的size,若小于,则通过改变_finish的指向,直接将容器的size缩小到n即可,否则先判断该容器是否需要增容,然后再将扩大的数据赋值为val即可。
empty
empty函数可以直接通过比较容器当中的_start和_finish指针的指向来判断容器是否为空,若_finish指向的位置与_start相同,则该容器为空。
bool empty() const
{return _finish == _start;
}
修改容器内容相关函数
push_back
要尾插数据首先得判断容器是否已满,若已满则需要先进行增容,然后将数据尾插到_finish指向的位置,再将_finish++即可。
void push_back(const T& x)
{if (_finish == _endofstorage)//判断是否需要增容{size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;//将容量扩大为原来的两倍reserve(newCapacity);//增容}*_finish = x; //尾插数据++_finish;//_finish指针后移
}
pop_back
尾删数据之前也得先判断容器是否为空,若为空则做断言处理,若不为空则将_finish--
即可。
//尾删数据
void pop_back()
{assert(!empty()); //容器为空则断言_finish--; //_finish指针前移
}
insert
insert函数可以在所给迭代器pos位置插入数据,在插入数据前先判断是否需要增容,然后将pos位置及其之后的数据统一向后挪动一位,以留出pos位置进行插入,最后将数据插入到pos位置即可。
iterator insert(iterator pos, const T& val)
{assert(pos >= _start);assert(pos < _finish);if (_finish == _endofstorage){size_t len = pos - _start;//记录pos与_start之间的间隔size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);// 扩容会导致pos迭代器失效,需要更新处理一下pos = _start + len;}// 挪动数据iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = val;++_finish;return pos;
}
注意: 若需要增容,则需要在增容前记录pos与_start之间的间隔,然后通过该间隔确定在增容后的容器当中pos的指向,否则pos还指向原来被释放的空间。
erase
erase函数可以删除所给迭代器pos位置的数据,在删除数据前需要判断容器是否为空以及pos位置是否在区间内,若为空则需做断言处理,删除数据时直接将pos位置之后的数据统一向前挪动一位,将pos位置的数据覆盖即可。
iterator erase(iterator pos)
{assert(!empty()); assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it < _finish){*(it- 1) = *(it);++it;}--_finish;//数据个数减少一个,_finish前移return pos;
}
swap
swap函数用于交换两个容器的数据,我们可以直接调用库当中的swap函数将两个容器当中的各个成员变量进行交换即可。
void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);
}
注意: 在此处调用库当中的swap需要在swap之前加上“::”(作用域限定符),告诉编译器去指定库中寻找swap函数,否则编译器会认为你调用的就是你正在实现的swap函数(就近原则)。
总结
模拟实现vector整体代码
namespace wyt
{template<class T>class vector{public: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;}T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}//构造vector():_start(nullptr), _finish(nullptr), _endofstorage(nullptr){}// v2(v1)/*vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){reserve(v.capacity());for (const auto& e : v){push_back(e);}}*///vector<int> v1(10, 1);//vector<char> v1(10, 'A');//构造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);}}//构造vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){reserve(n);for (size_t 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){vector<T> tmp(v.begin(), v.end());swap(tmp);}//传统写法//vector(const vector<T>& v)// :_start(nullptr)// ,_finish(nullptr)// ,_endofstorage(nullptr)//{// //开辟一块和容器v大小相同的空间// _start = new T[v.capcity()];// for (size_t i = 0; i < v.size(); ++i)// {// _start[i] = v[i];// }// _finish = _start + v.size(); //容器有效数据的尾// _endofstorage = _start + v.capacity(); //整个容器的尾//}//赋值运算符重载// v1 = v2// v1 = v1; // 极少数情况,能保证正确性,所以这里就这样写没什么问题vector<T>& operator=(vector<T> v){swap(v);return *this;}//传统写法//vector<T>& operator=(const vector<T>& v)//{// if (this != &v) //防止自己给自己赋值// {// delete[] _start; //释放原来的空间// _start = new T[v.capacity()]; //开辟一块和容器v大小相同的空间// for (size_t i = 0; i < v.size(); i++) //将容器v当中的数据一个个拷贝过来// {// _start[i] = v[i];// }// _finish = _start + v.size(); //容器有效数据的尾// _endofstorage = _start + v.capacity(); //整个容器的尾// }// return *this; //支持连续赋值//}~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}void reserve(size_t n){if (n > capacity()){size_t oldSize = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T)*oldSize);//memcpy是按字节拷贝,如果T是vector<T>类型,就会发生浅拷贝for (size_t i = 0; i < oldSize; ++i){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = tmp + oldSize;_endofstorage = _start + n;}}void resize(size_t n, T val = T()){if (n > capacity()){reserve(n);}if (n > size()){//reserve(n);while (_finish < _start + n){*_finish = val;++_finish;}}else{_finish = _start + n;}}bool empty() const{return _finish == _start;}size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}void push_back(const T& x){if (_finish == _endofstorage){size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);}*_finish = x;++_finish;}void pop_back(){assert(!empty());--_finish;}// 迭代器失效 : 扩容引起,野指针问题iterator insert(iterator pos, const T& val){assert(pos >= _start);assert(pos < _finish);if (_finish == _endofstorage){size_t len = pos - _start;size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);// 扩容会导致pos迭代器失效,需要更新处理一下pos = _start + len;}// 挪动数据iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = val;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *(begin);++begin;}--_finish;return pos;}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}void clear(){_finish = _start;}private:iterator _start;iterator _finish;iterator _endofstorage;};
}
相关文章:

【c++初阶】第九篇:vector(常用接口的使用 + 模拟实现)
文章目录vector介绍vector的使用vector的定义vector iterator(迭代器) 的使用begin和endrbegin和rendvector 空间增长问题size和capacityreserve和resize(重点)测试vector的默认扩容机制emptyvector的增删查改push_back和pop_backinsert和erasefindswapo…...

Taro React组件使用(6) —— RuiSendCode 短信验证码【倒计时】
1. 需求分析 获取验证码按钮,点击后进入倒计时环节;默认采用 120s 后才允许再次发送短信验证码;发送后不能再次点击发送按钮,点击也不执行发送逻辑;最好将发送短信的业务逻辑请求接口写在组件中,封装为公用组件,可以多处使用。2. 实现效果 2.1 验证码发送前 2.2 验证码…...

把ChatGPT接入我的个人网站
效果图 详细内容和使用说明可以查看我的个人网站文章 把ChatGPT接入我的个人网站 献给有外网服务器的小伙伴 如果你本人已经有一台外网的服务器,并且页拥有一个OpenAI API Key,那么下面就可以参照我的教程来搭建一个自己的ChatGPT。 需要的环境 Cento…...
关于数字游民是未来年轻人工作趋势的一种思考
Q:我觉得未来,数字游民会是中国工作的一种主流方式,因为实体行业受到严重冲击,科技的发展是推导支持这样的远程工作形式,而且未来人的时间是越来越离散化、碎片化、原子化的,以订单交付的形式,P2P的形式会是…...
2022年 合肥市经开区信息学竞赛区赛 初中组
2022年 合肥市经开区信息学竞赛区赛 初中组T1.普通排序 题目描述 牛牛是一位编程爱好者,今天第一次参加初中组比赛,看到第一题,不要紧张,来一个简单的排序题做一做,牛牛学过了很多排序,一直想练个手,这回机会来了,给牛牛N个数(n<=100),每个数都在(0 ~ 1000)之间…...

【工作小札】自定义classloader实现热加载jar
文章目录楔子第一步:添加maven依赖第二步:创建jar包路径构造类第三步:定义需要被加载的jar的目录结构第四步:创建自定义类加载器1 继承ClassLoader并实现Closeable接口2 标记该加载器支持并行类加载机制3 私有化构造方法ÿ…...

spring—AOP
系列文章目录 Spring中AOP技术的学习 文章目录系列文章目录前言一、AOP核心概念二、AOP入门案例1.AOP入门案例思路分析2.AOP入门案例实现三、AOP工作流程四、AOP切入点表达式五、AOP通知类型六、案例:测量业务层接口万次执行效率1.项目结构2.实现类七、AOP获取通知…...
自己曾经的C++笔记【在c盘爆满的时候找到的回忆】
文章目录**C与C的区别** (二)类和对象构造函数和析构函数C特殊成员C友元C类的继承C虚函数和多态C模板C可变参模板CSTL容器篇C迭代器C仿函数C函数适配器CSTL算法C智能指针C类型推断CIO流C正则表达式具有特殊意义的元字符量词元字符校验数字的表达式校验字符的表达式特…...

Nginx 实战-负载均衡
一、负载均衡今天学习一下Nginx的负载均衡。由于传统软件建构的局限性,加上一台服务器处理能里的有限性,在如今高并发、业务复杂的场景下很难达到咱们的要求。但是若将很多台这样的服务器通过某种方式组成一个整体,并且将所有的请求平均的分配…...

本周大新闻|128GB版Quest 2再降价,Mojo Vision完成“新A轮”融资
本周XR大新闻,AR方面,DigiLens推出SRG表面浮雕光栅衍射光波导;索尼成立Sony Research;NuEyes推出牙医场景AR眼镜NuLoupes;苹果EMG手环、AR/VR眼球追踪专利公布。 VR方面,128GB版Quest 2降至349美元&#x…...
【论文阅读】如何给模型加入先验知识
如何给模型加入先验知识 1. 基于pretain模型给模型加入先验 把预训练模型的参数导入模型中,这些预训练模型在另一个任务中已经p retrain好了模型的weight,往往具备了一些基本图片的能力 2. 基于输入给模型加入先验 比如说鸟类的头部是一个重要的区分部分&#x…...
arm系列交叉编译器各版本区别
目录交叉编译器命名规则具体编译器举例crosstool-ng交叉编译工具样本arm交叉编译器举例几个概念ABI与EABIgnueabi与gnueabihf参考交叉编译器命名规则 交叉编译器的命名规则:arch [-vendor] [-os] [-(gnu)eabi] [-language] arch - 体系架构, 如arm&…...
随笔记录工作日志
工作中遇到的问题随笔记录 1、将map集合中的key/value数据按照一定的需求过滤出来,并将过滤出来的map的key值存到list集合中 首先想到的是stream流,但是我对stream流的用法基本不熟,记不住方法,如果坚持用stream流去实现这个需求…...
LinkedHashMap源码分析以及LRU的应用
LinkedHashMap源码分析以及LRU的应用 LinkedHashMap简介 LinkedHashMap我们都知道是在HashMap的基础上,保证了元素添加时的顺序;除此之外,它还支持LRU可以当做缓存中心使用 源码分析目的 分析保持元素有序性是如何实现的 LRU是如何实现的…...
【每日一题Day166】LC1053交换一次的先前排列 | 贪心
交换一次的先前排列【LC1053】 给你一个正整数数组 arr(可能存在重复的元素),请你返回可在 一次交换(交换两数字 arr[i] 和 arr[j] 的位置)后得到的、按字典序排列小于 arr 的最大排列。 如果无法这么操作,…...
Canal增量数据订阅和消费——原理详解
文章目录 简介工作原理MySQL主备复制原理canal 工作原理Canal-HA机制应用场景同步缓存 Redis /全文搜索 ES下发任务数据异构简介 canal 翻译为管道,主要用途是基于 MySQL 数据库的增量日志 Binlog 解析,提供增量数据订阅和消费。 早期阿里巴巴因为杭州和美国双机房部署,存…...
为什么要使用线程池
Java线程的创建非常昂贵,需要JVM和OS(操作系统)配合完成大量的工作: (1)必须为线程堆栈分配和初始化大量内存块,其中包含至少1MB的栈内存。 (2)需要进行系统调用,以便在OS(操作系统)…...

在云服务部署前后端以及上传数据库
1.上传数据库(sql文件) 首先建立一个目录,用于存放要部署的sql文件,然后在此目录中进入mysql 进入后建立一个数据库,create database 数据库名 完成后,通过select * from 表名可以查到数据说明导入成功。 2.部署Maven后端 将Ma…...
Onedrive for Business迁移方案 | 分享一
文章目录 前言 一、Onedrive for Business迁移方案应用范围? 1.准备目标平台 2.导出源平台数据 <...
pt01数据类型、语句选择
python01 pycharm常用快捷键 (1) 移动到本行开头:home键 (2) 移动到本行末尾:end键盘 (3) 注释代码:ctrl / (4) 复制行:ctrl d #光标放行上 (5) 删除行:shift delete (6) 选择列:shift alt 鼠标左键…...

微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...

2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...

如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...

短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.
ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #:…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...