这一章讲了三种容器配接器(container adapter)(Stack, Queue, Priority queue) 和 bitset的特殊容器。
- 1.
配接器: 一种用来修饰容器(Containers)或仿函数(Functors)或迭代器(Iterators)接口的东西。 例如:STL提供的Queue和Stack,虽然看似容器,其实只能算是一种容器配接器,因为 它们的底部完全借助Deque,所有操作有底层的Deque供应。改变Functor接口者,称为Function Adapter;改变Container接口者,称为Container Adapter;改变Iterator接口者,称为Iterator Adapter。
- 2.(P435)
Stack(栈) class stack<>实作出了一个stack,可以让我们直接使用LIFO的栈。 使用stack<>要加入头文件:
#include
在头文件
namespace std {
template >
class stack;
}
带一个template参数代表元素型别,带有默认值的第二个template参数定义stack内部存放元素所用的实际容器,缺省采用queue.
下面使用vector来容纳元素:
stack > st;
- 3.(P446)
自定义的Stack Class 改变了两点: ①.pop()会返回下一个元素(即被删除元素) ②.如果栈为空,则pop()和top()会抛出异常
stack.h头文件:
#ifndef STACK_H
#define STACK_H
#include
#include
template
class Stack{
protected:
std::deque c; // container for the elements
public:
class ReadEmptyStack : public std::exception {
public:
virtual const char* what() const throw() {
return “read empty stack”;
}
};
typename std::deque::size_type size() const {
return c.size();
}
bool empty() const {
return c.empty();
}
void push(const T& elem) {
c.push_back(elem);
}
T pop() {
if(c.empty()) {
throw ReadEmptyStack();
}
T elem(c.back());
c.pop_back();
return elem;
}
T& top() {
if(c.empty()) {
throw ReadEmptyStack();
}
return c.back();
}
};
#endif
main.cpp文件:
#include
#include
#include
#include
#include
#include
#include “stack.h”
using namespace std;
int main()
{
try {
Stack st;
st.push(1);
st.push(2);
st.push(3);
cout << st.top() << endl;
st.pop();
cout << st.top() << endl;
st.pop();
st.top() = 77;
st.push(4);
st.push(5);
st.pop();
cout << st.pop() << ‘ ‘;
cout << st.pop() << endl;
cout << st.pop() << endl;
}
catch(const exception& e) {
cerr << “EXCEPTION: ” << e.what() << endl;
}
}
这个程序在stack的异常类编写时,注意what不再抛出任何异常,用了throw(),否则容易导致错误。 我在CSDN上求助过这个问题: http://topic.csdn.net/u/20110129/16/280fddaa-2ece-4260-9bcf-dbd14afc91f5.html?74553862 http://www.360doc.com/content/10/1215/21/1066008_78498762.shtml
- 4.(P444)
Queue(队列) Class queue<>实作出一个queue(FIFO)。 queue和上面讲的stack基本类似。 使用queue<>要加入头文件:
#include
在头文件
namespace std {
template >
class queue;
}
带一个template参数代表元素型别,带有默认值的第二个template参数定义queue内部存放元素所用的实际容器,缺省采用queue. queue的内部接口图: queue的自定义版本类似stack,只需要在pop()时由popback()改成popfront()即可。
- 5.(P453)
Priority Queue(优先队列) class priorityqueue<> 实作出一个queue,其元素根据优先级被读取,和queue的接口非常类似。只不过他的"下一个元素"不是最先插入的元素,而是"优先级"最高的元素。也就是说,priorityqueue里的元素按照指定的规则已经进行了排序。
缺省是按operator<进行升序排列,但如果同时存在若干数值最大的元素,则无法确定下一个元素是若干最大元素中的哪一个。
Priority Queue和一般的queue都定义在头文件
#include
在头文件
namespace std {
template ,
class Compare = less >
class priority_queue;
}
注意这里的缺省容器不再是deque了,而是vector。 带有默认值的第三个template之处了"用以搜寻下一个最高优先元素"的排序准则。缺省是operator<。 eg.下面定义一个逆向(降序的)priority queue:
priority_queue, greater > buffer;
随便写了一个小程序:
// Author: Tanky Woo
// Blog: www.WuTianQi.com
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int main()
{
vector vec1;
vector vec2;
for(int i=1; i<=9; ++i)
vec1.push_back (i);
for(int i=1; i<=9; ++i)
vec2.push_back (i+10);
// 注意这里的用法.
priority_queue, greater > st(vec1.begin(), vec1.end(), greater() , vec2);
while(!st.empty())
{
cout << st.top() << ” “;
st.pop();
}
}
- 6.(P460)
Bitset
bitset的优点在于可容纳任意个数的位,但是不能改变状态,如果需要一个可变长度的位容器,则可以选择vector
#include
bitset的定义:
namespace std {
template
class bitset;
}
bitset的初始化:
bitset
注: string对象和bitset对象之间是反向转化的:string对象的最右边字符(即下标最大的那个字符)用来初始化bitset对象的低阶位(即下标为0的位)。当用string对象初始化bitset对象时,记住这一差别很重要。
但是,如果直接输出bitset变量,其顺序又和string一样。 eg:
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int main()
{
string s(“0011001101″);
bitset<10> t(s);
// 直接输出
cout << t << endl;
// 从低位到高位输出
for(int i=0; i<10; ++i)
cout << t[i];
cout << endl;
}
输出结果: 0011001101 1011001100
bitset提供的函数很多,常用有下面几个。 any() 如果有任何一个位被设置就返回true count() 返回被设置的位的个数 flip() 反转bits中的位 none() 如果没有位被设置则返回true reset() 清空所有位 set() 设置位 size() 返回可以容纳的位的个数 test() 返回指定位的状态 tostring() 返回bitset的字符串表示 toulong() 返回bitset的整数表示