目录
一,容器适配器
deque双端队列
二,stack栈
stack接口
stack模拟实现
三,queue队列
queue接口
queue模拟实现
四,priority_queue优先级队列
priority_queue接口
priority_queue模拟实现
注:Date*,无法转化为const Date* &;
一,容器适配器
优缺点
注:
int main() { deque<int> dq; 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<int>::iterator it = dq.begin(); while (it != dq.end()) { cout << *it << " "; ++it; } return 0; }
二,stack栈
int main() { stack<int> st; st.push(1); st.push(2); st.top(); st.pop(); st.size(); st.empty(); return 0; }
template <class T, class container = deque<T>> 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<int, list<int>> st; st.push(1); st.push(2); st.push(3); st.push(4); while (!st.empty()) { cout << st.top() << " "; st.pop(); } return 0; }
三,queue队列
int main() { queue<int> q; q.push(1); q.push(2); q.front(); q.back(); q.pop(); q.size(); q.empty(); return 0; }
template <class T, class container = deque<T>> 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<int, list<int>> 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优先级队列
int main() { vector<int> v = { 1,2,3,4 }; priority_queue<int> pq(v.begin(), v.end()); pq.push(3); pq.push(5); while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } return 0; }
template<class T, class container = vector<T>, class compare = less<T>> class priority_queue { public: priority_queue() {} template<class InputIterator> 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 T> class less { public: bool operator()(const T& x, const T& y) { return x < y; } }; template<class T> class greater { public: bool operator()(const T& x, const T& y) { return x > y; } };
注,嵌套依赖名字需添加关键字typename
template<class container> void 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*, vector<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; }