1. The use of stack
Second, the simulation implementation of stack
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<vector>
#include<list>
//adapter pattern
namespace sk
{
template <class T, class Container = deque<T>>
class stack
{
public:
bool empty()const
{
return _con.empty();
}
size_t size()const
{
return _con.size();
}
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_back();
}
const T& top()const
{
return _con.back();
}
private:
Container _con;
};
void stack_test()
{
stack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << endl;
}
}
Three, the use of queue
Fourth, the simulation implementation of queue
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<vector>
#include<list>
namespace sk
{
template <class T, class Container = deque<T>>
class queue
{
public:
bool empty()const
{
return _con.empty();
}
size_t size()const
{
return _con.size();
}
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_front();
}
const T& front()const
{
return _con.front();
}
const T& back()const
{
return _con.back();
}
private:
Container _con;
};
void queue_test()
{
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
}
}
Five, the use of priority_queue
| function declaration | Interface Description |
|---|---|
| priority_queue()/priority_queue(first,last) | Construct an empty priority queue |
| empty( ) | Check whether the priority queue is empty, return true, otherwise return false |
| top( ) | Returns the largest (smallest element) in the priority queue, that is, the top element of the heap |
| push(x) | Insert element x into the priority queue |
| pop() | Delete the largest (smallest) element in the priority queue, that is, the top element of the heap |
[Notice]
- By default, priority_queue is a large heap.
Sample code:
#include <vector>
#include <queue>
#include <functional> // header file for greater algorithm
void TestPriorityQueue()
{
// By default, a large heap is created, and its bottom layer is compared according to the less than sign
vector<int> v{3,2,7,6,0,4,1,9,8,5};
priority_queue<int> q1;
for (auto& e : v)
q1.push(e);
cout << q1.top() << endl;
// If you want to create a small heap, replace the third template parameter with a greater comparison method
priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
cout << q2.top() << endl;
}
- If you put custom type data in priority_queue, users need to provide > or < overload in the custom type.
Sample code:
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;
};
void TestPriorityQueue()
{
// A large pile, requiring the user to provide an overload of < in the custom type
priority_queue<Date> q1;
q1.push(Date(2018, 10, 29));
q1.push(Date(2018, 10, 28));
q1.push(Date(2018, 10, 30));
cout << q1.top() << endl;
// If you want to create a small heap, you need to provide an overload of >
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;
}
Six, the simulation implementation of priority_queue
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;
namespace sk
{
//functor
template <class T>
struct lesser
{
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template <class T>
struct greater
{
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
//specialization
template <>
struct lesser<char>
{
bool operator()(const char& x, const char& y)
{
return x > y;
}
};
template<class T, class Container = vector<T>, class Compare = lesser<T>>
class priority_queue
{
Compare com;
void adjust_up(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (com(_con[parent] , _con[child]))
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2 ;
}
else
{
break;
}
}
}
void adjust_down(size_t parent)
{
size_t child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))
{
child++;
}
if (com(_con[parent] , _con[child]))
{
swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
public:
priority_queue()
{}
template<class Inputiterator>
priority_queue(Inputiterator first, Inputiterator last)
:_con(first, last)
{
//build pile
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
{
adjust_down(i);
}
}
void push(const T& val)
{
_con.push_back(val);
size_t child = _con.size() - 1;
adjust_up(child);
}
void pop()
{
assert(!empty());
swap(_con.front(), _con.back());
_con.pop_back();
adjust_down(0);
}
const T& top()const
{
return _con.front();
}
bool empty()const
{
return _con.empty();
}
size_t size()const
{
return _con.size();
}
private:
Container _con;
};
void priority_queue_test1()
{
//priority_queue<int, vector<int>, greater<int>> pq;//Small heap
std::vector<int> v = { 8,1,5,9,7,4,1,3,5,48,65,6,4,5 };
priority_queue<int> pq(v.begin(), v.end());//default large heap
pq.push(1);
pq.push(3);
pq.push(4);
pq.push(5);
pq.push(2);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
void priority_queue_test2()
{
//priority_queue<int, vector<int>, greater<int>> pq;//Small heap
std::vector<char> v = { 'a','f','d','v' };
priority_queue<char> pq(v.begin(), v.end());//default large heap
pq.push('q');
pq.push('w');
pq.push('e');
pq.push('r');
pq.push('t');
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
}
7. Container Adapter
7.1 What is an adapter
Adapter is a design pattern (a design pattern is a set of repeated use, known to most people, classified and cataloged, and a summary of code design experience), which converts the interface of a class into another that customers want. interface.
7.2 The underlying structure of stack and queue in the STL standard library
Although elements can also be stored in stack and queue, they are not divided into the ranks of containers in STL, but are called container adapters, because stacks and queues only wrap the interfaces of other containers, STL In stack and queue, deque is used by default, for example:
7.3 A brief introduction to deque
7.3.1 Introduction to the principle of deque
Deque (double-ended queue): It is a double-opened "continuous" space data structure. The meaning of double-opening is: insertion and deletion can be performed at both ends of the head and tail, and the time complexity is O(1). Compared with vector, the plug-in efficiency is high, and there is no need to move elements; compared with list, the space utilization rate is relatively high.
Deque is not a real continuous space, but is spliced by segments of continuous small spaces. The actual deque is similar to a dynamic two-dimensional array.
The bottom layer of the double-ended queue is an illusion of continuous space, which is actually segmented and continuous. In order to maintain its "overall continuity" and the illusion of random access, it falls on the iterator of the deque. Therefore, the iterator design of deque is more complicated.
7.3.2 The defect of deque
Compared with vector, the advantage of deque is that when the head is inserted and deleted, there is no need to move elements, and the efficiency is particularly high, and when expanding, there is no need to move a large number of elements, so its efficiency must be high.
Compared with list, its bottom layer is a continuous space, the space utilization rate is relatively high, and no additional fields need to be stored.
However, deque has a fatal flaw: it is not suitable for traversal, because when traversing, the iterator of deque needs to frequently check whether it has moved to the boundary of a small space, resulting in low efficiency. In sequential scenarios, it may be necessary to frequently Traversal, so in practice, when a linear structure is required, vector and list are given priority in most cases. There are not many applications of deque, and one application that can be seen so far is that STL uses it as the underlying data structure of stack and queue .
7.4 Why choose deque as the underlying default container of stack and queue
Stack is a special last-in-first-out linear data structure, so as long as it has a linear structure with push_back() and pop_back() operations, it can be used as the underlying container of the stack, such as vector and list; queue is a special first-in first-out A linear data structure, as long as it has a linear structure with push_back and pop_front operations, can be used as the underlying container of the queue, such as list. But in STL for stack and
queue chooses deque as its underlying container by default, mainly because:
- Stack and queue do not need to be traversed (so stack and queue have no iterators), and only need to operate at one or both ends of the fixed.
- When the elements in the stack grow, deque is more efficient than vector (no need to move a lot of data when expanding); when the elements in the queue grow, deque is not only efficient, but also has high memory usage.
Combining the advantages of deque, it perfectly avoids its defects.