C++ Basic

感觉多少有点复杂

Def

• A dangling pointer is a pointer that points to a location whose memory is deallocated.

• dynamic objects are managed by heap, and stack vice versa. Temporary objects are managed by stack. And rvalue reference is an alias of a temporary object/value.

const int* is different from int* const. int* const相当于我们让一个const变量成为指针，比如int* const ptr = & x，那么实际上ptr作为一个const变量是不可变的，但是他指向的x的值是可变的，即* x = 5编译是可以通过的。相较之下，const int* ptr = & x则是ptr是changeable，x是unchangeable。

我告诉你一个小的技巧，就是c++keyword修饰它前边的东西，这个是一定成立的。 ——whs

比如，const int* const p则分为两个部分理解，一个是int*这个指针指向一个const int变量，另一个则是第二个const管着int*，即这个指针也是unchangeable的。注意，int const* a也指的是值不变的指针。

a[i][j]的地址可以被这么表达：*((*(a+i)) + j)

指针在32位机器中占4byte，在64位机器中占8byte。

数组是连续的：即

a[4] = {0, 1, 2, 3, 4};
cout << * (a + 1) << ' ' << * (a + 4) << endl;

输出为1, 4

那么关于a、&a与&a[0]的差别，一下子有一篇博客阐释的较为清楚：

在探讨这个问题之前，我们首先来看一道笔试题，如下：
　　【摘自牛客网】下列代码的结果是：（正确答案是 C）

main() 
{ 
    int a[5]={1,2,3,4,5}; 
    int *ptr=(int *)(&a+1); 
    printf("%d,%d",*(a+1),*(ptr-1)); 
}

A、3,5　　　B、2,4　　　C、2,5　　　D、3,4
　　下面我们来分析一下选择C的原因，解释清楚这个题的正确答案，你就能清楚数组中&a与&a[0]存在什么区别了。
　　题目中首先定义了存放5个int类型空间大小的内存，然后初始化5个数。我们知道直接使用数组的名字a表示的是一个指向数组首地址的指针，所以直接a与&a[0]是相同的意思，都表示数组的首地址。所以(a+1)很好理解，假设a地址是0x1000，就是取（0x1000+sizeof(int)）地址的数，由于数组的物理地址是连续的，当然就是取2。
　　那&a表示什么意思呢，相当于取存放指向数组首地址的指针的存储地址，话有些绕，但是细细品味你就会发现，它就相当于二维指针，假设每个一维指针指向一排数组（当然除了第一个一维数组的指针之外实际都没有申请，但是在访问野指针之前计算机也不知道那块地址是否存在，但的确可以由物理地址连续性来获取这块地址的表示），所以简言之&a表示第一排数组，&a+1就是表示第二排数组（就是5sizeof(int)=54=20空间大小后一段空间的首地址）。
　　有了上面的介绍就好理解了，(ptr-1)是表示取(0x1000+5*sizeof(int)-sizeof(int))地址中的数，算得为5。
　　总结：
　　&a[0]表示数组的首地址，与直接a相同意义。而&a表示存储指向数组首地址的指针的地址，可以用二维指针来理解。

For dynamic 2D array:

• x == &x[0] != &x[0][0]
• &x[j] = x + j
• x[j] == &x[j][0]

Homogeneous

“homo-“ means same, “hetero-“ means different.

In any case if a single Java array can only store one type, say, only numbers, or only strings then it is homogeneous.

If multiple types then heterogeneous. In the above case, since collection is of Object type and can hold any type

Let’s take Javascript for understanding this better eg. arrays are heterogeneous, because I can make an array that holds [5, “hello”, new Object()], and in Java that’s not possible.

static member v.s. non-static member

static member可以不通过instance就直接call，而non-static member则需要先创建一个Helper instance g在经由g去call

return by value: return a copy of the original object.

return by reference:

int& FUNC () { ... }

The original object is passed back, which means further operations on returned value would affect the original object.

conversion constructor: a constructor accepting single para。值得注意的是，A constructor may have multiple arguments; if all but one argument have default values, it is still a conversion constructor. which means Word (const char *s, int k = 1)这种虽然两个变量但是实际上只有一个是unknown的也是conversion

implicit conversion: 指通过形似Word movie = “James”赋值，这种赋值方式实际上是先开一个新object with initial value “James”，然后再赋值给movie，故为implicit

copy constructor: 实际上就是初始化值变成了其他的同类型object。比如Word (const Word& W) {}。A constructor that has exactly one argument of the same class passed by its const reference.注意exactly one arg

Function

Formal-parameter-list指函数def那边的参数列表；Actual-parameter-list指的是调用的参数列表

define a function: int Func (int, int); 这里(int, int)被叫做signature。

function prototype: 1. function name. 2. return data type. 3. the number of formal parameters. 4. the data type of the formal parameters.

function declaration指的是写下他的interface (its function prototype)，而function definition则是将其header和body都写出来。

function resolution: 实际上就是指compiler判断到底用哪个overloaded function的过程。

default arguments必须写在变量之后，即void func (int x, int y, int z = 0, int p = 0);

Scope for an identifier is determined by the location of its declaration.

FIle scope: global scope. Local scope: function scope, block scope(即比如for () { int a; })那么a就在个block里面。

同一个scope不能重名，但不同scope里可以。重名的话编译器编译时会选择innermost enclosing scope的变量。

使用最基础的方法穿array到function里是pass-by-value的，但是这array的elements确实pass-by-reference，也就是说在func里对array进行修改，是会影响到原数组的。对于多维数组，值得注意的是，void func (int a[][]) {}这种写法是不行的，只有第一维能为空，其他必须制定大小。

Class:

保护成员的可访问范围比私有成员大，比公有成员小。能访问私有成员的地方都能访问保护成员。保护成员扩大的访问范围表现在：基类的保护成员可以在派生类的成员函数中被访问。

CONSTRUCTOR member functions: constructors

ACCESSOR member functions: functions that will not modify data members (i.e. funct () const {})

MUTATOR member functions: 反之

After compilation, 代码中一个pointer指向的function将会被转化成unique global function by adding a new argument. e.g., x.set (a)编译后将会被转化为Class::set (& x, a)

A const object can only call const member functions.

Keyword: private可以被member functioin及friend class访问；protected可以被member functions、friend class及friend class的derived class访问。

Constructor & Destructor

总结：1. static变量不会在主动constructor里面被访问去create。2. 对于继承关系，比如B继承A，那么construct B之前一定会先construct A，同理，destruct B之后也一定会destruct A。3. 对于A** a = new A*[2] { new A(1), new B(b) };的情况a不会经过constructor。4. 有一个方法就是可以看作stack，即destruct的过程完全和construct过程反过来。

A constructor accepting a single argument specifies a conversion from its argument type to the type of its class:

如果存在user-defined constructor但是在定义object的时候没有指定constructor，那么会报错而不会自动调用default constructor. default constructor只有在没有user-defined constructor的时候才会被自动调用。

explicit关键字before constructor指定了必定只能显式转换（对于JAVA：隐式转换也叫自动类型转换，指的是不需要调用函数，JVM自动将类型转换的一种方式）。

term: braced initializtion指的是int z{3}这种用大括号的初始化方法。

func () : () {} 这玩意儿叫做member initializer list (MIL).

const or reference members must be initialized using member initializer list if they don’t have default initializers.

construction order和destruction order分别类似于先序遍历和后序遍历。

A ‘has’ B: A的member里有B的object；A ‘owns’ B: A的member里有B的指针

Objects must be passed by reference in copy constructors. i.e. Copy constructor of class X must have the following signature: X::X(const X& copiee). It cannot be X::X(const X copiee)

A conversion constructor can be called anywhere when the type of the single argument is assigned to the object. 也就是说conversion constructor可以被call大于一次。

Inheritance

私有继承：使用私有继承，基类的公有成员和保护成员都将成为派生类的私有成员，只可以在派生类的成员函数中使用

保护继承：基类的public和protected成员：都以protected身份出现在派生类中；

Def: Polymorphic or Liskov Substitution Principle 指的是inheritance中derived class可以调用base class的所有东西，but not vice versa的原则。

Problems:

• Slicing: 将子类object的值赋给一个父类object
• Name Conflict

如果一个data member在base class中是private，那么他不可以被derived class的object访问，还是只能被base class’ own member function访问（除非friend）。

那么此时就要将他们改为protected，这种状态下they are accessible to member function in the base class as well as member functions in the derived class.

当使用类的指针调用成员函数时，普通函数由指针类型决定，而虚函数由指针指向的实际类型决定。

Polymorphism in C++ means that we can work with objects without knowing their precise type at compile time. We say that uperson exhibits polymorphism, because the object can take on multiple “shapes” (Student, Teacher, PG_Student, etc.). A pointer or reference must be used to take advantage of polymorphism. 至于为什么不能pass-by-value，也跟object slicing有关，因为当你pass-by-value传进去的时候，If the base-class object is not legit合法的 (e.g. it has pure virtual functions in it), you can’t even declare or call this function.

在基类中仅仅给出声明，不对虚函数实现定义，而是在派生类中实现。这个虚函数称为纯虚函数。普通函数如果仅仅给出它的声明而没有实现它的函数体，这是编译不过的。纯虚函数没有函数体，纯虚函数需要在声明之后加个=0；

Override is not possible if the member function is not virtual.

virtual destructor: 为了防止诸如UPerson* p = s而s是derived Student类，delete p却只调用UPerson的destructor而不是Student的destructor的情况，那么加上了virtual就可以通过object本身的类型来选择destructor了。

ABC: Abstract Base Class

• No objects of ABC can be created

• 抽象类不能直接实例化，并且对抽象类使用 new 运算符会导致编译时错误；

  抽象方法只能声明于抽象类中，且不包含任何实现，派生类必须覆盖它们；

  重要的是抽象类可以包括抽象方法，这是普通类所不能的，但同时也能包括普通的方法。

Keyword ‘final’ 意味着该类无法被继承

Generic Programming

fucntion template会自动deduce template arguments（即typename），但是class template必须要明确定义。

加号的函数用法实际上是operator+(a, b)

ostream is the base class for all possible output streams. cout, cerr都是该类中的object

overload operator []需要一个constant overloading和non-constant overloading。若不存在non-constant overloading，那么对那些non-constant的object的访问可以使用constant overloading的函数；但是若不存在constant overloading的话，那些constant的object就没法使用non-constant overloading的函数。但是注意，即使可以non-constant object可以调用constant的，也会产生lvalue和rvalue的问题，即constant overloading返回的是rvalue，不能用于赋值。

overload operator ++的时候，要注意overload的是lvalue还是rvalue。如果是lvalue，即++ a，那么写作Vector& Vector::operator ++ () {}；若是rvalue，即a ++，那么写作Vector Vector::operator ++ (int)。

STL

Containers: Sequence containers；Associate containers是非线性的，存key/value pairs；Container adapters adopted containers that support a limited set of container operatioins；Near containers

Sequence: vector, list, deque；Associative: map, multimap, multiset, set；Adapters: priority_queue, queue, stack；Near-containers: bitset, valarray, string

A predicate is a C++ function returning a boolean or an object having a bool operator() member.

function pointer: inline const T (*) (const T&, const T&);。用法诸如int (* f)(int x, int y) = larger，int (* f[])(int x) = { func1, func2, func3 }

Tree

Preorder：根左右；Inorder：左根右；Postorder：左右根

lvalue/rvalue reference

Temporary object/value在什么时候会存在呢？1. const reference initialization; 2. argument passing (e.g. type conversion或者诸如类似func (“pass_value”)的情况); 3. function returned value (by copying); 4. evaluatioin of expressions (e.g., result of sub-expressions比如int e = a + c + d中生成了temporary object来承载a + c + d).

Temporary objects are managed by stack. And rvalue reference is an alias of a temporary object/value.

lvalue reference only binds to another lvalue，即int& b = 4会报错，因为让lvalue reference等于一个rvalue。但是const lvalue reference可以接受rvalue，因为此时temporary value已经被created了，即const int& c = 5是正确的。

值得注意的是，rvalue ref必须被initialized，即int&& b是错误的；且他不能承接lvalue，即int a; int&& c = a是错的。

rvalue reference once bound, cannot be re-bound to another temporary object.

std::move () only does static casting.

C++11 new feature

{} initializer is more restrictive: it doesn’t allow conversions that lose information — narrowing conversions（即int a {0.5}）这种写法是不允许的（double值通过{} initializer赋值给一个int object）。

注意，lambda function中假如[]里面是value，那么他实际上只会在该lambda function被定义的时候copy一次，which means这样的写法int a = 1; auto f = [a](int x) mutable { return a *= x; }; cout << f (20) << ‘ ‘ << f (400) << endl;输出是20 400而不是20 20。

explicit关键字可以让函数拒绝implicit conversion

enum里面的identifier name必须在整个程序中唯一，即enum { ABC }; int ABC = 0之类的都是不合法的。且comparision between enum不合法。但C++11中引入了enum classes可以一定程度上避免这些问题。

Static

加了static关键字的全局变量我们就可以称为“内部”变量，这里的“内部”指的是static全局变量的作用域范围，“内部”作用域是指变量所在的文件作用域，也就是说static全局变量的作用域仅限于所在文件内部，工程内的其他文件不可见。

class里的static variable会让所有该class的object share同一个。Static variables cannot be initialized in the class definition (except for const int/enum static data). Static variables must be defined outside the class definition, usually in the class implementation (.cpp) file.（注意是define不是declare）

class中的static member function是属于class的所有object的，所以不存在this关键字，并且可以在不存在class object的时候使用，但是只可以对class中的static data member进行操作，且不能为const或者virtual functions，且不能被一个non-static member function of the same prototype overload。

AVL Tree

An AVL tree is a BST where the height of the two sub-trees of ANY of its nodes may differ by at most one. Each node stores a height value, which is used to check if the tree is balanced or not. 也被称作高度平衡树。

Insertion may violate the AVL tree property in 4 cases:

1. Right-Right (RR)
   Left (anti-clockwise) rotation [single rotation]:
   Insertion into the right sub-tree of the right child of a node

2. Left-Left (LL)
   Right (clockwise) rotation [single rotation]:
   Insertion into the left sub-tree of the left child of a node

3. Left-Right (LR)
   Left-right rotation [double rotation]:
   Insertion into the right sub-tree of the left child of a node

4. Right-Left (RL)
   Right-left rotation [double rotation]:
   Insertion into the left sub-tree of the right child of a node

Similar to node deletion in BST, 3 cases need to be considered

1. The node to be removed is a leaf node

   ⇒ Delete the leaf node immediately

2. The node to be removed has 1 child

   ⇒ Adjust a pointer to bypass the deleted node

3. The node to be removed has 2 children

   ⇒ Replace the node to be removed with either the

   • maximum node in its left sub-tree, or

   • minimum node in its right sub-tree Then remove the max/min node depending on the choice above.

Removing a node can render multiple ancestors unbalanced ⇒ every sub-tree affected by the deletion has to be re-balanced.

Constexpr:

Restrictions of constexpr function

1. In C++11, a constexpr function should contain only ONE return statement. (Relaxed in C++14)

2. Each of its parameters must be a literal type.

3. Its return type should not be void type and other operator like prefix

   increment are not allowed in constexpr function. It must be a literal

   type (e.g. scalar type, reference type, an array of literal type).

4. A constexpr function should refer only constant global variables.

5. A constexpr function can call only other constexpr functions.

6. A constexpr function has to be non-virtual.

Hashing

For any key K, h2 (K) must be relatively prime to the table size m

Like separate chaining, open addressing is a method for handling collisions. In Open Addressing, all elements are stored in the hash table itself. So at any point, the size of the table must be greater than or equal to the total number of keys

for( i = 0; i < m; i++ )
	compute L = ( h(K) + i ) % m;
	if T[L] is empty, put K there and stop

Quadratic Probing:

for( i = 0; i < m; i++ )
	compute L = ( h(K) + i*i ) % m;
	if T[L] is empty, put K there and stop

Double Hashing:

H(Ki, 0) = h(Ki)
H(Ki, 1) = (H(Ki, 0) + h2(Ki)) mod m
H(Ki, 2) = (H(Ki, 1) + h2(Ki)) mod m
. . .
H(Ki,m) = (H(Ki,m−1) +h2(Ki)) mod m

Main