-
主要学习的是容器适配器和仿函数，以及堆数据结构的回顾以及实践模拟
-
容器适配器类似接口，实际上是一种设计模式，将已有的容器进行封装与改造，大大提高了复用性。
-
仿函数是用起来像函数一样的类的方法，其重载了（），主要是用于简便函数指针的写法。用来代替>、<的比较。
-
堆的具体内容实际上是C数据结构的内容，将在C的堆模拟中提及
-
deque的学习之后会进行
知道了stack，queue，priority_queue是适配器之后，比如说以后要想要知道queue里面的全部元素，可以自己封装好，实现自己想要的功能。（这点还是比较有用的）
- my_stack.h
#pragma once #includenamespace YCB { template > class stack { public: //默认构造函数会调用自定义类型的类的构造函数 stack() { } void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_back(); } T& top() { return _con.back(); } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } //默认析构函数会调用自定义类型的类的析构函数 ~stack() { } private: Container _con; }; void test_stack1() { stack st; st.push(1); st.push(2); st.push(3); st.push(4); cout << st.size() << endl; while (!st.empty()) { cout << st.top() << " "; st.pop(); }cout << endl; cout << st.size() << endl; } };
-my_queue.h
#pragma once #includenamespace YCB { template
> class queue { public: queue() { } void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_front(); } T& front() { return _con.front(); } T& back() { return _con.back(); } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } ~queue() { } private: Container _con; }; void test_queue1() { queue que; que.push("zs"); que.push("tu"); que.push("@"); que.push(".com"); cout << que.size() << endl; cout << que.front() << endl; cout << que.back() << endl; while (!que.empty()) { cout << que.front() << endl; que.pop(); } cout << que.size() << endl;; } };
- my_priority_queue
#pragma once
namespace YCB {
//仿函数默认以less为大堆，greater为小堆
//Node:C++中
template
struct less {
bool operator()(const T& A, const T& B) const {
return A > B;
}
};
template
struct greater {
bool operator()(const T& A, const T& B) const {
return A < B;
}
};
//默认大堆
template,typename Compare=less >
class priority_queue
{
public:
//typedef Container::value_type VT;
//typedef typename Container::value_type VT; 需要指定typename告诉编译器实例化后再去找
//向下调整
void adjust_down(size_t parent) {
Compare cmp;
size_t child = parent * 2 + 1;
size_t n = _con.size();
while (child < n) {
if(child+1 0) {
size_t parent = (child - 1) / 2;
if (!cmp(_con[parent], _con[child])) {
std::swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else break;
}
}
//默认构造函数
priority_queue() {
}
//
template
priority_queue(InputIterator first, InputIterator second) {
while (first != second) {
push(*first);
first++;
}
}
void push(const T& val) {
_con.push_back(val);
adjust_up(_con.size()-1);
}
void pop() {
swap(_con[0], _con[(int)_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
void Print() {
for (int i = 0; i < _con.size(); i++) {
cout << _con[i] << " ";
}cout << endl;
}
T top() const {
return _con.front();
}
size_t size() const {
return _con.size();
}
bool empty() const {
return _con.empty();
}
~priority_queue() {
}
private:
Container _con;
};
void test_priority_queue1() {
priority_queue que;
que.push(3);
que.push(5);
que.push(1);
que.push(8);
que.push(9);
que.push(10);
que.push(4);
que.push(13);
que.Print();
while (!que.empty()) {
cout << que.top() << " ";
que.pop();
}cout << endl;
}
void test_priority_queue2() {
priority_queue, greater >que;
que.push(3);
que.push(5);
que.push(1);
que.push(8);
que.push(9);
que.push(10);
que.push(4);
que.push(13);
que.Print();
while (!que.empty()) {
cout << que.top() << " ";
que.pop();
}cout << endl;
}
void test_priority_queue3() {
vectorv;
v.push_back(3);
v.push_back(5);
v.push_back(1);
v.push_back(8);
v.push_back(9);
v.push_back(10);
v.push_back(4);
v.push_back(13);
priority_queue, greater >que(v.begin(), v.end());
que.Print();
while (!que.empty()) {
cout << que.top() << " ";
que.pop();
}cout << endl;
}
};
