左值和右值

左值（lvalue）：指向内存位置的表达式被称为左值（lvalue）表达式。左值可以出现在赋值号的左边或右边。 右值（rvalue）：术语右值（rvalue）指的是存储在内存中某些地址的数值。右值是不能对其进行赋值的表达式，也就是说，右值可以出现在赋值号的右边，但不能出现在赋值号的左边。

变量类型

int a = 0; //全局初始化区 
char *p1; //全局未初始化区 
main() 
{ 
    int b; //栈 
    char s[] = "abc"; //栈 
    char *p2; //栈 
    char *p3 = "123456"; //123456\0在常量区，p3在栈上。 
    static int c =0； //全局（静态）初始化区 
    p1 = (char *)malloc(10); //堆 
    p2 = (char *)malloc(20);  //堆 
}

栈比堆快的原因

1. 栈是连续的地址
2. 栈由于更经常使用，所以会被加载到高速缓存上面。

c++ STL

容器，算法，还有迭代器:iterator

包括顺序容器，和关联容器（key-value)

Vector:

O(1) 快速访问，除了删除最后一个，其他操作都是O(n)；当我们新建一个vector的时候，会首先分配给他一片连续的内存空间，如std::vector vec，当通过push_back向其中增加元素时，如果初始分配空间已满，就会引起vector扩容，其扩容规则在gcc下以2倍方式完成

在插入位置和删除位置之后的所有迭代器和指针引用都会失效，同理，扩容之后的所有迭代器指针和引用也都会失效。

Map, mutliplemap

底层数据结构均为红黑树，查找，插入和删除都是O(n)

unordered_map

底层数据结构是hash_table。要看有没有冲突

priority_queue 通过heap实现

取出最大元素是O(1),插入和删除都是O(logN)

List

双向链表：支持快速删除，增加

queue,deque

queue 是单向队列，先入先出 deque 双向队列，可以在头尾两端实现高效的插入和删除；两边都可以双向

Sort

C++ Peking University

Inline

Inline functions can get avoid extra run-time stacks of function calls.

Overloading

it can have two definitions, leading to errors

It is called re-definition when only return values is different

lack of arguments 实参

Increase the scalability of softwares; you don’t need to modify function calls.

Object-Oriented Programming

Easy to test, modify and expanse

Sizeof(class) = size of class variables.

Only “=” can be used before overloading

Member Range

private (by default), public, protected

private members: only can be accessed by member functions

Encapsulation

through .h files to the class

Avoid conflicts of names

Memory

Stack Memory

Stack Memory: stack memory always starts from high addresses and grows down:

after return values, stack memory is de-allocated

Memory overwritten: should not return pointers pointed to the value

Never return a pointer pointed to a local variable

Heap Memory

start from low-address, and grow up!

Heap memory allows us to create memory independent of the lifecycle of a function

int* numptr = new int;

• memory to store an integer pointer on the stack
• memory to store an integer on the heap

after delete, pointers = nullptr;

.h files are “header files”. These usually have definitions of objects and declarations of global functions. Recently, some people name header files with a “.hpp” suffix instead.

.cpp files are often called the “implementation files,” or simply the “source files”. This is where most function definitions and main program logic go.

Constructor

standard constructor

default constructor is not working when we define a custom constructor

copy constructor

A copy constructor creates a new object (constructor).

Often, copy constructors are invoked automatically: • Passing an object as a parameter (by value) • Returning an object from a function (by value) • Initializing a new object

One argument: const Cube & obj

 Cube::Cube(const Cube & obj) {
    length_ = obj.length_;
 }

copy constructor != assignment

Assignment Operator

Cube & Cube::operator=(const Cube & obj) {
  length_ = obj.length_;
  std::cout << "Assignment operator invoked!" << std::endl;
  return *this;
}

Variable Storages

Reference

The alias must be assigned when the variable is initialized;

Don’t need to apply copy constructor !!! Just an alias

Destructor

Cube:: ~ Cube(){};

Template Types

Tower of Hanoi Problem

check 0 -> 1 or 1 -> 0 check 0 -> 2 or 2 -> 0 check 1 -> 2 or 2 -> 1

Templates and Classes

template <typename T>
T max(T a, T b)
{
    return a > b? a:b;
}

Inheritance

Inheritance allows for a class to inherit all member functions and data from a base class into a derived class.

#include "Cube.h"
#include "Shape.h"
namespace uiuc {
    Cube::Cube(double width, uiuc::HSLAPixel color) : Shape(width) {
      color_ = color;
    }
    double Cube::getVolume() const {
      // Cannot access Shape::width_ due to it being `private`
      // ..instead we use the public Shape::getWidth(), a public function:
      return getWidth() * getWidth() * getWidth();
    }
}

给隐含的this指针加const，表示这个this指向的东西是const的，也就是说这个函数中无法改动数据成员了。const是一种保证，告诉你这个成员不会改变对象的状态。

#include "Shape.h"
Shape::Shape() : Shape(1) {
// Nothing.
}
Shape::Shape(double width) : width_(width) {
// Nothing.
}
double Shape::getWidth() const {
  return width_;
}

static

static 函数要调用 unstatic variables, should set them as arguments since static functions are global functions with some limits.

Remember: static functions cannot use unstatic variables since we don’t know which object it belongs to!!

产量函数可以修改静态成员变量，和静态成员函数，因为他们不属于某个对象，就不会修改对象。 不能访问非产量成员函数，因为不知道会不会修改对象成员变量！！！自动报错，无法自己判断。

static成员变量和成员函数属于类和派生类， 他们共享一个static变量或者函数！！ 可以通过类名或者对象调用

#include <iostream>
#include <vector>

using namespace std;

class Base
{
    private:
        int length;
    public:
        static void staticFunc(){cout << "static function" << endl;}
        virtual void func1(){cout << "base" << endl;}
        Base operator=(const Base& obj)
        {    
            length = obj.length;
            cout << "assignment overloadding !!" << endl;\
            return *this;
        }
        Base(int a):length(a){cout << "custom constructor!!"<< endl;}
        Base(){}
        Base(const Base& obj){length = obj.length; cout << "copy constructor!" << endl;}
};

class Derived:public Base
{
    public:
        Derived(int a):Base(a){};
        void func1(){cout << "derived" << endl;}
};

void print(Base* base)
{
    base -> func1();
    return;
}

int main()
{
    Base* base = new Base(1);
    Derived* derived = new Derived(1);
    print(base);
    print(derived);

    // copy constructor and assignment operator overloading
    Base obj1(1);
    Base obj2(obj1);
    Base obj3;// overloading of constructors
    obj3 = obj2;

    // static functions: public area in memory
    // can be called by objects, derived objects, class name
    obj1.staticFunc();
    Base::staticFunc();
    Derived::staticFunc();
    derived->staticFunc();
    return 0;
}

friend

一个类的友元函数，可以传入类的对象，然后可以访问对象的私有成员

一个类的友元类，可以访问该类的私有成员

友元关系，不能传递，不能继承

Rectangle* this 和 静态成员

this 指针相当于C++翻译成C语言的时候，成员函数多了一个this参数。用于指向成员函数所作用的对象，所以静态成员函数不能访问this指针，因为静态成员函数是属于整个类的，不是某个对象的。自然，静态成员函数只能访问静态成员变量和函数，不能访问非静态变量和函数，因为非静态属于某个类，而静态成员函数并不属于某个类。

可以通过构造函数，包括复制构造函数，析构函数修改静态成员变量（在对象创建和销毁的时候）。

const object, const class functions

可以修改静态成员变量，和静态成员函数，因为他们不属于某个类，不会修改对象。 不能访问非产量成员函数，因为不知道会不会修改对象成员变量！！！自动报错，无法自己判断。

常量对象可以执行产量成员函数

两个成员函数，名字和参数表都一样，但是一个是const,一个不是，算重载。

Overloading

赋值运算符 “=” 只能重载为成员函数

析构函数的时候释放同一内存两次，出错； 默认是浅拷贝 shallow copy

返回值类型，不能是void

设计复制构造函数的时候，也要考虑shallow copy的问题，内存重复释放。

虚函数 和 多态 Polymorphism

在面向对象的程序设计中使用多态，能够增强程序的可扩充性，即程序需要修改或增加功能 的时候，需要改动和增加的代码较少。

代价是时间和空间额外的开销：

• 空间：每个有虚函数的类都会多4个字节，代表虚函数表的指针
• 时间：在虚函数表中查询当前类的虚函数

构造函数和静态成员函数不能是虚函数

派生类的指针可以赋值给基类指针

派生类的引用可以赋值给基类

虚函数，这样不用为每个派生类写不一样的函数，比如求总面积。不用为各种派生类写不一样的totalArea(); 而只需要参数都是Shape* s1, Shape* s2 去调用基类的虚函数 virtual function； 这样可以调用派生类不同的area function， 按照各自的计算方法计算。

扩展性很好，添加新的派生类写一个area() 函数就好了，不用去修改其他子类的内容；

用基类指针数组存放指向各种派生类对象的指针，然后遍历该数组，就能对各个派生类对象做各种操作。

在非析构函数，非构造函数的成员函数中调用虚函数，是多态！！

多态实现原理

“多态”的关键在于通过基类指针或引用调用一个虚函数时，编译时不确定到底调用的是基类还是派生类的函数，运行时才确定 —- 这叫“动态联编”。

虚函数表的指针 + variable member

虚函数表：每个有虚函数的类，都有一个虚函数表，该类的任何对象中都反着虚函数表的指针。虚函数表存的就是同一个类的不同虚函数的地址。

虚析构函数

纯虚函数

形成抽象类，只能是基类；不能创建抽象类的对象；

实现所有的纯虚函数，才能成为非抽象类；不是=0就行，{}也是可以的

文件操作 file operation: ifstream, ofstream, fstream

• ifstream: read
• ofstream: write
• fstream: read or write

Templates –> Generic Programming

adapt to different kinds of data structures

template <class T>
void Swap(T & x, T & y)
{
  T tmp = x;
  x = y;
  y = tmp;
}

template<class T1, class T2>
T2 print(T1 arg1, T2 arg2)
{
  cout << arg1 << arg2 << endl;
  return arg2;
}


template <class T>
T MaxElement(T a[], int size) //size是数组元素个数
{
   T tmpMax = a[0];
   for( int i = 1; i < size; ++i )
   if( tmpMax < a[i] )
   tmpMax = a[i];
   return tmpMax;
}

类模板：class templates

类模板的实例化过程：自动用具体的数据类型，生成模板类的代码

两个模板类是不兼容的

可以包括类型参数，和非类型参数； 非类型参数不一致 （int) 也会导致是不同的模板类

函数指针

类型名 (* 指针变量名)(参数类型1, 参数类型2,…);

int (*pf)(int ,char);

函数指针作为参数传入到函数里面，很有用~

动态分配

new T[] 返回也是 T*

访问范围

protected

当前对象的基类的protected成员是可以被派生类访问的

shared_ptr

overload, override, re-definition

函数重载（overload） 函数重载是指在一个类中声明多个名称相同但参数列表不同的函数，这些的参数可能个数或顺序，类型不同，但是不能靠返回类型来判断。特征是： （1）相同的范围（在同一个作用域中）； （2）函数名字相同； （3）参数不同； （4）virtual 关键字可有可无（注：函数重载与有无virtual修饰无关）； （5）返回值可以不同；

函数重写（也称为覆盖 override） 函数重写是指子类重新定义基类的虚函数。特征是： （1）不在同一个作用域（分别位于派生类与基类）； （2）函数名字相同； （3）参数相同； （4）基类函数必须有 virtual 关键字，不能有 static 。 （5）返回值相同，否则报错； （6）重写函数的访问修饰符可以不同；

重定义（也称隐藏） （1）不在同一个作用域（分别位于派生类与基类） ； （2）函数名字相同； （3）返回值可以不同； （4）参数不同。此时，不论有无 virtual 关键字，基类的函数将被隐藏（注意别与重载以及覆盖混淆）； （5）参数相同，但是基类函数没有 virtual关键字。此时，基类的函数被隐藏（注意别与覆盖混淆）；

C++ Interview Questions

strcpy, strcat, strlen, strcmp

#include <assert.h>
#include <stdio.h>

char* strcpy(char* des, const char* src)
{
    assert((des!=NULL) && (src!=NULL)); 
    char* res = des;
    while ((*des++ = *src++) != '\0')
    {;}
    return res;
}

int strlenMy(const char* src)
{
    assert(src != NULL);
    int res = 0;
    while ((*src++) != '\0')
    {
        res++;
    }
    return res;
}

char* strcat(char* des, char* src)
{
    assert((des!=NULL) && (src!=NULL)); 
    char* res = des;
    while (*des != '\0'){des++;}
    while (*src != '\0')
    {
        *des++ = *src++;
    }
    *des = '\0';
    return res;
}

int strcmp(char* str1, char* str2)
{
    assert((str1!=NULL) && (str2!=NULL));
    while (*str1 == *str2)
    {
        if (*str1 == '\0') return 0;
        ++str1;
        ++str2;
    }
    return *str1 - *str2; 
}

int main()
{
    char a[4] = "abc";
    char b[4] = "abd";
    // printf("%d",strlenMy(a));
    // printf("%c",a[0]);
    // printf("\n%s",strcat(a,b));
    printf("%d",strcmp(a,b));
    printf("\n%d",strlenMy(a));
    return 0;
}

TCP/IP

三次握手

1. 客户端发送一个SYN段，并指明客户端的初始序列号，即ISN(c).
2. 服务端发送自己的SYN段作为应答，同样指明自己的ISN(s)。为了确认客户端的SYN，将ISN(c)+1作为ACK数值。这样，每发送一个SYN，序列号就会加1. 如果有丢失的情况，则会重传。
3. 为了确认服务器端的SYN，客户端将ISN(s)+1作为返回的ACK数值。

四次挥手

1. 客户端发送一个FIN段，并包含一个希望接收者看到的自己当前的序列号K. 同时还包含一个ACK表示确认对方最近一次发过来的数据。
2. 服务端将K值加1作为ACK序号值，表明收到了上一个包。这时上层的应用程序会被告知另一端发起了关闭操作，通常这将引起应用程序发起自己的关闭操作。
3. 服务端发起自己的FIN段，ACK=K+1, Seq=L
4. 客户端确认。ACK=L+1

Linux operations

GDB: debugging with run and frames

valgrind: check if allocated dynamic memory has been released or not

• Previous
  Parallel Computing
• Next
  Float Computing