《C++程序设计》朝花夕拾

浏览数：24 / 时间：2015年06月08日

（以后再也不用破Markdown写东西了，直到它有一个统一的标准，不然太乱了--）

函数签名

int         f   (int a, int b)
↑           ↑       ↑     ↑ 
返回类型    函数名   形 式 参 数

其中，函数名+形式参数=函数签名(function signature)。

引用变量
```
int a = 1;
int &b = a;
a++;
cout << a << ‘ ‘ << b << endl;  //2 2
```
注意引用变量的声明方式，&写在等号左边是引用变量的声明，写在右边就是取址符。
变量默认初始化
- 非Static的Local变量，默认初始化为任意值 //Local的Static变量默认初始化为0
- Global或Static变量，默认初始化为0（指针为NULL，NULL也是0）
Null Terminator ‘\0‘
```
char s1[] = {‘a‘, ‘b‘, ‘c‘, ‘d‘, ‘e‘};
char s2[10] = {‘a‘, ‘b‘, ‘c‘, ‘d‘, ‘e‘};
char s3[] = {‘a‘, ‘b‘, ‘c‘, ‘d‘, ‘e‘, ‘\0‘};
char s4[10] = {‘a‘, ‘b‘, ‘c‘, ‘d‘, ‘e‘, ‘\0‘};
char s5[] = "abcde";
char s6[6] = "abcde";   //若char s6[5] = "abcde";则编译出错 
cout << s1 << ‘ ‘ << strlen(s1) << endl;    //abcde#‘ 7
cout << s2 << ‘ ‘ << strlen(s2) << endl;    //abcde 5
cout << s3 << ‘ ‘ << strlen(s3) << endl;    //abcde 5
cout << s4 << ‘ ‘ << strlen(s4) << endl;    //abcde 5
cout << s5 << ‘ ‘ << strlen(s5) << endl;    //abcde 5
cout << s6 << ‘ ‘ << strlen(s6) << endl;    //abcde 5
```
```
这里面有几个知识点：
```
- 比较s1和s3，之所以s1多输出一些奇怪字符，就是因为没有加终止符‘\0‘
- 比较s1和s2，数组若分配了大小，则C++会自动在字符串末尾添加‘\0‘（其实这一点很容易想到，因为分配了大小的数组，如果元素没有被填满，则剩余元素均会被初始化为0，而0就是‘\0‘）
- 比较s1和s5，s5_直接写成字符串的形式，C++会自动在字符串末尾添加‘\0‘_
- 比较s3和s6，s3中发现终止符‘\0‘并不影响strlen的大小；s6中却发现分配大小时需要将终止符考虑上（好奇怪的一点，也就是说，分配大小需要考虑‘\0‘，而strlen会忽略‘\0‘）
- 比较s1和s2，s3和s4，s5和s6，发现数组初始化的大小并不影响strlen。所以strlen的实现方法应该是，遍历数组直到发现‘\0‘，char s = {‘a‘, ‘\0‘, ‘\a‘}的strlen其实是1
NULL

源码实现应该是 #define NULL 0，所以null和Null都是错的，只有NULL才对。
*、++、+的运算级别

*p++你觉得应该是先算p++呢还是*p呢？

*p+1你觉得应该先算p+1呢，还是*p呢
int *i, j

你觉得这样声明的话，j是一个int，还是一个int的指针？

static

static变量的初始化——类外初始化

class A
{
　　static int x;   //不能直接在声明的时候初始化
};
int A::x = 0;   //类外初始化必须加上int和A::

只有static const变量才能直接在类内声明时初始化

class A
{
    static const int x = 0;
};

static函数的调用——通过类名调用

class A
{
    public:
    static void f(){}
};
A a;
a.f();  //correct
A::f(); //correct
A.f();  //wrong

friend

注：这里的子类指的是子类的成员函数，而不是子类对象（子类对象在类外）
public继承、protected继承和private继承

先看一个表

再看下面的代码
```
#include <iostream>
using namespace std;

class A
{
    public:
    void f1()
    {
        cout<<"f1()"<<endl;
    }

    protected:
    void f2()
    {
        cout<<"f2()"<<endl;
    }

    private:
    void f3()
    {
        cout<<"f3()"<<endl;
    }
};


class B: public A
{
    public:  // 子类的代码范围内访问父类
    void g1(){f1();}
    void g2(){f2();}
    //void g3(){f3();}  error

};


int main()
{
    B b;     //子类对象访问父类成员
    b.f1();
    //b.f2();   error
    //b.f3();   error
    b.g1();
    //b.g2();   error
    //b.g3();   error
}
```
仔细看上面的表格和代码之后再继续往下看，这里我一直有个误解的地方，就是子类不是能够访问父类的protected成员吗，为什么子类对象访问父类的protected成员时会出错。

原来，我们所谓的子类能够访问父类的protected成员，指的是在子类的类内去访问，而子类对象其实已经属于类外了。所以把子类对象当成是普通的外界访问即可。

接着，上面的代码中，子类是通过public方式继承，如果换成protected和private继承会发生什么事呢？继续看。

三种访问权限
- public：可以被任意访问
- protected：只允许子类及本类的成员函数访问
- private：只允许本类的成员函数访问
三种继承方式
- public 继承
- protect 继承
- private 继承
见下表

可以看到，子类的成员属性其实是基类属性和继承方式中，取较严格的一个，当然基类的private成员子类是无权访问的。

这个时候，回过头去看上面的表格和代码，就一目了然了。

父类的构造函数只能在子类的构造函数中调用

class A
{
    public: 
    int x,y;
    A(int x1, int y1):x(x1),y(y1){}
};
class B: public A
{
    public:
    int z;
    B(int x1, int y1, int z1):A(x1,y1),z(z1){}
};

顺便看一下如何使用初始化列表来初始化参数。

简单谈谈泛型编程

举个例子，A是父类，B是子类
```
void f(A a){}
B b;
f(b);
```
You can pass a derived class object to the base class parameter type in the function.
This is a kind of ‘Generic Programming‘

另外，STL也是一种泛型编程（利用模版T来抽象数据类型）。所谓“泛型编程”，精华在于，把数据类型作为一种参数传递进来，而不关心是哪种具体的数据类型。
子类调用被重定义的父类函数
```
class A
{
    public: 
    void f(){cout << "A" << endl;}
};  
class B: public A
{
    public:
    void f(){cout << "B" << endl;}
};
B b;
b.f();       //B
b.A::f();    //A
```
可以看到，由于B中的f()重定义了A中的f()，所以默认调用了B中的f()，若想重新调用A中的f()，则需要加上A::。
注意一，如果是
```
A* a = &b;
b->f();    //A
```
则由于A中的f()没有声明为虚函数，所以默认调用A中的f()。

注意二，如果是
```
void g(A a){a.f()}
g(b);    //A
```
则即使A中的f()声明为虚函数，也仍然输出A，因为参数传递时已经进行了类型转换。所以实现多态时，参数必须是引用或指针啦~

动态绑定（多态）

动态绑定即在程序运行的时候才确定调用哪个函数，跟多态有关。
动态绑定需要满足两个条件：

父类有虚函数

实现多态的函数的参数必须包含对象的地址（引用或指针）
举个例子，A是父类，B是子类，实现多态无非有以下两种方式。

class A
{
    public: 
    virtual void f(){cout << "A" << endl;}
};
class B: public A
{
    public:
    void f(){cout << "B" << endl;}
};
void g1(A &a) {a.f();}
void g2(A *a) {a->f();}
B b;
g1(b);     //方法1通过引用，输出B
g2(&b);    //方法2通过指针，输出B
A *a = &b;
a->f();    //同方法2通过指针，输出B

抽象类

假如有父类是多边形，子类是圆形和矩形，那么计算面积的函数应该声明在子类里呢还是父类里呢？由于面积是多边形的共性，所以应放在父类里，但是面积的计算方式又跟子类的类型息息相关，即只有确定了子类类型，计算面积的函数才能真正实现。
所以这个时候就需要纯虚函数，将计算面积的函数声明为父类的纯虚函数，纯虚函数又叫抽象函数，不提供实现，一个包含纯虚函数的类叫做抽象类，抽象类无法创建对象。
纯虚函数的声明方式：
```
virtual void getArea()=0;
```

Dynamic cast

假如有父类是多边形，子类是圆形和矩形，圆形的类中有getRadius()这个函数，而矩形的类中没有，假如一个函数的参数类型是父类，这个函数要判断该多边形是否是圆形，如果是则输出半径（getRadius()）。怎么办？

class A
{
    public: 
    virtual void f(){cout << "A" << endl;}
};
class B: public A
{
    public:
    void f(){cout << "B" << endl;}
    void f2(){cout << "BB" << endl;}    //B特有的函数
};
class C: public A
{
    public:
    void f(){cout << "C" << endl;}
};

void g1(A &a) 
{
    A *a2 = &a;    //先转换为指针，再进行指针间的转换
    B *b = dynamic_cast<B*>(a2);    //a2进行了dynamic cast
    if (b != NULL)b->f2();    //如果不是B类型，则b为NULL
}
void g2(A *a)
{
    B *b = dynamic_cast<B*>(a);    //a进行了dynamic cast
    if (b != NULL)b->f2();    //如果不是B类型，则b为NULL
}
B b;
C c;
g1(b);     //BB
g1(c);     //
g2(&b);    //BB
g2(&c);    //

dynamic cast一般是downcasting（父类到子类），而upcasting（子类到父类）的转换比较简单，直接(隐式)转换即可。

A *a = new A();
B *b = new B();
a = b;    //b进行了upcasting，将结果赋给a，b本身没有变

运算符重载

类内成员函数：
```
bool operator <(T &t)
T operator +(T &t)
T operator +=(T &t)
T& operator[](int &index)   //T& 保证返回的值可成为左值
T operator +() 
T operator ++()             //++var
T operator ++(int dummy)    //var++(dummy)
friend ostream & operator <<(ostream &stream, T &t)
operator double()
T& operator =(T &t)
```
非类内成员函数：
```
bool operator <(T &t1, T &t2)
T operator +(T &t1, T &t2)
……
```
- 参数为什么要引用？
  节省传值方式中实参的拷贝方面的开销。
- 为什么要返回引用类型？
  首先先明白什么是左值(L-value)和右值(R-value)。
  比如a = b，a是左值，b是右值。
  赋值符号左边的值是左值，它是一个地址（很奇怪吧哈哈）；而赋值符号右边的值是右值，它是一个数据。
  左值是代表一个内存地址值，并且通过这个内存地址，就可以对内存进行读并且写（主要是能写）操作；这也就是为什么左值可以被赋值的原因了。
  右值指的是引用了一个存储在某个内存地址里的数据。
  左值可以被改变，而右值不可以变。所以左值可以作为右值，而右值不一定能成为左值。
  比如a = 2, b = a中a是左值，也可以成为右值，而2是右值，不能成为左值。
  抽象点说，左值应该是一个类似变量的东西，而不是某个常量（个人理解）。
  比如T& operator =(T &t)，如果返回的是T而不是T&
  那么a=b=c这样的式子会出错，为什么，因为b=c返回的是一个常量，而参数要求是T &t，此时可以将T &t改为T t或const T &t。
  由于a=b=c的计算顺序是a=(b=c)，所以刚好不会出错。
  但是会有一个问题，就是(a=b)=c这样的式子在现实中也是有意义的，但编译却通过不了，因为a=b返回的是一个常量，常量不能被赋值（不能成为左值）。
  所以最好还是返回一个引用类型。
  比如T& operator[](int &index)，如果返回的是T而不是T&
  那么s[1]=2这样的式子就会出错，因为s[1]返回的是一个常量，不能成为左值（常量是不能被赋值的）。
  比如friend ostream & operator <<(ostream &stream, T &t)，如果返回的是ostream而不是ostream &
  cout << a <<" ";这句就会出错，因为cout << a返回一个ostream类型的值，而这个值并没有一个类似变量的东西去承载它，只是一个值，不能成为左值。（类似a = 1是对的而1 = 1是错误的）
- 什么时候参数需要加const
  当你不希望该参数在该函数中被改变的时候可以加，但不是必须的。
- T operator ++() //++var
  T operator ++(int dummy) //var++(dummy)
  怎么记？第一个没有参数，类似正号的重载T operator +()
  而第二个有一个参数dummy(虚拟的)，类似加号的重载T operator +(T &t)
Template
- 模板的默认值Template< typename T=int>只适用于类模板，不能用于函数模板
  然后这样使用：Stack<> stack，而不是Stack stack
- 模板可以这样声明，template< typename T, int size>
  然后这样使用：Stack< int, 500> stack
复杂度的计算

以前一直以为快速排序的复杂度是这样计算的，每一层递归需要对每个元素进行划分（左或右），所以每一层都是O(n)，一共有logn层，所以是O(nlogn)。但是这样是错的，正确的应该从递推公式出发：
T(n) = T(n/2)+T(n/2)+n
推出T(n) = nlogn+n = O(nlogn)

假如一个函数是
```
void f(int n)
{
    if (n == 0) return;
    f(n/2);
    f(n/2);
}
```
则按照我以前的想法，一共有logn层，每一层复杂度是O(1)，所以O(logn).但是正确的应该是:
T(n) = T(n/2)+T(n/2)+C
推出T(n) = O(n)
External Sort(外部排序)

当内存太小不足以读取全部数据的时候，普通的排序算法不能用了，要用到外部排序。
所谓的外部排序，就是将数据分成N批依次读进内存，对每一批，用内部排序算法（普通排序算法）排序，将结果写进一个新的文件中，这样就有N个排序好的文件。然后对这些文件进行两两归并排序，直到剩下一个文件。
STL

STL包含三个部分：
- 容器
  - 顺序容器(vector, list, deque)
  - 关联容器(set, map, multiset, multimap)
  - 容器适配器(stack, queue, priority_queue)
- 迭代器
- 算法
Iterator

list< int>::const_iterator it; //指向的内容不可改变
const list< int>::iterator it; //迭代器自身不可改变
reverse_iterator //rbegin是最后一个，rend是第一个之前的位置，rbegin通过递增直到rend，懂？
Pointer是一种特殊的Iterator
Iterator是泛化的Pointer

STL Algorithm

int a[] = {1,2,3,4,5};
vector<int> v(5);
copy(a, a+5, v.begin());
ostream_iterator<int> out(cout, " ");
copy(v.begin(), v.end(), out);

copy(sourse.begin(), sourse.end(), target.begin())

fill(source.begin(), sourse.end(), value)
fill_n(source.begin(), n, value)

generate(source.begin(), sourse.end(), f(int)) 
generate_n(source.begin(), n, f(int))

//remove后原容器的size不变，空位由原来的值补全 
remove(source.begin(), sourse.end(), value) 
remove_if(source.begin(), sourse.end(), f(int)) 
//source不变，将remove之后的结果依次赋给target 
remove_copy(source.begin(), sourse.end(), target.begin(), value) 

remove_copy_if(source.begin(), sourse.end(), target.begin(), f(int))

replace(source.begin(), sourse.end(), oldValue, newValue) 
replace_if(source.begin(), sourse.end(), f(int), newValue) 
replace_copy(source.begin(), sourse.end(), target.begin(), oldValue, newValue) 
replace_copy_if(source.begin(), sourse.end(), target.begin(), f(int), newValue)

find(source.begin(), sourse.end(), value) 
find_if(source.begin(), sourse.end(), f(int)) 
//在source中找key（子串匹配），返回最后一个匹配的起始位置 
find_end(source.begin(), sourse.end(), key.begin(), key.end()) 
find_end(source.begin(), sourse.end(), key.begin(), key.end()), f(int1,int2)) 
//key中有一个元素符合条件就行，而不是整个子串 
find_first_of(source.begin(), sourse.end(), key.begin(), key.end()) 
find_first_of(source.begin(), sourse.end(), key.begin(), key.end(), f(int1,int2))

//与find_end相反，返回第一匹配子串的起始位置 
search(source.begin(), source.end(), key.begin(), key.end()) 
search(source.begin(), source.end(), key.begin(), key.end(), f(int1,int2)) 
//查找连续相同字符，返回第一个匹配的位置 
search_n(search(source.begin(), source.end(), n, value) 
search_n(search(source.begin(), source.end(), n, f(int))

//这个不多说了，经常用，经常用到的cmp(int)是greater() 
sort(source.begin(), source.end()) 
sort(source.begin(), source.end(), cmp(int1, int2)) 
binary_search(source.begin(), source.end(), value) 
binary_search(source.begin(), source.end(), value, cmp(int1, int2))

//找出相邻的两个相等的元素 
adjacent_find(source.begin(), source.end()) 
adjacent_find(source.begin(), source.end(), f(int1, int2))

//merge将2个排序好的序列存到其他地方，而inplace_merge是存到自身 
merge(s1.begin(), s1.end(), s2.begin(), s2.end(), t.begin()) 
merge(s1.begin(), s1.end(), s2.begin(), s2.end(), t.begin(), cmp(int1, int2)) 
inplace_merge(source.begin(), source.middle(), source.end()) 
inplace_merge(source.begin(), source.middle(), source.end(), cmp(int1, int2))

//reverse_copy source不变 
reverse(sourse.begin(), source.end()) 
reverse_copy(sourse.begin(), source.end(), target.begin())

rotate(sourse.begin(), source.newBegin(), source.end()) 
rotate_copy(sourse.begin(), source.newBegin(), source.end(), target.begin())

//swap_range是将[begin,end-1]和[begin2,...]交换，个数一样 
swap(T1, T2) 
iter_swap(it1, it2) 
swap_ranges(source.begin(), source.end(), source.begin2())

count(sourse.begin(), source.end(), value) 
count_if(sourse.begin(), source.end(), f(int))

//返回的是iterator 
max_element(sourse.begin(), source.end()) 
min_element(sourse.begin(), source.end())

//随机打乱[begin, end-1] 
random_shuffle(sourse.begin(), source.end())

for_each(sourse.begin(), source.end(), f(int)) 
transform(sourse.begin(), source.end(), target.begin(), f(int))

//交并差,对称差(A并B减掉A交B) 
includes(s1.begin(), s1.end(), s2.begin(), s2.end()) 
set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), target.begin()) 
set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), target.begin()) 
set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), target.begin()) 
set_symmetric_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), target.begin())

//求容器元素的和加上value的和 
accumulate(source.begin(), source.end(), value) 
accumulate(source.begin(), source.end(), value, minus())

//t[0]=s[0],t[i]=s[i]-s[i-1]; 
adjacent_difference(source.begin(), sourse.end(), target.begin()) 
adjacent_difference(source.begin(), sourse.end(), target.begin(), multiplies())

//value+s1[0]*s2[0]+s1[1]*s2[1]+…… 
inner_product(s1.begin(), s1.end(), s2.begin(), value) 
//value*(s1[0]-s2[0])(s1[1]-s2[1])…… 
inner_product(s1.begin(), s1.end(), s2.begin(), value, minus(), plus())

//target[i]表示source前i项的和 
partial_sum(source.begin(), source.end(), target.begin()) 
partial_sum(source.begin(), source.end(), target.begin(), minus())