构建大数类

白书你好

看书啊看书啊看书啊!

买了小大白书的kindle版,所以用稍微零碎的时间来看小白书,其实一直在说要看完白书啊看完白书啊,其实一批了木有看完。当然,小白对于这个阶段意义不是太大了,把语言篇直接pase,从算法篇开始,再过一遍。

其实看书是个很快的过程,理解用的时间也不是太多,更多的时间是花在总结上,我发现我自从建了博客写学习总结,一个学习过程有1/3是看书理解,1/3是琢磨写总结。几乎和再看一遍用的时间一样。记得开始的时候写数据结构总结,一章就是两三小时。

其实还是很纠结要不要再用这么多时间写总结的,那些不写总结的家伙,看书就是快。都无奈了。

大数问题

大数问题是进集训队第一周狂刷的东西,挺练模拟能力的,不过今天我才发现白书是用结构体和运算符重载把大数搞定的,我便模仿一下,不用结构体,直接用类,写个大数类,以后直接当模板。

大数,就是特别大的数,因为,大到longlong存储不下去,便需要用数组存储,因此,需要用数组来模拟加减乘除,这次我只打算搞加减乘。

构建大数类

存储:

要有长度,保存大数的长度,在计算,打印,都很有必要

要有负号标记,在处理的时候,知道这是一个大负数

一个长数组,用来保存大整数

class bign
{
private:
    bool sign;
    int len;
    int num[MAX_LEN];
}

 非计算操作:

要有初始化,赋值,包括字符串赋值,int赋值等,本来想和白书一样重载=运算符,但是突然发现我这是在写一个类啊,不是结构体,那么直接重载构造函数就可以了,所以写了无参数,字符串参数,整型参数的构造函数。

可以打印,直接友元函数重载

class bign
{
public:
    bign(){len = 0;memset(num,0,sizeof(num));}
    bign(char *s)
    {
        sign = 0;
        int s_len = strlen(s);
        memset(num,0,sizeof(num));

        if(s[0] == '-')
        {
            sign = 1;
            int i = 0;
            len = s_len - 1;
            for(char *p = s + s_len - 1;p > s;p--)
                num[i++] = *p - '0';
        }else
        {
            int i = 0;
            len = s_len;
            for(char *p = s + s_len - 1;p >= s;p--)
                num[i++] = *p - '0';
        }

    }
    bign(int n)
    {
        len = 0;
        sign = 0;
        memset(num,0,sizeof(num));
        if(n == 0)
        {
            len = 1;
        }else
        {
            if(n < 0)
            {
                sign = 1;
                n = -n;
            }
            while(n != 0)
            {
                num[len++] = n % 10;
                n /= 10;
            }
        }

    }

    friend ostream& operator << (ostream& os,bign n)
    {
        if(n.sign)
            os << '-';
        for(int i = n.len - 1;i >= 0;i--)
            os << n.num[i];
        return os;
    }
};

 大数计算

比较

在设计这些运算之前,我先搞定大数比较的问题,其实是想在大数减法上偷偷懒神马的。

//大数比较
    bool operator < (const Bigint & b) const
    {
        if(sign == b.sign)
        {
            if((!sign && !b.sign)&&len != b.len) return len < b.len;
            if((sign && b.sign)&&len != b.len) return len > b.len;
            if(sign)
            {
                for(int i = len - 1;i >= 0;i--)
                    if(num[i] != b.num[i]) return num[i] > b.num[i];
            }else
            {
                for(int i = len - 1;i >= 0;i--)
                    if(num[i] != b.num[i]) return num[i] < b.num[i];
            }
        }else
        {
            if(!sign && b.sign) return false;
            if(sign && !b.sign) return true;
        }
        return false;
    }

只需要写出一个小余,其他的操作都可以用小余来进行判断。

    bool operator > (const Bigint & b) const{return b < *this;}
    bool operator <= (const Bigint & b) const{return !(b < *this);}
    bool operator >= (const Bigint & b) const{return !(*this < b);}
    bool operator != (const Bigint & b) const{return b < *this || *this < b;}
    bool operator == (const Bigint & b) const{return !(b < *this) || !(*this < b);}

只为在减法的时候偷偷懒。

加法

在进行加法的时候进行了符号判断,虽然有点感觉是在画蛇添足,但是为了圆这个ADT式的谎,还是加上吧。

//加法
    bign operator + (const bign &b) const
    {
        bign c;
        //判断加后符号
        if(sign && b.sign)
            c.sign = 1;
        else if(!sign && b.sign)
            return c = b - *this;
        else if(sign && !b.sign)
            return c = *this - b;
        c.len = 0;
        for(int i = 0,g = 0;g || i < max(len,b.len);i++)
        {
            int x = g;
            if(i < len) x += num[i];
            if(i < b.len) x += b.num[i];
            c.num[c.len++] = x % 10;
            g = x / 10;
        }
        return c;
    }
    bign operator += (const bign &b)
    {
        *this = *this + b;
        return *this;
    }

 减法

有了大数比较之后,就可以轻松的偷懒了。

//减法
    Bigint operator - (const Bigint &b) const
    {
        Bigint c;
        c.len = 0;
        if(*this > b)
        {
            c.sign = 0;
            for(int i = 0;i < max(len,b.len);i++)
            {
                int x = 0;
                if(i < len) x += num[i];
                if(i < b.len) x -= b.num[i];
                if(c.len > 0 && c.num[c.len - 1] < 0){c.num[c.len - 1] += 10;x--;}
                c.num[c.len++] = x;
            }
        }else if(*this < b)
        {
            c.sign = 1;
            for(int i = 0;i < max(len,b.len);i++)
            {
                int x = 0;
                if(i < len) x -= num[i];
                if(i < b.len) x += b.num[i];
                if(c.len > 0 && c.num[c.len - 1] < 0){c.num[c.len - 1] += 10;x--;}
                c.num[c.len++] = x;
            }
        }else
        {
            c = 0;
        }

        while(c.num[c.len - 1] == 0 && c.len > 0)
            c.len--;
        if(c.len == 0) c.len = 1;

        return c;
    }
    Bigint operator -= (const Bigint &b)
    {
        *this = *this - b;
        return *this;
    }

 乘法

在写乘法之前特意去OJ找了两个加法和减法的题目,然后A掉,爽啊,想想还有最后一个乘法,常用大数类就搞出来了,那叫一个激动啊!!!

可以说乘法是比较难搞的,因为时间复杂度有点高。

//乘法
    Bigint operator * (const Bigint &b) const
    {
        Bigint c;
        if((sign && b.sign) || (!sign && !b.sign)) c.sign = 0;
        else c.sign = 1;

        //时间复杂度 O(len * b.len)
        for(int i = 0;i < len;i++)
            for(int j = 0;j < b.len;j++)
                c.num[c.len = max(i + j,c.len),i + j] += num[i] * b.num[j];

        for(int i = 0;i < c.len;i++)
        if(c.num[i] >= 10) {c.num[i + 1] += c.num[i] / 10;c.num[i] %= 10;}

        while(c.num[c.len] != 0)
            ++c.len;

        while(c.num[c.len - 1] == 0 && c.len > 0)
            c.len--;
        if(c.len == 0) c.len = 1;
        return c;
    }
    Bigint operator *= (const Bigint &b)
    {
        *this = *this * b;
        return *this;
    }

到此,常用大数类算是完成了。(除了除法)

大数类代码

#include <iostream>
#include <cstring>

using namespace std;

#define MAX_LEN 1500  //存储大整数的整型数组的长度

class Bigint
{
private:
    bool sign;//是否非负数
    int len;  //长度
    int num[MAX_LEN];
public:
    Bigint(){len = 0;memset(num,0,sizeof(num));}
    Bigint(char *s)
    {
        sign = 0;
        int s_len = strlen(s);
        memset(num,0,sizeof(num));

        if(s[0] == '-')
        {
            sign = 1;
            int i = 0;
            len = s_len - 1;
            for(char *p = s + s_len - 1;p > s;p--)
                num[i++] = *p - '0';
        }else
        {
            int i = 0;
            len = s_len;
            for(char *p = s + s_len - 1;p >= s;p--)
                num[i++] = *p - '0';
        }

    }
    Bigint(int n)
    {
        len = 0;
        sign = 0;
        memset(num,0,sizeof(num));
        if(n == 0)//特判
        {
            len = 1;
        }else
        {
            if(n < 0){sign = 1;n = -n;}
            while(n != 0){num[len++] = n % 10;n /= 10;}
        }

    }
    //打印大数
    friend ostream& operator << (ostream& os,Bigint &n)
    {
        if(n.sign)//判断符号
            os << '-';
        while(n.num[n.len - 1] == 0)
            n.len--;
        for(int i = n.len - 1;i >= 0;i--)
            os << n.num[i];
        return os;
    }
    //大数比较
    bool operator < (const Bigint & b) const
    {
        if(sign == b.sign)
        {
            if((!sign && !b.sign)&&len != b.len) return len < b.len;
            if((sign && b.sign)&&len != b.len) return len > b.len;
            if(sign)
            {
                for(int i = len - 1;i >= 0;i--)
                    if(num[i] != b.num[i]) return num[i] > b.num[i];
            }else
            {
                for(int i = len - 1;i >= 0;i--)
                    if(num[i] != b.num[i]) return num[i] < b.num[i];
            }
        }else
        {
            if(!sign && b.sign) return false;
            if(sign && !b.sign) return true;
        }
        return false;
    }
    bool operator > (const Bigint & b) const{return b < *this;}
    bool operator <= (const Bigint & b) const{return !(b < *this);}
    bool operator >= (const Bigint & b) const{return !(*this < b);}
    bool operator != (const Bigint & b) const{return b < *this || *this < b;}
    bool operator == (const Bigint & b) const{return !(b < *this) || !(*this < b);}
    //加法
    Bigint operator + (const Bigint &b) const
    {
        Bigint c;
        //判断加后符号
        if(sign && b.sign)
            c.sign = 1;
        else if(!sign && b.sign)
            return c = *this - b;
        else if(sign && !b.sign)
            return c = b - *this;
        c.len = 0;
        for(int i = 0,g = 0;g || i < max(len,b.len);i++)
        {
            int x = g;
            if(i < len) x += num[i];
            if(i < b.len) x += b.num[i];
            c.num[c.len++] = x % 10;
            g = x / 10;
        }
        return c;
    }
    Bigint operator += (const Bigint &b)
    {
        *this = *this + b;
        return *this;
    }
    //减法
    Bigint operator - (const Bigint &b) const
    {
        Bigint c;
        c.len = 0;
        if(*this > b)
        {
            c.sign = 0;
            for(int i = 0;i < max(len,b.len);i++)
            {
                int x = 0;
                if(i < len) x += num[i];
                if(i < b.len) x -= b.num[i];
                if(c.len > 0 && c.num[c.len - 1] < 0){c.num[c.len - 1] += 10;x--;}
                c.num[c.len++] = x;
            }
        }else if(*this < b)
        {
            c.sign = 1;
            for(int i = 0;i < max(len,b.len);i++)
            {
                int x = 0;
                if(i < len) x -= num[i];
                if(i < b.len) x += b.num[i];
                if(c.len > 0 && c.num[c.len - 1] < 0){c.num[c.len - 1] += 10;x--;}
                c.num[c.len++] = x;
            }
        }else
        {
            c = 0;
        }

        while(c.num[c.len - 1] == 0 && c.len > 0)
            c.len--;
        if(c.len == 0) c.len = 1;

        return c;
    }
    Bigint operator -= (const Bigint &b)
    {
        *this = *this - b;
        return *this;
    }
    //乘法
    Bigint operator * (const Bigint &b) const
    {
        Bigint c;
        if((sign && b.sign) || (!sign && !b.sign)) c.sign = 0;
        else c.sign = 1;

        //时间复杂度 O(len * b.len)
        for(int i = 0;i < len;i++)
            for(int j = 0;j < b.len;j++)
                c.num[c.len = max(i + j,c.len),i + j] += num[i] * b.num[j];

        for(int i = 0;i < c.len;i++)
        if(c.num[i] >= 10) {c.num[i + 1] += c.num[i] / 10;c.num[i] %= 10;}

        while(c.num[c.len] != 0)
            ++c.len;

        while(c.num[c.len - 1] == 0 && c.len > 0)
            c.len--;
        if(c.len == 0) c.len = 1;
        return c;
    }
    Bigint operator *= (const Bigint &b)
    {
        *this = *this * b;
        return *this;
    }
    //除法
    Bigint operator / (const long long b) const
    {
        Bigint c;
        c.sign = 0;
        long long n[MAX_LEN];
        long long n_len = 0;
        long long yushu = 0;

        int tf = 0;
        for(int i = len;i >= 0;i--)
        {
            if((yushu * 10 + num[i]) / b)
            {
                tf = 1;
                n[n_len++] = (yushu * 10 + num[i]) / b;
                yushu = (yushu * 10 + num[i]) % b;
            }else
            {
                if(tf)
                    n[n_len++] = 0;
                yushu = yushu * 10 + num[i];
            }
        }

        c.len = n_len;

        for(int i = 0;i < n_len;i++)
        {
            c.num[i] = n[n_len - 1 - i];
        }
        if(c.len == 0)
            c.len = 1;
        return c;
    }
    Bigint operator /= (const long long &b)
    {
        *this = *this / b;
        return *this;
    }
    //取余
    long long operator % (const long long b) const
    {
        long long yushu = 0;

        for(int i = len;i >= 0;i--)
        {
            if((yushu * 10 + num[i]) / b)
            {
                yushu = (yushu * 10 + num[i]) % b;
            }else
            {
                yushu = yushu * 10 + num[i];
            }
        }

        return yushu;
    }
    Bigint operator %= (const long long &b)
    {
        *this = *this % b;
        return *this;
    }
};
2014/11/19 posted in  C++

C++第九章笔记

和C一样,C++为内存存储数据方面提供了多种选择,可以选择数据保留在内存中的时间(生命域)以及程序的哪一部分可以访问数据(作用域和链接)等。

单独编译

和C语言一样,C++也允许甚至鼓励程序员将组件函数放在独立的文件中。可以单独编译这些文件然后将他们链接成可执行的程序。(IDE包含编译器和链接器的原由吧)。

头文件:包含结构声明和使用这些结构的函数的原型

源代码文件:包含与结构有关的函数的代码

源代码文件:包含调用与结构相关的函数代码

不要将函数定义或变量声明放在头文件中,对于简单的情况是可行的,但是如果存在重复包含头文件的文件,则会出现一个程序中将包含同一个函数的两个定义,除非函数式内联的,否则这将出错。

头文件经常包含的内容:

  • 函数原型
  • 使用define或const定义的符号常量
  • 结构声明
  • 类声明
  • 模板声明
  • 内联函数

将结构声明放在头文件中是可以的,因为它们不创建变量,而只是在源代码文件中声明结构变量时,告诉编译器如何创建该结构变量。同样,模板声明不是将被编译的代码,它们指示编译器如何生成与源代码中函数调用相匹配的函数定义。被声明为const的数据和内联函数有特殊的链接属性,因此可以放在头文件。

 存储持续性、作用域和链接性

在C++11中,有四种不同的方案来存储数据,这些方案的区别在于数据保留在内存中的时间。

  • 自动存储持续性(自动变量)
  • 静态存储持续性(静态变量,全局变量)
  • 线程存储持续性(C++11,使用关键字thread_local)
  • 动态存储持续性(动态内存)

作用域描述了名称在文件的多大范围内可见。

作用域为局部的变量只在定义它的代码块中可用。代码块是由花括号括起来的一系列语句。作用域为全局(也叫做文件作用域)的变量在定义位置到文件结尾之间都可用。自动变量的作用域为局部,静态变量的作用域是全局还是局部取决于是如何定义的:

链结性描述了名称如何在不同单元间共享:外部链接在文件间共享,内部链接只能有一个文件中的函数共享,自动变量没有链结性,因为它们不能被共享。

mutable说明符指出,即使结构变量为const,其某个成员也可以被修改

struct data
{
char name[30];
mutable int accesses;
...
};

又是一个神器。。

new支持定位操作,

char s[100];
int *p = new(s) int[10];

便可以在s的空间中申明出一个10个元素的int数组。神奇。

但是,因为毕竟不是在堆中开的内存,用delete会错误!

名称空间

在C++中,名称可以是变量、函数、结构、枚举、类以及类和结构的成员。当随着项目的增大,名称相互冲突的可能性增大。使用多个厂商的类库时,可能导致名称冲突。因此有了名称空间。

传统的C++名称空间,

声明区域是可以在其中声明的区域比如函数外的全局变量。

潜在作用域,变量在潜在作用域从声明点开始,到其声明区域结尾,因此潜在作用域比声明区域小,这是由于变量必须定以后才能使用。

一个名称空间不会和另外一个名称空间冲突。

名称空间可以是全局也可以位于另外一个名称空间中,但不能位于代码块中,因此,默认情况下在名称空间中声明的名称的链接性为外部。

名称空间定义起来很简单:

namespace Jill
{
char fetch(){...}
...
}

使用起来也简单,

Jill::fetch();

为了编程简单,于是有了using声明和using编译指令,

using Jill::fetch;

之后这个函数就可以正常使用了,

using namespace Jill;

之后,这个名称空间里的东西就可以正常使用了。

如果就着尽量节省的原则,前者可以节省更多的代码长度,因为没有用到的函数等其他名称空间的东西没被声明定义。

就着安全的原则,推荐使用第一种以避免多名称空间中的名称冲突。

名称空间是可以嵌套的,不过也很简单。

名称空间可以未命名,因为名称空间定义之后,里面的东西就相当于全局变量,但是未命名就限制了此空间内的东西只能在当前文件使用。

名称空间及其用途

  • 使用已命名的名称空间中声明的变量,而不是使用外部全局变量
  • 使用已命名的名称空间中声明的变量,而不是使用静态全局变量
  • 仅将using作为一种将旧代码转换为使用名称空间的权宜之计
  • 不要在头文件中使用using编译指令,非要添加using的话,只少要保证include的正确顺序
  • 导入名称空间时首选使用作用解析运算符或是using声明而不是using编译指令
  • 对于using声明,,首选将其作用域设置为局部而不是全局

总之,名称空间的引入是为了管理项目。

2014/11/10 posted in  C++

C++第八章笔记

昨天刚制定好学习计划,今天的任务是C++第八章,╮(╯▽╰)╭C++拖得太久了,耽误了好多事情。

好不容易把引用变量之前的写完了,因为草稿保存故障,又要重写,真心伤不起。

第八章是第七章的继续,继讲了函数部分。如果说第七章讲的是C++与C语言函数部分的共同点和微妙差异的话那么第八章讲的就是C++函数的独特之处。C++较之C语言提供了许多新的函数特性,包括内联函数、按引用传递变量、默认的参数值、函数重载(多态)以及函数模板。

内联函数

内联函数是C++为提高程序运行速度所做的一项改进。常规函数和内联函数之间的区别不在于编写方式,而在于C++编译器如何将它们组合到程序中的。As we all know,普通函数会在内存中占唯一的内存空间,每次调用函数的时候,CPU会终止当前运行的代码(并把当前运行地址保存到栈中),跳转到函数处继续执行,知道函数执行结束再跳转回来。然而跳转是需要时间的,尤其是跳转频繁的函数。因此,内联函数的目的就是把函数镶嵌到应当调用函数的代码块中,直接执行而不是跳转。虽然代价是消耗更多的内存空间来保存内联函数执行代码,但是却能节省下不少跳转时间。

也是因为内联函数节省的是跳转时间而且以内存作为代价,我们需要有选择的使用内联函数,如果执行函数代码时间比处理函数调用机制的时间长,则节省的时间将只占整个过程中很小的一部分,反之,如果代码执行时间很短,则时间优化很明显。我认为,对于调用频繁或代码短小的函数最好使用内联函数。

怎么使用内联函数

1.在函数声明前加上关键字inline

2.在函数定义前加上关键字inline

也就是说,如果想要使用内联函数,那么声明和定义前都需要加上关键字。当然,如果省略原型的函数,也就是声明加定义在一起的函数,写一次就够了。

总之,用不用内联函数是程序员的事,怎么实现内联函数是编译器的事。但是不是你认为使用了内联关键字就内联了,因为编译器不会总满足程序员的请求,如果编译器觉得函数代码过长或者内联函数调用了自己(内联函数不允许递归),因此不将其作为内联函数。当然这些标准的主动性在编译器。

因为内联函数和C语言的defin很像,但较之C的宏定义函数,还是内联函数更胜一筹,因为内联函数本来就是个函数,而define只不过是替换罢了,函数更容易查错和避免一些有歧义的语句。

引用变量

引用变量是C++新定义的一种复合类型。引用时已定义的变量的别名,我总感觉引用和指针差不多,只不过是对那些不先用*的安慰品。

其实引用最大的作用就是帮助函数传参,和指针类似,传递的实参没有被复制,而是直接访问原变量的内存空间,从而节省时间。(还有一个作用,像double在复制时也会有精度损失,引用传递double可以避免损失)。

创建引用变量,其实很简单,和指针类似

对于int a;

创建应用 int &b = a;

这时候b就可以和a一样使用了,他们两个控制的是同一个内存空间。

但是要注意,对新建一个引用,必须要在声明的时候把他定义,这一点有点像指针常量的声明。

也正是因为引用访问原变量的存储空间,在引用传参的时候,要和指针一样注意原数据的保护(不如,多多使用const)。

对于使用引用传参的函数,传递的必须是一个变量也不应是一个值(换句话说,就说传递的参数必须有个存储空间)。

比如 void fun(int &n)函数,传参fun(a + 3)是非法的。(有些老编译器只是警告,但是重新开辟了临时空间保存a+3的值)。

对于引用不匹配,编译器可能会开辟临时存储空间(和普通函数效果一样),但是开辟是有条件的。如果参数仅为const引用和满足一下条件时C++才允许这么做:

1.实参的类型不正确,但不是左值(不可以改变的常量)

2.实参的类型不正确但可以转换为正确的类型(比如int转double)。

但是,如果接受引用参数的函数的意图是修改作为参数传递的变量,那么创建临时变量将阻止这种意图的实现,因此此时要避免创建临时变量。

如果函数返回的是个引用,应该要注意,如果变量是在函数内定义的,如果返回这个变量的引用是危险的,因为这个变量在函数结束的时候便被释放了。而返回、访问一个被释放的变量的空间十分危险。

因为函数返回可以是引用,也就是可以修改的左值,那么 function(a,b) = c;这种语句是合法的。虽然高大上但有点费劲,避免这种语句的良策还是const返回类型。

C++有个有趣的现象,因为类可以继承,所以对基类的函数参数,既可以用基类,也可以用派生类。

如果需要显示小数模式则

setf(ios_base::showpoint); //将对象置于显示小数模式
precision(); //制定小数显示多少位

对于这些设置会一直保存,知道在修改回默认。

使用引用的原因有两个:

1.程序员能够修改调动函数中的数据对象

2.通过传递引用而不是整个数据对象可以提高程序运行速度

但要注意,对于本来就是传递地址的数据对象比如数组只能使用指针。

默认参数

默认参数是C++中十分炫酷的功能。默认参数指的是当函数调用中省略了实参是自动使用的一个值。

很吊大上的功能,使用起来也很方便。

char * left(const char *str,int n = 1);

当调用函数left的时候,如果只写了一个参数str,那么第二个参数默认n=1。

我认为很屌的功能但C++PP确认为并非编程方面的巨大突破,而只是提供了一种便捷的方式。在设计类时,通过使用默认参数,可以减少要定义的析构函数、方法以及方法重载的数量。

对于使用函数默认参数,只有原形制定了默认值,而函数定义与没有默认参数时完全相同

因为默认参数调用时可以省略,导致如果你为一个参数设定默认值,你必须为其右边所有参数设定默认值!

函数重载

函数多态是C++在C语言基础上新增的功能。而函数多态能够使用多个同名函数。术语“多态”指的是有多种形式,因此函数多态允许函数可以有多种形式。类似的,术语“函数重载”指的是可以有多个同名函数,因此对名称进行了重载。这两个术语指的是同一回事,但我们通常使用函数重载。可以通过函数重载来设计一系列函数——让他们完成相同的工作,但使用不同的参数列表

函数重载的关键是函数的参数列表,也称之为函数特征标,所谓参数列表就是,函数的参数的数目和数据类型(不包括形参的变量名以及返回类型)。

对于重载不是完全匹配,编译器不会武断的停止匹配而是尝试使用标准类型转换强制进行匹配,比如,把int实参转化为double类型。但是,如果在不完全匹配的情况下,通过转换存在多种较为合理的解释,编译器便会保持。其实,不论是否非完全匹配,只要在函数重载中存在歧义,编译器都会报错

不止是在调用的时候,如果在声明了两个特征标相同的函数,编译器也是不允许的比如下面(不要把数据类型的引用和数据的类型本身会为一谈):

double cube(double x);

double cube(double &x);

不仅如此,特征标不区分是否是const和非const变量。因为正如前面,非const函数只能接受非const实参,而const函数能接受非const实参和const实参,因此使用范围有交集,也就是说有歧义。编译器不允许这么做。

重载引用参数存在特殊性。

void stove(double & r1);
void stove(const double & r2);
void stove(double && r3);

double x = 1.0;
const double y = 2.0;

stove(x);
stove(y);
stove(x + y);

对于第一个函数,要求一个可以修改的左值,对于第二个函数,要求一个不可修改的左值,最后一个左值引用参数r3将于一个左值匹配。

因此,x调用第一个函数,y调用第二个函数,x+y调用第三个函数。

但是,这并不是绝对的,因为,对于x+y,第二个函数也是可以行得通的(不可修改的左值)。因此,如果

void stove(double && r3);

不存在的话,编译器会自动匹配到

void stove(const double & r2);

这就是重载引用参数时,编译器会自动调用最匹配的版本。

函数重载虽然吸引人但也不要滥用,仅当函数基本上执行相同的任务,但是用不同的形式的数据时,才应采用函数重载。

如果需要使用不同类型的参数,则默认参数便不管用了,在这种情况下,也可以考虑函数重载。

函数模板

函数模板也是C++新增特性,函数模板是通用的函数描述,也就是说它们使用泛型来定义函数,其中的泛型可用具体的类型如int,double替换。通过将类型转化为参数传递给模板,可使编译器生成该类型的函数。由于模板允许以泛型的方式编写程序,因此有时也被成为通用编程。由于累心是由参数表示的,因此模板特性有时也被成为参数化类型。

怎么使用函数模板

template
void Swap(AnyType &a,AnyType &b)
{
AnyType temp;
temp = a;
a = b;
b = temp;
}

第一行指出,要建立一个模板,并将类型命名为AnyType,关键字template和typename是必须的。除非使用关键字class代替typename(在C++98添加typename之前,都是用class来创建模板的)。另外,必须使用尖括号,类型名可以任意选择(这里的AnyType)。

模板不会创建任何函数,只是告诉编译器如何定义函数,当调用实际参数的时候,编译器才会根据传递的参数类型自动生成函数。

如果声明和定义是分开的函数模板,声明部分和定义部分的前面都要加上template 以保证让编译器知道这是函数模板使用的数据类型。

注意:函数模板可能会缩短代码量但不会缩短可执行代码量,因为用不同的类型调用函数模板,会确确实实生成的不同函数,就像手工写了这两个函数一样。因此函数模板的本质就是给编译器一个自己写函数的模型。

函数模板的好处就是生成多个函数定义更简单更可靠。

更常见的形式是将模板放在头文件,并在需要时用的模板的文件中包含头文件。

需要对多种类型使用同一种算法时可以考虑函数模板,但是,并非所有的类型都使用相同的算法,因此,为了解决这个问题,可以像重载常规函数定义一样重载函数模板定义。但是同样要注意,要保证被重载的函数模板的特征标不同(在函数模板中,并非所有的参数为模板参数类型)。

函数模板的局限性

template
void f(T a,T b)
{
if(a > b)
a = b;
...
}

像这样的模板,如果a,b是普通的常规数据类型,也无大碍,但是如果a,b传入了数组,那么if比较的是两个地址没有意义,如果执行if里面的语句将是不合法的。

因此即使使用函数模板,但其中的小细节仍然需要注意语法。

对于上述也不是没有解决办法重载>和=运算符也可以实现。

显式具体化

如果想要交换两个值,传入的是两个结构,函数模板也能正常使用。但是我们传入两个结构,想交换其中两个结构的结构成员,那么我们就需要明确到底是什么结构的什么成员。这时候,单纯的函数模板就无法实现,我们需要显式具体化。

我们提供一个具体化函数定义,其中包含了所需代码,当编译器找到与函数匹配的具体化定义时,将使用该函数而不再寻找模板。

具体化方式有很多种,C++98采用了第三代具体化:

1.对于给定的函数名,可以有非模板函数、模板函数和显示具体化模板函数以及他们的重载版本

2.显示具体化的原型和定义应以template<>打头,并通过名称来指出类型

3.具体化优先于常规模板,而非模板函数优先于具体化和常规模板

如果交换job结构的示例:

//非函数模板
void Swap(job & a,job & b);

//常规函数模板
template
void Swap(T & a,T & b);

//显式具体化函数模板
template<> void Swap(job & a,job & b);

其中是可选的,因为函数的参数类型表明,这是job的一个具体化,也就是说可写可不写。但是,如果在参数类型中没有job,那么,写这个还是很关键的!

在使用显示具体化的时候和使用函数模板一样要声明定义都要加template<>

实例化

就像前面说的,模板不会生成函数,但可以调用模板之后,使模板实例化,从而生成实例函数,这被称为隐式实例化,早期的C++也只允许这么做,但现在C++允许显示实例化。这就意味着可以直接命令编译器创建特定的实例,耆域法师声明所需的种类用<>符号指示类型,并在声明前加上关键字template,如:

template void Swap(int ,int );

实现了这种特性的编译器看到上述声明之后将使用Swap模板生成一个使用int类型的实例。

当比较一下显式具体化:

template<> void Swap(job & a,job & b);
template<> void Swap(job & a,job & b);

还是有差别的,一定要注意,差别不仅仅是有无<>,更大的区别在于是否使用Swap模板创建函数,实例化是用Swap创建函数,而具体化是不使用模板创建一个新函数

实例化有什么用呢?

比如我们有int a,double b;

有个函数模板:

template
T add(T a,T b)
{
return a
}

int a = 1;
double b = 2;

cout (a,b)

这样就会强制使用double的实例。

隐式实例化,显示实例化,显式具体化统称具体化,他们的相同之处在于表示的都是适用具体类型的函数定义而不是通用描述。

最后,一定要注意,要区分使用template和template<>来使用显示实例化和显示具体化。

编译器选择使用哪个版本的函数

对于函数重载、函数模板和函数模板重载,C++需要有一个定义良好的策略来决定为函数调用使用哪个函数定义,尤其是有多个参数时,这个过程称为函数解析。过程:

1.创建候选函数列表,其中包括与被调用函数的名称相同的函数和函数模板

2.使用候选函数列表创建可行函数列表。这些都是参数数目正确的函数,为此有一个隐形转换序列,其中包括实参类型与相应的形参类型完全匹配的情况。

3.判断是否有最佳可行函数,否者报错。

那么,最后一步中的是否最佳的顺序如何确定呢?

1.完全匹配,但常规函数优先于模板

2.提升匹配,如(char,short提升为int后匹配)

3.标准转换,如(int转换为char,long转化为double)

4.用户定义的转换,如类声明中定义的转换。

C++允许某些无关紧要的匹配比如int匹配给const int,char[]和char *之类的。这意味着用作实参的函数名与用作形参的函数指针只要返回类型和参数列表相同,就是匹配了。

然而,有时候即使两个函数都完全匹配了,然可完成重载解析,首先,直线非const数据的指针和引用优先于非const指针和引用参数匹配。然而,const和非const之间的区别值适用于指针和引用指向的数据(const的影响,更强调与指针和引用)。

对于函数只有模板,那么,更为具体的模板优先。

对于只有需要转换的函数,那么,转换最少的函数优先(更具体)。

其实我们可以手动选择,比如在调用函数模板的时候

add<>(a,b);

这时选择模板优先有常规函数。

对于多参数的函数情况更复杂,编译器必须考虑所有参数匹配的情况,什么是一个合适的函数呢?

1.其所有参数的匹配程度都必须不比其他函数差

2.同时至少有一个参数的匹配程度比其他函数都高

C++11给了模板函数更大的发展。主要的进步在于添加了decltype关键字,用来确定数据类型。

那么,这种模板就成为了可能:

template
void Add(T1 a,T2 b)
{
decltype(a + b) ans = a + b;
}

这个是在过程中出现不知类型的中间变量就使用decltype关键字,如果返回类型呢?

C++11允许返回值后置

template
auto Add(T1 a,T2 b)
{
decltype(a + b) ans = a + b;
return ans;
}

强大的自动类型auto啊!

编译器如何确定使用哪个函数是个十分复杂的机制,还需后续了解。

2014/10/22 posted in  C++

C++第七章笔记

乐趣在于发现。


C++自带了一个包含函数的大型库,但真正的编程乐趣在于编写自己的函数。虽然语言越来越高级,C++也有强大的STL支持,但从创造到毁灭的乐趣才是无可替代的。

函数原型的功能

  1. 编译器正确处理函数的返回值
  2. 编译器检查使用的参数数目是否正确
  3. 编译器检查使用的参数类型是否正确

在C语言中,如果参数类型不正确则会导致错误,但是在C++中编译器会自动转化为正确的类型。(但是这样也会在函数重载中产生二义性),如果由大精度到小精度转换的时候编译器会发出警告,因此不要忽略任何一个警告。

有关数组方面,C++和C语言,将数组当指针处理。

至于数组和指针如何确定元素,《C++ PP》提出两个恒等式= =,

arr[i] == *(ar + i);

&arr[i] == ar + i;

tip:因为数组是指针传递,一定要注意数据保护,必要的时候可以使用const

对于程序设计,我们首先考虑的是通过数据类型和设计适当的函数处理数据,然后将这些函数组合成一个程序。有时也称为自下而上的程序设计,因为设计过程葱组件到整体进行。这种方法非常适合OPP,它首先强调的是数据表示和操纵。而传统的过程性编程倾向于从上而下的程序设计,首先制定模块化设计方案,然后再研究细节。这两种方法都很有用,优劣是相对而言的。最终的产品都是模块化程序。

对于把数组传参,一般有两种方法。

1.传递数组头地址和数组长度

2.传递数组头地址和尾地址。

第一种方法很常见,第二种方法挺有意思的。

对于double num[20];,我们可以传递num和num + 20,作为形参,指针num和num + 20定义了一个区间,是[num[0],num[19]],也就是说指向尾的指针是指向的最后一个元素的下一个元素(可能不存在)。

这样,对于数组遍历求和我们可以这样新颖的写:

for(pt = begin;pt != end;pt++)
total = total + *pt;

注意:根据指针减法规则,end-begin是一个整数值,等于数组的元素数目。

指针和const

指针和const的使用是一个很微妙的东西,可以有两种不同的方式将const关键之用于指针:

1.让指针指向一个常量对象,这样可以防止该指针修改所指向的值;

2.将指针本身声明为常量,可以防止改变指针指向的位置。

所有的操作,都是以这两个为基础的。

以前我们将常规变量的地址赋给常规指针,亦可以将常规变量的地址赋给指向const的指针(不可以用指针修改变量的值,但是可以用变量名修改)。因此还有两种可能性:

1.将const变量的地址赋给指向const的指针

2.将const的变量的地址赋给常规指针(非法)。

为什么第二种情况非法呢,因为常规指针是可以修改指向的值的,而指向的是一个const的值,那么编译器是不允许这么做的。

那么如果我们有一个const指针指向一个const常量,然后用一个指向指针指向这个const指针会如何呢?因为任何情况下编译器是允许将非const类型赋值给const指针的,因此描述二级间接关系,与一级间接关系一样将const和非const混合的指针赋值方式将不再安全。因此,仅当只有一层间接关系(如指针指向基本类型)时,才可以将非const地址或指针赋给const指针。

注意,如果数据类型本身并不是指针,则可以将const数据或非const数据的地址赋给指向const的指针,但只能将非const数据的地址赋给非const指针。

禁止将常量数据的地址赋给非常量指针将意味着不能讲数组名当做参数传递给使用非常量形参的函数。

因此,要尽可能的使用const

1.可以避免由于无意见修改数据而导致的编程错误

2.使用const使得函数可以处理const和非const实参,否则只能接受非const的数据。

如果条件允许,则应将指针形参声明为指向const的指针。

到底是指针是常量还是指针指向的常量呢?其实可以以为分界符,在左边有const就说明指向的内容不能改,在*右边就说明指针不能改,而左边的char和const顺序是不要紧的。

将指针作为函数形参来传递,可以使用指向const的指针保护。但是传递的必须是基本类型,比如

void show_array(const double ar[],int n);可以这样使用,但是如果这里的不是数组ar,而是指针甚至是指向指针的指针,不能保证只有一层的间接关系,则不能使用const。

对于函数和结构,要注意函数形参的特殊性,函数会把形参进行复制,如果结构过大,C语言一般采取传递地址的方法避免复制操作节省时间,而C++还支持引用。

函数和指针

指针和函数联用是个很高大上的东西,和数据一样,函数也是有地址的,这些地址对用户没有啥用,但是对于程序用处很大,可以编写将另一个函数地址作为参数的函数,这样第一个函数就能够找到第二个函数。使用起来将十分的灵活。

获取函数地址的方式和数组一样,函数名就是函数的地址。

对于声明函数指针,因为括号的运算级要高于号,所以声明函数指针时要加括号,比如:double (pf) (int);

其中pf便是指向形参为int,返回值为double的函数。

使用函数指针调用函数:

double pam(int);
double (pf)(int);
pf = pam;
double x = pam(4);
double y = (
pf)(5);

//C++还允许这样使用
double y = pf(5);

虽然第一种方式不好看,但他明确的提示——正在使用函数指针。

函数指针的表示可以非常的恐怖,实现的功能也可以十分恐怖,比如用一个函数指针数组存储几个函数,用for循环依次执行这几个函数

但对于太恶心的指针可以使用auto,auto只允许但只初始化,不允许列表初始化。

自动类型推断确保变量的类型与赋给它的初值的类型一致,但一定要保证提供的初值的类型正确。


第七章终于写完了,要在一堆已经会的东西找出不太牢固的着实是个耐心活><,写到现在也是醉了。

2014/10/21 posted in  C++

C++第六章笔记

第六章主要讲的是分支语句、逻辑运算符和文件读写入门,分支结构没有什么可以总结的,C++的分支结构和C完全一样。

但在逻辑运算符方面,C++居然支持直接用and,or,not来代替&&,||,!。也就是说,C++将前三个单词作为保留字(但不是关键字),不可以将前三个单词作为变量名。

C++在C上完美继承了字符处理的相关函数集,在C++中封装在cctype(原ctype.h)头文件。

其中常用函数:

函数名称 返回值
isalnum() 如果参数是字母数字,即字母或数字,该函数返回true
isalpha() 如果参数是字母,该函数返回真
isblank() 如果参数是空格或水平制表符,该函数返回true
iscntrl() 如果参数是控制字符,该函数返回true
isdigit() 如果参数是数字(0~9),该函数返回true
isgraph() 如果参数是除空格之外的打印字符,该函数返回true
islower() 如果参数是小写字母,该函数返回true
isprint() 如果参数是打印字符(包括空格),该函数返回true
ispunct() 如果参数是标点符号,该函数返回true
isspace() 如果参数是标准空白字符,如空格、进纸、换行符、回车、水平制表符或者垂直制表符,该函数返回true
isupper() 如果参数是大写字母,该函数返回true
isxdigit() 如果参数是十六进制的数字,即0~9、a~f、A~F,该函数返回true
tolower() 如果参数是大写字符,则返回其小写,否则返回该参数
toupper() 如果参数是小写字母,则返回其大写,否则返回该参数

文件输入输出入门

和C不一样,C++实现文件输入输出的方式几乎和对标准输入输出的方式一样。

C++通过对ostream类和istream类来实现标准输入输出的,而文件是依靠ofstream类和ifstream类来实现,并且包含在fstream头文件中。

我们可以自己定义ofstream类和ifstream类的对象,用成员函数open打开它,使用运算符>进行操作,用完后用close关闭它。

写入到文本文件

ofstream outFile;
ofstream fout;
outFile.open("text.txt");
char s[100];
cin >> s;
fout.open(s);
double data;
cin >> data;
outFile

应用起来十分方便,十分高大上。

文件输入输出可以使用标准输入输出的任何方法(我都怀疑文件输入输出是标准输入输出的继承),比如格式化方法如setf()和precision()。当然,这些函数只影响调用它们的对象。

在默认情况下,打开一个文件时发现文件不存在,则会新建这个文件,如果存在这个文件,则会先把文件清空,然后重新写(也就是清零了)。

读取文本文件

ifstream inFile;
ifstream fin;

inFile.open("text.txt");
char s[100];
cin >> s;
fin.open(s);

double data;
inFile >> data;

char line[80];
fin.getline(line.80);

一样的高大上。

如果文件打开失败,则is_open()返回TRUE,反之返回FALSE,因此可以判断是否成功打开了文件。

在文件操作头文件里,还定义了用于同操作系统通信的参考值EXIT_FAILURE,函数exit()终止程序。

if(!inFile.is_open())
{
exit(EXIT_FAILURE);
}

因为文件操作意外挺多,所有有个good类方法,来确定操作有木有成功。

所以建议每操作一次就检查一下good是否返回TRUE,

inFile >> value;

while(inFile.good())
{
inFile >> value;
}

因为inFile的返回值就是inFile.good()(和cin类似),所以可以简化:

while(inFile >> value)
{
;
}

2014/10/13 posted in  C++