Tanky WooRSS

《C++标准程序库》学习笔记8 -- 第十章

29 Jan 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

这一章讲了三种容器配接器(container adapter)(Stack, Queue, Priority queue) 和 bitset的特殊容器。

配接器: 一种用来修饰容器(Containers)或仿函数(Functors)或迭代器(Iterators)接口的东西。 例如:STL提供的Queue和Stack,虽然看似容器,其实只能算是一种容器配接器,因为 它们的底部完全借助Deque,所有操作有底层的Deque供应。改变Functor接口者,称为Function Adapter;改变Container接口者,称为Container Adapter;改变Iterator接口者,称为Iterator Adapter。

 

Stack(栈) class stack<>实作出了一个stack,可以让我们直接使用LIFO的栈。 使用stack<>要加入头文件:

#include 

在头文件中,class stack定义如下:

namespace std {
    template  >
    class stack;
}

带一个template参数代表元素型别,带有默认值的第二个template参数定义stack内部存放元素所用的实际容器,缺省采用queue.

下面使用vector来容纳元素:

stack > st;

stack的内部接口图: stack1

 

自定义的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

 

Queue(队列) Class queue<>实作出一个queue(FIFO)。 queue和上面讲的stack基本类似。 使用queue<>要加入头文件:

#include 

在头文件中,class queue定义如下:

namespace std {
    template  >
    class queue;
}

带一个template参数代表元素型别,带有默认值的第二个template参数定义queue内部存放元素所用的实际容器,缺省采用queue.   queue的内部接口图: queue queue的自定义版本类似stack,只需要在pop()时由popback()改成popfront()即可。

 

Priority Queue(优先队列) class priorityqueue<> 实作出一个queue,其元素根据优先级被读取,和queue的接口非常类似。只不过他的"下一个元素"不是最先插入的元素,而是"优先级"最高的元素。也就是说,priorityqueue里的元素按照指定的规则已经进行了排序。

缺省是按operator<进行升序排列,但如果同时存在若干数值最大的元素,则无法确定下一个元素是若干最大元素中的哪一个。 Priority Queue和一般的queue都定义在头文件中:

#include 

在头文件中,Priority Queue的定义如下:

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();
    }
}

 

Bitset bitset的优点在于可容纳任意个数的位,但是不能改变状态,如果需要一个可变长度的位容器,则可以选择vector。 Class bitset定义于头文件中。

#include 

bitset的定义:

namespace std {
    template 
    class bitset;
}

bitset的初始化:

bitset b;  b有n位,每位都为0 bitset b(u);  b是unsigned long型u的一个副本 bitset b(s);  b是string对象s中含有的位串的副本 bitset b(s, pos, n);  b是s中从位置pos开始的n个位的副本

注: 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的整数表示