【STL】容器适配器 - stackqueuepriority_queue模拟实现
目录
一.适配的核心思想
二.stack&queue&priority_queue用什么容器适配最为合适
三.stack模拟实现
1.框架
2.实现
四.queue模拟实现
1.框架
2.实现
五.容器deque(了解)
0.deque的概念
1.deque底层内存布局以及如何支持O(1)的头尾插删
2.如何支持迭代器达到随机访问的目的
3.deque的优缺点对比
六.仿函数
七.priority_queue模拟实现
1.框架
2.实现
一.适配的核心思想
适配的核心思想 - 复用
对比之前模拟实现list时, 所学习到的迭代器适配器是同一个道理
list模拟实现(包含反向迭代器, 迭代器适配器)详解入口: http://t.csdn.cn/k3REu
对于迭代器适配器而言, reverse_iterator复用了iterator
那么, 对于容器适配器而言, 不难理解, stack&queue&priority_queue也是以这种方式, 适配(复用)其他容器
深刻理解: 这也是一种封装思想, 本质是对于其他容器的一种封装
二.stack&queue&priority_queue用什么容器适配最为合适
stack&queue&priority_queue由于特性原因, 都不能支持iterator
那么在stl中, stack和queue, 默认适配deque
对于stack而言, 需要遵循先进后出原则, 执行的操作有尾插尾删
最好使用deque
支持O(1)时间复杂度的尾插尾删, 缓存利用率相对较高, 扩容代价较小, 结合了vector与list的优点于一身
可以使用vector
缺点: 扩容代价较大
优点: 支持O(1)时间复杂度的尾插尾删, 且缓存利用率较高, 内存布局非常紧凑
使用list
缺点: 内存碎片化程度较高, 缓存利用率低
优点: 带头双向循环链表与数组的尾插尾删效率相差不大
对于queue而言, 需要遵循先进先出原则, 执行的操作有头删尾插
最好使用deque
支持O(1)时间复杂度的尾插头删, 缓存利用率相对较高, 扩容代价较小, 结合了vector与list的优点于一身
可以使用list
O(1)时间复杂度的尾插头删
使用vector(一般不用)
缺点: 就是头删要挪动n-1的数据, 效率低
deque: 双端队列, 支持随机存取, 内存碎片化较低, 且O(1)时间复杂度的头删/头插/尾删/尾插, 具体在后面deque部分讲解
priority_queue, 默认适配vector
对于priority_queue而言, 底层其实是堆, 所以必须使用连续的空间, 所以使用vector
priority_queue是一种特殊的队列, 只要是队列就要遵循先进先出(FIFO)(first in first out)规则
那么有人会问priority_queue使用vector适配, 出数据需要出队头的数据, 那vector要删除第一个元素, 后面的元素就都要向前挪动一个位置, 效率岂不是很低? 解答: 效率不低, priority_queue一次pop的时间复杂度是O(logN), 这正因为虽然使用到了vector适配, 不代表他就是vector的原装操作, priority_queue底层是堆结构, 每次pop会交换首尾, 出掉尾, 然后对整体执行一次向下调整算法(这一次的向下调整, 时间复杂度就是O(logN)
三.stack模拟实现
1.框架
默认使用deque容器适配
template<class T, class Container = deque<T>>
class stack
{
public:
bool empty() const;
size_t size() const;
void push(const T& val);
void pop();
T& top();
const T& top()const;
private:
Container con;
};2.实现
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();
}
T& top()
{
return con.back();
}
const T& top()const
{
return con.back();
}
private:
Container con;
};
四.queue模拟实现
1.框架
默认使用deque容器适配
template<class T, class Container = deque<T>>
class queue
{
public:
bool empty() const;
size_t size() const;
void push(const T& val);
void pop();
T& front();
const T& front() const;
T& back();
const T& back() const;
private:
Container con;
};
2.实现
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)
{
return con.push_back(val);
}
void pop()
{
return con.pop_front();
}
T& front()
{
return con.front();
}
const T& front() const
{
return con.front();
}
T& back()
{
return con.back();
}
const T& back() const
{
return con.back();
}
private:
Container con;
};
五.容器deque(了解)
0.deque的概念
deque - 双端队列
实际底层空间是不连续的, 将每个数组以链表的形式链接起来
但实际上并不是队列, 支持迭代器, 支持随机存取, 支持O(1)时间复杂度的头插/头删/尾插/尾删, 常用来适配stack&queue
1.deque底层内存布局以及如何支持O(1)的头尾插删
2.如何支持迭代器达到随机访问的目的
deque迭代器的运作方式: 每次迭代时, cur如果不等于last就向后++, 如果cur等于last, node向后+1, 然后cur继续从first开始
3.deque的优缺点对比
deque集合了vector与list的优点:
缓存利用率较高, 内存碎片较少, 内存空间布局相比于list较为紧凑, 支持O(1)头尾插删, 支持iterator随机存取
deque仍有缺点:
iterator与list对比, list没有迭代器; 与vector对比, vector的迭代器效率要比deque高(因为在大量使用情况下, 不需要大量计算)
与list和vector相比, 迭代器设计复杂, 可读性差
中间插入删除的效率较低, 仍然需要挪动大量数据
总结: 外强中干, 确实结合了vector与list的优点于一身, 但是并不能在某一项上突出, 仍有一些欠缺
stack&queue的实现选择了deque来适配主要原因:
stack&queue不需要支持iterator, 不需要中间插入删除, 需要O(1)时间的头尾插删, deque缓存利用率较高, 内存碎片较少, 刚好对于deque而言, 用到了优点而又避开了缺点
六.仿函数
仿函数本质就是一个类, 本质上代替了C语言的回调函数
C语言的回调函数, 需要自己实现一个函数, 然后以函数指针的方式传参, 去其他函数中调用这个函数
在视觉上, 看似是一个普通函数调用, 实际是类对象对成员函数的调用
核心: 重载operator()
//仿函数less
template<class T>
class less
{
public:
bool operator()(const T& leftVal, const T& rightVal) const;
};
//仿函数great
template<class T>
class greater
{
public:
bool operator()(const T& leftVal, const T& rightVal) const;
};
//使用
int main()
{
int a = 10;
int b = 20;
less<int> comp;
//看似像一个普通函数调用, 实则是类对象调用自己的成员函数
bool flag = comp(a, b);//本质: comp.operator()(a, b)
return 0;
}
七.priority_queue模拟实现
1.框架
默认使用vector容器适配, 同时使用到了仿函数, 类模板偏特化技术
为何使用vector适配, 而并不是deque?
由于deque的性质我们可以了解到, deque底层数据存储并不是连续的, 而priority_queue(优先级队列)的底层实际是一个堆状结构, 默认使用vector数组适配
想要将优先级队列完全理解, 需要对 数据结构 - 堆 有深刻认识, 可以参考我之前写的一篇博客
数据结构 - 堆详解入口: http://t.csdn.cn/x7G7z
以及如果有对模板偏特化了解较少的情况, 可以参考我之前写的一篇博客
C++模板进阶详解入口: http://t.csdn.cn/xIyZl
//仿函数less
template<class T>
class less
{
public:
bool operator()(const T& leftVal, const T& rightVal) const;
};
//模板特化
template<class T>
class less<T*>
{
public:
bool operator()(const T* val1, const T* val2);
};
//仿函数great
template<class T>
class greater
{
public:
bool operator()(const T& leftVal, const T& rightVal) const;
};
//模板特化
template<class T>
class greater<T*>
{
bool operator()(const T* leftVal, const T* rightVal) const;
};
//priority_queue类
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
public:
bool empty() const;
size_t size() const
T& top();
const T& top() const;
void adjustDown(size_t parent);//向下调整算法
void adjustUp(size_t child);//向上调整算法
//构造函数
priority_queue();
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last);
void push(const T& val);
void pop();
private:
Container _con;
Compare _comp;
};2.实现
//仿函数less
template<class T>
class less
{
public:
bool operator()(const T& leftVal, const T& rightVal) const
{
return leftVal < rightVal;
}
};
//模板特化
template<class T>
class less<T*>
{
public:
bool operator()(const T* val1, const T* val2)
{
return *val1 < *val2;
}
};
//仿函数great
template<class T>
class greater
{
public:
bool operator()(const T& leftVal, const T& rightVal) const
{
return leftVal > rightVal;
}
};
//模板特化
template<class T>
class greater<T*>
{
bool operator()(const T* leftVal, const T* rightVal) const
{
return *leftVal > *rightVal;
}
};
//priority_queue类
template<class T, class Container = deque<T>, class Compare = less<T>>
class priority_queue
{
public:
bool empty() const
{
return _con.empty();
}
size_t size() const
{
return _con.size();
}
T& top()
{
return _con.front();
}
const T& top() const
{
return _con.front();
}
void adjustDown(size_t parent)
{
size_t child = parent * 2 + 1;//左孩子
while (child < _con.size())
{
//假设Compare = less
//_con[child] < _con[child + 1], 选出大的, 建大堆, 出来top是由大到小
if (child + 1 < _con.size() && _comp(_con[child], _con[child + 1]))
{
child++;
}
if (_comp(_con[parent], _con[child]))
{
::swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void adjustUp(size_t child)
{
if (child == 0)
return;
size_t parent = (child - 1) / 2;
while (parent >= 0)
{
if (_comp(_con[parent], _con[child]))
{
::swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//构造函数
priority_queue()
{
;
}
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
//思路1: 全部push后采用向下调整建堆(时间复杂度O(N))
//思路2: 一边push一边向上调整(时间复杂度O(N*logN))
//采取思路1
//全部push
while (first != last)
{
_con.push_back(*first);
first++;
}
//向下调整
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
{
adjustDown(i);
}
}
void push(const T& val)
{
//插入一个
_con.push_back(val);
//向上调整一次(O(N))
adjustUp(_con.size() - 1);
}
void pop()
{
//交换
::swap(_con[0], _con[_con.size() - 1]);
//出队
_con.pop_back();
//向下调整一次
adjustDown(0);
}
private:
Container _con;
Compare _comp;
};在cplusplus官方文档中, 对于priority_queue构造函数的传参是传入的匿名对象
匿名对象的特性就是, 在本行就会调用析构函数, 进行释放
但在这里是没有问题的, 因为将匿名对象赋值给了一个const修饰的引用, 这个const就为这个匿名对象提供常性, 延长了匿名对象的生命周期
那我们在传参的时候, 是否要依据官方文档这样的形式去传一个Compare()呢?
答案是: 这样其实是绕远路了, 我们在实例化模板类的时候, 例如priority_queue<int, vector<int>, less<int>>, 这个less<int>类型已经传给了模板参数Compare, 之后我们不需要传入Compare(), _comp会去调用仿函数less的默认构造即可, 因为这个仿函数对象真正的价值就是去调用operator()而已!对象本身的属性并没有实际价值
那么如果像官方文档这样的传参, 我们想要传入一个Compare(), 参考他给的案例, 我们什么时候需要这样传参呢? 当我们要自己实现一个仿函数的时候(不使用官方给的less与greater), 这时我们就需要传入一个Compare对象, 例如Compare(), 通过Compare()来调用我们自己写的仿函数的默认构造
总结: 我们在实际使用priority_queue时, 很少关心对于priority_queue构造函数是否要传入一个匿名对象, 通常都是以这种形式来创建对象
priority_queue<int> pq; --or-- priority_queue<int> pq(iterator, iterator), 自己去写一个仿函数, 在传入这个仿函数的匿名对象, 这是很少见的!!
应用:
priority_queue在实际中常用来解决topK等类似问题
例如: 找出一组数种的第K大的数, 使用priority_queue解决的时间复杂度通常是O(N)
注意:
stl标准库中的定义, 如果传入less类型, 则是建大堆, 最终遍历出来的结果是由大->小的
如果传入greater类型, 则是建小堆, 最终遍历出来的结果是由小->大的