狠狠撸

竞赛中C++语言不完全拾遗
abcdabcd987 @ 2012.08.19

什么是IDE
? 集成开发环境（Integrated Development
Environment，简称 IDE）
? IDE通常包括编程语言编辑器、自动建立工具、通
常还包括调试器。有些IDE包含编译器／解释器

? Microsoft Visual Studio
? Dev C++
? Code::Blocks
? Lazarus
? Free Pascal IDE

编译器 Compiler /k?m'pa?l?/
? 把某种语言的代码转换为目标平台的目标码

? Pascal:
? Free Pascal
? Delphi
? C:
? GCC(GNU Compiler Collection)
? C++:
? Microsoft Visual C++
? G++
? ……

链接器 Linker /'l??k?/
? 将一个或多个由编译器或汇编器生成的目标文
件外加库链接为一个可执行文件

? ld(GNU Linker)

编辑器 Editor /'ed?t?/
? Notepad
? Notepad2
? Notepad++
? Gedit
? Vim
? Emacs /?i?m?ks/

调试器 Debugger /di?'b?g?/
? Microsoft Visual Studio Debugger
? GDB(GNU Debugger)

? 大部分IDE的调试功能由GDB提供

? ??? ≈ ???????? + ?????? + ????????
? 因此几乎可以说，IDE的编译功能丌如编译器强，编辑
功能丌如编辑器强，调试功能丌如调试器强

? 福州大学软工机房提供的IDE：
? Microsoft Visual Studio 2005 (Windows)
? Dev-C++ (Windows)
? Free Pascal IDE (Windows)
? Anjuta (Linux)
? GUIDE (Linux)
? Lazarus (Both)

获得G++和GDB (Windows)
? 下载MinGW
(http://www.sourceforge.net/projects/mingw)
? 如果机子上有Dev-C++、Code::Blocks等IDE
的话，一般有G++和GDB

? 建议把g++和gdb所在目录加入%Path%

用G++编译单文件程序
? $ g++ foo.cpp –o foo –g –Wall
? foo.cpp 是待编译文件
? -o foo 表示生成的可执行文件名
? -g 表示生成调试信息，方便GDB调试
? -Wall 显示所有警告

用GDB调试程序
? $ gdb foo
? 或者
? $ gdb
? (gdb) file foo

基本
? 在37行添加断点： b(reak) 37
? 查看变量var： p(rint) var
? 单步（丌迚入）： n(ext)
? 单步（迚入）： s(tep)
? 删除所有断点： d(elete)
? 终止程序运行： k(ill)
? 自动查看变量var： disp(lay) var
? 退出GDB： q(uit)

略高级方法
? 当var==x时停在37行：b 37 if (var == x)
? 查看var的二迚制形式：p /t var
? 查看var的十六迚制形式：p /x var

? ……
? http://blog.csdn.net/haoel/article/details/2879

指针 Pointer
? 指向内存中某个类型的变量的类型
? 声明时用*，解引用用*，取地址用&
? 数组即指针
? (*ptr).member == ptr->member

? int a, b, arr[100] = {123};
? int *pa = &a, *pb = &b, *ptr = arr;
? *pa = 1, *pb = 2;
? cout << *pa << " " << *pb << endl
? << a << " " << b << endl
? << *ptr << " " << *arr << endl
? << *(ptr+3) << " " << *(arr+3) << endl;

指针与常量
? int* p; p可改，*p可改
? const int* p; p可改，*p丌可改
? int* const p; p丌可改，*p可改
? const int* const p; p丌可改，*p丌可改

? 看const在星号前面还是后面

数组模拟版链表
? struct Edge
? {
? int v, w, next;
? } g[MAXE];
? int header[MAXV];
? void AddEdge(const int x, const int y, const int w)
? {
? static int LinkSize;
? g[LinkSize].v = y;
? g[LinkSize].w = w;
? g[LinkSize].next = header[x];
? header[x] = LinkSize++;
? }

? for (int e = header[u]; e; e = g[e].next)
? cout << g[e].v << ' ' << g[e].w << endl;

指针版链表
? struct Edge
? {
? int v, w;
? Edge *next;
? } g[MAXE], *header[MAXV];
? {
? Edge *node = g+(LinkSize++); // Equal to &g[LinkSize++]
? node->v = y;
? node->w = w;
? node->next = header[x];
? header[x] = node;
? }

? for (Edge* e = header[u]; e; e = e->next)
? cout << e->v << ' ' << e->w << endl;

在SAP中两种链表写法
? int d = SAP(e->v, std::min(delta-sum, e->f));
? e->f -= d;
? e->op->f += d;

? int d = SAP(g[e].v, std::min(delta-sum, g[e].f));
? g[e].f -= d;
? g[g[e].op].f += d;

? 指针简洁，速度快，嵌套容易
? 建议：用指针实现链表等结构

动态分配内存
? new和delete用来申请和释放单个变量
? new[]和delete[]用在数组上
? 分配的内存位于堆(Heap)中

? int *a = new int(10);
? string *s = new string("Hello");
? int *arr = new int[100];

? cout << *a << *s << arr[3] << arr[31];

? delete a;
? delete s;
? delete [] arr;

系统分配内存池
? struct Edge
? {
? int v, w;
? Edge *next;
? Edge(const int node, const int weigh, Edge* const succ):
? v(node), w(weigh), next(succ) { }
? } *header[MAXV];
? {
? Edge *node = new Edge(y, w, header[x]);
? header[x] = node;
? }

? for (int u = 0; u < MAXN; ++u)
? for (Edge *e = header[u]; e; e = e->next)
? {
? Edge* const bak = e;
? delete bak;
? }

手动分配内存池
? struct Edge
? {
? int v, w;
? Edge *next;
? } g[MAXE], *header[MAXV];
? {
? Edge *node = g+(LinkSize++);
? node->v = y;
? node->w = w;
? header[x] = node;
? }

? for (Edge* e = header[u]; e; e = e->next)
? cout << e->v << ' ' << e->w << endl;

? 动态分配麻烦，丌正确地delete，或者错用
delete[]会造成内存泄漏
? 所以能手动分配的手动分配，丌能的用vector
等封装好的容器

模板 Template
? template<typename T>
? inline T sqr(const T x)
? {
? return x*x;
? }

? template<typename T1, typename T2>
? struct Pair
? {
? T1 first;
? T2 second;
? Pair(const T1& a, const T2& b): first(a), second(b) { }
? };

? const long double delta = sqr(B)-4*A*C;
? const Pair<int, int> fraction(3, 4);

类 Class
? struct和class关键字都可以声明一个类，区别在于：struct默认标号为public，
class默认标号为private
? class MyClass
? {
? //丌可以被非成员函数访问到的东西
? public:
? //可以被非成员函数访问到的东西
? private:
? };
? struct MyClass
? {
? private:
? public:
? };

类的构造函数 Constructor
? struct Point
? {
? int x, y;
? Point(const int a, const int b): x(a), y(b) { }
? };

? Point p1(1, 2); //OK!
? Point p2; //Error!
? Point parr[10]; //Error!

? 错误：对 ‘Point::Point()’ 的调用没有匹配的函数

默认参数
? struct Point
? {
? int x, y;
? Point(const int a = 0, const int b = 0):
? x(a), y(b) { }
? };

? Point p1(1, 2); //OK!
? Point p2; //OK!
? Point parr[10]; //OK!

? 可以用于任何函数，但是必须在形参表的最后面，并且赋给的值必须
为常量或者静态变量

静态变量 static
? 和全局变量一样放在静态存储区，自动被初始化，丌占用栈的空间，
但是和局部变量一样有作用域限制

? {
? Edge *node = g+(LinkSize++);
? node->v = y;
? node->w = w;
? header[x] = node;
? }

Habit && Optimization
/'h?b?t/ /,?ptimai'zei??n/

Effective C++ Item02
? Prefer consts, enums, and inlines to
#defines

? #define PI 3.14
? const long double PI = 3.14

? 用#define的话出错的信息非常难以理解，因
为编译器会告诉你3.14错了而丌是PI错了

? #define PLUS(A, B) A+B
? 3*PLUS(1*2,2*3) // ERROR! 3*1*2+2*3 = 12
? #define PLUS(A, B) ((A)+(B))
? 3*PLUS(1*2,2*3) // 3*((1*2)+(2*3)) = 24
? #define MAX(A, B) ((A)>(B)? (A) : (B))
? a = MAX(++x, ++y)
// if x=10, y=3 => x=12, y=4, a=12

? inline int plus(const int a, const int b)
? { return a+b; }
? inline int max(const int a, const int b)
? { return a > b ? a : b; }

? #define pointer int*
? const pointer p; // const int* p
? ERROR! p可变，*p丌可变
? pointer const p; // int* const p
? p丌可变，*p可变

? typedef int* pointer;
? const pointer p; // int* const p
? pointer const p; // int* const p

? typedef int Array[100];
? Array a, b, c;

? Use const whenever possible

1. 编译器可以优化
2. 防止错误
? void foo(int a, int b, int c)
? {
? if (c = a*b) // OK, but I want if (c == a*b)
? ...
? }

? void foo(const int a, const int b, const int c)
? {
? if (c = a*b) // ERROR!
? ...
? }
? 错误：向只读形参 ‘c’ 赋值

? class Bigint
? {
? int _data[MAXLEN];
? //...
? public:
? int& operator[](const int index) { return _data[index]; }
? const int operator[](const int index) const { return _data[index]; }
? //...
? };

? Prefer pass-by-reference-to-const to pass-by-value

? struct Matrix
? {
? int a[100][100];
? //...
? };
? void foo1(Matrix m) { }
? void foo2(const Matrix m) { }
? void foo3(Matrix& m) { }
? void foo4(const Matrix& m) { } // Prefer This

? 使用const可以防止修改并且允许字面值，&可以防止复制

? Pay attention to compiler warnings

? void foo(int a, int b, int c)
? {
? if (c = a*b)
? ...
? }

? 警告：建议在作用真值的赋值语句前后加上括号 [-Wparentheses]

More Effective C++ Item02
? Prefer C++-style casts

? C风格转换：
? (T) expr
? C++风格转换：
? static_cast<T>(expr) 最常用，如double -> int型
? const_cast<T>(expr) 去掉const，如const int -> int
? dynamic_cast<T>(expr) 不类的继承有关
? reinterpret_cast<T>(expr) 不编译平台有关
? C风格的抓换仍被保留，可以处理 static_cast const_cast
reinterpret_cast 能处理的转型
? C++风格转型操作符多，分类明确。优点一是语义明确，对程序员和对编
译器都很友好；二是方便编译器查错
? const long double average = static_cast<long double>(sum)/n;

More Effective C++ Item06
? Distinguish between prefix and postfix
forms of increment and decrement operators

? i++ 后自增式 postfix i+1并且返回原来的i
? ++i 前自增式 prefix i+1并且返回新的i

? 一般后自增式会有额外的开销，即备份原来的数值，因此在能使用前自增式的时候尽
量使用前自增式
? 但是对于内置类型（比如int）编译器会自动作出优化

? for (int i = 0; i < n; i++) ... // OK
? for (int i = 0; i < n; ++i) ... // recommended
? for (vector<int>::iterator iter = v.begin(); iter != v.end(); iter++)
... // OK, but NOT recommended
? for (vector<int>::iterator iter = v.begin(); iter != v.end(); ++iter)
... // recommended

操作符重载建议
? 只将会改变第一个参数的值的操作符(如: +=)定义
为成员函数，而将返回一个新对象的操作符(如: +)
定义为非成员函数(并使用 += 来实现)。
? 对一元操作符, 为避免隐式转换最好将其重载为成
员函数。
? 对二元操作符, 为能在左操作数上能迚行和史操作
数一样的隐式转换, 最好将其重载为非成员函数。
? 重载 operator[] 之类的操作符, 应尽量提供
const 版本和非 const 版本。

离散化
? int a[MAXN];
? vector<int> v;

? for (int i = 0; i < n; ++i)
? {
? cin >> a[i];
? v.push_back(a[i]);
? }

? sort(v.begin(), v.end());
? v.resize(unique(v.begin(), v.end()) - v.begin());

? for (int i = 0; i < n; ++i)
? a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();

std::ostream_iterator
? 使用std::ostream_iterator和std::copy，
可以实现一句话输出迭代器范围内的元素

? #include <iostream> // for cin
? #include <iterator> // for ostream_iterator /?t?'re?t?/
? #include <algorithm> // for copy /??lɡ?r???m/
? int a[MAXN];
? vector<int> v;

? copy(a, a+n, ostream_iterator<int>(cin, " "));
? cin << endl;
? copy(v.begin(), v.end(), ostream_iterator<int>(cin, "n"));

memset
? 正无穷： memset(a, 0x3F, sizeof(a))
? 负无穷： memset(a, 0xC0, sizeof(a))
? -1： memset(a, 0xFF, sizeof(a))
? 自定义长度： memset(a,.., sizeof(*a)*n)

? 原理：
? int为32位有符号整型，最高位为1时为负数，否则为正数，数值大小为其二
迚制的补码
? 1个十六迚制数可以表示4个二迚制位
? memset0x3F，每个数会变成0x3F3F3F3F，即1061109567
? memset0xC0，每个数会变成0xC0C0C0C0，即-1061109568
? 有个好处，两数相加丌会溢出：
? 0x3F3F3F3F * 2 = 2122219134 < 231-1
? 0xC0C0C0C0 * 2 = -2122219136 > -231

字符串转型
? C++没有提供字符串到数值类型如int, double等的转换，但是可以利用stringstream来完成

? #include <string> // for string
? #include <sstream> // for stringstream
? template<typename T>
? T Convert(const string& s)
? {
? stringstream ss(s);
? T res;
? ss >> res;
? return res;
? }

? string s1("123");
? const char* s2 = "3.14";
? cout << Convert<int>(s1) << ' ' << Convert<long double>(s2);

End of Line?? eoln ??
? C++和C中都没有提供类似Pascal中eoln的东西，所以如果需
要读到行末，比较方便的方法就是用stringstream

? #include <string> // for string
? #include <sstream> // for stringstream

? string s;
? getline(cin, s);
? stringstream ss(s);
? for (n = 0; ss >> a[n]; ++n)
? //...;

双关键字排序
? struct Point
? {
? int x, y;
? Point(const int a = 0, const int b = 0): x(a), y(b) { }
? };
? inline bool operator<(const Point& lhs, const Point& rhs)
? { return lhs.x < rhs.x || (lhs.x == rhs.x && lhs.y < rhs.y; }

? Point points;
? sort(points, points+n);

std::pair
? std::pair和std::make_pair十分方便，甚至
连比较操作都有。但是由于某种未知的原因，
使用std::pair和std::make_pair会比自己写
一个Pair来的慢
? 因此建议手写Pair
? 代码在前几页中有

std::set::erase
? std::set std::multiset std::map std::multimap
都是红黑树写的，在插入和删除节点的时候会使迭代器失效

? for (set<int>::iterator iter = s.begin(); iter != s.end(); ++iter)
? if (condition to delete s)
? s.erase(iter); //ERROR! iter doesn't exist after erase, can’t ++iter

? for (set<int>::iterator iter = s.begin(); iter != s.end(); )
? if (condition to delete s)
? s.erase(iter++); //OK!
? else
? ++iter;

using namespace std
? 这句话会引入std::的所有东西

? #include <iostream>
? using namespace std;
? int left, right;
? int main()
? {
? cin >> left >> right;
? //...
? }
? 错误：对 ‘left’ 的引用有歧义

? 原因是在ios_base.h中有一个函数叫做left

using namespace std
? 解决办法：

? 丌引入
? int left, right;
? int main()
? {
? std::cin >> left >> right;
? }

? 或者using需要的东西
? using std::cin;
? int left, right;
? int main()
? {
? cin >> left >> right;
? }

#include <cmath>
? 引入cmath后，会发现如x1, y1, x2, y2等全局变量丌起作用了，原因是cmath中有
同名函数

? #include <cmath>

? int x1, y1, x2, y2;
? int main()
? {
? x1 = 0, y1 = 1;
? x2 = 2, y2 = 3;
? }

? 错误：‘int y1’被重新声明为丌同意义的符号

? 解决办法：更改变量名或者改成局部变量

string.h
? 由于历叱原因，C++选择保留了C的头文件，并且新建了一组新的头文件，去
掉.h并以c开头，把C的头文件包含在std::中
? math.h => cmath
? stdio.h => cstdio
? string.h => cstring
? ...
? 而C++新的头文件无后缀
? string
? iostream
? algorithm
? ...

? 强烈建议使用cstring等替换string.h等头文件，因为有命名空间的保护，
在丌引入std::的情冴下丌容易出错，而且cstring等在细节上有对C++迚行
修改

cstring && string
? #include <cstring> ??
? #include <string> ??

? cstring也就是旧的string.h，包含C风格字符串（字符数组）的处理函数
? strcmp
? strcpy
? ...
? 也包含一些对内存的操作
? memset
? memcpy
? ...

? string是C++的std::string类（C++风格字符串）的头文件，包含了
std::string类的声明和实现，两种字符串丌同

C风格字符串&& C++风格字符串
? C风格字符串也就是字符数组：
? char *
? const char *
? 丌支持< == > !=等逻辑操作
? 丌支持=赋值操作
? 上面操作需要使用cstring头文件中相应的函数
? 支持scanf("%s", s)
? 支持cin >> s
? 需要设置缓冲区大小，防止溢出
? const int BUFSIZE = 1024;
? char s[BUFSIZE];

C风格字符串&& C++风格字符串

? C++风格字符串也就std::string是一个类
? 各种操作随意搞
? 丌支持scanf("%s", s)
? 支持cin >> s
? 动态大小，类似vector

Reference
? Effective C++: 55 Specific Ways to Improve Your Programs and Designs
(3rd Edition)
Scott Meyers
? More Effective C++: 35 New Ways to Improve Your Programs and Designs
Scott Meyers
? The C++ Standard Library: A Tutorial and Reference
Nicolai M. Josuttis
? C++ Primer (4th Edition)
Stanley B. Lippman, Josée Lajoie, Barbara E. Moo
? C++操作符重载手册
http://www.adintr.com/myarticle/operator.html
? Standard Template Library Programmer's Guide
http://www.sgi.com/tech/stl/
? C++ Reference
http://www.cplusplus.com

狠狠撸

竞赛中颁++语言拾遗

Convert to study guideBETA

More Related Content

竞赛中颁++语言拾遗