list(二)和_stack_queue

嗨喽大家好，时隔许久阿鑫又给大家带来了新的博客，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;};
}

给出的对创建存储自定义类型的vector和存储自定义类型指针的vector的解释

编译器通过类型信息来确保您不会将非 Date* 类型的指针错误地插入到 a 中。如果您尝试将一个不是 Date* 类型的指针插入到a 中，编译器会发出一个错误，告诉您类型不匹配。所以当我们创建存储Date*类型的vector时，不需要调用Date的构造函数，只有在创建Date对象的时候，我们才需要调用Date的构造函数。

并且上述程序我们需要注意：程序结束时，只有局部对象（如a数组本身和任何在栈上分配的局部变量）的生命周期会结束，但由new在堆上分配的对象不会自动被销毁。你需要手动管理这些对象的生命周期。

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;
}

好啦，今天的内容我们就学习到这里，如果大家觉得阿鑫写的不错的话，记得留下你的一键三连哦，期待我们的下一次相遇！