STL

结论 allocator 分配器是定义内存模型的类，用于标准库的某些部分，尤其是 STL 容器，如果所有标准容器的最后一个(可选)模板参数没有指定，那么它将使用这个分配器，并且它是标准库中唯一一个预定义的分配器 vector 中存放的如果是对象类型，则会通过 allocator 在堆上开辟足够的空间来存放和管理集合中的对象 vector 中存放指针类型，一定要记得手动释放内存 存放对象 class Person{ public: Person(int age, int id){ m_age = age; m_id = id; cout << "Person(int, int)..." << endl; } Person(const Person& p){ m_age = p.m_age; m_id = p.m_id; cout << "Person(const Person& p)..." << endl; } ~Person(){ cout << "~Person()..." << endl; } void* operator new(size_t size){ void* p = malloc(size); cout << "new()..." << endl; return p; } void operator delete(void *p){ cout << "delete()....

平时要有容器、算法、迭代器的思维模式 容器提供迭代器，算法使用迭代器 // 算法 int count(int* begin, int* end, int val){ int n = 0; while(begin != end){ if(*begin == val){ n++; } begin++; } return n; } int main() { // 容器 int arr[] = {1, 3, 0, 5, 1, 3, 1, 0}; // 迭代器 int* begin = arr; int* end = *(&arr + 1); int n = count(begin, end, 1); cout << "count: " << n << endl; return 0; }

1、六大组件介绍 容器：数据结构，用来存放数据 算法：常用算法 迭代器：容器和算法之间的胶合剂，“范型指针” 仿函数：一种重载了operator()的类，使得这个类的使用看上去像一个函数 配置器：为容器分配并管理内存 适配器：修改其他组件接口 2、STL 常用的容器有哪些以及各自的特点是什么? 名称 特点 vector 底层数据结构为数组，支持快速随机访问 list 底层数据结构为双向链表，支持快速增删 deque 底层数据结构为一个中央控制器和多个缓冲区，支持首尾（中间不能）快速增删，也支持随机访问 stack 底层一般用deque/list实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时 queue 底层一般用deque/list实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时 priority_queue 底层数据结构一般为vector为底层容器，堆heap为处理规则来管理底层容器实现 set 底层数据结构为红黑树，有序，不重复 multiset 底层数据结构为红黑树，有序，可重复 map 底层数据结构为红黑树，有序，不重复 multimap 底层数据结构为红黑树，有序，可重复 unordered_set 底层数据结构为hash表，无序，不重复 unordered_multiset 底层数据结构为hash表，无序，可重复 unordered_map 底层数据结构为hash表，无序，不重复 unordered_multimap 底层数据结构为hash表，无序，可重复 3、vector 和 list 的区别 vector底层实现是数组，所以在内存中是连续存放的，随机读取效率高，但插入、删除效率低；list底层实现是双向链表，所以在内存中是任意存放的，插入、删除效率高，但访问元素效率低 vector在中间节点进行插入、删除会导致内存拷贝，而list不会 vector一次性分配好内存，不够时才进行2倍扩容；list每次插入新节点都会进行内存申请 4、vector 扩容原理 以原内存空间大小的两倍配置一份新的内存空间，并将原空间数据拷贝过来进行初始化...

vector 常用操作 #include <iostream>#include <vector> int main() { //1.定义和初始化 vector<int> vec1; //默认初始化，vec1为空 vector<int> vec2(vec1); //使用vec1初始化vec2 vector<int> vec3(vec1.begin(),vec1.end());//使用vec1初始化vec2 vector<int> vec4(10); //10个值为0的元素 vector<int> vec5(10,4); //10个值为4的元素 //2.常用操作方法 //2.1 添加函数 vec1.push_back(100); // 尾部添加元素 vec1.insert(vec1.end(),5,3); // 从vec1.back位置插入5个值为3的元素 //2.2 删除函数 vec1.pop_back(); // 删除末尾元素 vec1.erase(vec1.begin(),vec1.begin()+2); // 删除vec1[0]-vec1[2]之间的元素，不包括vec1[2]其他元素前移 vec1.clear(); // 清空元素，元素在内存中并未消失，通常使用swap()来清空 vector<int>().swap(V); // 利用swap函数和临时对象交换内存，交换以后，临时对象消失，释放内存。 // 必须是同类型的 vector // 且只有存储对象时才有效 //2.3 遍历函数 vec1[0]; //取得第一个元素 vec1....

STL六大组件 STL（Standard Template Library），即标准模板库，是一个具有工业强度的，高效的C++程序库。STL中包括六大组件：容器、算法、迭代器、适配器、仿函数、空间配置器 适配器：适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该中模式是将一个类的接口转换成客户希望的另外一个接口。 一、容器 序列式容器（vector、deque、list）、关联式容器（map、set）、容器适配器（stack、queue、priority_queue） 1. vector 是一种动态数组，在内存中具有连续的存储空间，支持快速随机访问。由于具有连续的存储空间，所以在插入和删除操作方面，效率比较慢 2. deque deque 是 double ended queue 的缩写，双向队列不论在尾部或头部插入元素，都十分迅速。而在中间插入元素则会比较费时，因为必须移动中间其他的元素。与 vector 不同，deque 不能保证将所有元素存储在连续的存储空间上 3. list list 是 STL 实现的双向链表，与 vector 相比, 它允许快速的插入和删除，但是随机访问却比较慢 4. map、multimap、unordered_map、unordered_multimap map 是 STL 的一个关联容器，它是一种键值对容器，里面的数据都是成对出现的，且键值是唯一的，可在我们处理一对一数据的时候，在编程上提供快速通道。map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。 multimap 中的元素也是有序的，但允许存在相同键值的 unordered_map 中的元素是唯一的，但无序（也不是插入顺序），而是根据它们的散列值（hash values）组织成桶（buckets），从而允许通过键值直接快速访问单个元素（速度一般比 map 更快） unordered_multimap 无序且不唯一 5. set、multiset、unordered_set、unordered_multiset set 的含义是集合，它是一个有序的容器，里面的元素都是唯一且排序好的，支持插入、删除、查找等操作，就像一个集合一样，所有的操作都是严格在 logn时间内完成，效率非常高，使用方法类似 list multiset 也是排序好的，但是可以存有相同的元素 unordered_set 无序但元素是不可重复的 unordered_multiset 无序，元素也不唯一 二、容器适配器 虽然 stack、queue、priority_queue 中也可以存放元素，但在 STL 中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为每个容器在底层都有自己的实现方式，而 stack、queue、priority_queue 只是在底层将其他容器进行了封装 std::stack template<class T, class Container = deque<T>> class stack; std::queue template<class T, class Container = deque<T>> class queue; std::priority_queue template<class T, class Container = vector<T>, class Compare = less<typename Container::value_type>> class priority_queue; 为什么选择 deque 作为 stack 和 queue 的底层默认容器？...