代码拉取完成,页面将自动刷新
同步操作将从 ALONE_WORK/CPlusPlusThings 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
为何stack与queue不被称为容器呢?
下面本节带着这个问题来深入源码分析。
在stack的源码中我们关注两点:
_Sequence
为deque
_Sequence
对应容器的函数。template<typename _Tp, typename _Sequence = deque<_Tp> >
class stack
{
public:
typedef typename _Sequence::value_type value_type;
typedef typename _Sequence::reference reference;
typedef typename _Sequence::const_reference const_reference;
typedef typename _Sequence::size_type size_type;
typedef _Sequence container_type;
protected:
// See queue::c for notes on this name.
_Sequence c;
public:
reference
top()
{
__glibcxx_requires_nonempty();
return c.back();
}
void
push(const value_type& __x)
{ c.push_back(__x); }
}
测试stack底层容器
对于stack来说,底层容器可以是vector
、deque
、list
,但不可以是map
、set
。
由于编译器不会做全面性检查,当调用函数不存在的时候,就编译不通过,所以对于像set虽然不能作为底层容器,但如果具有某些函数,调用仍然是成功的,直到调用的函数不存在。
int test_stack() {
cout<<"============test_stack============="<<endl;
clock_t timeStart = clock();
stack<int, list<int>> c;
for (long i = 0; i < 100000; i++)
c.push(i+1);
cout << "stack.size()= " << c.size() << endl;
cout << "stack.top()= " << c.top() << endl;
c.pop();
cout << "stack.size()= " << c.size() << endl;
cout << "stack.top()= " << c.top() << endl;
cout << "use stack milli-seconds : " << (clock() - timeStart) << endl;
timeStart=clock();
stack<int, deque<int>> c1;
for (long i = 0; i < 100000; i++)
c1.push(i+1);
cout << "stack.size()= " << c1.size() << endl;
cout << "stack.top()= " << c1.top() << endl;
c1.pop();
cout << "stack.size()= " << c1.size() << endl;
cout << "stack.top()= " << c1.top() << endl;
cout << "use stack milli-seconds : " << (clock() - timeStart) << endl;
// vector可以作为stack的底层容器
stack<int, vector<int>> c2;
for (long i = 0; i < 100000; i++)
c2.push(i+1);
cout << "stack.size()= " << c2.size() << endl;
cout << "stack.top()= " << c2.top() << endl;
c2.pop();
cout << "stack.size()= " << c2.size() << endl;
cout << "stack.top()= " << c2.top() << endl;
cout << "use stack milli-seconds : " << (clock() - timeStart) << endl;
}
在queue的源码中我们关注两点:
_Sequence
为deque
_Sequence
对应容器的函数。template<typename _Tp, typename _Sequence = deque<_Tp> >
class queue
{
public:
typedef typename _Sequence::value_type value_type;
typedef typename _Sequence::reference reference;
typedef typename _Sequence::const_reference const_reference;
typedef typename _Sequence::size_type size_type;
typedef _Sequence container_type;
protected:
_Sequence c;
public:
void push(const value_type& __x)
{ c.push_back(__x); }
void pop()
{
__glibcxx_requires_nonempty();
c.pop_front();
}
}
其对应的UML类图如下:
同理,优先队列则是使用vector
作为默认容器。
template<typename _Tp, typename _Sequence = vector<_Tp>,
typename _Compare = less<typename _Sequence::value_type> >
class priority_queue
{
public:
typedef typename _Sequence::value_type value_type;
typedef typename _Sequence::reference reference;
typedef typename _Sequence::const_reference const_reference;
typedef typename _Sequence::size_type size_type;
typedef _Sequence container_type;
protected:
// See queue::c for notes on these names.
_Sequence c;
_Compare comp;
public:
reference
top()
{
__glibcxx_requires_nonempty();
return c.front();
}
void
push(const value_type& __x)
{
c.push_back(__x);
std::push_heap(c.begin(), c.end(), comp);
}
}
测试这两个容器配接器支持的底层容器:
queue
对于queue底层容器可以是deque
,也可以是list
,但不能是vector
,map
,set
,使用默认的deque效率在插入方面比其他容器作为底层要快!
int test_queue() {
cout<<"============test_queue============="<<endl;
clock_t timeStart = clock();
queue<int, list<int>> c;
for (long i = 0; i < 100000; i++) {
c.push(i+1);
}
cout << "stack.size()= " << c.size() << endl;
cout << "stack.front()= " << c.front() << endl;
c.pop();
cout << "stack.size()= " << c.size() << endl;
cout << "stack.front()= " << c.front() << endl;
cout << "use list milli-seconds : " << (clock() - timeStart) << endl;
timeStart=clock();
queue<int, deque<int>> c1;
for (long i = 0; i < 100000; i++) {
c1.push(i+1);
}
cout << "stack.size()= " << c1.size() << endl;
cout << "stack.front()= " << c1.front() << endl;
c1.pop();
cout << "stack.size()= " << c1.size() << endl;
cout << "stack.front()= " << c1.front() << endl;
cout << "use deque milli-seconds : " << (clock() - timeStart) << endl;
}
priority_queue
对于优先队列来说,测试结果发现,采用deque
要比默认的vector
插入速度快!
底层支持vector、deque容器,但不支持list、map、set。
int test_priority_queue() {
cout<<"============test_priority_queue============="<<endl;
clock_t timeStart = clock();
priority_queue<int, deque<int>> c1;
for (long i = 0; i < 100000; i++) {
c1.push(i+1);
}
cout << "stack.size()= " << c1.size() << endl;
cout << "stack.top()= " << c1.top() << endl;
c1.pop();
cout << "stack.size()= " << c1.size() << endl;
cout << "stack.top()= " << c1.top() << endl;
cout << "use deque milli-seconds : " << (clock() - timeStart) << endl;
priority_queue<int, vector<int>> c2;
for (long i = 0; i < 100000; i++)
c2.push(i+1);
cout << "stack.size()= " << c2.size() << endl;
cout << "stack.top()= " << c2.top() << endl;
c2.pop();
cout << "stack.size()= " << c2.size() << endl;
cout << "stack.top()= " << c2.top() << endl;
cout << "use stack milli-seconds : " << (clock() - timeStart) << endl;
}
因此,stack、queue、priority_queue不被称为容器, 把它称为容器配接器。
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。