目录
一,容器适配器
deque双端队列
二,stack栈
stack接口
stack模拟实现
三,queue队列
queue接口
queue模拟实现
四,priority_queue优先级队列
priority_queue接口
priority_queue模拟实现
注:Date*,无法转化为const Date* &;
一,容器适配器
- 适配器是一种设计模式,该模式是将一个类的接口转换成用户希望的另一个接口;
- 虽然stack、queue中可以存元素,但在STL中并没有划为容器行列,而是将其称为容器适配器;这是因为他们只是对其他的接口进行了包装,STL中stack、queue默认的底层容器为deque;
- 是一种双开口的“连续”空间的数据结构;
- 双开口,即头尾两端都可高效插入和删除 *** 作,时间复杂度为O(1);
- “连续”空间,其实并非真正的连续空间,而是由一段段连续的小空间拼接而成,类似于一个动态的二维数组;
- 与vector比较,头插效率高,无需挪动数据;vector的cpu高速缓存命中率高,但增容代价大且存在空间浪费;
- 与list比较,空间利用率较高;list按需申请或释放空间,任意插入删除效率高,不支持随机访问,cpu高速缓存命中率低;
优缺点
- 非常适合头插/尾插,头删/尾删,默认适合做stack/queue适配器;
- 中间插入/删除数据非常麻烦,效率不高;
- 不适合遍历,遍历时迭代器要频繁的检测是否到达边界;
- deque可以说是一种折中的方案,随机访问不及vector,任意位置插入删除不及list;
注:
- stack是一种LIFO的特殊线性数据结构,只要满足尾插尾删 *** 作均可作为其底层容器,如vector、list;
- queue是一种FIFO的特性线性数据结构,只要满足尾插头删 *** 作均可作为底层容器,如list;
- stack、queue默认选择deque作为其底层容器,是因为stack、queue没有迭代器无需遍历,只要在一端或两端 *** 作即可,stack增容时deque比vector效率高不需要大量挪动数据,queue元素增长时,不仅效率高,且内存使用率也高;
int main() { dequedq; dq.push_back(1); dq.push_back(2); dq.push_front(3); dq.push_front(4); cout << dq[0] << endl; cout << dq.front() << endl; cout << dq.back()<< endl; dq.pop_back(); dq.pop_front(); deque ::iterator it = dq.begin(); while (it != dq.end()) { cout << *it << " "; ++it; } return 0; }
二,stack栈
- stack是一种容器适配器,专门用在具有后进先出 *** 作的上下文环境中,只能从容器的一端进行元素的插入与提取 *** 作;
- stack是作为容器的适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定类作为其底层,元素在特定容器尾部即栈顶被压入和d出;
- 底层容器可以是任何标准的容器类模板或其他特定的容器类,这些容器类应支持,empty、back、push_back、pop_back *** 作;
- 标准容器vector、deque、list均符号要求,如stack未指定特定的底层容器,默认使用deque;
- stack(),构造空栈;
- empty(),判断释放为空栈;
- size(),返回元素个数;
- top(),返回栈顶元素个数;
- push(),压入元素;
- pop(),d出元素;
int main() { stackstack模拟实现st; st.push(1); st.push(2); st.top(); st.pop(); st.size(); st.empty(); return 0; }
template> class stack { public: void push(const T& val) { _con.push_back(val); } void pop() { _con.pop_back(); } const T& top() { return _con.back(); } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } private: container _con; }; int main() { stack > st; st.push(1); st.push(2); st.push(3); st.push(4); while (!st.empty()) { cout << st.top() << " "; st.pop(); } return 0; }
三,queue队列
- queue是一种容器适配器,专门用于在先进先出中 *** 作,其中从容器一端插入元素,另一端提取元素;
- 队列作为容器适配器实现,容器适配器即将特定容器封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素,元素从队尾入队列,从对头出队列;
- 底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器类,该底层容器应至少支持,empty、size、front、back、push_back、pop_front *** 作;
- 标准容器类deque和list默认要求,如queue没有实例化指定容器类,默认使用deque;
- queue(),构造空队列;
- empty(),判断释放为空栈;
- size(),返回有效元素个数;
- front(),返回对头元素引用;
- back(),返回队尾元素引用;
- push(),在队尾将元素入队列;
- pop(),将对头元素出队列;
int main() { queuequeue模拟实现q; q.push(1); q.push(2); q.front(); q.back(); q.pop(); q.size(); q.empty(); return 0; }
template> class queue { public: void push(const T& val) { _con.push_back(val); } void pop() { _con.pop_front(); } const T& front() { return _con.front(); } const T& back() { return _con.back(); } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } private: container _con; }; int main() { queue > st; st.push(1); st.push(2); st.push(3); st.push(4); while (!st.empty()) { cout << st.front() << " "; st.pop(); } return 0; }
四,priority_queue优先级队列
- 优先级队列,默认使用vector作为底层容器;
- vector上使用堆算法,将元素构造成堆结构;
- 优先级队列其实是堆,默认为大堆;
- priority_queue(),构造空优先级队列;
- priority_queue(InputIterator first,InputIterator last),用指定范围构造优先级队列;
- push,插入元素;
- pop,删除堆顶元素;
- top,返回堆顶元素;
- size,返回有效元素个数;
- empty,检测是否为空;
int main() { vectorpriority_queue模拟实现v = { 1,2,3,4 }; priority_queue pq(v.begin(), v.end()); pq.push(3); pq.push(5); while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } return 0; }
template, class compare = less > class priority_queue { public: priority_queue() {} template priority_queue(InputIterator first, InputIterator last) { while (first != last) { push(*first); ++first; } } void push(const T& val) { _con.push_back(val); AdjustUp(_con.size() - 1); } void pop() { std::swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0); } const T& top()const { return _con.front(); } size_t size()const { return _con.size(); } bool empty()const { return _con.empty(); } void AdjustDown(size_t parent) { size_t child = parent * 2 + 1; while (child < _con.size()) { if (child + 1 < _con.size() && compare()(_con[child], _con[child + 1])) child++; if (compare()(_con[parent], _con[child])) { std::swap(_con[parent], _con[child]); parent = child; child = parent * 2 + 1; } else break; } } void AdjustUp(size_t child) { size_t parent = (child - 1) / 2; while (child > 0) { if (compare()(_con[parent], _con[child])) { std::swap(_con[parent], _con[child]); child = parent; parent = (child - 1) / 2; } else break; } } private: container _con; }; template class less { public: bool operator()(const T& x, const T& y) { return x < y; } }; template class greater { public: bool operator()(const T& x, const T& y) { return x > y; } };
注,嵌套依赖名字需添加关键字typename
templatevoid print(const container& con) { //无法确定container::iterator是类型,还是静态成员变量 //需在前添加typename typename container::const_iterator it = con.begin(); while (it != con.end()) { cout << *it << " "; ++it; } }
附,自定义compare仿函数,控制比较结果;
class Date { friend ostream& operator<<(ostream& _cout, const Date& d); public: Date(int year = 1900, int month = 1, int day = 1) : _year(year) , _month(month) , _day(day) {} bool operator<(const Date& date) const { return (_year < date._year) || (_year == date._year && _month < date._month) || (_year == date._year && _month == date._month && _day < date._day); } bool operator>(const Date& date) const { return (_year > date._year) || (_year == date._year && _month > date._month) || (_year == date._year && _month == date._month && _day > date._day); } private: int _year; int _month; int _day; }; ostream& operator<<(ostream& _cout, const Date& date) { _cout << date._year << "-" << date._month << "-" << date._day << endl; return _cout; } //自定义compare仿函数,控制比较结果 class pDateLess { public: bool operator()(const Date* pdate1, const Date* pdate2) { return *pdate1 < *pdate2; } }; int main() { priority_queue注:Date*,无法转化为const Date* &;, pDateLess> pq; pq.push(new Date(2000, 1, 1)); pq.push(new Date(2001, 1, 1)); pq.push(new Date(2002, 1, 1)); while (!pq.empty()) { cout << *pq.top(); pq.pop(); } return 0; }
//const Date*&,是对类型const Date*的引用 //但实际传递的类型为Date*,无法转化为const Date* & bool operator()(const Date*& pdate1, const Date*& pdate2) { return *pdate1 < *pdate2; } //说明 int a = 1; int* pa = &a; const int*& pb = pa; //报错int*无法转换为const int*& //const引用非const对象 //首先int*会隐形转化为const int*, 需借助临时变量,临时变量具有常性
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)