目录
容器适配器模式
容器适配器模式是结构设计模式的一种,看看STL的栈和队列:
1.发现它们第二个模版参数都是class Container = deque<T>,使用了缺省参数
2.新名词:container adaptor(容器适配器)
Stacks are a type of container adaptor.
Queues are a type of container adaptor.
栈和队列是容器适配器的一种,它们是通过其他容器转换而来的,也可以说是复用.
下面从一个类实现数组栈和链式栈为例说明容器适配器:
一个类实现数组栈和链式栈
数组栈:即底层是用数组实现的;链式栈:即底层是用链表实现的
框架:
#pragma once
#include <list>
#include <vector>//动态数组
#include <array>//静态数组
namespace mystl
{
template<class T, class Container>
class stack
{
public:
//成员函数
private:
Container _con;
}
}Container可以为vector<int>,也可以是list<int>
成员函数中可以直接调用vector或list的成员函数,因==因为它们很多接口是统一的:
统一的调用代码:
_con.容器的成员函数(参数);完整实现:
namespace mystl
{
template<class T, class Container>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
T& top()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
size_t max_size()
{
return _con.max_size();
}
private:
Container _con;
};
}当然也可以用缺省参数:
template<class T, class Container=std::vector<T>>
class stack
{
//......
}这样可以省略第二个参数: mystl::stack<int> st1,默认是用vector实现的
注:不用写构造函数和析构函数,因为Container _con是自定义类型,编译器会自动调用它的构造函数和析构函数
拓展:带容器适配器的迭代器函数的写法
虽然栈不需要迭代器,但如果加上vector或list的迭代器的函数应该怎么写?
以begin()为例,如果直接这样写会报错:
iterator begin()
{
return _con.begin();
}
上面这样写是有歧义的,当模版没有实例化时,编译器不确定iterator是类型还是静态成员变量,因此要使用typename关键字(之前在CD33.【C++ Dev】初识模版文章提到过)来告知编译器iterator是类型
typename typedef Container::iterator iterator;也可以看看IBM公司的参考手册对此的描述:
限定名(qualified name)指代某个类型且这个名字依赖于模板参数时,要使用关键字 typename
提交到LeetCode上https://leetcode.cn/problems/implement-stack-using-queues/description/测试:
数组栈:
namespace mystl
{
template<class T, class Container>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
T& top()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
size_t max_size()
{
return _con.max_size();
}
private:
Container _con;
};
}
class MyStack {
public:
MyStack() {}
void push(int x)
{
st1.push(x);
}
int pop()
{
int ret=st1.top();
st1.pop();
return ret;
}
int top()
{
return st1.top();
}
bool empty()
{
return st1.empty();
}
mystl::stack<int, std::vector<int>> st1;
};提交结果:
链式栈(将上方代码的mystl::stack<int, std::vector<int>> st1;的vector改成list)的提交结果:
用vector实现队列queue
之前在98.【C语言】数据结构之队列文章提到过用数组实现queue
方法1:强制适配
除了pop()需要强制适配,其余的成员函数比较好写:
namespace mystl
{
template<class T, class Container=std::vector<T>>
class queue
{
public:
void push(T& x)
{
_con.push_back(x);
}
T& front()
{
return _con.front();
}
T& back()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
}pop()的写法:
弹出队头元素,在vector数组中就是删除下标为0(当然可以传begin()迭代器)的元素
void pop()
{
_con.erase(_con.begin());
}(注:vector没有pop_front函数)
提交到LeetCode的https://leetcode.cn/problems/implement-queue-using-stacks/description/上测试:
namespace mystl
{
template<class T, class Container=std::vector<T>>
class queue
{
public:
void pop()
{
_con.erase(_con.begin());
}
void push(T& x)
{
_con.push_back(x);
}
T& front()
{
return _con.front();
}
T& back()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
}
class MyQueue {
public:
MyQueue() {}
void push(int x)
{
q.push(x);
}
int pop()
{
int tmp=q.front();
q.pop();
return tmp;
}
int peek()
{
return q.front();
}
bool empty()
{
return q.empty();
}
mystl::queue<int> q;
};
提交结果:
方法1的实现也能适配list容器,提交结果:
但方法1的缺点是:vector的头删太慢了,降低效率
方法2:使用deque适配
看看STL库中queue的pop()写法:
#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class T, class Sequence = deque<T> >
#else
template <class T, class Sequence>
#endif
class queue {
friend bool operator== __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
friend bool operator< __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c;
public:
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference front() { return c.front(); }
const_reference front() const { return c.front(); }
reference back() { return c.back(); }
const_reference back() const { return c.back(); }
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_front(); }
};会发现默认的适配器为deque,而且pop()直接调用pop_front(),代码简洁,可读性高,并没有强制适配
稍微改改,提交到Leetcode的题上是能过的
namespace mystl
{
template <class T, class Sequence = std::deque<T>>
class queue {
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c;
public:
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference front() { return c.front(); }
const_reference front() const { return c.front(); }
reference back() { return c.back(); }
const_reference back() const { return c.back(); }
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_front(); }
};
}
class MyQueue {
public:
MyQueue() {}
void push(int x)
{
q.push(x);
}
int pop()
{
int tmp=q.front();
q.pop();
return tmp;
}
int peek()
{
return q.front();
}
bool empty()
{
return q.empty();
}
mystl::queue<int> q;
};
提交结果:
下一篇将讲deque的设计思路