C++ Library(3)

C++ Library(3)

8.结构体 struct(2)

下面我们来进一步了解结构体

8.1 构造函数

我们还是以Point类型为例

如果我们想要获得一个x=1,y=2Point, 目前可以怎么做?

Point p;
p.x = 1, p.y = 2;

这样未免不太优雅, 而且效率上也略有损失(当我们需要赋值的东西更多的时候, 这样的损失更大)

有方法可以直接「构造」出一个我们想要的Point吗?

构造函数!

一个结构体的构造函数是一个「返回这种类型」的函数, 作用上相当于构造了一个此类型, 因而得名「构造函数」(constructor)

struct Point
{
    int x, y;
    Point (int xx, int yy) : x (xx), y (yy) {}
};

Point p1 = Point(1,2);//这样就可以用这种方式来构造Point了, p1就是一个x=1, y=2的Point
Point p2(1, 3);
  • 构造函数是特殊的函数, 函数名等于「类型的名字」, 这里的Point类型的构造函数的名字也叫Point
  • 括号内填你想用来构造一个Point所需的参数(同普通函数)
  • 参数列表后跟一个「初始化列表」, 具体形式为变量名(给它赋的值), 多个「初始化」语句用括号隔开
  • 「初始化列表」之后就是函数体, 这里因为我们没有什么要做的了, 所以只跟了一对空的花括号
  • 构造函数不需要return, 因为默认return的就是构造好了的Point

当然, 你也可以这么写, 但是不推荐

struct Point
{
    int x, y;
    Point (int xx, int yy)
    {
        x = xx, y = yy;
    }
};

至于为什么, 这就涉及到了「初始化」和「赋值」的区别了, 这里略去. 总之: 尽量使用「初始化列表」的方式来写

但是, 仅仅这样写构造函数的话, 如果你的程序中还有有类似于这样的语句:

Point p;

那么就会报错, 因为: 你只定义了「有两个参数的时候的构造函数」, 而这里你没有定义这种情况下Point应该如何构造, 编译器懵逼了, 所以抛出了这个Error

所以, 我们只需要再添加一个「默认构造函数」(也就是没有任何参数时候的构造函数)就可以了:

struct Point
{
    int x, y;
    Point() : x (0), y (0) {}
    Point (int xx, int yy) : x (xx), y (yy) {}
};
Point p;//这样默认就是(0, 0)

或者, 还有更加高级一点的方法, 利用「函数参数默认值」:

struct Point
{
    int x, y;
    Point (int xx = 0, int yy = 0) : x (xx), y (yy) {}
};

这样当缺少参数时, xx.yy会默认为0, 也就达到了我们想要的效果

8.2 重载运算符

  • 运算符是特殊的函数

所以重载运算符和定义/重载函数是基本一样的语法

我们往往需要这样的功能, 对一个自定义的结构体数组进行排序, 比如:

P1051 谁拿了最多奖学金中, 我们可以定义一个「学生类型」:

struct Student
{
    string name;
    int final_grade;
    int class_evaluation;
    bool cadres;
    bool western_provinces;
    int papers;
    int scholarship;
} student[MAXN];

然后我们需要求出拿了最多奖学金的那个人, 那么我们就需要对student数组排序. 那么, 我们就需要知道「如何比较两个student」; 或者说: 我们需要让编译器知道「如何比较两个student」, 再进一步, 我们需要定义student<小于号运算符.

bool operator < (const Student &a, const Student &b)
{
    return a.scholarship < b.scholarship;
}

重载运算符的定义和函数的定义非常相似, 唯一的区别在于「函数名」不是自定义的了, 而是operator <op>的形式, 其中<op>为你想重载的运算符.

我们都知道, <小于号是一个「二元运算符」, 需要两个参数(来进行比较). 并且返回一个bool值.

注意: 这里的参数使用了「const引用」, 是为了具有更好的通用性, 记住即可.

这样, 我们就可以直接调用sort啦:

sort (student + 1, student + n + 1);

同理, 你也可以重载更多的运算符, 比如你可以重载Pointint相加, 你甚至可以重载下标运算符[], 逗号运算符,, 但是请注意, 你不能重载内置类型和内置类型的运算, 比如你不能重载int+int

9.双向队列 deque

  • queue,priority_queue一样, 包含在<queue>
  • 顾名思义, 支持从队首和队尾插入和删除
#include <iostream>
#include <queue>

using namespace std;

int main()
{
    deque<int> q;
    q.push_front (1); //从队首插入,{1}
    q.push_back (2); //从队尾插入,{1,2}
    q.push_back (3); //{1,2,3}
    q.push_front (4); //{4,1,2,3}
    q.push_back (5); //{4,1,2,3,5}
    q.push_front (6); //{6,4,1,2,3,5}
    q.push_back (7); //{6,4,1,2,3,5,7}
    q.push_front (8); //{8,6,4,1,2,3,5,7}
    while (!q.empty())
    {
        cout << q.front() << ' ' << q.back() << endl;//分别输出队首和队尾
        q.pop_front();//从队首删除
        q.pop_back();//从队尾删除
    }
    return 0;
}

10.<cctype>

isdigit(char)//判断是否为整数字符’0′-‘9’

isalpha(char)//判断是否为字母字符’a’-‘z’

isupper(char) //判断是否为大写字母字符

islower(char) //判断是否为小写字母字符

toupper(char&) //转大写

tolower(char&) //转小写

11.<cmath>

pow(x, n)//求x的n次方, 返回一个浮点数

log(x)//返回x的自然对数(以e为底的对数)

log10(x)//返回x的常用对数(以10为底的对数)

log2(x)//返回x的以2为底的对数

min(x, y)//返回x和y中的较小值

思考题1: 实现下列函数, 要求不得调用其它函数(如min, max)、不得使用与逻辑相关的语法(如比较运算符>,<,==; if语句; 三目运算符?:等)

unsigned int my_max(unsigned int a, unsigned int b)//求两个非负整数的最大值
{

}

解答:

unsigned int my_max (unsigned int a, unsigned int b)
{
    return (a * (a / b) + b * (b / a)) / (a / b + b / a);
}

a<b时,a/b=0,所以前面为b*(b/a),后面为b/a,那么结果就是b
a=b时,a/b=1,所以前面为a+b=2a,后面为2,那么结果就是a
a>b时,b/a=0,所以前面为a*(a/b),后面为a/b,那么结果就是a

12.快速读入

  • cin/cout
  • scanf/printf
  • gets/puts

快速读入非负整数:

inline int getint()
{
    int x = 0;
    char c = getchar();
    while (!isdigit (c)) c = getchar();
    while (isdigit (c))
    {
        x = x * 10 + c - 48;
        c = getchar();
    }
    return x;
}

思考题2: 如何实现快速读入整数、浮点数?

C++ Library(2)

C++ Library(2)

4.字符串 string

4.1 定义

string代表字符序列(字符串),如”haha”、”Hello world! “等都可以称之为字符串(严格一点说,是字符串”值”)

4.2 常用运算

  • operator +

“`C++
string a = “1”;
string b = “2”;
string c = a + b;
cout << a + b << endl;


字符串可以直接相加, 结果等于两个字符串顺次连接 > > 练习1: 已知`string s = "1";` 下列哪些语句会编译错误? A.`string a = s + "2";` B.`string b = "1" + s + "2";` C.`string c = s + 1;` D.`string d = s + '2';` ### 4.3 常用函数 #### size()/length() 不多说 #### 插入insert(),删除erase(),替换replace(),子串substr() 参数形式较为统一:起始位置、长度、字符串(后两个参数依据具体函数而情况不同) ```c++ string a = "HelloWorld!"; // 0123456789 a.insert(5, ","); //Hello,World! a.erase(5, 5); //Hello! a.replace(5, 5, "OI"); //HelloOI!

值得注意的是,string在对非结尾处进行插入、删除、替换的时候的效率是较低的,在暴力的时候要慎重考虑使用。

一般情况下我们只使用string的+、[]、size()等操作

查找find()

string.find(要找的字符或字符串, 起始位置);

起始位置可以不填, 不填则默认为0

返回找到的第一个位置的下标, 没找到则返回一个常数string::npos, 这个常数是一个「机器相关」的数字, 转成int的时候「通常」为-1, 所以我们通常直接用string::npos而不用-1来判断

string s = "Hello world!";
cout << s.find ("o") << endl; // 输出4
cout << s.find ("o", 5) << endl; //输出7
cout << s.find ("o", 8) << endl; // 本机输出18446744073709551615
cout << (int) s.find ("hello", 8) << endl; // 本机输出-1

那么, 如何输出一个字符串中某个串出现的所有位置呢?

string s = "abcsasdqaweawqfdgadfsjhxacvazhwuaeyr";
string x = "a";
int pos = s.find (x); //先找到第一个位置
while (pos != string::npos)
{
    cout << pos << endl;
    pos = s.find (x, pos + 1);
}

练习2:P2799 国王的魔镜

推荐使用「递归」和string的一些函数

5.集合 set

C++中的集合set底层实现是平衡二叉树, 可以进行插入删除等操作来维护一个有序的集合, set的(中间)插入、删除等操作比序列容器vector要快很多

注意:set是默认没有重复元素的

常用操作:

set<int> s;
s.insert (1);//此时s中元素为{1}
s.insert (3);//此时s中元素为{1,3}
s.insert (2);//此时s中元素为{1,3,2}
s.insert (1);// 集合是没有「重复元素」的, 所以这句话没有产生什么影响
cout << s.size() << endl;
cout << s.count (1) << endl;//输出1, 最多也只会有一个元素, 所以count函数一般可以用来判断是否存在集合中
s.erase (2);
cout << s.count (2) << endl;//2被删除了, 所以输出0

练习3:P3370 【模板】字符串哈希

使用set水过去!

6.映射 map

map,可以看作是set的加强版, 大多数时候可以替代set

map表示的是一种「映射关系」, 并且是任意的映射关系(这取决于你想怎么映射)

我们最常用的一种映射关系就是int数组, 这是一种「int」到「int」的映射关系, 每一个int(当然必须在下标范围内)都「对应」着另一个int

对应于map,我们可以写一个「不算太无聊」的程序来作为示例:

map<int, int> mii;//建立一个int到int的映射
mii[1] = 1; //是不是很像数组?
mii[-1] = 1; //不过这个数组的「下标」只要是int就可以了
mii[1000000000] = 1;//如果是数组这样写, 内存就爆了
//不用担心这样子会产生很多内存, 实际上只产生了3份(因为map是动态申请的内存), 几乎忽略不计了
cout << mii.size() << endl;//输出3, 我们的map并没有占用很多空间
cout << mii[5] << endl;//虽然我们之前没有给这个位置赋值, 但是当我们直接访问的时候, map发现mii[5]不存在的话, 会自动创建一个, 并且初始化一个默认值(对于整数int, 当然就是0)
cout << mii.count (8) << endl; //输出0, 因为8并不在map里面(我们还没有用过8), 使用count函数并不会自动创建8, 所以我们可以用count来帮助判断map里面是否有这个键(key)
cout << mii.count (5) << endl; //输出1, 因为之前访问过mii[5]了, 所以5已经存在于map里面了
mii.erase (5);
cout << mii.count (5) << endl; //输出0, 因为5被我们删除了

同时还可以有非常多的应用:

map<string, int> msi;//建立一个string到int的映射
msi["sunlaoshi"] = 100;
msi["zhalaoshi"] = 90;
msi["wanglaoshi"] = 0;

练习4:P1032 字串变换

双向BFS, queue/string/map综合应用

7.迭代器 iterator

类似于指针, 比指针更高级和安全

map<int, int> cnt;
for (map<int, int>::iterator it = cnt.begin(); it != cnt.end(); ++it)
{
    cout << (it->first) << ' ' << (it->second) << endl;
}

练习5:P1097 统计数字

map+迭代器水过去

C++ Library(1)

C++ Library(1)

0.结构体 struct

0.1 定义

有时我们需要定义自己的「数据类型」,比如平面上的点,需要由两个数字来表示. 也就是每一个「点类型」对应两个「整数类型」

让我们来定义我们自己的数据类型Point:

struct Point
{
    int x, y;
};

这段代码的作用是定义结构体, 或者通俗一点说: 告诉编译器, 我要定义一种类型, 类型名字叫做Point, 其中1个Point由2个名字分别为x,y的整数构成

structC++中的关键字, 类似于if,else等. 定义语句要注意结尾的分号(第4行).

Point是要定义的类型的名字, 类似于给变量取名字.

x,y是结构体的「成员」类型的名字

0.2 实例化

定义完Point类型之后, 我们可以来定义一些Point类型的变量

Point p;
Point arr_p[10];

基本上就相当于把Point当作int,char这些内置类型来用

0.3 访问成员

Point p;
p.x = 1;
p.y = 2;
cout << p.x << ' ' << p.y <<endl;

通过「成员运算符 member operator」.来访问/调用Point类型变量p的成员, p.x,p.y的类型显然是int

同理也可以输入之类的

Point arr_p[10];
for (int i = 1; i < 10; i++)
{
    cin >> arr_p[i].x >> arr_p[i].y;
}

0.4 成员函数

比如我们想用一个函数来算一个点到原点的距离, 但是这个函数显然是和Point这个类型高度「耦合」的, 这个时候我们「最好」定义一个「成员函数」

struct Point
{
    int x, y;
    double distance()
    {
        return sqrt (x * x + y * y);
    }
};

其中第4行到第7行就是「Point类型的成员函数的定义」, 定义基本上和普通的函数一模一样, 不过值得注意的是, distance()函数内可以直接访问「当前结构体内的成员」,比如x,y

distance()函数被封装在了Point类型里面, 外部不能直接访问, 也只能通过「成员运算符」.

Point p;
p.x = 1, p.y = 1;
cout << p.distance() << endl;
  • 到这里, 你有没有什么联想呢?
struct string
{
    // declare something
    int size()
    {
        // return something
    }
};

// when you write your program like this:
string s = "123asd";
int l = s.size();
// do something

1.队列 queue

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(back)进行插入操作。

队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

#include <iostream>
#include <queue>//STL容器通常需要包含与其同名的头文件
using namespace std;//STL:Standard Template Library 标准模板库
int main()
{
    queue<int>q;//定义一个'装'int类型,名字为q的队列.初始时q为空队列
    q.push (1); //调用队列q的「成员函数」push,将一个整数1加入队列
    q.push (3); //同上,此时队列中依次为1,3
    q.push (2); //同上,此时队列中依次为1,3,2
    cout << q.size() << endl;//输出3,即当前队列元素个数
    //size()是队列q的一个成员函数,返回q中包含的元素个数,几乎所有STL容器都有size()函数,记得size后面有一对「小括号」
    while (!q.empty()) //同理,empty()也是队列q的一个成员函数,望文生义:如果q当前是空的,就返回true;否则返回false
    {
        //while中的判断条件即为"当q不为空就一直做",在BFS(广度优先搜索)中经常见到
        cout << q.front() << ' '; //front()返回q的队首元素
        q.pop();//队首元素出队,这样可以遍历q中的所有元素
    }
    return 0;
}

练习1:#include <iostream> #include <stack>//STL容器通常需要包含与其同名的头文件 using namespace std;//STL:Standard Template Library 标准模板库 int main() { stack<int> s;//定义一个'装'int类型,名字为s的栈.初始时s为空栈 s.push (1); //调用栈s的「成员函数」push,将一个整数1加入栈 s.push (3); //同上,此时栈中依次为3,1 s.push (2); //同上,此时栈中依次为2,3,1 cout << s.size() << endl;//输出3,即当前栈元素个数 //size()是栈s的一个成员函数,返回s中包含的元素个数,几乎所有STL容器都有size()函数,记得size后面有一对「小括号」 while (!s.empty()) //同理,empty()也是栈s的一个成员函数,望文生义:如果s当前是空的,就返回true;否则返回false { cout << s.top() << ' '; //front()返回s的栈顶元素 s.pop();//栈顶元素弹栈(退栈),这样可以遍历s中的所有元素 } return 0; }

练习2:P1739 表达式括号匹配

练习3:P1449 后缀表达式

3.优先队列 priority_queue

普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。

在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。

优先队列通常采用堆数据结构来实现。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
    priority_queue<int> pq; //默认是越「大」的元素「优先级」越高,也就是越先出队
    //priority_queue<int, vector<int>, greater<int> >pq;
    //如果你想让越「小」的元素「优先级」越高,像被注释的上一行这样做,记得包含<vector>
    pq.push (1);
    pq.push (3);
    pq.push (2);
    while (!pq.empty())
    {
        cout << pq.top() << ' ';//访问队首(堆顶),即最大元素
        pq.pop();//队首(堆顶)出队
    }
    return 0;
}

练习4:P3378 【模板】堆

练习5:P1090 合并果子

MinGW中的两组头文件(c++/和c++/tr1/)

今天在搜索cstdio文件时发现有两个,分别位于

mingw-w64\x86_64-8.1.0-posix-seh-rt_v6-rev0\mingw64\lib\gcc\x86_64-w64-mingw32\8.1.0\include\c++
mingw-w64\x86_64-8.1.0-posix-seh-rt_v6-rev0\mingw64\lib\gcc\x86_64-w64-mingw32\8.1.0\include\c++\tr1

唯一的区别只是后者在这个tr1的子文件夹下.
什么是tr1?

C++ TR1 是ISO/IEC TR 19768 C++ Library Extensions(函式库扩充)的一般名称。TR1 是一份文件,内容提出了对C++标准函式库的追加项目。这些追加项目包括了正则表达式、智能指针、哈希表、随机数生成器等。TR1自己并非标准,他是一份草稿文件。然而他所提出的项目很有可能成为下次的官方标准。这份文件的目标在于「为扩充的C++标准函式库建立更为广泛的现成实作品」。
C++ tr1是针对C++标准库的第一次扩展。即将到来的下一个版本的C++标准c++0x会包括它,以及一些语言本身的扩充。tr1包括大家期待已久的smart pointer,正则表达式以及其他一些支持范型编程的内容。草案阶段,新增的类和模板的名字空间是std::tr1。

经过测试,一般情况下编译器调用的是前者的头文件.