STL实践与分析

--容器适配器

引：

除了顺序容器。标准库还提供了三种顺序容器适配器：queue,priority_queue和stack。适配器是标准库中的概念。包含容器适配器，迭代器适配器和函数适配器。

1、使用适配器时，必须包括相关头文件：

#include <stack>
#include <queue>

2、覆盖基础容器类型

    默认的queue和stack都是基于deque实现，而priority_queue则再vector容器上实现，在创建适配器时,通过将一个顺序容器指定为适配器的第二个类型实參,可覆盖其关联的基础容器类型:

stack<string> strStk;
stack< string,vector<string> > str_stk;
stack< string,vector<string> > str_stk2(strStk);
//Error
stack< string,vector<string> > str_stk3(str_stk);
//OK

stack适配器所关联的基础容器能够是随意一种顺序容器类型。

因此,stack栈能够建立在vector、list或者 deque容器之上。

而queue适配器要求其关联的基础容器必须提供push_front运算,因此仅仅能建立在list容器上,而不能建立在vector容器上。

priority_queue适配器要求提供随机訪问功能,因此可建立在vector或 deque容器上,但不能建立在list容器上。

3、适配器的关系运算由当中的元素依次比較来实现

一、栈适配器

const stack<int>::size_type stk_size = 10;
stack<int> intStk;
int ix = 0;
while (intStk.size() != stk_size)
{
intStk.push(ix ++);
}
int err_cnt = 0;
while (!intStk.empty())
{
int val = intStk.top();
if (val != --ix)
{
cerr << "oops! expected " << ix
<< " received " << val << endl;
++err_cnt;
}
intStk.pop();
}
cout << "Our Program ran with " << err_cnt << " errors!" << endl;

   默认情况下,栈适配器建立在deque容器上,因此採用deque提供的操作来实现栈功能。

比如,运行以下的语句:

intStack.push(ix++);

这个操作通过调用push_back操作实现,而该intStk所基于的 deque对象提供。

虽然栈是以deque容器为基础实现的,可是程序猿不能直接訪问deque所提供的操作。

二、队列和优先级队列

使用这两种队列，必须包括queue头文件。

    priority_queue同意用户为队列中存储的元素设置优先级。

这样的队列不是直接将新元素放置在队列尾部,而是放在比它优先级低的元素前面。标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。

//P302 习题9.42
int main()
{
//
freopen("input","r",stdin);
stack<string> strStk;
string val;
while (cin >> val)
{
strStk.push(val);
}
while (!strStk.empty())
{
val = strStk.top();
cout << val << endl;
strStk.pop();
}
}

//习题9.43
int main()
{
freopen("input","r",stdin);
stack<char> sexp;
string exp;
cin >> exp;
string::iterator iter = exp.begin();
while (iter != exp.end())
{
if (*iter != ')')
{
sexp.push(*iter);
}
else
{
while (!sexp.empty() && sexp.top() != '(')
{
cout << sexp.top() << endl;
sexp.pop();
}
if (sexp.top() == '(')
{
sexp.pop();
sexp.push('@');
}
else
{
cerr << "No match ( !" << endl;
return 0;
}
}
++iter;
}
while (!sexp.empty())
{
cout << sexp.top() << endl;
sexp.pop();
}
}