Data Structure

Avl Tree

有时候我们需要用一个变量存储一个不变的值，例如缓冲区的大小、数组的元素个数等等。好处是我们可以根据需求很容易对其进行调整，并且也能防止程序不小心修改了这个值，此时可以使用关键字const对变量的类型加以限定。

初始化

const对象一旦创建后，其值就无法修改，因此必须初始化。初始值可以是任何复杂的表达式，包括常量和变量。 

1
2
3
4
5
6
7
8
9
10
11
12
13
int i = 10; // i是一个已初始化的变量
int j; // j是一个未初始化的变量
const int k = 9; // k是一个常量，必须初始化
cin >> j;
const int a = i;
const int b = j;
const int c = k;
cout << "i = " << i <<endl;
cout << "j = " << j <<endl;
cout << "k = " << k <<endl;
cout << "a = " << a << endl;
cout << "b = " << b << endl;
cout << "c = " << c << endl;

输出结果如下： 

1
2
3
4
5
6
7
8
9
10
11
12
6
i = 10
j = 6
k = 9
a = 10
b = 6
c = 9
```  
当用i、j和k去初始化a、b和c时，根本无须在意是不是用常量初始化，常量特征仅仅在执行改变该对象的操作时才会发生作用。任何试图改变const对象的内容的行为都是非法的。
```c++
    a = b; // 错误，不能修改常量的值
    const int d; // 错误，常量必须初始化

文件作用域

当以编译时初始化的方式定义一个const对象时，如下

1
const int bufSize = 512;

编译器将在编译过程中把用到该变量的地方都替换成对应的值。为了执行替换，编译器必须知道变量的初始值，如果程序包含多个文件，则每个用了const对象的文件必须能够访问到它的初始值。因此，就必须在每个用到变量的文件中都有对它的定义，为了支持这一用法，同时避免对同一变量的重复定义，默认情况下，const对象被设定为仅在文件内有效。当多个文件中出现了同名的const变量，其实等同于在不同文件中分别定义了独立的变量。
main.cc中声明了func()函数，其定义在a.cc中，初始化bufSize = 512，在main函数中打印它的值，并调用func()。

1
2
3
4
5
6
7
8
9
10
11
12
// main.cc


const int bufSize = 512;
void func(); // define in a.cc

int main()
{
    cout<< "main.c: " << bufSize<<endl;
    func(); // call func
    return 0;
}

a.cc中定义了func()函数，其输出定义在本文件中的const变量bufSize。

1
2
3
4
5
6
7
8
// a.cc

const int bufSize = 1024;

void func()
{
    std::cout << "a.cc: " << bufSize << endl;
}

命令行编译并执行：

1
2
3
4
rda@pa ~/Downloads> g++ a.cc main.cc -g -o main
rda@pa ~/Downloads> ./main
main.c: 512
a.cc: 1024

可见，定义在不同文件中的同名const对象是不同的。
若需要在文件之间共享const变量，则对于其声明和定义都添加extern关键字，这样只需定义一次就可以了。
为main.cc中的bufSize添加extern关键字。

1
2
3
4
5
6
7
8
9
10
11
12
// main.cc


extern const int bufSize = 512;
void func(); // define in a.cc

int main()
{
    cout<< "main.c: " << bufSize<<endl;
    func(); // call func
    return 0;
}

为a.cc中的bufSize添加extern关键字，并舍去其初始值。

1
2
3
4
5
6
7
8
// a.cc

extern const int bufSize;

void func()
{
    std::cout << "a.cc: " << bufSize << endl;
}

再次编译并执行：

1
2
3
rda@pa ~/Downloads> g++ a.cc main.cc -g -o main && ./main
main.c: 512
a.cc: 512

此时bufSize在两个文件之间共享。

const的引用

可以把引用绑定到const对象上，称之为对常量的引用。对常量的引用无法修改它所绑定的对象：

1
2
3
4
const int ci = 1024;
const int &r1 = ci;
r1 = 42;  // 错误，常量引用无法修改绑定的对象
int &r2 = ci; // 错误，非常量引用无法绑定到一个常量对象

一般来说，引用的类型必须与其所引用的对象的类型一致，但当初始化常量引用时允许使用任意表达式作为初始值，只要该表达式的结果能转换成引用的类型即可。允许一个常量引用绑定到非常量的对象、字面值甚至是一般表达式：

1
2
3
4
5
int i = 42;
const int & r1 = i; // 常量引用绑定到非常量对象
const int &r2 = 42; // 常量引用绑定到字面值
const int &r3 = 2 * r1; // 常量引用绑定到表达式
int &r4 = r1 * 3; // 错误，非常量引用无法绑定到一个表达式

当一个常量引用绑定到另一种类型上时，如下：

1
2
double dval = 3.14;
const int &ri = dval;

编译器把上述代码变成如下格式：

1
2
const int temp =dval; // temp的值为3
const int &ri = temp;

这种情况下，ri绑定到了一个临时量（temporary）对象，所谓的临时对象就是当编译器需要一个空间来暂存表达式的求值结果时临时创建的一个未命名的对象。

指针和const

可以令指针指向常量或非常量。指向常量的指针不能用于改变其所指的对象的值，想要存放常量对象的地址，只能使用指向常量的指针。

1
2
3
4
const double pi = 3.14;
double *ptr = &pi;  // 错误，常量对象的地址只能使用指向常量的指针保存
const double *cptr = &pi;
*cptr = 4.2; // 错误，指向常量的指针无法改变其所指对象的值

指针的类型必须与其所指对象的类型一致，但是有两个例外，第一个例外是，允许一个指向常量的指针指向一个非常量对象。

1
2
double dval = 3.14;
const double *cptr = &dval;

所谓指向常量的指针或引用，仅仅是自身无法修改所指向的对象或所绑定的对象，而没有规定那个对象的值无法修改。
指针是对象，而引用不是，因此允许把指针本身定义为常量，即常量指针，意味着不变的是指针本身的值而非指向的地址中存储的值。和其他常量一样，常量指针必须初始化，且一旦初始化完成，则它的值（存放在指针中的地址）不能再改变。

1
2
3
4
5
6
7
8
9
10
11
int errNumb = 0;
int anoNum = 1;
int *const curErr = &errNumb;  // 常量指针
int *curAno = &errNumb;
const double pi = 3.14159;
const double *const pip = &pi; // 指向常量对象的常量指针

curErr = &anoNum; // 错误，常量指针的值不能修改
curAno = &anoNum; // 非常量指针的值可以修改
*curErr = 23;
*pip = 9.8;  // 指向常量对象的指针无法修改指向对象的值

顶层const和底层const

对于指针来说，其本身是一个对象，且指向另一个对象（存储该对象的地址），因此指针本身是不是一个常量以及其指向的是不是一个常量对象是独立的。名词顶层const表示指针本身是个常量，而底层const表示指针所指向的对象是一个常量。更为一般的，顶层const可以表示任意的对象是一个常量。

1
2
3
4
5
6
7
8
9
    int i = 0;
    int *const pi = &i;  // 顶层const，pi本身的值无法改变
    const int ci = 6;    // 顶层const，ci本身的值无法改变
    const int *p2 = &ci; // 底层const，p2所指向的对象的值无法改变
    const int *const p3 = p2; // 左边的const是底层const，右边的const是顶层const
    const int &r = ci; // 底层const
//    进行拷贝操作时，拷入和拷出的对象是否为常量没有影响
    i = ci;
    p2 = p3;

拷贝时，两个对象必须具有相同的底层const资格，或者两个对象的数据类型可以转换，一般来说，非常量可以转换成常量，反之则不行。 

1
2
3
4
5
int *p = p3; // 错误，p3和p的底层const不同且常量无法转换为非常量
p2 = p3;
p2 = &i;
int &r=ci;  // 错误，普通int&无法绑定到int常量
const int &r2 = ci; // const int & 可以绑定到非常量

重载函数中的const

实参初始化形参时会忽略顶层const，当形参含有顶层const时，传递给它常量对象或非常量对象都是可以的，因此如下重载函数会发生错误。

1
2
3
4
5
6
7
8

void fcn(const int i){
    cout << "call const fcn, i = "<< i << endl;
}
void fcn(int i) // 错误，重复定义了fcn
{
    cout << "call non-const fcn, i = "<< i << endl;
}

但底层const可以用来区分不同的重载函数，此时，常量对象调用底层const对应版本的函数。

1
2
3
4
5
6
7
8
const int i = 3;
const int &ri =i;
int j = 9;
int &cj = j;
fcn(i);
fcn(ri);
fcn(j);
fcn(cj);

输出结果为：

1
2
3
4
call const fcn, i = 3
call const fcn, i = 3
call non-const fcn, i = 9
call non-const fcn, i = 9

注意，如下情况编译不会报错，但运行时会有错误。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void fcn(const int& i){
    cout << "call const fcn, i = "<< i << endl;
}
void fcn(const int i) // 错误，重复定义了fcn
{
    cout << "call non-const fcn, i = "<< i << endl;
}

int main()
{
    const int i = 3;
    int j = 5;
    fcn(i); // ambiguous
    fcn(j); // ambiguous
   return 0;
}

无法得知调用的是哪个版本的重载函数。