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 );
//空间的释放
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 
#include 
using std::cout;
using std::endl;

template 
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 _alloc;//静态成员声明
    T *_start;//指向数组中的第一个元素
    T *_finish;//指向最后一个实际元素之后的那个元素
    T *_end_of_storage;//指向数组本身之后的位置
};
//静态成员变量类外定义
template 
std::allocator Vector::_alloc;

template
Vector::~Vector()//析构函数：先释放对象destroy，再销毁空间deallocate
{
    //先销毁对象，再释放空间
    if(_start)
    {
        while(_finish !=_start)
        {
            _alloc.destroy(--_finish);
        }
        _alloc.deallocate(_start,capacity());
    }
}
template 
void Vector::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
void Vector::push_back(const T &t)//
{
    if(size() == capacity())//
    {
       reallocator();//vector满了，进行扩容
    }
    if(size()
void Vector:: pop_back()
{
    //pop_back()，把空间里的对象销毁就行了,不用管空间内存
    if(size()>0)
    {
        _alloc.destroy(--_finish);//对象的销毁
    }
}
template 
void display(const Container &c)
{
    cout<<"c.size()="< 
2.类模板实现堆排序
 
#include 
#include 
#include 
#include 

using std::cout;
using std::cin;
using std::endl;
using std::vector;

template 
void swap(T &lhs, T &rhs)
{
    auto temp = lhs;
    lhs = rhs;
    rhs = temp;
}
template >
class HeapSort
{
public:
    HeapSort(T *arr, size_t size, Compare);//构造函数
    void heapAdjust(size_t,size_t,Compare &);//自顶向下进行调整大根堆
    void sort(Compare&);//排序接口
    void print();

private:
    vector _vec;
};
template 
void HeapSort::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 
HeapSort::HeapSort(T *arr, size_t size,Compare com)
{
    for(int idx = 0;idx=0 ; i--)
    {
        heapAdjust(i, size,com);
    }

    //3.调整为大根堆后,arr[0]是数组中最大的值
    swap(arr[0], arr[size-1]);//交换
    sort(com);//排序
}
template 
void HeapSort::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 
void HeapSort::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 hs(arr, 10, std::less());
    hs.print();
    cout << endl;
}
int main()
{
    test01();
    return 0;
}
 
3.类模板实现快速排序
 
//类模板实现快速排序
#include 
#include 
#include 
#include 

using std::cout;
using std::cin;
using std::endl;
using std::vector;
template
void swap(T &lhs,T &rhs)
{
    auto temp= lhs;
    lhs = rhs;
    rhs = temp;
}
template >
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 _vec;
};
template 
void MyQsort::print()
{
    for(auto &elem: _vec)
    {
        cout<//构造函数：先把数组内容push_back到容器，再调用排序接口
MyQsort::MyQsort(T *arr, size_t size, Compare com)
{
    for(size_t i=0; i//快速排序
void MyQsort::quick(int left, int right, Compare &com)
{
    int pivot;
    if(left//分治
int MyQsort:: partition(int left,int right,Compare &com)
{
    int indexi,indexk;
    for(indexi=left, indexk = left; indexi q(arr,10,std::greater());
    q.print();
}
int main()
{
    test01();
    return 0;
}
 
3.类模板实现归并排序
 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
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<
struct less//仿函数，用于自定义类型的比较
{
    bool operator()(const Person &lhs, const Person &rhs)
    {
        return lhs.get_age()< rhs.get_age();
    }
};
}
template >
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 _vec;
};
template 
MergeSort:: MergeSort(T *arr, size_t arrlen, Compare com)
{
    for(int idx = 0; idx//二路归并
void MergeSort::mergeSort(size_t left, size_t right, Compare &com)
{
    if(left
void MergeSort::merge(size_t left, size_t mid, size_t right, Compare &com)
{
    vector temp;//临时容量
    copy(_vec.begin(),_vec.end(), std::back_insert_iterator>(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 
void MergeSort::print()
{
    for(auto &elem:_vec)
    {
        cout< my_merge(arr, 10, std::less());
    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< my_sort(arr, 5, std::less());
    my_sort.print();
}
int main()
{
    test01();
    test02();//自定义类型排序
    return 0;
}
 
4.按照以上三个排序的方式依次实现类模板选择排序、插入排序、计数排序。。。
 
2021.11.24记
 
 
 
C++基础(2021/10/26开始)，跟着视频已过一遍，后续继续加强学习，巩固复习，路漫漫其修远兮。