目录
一.前言
二.vector的容量操作接口
1.size() 和 capacity()
2.扩容接口reserve
3.resize接口
三.增删数据操作接口
1.insert 和 erase
2.push_back 和 pop_back接口
四. 数据访问接口
1.获取迭代器的接口
2.下标访问操作符重载
五.变量交换函数
六.vector的默认成员函数
1.构造和析构函数
2.构造函数模板
3.拷贝构造函数和赋值运算符重载
七.测试自制vector运行leetcode题解
一.前言
vector在STL中是一个待实例化的类模板：
template <typename T>
class vector
{
}其具体的实例化方式如下：
vector a ; 储存int类型数据的对象
vector b ; 储存string类型数据的对象
vector<vector> b; 储存vector类型数据的对象
vector的迭代器和string类似,本质都是原生指针,vector主要的私有成员变量是三个typedef为指针变量的迭代器：
template
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator; private:
iterator _start; // 指向堆区数据块的起始位置
iterator _end; // 指向最后一个有效数据的后一个位置
iterator _endofstorage; // 被申请出来的内存块的末尾地址}
以vector类型为例说明一下三个成员迭代器是如何维护对象申请出来的堆区空间的：
再以vector类型为例说明一下用自定义类型实例化的vector模板，其创建出的对象在内存中的数据结构：
二.vector的容量操作接口
1.size() 和 capacity()
size_t size():其功能是返回vector对象中的有效数据个数：
size_t size() const //获取有效元素个数的接口
{
return _end - _start;
}
指针减指针能够得到两个地址之间的元素个数
size_t capacity():其功能是返回vector对象的容量大小：
size_t capacity()const //获取容器容量的接口
{
return _endofstorage - _start;}
const修饰的是指向接口调用对象的this指针
2.扩容接口reserve
void reserve(size_t n)：将容器的容量扩大到n个(只能扩容，不能缩容)，不改变其有效数据
void reserve(size_t n) //扩容接口
{
size_t precapacity = _endofstorage - _start;//计算旧的容量
size_t presize = _end - _start;
if(n>precapacity)
{
T * tem = new T[n];
if(_start) //如果原容量不为0(_start不为空指针)，则需要把原空间数据拷贝到新空间
{
for(size_t i =0;i<presize;++i)
{
tem[i]=_start[i];
}
delete[] _start; //释放旧空间(注意若_start为空，则不能释放空间)
}
_start = tem; // 注意三个迭代器都要调整
_end = _start + presize;
_endofstorage = _start + n;
}
}
注意这里的数据拷贝必须是深拷贝,因为vector存储的可以是对象数组比如string数组：
该循环中的赋值语句会自动调用string的赋值运算符重载完成深拷贝。
完成扩容对象维护的堆区内存块地址会改变，因此三个成员迭代器都要更新。
3.resize接口
void resize(size_t n, const T& val = T())：将容器的有效数据个数调整到n个(多出的有效数据赋值为val)
形参val的缺省值T()是一个T类型的匿名对象(如果用户没有传实参给val，该对象会自动调用自身默认的无参构造函数完成初始化并将默认初始值赋给val)
C++为了让自定义类型变量与内置类型保持语法上的一致，允许内置类型变量以如下的方式初始化：
匿名对象的生命周期限定在其所在的代码语句中(语句执行完就调用析构函数销毁)。
匿名对象如果被const引用所指定，其生命周期会延长到其所在的作用域中(出作用域才销毁)
void resize(size_t n, const T& val = T()) //val的缺省值取T类型的默认缺省值(T()是一个
//匿名对象，创建时会自动调用其无参构造函数)
{
size_t presize = _end - _start;
size_t precapacity = _endofstorage - _start;
if(n<=presize)
{
_end = _start + n;
return ;
}
else if(n>precapacity)
{
reserve(n); //复用扩容接口
}
for(iterator it = _end ; it!=_endofstorage; ++it)
{
*it = val; //多出的有效数据赋值为val
}
_end = _start + n;
}
三.增删数据操作接口
1.insert 和 erase
iterator insert(iterator pos , const T& val)； 在pos迭代器指向的位置插入值为val的元素
insert接口返回值的说明：
insert返回的是一个指向新插入元素的vector内置迭代器。
由于插入数据可能会导致扩容，扩容意味着对象指向了新的堆空间：
这样一来原来作为实参传入insert函数的迭代器会成为野指针(这就是容器的迭代器失效的场景之一)，所以insert返回值是为了让用户能够接收到指向新空间的迭代器来更新成为野指针的旧迭代器。
接口实现：
//插入元素的接口(在pos位置插入元素val)
iterator insert(iterator pos , const T& val)
{
assert(pos<=_end && pos >=_start);
size_t poslenth = pos - _start;
if(_end == _endofstorage)
{
size_t precapacity = _endofstorage - _start;
size_t newcapacity = (0==precapacity)? 4 : 2*precapacity;//采用常用的两倍扩容的方式
reserve(newcapacity);
pos = _start + poslenth; //扩容后迭代器失效(变为野指针)需要重置迭代器
}
for(iterator it = _end;it >pos ; --it)//挪动pos位置后的数据
{
*it= *(it-1);
}
*pos = val;
++ _end;
return pos; //返回指向新空间的迭代器}
注意扩容完后一定要更新pos迭代器：
iterator erase(iterator pos)；删除pos迭代器指向的位置的数据
erase的返回值是一个指向被删除的数据的下一个数据的迭代器：
设计该返回值也是为了让用户能够处理迭代器失效的问题(有些vector的底层实现可能会在删除数据的接口中进行缩容的操作)
接口实现：
iterator erase(iterator pos)
{
assert(pos>=_start && pos<_end);
for(iterator it = pos; it < _end ; ++it)
{
*it = *(it+1);
}
-- _end;
return pos;}
2.push_back 和 pop_back接口
push_back:尾插一个数据
pop_back:尾删一个数据
分别复用insert 和 erase即可实现：
//尾插和尾删数据的接口
void push_back(const T& val)
{
insert(_end,val);
}
void pop_back()
{
erase(_end-1);
}四. 数据访问接口
1.获取迭代器的接口
//获取迭代器的接口
iterator begin ()
{
return _start;
}
iterator end()
{
return _end;
}
const iterator begin()const
{
return _start;
}
const iterator end()const
{
return _end;
}
2.下标访问操作符重载
//数据访问接口
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}五.变量交换函数
为了使用现代STL的常用写法来实现vector的拷贝构造函数和赋值运算符重载，先准备好两个变量交换函数。
全局交换函数模板：
//交换函数模板
template <typename T1>
void myswap(T1& e1 , T1& e2)
{
T1 tem = e1;
e1 = e2;
e2 = tem;
}成员交换函数：
void swap (vector<T> & vec) //成员交换函数
{
myswap(_start,vec._start);
myswap(_end,vec._end);
myswap(_endofstorage,vec._endofstorage);
}附带说明：
如果我们想交换两个容器对象的内容，最好使用容器的成员交换函数(直接交换成员指针的指向)，因为使用全局交换函数交换两个对象会进行三次深拷贝，性能代价极大：
int main ()
{
vector<int> a(10,5);
vector<int> b(10,6);
myswap(a,b); 使用全局交换函数交换两个变量
a.swap(b); 使用成员交换函数交换两个变量
return 0;}
六.vector的默认成员函数
1.构造和析构函数
无参构造函数：
vector<T>() //无参的默认构造函数
:_start(nullptr)
,_end(nullptr)
,_endofstorage(nullptr)
{}带参构造函数vector(int n , const T& val = T())：构造一个存有n个有效数据的对象，并将每一个有效数据初始化为val.
vector<T>(int n , const T& val = T()) //带参的构造，构造有效元素个数为n的vector，并将
//各元素初始化为val
:_start(nullptr)
,_end(nullptr)
,_endofstorage(nullptr)
{
reserve(n); //复用扩容接口
for(size_t i = 0 ; i<n ;++i)
{
_start[i]= val;
++_end;
}
}析构函数：
~vector<T>()
{
if(_start)
{
delete[]_start;
}
_start = nullptr;
_end = nullptr;
_endofstorage = nullptr;
}2.构造函数模板
template<typename InputIterator>
vector<T>(InputIterator first , InputIterator last)
:_start(nullptr)
,_end(nullptr)
,_endofstorage(nullptr)
{
while(first != last)
{
push_back(*first);
++first;
}
}该构造函数功能是：用两个迭代器指向的区间中的数据来初始化对象。(所传入的迭代器可能是别的类型的容器的迭代器，比如list，map，set等容器的迭代器)
C++中允许在类模板中定义成员函数模板
3.拷贝构造函数和赋值运算符重载
通过复用构造函数模板实现拷贝构造函数：
vector<T>(const vector<T>& vec) //vector的拷贝构造
:_start(nullptr) //不初始化就会把随机值交换给tem，tem调用自身析构函
//数时程序会崩溃
,_end(nullptr)
,_endofstorage(nullptr)
{
vector<T>tem(vec.begin(),vec.end());
swap(tem);
}
通过复用拷贝构造函数实现赋值运算符重载：
vector<T>& operator= (vector<T>vec)
{
swap(vec);
return (*this);
}
七.测试自制vector运行leetcode题解
- 杨辉三角 - 力扣（Leetcode）
include "myvector.h"
using myvector :: vector;
using std :: cin;
using std :: cout;
using std :: endl;
class Solution
{
public:
vector<vector<int>> generate(int numRows)
{
vector<vector<int>> answer(numRows);
int i = 0;
int j = 0;
for (i = 0; i < numRows; i++)
{
answer[i].resize(i + 1);
answer[i][0] = 1;
answer[i][i] = 1;
}
for (i = 2; i < numRows; i++)
{
for (j = 1; j < i; j++)
{
answer[i][j] = answer[i - 1][j] + answer[i - 1][j - 1];
}
}
return answer;
}};
int main()
{
Solution a;
vector<vector<int>> b = a.generate(5);
for (size_t i = 0; i < b.size(); i++)
{
for (size_t j = 0; j < b[i].size(); j++)
{
cout << b[i][j] << ' ';
}
cout << endl;
}
cin.get();
return 0;}
模式实现代码总览：
include
include <assert.h>
namespace myvector
{
//交换函数模板
template <typename T1>
void myswap(T1& e1 , T1& e2)
{
T1 tem = e1;
e1 = e2;
e2 = tem;
}
//vector类模板
template <typename T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
void swap (vector<T> & vec) //成员交换函数
{
myswap(_start,vec._start);
myswap(_end,vec._end);
myswap(_endofstorage,vec._endofstorage);
}
//获取迭代器的接口
iterator begin ()
{
return _start;
}
iterator end()
{
return _end;
}
const iterator begin()const
{
return _start;
}
const iterator end()const
{
return _end;
}
//构造和析构接口
vector<T>() //无参的默认构造函数
:_start(nullptr)
,_end(nullptr)
,_endofstorage(nullptr)
{}
vector<T>(int n , const T& val = T()) //带参的构造，构造有效元素个数为n的vector，并
//将各元素初始化为val
:_start(nullptr)
,_end(nullptr)
,_endofstorage(nullptr)
{
reserve(n);
for(size_t i = 0 ; i<n ;++i)
{
_start[i]= val;
++_end;
}
}
template<typename InputIterator>
vector<T>(InputIterator first , InputIterator last)
:_start(nullptr)
,_end(nullptr)
,_endofstorage(nullptr)
{
while(first != last)
{
push_back(*first);
++first;
}
}
vector<T>(const vector<T>& vec) //vector的拷贝构造
:_start(nullptr) //不初始化就会把随机值交换给tem，tem调用自身析构
//函数时程序会崩溃
,_end(nullptr)
,_endofstorage(nullptr)
{
vector<T>tem(vec.begin(),vec.end());
swap(tem);
}
~vector<T>()
{
if(_start)
{
delete[]_start;
}
_start = nullptr;
_end = nullptr;
_endofstorage = nullptr;
}
//赋值运算符重载
vector<T>& operator= (vector<T>vec)
{
swap(vec);
return (*this);
}
//数据访问接口
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
//容量操作接口
void reserve(size_t n) //扩容接口
{
size_t precapacity = _endofstorage - _start;//计算旧的容量
size_t presize = _end - _start;
if(n>precapacity)
{
T * tem = new T[n];
if(_start) //如果原容量不为空，则需要把原空间
//数据拷贝到新空间
{
for(size_t i =0;i<presize;++i)
{
tem[i]=_start[i];
}
delete[] _start; //释放旧空间(注意若_start为空，则不
//能释放空间)
}
_start = tem; // 注意三个迭代器都要调整
_end = _start + presize;
_endofstorage = _start + n;
}
}
void resize(size_t n, const T& val = T())
{
size_t presize = _end - _start;
size_t precapacity = _endofstorage - _start;
if(n<=presize)
{
_end = _start + n;
return ;
}
else if(n>precapacity)
{
reserve(n); //复用扩容接口
}
for(iterator it = _end ; it!=_endofstorage; ++it)
{
*it = val;
}
_end = _start + n;
}
//插入元素的接口(在pos位置插入元素val)
iterator insert(iterator pos , const T& val)
{
assert(pos<=_end && pos >=_start);
size_t poslenth = pos - _start;
if(_end == _endofstorage)
{
size_t precapacity = _endofstorage - _start;
size_t newcapacity = (0==precapacity)? 4 : 2*precapacity;
reserve(newcapacity);
pos = _start + poslenth; //扩容后迭代器失效(变为野指针)需
//要重置迭代器
}
for(iterator it = _end;it >pos ; --it)
{
*it= *(it-1);
}
*pos = val;
++ _end;
return pos;
}
iterator erase(iterator pos)
{
assert(pos>=_start && pos<_end);
for(iterator it = pos; it < _end ; ++it)
{
*it = *(it+1);
}
-- _end;
return pos;
}
//尾插和尾删数据的接口
void push_back(const T& val)
{
insert(_end,val);
}
void pop_back()
{
erase(_end-1);
}
size_t size() const //获取有效元素个数的接口
{
return _end - _start;
}
size_t capacity()const //获取容器容量的接口
{
return _endofstorage - _start;
}
private:
iterator _start; // 指向数据块的开始
iterator _end; // 指向有效数据的尾
iterator _endofstorage; // 指向存储容量的尾
};}
