AVL树

• 左右子树都是AVL树
• 左右子树高度差的绝对值不超过1（-1/0/1）（一般：右子树高度 - 左子树高度）
• 如果一棵二叉搜索树树高度平衡的，它就是AVL树。如果它有n个节点，其高度可保持在O(log₂N)，搜索时间复杂度O(log₂N)

set

1. 实现—->目前使用搜索树实现（红黑树）
2. 底层是一个存放KV结构的搜索树，但是此处K、V相同
3. set中只需要存放value
4. set中不能存放重复的元素
5. set中的元素不能修改，不支持修改的操作
6. set默认比较是小于，可以通过修改仿函数，修改比较逻辑
7. 迭代器遍历有序：底层顺序是二叉搜索树的中序遍历
8. 迭代器只能读取内容，不能修改内容
9. 插入：如果用迭代器指定插入位置，最终实际的插入位置可能不是指定的位置，此处的位置只是一个建议，新的元素的插入位置必须符合搜索树的性质
10. 删除会导致当前删除位置的迭代器失效，但是不影响其他位置的迭代器
11. find：找到返回元素的迭代器，未找到返回end迭代器
12. count：获取指定元素在set中的个数，根据性质4，只用两个值，1或0

位图

每一个比特位来表示当前比特位对应的数据是否存在，存在为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";
}