只能在堆上创建对象的类

1. 构造函数私有
2. 提供一个静态的堆上创建对象的方法
3. 防止拷贝（拷贝构造声明为私有且不实现，或者声明为delete）

列表初始化

C++11：支持内置类型与自定义类型的列表初始化，其中自定义类型不是天然支持列表初始化，需要显示定义参数类型为initiaizer_list的构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class A
{
public:
  A (int a, int b)
    : _a(a)
    , _b(b)
  { }
private:
  int _a;
  int _b;
};


int arr[] = {1, 2, 3, 4, 5};

int a = 1;
int b = { 1 };
int c{ 1 };
float d = { 1.2 };

vector<int> arr1{1, 2, 3, 4, 5};
vector<int> arr2 = {1, 2, 3};

pair<int, int> p = {1, 1};
map<int, int> m = { {1, 1}, {2, 2}, {3, 3} };

A a = {1, 2};
A a(1, 2);

无序关联容器

unordered_map

基本使用与map相同，迭代器无反向迭代器，无序map，其体现在遍历时无序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <unordered_map>

void testUMap()
{
	unordered_map<int, int> um;
	map<int, int> m;

	um.insert(make_pair(1, 1));
	um.insert(make_pair(10, 1));
	um.insert(make_pair(2, 1));
	um.insert(make_pair(15, 1));
	um.insert(make_pair(8, 1));

	um[100] = 100;//插入
	um[15] = 15;//修改

	um.at(2) = 2;//at无法插入，key不存在直接抛异常

	//遍历无序
	unordered_map<int, int>::iterator uit = um.begin();
	while (uit != um.end())
	{
		cout << uit->first << "-->" << uit->second << endl;
		uit++;
	}
  
  uit = um.find(100);//find找到返回指定位置迭代器，找不到则返回end迭代器
	cout << um.count(100) << endl;//count返回元素个数，1或0
	cout << uit->first << "-->" << uit->second << endl;
	uit = um.find(20);
	cout << um.count(20) << endl;
	cout << (uit == um.end()) << endl;
}

改造红黑树

关联式容器存储的是K， V键值对，故在改造红黑树时，K为key类型，对于V来说，如果是set，则其为K类型，如果是map则为

pair<K, V>，类型，除此之外，还需要一个仿函数类KeyOfValue来兼容map与set的大小比较，其迭代器也需要封装指针为一个类，迭代器的自加自减相当于红黑树的中序遍历

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