目录
4.1.2:back 和 front 和 size 与 empty
1:容器适配器
stack 和 queue 有一点需要注意，虽然 stack 和 queue 也可以存放元素，但在 STL 中并没有将其划分在容器的行列，而是将其称为容器适配器，STL 中stack 和 queue默认使用deque。在 stack 和 queue 的类模版声明中我们可以看到，它们的模版参数有两个，第一个是 stack 和 queue 当中所存储的元素类型，而另一个则是指定使用的容器类型，只不过当我们不指定使用何种容器的情况下，stack 和 queue 默认使用 deque 作为容器。
2:stack 的模拟实现
2.1:stack.h
#include <iostream>
using namespace std;
#include <deque>
namespace MyStack {
template<class T, class Container = deque<T> >
class stack {
public:
void push(const T& x);
void pop();
//自定义类型传值返回时会调用拷贝构造，所以传引用
T& top();
const T& top()const;
size_t size()const;
bool empty();
private:
Container _Container;
};
};
2.1.1:push 和 pop
栈的特点是后进先出，那么对于 push 我们可以调用容器适配器的 push_back，由于是后进先出，那么 pop 调用的则是 pop_back。
void push(const T& x) {
//尾插
_Container.push_back(x);
}
void pop() {
_Container.pop_back();
}
2.1.2:top 和 size 以及 empty
栈的 top 指的是栈顶元素，那么对应的则应该是容器适配器的 back() 函数，由于会存在 const 对象调用 top 函数，那么因此我们要对其进行函数重载。size 和 empty 直接调用容器适配器的 size() 和 empty 函数即可。
const T& top()const { return _Container.back(); }
size_t size()const { return _Container.size(); }
bool empty() { return _Container.empty(); }
T& top() { return _Container.back(); }
2.2:Test.cpp
#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"
#include <vector>
int main() {
MyStack::stack<int,vector<int>> st1;
st1.push(1);
st1.push(2);
st1.push(3);
st1.push(4);
st1.push(5);
cout << "size:> " << st1.size() << endl;
while (!st1.empty()) {
cout << st1.top() << " ";
st1.pop();
}
return 0;
}
3:queue 的模拟实现
3.1:Queue.h
#include <iostream>
using namespace std;
#include <deque>
namespace MyQueue {
template<class T, class Container = deque<T>>
class queue {
public:
//尾插
void push(const T& value);
//头删
void pop();
//获取队尾元素
T& back();
T& back() const;
//获取队头元素
T& front();
T& front() const;
size_t size()const;
bool empty() const;
private:
Container _Container;
};
};
3.1.1:push 和 pop
队列的特点是先进先出，那么对于 push 我们可以调用容器适配器的 push_back，由于是先进先出，那么 pop 调用的则是 pop_front。
//尾插
void push(const T& value) {
_Container.push_back(value);
}
//头删
void pop() {
_Container.pop_front();
}
3.1.2:back 和 front 和 size 与 empty
队列的 back 指的是队尾元素，那么对应的则应该是容器适配器的 back() 函数，由于会存在 const 对象调用 back 函数，那么因此我们要对其进行函数重载。队列的 front 指的是队头元素，那么对应的则应该是容器适配器的 front() 函数，同理 back 函数我们也要对其进行函数重载。size 和 empty 直接调用容器适配器的 size() 和 empty 函数即可。
T& back() { return _Container.back(); }
T& back() const { return _Container.back(); }
T& front() { return _Container.front(); }
T& front() const { return _Container.front(); }
size_t size()const { return _Container.size(); }
bool empty() const { return _Container.empty(); }
3.2:Test.cpp
#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"
#include <list>
int main() {
MyQueue::queue<int, list<int>> q1;
q1.push(1);
q1.push(2);
q1.push(3);
q1.push(4);
q1.push(5);
while (!q1.empty()) {
cout << q1.front() << "::" << q1.back() << endl;
q1.pop();
}
return 0;
}
4:priority_queue 的模拟实现
4.1:priority_queue.h
#pragma once
#include <iostream>
using namespace std;
#include <assert.h>
#include <vector>
#include <algorithm>
namespace MyPriorityQueue {
template <class T,class Container = vector<T>,class Compare = less<T>>
class priority_queue {
public:
void Adjust_Up(int child);
void Adjust_Down(int parent);
void push(const T& val);
void pop();
bool empty() const;
size_t size() const;
T& top();
private:
Container _Container;
};
}
4.1.1:向上调整算法
- 将目标节点与其父节点进行比较。
- 若目标节点的值比父节点大，则进行交换，并且同时将原目标节点的父亲节点当作新的目标节点进行向上调整，若目标结点的值比其父结点的值小，则停止向上调整，此时该树已经是大堆了。
void Adjust_Up(int child) {
//找到目标节点的父亲节点
int parent = (child - 1) / 2;
while(child > 0) {
//孩子比父亲大，进行交换
if(_Container[child] > _Container[parent]) {
swap(_Container[child],_Container[parent]);
//更新孩子和父亲，继续进行向上调整
child = parent;
parent = (child - 1) / 2;
} else {
break;
}
}
}
4.1.2:向下调整算法
使用向下调整算法有一个前提：若想将其调整为小堆，那么根结点的左右子树必须都为小堆。若想将其调整为大堆，那么根结点的左右子树必须都为大堆。
- 从根节点开始，选出左右孩子中的最大值。
- 让最大的孩子与父亲进行比较。
- 若孩子比父亲大，则让该孩子的与其父亲的位置进行交换。并将原来大的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止
- 若大的孩子比父亲小，则不需处理了，调整完成，整个树已经是大堆了。
void Adjust_Down(int parent) {
//假设左孩子最大
int child = parent * 2 + 1;
while (child < size()) {
if(child + 1 < size() && _Container[child + 1] > _Container[child]) {
child++;
}
//孩子比父亲大，进行交换
if (_Container[child] > _Container[parent]) {
swap(_Container[child], _Container[parent]);
//更新孩子和父亲，继续进行向下调整
parent = child;
child = parent * 2 + 1;
} else {
break;
}
}
}
4.1.3:push 和 pop
对于 push，直接尾插，然后进行向上调整算法即可。对于 pop，删除的是堆顶的元素，但是这个删除过程可并不是直接删除堆顶的数据，而是先将堆顶的数据与最后一个结点的位置交换，然后再删除最后一个结点，再对堆进行一次向下调整。若是直接删除堆顶的数据，那么原堆后面数据的父子关系就全部打乱了，需要全体重新建堆，时间复杂度为 O(N)。若是用上述方法，那么只需要对堆进行一次向下调整即可，因为此时根结点的左右子树都是小堆，我们只需要在根结点处进行一次向下调整即可，时间复杂度为 O(log(N))。
void push(const T& val) {
//尾插
_Container.push_back(val);
//向上调整
Adjust_Up(size() - 1);
}
void pop() {
//交换堆顶和堆底
swap(_Container[0], _Container[size() - 1]);
//尾删
_Container.pop_back();
//向下调整
Adjust_Down(0);
}
4.1.4:empty 与 size 与 top
bool empty() const { return _Container.empty(); }
size_t size() const { return _Container.size(); }
T& top() { return _Container[0]; }
4.2:Test.cpp
#include "Priority_queue.h"
int main() {
MyPriorityQueue::priority_queue<int> pq;
pq.push(70);
pq.push(56);
pq.push(30);
pq.push(15);
pq.push(25);
pq.push(10);
pq.push(90);
pq.push(100);
while(!pq.empty()) {
cout << pq.top() << " " << "size:>" << pq.size() << endl;
pq.pop();
}
return 0;
}
5:反向迭代器
反向迭代器与正向迭代器的区别主要在遍历的方向上：正向迭代器是从容器的第一个元素开始向后遍历的，反向迭代器是从容器的最后一个元素开始向前遍历的。因此我们可以通过对正向迭代器的封装来生成反向迭代器----迭代器适配器。
反向迭代器在实现的时候与正向迭代器是一种镜像对称的关系。
使用正向迭代器适配反向迭代器的时候会认为它两存在对称关系，那么此时就会导致两个问题 rbegin 第一次解引用是一个随机值。rbegin == rend 就结束了。
那么就导致了第一个元素没有取到，那么我们该如何解决这个对称的坑呢通过解引用来解决这个坑，解引用时，我们并不是解引用当前位置，而是解引用它的前一个位置！
反向迭代器的++是正向迭代器的--，反向迭代器的--就是正向迭代器的++。
5.1:代码实现
#define _CRT_SECURE_NO_WARNINGS
namespace MyReverseIterator {
template<class Iterator,class Reference,class Pointer>
class ReverseIterator {
typedef ReverseIterator<Iterator, Reference, Pointer> Self;
ReverseIterator(Iterator it) :_it(it) { };
Self& operator++() { --_it; return *this; }
Self& operator--() { ++_it; return *this; }
Reference operator*() {
/*
* 正向迭代器与反向迭代器成一个镜像对称的关系，所以反向迭代器解引用时的元素不是解引用当前位置
* 而是解引用它的前一个位置
* 因为解引用是不能够影响当前迭代器的，所以需要创建一个临时变量
*/
Iterator temp = _it;
--temp;
return *temp;
}
Pointer operator->() { return &(operator*()); }
bool operator!=(const Self& rit) { return _it != rit._it; }
bool operator==(const Self& rit) { return _it == rit._it; }
private:
Iterator _it;
};
}
5.2:反向迭代器的应用
我们用 list 的正向迭代器生成 list 的反向迭代器为例。
5.2.1:ReverseIterator.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
namespace MyReverseIterator {
template<class Iterator, class Reference, class Pointer>
struct ReverseIterator {
typedef ReverseIterator<Iterator, Reference, Pointer> Self;
Iterator _it;
ReverseIterator(Iterator it) :_it(it) { };
Self& operator++() { --_it; return *this; }
Self& operator--() { ++_it; return *this; }
Reference operator*() {
/*
* 正向迭代器与反向迭代器成一个镜像对称的关系，所以反向迭代器解引用时的元素不是解引用当前位置
* 而是解引用它的前一个位置
* 因为解引用是不能够影响当前迭代器的，所以需要创建一个临时变量
*/
Iterator temp = _it;
--temp;
return *temp;
}
Pointer operator->() { return &(operator*()); }
bool operator!=(const Self& rit) { return _it != rit._it; }
bool operator==(const Self& rit) { return _it == rit._it; }
};
};
5.2.2:List.h
#pragma once
#include <iostream>
using namespace std;
#include <assert.h>
#include <string>
#include "ReverseIterator.h"
namespace MyList {
//节点类的定义
template <class T>
struct ListNode {
ListNode* Previous;
ListNode* Next;
T Val;
//构造函数
ListNode(const T& val = T()) :Previous(nullptr), Next(nullptr), Val(val) { }
};
//迭代器类的定义
template <class T, class Reference, class Pointer>
struct ListIterator {
typedef ListNode<T> Node;
typedef ListIterator<T, Reference, Pointer> Self;
//构造函数
ListIterator(Node* node) :_Node(node) { };
Node* _Node;
//前置++
Self& operator++() { _Node = _Node->Next; return *this; }
//后置++
Self operator++(int) {
//拷贝一个临时变量
Self temp = *this;
_Node = _Node->Next;
return temp;
}
//前置--
Self& operator--() { _Node = _Node->Previous; return *this; }
//后置--
Self operator--(int) {
//拷贝一个临时变量
Self temp = *this;
_Node = _Node->Previous;
return temp;
}
Reference operator*() { return _Node->Val; }
Pointer operator->() { return &_Node->Val; }
bool operator!=(const Self& it) {
//通过比较节点地址来判断迭代器是否相等
return _Node != it._Node;
}
bool operator==(const Self& it) { return _Node == it._Node; }
};
template <class T>
class List {
typedef ListNode<T> Node;
public:
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
typedef MyReverseIterator::ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef MyReverseIterator::ReverseIterator<iterator, const T&, const T*> const_reverse_iterator;
public:
void Empty_Init() {
//创建哨兵位的头节点
_Head = new Node();
_Head->Next = _Head;
_Head->Previous = _Head;
_Size = 0;
}
List() { Empty_Init(); }
//拷贝构造函数
//lt2(lt1); lt1 不变，lt2 和 lt1 内容相同
List(const List<T>& lt) { Empty_Init(); for (auto& element : lt) { push_back(element); } }
reverse_iterator rbegin() { return reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
iterator begin() {
//返回第一个有效节点
return iterator(_Head->Next);
}
iterator end() {
//返回哨兵位节点
return iterator(_Head);
}
const_iterator begin() const {
//返回第一个有效节点
return _Head->Next;
}
const_iterator end() const {
//返回哨兵位节点
return _Head;
}
void push_back(const T& Val) {
insert(end(), Val);
}
void pop_back() { erase(--end()); }
void push_front(const T& Val) { insert(begin(), Val); }
void pop_front() { erase(begin()); }
void insert(iterator Position, const T& Val) {
//构建新节点
Node* NewNode = new Node(Val);
//找到 Position 位置的节点
Node* Current = Position._Node;
//找到 Position 位置节点的前驱节点
Node* Prev = Current->Previous;
//当前节点的前驱指向 NewNode
Prev->Next = NewNode;
//NewNode 的前驱指向 Prev
NewNode->Previous = Prev;
//NewNode 的后驱指向 Current
NewNode->Next = Current;
//Current 的前驱指向 NewNode
Current->Previous = NewNode;
_Size++;
}
iterator erase(iterator Position) {
//找到 Position 位置的节点
Node* Current = Position._Node;
//找到 Position 位置节点的前驱节点
Node* Prev = Current->Previous;
//找到 Position 位置节点的后继节点
Node* Next = Current->Next;
//当前节点的前驱节点的后继指向当前节点后继节点
Prev->Next = Next;
//当前节点的后继节点的前驱指向当前节点前驱节点
Next->Previous = Prev;
//释放当前节点
delete Current;
_Size--;
return iterator(Next);
}
size_t size() { return _Size; }
bool empty() { return _Size == 0; }
void clear() {
iterator it = begin();
while (it != end()) { it = erase(it); }
}
void swap(List<T>& lt) { std::swap(_Head, lt._Head); std::swap(_Size, lt._Size); }
List<T>& operator=(List<T> lt) { swap(lt); return *this; }
~List() { clear(); delete _Head; _Head = nullptr; }
private:
Node* _Head;
size_t _Size;
};
}
5.2.3:Test.cpp
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include "List.h"
void TestList12() {
MyList::List<int> lt;
lt.push_back(10);
lt.push_back(20);
lt.push_back(30);
lt.push_back(40);
lt.push_back(50);
MyList::List<int>::reverse_iterator rit = lt.rbegin();
while (rit != lt.rend()) {
cout << *rit << " ";
++rit;
}
cout << endl;
}
void TestList13() {
MyList::List<int> lt;
lt.push_back(10);
lt.push_back(20);
lt.push_back(30);
lt.push_back(40);
lt.push_back(50);
MyList::List<int>::reverse_iterator rit = lt.rbegin();
while (rit != lt.rend()) {
cout << *rit << " ";
++rit;
}
cout << endl;
}
int main() {
TestList12();
cout << endl;
TestList13();
return 0;
}
