{读书笔记} C++ language

Inside the C++ object model

Chapter 1: Objects lessons
  C++ object model
    Each class object in C++ has a pointer named vptr which points to a table that store all virtual function pointers this class
  has and a type_info object associated with this class in support of runtime type identification (RTTI) is also addressed 
  within the virtual table, usually within the table's first slot. And all objects of this class share this virtual table, I 
  think.
    Problem: it's still like this for new C++ (C11)?
  
  Inheritance
      In the case of virtual inheritance, only a single occurrence of the base class is maintained (called a subobject) 
    regardless of how many times the class is derived from within the inheritance chain. 
      ?:Virtual inheritance is a technique used in object-oriented programming, where a particular base class in an inheritance hierarchy is declared to share its member data instances with any other inclusions of that same base in further derived classes. For example, if class A is normally (non-virtually) derived from class X (assumed to contain data members), and class B likewise, and class C inherits from both classes A and B, it will contain two sets of the data members associated with class X (accessible independently, often with suitable disambiguating qualifiers). But if class A is virtually derived from class X instead, then objects of class C will contain only one set of the data members from class X.
      Object model of base class instance: the data members of base class object are directly stored within the derived class   
    object

  A keyword distinction
    Meta-language rule: when the language can't distinguish between a declaration and an expression, it is to be interpreted as a declaration
    int (*pf) (); //right declaration
    int ( *pf )( 1024 ); //wrong definition or declaration or invocation
    ( *pf )( 1024 ); //right invocation
    struct == class except for the data member layout
    The data members within a single access section are guaranteed within C++ to be laid out in the order of their declaration. The layout of data contained in multiple access sections, however, is left undefined. The layout of data members of the base and derived classes is left undefined

  An object distinction
    three C++ programing paradigms:
      1. The procedural model as programmed in C, and, of course, supported within C++.
      2. The abstract data type (ADT) model in which users of the abstraction are provided with a set of operations (the public interface), while the implementation remains hidden.
      3. The object-oriented (OO) model in which a collection of related types are encapsulated through an abstract base class providing a common interface.
    
    Polymorphism
      Only the indirect manipulation of the object through a pointer or reference supports the polymorphism necessary for OO programming. Because in the ADT paradigm the programmer manipulates an instance of a fixed, singular type that is completely
defined at the point of compilation.
      Library_materials thing1;
      Book book;

      //Oops: thing1 is not a Book! Rather, book is ``sliced'' — thing1 remains a Library_materials
      thing1 = book;

    The actual type of the object addressed is not resolved in principle until runtime at each particular point of execution ?
    ?: Why, is we can't resolve it or we don't in C++?

    ?: what's Nonpublic derivation in polymorphism ?

    The C++ language supports polymorphism in the following ways:
      1. throught a set of implict conversion, (i.e.) such as the conversion of a derived class pointer to the pointer of its public base class type:
        fruit *ft = new Apple();
      2. through the virtual function mechanism:
        ft->eat();
      3. through the dynamic_cast or typeid operators:
        if (Apple *ap = dynamic_cast<Apple *>(ft))...

    The memory requirments to represent a class object in general:
      1. the accumulated size of nonstatic data members
      2. plus any padding due to aligement constraints
      3. plus any internally generated overhead to support virtuals
    
    The type of a pointer instructs the compiler as to how to interpret the memory found at a particular address and also just how much memory that interpretation should span

    C++多态的原理：
    首先，类型的唯一作用在于帮助编译器确定所在内存位置存储数据的解释形式，是对内存正确解码的钥匙；同时编译器除了相信指针或者引用这把钥匙之外没有其他的线索去确定这一点，因此哪怕内存中实际存储的是类型A，但是编译器也只能把它解释成指针/引用类型X。编译器没法在静态的时候完全确定内存类型，因为函数调用的关系，编译器无法实现对传入的参数进行预估，而同时又保证多态的灵活性。但是这不妨碍利用指针/引用去实现多态，因为对对象实际方法的调用取决于虚表的内容，只要具有继承关系的类型具有相同的虚表入口地址，大家就可以公用同一个指针类型去实现不同的函数调用的相同代码和实现。但是C++的多态是不适用于对象的，对象会在初始化的过程中被编译器保证初始化成正确的虚表形式。对象是确定的。

Chapter 2. the semantics of constructor
=========================================
2.1 default constructor
Compiler help to build a complete and necessary class initialization constructor. So if one class doesn't have a default  
constructor, compiler will create one for it and insert into code; if one class has a default construtor or other  
constructors that do not finish all initialization work (missing some member class object initialization work),  
compiler also help to argument these constructors and insert the necessary initialization work.  

2.2 Copy constructor  
Bitwise Copy Semantics

2.4 Member initialization list  
The order in which the list entries are set down is determined by the declaration order of the members within the class  
declaration, not the order within the initialization list.  
And the initialization list entries are placed before explicit user code.  

Chapter 3. The semantics of data
======================================

The practice of programming

chapter 2: algorithm and data structure
  基本算法：检索和排序

  //quick sort
  void quickSort(int v[], int n) {
    if (n <= 1) return;

    //choose a random pivot
    swap(v, 0, rand() % n);

    int last = 0;

    for (int i = 1; i < n; i++) {
      if (v[i] < v[0]) swap(v, ++last, i);
    }
    swap(v, 0, last);
    quickSort(v, last - 1);
    quickSort(v + last + 1, n - last - 1);
  }
  一般情况下快排都很快，但是在输入很奇特的时候（比如数组所有项都相等），它反而会变的很慢。
  尽量用库：多年的历史证明，程序员能把二分检索程序写正确也是很不容易的。

  //non-recursive quick sort

  Java的快排类

  散列表（HashTable）
  字符串的常见散列函数是把新字符所对应的数值加到之前数值和的倍数上，经验表明31和37（都是素数）是比较适合的倍值
  最慢的排序算法：随即选取一个排列顺序比较O（n!）或者sleep（n）然后打印排序

Chapter 3: 编程语言
  C非常高效，但是代码耦合度高；C++和Java库支持使得代码行数变少，性能略微降低，但是值得；脚本语言开发快，性能一般并且不具有很好的扩展性。
  设计好数据结构对于解决具体问题非常有帮助，好比人的骨架一般。
  不要试图一次解决所有的问题，循环和循序渐进是必须的。

Chapter 4: 界面
  接口是设计，好坏决定了程序的好坏。
  程序很多时候是受小概率事件支配的，也很符合信息论的原理似乎：）

Chapter 7: 性能
  优化的第一要义是不做。
  一般的优化基于发现重复计算的部分，消除他们。重复的部分是不必要的，或者是算法本身不需要（更好的算法可以证明他们是无意义的），或者我们重复计算了同一个问题很多次（动态规划是一个典型的用空间去优化重复计算的算法）。
  空间优化：采用隐含的方式或者一种共同的形式存储公共值，在其他值上花更多的空间和时间。如果其中共性最强的值真正是共有的，这个招数就奏效了。
  常见指令和语句的时间消耗？

the-algorithm-design-manaul.md

layout	title
none	the-algorithm-design-manaul

**** The big O notation

• f(n) = O(g(n)) means f(n) <= cg(n) for n > n0;
  Thus cg(n) is an upper bound on f(n): there exists some constant c such that c*g(n) is always >= f(n) for large enough n.
• f(n) = Ω(g(n)) menas f(n) >= cg(n) for some constants c when n > n0;
  Thus cg(n) is an lower bound on f(n): there exists some constant c such that c*g(n) is always <= f(n) for large enough n
• f(n) = Θ(g(n)) means c1g(n) is an upper bound on f(n) and c2g(n) is an lower bound on f(n); Thus, there exists some constants c1, c2 such that c1g(n) is always >= f(n) and c2g(n) is always <= f(n) for large enough n

*** Data structure

• dynamic array: actually resizing array only double the array data write overall. Each elements in the array move only two times on average.

    void delete_list(list **l, int item) {
        if (!l || !(*l)) return;
        list *p = *l;
        if (p->data == item) *l = p->next;
                    
        while (p->next) {
            if (p->next->data == item) {
                p->next = p->next->next;
                return;
            } else
                p = p->next;
        }
    }  
  

• binary search tree

    class Tree { //Tree<T>
        int value;  //or T item
        Tree *parent;
        Tree *left;
        Tree *right;
    }
    
    Tree *insert(Tree *root, int v) {
        if (!root) {
            Tree *node = new Tree();
            node->value = v;
            node->parent = NULL;
            return node;
        }
        
        if (v < root->value) {
            root->left = insert(root->left, v);
            root->left->parent = root;
        } else {
            root->right = insert(root->right, v);
            root->right->parent = root;
        }
        
        return root;
    }