嗨喽大家好，时隔许久阿鑫又给大家带来了新的博客，list的模拟实现（二）以及_stack_queue，下面让我们开始今天的学习吧！
list(二)和_stack_queue
1.list的构造函数
2.设计模式之适配器和迭代器
3.新容器deque
4.优先级队列
5.仿函数
1.list的构造函数
最好加上引用，如果不加引用，T为list时，将it解引用赋值给e时，list为自定义类型要耗费大量空间进行拷贝操作，所以在利用for语句时，我们最好加上引用
//list的默认构造，构造出一个头节点
void empty_init()
{//利用节点的默认构造，生成一个节点//定义该节点为头节点，节点对象拥有两个成员变量_head = new Node();_head->_next = _head;_head->_prev = _head;
}list(initializer_list <T> il)
{//initializer_list常量数组中有两个指针，分别指向数组的开头和结尾empty_init();for (const auto& e : il){push_back(e);}
}list()
{//看一下交换的时候，是不是新创建的对象是调用默认构造进行初始化empty_init();
}list(const list<T>& it)
{empty_init();for (const auto& e :it){push_back(e);}
}~list()
{clear();delete _head;_head = nullptr;
}void clear()
{auto it = begin();while (it != end()){it = erase(it);}
}
//it1(it3)
list<T>& operator=(list<T> it)
{std::swap(_head, it._head);return *this;
}
2.设计模式之适配器和迭代器
using namespace std;
namespace ZJ
{template<class T, class Container = vector<T>>class Stack{public:void push(const T& x){_con.push_back(x);}void pop(){//后进先出_con.pop_back();}const T& top(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private :Container _con;};void Test_stack1(){ZJ::Stack<int> st1;st1.push(1);st1.push(2);st1.push(3);st1.push(4);st1.push(5);int n = st1.size();for (int i = 0; i < n; i++){cout << st1.top() << " ";st1.pop();}cout << endl;}}
3.新容器deque
deque的每个对象有四个成员变量，每个迭代器中又有四个指针
cur指向当前数据，node(是一个二级指针)指向当前数据在中控数组中的位置，first和last分别指向buff数组中第一个和最后一个数据,而finish中的node指针指向最后一个buff的最后一个数据的下一个位置
4.优先级队列
底层是一个堆
void Test_priority_queue1()
{vector<int> v1 = { 1,2,3,8,9,7,5,6,4 };priority_queue<int> q1(v1.begin(), v1.end());//for (const auto& e : v1)//{// q1.push(e);////}while (!q1.empty()){cout << q1.top() << " ";q1.pop();}}堆逻辑上是一个二叉树，物理结构上是一个数组
没有引入仿函数时。
namespace ZJ
{template<class T, class Container = vector<T>>class priority_queue{public:template <class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);++first;}// 从最后一个非叶子节点开始向下建堆for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){adjust_down(i);}}void adjust_up(int child){size_t parent = (child - 1) / 2;while (child > 0){if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(int parent){size_t child = parent * 2 + 1;while (child<_con.size()){if (child + 1 < _con.size() && _con[child] < _con[child + 1]){child = child + 1;}if (_con[child] > _con[parent]){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}
5.1仿函数初识
class Func
{
public:void operator()(int a = 10){while (a--){cout << "Func调用" << endl;}}
};
有了仿函数之后的优先级队列
namespace ZJ
{template<class T>class myless{public:bool operator() (const T& x, const T& y){return x < y;}};template<class T>class mygreater{public:bool operator() (const T& x, const T& y){return x > y;}};template<class T, class Container = vector<T>,class compare = myless<T>>class priority_queue{public:template <class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);++first;}// 从最后一个非叶子节点开始向下建堆for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){adjust_down(i);}}void adjust_up(int child){compare comfunc;size_t parent = (child - 1) / 2;while (child > 0){if (comfunc(_con[parent],_con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(int parent){compare comfunc;size_t child = parent * 2 + 1;while (child<_con.size()){if (child + 1 < _con.size() && comfunc(_con[child] , _con[child + 1])){child = child + 1;}if (comfunc(_con[parent],_con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}
5.2仿函数用法之自定义类型比较大小
priority_queue() = default;//生成默认的构造函数
class Date
{
public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}friend ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}
private:int _year;int _month;int _day;
};
struct PDateLess
{bool operator() (Date* p1, Date* p2){return *p1 < *p2;}
};
struct PDateMore
{//小堆bool operator() (Date* p1, Date* p2){return *p1 > *p2;}
};
void TestPriorityQueue()
{// 大堆，需要用户在自定义类型中提供<的重载ZJ::priority_queue<Date*,vector<Date*>,PDateMore> q1;q1.push(new Date(2018, 10, 29));q1.push(new Date(2018, 10, 28));q1.push(new Date(2018, 10, 30));while(!q1.empty()){cout << *q1.top() << endl;q1.pop();} 如果要创建小堆，需要用户提供>的重载//priority_queue<Date, vector<Date>, greater<Date>> q2;//q2.push(Date(2018, 10, 29));//q2.push(Date(2018, 10, 28));//q2.push(Date(2018, 10, 30));//cout << q2.top() << endl;
}
int main()
{TestPriorityQueue();return 0;
}
