位图

每一个比特位来表示当前比特位对应的数据是否存在，存在为1，不存在为0

整数数组：

1. 整数位置：n/32
2. 整数位置中具体的bit位置：n%32

• 右移相当于除，右移n位 == 数字➗2^n^

位图实现：哈希表

1. 实现：整数数组
2. 数据单元是bit位
3. 节省空间，一个字节可以存放8个整数的二值信息（存在与否），不存放数据本身
4. 操作效率高，通过哈希映射获取位置，通过位运算执行操作， 时间效率O(1)
5. 位置映射：
   1. 获取整数位置，n / 32
   2. 获取整数的比特位：n % 32
6. 位图需要的空间大小和数据的范围有关，和数据本身大小没有关系
7. 适合的场景：数据不重复，信息简单

二叉搜索树

• 若左子树非空，则左子树上所有节点的值都小于根节点的值
• 若右子树非空，则右子树上所有节点的值都小根节点的值
• 左右子树也是二叉搜索树

上述条件反之亦可

多态的概念、定义以及实现

多种形态，当不同的对象去执行同一种行为时，产生的不同表现形态

构成条件：在不同的继承关系的类对象，去调用同一函数，产生了不同的行为

1. 继承关系
2. 必须通过基类的指针或者引用调用的虚函数，一般都是用父类指针/引用指向父类以及子类实体，即都为切片行为
3. 被调用的函数必须是虚函数，且派生类必须对基类的虚函数进行重写

继承概念

类级别的代码复用

1. 继承方式：public、protected、private
2. protectde访问权限/private访问权限：
   • protected —-> 在当前类和子类中可见，在其他地方不可见
   • private —-> 在当前类中可见，在其他地方不可见
3. 父类成员在子类中的访问权限：min { 成员在父类中的原始访问权限，继承方式 }
4. 一般都是public继承，protected/private继承很少使用/几乎不用
5. 默认继承方式：
   • class定义的类默认继承方式是private
   • struct定义的类默认继承方式public

stack的基本使用

1
2
3
4
5
6
7
8
9
10
11

#include<stack>
stack<int> st;
st.push(1);
st.push(2);
st.push(3);
while(!st.empty())
{
  cout << st.top() << " ";
  st.pop();
}
cout << endl;

list的基本使用

本质为双向带头循环列表

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向带头循环链表，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
4. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

vector的基本使用

1
2
3
4
5
6
7
8
9
10

vector<int> v;
vector<char> v2;
vector<string> v3;

vector<int> v4(10, 5);//10个5

string s2 = "0123456789";
vector<char> v5(s2.begin(), s2.end());

vector<char> v6(v5);

string类基本使用

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

#include <string>

void test()
{
  string str;//""
  string str2("123");//"123"
  string str3 = "abc";//"abc"
  string str4("0123456789", 5);//"01234"
  string cpy(str3);//"abc"
  
  string str5(str4, 2, 2);//"23" 从str4的第2个位置拿两个字符创建一个字符串
  string str6(10, a);//"aaaaaaaaaa"
  
  str6 = str5;//操作符重载
  str6 = "321";
  str6 = "xyz";
}

泛型编程

编写与类型无关的代码

1

template <typename / class 泛型参数1, typename / class 泛型参数2 ...... >

告诉编译器一个模板，让编译器根据不同的类型利用该模板生成代码

C/C++内存分布

1. 栈：非静态局部变量，函数参数，返回值等，栈是向下增长的
2. 内存映射段：装载一个共享的动态内存库
3. 堆：用于程序运行时动态内存分配，可以向上增长
4. 数据段：存储全局变量和静态数据
5. 代码段：可执行的代码、只读常量