在学习邓俊辉老师的《数据结构》一书时，发现Vector数据结构内没有移动构造，移动赋值等构造函数，遂想着添加上拷贝赋值运算。
Vector部分代码
/*
* @Author: your name
* @Date: 2020-09-06 09:07:54
* @LastEditTime: 2020-09-06 09:24:20
* @LastEditors: Please set LastEditors
* @Description: In User Settings Edit
* @FilePath: \code20200906\Vector.h
*/
#ifndef VECTOR_H
#define VECTOR_H
typedef int Rank; //using Rank=int;
#define DEFAULT_CAPACITY 3 //默认的初始容量(实际应用中可设置为更大)
#include <memory>
template <typename T>
class Vector
{ //向量模板类
protected:
Rank _size; //规模
int _capacity; //容量
T* _elem; //数据区
void copyFrom(T const* A, Rank lo, Rank hi); //复制数组区间;作为一个辅助函数来使用，
//构造函数多次用到
void expand(); //空间不足时扩容
void shrink(); //装填因子过小时压缩
bool bubble(Rank lo, Rank hi); //扫描交换
void bubblesort(Rank lo, Rank hi); //气泡排序法;
Rank max(Rank lo, Rank hi); //选取最大元素
void selectionSort(Rank lo, Rank hi); //选择排序法
void merge(Rank lo, Rank hi); //归并算法
void mergesort(Rank lo, Rank hi); //归并排序
Rank partition(Rank lo, Rank hi); //轴点构造算法
void quiksort(Rank lo, Rank hi); //快速排序算法;
void heapsort(Rank lo, Rank hi); //堆排序
public:
//构造函数
//默认构造函数
//此默认构造函数我觉着不好，用下面的吧
//Vector(int c = DEFAULT_CAPACITY,int s , 0,T v = 0) //容量为c，规模为s，所有元素初始为v
//{
// //构建容量大小
// _elem = new T[_capacity = c];
// for (_size = 0; _size < s; _elem[_size++] = v);
//}//:_elem(new T[_capacity=c]),_capacity(c),_size(s)
Vector(int c = DEFAULT_CAPACITY,int s= 0, T v = 0) :_elem(new T[c]), _capacity(c), _size(s) //容量为c，规模为s，所有元素初始为v
{
//构建容量大小
for (int i = 0; i < _size; ++i)
_elem[i] = v;
}
Vector(T const* A, Rank n) { copyFrom(A, 0, n); }//数组整体复制//T const ;const T 都一样，指的是指向常对象的指针
Vector(T const* A, Rank lo, Rank hi) { copyFrom(A, lo, hi); }//区间整体复制
//拷贝构造函数
Vector(Vector<T> const& V) { copyFrom(V._elem, 0, V._size); }//向量整体复制
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
Vector(Vector<T>&& V);//移动构造函数
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
Vector& operator=(const Vector<T>&);//拷贝赋值
Vector& operator=(Vector<T>&&);//移动构造赋值
Vector(Vector<T> const& V, Rank lo, Rank hi) { copyFrom(V._elem, lo, hi); }//区间复制
//析构函数
~Vector() { delete[]_elem; }//释放内部空间，需要析构函数的也需要构造函数和拷贝赋值函数
//只读访问接口
Rank size()const { return _size; }//规模
bool empty()const { return !_size; }//自己写成了_size==0
int disordered()const;//判断向量是否已排序
Rank find(T const& e)const { return find(e, 0, _size); }//无序向量整体查找,调用下面的函数
Rank find(T const& e, Rank lo, Rank hi)const;//无序向量区间查找
Rank search(T const& e)const//有序向量整体查找
{return (0 >= _size ? -1: search(e, 0, _size)); }
Rank search(T const& e, Rank lo, Rank hi)const;//有序向量区间查找
//可写访问接口
T& operator[](Rank r)const;//重载下标运算符
T remove(Rank r);//删除秩为r的元素
int remove(Rank lo, Rank hi);//删除区间内的元素
Rank insert(Rank r, T const& e);//插入元素
Rank insert(T const& e) { return insert(_size, e); }//默认作为末尾元素插入
void sort(Rank lo, Rank hi);//对区间内排序
void sort() { sort(0, _size); }//整体排序
void unsort(Rank lo, Rank hi);//对区间置乱
void unsort() { unsort(0, _size); }//整体置乱
int deduplicate();//无序去重
int uniquify();//有序去重
//遍历
void traverse(void(*)(T&));//遍历
template<typename VST>void traverse(VST&);//遍历
};
//具体到功能的实现
template<typename T>
void Vector<T> ::copyFrom(T const* A, Rank lo, Rank hi) {//运行时间正比于O(_size)
//以数组区间A[lo,hi)为蓝本复制对象
_elem = new T[_capacity = 2 * (hi - lo)]; _size = 0;//分配空间，规模清零,2倍的空间
while (lo < hi) {
_elem[_size++] = A[lo++];//复制到_elem[0,hi-lo)
}
}
template<typename T>
Vector<T>& Vector<T>::operator =(const Vector<T>& V) {
//拷贝赋值的功能类似于析构+构造
if (_elem)delete[]_elem;
copyFrom(V._elem,0,V.size());
return *this;
}
template<typename T>
Vector<T>& Vector<T>::operator=(Vector<T>&& V) {
if (this != &V)//注意取V的地址
{
delete[]_elem;
_elem = V._elem;
_size = V._size;
_capacity = V._capacity;
V._elem = nullptr;
}
return *this;
}
#endif
测试主函数代码
/*
* @Author: your name
* @Date: 2020-09-06 09:07:12
* @LastEditTime: 2020-09-06 09:07:45
* @LastEditors: Please set LastEditors
* @Description: In User Settings Edit
* @FilePath: \code20200906\main.cpp
*/
#include"Vector.h"
#include <ctime>
#include <iostream>
int main(int argc, char** argv) {
Vector<int> v(1000000000, 1000000000, 5);
Vector<int> v1;
Vector<int> v2;
std::clock_t t_start, t_end;
t_start = std::clock();
v1 = v;
t_end = std::clock();
std::cout << "拷贝赋值运算耗时: " << double(t_end - t_start) / 1000.0 << " S" << "\n";
t_start = std::clock();
v2 = std::move(v);
t_end = std::clock();
std::cout << "移动赋值运算耗时: " << double(t_end - t_start) / 1000.0 << " S" << "\n";
return 0;
}
对比结果
运行时间结果
结论
- 移动赋值运算由于没有申请新空间，赋值等操作比拷贝赋值运算快许多；
- 但是只有在源对象不再使用等情况下才可以使用移动赋值。
