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

这一章讲了三种容器配接器(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<>要加入头文件:

1
#include <stack>

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

1
2
3
4
namespace std {
    template <class T, class Container = deque<T> >
    class stack;
}

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

下面使用vector来容纳元素:

1
stack<int, vector<int> > st;

stack的内部接口图:
stack1

 

  • 3.(P446)

自定义的Stack Class
改变了两点:
①.pop()会返回下一个元素(即被删除元素)
②.如果栈为空,则pop()和top()会抛出异常

stack.h头文件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#ifndef STACK_H
#define STACK_H
 
#include <deque>
#include <exception>
 
template <class T>
class Stack{
protected:
    std::deque<T> 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<T>::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文件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <list>
#include <algorithm>
#include “stack.h”
using namespace std;
 
int main()
{
    try {
        Stack<int> 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<>要加入头文件:

1
#include <queue>

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

1
2
3
4
namespace std {
    template <class T, class Container = deque<T> >
    class queue;
}

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

 

  • 5.(P453)

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

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

1
#include <queue>

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

1
2
3
4
5
6
namespace std {
    template <class T,
              class Container = vector<T>,
              class Compare = less<typename Container::value_type> >
    class priority_queue;
}

注意这里的缺省容器不再是deque了,而是vector。
带有默认值的第三个template之处了”用以搜寻下一个最高优先元素”的排序准则。缺省是operator<。
eg.下面定义一个逆向(降序的)priority queue:

1
priority_queue<float, vector<float>, greater<float> > buffer;

随便写了一个小程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// Author: Tanky Woo
// Blog:    www.WuTianQi.com
#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <queue>
using namespace std;
 
int main()
{
    vector<int> vec1;
    vector<int> 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<int, vector<int>, greater<int> > st(vec1.begin(), vec1.end(), greater<int>() , vec2);
    while(!st.empty())
    {
        cout << st.top() << ” “;
        st.pop();
    }
}

 

  • 6.(P460)

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

1
#include <bitset>

bitset的定义:

1
2
3
4
namespace std {
    template <size_t Bits>
    class bitset;
}

bitset的初始化:

bitset<n> b; 
b有n位,每位都为0

bitset<n> b(u); 
b是unsigned long型u的一个副本

bitset<n> b(s); 
b是string对象s中含有的位串的副本

bitset<n> b(s, pos, n); 
b是s中从位置pos开始的n个位的副本

注:
string对象和bitset对象之间是反向转化的:string对象的最右边字符(即下标最大的那个字符)用来初始化bitset对象的低阶位(即下标为0的位)。当用string对象初始化bitset对象时,记住这一差别很重要。

但是,如果直接输出bitset变量,其顺序又和string一样。
eg:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <queue>
#include <bitset>
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() 返回指定位的状态
to_string() 返回bitset的字符串表示
to_ulong() 返回bitset的整数表示

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《《C++标准程序库》学习笔记8 — 第十章》有81个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注