#include <iostream>
#include <string>
using namespace std;


void merge(int a[],int c[],int first,int mid,int last){
    int i = first;
    int j = mid+1;
    int k = first;
    while(i<=mid && j<=last){
        if(a[i] <= a[j]){
            c[k] = a[i];
            k++;
            i++;
        }
        else{
            c[k] = a[j];
            k++;
            j++;
        }
    }
    while(i<=mid){
        c[k]=a[i];
        k++;
        i++;
    }
    while(j<=last){
        c[k]=a[j];
        k++;
        j++;
    }
for(int i=first;i<=last;i++)a[i]=c[i];
}

void mergeSort(int a[],int c[],int first , int last){
    if(first<last){
    int mid = (first+last)/2;
    mergeSort(a,c,first,mid);
    mergeSort(a,c,mid+1,last);
    merge(a,c,first,mid,last);
}
}

int  main(){
    int a[99] = {5,4,3,2,1};
    int c[99];
    mergeSort(a,c,0,4);
    for(int i = 0 ;i<5;i++){
        cout<<a[i]<<" ";
    }
}

归并排序的思想是分而治之,将数组不断分割,最后将两部分数组合并,通过判断第一部分和第二部分数组当前元素的大小来合并,不断合并直到完成排序。

归并排序是稳定的排序方式,归并排序的比较次数小于快速排序的比较次数,移动次数一般多于快速排序的移动次数,归并排序的时间复杂度为O(nlogn),空间复杂度为O(n)。

有时候scanf(“%c”,&ch)本应该阻塞等待用户输入一个char型数据的,但为什么会跳过呢?
例:在该程序段中,
int year;
    printf("请输入一个年份:\n");
    scanf("%d",&year);
   // setbuf(stdin,NULL);//或者直接用getchar();
    //在键盘输入一字符,显示其类型(数字、大写字母、小写字母、其他)
    char ch;
    printf("请输入一个字符:\n");
    scanf("%c",&ch);
    if(ch>='1'&&ch<='9')
        printf("this is digital\n");
    else if (ch>='A'&&ch<='B')
        printf("this is capital letter\n");
    else if (ch>='a'&&ch<='z')
        printf("this is letter\n");
    else
        printf("other!\n”);

 

会输出:
请输入一个年份:
2000
请输入一个字符:
other!
 
例2:
以下程序段:
while (n<=0)
{
printf(“请输入字符串长度:\n”);
scanf(“%d”,&n);
}
setbuf(stdin,NULL); //<1>
char a[n],b[n];
printf(“输入字符串:\n”);
for (int i=0; i<n; i++)
{
scanf(“%c”,&a[i]);
}
printf(“输出字符串为:\n”);
for (int i=0; i<n; i++)
{
b[i]=a[n-1-i];
printf(“%c”,b[i]);
}
如果将<1>语句去除,会使结果错误
例:
请输入字符串长度:
5
输入字符串:
hello
输出字符串为:
lleh

纠其根源,我们先来了解一下scanf()是怎么接受数据的。

首先,当我们的pc指向scanf这句时,系统并不是等待用户输入,而是判断输入缓冲区有没有符合格式的内容,如果有,则直接读取。

知道了这个,我就应该明白,scanf(“%c”,&ch);不是没有读到数据,而是读到了我们不知道的数据。

那问题又来了,它读到了什么??

好吧,这就要说到行缓存;

我们用scanf()的时候都要按下enter键,那enter键按了之后去哪儿了??

好吧,问题基本应该知道了,enter键也进入了输入缓存区,也就是scanf(“%c”,&ch);

读到了’\n’;

解决办法,很简单,既然缓存区有东西,那我们就清空它呗~~

setbuf(stdin,NULL);//这个windows和linux下都可以
fflush(stdin);//这个只能windows;

 

 

有没有想过,当我们定义一个对象的时候,该对象是定义在堆上还是栈上的呢?

现在,假设你已经清楚什么是堆,什么是栈。

如果需要在堆上创建对象,要么使用C++的new运算符,要么使用C语言的malloc系列函数。这点没有异议。

那么假如有一个类A,语句如下:

A a;

此时,a是在栈上分配的吗?

其实,这行语句的含义是,使对象a具有“自动存储(automatic storage)”的性质。所谓“自动存储”,意思是这个对象的存储位置取决于其声明所在的上下文。

如果这个语句出现在函数内部,那么它就在栈上创建对象。

如果这个语句不是在函数内部,而是作为一个类的成员变量,则取决于这个类的对象是如何分配的。

一般来说,如果你用new来生成的对象都是放在堆中的,而直接定义的局部变量都是放在栈中的,全局和静态的对象是放在数据段的静态存储区中。

那么,该如何定义一个只能在堆/栈上生成对象的类呢?

只能在堆上

方法:将析构函数设置为私有

原因:C++ 是静态绑定语言,编译器管理栈上对象的生命周期,编译器在为类对象分配栈空间时,会先检查类的析构函数的访问性。若析构函数不可访问,则不能在栈上创建对象。

如下所示:

#include <iostream>
using namespace std;

class A{
  public:
    A(){};
  private:
    ~A(){};//将析构函数设为私有
};

int main(){
    A a;//无法通过编译,提示A类的析构函数是私有的
    A *aa = new A();//通过编译,在堆上生成对象
}

 

只能在栈上

方法:将 new 和 delete 重载为私有

原因:在堆上生成对象,使用 new 关键词操作,其过程分为两阶段:第一阶段,使用 new 在堆上寻找可用内存,分配给对象;第二阶段,调用构造函数生成对象。将 new 操作设置为私有,那么第一阶段就无法完成,就不能够在堆上生成对象。

#include <iostream>
using namespace std;

class A{
  public:
    A(){};
    ~A(){};
   private:
    void * operator  new ( size_t  t){}//重载new运算符为私有类型
    void operator delete ( void * ptr){}//重载delete运算符为私有类型
};

int main(){
    A a;//通过编译,在栈上建立了对象
    A *aa = new A();//无法通过编译,提示new运算符是A的私有成员
}

 

翻阅以前的代码,时常会看到如下代码:

if(str.size() == 0) {}
if(!vec.size())     {}
if(!list.size())    {}
// ......

这些例子中只是把 size() 的返回值简单地进行布尔逻辑比较,意思是判断容器空与非空。

代码没有逻辑问题,只是可能效率不够高。

在C++的标准库容器中都有一个 empty() 方法,返回布尔值,表明容器当前是否为空。

使用 size() 判断容器非空与否的不好之处在于:某些标准库中的实现中对某些容器的 size() 求值操作不是线性的。

比如 std::list<>,在某些实现中,每一次调用 size() 都会遍历整个 list 来求 size,这会带来一定的性能问题。如果是线性容器则不会有此问题。

总之,如果只是想判断空与非空,则应总是使用 empty(),而不是 size()

#include <iostream>
#include<vector>
using namespace std;


void quickSort(vector<int>&a,int first , int last){
    if(first >= last){
        return;
    }
    int i = first,j = last;
    int key = a[first];//选择当前数字中第一个数作为基准key
    while(i < j){
        while(i < j && a[j] > key){
            j--;
        }
        a[i] = a[j];//在数组的后面遇到了比基准key小的数,放到前面去
        while(i < j && a[i] < key){
            i++;
        }
        a[j] = a[i];//在数组的前面遇到了比基准key大的数,放到后面去,刚好覆盖上次那个比基准大的数的位置
    }
    a[j] = key;//此时i==j,这个位置应该就是我们的基准key应该放到的地方
    quickSort(a,first,j-1);//递归对目前的key左边部分使用快速排序
    quickSort(a,i+1,last );//递归对目前的key右边部分使用快速排序
}

int main()
{
    vector<int>a = {22,32,54,79,154,2,10,0,-6,48,99};
    quickSort(a,0,10);
    for(int i = 0;i<11;i++){
        cout<<a[i]<<" ";
    }
}

快速排序是综合性能最好的排序方式,平均时间复杂度为O(nlogn),且不具有稳定性。

当序列已经是递增序列的时候,快速排序此时的时间复杂度最高,为O(n²)。

运算符重载就是用同一个运算符完成不同的运算功能,和函数重载一样,运算符重载是在编译阶段完成的,体现出静态的多态性。

C++运算符重载的规定如下:

  • 不能改变原运算符的优先级
  • 不能改变原运算符的结合性
  • 默认参数不能和运算符重载一起使用
  • 不能改变原运算符的操作数个数
  • 不能创建新的运算符,且部分已有运算符可能因为存在二义性问题所以无法被重载
  • 当运算符作用于C++内部提供的数据类型时,原来的含义保持不变。
  • 运算符可以被重载用于用户定义的类对象或者用户定义的类对象与内置数据类型变量的组合

C++中不能重载的运算符:

  1. .
  2. .*
  3. ::
  4. ?:
  5. sizeof

运算符重载为类成员函数时主要有3种形式:重载为类的成员函数、重载为类的友元函数、重载为普通函数。

 

重载++,–单目运算符

++和–重载运算符有前缀和后缀两种运算符重载形式,这里以++重载运算符为例,采用成员函数重载。

#include<iostream>
using namespace std;

class A
{
    int n;
public:
    A(int i){n = i;}
    operator ++(){//重载前缀运算符
     n++;
    }
    operator ++(int){//重载后缀运算符
     n = n+2;
    }
void show(){
cout<<"n="<<n<<endl;
}

};

int main()
{
    A a(5);
    A b(5);
    ++a;
    b++;
    a.show();
    b.show();
}

 

输出结果为:

n=6
n=7

 

如果改用成员函数的调用方式,重载后缀运算符的调用方式是a.operator++(1),其中1可以改为任意整数,它只是一个占位符。重载前缀运算符的调用方式是b.operator()。

 

重载下标运算符

下标运算符[]通常用于取数组的某个元素,下标运算符重载可以实现数组下标的越界检测等,如下Words类所示:

class Words
{
    int len;
    char *str;
public:
    Words(char *s){
    str = new char[strlen(s)+1];
    strcpy(str,s);
    len = strlen(s);
    }

    char operator[](int n){
    if(n > len-1){
        cout<<"数组下标越界";
        return ' ';//返回一个特殊字符即可
    }
    else return *(str+n);
    }
};

 

重载运算符new/delete

C++提供了new和delete两个运算符用于内存管理,在大多数情况下它们是非常有效的,但在有些情况下需要自己管理内存,以克服原new与delete的不足,这就是重载运算符new和delete。delete和delete只能被重载为类的成员函数或者普通函数,不能被重载为友元函数,而且不论是否使用关键字static进行修饰,重载了的new和delete均为类的静态成员函数。

重载new运算符的一般格式:

void *类名::operator new(size_t size,其他形参){
     //使用malloc完成分配工作
     //完成自己需要的操作
     return void *型指针;
}

上述new重载函数应返回一个无值型的指针,形参可以有多个,但第1个参数一定是size_t类型的参数,它表示要分配空间的大小,再调用时由系统自动获取。

在使用重载new运算符时先调用new的重载成员函数,再调用该类的构造函数。

重载delete运算符的一般格式:

void *类名::operator delete(void *p){
     //使用free完成内存释放工作
     //完成自己需要的操作
}

在使用重载delete运算符时默认先调用类的析构函数,再调用重载的delete成员函数。

重载new[]/delete[]和重载new/delete类似。

 

重载输入/输出运算符

重载插入运算符的一般格式如下:

friend ostream& operator<< (ostream & stream,类名 &类引用名){
  //函数体
   return stream;
}

 

重载输出运算符的一般格式如下:

friend istream& operator>> (ostream & stream,类名 &类引用名){
  //函数体
   return stream;
}

 

设计单例模式的意图是保证一个类仅有一个实例,并提供类的一个全局访问点,该实例被所有程序模块共享。

采用C++实现单例模式有多种方式,这里采用嵌套类实现。

其中类A实现单例模式。

  • 它的构造函数的私有的,这样就不能从别处创建该类的实例。
  • 它有一个唯一实例的静态对象指针pinstance,且是私有的。
  • 它有一个共有函数GetInstance(),可以获取这个唯一的实例,并在需要的时候创建该实例。
  • 设计嵌套类的目的是为了定义它的静态子对象,在程序结束时会调用该子对象的析构函数以释放唯一的实例。
  • 如果采用在类A中设计析构函数来释放实例,则该析构函数必须是公用的,这在单例模式中是不恰当的。

源代码如下:

#include<iostream>
using namespace std;

class A{
   //其他数据成员
public:
    static A *GetInstance(){
    if(pinstance ==NULL){
        pinstance = new A();
    }
    return pinstance;
    }
private:
    static A *pinstance;//返回唯一实例的指针
    class B //嵌套类,它的唯一工作就是在析构函数中释放实例
    {
    public:
        ~B(){
          if(A::pinstance!=NULL){
            delete A::pinstance;
            cout<<"delete";
          }
        }
    };
    static B b;//定义一个子对象,在程序结束时会调用它的析构函数
};

A *A::pinstance=NULL;//静态子对象指针初始化
A::B A::b;//静态子对象初始化

int main(){
    A *p= A::GetInstance();
    A *q = A::GetInstance();
    if(p == q) cout<<"Same"<<endl;
    return 0;
}

 

输出结果为:

Same
delete

 

从结果可以看出类A的两个对象指针指向同一个实例,说明只能创建唯一的实例,并且该唯一实例是自动销毁的。

在C++中,对象复制分为浅复制和深复制。

(1)对象的浅复制

当两个对象之间进行复制时,若复制完成后它们还共享某些内存空间,其中一个对象的销毁会影响到另一个对象,这种对象之间的复制称为浅复制。

(2)对象的深复制

当两个对象之间进行复制时,若复制完成后它们不会共享任何内存空间,其中一个对象的销毁不会影响到另一个对象,这种对象之间的复制称为深复制。

通常情况下拷贝构造函数执行的都是浅复制,当有必要时,我们可以自己写一个拷贝构造函数实现深复制。当一个类中的数据成员带有指针时,此时使用默认的拷贝构造函数,类对象的指针数据成员经过浅复制后会指向同一块内存区域,表面上看上去仿佛没事,但一旦销毁其中任意一个对象时,会调用该类的析构函数,那么指针指向的那块内存区域会被回收,此时再访问另一个对象时,这个对象的指针数据成员所指地址的内存区域已经被回收,会产生未定义的结果,要解决这个问题,我们需要重写拷贝构造函数,实现深复制。实现深复制只需要在该类的拷贝构造函数中,动态分配一块大小和被复制的对象的指针指向的内存区域相同大小的内存区域,将数据复制过去,并将指针指向刚刚分配的内存区域即可。

如下为String 类的基本实现,用到了深复制。

class String{
public:
    String(const char *str = NULL);//构造函数
    String(const String &other);//拷贝构造函数
    ~String(void);//析构函数
    String & operator = (const String &other);//重载赋值运算符
private:
    char *m_data;//用于保存字符串
};

String::String(const char *str )//构造函数
{
    if(str == NULL){
        m_data = new char[1];
        *m_data = '\0';
    }
    else{
        int length = strlen(str);
        m_data = new char[length+1];
        strcpy(m_data,str);
    }
}
String::String(const String &other)//拷贝构造函数
{
    int length = strlen(other.m_data);
    m_data = new char[length+1];
    strcpy(m_data,other.m_data);
}
String::~String(void)//析构函数
{
    delete m_data;
}
String &String :: operator = (const String &other)//重载赋值运算符
{
    if(this==&other){//检查自赋值
        return *this;
    }
    delete m_data;
    int length = strlen(other.m_data);
    m_data = new char[length+1];
    strcpy(m_data,other.m_data);
    return *this;
}

 

C++的空类是指设计时不包含任何数据成员和成员函数的类。

实际上,对于一个空类,系统会自动添加以下默认的成员函数:

1.默认构造函数

2.默认拷贝构造函数

3.默认析构函数

4.赋值“=”运算符

5.取地址运算符

6.取地址运算符const

对于一个空类A,sizeof(A)的值为1,这是因为实例化的原因,空类同样可以被实例化,每个实例在内存中都应该有唯一的地址,为了达到这个目的,编译器会给一个空类插入一个字节,这样空类在实例化后在内存中得到唯一的地址,所以空类所占的内存大小是1个字节。

 

在C++中,类对象的存储空间分配方式如下:

(1)一个类对象的分配空间中仅包含所有非静态数据成员,并按照这些数据成员定义的顺序存放。

(2)一个类对象的大小为其所有非静态数据成员的类型大小之和,普通成员函数与sizeof是没有关系的。当类中有一个或者多个虚函数时,由于要维护虚函数表,所以有一个虚函数表指针,另外当存在虚继承时还需要一个指向虚基类的指针,每个指针占用一个地址大小的内存空间,即4个字节。

(3)类对象中的各个数据成员分配内存时也遵守内存对齐规则。内存对齐规则请看:内存对齐

在了解了对象的存储结构后,可以采用取指定地址中值的方式访问对象的私有数据成员,如下程序所示:

#include<iostream>
using namespace std;

class A{
private:
    int x;
    int y;
public:
    A(int i,int j){
        x = i;
        y = j;
    }
    
};

int main()
{
    A a(1,3);
    cout<<"a.x="<<*((int *)(&a))<<endl;
    cout<<"a.y="<<*((int *)(&a)+1)<<endl;
}

输出为:

a.x=1
a.y=3
Program ended with exit code: 0