文章目录
一、C++ STL standard template libaray 标准模板库
1.顺序容器
vector：
底层数据结构：动态开辟的数组
扩容方式：每次以原来空间大小的2倍进行扩容
具体过程：
当需要在 std::vector 中插入元素时，如果当前容量足够，则直接在当前内存空间进行插入操作。
如果当前容量不足以容纳新元素，则需要进行扩容操作。
std::vector 会分配一个新的更大的内存空间，通常是当前容量的两倍或根据具体实现策略进行动态调整。
接下来，std::vector 将会将原来的元素逐个复制到新的内存空间中。
扩容完成后，原来的内存空间将会被释放，而新的内存空间将会成为 std::vector 的内部存储空间。
vec.push_back(20); vec.erase(it迭代器);
deque：
底层数据结构：动态开辟的二维数组
扩容方式：一维数组从2开始，以2倍的方式进行扩容，每次扩容后，原来第二维的数组，从新的第一维数组的下标oldsize/2开始存放，上下都预留相同的空行，方便支持deque的首尾元素添加；
通过动态增加内存块来实现的。当需要在 std::deque 的前端或后端插入元素时，如果当前内存块已满，std::deque 将会分配一个新的内存块。
添加：
deq.push_back(20); 从末尾添加元素 O(1)
deq.push_front(20); 从首部添加元素 O(1) // vec.insert(vec.begin(), 20) O(n)
deq.insert(it, 20); it指向的位置添加元素 O(n)
删除：
deq.pop_back(); 从末尾删除元素 O(1)
deq.pop_front(); 从首部删除元素 O(1)
deq.erase(it); 从it指向的位置删除元素 O(n)
list:
底层数据结构：双向的循环链表 pre data next
区别：
vector特点：动态数组，内存是连续的，2倍的方式进行扩容，
vector vec; 0-1-2-4-8… reserve(20)/resize
deque特点：动态开辟的二维数组空间，第二维是固定长度的数组空间，扩容的时候（第一维的数组进行2倍扩容）
deque底层内存是否是连续的？并不是，每一个第二维是连续的
容器的纵向考察：容器掌握的深度
容器的横向考察：各个相似容器之间的对比
vector和deque之间的区别？
1.底层数据结构
2.前中后插入删除元素的时间复杂度： 中间和末尾 O(1) 前 deque O(1) vector O(n)
3.对于内存的使用效率： vector 需要的内存空间必须是连续的, deque 可以分块进行数据存储，不需要内存空间必须是一片连续的
4.在中间进行insert或者erase，vector和deque它们的效率谁能好一点(vector)？谁能差一点(deque)？ O(n)
vector和list之间的区别？
数组:增加删除O(n) 查询O(n) 随机访问O(1) 链表:(考虑搜索的时间)增加删除O(1) 查询O(n)
2.容器适配器
stack
queue
priority_queue
什么是适配器？为什么叫适配器？
- 适配器底层没有自己的数据结构，它是另外一个容器的封装，它的方法全部由底层依赖的容器进行实现的
- 没有实现自己的迭代器
stack: push入栈 pop出栈 top查看栈顶元素 empty判断栈空 size返回元素个数
queue: push入队 pop出队 front查看队头元素 back查看队尾元素 empty判断队空 size返回元素个数
priority_queue: push入队 pop出队 top查看队顶元素 empty判断队空 size返回元素个数 默认：大根堆
问：queue => deque 为什么不依赖vector呢？？？stack => deque 为什么不依赖vector呢？？？
1.vector的初始内存使用效率太低了！没有deque好 queue stack vector 0-1-2-4-8 deque 4096/sizeof(int) = 1024
2.对于queue来说，需要支持尾部插入，头部删除，O(1) 如果queue依赖vector，其出队效率很低
3.vector需要大片的连续内存，而deque只需要分段的内存，当存储大量数据时，显然deque对于内存的利用率更好一些
问：priority_queue => vector，为什么依赖vector？？？
底层默认把数据组成一个大根堆结构，在一个内存连续的数组上构建一个大根堆或者小根堆的
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
int main()
{
priority_queue<int> pque;
for (int i = 0; i < 20; ++i)
{
pque.push(rand() % 100 + 1);
}
cout << pque.size() << endl;
while (!pque.empty())
{
cout << pque.top() << " ";
pque.pop();
}
cout << endl;
cout << "---------------------------" << endl;
queue<int> que;
for (int i = 0; i < 20; ++i)
{
que.push(rand() % 100 + 1);
}
cout << que.size() << endl;
while (!que.empty())
{
cout << que.front() << " ";
que.pop();
}
cout << endl;
cout << "---------------------------" << endl;
stack<int> s1;
for (int i = 0; i < 20; ++i)
{
s1.push(rand() % 100 + 1);
}
cout << s1.size() << endl;
while (!s1.empty())
{
cout << s1.top() << " ";
s1.pop();
}
cout << endl;
system("pause");
return 0;
}
3.关联容器
3.1 无序关联容器 => 链式哈希表 增删查O(1)
unordered_set set1
不会存储key值重复的元素：利用此特征进行海量数据去重
插入:set1.insert(15) 查找:set1.count(15)
海量数据去重
#include <unordered_map>
#include <unordered_set>
#include <iostream>
using namespace std;
int main()
{
// 处理海量数据查重复；去重复的时候
const int ARR_LEN = 100000;
int arr[ARR_LEN] = { 0 };
for (int i = 0; i < ARR_LEN; ++i)
{
arr[i] = rand() % 20 + 1;
}
// 上面的10万个整数中，把数字进行去重打印 set map
unordered_set<int> set;
for (int v : arr) // O(n)
{
set.insert(v); // O(1)
}
for (int v : set)
{
cout << v << " ";
}
cout << endl;
return 0;
}
统计重复次数
#include <unordered_map>
#include <unordered_set>
#include <iostream>
using namespace std;
int main()
{
// 处理海量数据查重复；去重复的时候
const int ARR_LEN = 100000;
int arr[ARR_LEN] = { 0 };
for (int i = 0; i < ARR_LEN; ++i)
{
arr[i] = rand() % 20 + 1;
}
// 上面的10万个整数中，统计哪些数字重复了，并且统计数字重复的次数
unordered_map<int, int> map1;
for (int k : arr)
{
map1[k]++; // map1[k] [k, 1]
}
auto it = map1.begin();
for (; it != map1.end(); ++it)
{
if (it->second > 1)
{
cout << "key:" << it->first <<
" count:" << it->second << endl;
}
}
return 0;
}
set:集合 key map:映射表 [key,value]
unordered_set 单重集合
unordered_multiset 多重集合
unordered_map 单重映射表
unordered_multimap 多重映射表
3.2 有序关联容器 => 红黑树 增删查O(log2n) 2是底数(树的层数，树的高度)
set
multiset
map
multimap
有序关联容器（如 std::set 和 std::map）使用红黑树作为底层实现的主要原因是红黑树能够提供高效的查找、插入和删除操作，同时保持元素有序。
红黑树是一种自平衡二叉搜索树，具有以下特点：
每个节点都有一个颜色属性，通常为红色或黑色。
根节点和叶子节点（即空节点）都是黑色的。
如果一个节点是红色的，则它的子节点必须是黑色的。
对于任意节点，从该节点到其后代叶子节点的每条路径上，黑色节点的数量必须相同。
通过这些特性，红黑树能够保持树的平衡，使得查找、插入和删除操作的平均时间复杂度为 O(log n)，其中 n 是树中元素的数量。
在有序关联容器中，元素按照键的顺序进行存储和组织。通过使用红黑树作为底层实现，可以在 O(log n) 的时间复杂度内快速查找和插入元素，同时保持元素有序。红黑树的自平衡特性确保了树的高度相对较低，从而提供了高效的操作性能。
此外，红黑树还支持一些其他的操作，如范围查询和遍历有序元素。这使得红黑树成为实现有序关联容器的理想选择。
需要注意的是，虽然红黑树是常用的底层实现方式，但具体的实现细节可能因不同的标准库或实现而有所差异。但无论如何，红黑树提供了一种高效且可靠的数据结构，用于实现有序关联容器。
二、近容器
数组，string，bitset(位容器)
三、迭代器
iterator和const_iterator
reverse_iterator和const_reverse_iterator
const_iterator:常量的正向迭代器 只能读，不能进行写操作
iterator:普通的正向迭代器
reverse_iterator:普通的反向迭代器
const_reverse_iterator:常量的反向迭代器
const_iterator底层代码：
//底层代码
// vector<int>::iterator
// auto it1 = vec.begin();
// const_iterator <= iterator
class const_iterator
{
public:
const T& operator*(){return *_ptr;}
}
class iterator : public const_iterator
{
T& operator*(){return *_ptr;}
}
// rbegin()：返回的是最后一个元素的反向迭代器表示
// rend：返回的是首元素前驱位置的迭代器的表示
// vector<int>::reverse_iterator
其实一般都auto = vec.begin();
vector<int> vec;
for (int i = 0; i < 20; ++i)
{
vec.push_back(rand() % 100);
}
vector<int>::const_iterator it1 = vec.begin();
for (; it1 != vec.end(); ++it1)
{
cout << *it1 << " ";
}
cout << endl;
四、函数对象（类似C的函数指针）
greater,less
1.通过函数对象调用operator()，可以省略函数的调用开销，比通过函数指针调用函数（不能够inline内联调用）效率高
2.因为函数对象是用类生成的，所以可以添加相关的成员变量，用来记录函数对象使用时更多的信息
C与C++的提升
类和对象：C++ 引入了类和对象的概念，支持面向对象编程。C 语言没有类和对象的概念，只有结构体和函数。
封装和继承：C++ 支持封装和继承，使得开发者能够更好地组织和管理代码。C 语言没有直接的封装和继承机制。
模板：C++ 引入了模板（template）机制，支持泛型编程，使得代码可以在不同的类型上进行通用操作。C 语言没有模板机制。
异常处理：C++ 引入了异常处理机制，允许开发者捕获和处理异常情况。C 语言没有内置的异常处理机制。
五、泛型算法(C++特性)
sort,find,find_if,binary_search,for_each
泛型算法 = template + 迭代器 + 函数对象
特点一：泛型算法的参数接收的都是迭代器
特点二：泛型算法的参数还可以接收函数对象（C函数指针）
sort,find,find_if,binary_search,for_each
绑定器 + 二元函数对象 =》 一元函数对象
bind1st：把二元函数对象的operator()(a, b)的第一个形参绑定起来
bind2nd：把二元函数对象的operator()(a, b)的第二个形参绑定起来
#include <iostream>
#include <vector>
#include <algorithm> // 包含了C++ STL里面的泛型算法
#include <functional> // 包含了函数对象和绑定器
using namespace std;
int main()
{
int arr[] = { 12,4,78,9,21,43,56,52,42,31};
vector<int> vec(arr, arr+sizeof(arr)/sizeof(arr[0]));
for (int v : vec)
{
cout << v << " ";
}
cout << endl;
// 默认小到大的排序
sort(vec.begin(), vec.end());
for (int v : vec)
{
cout << v << " ";
}
cout << endl;
// 有序容器中进行二分查找
if (binary_search(vec.begin(), vec.end(), 21))
{
cout << "binary_search 21" << endl;
}
auto it1 = find(vec.begin(), vec.end(), 21);
if (it1 != vec.end())
{
cout << "find 21" << endl;
}
// 传入函数对象greater，改变容器元素排序时的比较方式
sort(vec.begin(), vec.end(), greater<int>());
for (int v : vec)
{
cout << v << " ";
}
cout << endl;
// 78 56 52 43 42 31 21 12 9 4
// 把48按序插入到vector容器当中 找第一个小于48的数字
// find_if需要的是一个一元函数对象
// greater a（48） > b less a < b(48)
auto it2 = find_if(vec.begin(), vec.end(),
//bind1st(greater<int>(), 48));
//bind2nd(less<int>(), 48));
[](int val)->bool {return val < 48; });
vec.insert(it2, 48);
for (int v : vec)
{
cout << v << " ";
}
cout << endl;
// for_each可以遍历容器的所有元素，可以自行添加合适的函数对象对容器
// 的元素进行过滤
for_each(vec.begin(), vec.end(),
[](int val)->void
{
if (val % 2 == 0)
{
cout << val << " ";
}
});
cout << endl;
system("pause");
return 0;
}
