C++学习之第二十一天-vector容器底层实现以及类模板实现快排、堆排
1.Vector容器底层实现1.空间的申请和释放：allocate和deallocate//空间的申请,申请的是原始的，未初始化的空间pointer allocate( size_type n, const void * hint = 0 );T* allocate( std::size_t n, const void * hint);T* allocate( std::size_t n );//
·
1.Vector容器底层实现
1.空间的申请和释放：allocate和deallocate
//空间的申请,申请的是原始的，未初始化的空间
pointer allocate( size_type n, const void * hint = 0 );
T* allocate( std::size_t n, const void * hint);
T* allocate( std::size_t n );
//空间的释放
void deallocate( T* p, std::size_t n );2.对象的销毁和释放：construct 和 destroy
//对象的构建，在指定的未初始化的空间上构建对象，使用的是定位new表达式
void construct( pointer p, const_reference val );
//对象的销毁
void destroy( pointer p )3.vector容器中有三个指针：
T *_start;//指向数组中的第一个元素
T *_finish;//指向最后一个实际元素之后的那个元素
T *_end_of_storage;//指向数组本身之后的位置
#include <iostream>
#include <memory>
using std::cout;
using std::endl;
template <class T>
class Vector
{
public:
using iterator = T *;//迭代器本身是一个广义的指针
Vector()//构造函数
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{}
~Vector();
void push_back(const T &t);
void pop_back();
iterator begin()//用于打印
{
return _start;
}
iterator end()
{
return _finish;
}
int size()const
{
return _finish-_start;
}
int capacity()const
{
return _end_of_storage - _start;
}
private:
void reallocator();//重新分配内存,动态扩容要用的
private:
static std::allocator<T> _alloc;//静态成员声明
T *_start;//指向数组中的第一个元素
T *_finish;//指向最后一个实际元素之后的那个元素
T *_end_of_storage;//指向数组本身之后的位置
};
//静态成员变量类外定义
template <class T>
std::allocator<T> Vector<T>::_alloc;
template<class T>
Vector<T>::~Vector()//析构函数：先释放对象destroy，再销毁空间deallocate
{
//先销毁对象，再释放空间
if(_start)
{
while(_finish !=_start)
{
_alloc.destroy(--_finish);
}
_alloc.deallocate(_start,capacity());
}
}
template <class T>
void Vector<T>::reallocator()//自己实现的扩容
{
int oldCapacity = capacity();
int newCapacity = 2 * oldCapacity > 0? 2*oldCapacity:1;
T *ptmp = _alloc.allocate(newCapacity);//申请空间
//考虑边界条件
if(_start)
{
//std::copy(_start,_finish,ptmp);//拷贝老空间的数据到新空间
std::uninitialized_copy(_start,_finish,ptmp);//ptmp上没有对象,所以使用未初始化的copy算法
while(_finish!=_start)
{
//考虑边界条件
_alloc.destroy(--_finish);//释放老空间中的对象
}//执行完后，_start和_finish所执行的空间的对象都被销毁
_alloc.deallocate(_start,oldCapacity);//释放老空间
}
//重新置位
_start = ptmp;
_finish = _start+oldCapacity;
_end_of_storage = _start + newCapacity;
}
template<class T>
void Vector<T>::push_back(const T &t)//
{
if(size() == capacity())//
{
reallocator();//vector满了，进行扩容
}
if(size()<capacity())
{
_alloc.construct(_finish++,t);//对象的构建
}
}
template<class T>
void Vector<T>:: pop_back()
{
//pop_back()，把空间里的对象销毁就行了,不用管空间内存
if(size()>0)
{
_alloc.destroy(--_finish);//对象的销毁
}
}
template <typename Container>
void display(const Container &c)
{
cout<<"c.size()="<<c.size()<<endl;
cout<<"c.capacity()="<<c.capacity()<<endl;
}
void test01()
{
Vector<int> number;
display(number);
number.push_back(1);
number.push_back(3);
number.push_back(5);
number.push_back(7);
number.push_back(9);
display(number);
for(auto &elem: number)
{
cout<<elem<<" ";
}
cout<<endl;
}
int main()
{
test01();
return 0;
}
2.类模板实现堆排序
#include <iostream>
#include <math.h>
#include <vector>
#include <ostream>
using std::cout;
using std::cin;
using std::endl;
using std::vector;
template <typename T>
void swap(T &lhs, T &rhs)
{
auto temp = lhs;
lhs = rhs;
rhs = temp;
}
template <typename T, typename Compare=std::less<T>>
class HeapSort
{
public:
HeapSort(T *arr, size_t size, Compare);//构造函数
void heapAdjust(size_t,size_t,Compare &);//自顶向下进行调整大根堆
void sort(Compare&);//排序接口
void print();
private:
vector<T> _vec;
};
template <typename T, typename Compare>
void HeapSort<T,Compare>::heapAdjust(size_t adjustPos, size_t arrlen, Compare &com)
{
//把某个结点下的树,调整为大根堆
size_t dad = adjustPos;//
size_t son = 2*adjustPos + 1;//左孩子
while(son < arrlen)
{
if(son + 1 <arrlen &&com(_vec[son], _vec[son+1]))//右孩子存在且节点值比左孩子大
{
++son;//son指向右孩子
}
//父亲结点小于孩子结点
if(com(_vec[dad],_vec[son]))//_vec[dad] < _vec[son]
{
swap(_vec[dad],_vec[son]);//互换
dad = son;
son = 2*dad+1;
}
else
{
break;
}
}
}
template <typename T,typename Compare>
HeapSort<T,Compare>::HeapSort(T *arr, size_t size,Compare com)
{
for(int idx = 0;idx<size; ++idx)//1.把数组数据存入vector
{
_vec.push_back(arr[idx]);
}
//2.建堆,对_vec中的元素建立大根堆，从第一个非叶子结点开始调整，一直调整到根节点_vec[0]
for(int i = size/2 - 1; i >=0 ; i--)
{
heapAdjust(i, size,com);
}
//3.调整为大根堆后,arr[0]是数组中最大的值
swap(arr[0], arr[size-1]);//交换
sort(com);//排序
}
template <typename T,typename Compare>
void HeapSort<T,Compare>::sort(Compare &com)//排序
{
size_t size = _vec.size();
for(size_t i = size; i > 1;i--)
{
heapAdjust(0,i,com);//每次与最后一个元素对调完，重新调节根节点，调整的数组长度每次减1
swap(_vec[0],_vec[i-1]);//把大的元素放到正确的位置，再调整整棵树为大根堆
}
}
template <typename T, typename Compare>
void HeapSort<T,Compare>::print()
{
for(auto &elem : _vec)
{
cout<< elem << " ";
}
cout << endl;
}
void test01()
{
int arr[10] = {1, 2, 6, 3, 4, 8, 5, 7, 9, 10};
HeapSort<int> hs(arr, 10, std::less<int>());
hs.print();
cout << endl;
}
int main()
{
test01();
return 0;
}
3.类模板实现快速排序
//类模板实现快速排序
#include <iostream>
#include <math.h>
#include <vector>
#include <ostream>
using std::cout;
using std::cin;
using std::endl;
using std::vector;
template<typename T>
void swap(T &lhs,T &rhs)
{
auto temp= lhs;
lhs = rhs;
rhs = temp;
}
template <typename T, typename Compare=std::greater<T>>
class MyQsort
{
public:
MyQsort(T *arr,size_t size, Compare);//构造函数：
void quick(int left,int right,Compare &);//递归处理
int partition(int left, int right, Compare &);//分堆
void print();//打印
private:
vector<T> _vec;
};
template <typename T, typename Compare>
void MyQsort<T, Compare>::print()
{
for(auto &elem: _vec)
{
cout<<elem<<" ";
}
cout<<endl;
}
template <typename T, typename Compare>//构造函数：先把数组内容push_back到容器，再调用排序接口
MyQsort<T,Compare>::MyQsort(T *arr, size_t size, Compare com)
{
for(size_t i=0; i<size;i++)
{
_vec.push_back(arr[i]);
}
quick(0,_vec.size()-1,com);//快排
}
template <typename T, typename Compare>//快速排序
void MyQsort<T, Compare>::quick(int left, int right, Compare &com)
{
int pivot;
if(left<right)
{
pivot = partition(left, right,com);
quick(left,pivot-1,com);
quick(pivot+1, right,com);
}
}
template <typename T,typename Compare>//分治
int MyQsort<T,Compare>:: partition(int left,int right,Compare &com)
{
int indexi,indexk;
for(indexi=left, indexk = left; indexi<right;indexi++)
{
if(com(_vec[indexi],_vec[right]))//以数组最右边的元素作为pivot
{
swap(_vec[indexi],_vec[indexk]);
++indexk;//indexk记录的是小于pivot的元素个数，
}
}
swap(_vec[indexk], _vec[right]);//交换后indexk左边是小于pivot的元素，右边是大于Pivot的元素
return indexk;//返回indexk
}
void test01()
{
int arr[10] = {99,88,77,12,34,10,9,8,6,76};
MyQsort<int> q(arr,10,std::greater<int>());
q.print();
}
int main()
{
test01();
return 0;
}
3.类模板实现归并排序
#include <iostream>
#include <string>
#include <time.h>
#include <math.h>
#include <vector>
#include <ostream>
#include <iterator>
#include <algorithm>
using std::copy;
using std::cout;
using std::cin;
using std::endl;
using std::vector;
using std::string;
class Person//自定义类型Person
{
friend std::ostream& operator<<(std::ostream &os,const Person &rhs);
public:
string get_age()const
{
return _age;
}
Person(string name = "", string age = "")
:_name(name),_age(age)
{
}
private:
string _name;
string _age;
};
std:: ostream& operator<<(std::ostream &os,const Person &rhs)
{
cout<<rhs._name<<" "<<rhs._age;
return os;
}
namespace std//命名空间的扩展
{
template<>
struct less<Person>//仿函数，用于自定义类型的比较
{
bool operator()(const Person &lhs, const Person &rhs)
{
return lhs.get_age()< rhs.get_age();
}
};
}
template <typename T,typename Compare = std::less<T>>
class MergeSort
{
public:
MergeSort(T *arr,size_t , Compare com);
void print();
void mergeSort(size_t left, size_t right, Compare &com);
void merge(size_t left, size_t mid, size_t right, Compare &com);
private:
vector<T> _vec;
};
template <typename T, typename Compare>
MergeSort<T,Compare>:: MergeSort(T *arr, size_t arrlen, Compare com)
{
for(int idx = 0; idx<arrlen;idx++)
{
_vec.push_back(arr[idx]);
}
mergeSort(0,arrlen-1, com);//归并排序
}
template <typename T, typename Compare>//二路归并
void MergeSort<T,Compare>::mergeSort(size_t left, size_t right, Compare &com)
{
if(left<right)
{
size_t mid = (left+right)/2;
mergeSort(left,mid,com);
mergeSort(mid+1,right,com);
merge(left,mid,right,com);//归并
}
}
template <typename T,typename Compare>
void MergeSort<T, Compare>::merge(size_t left, size_t mid, size_t right, Compare &com)
{
vector<T> temp;//临时容量
copy(_vec.begin(),_vec.end(), std::back_insert_iterator<vector<T>>(temp));
//把_vec中的内容拷贝到temp，temp用来进行遍历，在归并的过程中，重写_vec容器里面的元素，按顺序存储
int left_1 = left;
int k = left;//从左开始，作为_vec的下标，从小到大进行存储
int left_2 = mid + 1;
while(left_1 <=mid && left_2 <= right)
{
if(com(temp[left_1], temp[left_2]))
{
_vec[k++] = temp[left_1++];
}
else
{
_vec[k++] = temp[left_2++];
}
}
while(left_1 <= mid)
{
_vec[k++] = temp[left_1++];
}
while(left_2<=right)
{
_vec[k++] = temp[left_2++];
}
}
template <typename T, typename Compare>
void MergeSort<T,Compare>::print()
{
for(auto &elem:_vec)
{
cout<<elem<<" ";
}
cout<<endl;
}
void test01()
{
srand(time(NULL));
int arr[10]={0};
for(int idx=0;idx<10;idx++)
{
arr[idx] = rand()%100;
}
MergeSort<int> my_merge(arr, 10, std::less<int>());
my_merge.print();
}
void test02()
{
Person p1("孙悟空","550");
Person p2("猪八戒","666");
Person p3("沙僧","444");
Person p4("唐僧","999");
Person p5("白龙马","888");
Person arr[5] = {p1,p2,p3,p4,p5};
for(int idx=0;idx < 5;idx++)
{
cout<<arr[idx]<<endl;
}
MergeSort<Person> my_sort(arr, 5, std::less<Person>());
my_sort.print();
}
int main()
{
test01();
test02();//自定义类型排序
return 0;
}
4.按照以上三个排序的方式依次实现类模板选择排序、插入排序、计数排序。。。
2021.11.24记
C++基础(2021/10/26开始)，跟着视频已过一遍，后续继续加强学习，巩固复习，路漫漫其修远兮。
权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区
更多推荐
5
0- 0
已为社区贡献1条内容
所有评论(0)