ftp里找到的index文件查看网站建设中,wordpress上传图片插件,自己怎么创建微信小程序,网站建设费分多少期摊销文章目录 一.stack二.queue三.deque#xff08;双端队列#xff09;四.优先级队列优先级队列中的仿函数手搓优先级队列 五.反向迭代器手搓反向迭代器 vector和list我们称为容器#xff0c;而stack和queue却被称为容器适配器。 这和它们第二个模板参数有关系#xff0c;可以… 文章目录 一.stack二.queue三.deque双端队列四.优先级队列优先级队列中的仿函数手搓优先级队列 五.反向迭代器手搓反向迭代器 vector和list我们称为容器而stack和queue却被称为容器适配器。 这和它们第二个模板参数有关系可以看到stack和queue的第二个模板参数的缺省值都是deque即双端队列容器。也就是说栈和队列都是以容器为主材料构建的而且因为第二个参数是一个缺省值我们不但可以使用deque构建同样可以使用vector和list来构建。 用已经存在的容器来封装转换成不存在的容器这种方式就被称之为适配器模式。
有了deque提供的接口再要实现栈和队列就会变得很简单。
一.stack
栈的特点就是后进先出插入和删除都是在尾部进行栈不提供迭代器因为栈只能访问栈顶的元素。
#includedeque
namespace wbm
{template class T, class Container dequeTclass stack{public:bool empty()const{return _con.empty();}void push(const Tx){_con.push_back(x);}void pop(){_con.pop_back();}size_t size()const{return _con.size();}const T top()const{return _con.back();}private:Container _con;};}栈不但可以通过deque来封装还可以通过vector和list来封装只要支持尾插尾删即可 二.queue
队列的特点是先进先出队尾入队头出可以访问队头和队尾的数据也不提供迭代器
#includedequenamespace wbm
{templateclass T,class ContainerdequeTclass queue{public:bool empty()const{return _con.empty();}void push(const T x){_con.push_back();}void pop(){_con.pop_front();}size_t size()const{return _con.size();}const T fornt()const{return _con.front();}const T back()const{return _con.back();}private:Container _con;};
}只要是支持尾插头删的容器都可以做queue的适配器但是不建议使用数组因为数组的头删效率太低 三.deque双端队列
因为vector和list都各有优缺点因此大佬们就想是否可以创造一个容器兼具vector和list的优点又避免缺点于是便有了双端队列deque虽然deque的名字带着队列但是它和队列毫无关系。 观察它提供的接口发现它既支持随机访问又支持头插头删和尾插尾删看起来似乎确实是一个完美的容器。但如果真的那么完美vector和list岂不是早就被淘汰了。
其实deque的底层是一个指针数组多个buffer数组buffer数组的大小是固定的的组成形式这个指针数组是一个中控数组其中存放的元素是属于这个deque的buffer数组的地址。
第一次插入数据开辟的buffer数组的地址存放在中控数组的中间元素如果buffer数组满了要继续尾插则继续开辟新的buffer数组此时第二个buffer数组的地址存放在中控数组中间元素的下一个。如果你要头插则开辟一个新的buffer数组并将这个buffer数组的地址存放在中间元素的前一个。 deque的优点 1.扩容代价小于vector它只有在中控满了以后才需要扩容并且不需要拷贝原生数据只要将中控数组与buffer之间的映射关系拷贝下来即可。 2.因为是一段一段的空间所以CPU高速缓存命中率高于list。 3.头尾插入删除效率都较高并且支持随机访问 但是deque也有自己的缺点: 1.随机访问效率不如vector它的随机访问要通过计算得到假设每个buffer数组的大小为size你要访问第10个元素首先要10/size来确定这个元素在哪一个buffer数组中再用10%size来确定这个元素在这个buffer数组中的哪个位置所以deque也不适合排序因为排序需要大量的随机访问。 2.中间插入删除不如list它在中间插入删删同样需要挪动一定量的数据 3.迭代器实现复杂它的迭代器中有四个指针当curlast时说明本段空间被使用完毕node继续去访问下一段空间并更新first和last 四.优先级队列 优先级队列的特点就是优先级高的先出它也是一个容器适配器不提供迭代器底层是一个堆并且默认是大堆。
priority_queueint //小堆
priority_queueint,vectorint,greaterint //大堆优先级队列中的仿函数
仿函数是一个函数对象它是一个类函数的对象要达到类函数所以这个类中必须要重载()。优先级队列中默认是大堆如果我们要改成小堆除了要显示传递第三个参数以外还要更改比较大小的算法。在C语言中为了能让qsort排序任意类型库中使用了函数指针的办法让使用者显示的去写一个比较函数并将该函数的地址作为参数传递过去。仿函数的一个应用场景就类似于函数指针。
namespace wbm
{templateclass Tstruct less //可以使用struct也可以使用class它们都是类只是默认的访问限定不同{bool operator()(const T x, const T y){return x y;}};template class Tstruct greater{bool operator()(const T x, const T y){return x y;}};
}
int main()
{wbm::lessint func;//两者等价func(1, 2)func.operator()(1, 2);return 0;
}手搓优先级队列
#includevector
#includeiostream
namespace wbm
{templateclass Tstruct less //可以使用struct也可以使用class它们都是类只是默认的访问限定不同{bool operator()(const T x, const T y){return x y;}};template class Tstruct greater{bool operator()(const T x, const T y){return x y;}};templateclass T, class Container std:: vectorT,class Compare lessTclass priority_queue{private:void Adjustdown(size_t parent){Compare com;//构造一个仿函数对象size_t child parent * 2 1;//先默认是左孩子大如果右孩子更大把孩子节点更新成右孩子while (child _con.size()){if (child1 _con.size() com(_con[child], _con[child 1])){child;//默认是less也就是左孩子比右孩子小}//将孩子节点和父节点做比较if (com(_con[parent], _con[child])) {std::swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else{break;}}}void Adjustup(size_t child){Compare com;size_t parent (child - 1) / 2;while (child 0){if (com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;}}}public:priority_queue(){//要有一个默认构造不写就会报错}//迭代器区间构造,直接构造出一个堆使用向下调整更佳templateclass InputIteratorpriority_queue(InputIterator first, InputIterator last):_con(first, last) //初始化列表vector支持迭代器区间构造{//初始化建堆使用向下调整从第一个非叶子节点开始for (int i (_con.size() - 1 - 1) / 2; i 0; i--){Adjustdown(i);}}void push(const T x){_con.push_back(x);Adjustup(_con.size() - 1);}void pop(){//将首元素和末尾元素换位置删除后调整std::swap(_con.front(), _con.back());_con.pop_back();Adjustdown(0);}bool empty()const{return _con.empty();}size_t size()const{return _con.size();}const T top()const{return _con.front();}private:Container _con;};
}如果优先级队列中存放的是某个类的地址又需要我们比较地址中值的优先级那就需要使用仿函数来进行特殊处理。否则只会按照地址来比较。
五.反向迭代器
反向迭代器采用的是适配器模式是通过正向迭代器的再封装实现的你给它某个容器的正向迭代器它就产生这个容器的反向迭代器它与正向迭代器的位置是对称的并且正好相反。所以要控制反向迭代器只需要使用运算符重载篡改方向迭代器中和--的规则就可以。
reverse_iterator rbegin(){return reverse_iterator(end());}
reverse_iterator rend(){return reverse_iterator(begin());}rbegin和end一样指向的是最后一个元素的下一个位置要想访问到3要先--再访问这个问题可以通过重载*来解决
templateclass Iterator,class Ref,class Ptr
Ref operator*()
{Iterator tmpit;return *(--tmp);
}手搓反向迭代器
namespace wbm
{//反向迭代器使用正向迭代器封装templateclass Iterator,class Ref,class Ptr //迭代器,T/const T,T*/const T*class ReverseIterator{typedef ReverseIteratorIterator, Ref, Ptr Self;public:ReverseIterator(Iterator it):_it(it){}Ref operator*(){Iterator tmp;return *(--tmp);}Ptr operator-(){return (operator*())}Self operator(){--_it;return *this;}Self operator--(){_it;return *this;}bool operator!(const Ref rit)const//两个迭代器之间的比较{return _it ! rit;}private:Iterator _it;//这里给的参数是一个正向迭代器};
}
