模拟vector
一、vector---模拟动态数组
#include
1、vector的理解
封装了动态数组的顺序容器，可以简单的认为，vector是一个能够存放任意类型的动态数组，也称为向量
2、vector的特性
1.顺序序列，有序群集，逻辑位置和物理位置连续
2.支持随机存取
3.在末端添加或删除元素方便，性能好
4.头部或者中部插入元素或删除元素需要移位，性能差
5.可以扩容，但是会导致内存重新分配
二、vector里的基本函数
1、构造与析构
1;
vector();//创建一个空vector
2;
vector(int size);//创建一个vector，元素个数为size
3;
vector(int size,const T&t);//创建一个vector，元素个数为size，且值均为t
4;
vector(const vector&other);//复制构造函数
5;
vector(begin,end);//复制[begin,end]区间内另一个数组的元素到vector中
6;
~vector();//删除所有元素，释放内存
2、非变动性函数
1;
int size()const;//返回向量中元素的个数
2;
bool empty()const;//判断向量是否为空，若为空，则向量中无元素
3;
int capaicity()const;//返回当前向量所能容纳的最大元素值,capacity--容量
4;
int max_size()const;//返回最大可允许的vector元素数量值
5;
int capaicity()const;//返会容器的大小
3、赋值操作
1;
void swap(vector&);//交换两个同类型向量的数据
2;
void assign(int n,const T&x=T());//清除容器中的元素，然后n个元素赋值为x
3;
void assign(const_iterator first,const_iterator last);//向量中[fist,last]中元素设置为当前向量元素
4、元素存取
1;
reference at(int pos);//返回pos位置元素的引用，reference--引用
2;
operator[idx];//返回索引idx所标示的元素，不进行范围检查
3;
reference front();//返回首元素的引用
4;
reference back();//返回尾元素的引用
5、迭代器相关
1;
iterator begin();//返回向量头指针，指向第一个元素
2;
iterator end();//返回向量尾指针，指向向量最后一个元素的下一个位置
3;
reverse_iterator rbegin();//反向迭代器，指向最后一个元素
4;
reverse_iterator rend();//反向迭代器，指向第一个元素之前的位置
6、插入和删除
1;
void push_back(const T&x);//向量尾部增加一个元素x
2;
iterator insert(iterator it,const T&x);//在迭代器指向位置处插入元素x
3;
iterator insert(iterator it，int n,const T&x);//在迭代器指向位置处插入n个元素，值为x
iterator insert(iterator it,const_iterator first,const_iterator last);//容器中迭代器指向位置插入另一个相同类型向量的[first,last]间的数据
5;
iterator erase(iterator it);//删除向量中迭代器指向元素，erase-擦去
6;
iterator erase(iterator first,iterator last);//删除容器中[first,last]中的元素
7;
void pop_back();//删除向量中最后一个元素
8;
void clear();//清空向量中的所有元素
9;
void resize(int num);//将元素数量改为num，对空间进行重分配
10;
void resize(int num,T elem);//将元素数量改为num，如果size()变大了。多出来的新元素都用elem来赋值
void reserve(int n);//修改容器的大小
//resize既修改capacity的大小，也修改size的大小
//reserve只修改capacity的大小
7、实际使用
vector<double> v1(10);//调用构造函数
vector<int> v;//动态数组的容器
for (int i = 0; i < 10; i++)
{
v.push_back(i + 1);//尾部插入元素
}
printf("%d
", v[5]);//operator[idx]返回idx所标示的元素，不进行范围检查
v.pop_back();//尾部弹出容器
vector<int>::iterator vit;//定义一个迭代器
vit = v.begin() + 3;//begin()返回的是指向第一个元素的指针，再向后面移动三位，移动到容器下标为3的位置
v.insert(vit, 123);//从迭代器位置进行插入
vit=v.begin();//插入数据后，导致内存重分配，内存地址改变，必须重新让迭代器指向新的容器
vit=vit+5;//vit（迭代器）指向了容器下标为6的元素
v.erase(vit);//iterator erase(iterator it);//删除向量中迭代器指向元素，erase-擦去
//begin函数返回容器中第一个元素的位置（返回迭代器）
//end函数返回容器中最后一个元素的下一个位置（返回迭代器）
for (vit = v.begin(); vit != v.end(); vit++)
{
printf("%d
", *vit);
}
8、二维数组的操作
int row = 5, col = 6;//5行，6列
vector<vector<int>>myvector(row);//定义二维动态数组大小为row行
for (size_t i = 0; i < myvector.size(); i++)//动态二维数组为row行col列，值全为0
{
myvector[i].resize(col);//表示调整容器的大小为col，扩容后的每个元素的值为element，默认为0，就是给每一行指定大小为col
//void resize(int n);//将元素数量改为num
//int size()const;//返回向量中元素的个数
}
for (size_t i = 0; i < myvector.size(); i++)//输出动态二维数组
{
for (size_t j = 0; j < myvector[i].size(); j++)
{
myvector[i][j] = i * 10 + j;
cout << myvector[i][j] << " ";
}
cout << endl;
}
9、sort函数
/*
algorithm库的sort() 排序函数
首先，sort不会用到冒泡排序，时间复杂度过高导致性能太差。SGI STL版本的sort在数据量很大时采用Quick Sort进行分段递归排序。如果分段之后的数据量小于某个门槛值，会改用Insertion Sort这种在数据量很小时性能很好的排序算法。
使用方法：Sort(start,end,排序方法)
Sort函数有三个参数：
（1）第一个是要排序的数组的起始地址。
（2）第二个是结束的地址（最后一位要排序的地址）
（3）第三个参数是排序的方法，可以是从大到小也可是从小到大，还可以不写第三个参数，此时默认的排序方法是从小到大排序。
想要实现从大到小的排序，可以自己写一个比较函数作为sort的第三个参数
*/
三、模拟vector
//#pragma once
#ifndef __MYVECTOR_H__
#define __MYVECTOR_H__
#include<assert.h>
template<class T>
class CMyVector
{
T* pbuff;
size_t len;
size_t maxsize;
public:
struct MyIterator//迭代器
{
T* pIt;//指向模板这种类型的数据的指针
MyIterator& operator=(MyIterator const&srcIt)
{
pIt = srcIt.pIt;//迭代器的赋值操作
return *this;
}
bool operator!=(MyIterator const&srcIt)
{
return pIt != srcIt.pIt;
}
MyIterator&operator++()//++a
{
pIt++;
return *this;
}
MyIterator operator++(int)//a++
{
MyIterator tempIt = *this;
pIt++;
return tempIt;
}
T operator*()
{
return *pIt;
}
MyIterator operator+(int n)//指针的偏移
{
MyIterator tempIt = *this;
tempIt.pIt += n;
return tempIt;
}
int operator-(MyIterator const&srcIt)//指针相减
{
return pIt - srcIt.pIt;
}
};
public:
MyIterator begin()
{
MyIterator tempIt;
tempIt.pIt = pbuff;//让迭代器里的指针指向动态数组
return tempIt;
}
MyIterator end()
{
MyIterator tempIt;
tempIt.pIt = pbuff + len;
return tempIt;
}
MyIterator insert(MyIterator const &pos, T const &elem)//在迭代器指向位置处插入元素x
{
int index = (int)(pos.pIt - pbuff);//把迭代器位置转为当前从下标0的偏移，防止迭代器失效
if (len >= maxsize)
{
maxsize = maxsize + ((maxsize >> 1) > 1 ? maxsize >> 1 : 1);
T* temp = new T[maxsize];
for (size_t i = 0; i < len; i++)
{
temp[i] = pbuff[i];
}
if (pbuff)
delete[]pbuff;
pbuff = temp;
}
for (int i = (int)len; i > index; i--)
{
pbuff[i] = pbuff[i - 1];
}
pbuff[index] = elem;
len++;
MyIterator tempIt;
tempIt.pIt = pbuff + index;
return tempIt;//返回的是当前插入元素的位置
}
MyIterator insert(MyIterator const &pos, int n, T const &elem)
{
//MyIterator tempPit = pos;
//for (int i = 0; i < n; i++)
//{
// tempPit = insert(tempPit, elem);//函数重用,效率太低了
//}
//return tempPit;
int index = pos.pIt - pbuff;
if (len + n > maxsize)
{
maxsize = maxsize + ((maxsize >> 1) > 1 ? maxsize >> 1 : 1);
T* temp = new T[maxsize];
for (size_t i = 0; i < len; i++)
{
temp[i] = pbuff[i];
}
if (pbuff)
delete[]pbuff;
pbuff = temp;
}
for (int i = (int)len + n-1; i > index; i--)
{
pbuff[i] = pbuff[i - n];
}
for (int i = 0; i < n; i++)
{
pbuff[index + i] = elem;
}
len += n;
MyIterator tempIt;
tempIt.pIt = pbuff + index;
return tempIt;
}
MyIterator insert(MyIterator const&pos, MyIterator const &first, MyIterator const &second)
{
MyIterator tempPit = pos;
int n = second - first;//两个指针的间隔距离
for (int i = 0; i < n; i++)
{
tempPit = insert(tempPit, *(first + i));
}
return tempPit;
}
MyIterator erase(MyIterator const &pos)//删除操作
{
int index = pos.pIt - pbuff;//找到删除位置
for (size_t i = index; i < len - 1; i++)
{
pbuff[i] = pbuff[i + 1];
}
len--;//删除操作
MyIterator tempPit;
tempPit.pIt = pbuff + index;//迭代器指向删除位置
return tempPit;
}
MyIterator erase(MyIterator const&first, MyIterator const &second)
{
int n = second.pIt - first.pIt;
MyIterator tempPit = first;
for (int i = 0; i < n; i++)
{
tempPit = erase(tempPit);
}
return tempPit;
}
public://构造析构
CMyVector();
CMyVector(int n);//带参构造，n表示动态数组的大小
CMyVector(int n, T elem);//带参构造，创建一个vector，元素个数n，大小均为elem
CMyVector(CMyVector const&other);//拷贝构造，就是将一个vector拷贝（复制）到一个新的vector中
~CMyVector();
public://这些都是非变动性函数
size_t size() const;//计算动态数组中有多少个元素
size_t capacity() const;//计算动态数组的最大容量
bool empty() const;//判断动态数组元素是否为空
//运算符重载
bool operator==(CMyVector const &srcVector) const;//比较两个容器里的元素是否相等，元素个数是否相同,相等返回true
bool operator!=(CMyVector const&srcVector) const;//不相等返回true
bool operator>(CMyVector const &srcVector) const;
bool operator>=(CMyVector const&srcVector) const;
bool operator<(CMyVector const &srcVector) const;
bool operator<=(CMyVector const &srcVector) const;
public://变动性函数
void swap(CMyVector&v);//交换两个容器的元素
void assign(int n, const T&x);////清除容器中的元素，然后n个元素赋值为x
void clear();
public://元素的存取
T at(int index);//唯一一个要抛异常的函数，根据索引index，查找容器中的元素
T operator[](int index);//根据索引index，返回容器中的值
T front();//获取容器的第一个元素
T back();//获取容器的最后一个元素
void push_back(T const &elem);//尾插法
void pop_back();//删除最后一个元素
public:
void resize(int num);//将元素数量改为num，对空间进行重分配
void resize(int num, T const &elem);//将元素数量改为num，如果size()变大了。多出来的新元素都用elem来赋值，这种函数基本上都是成对的出现
void reserve(int n);//修改容器的大小,只有当n>maxsize的时候才会修改
};
#endif//只执行一次
template<class T>
CMyVector<T>::CMyVector()
{
pbuff = nullptr;
len = maxsize = 0;
}
template<class T>
CMyVector<T>::CMyVector(int n)
{
if (n <= 0)//这里没有抛异常，而系统的会报错
{
pbuff = nullptr;
maxsize = len = 0;
}
else
{
len = maxsize = n;
pbuff = new T[maxsize];//这里可以是使用T类型的默认构造函数去构造T
/*for (int i = 0; i < len; i++)
{
pbuff[i] = 0;//这个操作是不行的，因为不知道T的类型
}*/
//可以使用memset
memset(pbuff, 0, sizeof(T)*len);
}
}
template<class T>
CMyVector<T>::CMyVector(int n, T elem)
{
if (n <= 0)//这里没有抛异常，而系统的会报错
{
pbuff = nullptr;
maxsize = len = 0;
}
else
{
len = maxsize = n;
pbuff = new T[maxsize];
for (int i = 0; i < len; i++)
{
pbuff[i] = elem;//让数组中的每一个元素都等于elem
}
}
}
template<class T>
CMyVector<T>::CMyVector(CMyVector const & other)
{
len = other.len;
maxsize = other.maxsize;//先让数组大小，元素个数等于other
pbuff = nullptr;
if (maxsize > 0)//证明other里面一定有堆区内存
{
pbuff = new T[maxsize];//这个是给新的vector申请的内存空间
for (size_t i= 0; i < len; i++)
{
pbuff[i] = other.pbuff[i];//将旧的vector中的元素数据拷贝到新的vector中去
}
}
}
template<class T>
CMyVector<T>::~CMyVector()
{
clear();
}
template<class T>
size_t CMyVector<T>::size() const
{
return len;
}
template<class T>
size_t CMyVector<T>::capacity() const
{
return maxsize;
}
template<class T>
bool CMyVector<T>::empty() const
{
//return pbuff == nullptr;
return len = 0;
//有两种可能，一种是：pbuff为空，容器为null。一种是：pbuff不为空，len=0,就是有内存，但是没有元素存在
}
template<class T>
bool CMyVector<T>::operator==(CMyVector const & srcVector) const
{
//strcpm
if (this == &srcVector)//这个是自己和自己比较
return true;
if (len != srcVector.len)//两个容器里的元素个数不相等的话，就返回false
return false;
for (size_t i = 0; i < len; i++)
{
if (pbuff[i] != srcVector.pbuff[i])
{
return false;
}
}
return true;//把两个容器里的元素比较完了，都是相等的，就返回true
}
template<class T>
bool CMyVector<T>::operator!=(CMyVector const & srcVector) const
{
return !(*this == srcVector);//调用了上面的等号重载
}
template<class T>
bool CMyVector<T>::operator>(CMyVector const & srcVector) const
{
size_t minlen = (len < srcVector.len) ? len : srcVector.len;//先出二者中较小的len
for (size_t i = 0; i < len; i++)
{
if (pbuff[i] > srcVector.pbuff[i])
return true;
if (pbuff[i] < srcVector.pbuff[i])
return false;
}
//如果循环完了没有结果，那么就还有三种情况
//1，两个容器相等。2，this.len>srcVector.len。3，this.len<srcVector.len
if (len == minlen)//这一步表示两种情况，两个容器相等返回false，还有this.len<srcVector.len也要返回false
return false;
return true;//this.len>srcVector.len返回true
}
template<class T>
bool CMyVector<T>::operator>=(CMyVector const & srcVector) const
{
return (*this > srcVector || *this == srcVector);
}
template<class T>
bool CMyVector<T>::operator<(CMyVector const & srcVector) const
{
return !(*this >= srcVector);
}
template<class T>
bool CMyVector<T>::operator<=(CMyVector const & srcVector) const
{
return (*this < srcVector || *this == srcVector);
}
template<class T>
T CMyVector<T>::at(int index)
{
if (index < 0 || index >= len)
{
throw "out_of_range";
}
return pbuff[index];
}
template<class T>
T CMyVector<T>::operator[](int index)
{
return pbuff[index];
}
template<class T>
T CMyVector<T>::front()
{
return pbuff[0];
}
template<class T>
T CMyVector<T>::back()
{
return pbuff[len - 1];
}
template<class T>
void CMyVector<T>::push_back(T const & elem)
{
if (len >= maxsize)
{
maxsize = maxsize + ((maxsize >> 1) > 1 ? maxsize >> 1 : 1);
T* temp = new T[maxsize];
for (size_t i = 0; i < len; i++)
{
temp[i] = pbuff[i];
}
if (pbuff)
delete[]pbuff;
pbuff = temp;
}
pbuff[len++] = elem;
}
template<class T>
void CMyVector<T>::pop_back()
{
len--;
}
template<class T>
void CMyVector<T>::resize(int num)
{
if (num < 0)
assert(NULL);
if (num > maxsize)
{
maxsize = num;
T* temp = new T[maxsize];
for (size_t i = 0; i < len; i++)
{
temp[i] = pbuff[i];
}
if (pbuff)
delete[]pbuff;
pbuff = temp;
}
//上面是只给len个元素赋了值，num-len个元素是用T的默认类型去构造的值
len = num;
}
template<class T>
void CMyVector<T>::resize(int num, T const & elem)
{
if (num < 0)
assert(NULL);
if (num > maxsize)
{
maxsize = num;
T* temp = new T[maxsize];
for (size_t i = 0; i < len; i++)
{
temp[i] = pbuff[i];
}
if (pbuff)
delete[]pbuff;
pbuff = temp;
}
if (num > len)
{
for (size_t i = len; i < num; i++)
pbuff[i] = elem;
}
len = num;
}
template<class T>
void CMyVector<T>::reserve(int n)
{
if (n > maxsize)
{
maxsize = n;
T* temp = new T[maxsize];
for (size_t i = 0; i < len; i++)
{
temp[i] = pbuff[i];
}
if (pbuff)
delete[]pbuff;
pbuff = temp;
}
}
template<class T>
void CMyVector<T>::swap(CMyVector & v)
{
T* tempbuff = pbuff;
size_t templen = len;
size_t tempmaxsize = maxsize;
pbuff = v.pbuff;
len = v.len;
maxsize = v.maxsize;
v.pbuff = tempbuff;
v.len = templen;
v.maxsize = tempmaxsize;
}
template<class T>
void CMyVector<T>::assign(int n, const T & x)
{
clear();
len = maxsize = n;
if (maxsize > 0)
{
pbuff = new T[maxsize];
for (size_t i = 0; i < len; i++)
{
pbuff[i] = x;
}
}
}
template<class T>
void CMyVector<T>::clear()
{
if (pbuff)
delete[]pbuff;
pbuff = nullptr;
maxsize = len = 0;
}