stack与queue
这两个就是之前数据结构学过的栈和队列，只不过多了几个接口。
stack：
queue：
这两个容器没有迭代器，这是因为怕我们更改导致顺序错误。
#include<iostream> #include<stack> #include<queue> int main() { stack<int> a; a.push(1); a.push(2); a.push(3); a.push(4); a.push(5); queue<int> b; b.push(6); b.push(7); b.push(8); b.push(9); b.push(0); while (!a.empty()) { cout << a.top() << ' '; a.pop(); } cout << endl; while (!b.empty()) { cout << b.front() << ' '; b.pop(); } return 0; }
priority_queue
这个容器是优先级队列，看起来是队列，其实内部结构并不是队列，而是一个堆。
#include<iostream> #include<queue> int main() { priority_queue<int> a;//大堆 priority_queue<int, vector<int>, greater<int>> b;//小堆 a.push(3); a.push(0); a.push(9); a.push(5); a.push(6); while (!a.empty()) { cout << a.top() << ' '; a.pop(); } cout << endl; b.push(3); b.push(0); b.push(9); b.push(5); b.push(6); while (!b.empty()) { cout << b.top() << ' '; b.pop(); } return 0; }
容器适配器
什么是适配器呢？生活中我们用的充电器就是，一个充电器可以给好几种手机使用。
适配器是一种设计模式：该种模式是将一个类的接口转换成客户希望的另外一个接口。
vector与list的反向迭代器模拟实现
实现的目的主要是要求无论是list还是vector都可以用这个反向迭代器。
反向迭代器其实是迭代器位置变了而已，反向迭代器的begin与正向的end，反向迭代器的end与正向的begin指向同一个位置。
namespace baiye { template<class Iterator, class Ref, class Ptr> struct Reverse_iterator { typedef Reverse_iterator<class Iterator, class Ref, class Ptr> self; Reverse_iterator(Iterator it) :_it(it) {} Ref operator*()//区别是否有const { Iterator tmp = _it; return *(--tmp);//因为begin是指向正向迭代器end的原因，所以需要-- } self operator++() { _it--; return *this; } self operator--() { _it++; return *this; } bool operator!=(const Iterator it)const { return it != _it; } Ref operator->() { return &(operator*()); } Iterator _it;//反向迭代器的本质 }; }
仿函数
#include<iostream> using namespace std; namespace baiye { template<class T> struct greater_than { bool operator()(const T& a, const T& b) { return a > b; } }; template<class T> struct less_than { bool operator()(const T& a, const T& b) { return a < b; } }; } int main() { int a = 4; int b = 0; int c = 5; baiye::greater_than<int> compare; baiye::less_than<int> contrast; int sum = compare(a, b); cout << sum << endl; sum = compare(a, c); cout << sum << endl; sum = contrast(a, b); cout << sum << endl; sum = contrast(a, c); cout << sum << endl; return 0; }
仿函数其实是一个类，在函数回调他用起来比函数地址好用，如果在某一段代码需要用到函数回调，这个函数的参数特别多，写出来之后会破坏代码看起来的美感。
deque(了解)
这是一个双端队列。他是vector与list的结合体，但是又没有vector与list在某一方面好用。
链接：https://legacy.cplusplus.com/reference/deque/deque/?kw=deque
大概的结构是这样的：
图片出自侯捷老师的《STL源码剖析》。
在开辟一个deque类的时候会有一个指针数组，里面的指针指向了模板的类型，
cur是指向数组当前访问的位置，first是指向第一个位置，last指向末尾，node不是和他们三个一个层次的，而是指向指针数组的指针。
在如果一个fairse指向的空间满了，头插就会在node指向元素的下一个位置开辟空间，在第一个位置进行插入，如果想头插就会在node指向的前一个元素进行空间开辟，然后再末尾的位置进行数据写入。
cur是用来遍历node指向的内容的，他是用来实现++，- -的。
stack与queue模拟实现
stack
namespace baiye { template<class T, class Con = deque<T>>//这里也可以用list或者vector class stack { public: stack() {} void push(const T& x) { _c.push_back(x); } void pop() { _c.pop_back(); } T& top() { return _c.back(); } const T& top()const { return _c.back(); } size_t size()const { return _c.size(); } bool empty()const { return _c.empty(); } private: Con _c; }; }
queue
namespace baiye { template<class T, class Con = deque<T>> class queue { public: queue() {} void push(const T& x) { _c.push_back(x); } void pop() { _c.pop_front(); } T& back() { return _c.back(); } const T& back()const { return _c.back(); } T& front() { return _c.front(); } const T& front()const { return _c.front(); } size_t size()const { return _c.size(); } bool empty()const { return _c.empty(); } private: Con _c; }; }
priority_queue模拟实现
priority_queue
#include<iostream> #include<stack> #include<queue> #include<deque> #include<list> #include<vector> #include<algorithm> using namespace std; namespace baiye { template<class T> struct less { bool operator()(const T& a, const T& b) { return a < b; } }; template <class T, class Container = vector<T>, class Compare = less<T> > class priority_queue { public: void adjust_up(size_t child)//向上调整 { Compare com;//仿函数 while (child > 0) { if(com(c[(child - 1) / 2], c[child])) { swap(c[child], c[(child - 1) / 2]); child = (child - 1) / 2; } else { break; } } } void adjust_down(size_t parent)//向下调整 { size_t left = parent * 2 + 1;//左孩子 Compare com;//仿函数 while (left < c.size()) { if (left + 1 < c.size() && com(c[left], c[left + 1])) { left++; } if (com(c[parent], c[left])) { swap(c[left], c[parent]); parent = left; left = parent * 2 + 1; } else { break; } } } priority_queue() {} template <class InputIterator> priority_queue(InputIterator first, InputIterator last) :c(first,last) { for (int i = (c.size() - 2) / 2; i >= 0; i--)//建堆 { adjust_down(i); } } bool empty() const { return c.empty(); } size_t size() const { return c.size(); } const T& top() const { return c[0]; } void push(const T& x) { c.push_back(x); adjust_up(c.size()-1); } void pop() { swap(c[0], c[c.size() - 1]); c.pop_back(); adjust_down(0); } private: Container c; }; }
