1.基本概念deque是一个双端队列内容保存在堆中支持随即访问和快速插入删除在容器中某一位置上的操作所花费的是线性时间。它的保存形式为堆1 堆2 堆3每个堆保存好几个元素堆和堆之间有指针指向。使用时添加头文件#includedeque。1.1内部原理vector内部采用连续的线性空间空间不足时会重新申请空间。deque容器存储数据的空间是由一段一段等长的连续空间组成各段可能位于内存的不同区域。deque容器使用数组map存储各个连续空间的首地址map中存储的都是指针指向真正的连续存储空间从而实现整体连续的效果。当向deque容器头部或尾部插入元素需要增加存储空间时会申请一段新的连续空间同时在map数组的开头或结尾添加指向该空间的指针将该空间链接到deque容器的头部或尾部。如果map数组满了再申请一块更大的空间供map数组使用将原有数据(指针)拷贝到新的map数组中然后释放旧的空间。deque容器的分段存储结果提高了在序列两端添加或删除元素的效率同时也使得容器的底层实现变得更复杂。1.2底层实现deque迭代器的内部结构如下templateclass T,... struct __deque_iterator{ ... T* cur; T* first; T* last; map_pointer node;//map_pointer 等价于 T** }内部维护了4个指针cur:当前正在遍历的元素first:当前连续空间的首地址last:当前连续空间的末尾地址node:是一个二级指针指向map数组中存储的指向当前连续空间的指针deque容器的底层实现deque容器除了维护map数组还维护start,finish迭代器deque容器的定义如下//_Alloc为内存分配器 templateclass _Ty, class _Alloc allocator_Ty class deque{ ... protected: iterator start; iterator finish; map_pointer map; ... }其中start迭代器记录中map数组中首个连续空间的信息finish迭代器记录着map数组中最后一个连续空间的信息。和普通迭代器不同的是start迭代器中的cur指针指向的是连续空间的首个元素finish迭代器的cur指针指向的连续空间最后一个元素的下一个位置。1.3构造函数dequeT deq;///默认构造 deque(begin,end);///构造函数将[begin,end)之间的元素拷贝给本身 deque(n,val);///构造函数将n个val拷贝给本身 deque(const deque deq);///拷贝构造函数示例如下dequeint deq1; for(int i0;i5;i) deq1.push_back(i); dequeint deq2(deq1.begin(),deq1.end());///值为01234 dequeint deq3(3,50);///50,50,50 dequeint deq4deq2;//值为01234 dequeint deq5{1,2,3,4,5}; dequeint deq6(deq1);二、操作函数1赋值操作对deque容器进行赋值。函数原型为deque operator(const deque deq);///重载等号操作符 assign(deq.begin(),deq.end());///将[begin,end)中的元素拷贝赋值 assign(n,val);//将n个val拷贝赋值示例如下dequeint deq1{1,2,3,4,5}; dequeint deq2deq1;//1,2,3,4,5 dequeint deq3; deq3.assign(deq2.begin(),deq2.end());///12345 dequeint deq4; deq4.assign(5,3);//3,3,3,3,32)插入元素deque可以从两端插入元素。函数原型为push_back(val);//尾部插入 push_front(val);//头部插入 insert(pos,val);//位置pos插入元素val,返回的是新元素的位置 insert(pos,n,val);//位置pos插入n个val,无返回值 insert(pos,begin,end);//位置pos插入[begin,end)之前的元素无返回值示例如下dequeint deq1{1,2,3,4,5}; deq1.push_back(6);//1,2,3,4,5,6 deq1.push_front(0);//0,1,2,3,4,5,6 deq1.insert(deq1.begin()2,0);//0,1,0,2,3,4,5,6 deq1.insert(deq1.begin()4,2,0);//0,1,0,2,0,0,3,4,5,63)删除元素删除同样可以从两端进行删除pop_back();//删除最后一个元素 pop_front();//删除第一个元素 erase(begin,end);//删除[begin,end)之间的元素 erase(pos);//删除指定pos位置的元素 clear();//删除所有的元素示例如下dequeint deq1{1,2,3,4,5,6}; deq1.pop_back();//1,2,3,4,5 deq1.pop_front();//2,3,4,5 deq1.erase(deq1.begin(),deq1.begin()1);///3,4,5 deq1.erase(deq1.begin()2);//3,4 deq1.clear();//删除所有4)获取数据at(int idx);//返回索引idx所指的数据 operator[idx];//返回索引idx所指的数据 front();//返回第一个元素 back();//返回最后一个元素示例如下dequeint deq1{1,2,3,4,5,6}; coutdeq1.at(3)endl;//4 coutdeq1[5]endl;//6 coutdeq1.front()endl;//1 coutdeq1.back()endl;//65容器大小函数原型为empty();//判断是否为空为空返回1否则返回0 size();//容器中元素个数 resize(num);//重新指定容器长度容器变长使用默认值0填充容器变短超过的部分被删除 resize(num,val);//重新指定容器长度容器变长使用值val填充容器变短超过的部分被删除示例如下dequeint deq1{1,2,3,4,5}; coutdeq1.empty()endl;//0 coutdeq1.size()endl;///5 deq1.resize(10);///1,2,3,4,5,0,0,0,0,0 deq1.resize(12,2);///1,2,3,4,5,0,0,0,0,0,2,26)排序使用sort函数示例如下dequeint deq1{1,2,8,0,4,5,6}; sort(deq1.begin(),deq1.end());//0,1,2,4,5,6,8三 优先队列优先队列Priority Queue是一种特殊的队列元素按照优先级出队而非先进先出。通常基于堆Heap实现分为最大堆和最小堆。最大堆与最小堆定义最大堆父节点的值大于或等于子节点的值根节点为最大值。最小堆父节点的值小于或等于子节点的值根节点为最小值。有3 个模板参数T数据类型intContainer底层容器默认是vectorTCompare比较函数默认是lessT→最大堆最大堆时第二个参数可以不写编译器会自动补全如priority_queueint maxHeap; 编译器补全为 priority_queueint, vectorint, lessint maxHeap;3.1 内部原理template class T, class Container vectorT, class Compare lessT class priority_queue;3.2 基本用法基本操作以C的priority_queue为例#include queue #include iostream // 最大堆默认 std::priority_queueint maxHeap; maxHeap.push(3); // 插入元素 maxHeap.push(1); maxHeap.push(4); std::cout maxHeap.top(); // 输出4堆顶最大值 maxHeap.pop(); // 删除堆顶 // 最小堆需显式指定比较函数 std::priority_queueint, std::vectorint, std::greaterint minHeap; minHeap.push(3); minHeap.push(1); std::cout minHeap.top(); // 输出1堆顶最小值遍历std::priority_queueint pq; pq.push(3); pq.push(1); pq.push(2); while (!pq.empty()) { std::cout pq.top() ; // 输出3, 2, 1默认大根堆 pq.pop(); }其他常见操作empty()判断队列是否为空。size()返回队列中元素数量。top()返回堆顶元素但不一出pop()移除堆顶元素3.2 自定义排序规则通过自定义比较函数或重载运算符实现复杂数据类型的优先级规则。方法1重载运算符若需对结构体排序可直接重载运算符默认最大堆需反向逻辑struct Node { int value; // 重载运算符最大堆 bool operator(const Node other) const { return value other.value; // 按value降序 } }; std::priority_queueNode customHeap; customHeap.push({3}); customHeap.push({1}); std::cout customHeap.top().value; // 输出3 //Node具备多个元素 struct Node { int value; int count; bool operator(const Node other) const { return count other.count; // 按value降序 } }; std::priority_queueNode customHeap; customHeap.push({3, 5}); // value3, count5 customHeap.push({1, 8}); // value1, count8 std::cout customHeap.top().value; // 输出1因为count8更大注意bool operator(const Node other) const { return count other.count; // 大根堆 } bool operator(const Node other) const { return count other.count; // 小根堆 }优先队列默认是按照构建大根堆的方式在执行运算时只有atop成立的才会进入堆内。堆顶元素在运算符右边。第一种方式即符合a.counttop.count才进入堆堆顶元素最大是大根堆第二种方式即符合a.counttop.count,才进入堆堆顶元素最小是小根堆。逻辑上整个堆是大根堆但根据count看实际是小根堆。即自定义Node时优先队列逻辑上使用按照构建大根堆的方式执行但由于重载了操作符可能导致实际构建的堆是小根堆。优先队列里只使用了操作符不使用操作符。方法2自定义比较函数使用函数对象或Lambda表达式需指定容器和比较类型auto cmp [](const Node a, const Node b) { return a.value b.value; // 最小堆规则 }; std::priority_queueNode, std::vectorNode, decltype(cmp) customHeap(cmp); customHeap.push({3}); customHeap.push({1}); std::cout customHeap.top().value; // 输出1注意事项比较函数需满足严格弱序如或。最小堆需显式传递std::greater或自定义比较逻辑。
C ++ deque及2优先队列
1.基本概念deque是一个双端队列内容保存在堆中支持随即访问和快速插入删除在容器中某一位置上的操作所花费的是线性时间。它的保存形式为堆1 堆2 堆3每个堆保存好几个元素堆和堆之间有指针指向。使用时添加头文件#includedeque。1.1内部原理vector内部采用连续的线性空间空间不足时会重新申请空间。deque容器存储数据的空间是由一段一段等长的连续空间组成各段可能位于内存的不同区域。deque容器使用数组map存储各个连续空间的首地址map中存储的都是指针指向真正的连续存储空间从而实现整体连续的效果。当向deque容器头部或尾部插入元素需要增加存储空间时会申请一段新的连续空间同时在map数组的开头或结尾添加指向该空间的指针将该空间链接到deque容器的头部或尾部。如果map数组满了再申请一块更大的空间供map数组使用将原有数据(指针)拷贝到新的map数组中然后释放旧的空间。deque容器的分段存储结果提高了在序列两端添加或删除元素的效率同时也使得容器的底层实现变得更复杂。1.2底层实现deque迭代器的内部结构如下templateclass T,... struct __deque_iterator{ ... T* cur; T* first; T* last; map_pointer node;//map_pointer 等价于 T** }内部维护了4个指针cur:当前正在遍历的元素first:当前连续空间的首地址last:当前连续空间的末尾地址node:是一个二级指针指向map数组中存储的指向当前连续空间的指针deque容器的底层实现deque容器除了维护map数组还维护start,finish迭代器deque容器的定义如下//_Alloc为内存分配器 templateclass _Ty, class _Alloc allocator_Ty class deque{ ... protected: iterator start; iterator finish; map_pointer map; ... }其中start迭代器记录中map数组中首个连续空间的信息finish迭代器记录着map数组中最后一个连续空间的信息。和普通迭代器不同的是start迭代器中的cur指针指向的是连续空间的首个元素finish迭代器的cur指针指向的连续空间最后一个元素的下一个位置。1.3构造函数dequeT deq;///默认构造 deque(begin,end);///构造函数将[begin,end)之间的元素拷贝给本身 deque(n,val);///构造函数将n个val拷贝给本身 deque(const deque deq);///拷贝构造函数示例如下dequeint deq1; for(int i0;i5;i) deq1.push_back(i); dequeint deq2(deq1.begin(),deq1.end());///值为01234 dequeint deq3(3,50);///50,50,50 dequeint deq4deq2;//值为01234 dequeint deq5{1,2,3,4,5}; dequeint deq6(deq1);二、操作函数1赋值操作对deque容器进行赋值。函数原型为deque operator(const deque deq);///重载等号操作符 assign(deq.begin(),deq.end());///将[begin,end)中的元素拷贝赋值 assign(n,val);//将n个val拷贝赋值示例如下dequeint deq1{1,2,3,4,5}; dequeint deq2deq1;//1,2,3,4,5 dequeint deq3; deq3.assign(deq2.begin(),deq2.end());///12345 dequeint deq4; deq4.assign(5,3);//3,3,3,3,32)插入元素deque可以从两端插入元素。函数原型为push_back(val);//尾部插入 push_front(val);//头部插入 insert(pos,val);//位置pos插入元素val,返回的是新元素的位置 insert(pos,n,val);//位置pos插入n个val,无返回值 insert(pos,begin,end);//位置pos插入[begin,end)之前的元素无返回值示例如下dequeint deq1{1,2,3,4,5}; deq1.push_back(6);//1,2,3,4,5,6 deq1.push_front(0);//0,1,2,3,4,5,6 deq1.insert(deq1.begin()2,0);//0,1,0,2,3,4,5,6 deq1.insert(deq1.begin()4,2,0);//0,1,0,2,0,0,3,4,5,63)删除元素删除同样可以从两端进行删除pop_back();//删除最后一个元素 pop_front();//删除第一个元素 erase(begin,end);//删除[begin,end)之间的元素 erase(pos);//删除指定pos位置的元素 clear();//删除所有的元素示例如下dequeint deq1{1,2,3,4,5,6}; deq1.pop_back();//1,2,3,4,5 deq1.pop_front();//2,3,4,5 deq1.erase(deq1.begin(),deq1.begin()1);///3,4,5 deq1.erase(deq1.begin()2);//3,4 deq1.clear();//删除所有4)获取数据at(int idx);//返回索引idx所指的数据 operator[idx];//返回索引idx所指的数据 front();//返回第一个元素 back();//返回最后一个元素示例如下dequeint deq1{1,2,3,4,5,6}; coutdeq1.at(3)endl;//4 coutdeq1[5]endl;//6 coutdeq1.front()endl;//1 coutdeq1.back()endl;//65容器大小函数原型为empty();//判断是否为空为空返回1否则返回0 size();//容器中元素个数 resize(num);//重新指定容器长度容器变长使用默认值0填充容器变短超过的部分被删除 resize(num,val);//重新指定容器长度容器变长使用值val填充容器变短超过的部分被删除示例如下dequeint deq1{1,2,3,4,5}; coutdeq1.empty()endl;//0 coutdeq1.size()endl;///5 deq1.resize(10);///1,2,3,4,5,0,0,0,0,0 deq1.resize(12,2);///1,2,3,4,5,0,0,0,0,0,2,26)排序使用sort函数示例如下dequeint deq1{1,2,8,0,4,5,6}; sort(deq1.begin(),deq1.end());//0,1,2,4,5,6,8三 优先队列优先队列Priority Queue是一种特殊的队列元素按照优先级出队而非先进先出。通常基于堆Heap实现分为最大堆和最小堆。最大堆与最小堆定义最大堆父节点的值大于或等于子节点的值根节点为最大值。最小堆父节点的值小于或等于子节点的值根节点为最小值。有3 个模板参数T数据类型intContainer底层容器默认是vectorTCompare比较函数默认是lessT→最大堆最大堆时第二个参数可以不写编译器会自动补全如priority_queueint maxHeap; 编译器补全为 priority_queueint, vectorint, lessint maxHeap;3.1 内部原理template class T, class Container vectorT, class Compare lessT class priority_queue;3.2 基本用法基本操作以C的priority_queue为例#include queue #include iostream // 最大堆默认 std::priority_queueint maxHeap; maxHeap.push(3); // 插入元素 maxHeap.push(1); maxHeap.push(4); std::cout maxHeap.top(); // 输出4堆顶最大值 maxHeap.pop(); // 删除堆顶 // 最小堆需显式指定比较函数 std::priority_queueint, std::vectorint, std::greaterint minHeap; minHeap.push(3); minHeap.push(1); std::cout minHeap.top(); // 输出1堆顶最小值遍历std::priority_queueint pq; pq.push(3); pq.push(1); pq.push(2); while (!pq.empty()) { std::cout pq.top() ; // 输出3, 2, 1默认大根堆 pq.pop(); }其他常见操作empty()判断队列是否为空。size()返回队列中元素数量。top()返回堆顶元素但不一出pop()移除堆顶元素3.2 自定义排序规则通过自定义比较函数或重载运算符实现复杂数据类型的优先级规则。方法1重载运算符若需对结构体排序可直接重载运算符默认最大堆需反向逻辑struct Node { int value; // 重载运算符最大堆 bool operator(const Node other) const { return value other.value; // 按value降序 } }; std::priority_queueNode customHeap; customHeap.push({3}); customHeap.push({1}); std::cout customHeap.top().value; // 输出3 //Node具备多个元素 struct Node { int value; int count; bool operator(const Node other) const { return count other.count; // 按value降序 } }; std::priority_queueNode customHeap; customHeap.push({3, 5}); // value3, count5 customHeap.push({1, 8}); // value1, count8 std::cout customHeap.top().value; // 输出1因为count8更大注意bool operator(const Node other) const { return count other.count; // 大根堆 } bool operator(const Node other) const { return count other.count; // 小根堆 }优先队列默认是按照构建大根堆的方式在执行运算时只有atop成立的才会进入堆内。堆顶元素在运算符右边。第一种方式即符合a.counttop.count才进入堆堆顶元素最大是大根堆第二种方式即符合a.counttop.count,才进入堆堆顶元素最小是小根堆。逻辑上整个堆是大根堆但根据count看实际是小根堆。即自定义Node时优先队列逻辑上使用按照构建大根堆的方式执行但由于重载了操作符可能导致实际构建的堆是小根堆。优先队列里只使用了操作符不使用操作符。方法2自定义比较函数使用函数对象或Lambda表达式需指定容器和比较类型auto cmp [](const Node a, const Node b) { return a.value b.value; // 最小堆规则 }; std::priority_queueNode, std::vectorNode, decltype(cmp) customHeap(cmp); customHeap.push({3}); customHeap.push({1}); std::cout customHeap.top().value; // 输出1注意事项比较函数需满足严格弱序如或。最小堆需显式传递std::greater或自定义比较逻辑。
