[数据结构与算法]c++复习笔记——4、指针与内存管理

new/delete与malloc/free区别

基本数据类型：int, char, short, long, double…及数组

 	int *p = new int(5);
    cout<<" p="<<p<<endl;
    delete p;//free(p);//对于基本数据类型,效果一样，数组delete []p;
    cout<<" p="<<p<<endl;

    p = nullptr;//*delete不会改变指针的值，为了避免迷途指针，delete之后指针设定为nullptr
    delete p;//nullptr不会导致迷途指针
    //    delete free对于基本数据类型，释放两次都会出错，
    //    free 不改变指针的值，delete会改变,delete之后指针指向一个特定的位置
    
    int *p1((int *)malloc(4));
    cout<<" p1="<<p1<<endl;
    *p1=4;
    cout<<" p1="<<p1<<endl;
    free(p1);
    cout<<" p1="<<p1<<endl;

自定义类型myData

class mydata{
public://c++ class 默认private，如果都不写，系统会自动分配为两个public空的构造、析构函数
    void *p;
    mydata(){//构造
        p = malloc(1024*1024*100);
        cout<<"mydata create"<<endl;
    }
    ~mydata()//析构
    {
        free(p);
        cout<<"mydata delete"<<endl;
    }
};

//mydata d1;

void test(){
    mydata t1;
    
}

int main(){
    //    test();
    //mydata *p = (mydata *)malloc(sizeof(mydata));//malloc不调用构造函数
    mydata *p = new mydata;
    //free(p);//free不调用机构函数
    delete p;
}

new/delete单个对象以及数组注意事项

*对自定义类型需要严格配对 new []/ delete []或者new/delete。

	int *p = new int[3]{1,2,3};
	cout<<p<<endl;
	delete []p;//对于基本数据类型,效果一样，数组delete []p和delete p效果一样;
	//单个堆上的对象,调用delete []p会一直调用delete; 自定义类型数组，调用delete []会根据数组个数调用相应次数的析构函数, 调用delete则只调用一次。

new分配内存，静态区\栈\堆

char str[1024] = { 0 };//内存全局静态区

int main(){
//    char str[1024] = { 0 };//栈区
//    char *str = new char[1024]{ 0 };//堆区
    int *p = new int[3]{1,2,3};//一定在堆区
    int *p1 = new (str) int[3]{1,2,3};//分配内存，指定为str开始的地址

    cin.get();
    return 1;
}

c++ new分配内存可以指定内存区域，一定程度上继承了unix系统的优良特性，Windows经常奔溃，Linux次之，Unix最为稳定，而Linux为android底层，Unix为iOS底层，这也是iOS较android更稳定的原因。这也是多数银行系统采用Unix做为服务系统的原因。
静态区\栈\堆的内存都可以覆盖重写，而唯独堆区内存可以delete重新利用。

new/delete重载

new/delete局部重载

单例的new/delete重载

int objs = 0;//全局变量用于统计
void *g_p = nullptr;//全局指针实现单列

using namespace std;

//无法被堆上创建的类
class mydata{
public://c++ class 默认private，如果都不写，系统会自动分配为两个public空的构造、析构函数
    mydata(){//构造
//        objs++;
        cout<<"mydata create"<<endl;
    }
    ~mydata()//析构
    {
//        objs--;
        cout<<"mydata delete"<<endl;
    }
    static void *operator new(size_t size){//重载new,对new重新解释，只针对当前类
        if (g_p==nullptr) {//单例加空判断
            objs++;
            mydata *p = ::new mydata();
            cout<<"new call"<<endl;
            g_p = p;
            return p;
        }else{
            return g_p;
        }
    }
    static void operator delete(void *p){//重载delete,对delete重新解释，只针对当前类
        if (g_p != nullptr) {
            objs--;
            cout<<"delete call"<<endl;
            ::delete p;
        }
    }
};

int main(){
    mydata *p1 = new mydata();
    mydata *p2 = new mydata();
    mydata *p3 = new mydata();

    delete p1;
    cout<<"objs="<<objs<<endl;
    cin.get();
    return 1;
}

new/delete全局重载

new=>::new=>malloc=>create;//分配内存优先于构造函数
decreate=>free=>::delete=>delete;//析构函数优先于释放内存

全局与局部new/delete分析

全局重载不完全，objs统计有问题

void * operator new (size_t size)
{
    objs++;
    cout<<"g_new call"<<endl;
    void *p = malloc(size);
    return p;
}


void operator delete(void *p) noexcept{
    objs--;
    cout<<"g_delete call"<<endl;
    free(p);
}

void * operator new [] (size_t size)
{
    objs++;
    cout<<"g_new [] call"<<endl;
    return operator new(size);
}

void operator delete [](void *p) noexcept{
    objs--;
    cout<<"g_delete [] call"<<endl;
    free(p);
}

int main()
{
    int *p  = new int(5);
    int *p2 = new int[10]{1,2,3,4,5,6,7,8,9,0};
    cout<<"objs="<<objs<<endl;
    delete p;
    cout<<"objs="<<objs<<endl;
    delete [] p2;
    cout<<"objs="<<objs<<endl;

	return 1;
 }

局部重载，objs统计可以放在构造和析构函数

static int objs = 0;
void *g_p = nullptr;
using namespace std;

class mydata{
public://c++ class 默认private，如果都不写，系统会自动分配为两个public空的构造、析构函数
    void *p;
    mydata(){//构造
        p = malloc(1024*1024*100);
        cout<<"mydata create"<<endl;
        objs++;
    }
    ~mydata()//析构
    {
        objs--;
        free(p);
        cout<<"mydata free"<<endl;
    }
    static void* operator new(size_t size);
    static void operator delete(void* p)noexcept;
    static void* operator new[](size_t size);
    static void operator delete[](void* p);
};

void mydata::operator delete(void *pf)noexcept{//重载delete,对delete重新解释，只针对当前类
    if (g_p != nullptr) {
        cout<<"mydata delete call"<<endl;
        //Cannot delete expression with pointer-to-'void' type 'void *'
        //::delete pf;
        free(pf);
    }
}

void *mydata::operator new(size_t size){//重载new,对new重新解释，只针对当前类
   if (g_p==nullptr) {//单例加空判断
       mydata *p = ::new mydata();
       cout<<"mydata new call"<<endl;
       g_p = p;
       return p;
   }else{
       return g_p;
   }
}

void *mydata::operator new [] (size_t size)
{
    cout<<"mydata new [] call"<<" size="<<size<<endl;
    void *p = malloc(size);
    return p;
}

void mydata::operator delete [](void *p){
    cout<<"mydata delete [] call"<<endl;
    free(p);
}

int main()
{
    mydata* pf = new mydata;//栈指针对象，指向堆对象
    cout<<"objs="<<objs<<endl;//2
    mydata* pf1 = new mydata[4];
    cout<<"objs="<<objs<<endl;//6
    delete pf;
    cout<<"objs="<<objs<<endl;//5
    delete[] pf1;
    cout<<"objs="<<objs<<endl;//1
    return 1;
}

也可以放在new/delete、new[]/delete[]里

static int objs = 0;
void *g_p = nullptr;
using namespace std;

class mydata{
public://c++ class 默认private，如果都不写，系统会自动分配为两个public空的构造、析构函数
    void *p;
    mydata(){//构造
        p = malloc(1024*1024*100);
        cout<<"mydata create"<<endl;
//        objs++;
    }
    ~mydata()//析构
    {
//        objs--;
        free(p);
        cout<<"mydata free"<<endl;
    }
    static void* operator new(size_t size);
    static void operator delete(void* p)noexcept;
    static void* operator new[](size_t size);
    static void operator delete[](void* p);
}
 
void mydata::operator delete(void *pf)noexcept{//重载delete,对delete重新解释，只针对当前类
    if (g_p != nullptr) {
        cout<<"mydata delete call"<<endl;
        //Cannot delete expression with pointer-to-'void' type 'void *'
        //::delete pf;
        free(pf);
        objs--;
    }
}

void *mydata::operator new(size_t size){//重载new,对new重新解释，只针对当前类
   if (g_p==nullptr) {//单例加空判断
       objs++;
       mydata *p = ::new mydata();
       cout<<"mydata new call"<<endl;
       g_p = p;
       return p;
   }else{
       return g_p;
   }
}

void *mydata::operator new [] (size_t size)
{
    short num = (short)size/sizeof(mydata);
    objs+=num;
    cout<<"mydata new [] call"<<" size="<<size<<endl;
    void *p = malloc(size);
    return p;
}

void mydata::operator delete [](void *p){
    short num = (short)sizeof(&p)/sizeof(mydata);
    objs-=num;
    cout<<"mydata delete [] call"<<endl;
    free(p);
}

list数据结构及双链表

list的应用

要了解c++的list实现细节可以参考C++链表的C实现（查找中间节点、判断是否存在环）

#include <list>
#include <list>
#include <iostream>

using namespace std;
int main()
{
    list<int> mylist{1,2,3,4,5};
    mylist.push_back(10);
    for(auto i : mylist){
        cout<<i<<endl;
    }
    cout<<endl;

    mylist.assign(3,5);//重新初始化链表为3个5
    for(auto i : mylist){
        cout<<i<<endl;
    }
    cout<<endl;
    
    mylist.assign(5,3);//重新初始化链表为5个3
    mylist.push_front(9);
    for(auto ib = mylist.begin(), ie = mylist.end();ib!=ie;ib++){//正序
        cout<<*ib<<endl;
    }
    cout<<endl;
    
    for(auto rb = mylist.rbegin(), re = mylist.rend();rb!=re;rb++){//倒序
        cout<<*rb<<endl;
    }
    cout<<"第一个L:"<<mylist.front()<<endl;
    cout<<"最后一个:"<<mylist.back()<<endl;
    cout<<"个数："<<mylist.size()<<endl;
    mylist.clear();
    cout<<endl;
    
    
    int a[10] {1,2,3,4,5,6,7,8,9,0};
    mylist.assign(a, a+5);//拷贝数组前5个
    for(auto ib = mylist.begin(), ie = mylist.end();ib!=ie;ib++){//正序
        cout<<*ib<<endl;
    }
    cout<<endl;

    
    for(auto ib = mylist.begin(), ie = mylist.end();ib!=ie;ib++){//前插
        if (*ib==3) {
            mylist.insert(ib, 123);
        }
        if (*ib==3) {
            //No matching member function for call to 'erase'
            //mylist.erase(3);
            mylist.erase(ib);
            break;//删除链表节点，应该退出循环
        }
    }
    for(auto ib = mylist.begin(), ie = mylist.end();ib!=ie;ib++){//正序
        cout<<*ib<<endl;
    }
    cout<<endl;

    mylist.pop_front();//删头
    mylist.pop_back();//删尾
    mylist.reverse();//反转
    mylist.sort();//排序
}

链表归并、交换，双链表及多链表

归并merge()

	list<int> mylist1{1,2,3,4,5};
    list<int> mylist2{6,7,8,9,0,10};
    mylist1.merge(mylist2);
    for(auto ib = mylist1.begin(), ie = mylist1.end();ib!=ie;ib++){//正序
        cout<<*ib<<endl;
    }//1,2,3,4,5,6,7,8,9,0,10

交换swap()

	list<int> mylist1{1,2,3,4,5};
    list<int> mylist2{6,7,8,9,0,10};
	mylist1.swap(mylist2);
    for(auto ib = mylist1.begin(), ie = mylist1.end();ib!=ie;ib++){//正序
        cout<<*ib<<endl;
    }//6,7,8,9,0,10

多链表

	list<int> mylist1{11,12,33,4,5};
    list<int> mylist2{6,17,8,12,9,0,10};
    list<int> mylist3{6,17,8,12,9,0,10};
    list<list<int>> mylist{mylist1,mylist2,mylist3};
    for(auto i : mylist){
        for(auto j :i){
            cout<<j<<" ";
        }
        cout<<endl;
    }

双链表管理一个类对象

类对象即使是空指针可以访问代码区函数，但是如果该函数访问局部变量，会因为没分配内存空间报错：

class MyClass{
public:
    int i=0;
    void show(){
//        Thread 1: EXC_BAD_ACCESS (code=1, address=0x0)
//        i = 2;
        messages_base();
    }
    my
};


int main(){
    MyClass *myClass(nullptr);
    myClass->show();//代码区共享可以访问

    return 1;
}

对于类来说：类的函数共享，数据则是每个类对象私有的，空对象调用成员函数，没有访问数据，可以调用，访问数据不可以。

class MyClass;

struct Info{
    MyClass *p;
    int n;
};
list<Info> myClasslist;//双链表数据结构，管理一个类所有对象

class MyClass{
public:
    void showMessage(){
        cout<<"hello"<<endl;
    }
    MyClass(){
        cout<<"MyClass()"<<endl;
    }
    ~MyClass(){
        cout<<"~MyClass()"<<endl;
    }
    void * operator new(size_t size){
        void *p = malloc(size);
        Info info;
        info.p = (MyClass *)p;
        if (size == sizeof(MyClass)) {
            info.n = 1;
        }else{
            info.n = (int)(size-8)/sizeof(MyClass);
        }
        myClasslist.push_back(info);
        return p;
    }
    void operator delete(void *p){
        //双链表检索内存，存在就删除，不存在不管
        for (auto ib = myClasslist.begin(), ie = myClasslist.end(); ib != ie; ib++) {
            if (p==(*ib).p) {
                myClasslist.erase(ib);
                free(p);
                break;
            }
        }
    }
    void * operator new[](size_t size){
        cout<<"new[]"<<size<<endl;//size = n+8;
        return operator new(size);
    }
    void operator delete[](void *p){
        operator delete(p);
    }
};

void showmemory(){
    for(auto i : myClasslist){
        cout<<"内存地址："<<i.p<<" "<<"个数："<<i.n<<endl;
    }
}

void callAllObjs(){
    for(auto myclass : myClasslist){
        if (myclass.n == 1) {
            myclass.p->showMessage();
        }else{
        	//对象数组的第一个地址是数组名,要跳过
            for (int j=0; j<myclass.n; j++) {
                myclass.p[j+1].showMessage();
            }
        }
    }
}

int main(){
    MyClass *p1 = new MyClass;
    MyClass *p2 = new MyClass;
    MyClass *pa1 = new MyClass[2];//size 18
    delete p1;
    delete p2;
    MyClass *pa2 = new MyClass[3];
    delete [] pa1;
    showmemory();
    callAllObjs();//3个
    
    return 1;
}

要是创建树结构

struct ClassInfo{
    MyClass *p;
    int n;
    char name[10];//类的名称
};
list<list<ClassInfo>> myTree;