Appendix：C & C++ Topics

1.C&C++ 的内存管理

1.1 C 动态内存管理函数

• 给特定数据类型分配一段内存空间并将地址赋给指针，可以用void *malloc( size_t size )，注意指针的type casting。Resize时，可以用 void *realloc(void *ptr, size_t size) 返回新地址，旧数据会最大限度得到保留。最后需要free(void *ptr) 释放空间。
• memcpy(dest,src,num);用于连续内存复制; memset (ptr, value, num);用于连续内存内容的初始化。

1.2 C++ 的动态内存管理
在C++中分配内存空间，可以使用new/delete与new[]/delete[]操作符，对于object实际上调用了对象的constructor/destructor。在C++中没有realloc的对应函数，一般可以使用container自带函数resize()。

1.3 Smart pointers in C++
Smart pointer可用于管理内存空间的ownership，并防止memory leak（owner撤出时必须清理垃圾）: A smart pointer is a class that wraps a raw pointer, to manage the lifetime of the object being pointed to.
smart pointer可以通过raw pointer（包括new 操作符 ）或smart pointer创建。两类smart pointer：

• Reference-counted ( std::shared_ptr<T>），stack-based, share ownership of the object/raw-pointer ( copyable );
• Non-reference-counted (std::unique_ptr<T>)，can't share ownership，you have to transfer using std::move()。

在C++11中，shared_ptr与unique_ptr均可作为standard container存储的对象。（web reference）

e.g. Write a (reference-counted) smart pointer class.( CtCI: 13.8 )

2.C++的OOP特性

2.1 C++ vs Java

• Java runs in a virtual machine.
• C++ allows operator overloading.
• C++ allows multiple inheritance of classes.
• Java has built-in garbage collection.
• In Java, parameters are always passed by value.( or with objects, their references are passed by value ).
• C++ natively supports unsigned arithmetic.

2.2 Virtual Functions
C++一般通过virtual function来实现dynamic-binding，即程序中所调用的函数，由base class的指针或引用所指向的object的实际类型，而不是指针或引用的类型，在runtime决定，从而实现多态（Polymorphism），提高复用性。拥有至少一个pure virtual function的类为抽象类，不能实例化对象。从内部机制上说，类的“Virtual Table”记录virtual functions的地址，并由vptr指向"Most Derived virtual function"。注意在多态实现中，destructor也需标示为virtual。

2.3 Polymorphism
通过virtual function实现的狭义多态，也称runtime polymorphism。广义的多态，也可通过"template"，"overloading"（操作符或函数）或"type-casting"实现。

2.4 Operator Overloading
定义user-define的class或struct的运算符,如bool operator<(const Key& param1, const Key& param2) 用以判断param1是否严格小于param2。对于Key类型有多个判断变量的情况，务必保证顺序的完备性。

e.g.

// Comparison operator for table sorting.(as a member function)
bool Complex::operator<(const Complex& param) connst
{
    if (keyA < param.keyA) return true;
    if (keyA > param.keyA) return false;
    if (keyB < param.keyB) return true;
    if (keyB > param.keyB) return false;
    if (keyC < param.keyC) return true;
    if (keyC > param.keyC) return false;
    return false;
}

3.C&C++ Utilities

3.1 Data Types
3.1.1 Implict conversion：适用于基本类型之间的转换，或者部分指针之间的转换：CBase *pb = new CDerived();。
3.1.2 C-style type cast: 适用于基本类型或指针之间的强制转换：(new_type) expression，用于struct或class或其指针则可能会因为转换的对象不兼容而出现runtime error。
3.1.3 C++ type casting:

CBase *pb = dynamic_cast<CBase*>(pd);     // "dynamic" for derived-to-base pointers/references only
CDerived *pd = static_cast<CDerived*>(pb); // for derived-to-base/base-to-derived pointers/references
B *pb = reinterpret_cast<B*>(pa);             // from any pointer to any other pointer
const_cast<T*>(pc);                             // set or remove constness

3.1.4 typeid( type )或typeid( expression )操作符可以返回类型信息，当expression对应多态对象（不包括其指针），则返回most derived complete object的类型信息。
3.1.5 typedef type new_type_name ;可以预处理，创建已知类型（包括模板类）的别名，简化书写。
3.1.6 enum用于建立稀疏的标记类型，如enum state { UNIVISITED = 0, VISITING, VISITED };

3.2 C 语言字符与字符串相关函数
字符相关：isdigit(), isalpha(), tolower(), toupper();
字符串相关：
（返回char*指针）strstr(long,short),·strchr(str,c),strcpy(dest,src), strncpy(dest,src,num),strcat(dest,src);
（返回int值） strlen(str),strcmp(str1,str2)

3.3 sizeof 操作符： sizeof( type ) 或 sizeof expression 返回该文件类型的 size ( in bytes）。

3.4 auto 标示符（C++11）：声明同时初始化变量时，可以使用auto来动态推断类型，而不影响后续的操作。

3.5 Functor：A functor is pretty much just a class which defines the operator().

struct functor{
    int operator()(const type1 &param1, const type2 &param2){
            //return an int value
    }
}

3.6 NULL地址在C++与0的含义等效；C-string的结束符'\0' 的值亦为0。

3.7 std::numeric_limits<T>可以对基本类型使用，通过min()与max()得到临界值，epsilon()得到精度。

4. C++ Keywords

• const 用于标识不可修改的变量，如指针常数 T *const；或 不修改除mutable以外成员变量的成员函数。
• volatile 用于示意编译器变量可从外部修改。
• static 意指变量或函数在scope内的寿命超过他的owner本身，static变量只需初始化一次。特别地，static的成员变量，属于class而非任何实例；static的成员函数，也是如此（可以通过class直接调用）。在plain C中，则具有不同含义：static函数仅对同一文件内的其它函数可见。

5.C++ STL 常用函数

5.1 对于一维双向有序数据结构如<vector>& <list>，有push_back(), pop_back() ; insert(iterator it,const val_type& val); erase(iterator it)。

5.2 对于一维单向有序数据结构如<stack>, <queue>,有pop(), push(const val_type& val)。

5.3 对于多维或无序数据结构如<map>,<set>,<unordered_map>,<unordered_set>, insert函数的参数是其基本元素（pair或key ), erase函数的参数为iterator，find(const val_type& val)的返回值为亦对应的iterator，在检索不到时返回end()

5.4 关于自定义Compare函数或类的用法:
a.如果在模板中声明Compare（如 map<K,V,Compare>或 priority_queue<K, vector<K>,Compare>），则创建一个functor类: class comp，并在其中重载typename K的运算符: bool operator(){ const K& param1,const K &param2) const;
b.如果在函数（包括构造函数）中声明Compare，则定义bool comp (K &param1, K &param2 ); 或创建一个functor，并将comp作为参数传入函数即可。

5.5 排序函数 void sort( iterator first, iterator last, Compare comp );
默认按照升序排列，不保证stable sort。此处iterator也可为数组头尾指针，comp可以是函数指针或functor（如greater<int>()）。当缺少comp参数时，以<操作符判断元素之间的严格弱序（自定义对象可以重载操作符）。

5.6 std::ref()提供reference wrapper，通常用于"call_back"函数或创建thread；std::move()用于转移内容，通常用于不可复制的对象。

6.Stream类
fstream与stringstream继承iostream，默认继承istream与ostream操作符与函数：

• fstream::open(const char*),fstream::close()；stringstream str( const string& ) 或使用构造函数初始化；
• good()标识无错误且未到EOF；
• 输入流：>>操作符，get(char *s,n)，getline(s,n)或getline(istream &,string &)，ignore(int,char);
• 输出流：<<操作符。

7.Exceptions
Exceptions provide a way to react to exceptional circumstances (like runtime errors) in our program by transferring control to special functions called handlers.

e.g. Possible bad allocation:

try{
    int* myarray= new int[1000];
 }catch (exception& e){
    cout << "Standard exception: " << e.what() << endl;
}