The C++ standard library(侯捷/孟岩 译

10 Special Containers(p435)

概述：

1. container adapters:
   1). stack
   2). queue
   3). priority queue

2. bitset

10.1 stack

#include <stack>
LIFO : last in first out
可能实现如下：

namespace std
{
    template <class T, class Container = deque<T> > class stack
    {
        public:
            typedef typename Container::value_type value_type;
            typedef tupename Container::size_type size_type;
            typedef Container container_type;

        protected:
            Container c;    // container

        public:
            explicit stack (const Container& = Container() );

            bool empty() const {    return c.empty();}
            size_type size() const {    return c.size();}
            void push( const value_type& x) {c.push_back(x);}
            void pop() {    c.pop_back();}
            value_type& top() { return c.back();}
            const value_type& top() const { return c.back();}
    };

    template <class T, class Container> 
        bool operator== (const stack<T, Container>& , const stack<T, Container>& );

    template <class T, class Container>
        bool operator< (const stack<T, Container>& , const stack<T, Container>& );

    //... other comparision operators
}

10.2 queue(p444)

#include <queue>
FIFO : first in first out
可能实现如下：

namespace std
{
    template <class T, class Container = deque<T> > class queue
    {
        public:
            typedef typename Container::value_type value_type;
            typedef typename Container::size_type size_type;
            typedef typename container_type;

        protected:
            Container c;    // container

        public:
            explicit queue(const Container& = Container());

            bool empty() const {    return c.empty();}
            size_type size() const {    return c.size();}
            void push( const value_type& x) {   c.push_back(x);}
            void pop()  {   c.pop_front();}
            value_type& front() {   return c.front();}
            const value_type& front() const {   rerurn c.front();}
            value_type& back() {    return c.back();}
            const value_type& back() const {    return c.back();}
    };

    template <class T, class Container>
        bool operator== (const queue<T, Container>& , const queue<T, Container>& );

    template <class T, class Container>
        bool operator< (const queue<T, Container>& , const queue<T, Container>& );

    //... other comparision operators
}

乍一看，关于泛型之类的定义结构，和pair有些相似呢

10.3 priority queue(p453)

#include <queue>
基于heap。

namespace std
{
    template <class T, class Container = vector<T> ,
             class Compare = less<typename Container::value_type> > 
    class priority_queue
    {
        public:
            typedef typename Container::value_type value_type;
            typedef typename Container::size_type size_type;
            typedef typename Container container_type;

        protected:
            Compare comp;   // sorting criterion
            Container c;    // container

        public:
            // constructor
            exlicit priority_queue(const Compare& cmp = Compare(),
                    const Container& cont = Container():
                    comp(cmp), c(cont)
            {
                make_heap(c.begin(), c.end(),comp));
            }

            template <class InputIterator>
            priority_queue(InputIterator first, InputIterator last,
                        const Compare& comp = Compare(),
                        const Container& cont = Container() ):
                comp(cmp), c(cont)
            {
                c.insert(c.end(), first, last);
                make_heap(c.begin(), c.end(), comp);
            }

            void push(const value_type& x)
            {
                c.push_back(x);
                push_heap(c.begin(), c.end(), comp);
            }

            void pop()
            {
                pop_heap(c.begin(), c.end(), comp);
                c.pop_back();
            }

            bool empty() const {    return c.empty();}
            size_type size() const {    return c.size();}
            const value_type& top() const { return c.front();}
    };
}

10.4 bitset(p460)

#include <bitset>
生成-拷贝-销毁

bitset<bits>::bitset()   default ctor所有位初始化为0；
bitset<bits>::bitset(unsigned long value) 以整数值value的位初始化；

explicit bitset<bits>::bitset(const string& str)
bitset<bits>::bitset(const string& str, string::size_type str_idx)
bitset<bits>::bitset(const string& str, string::size_type str_idx, 
                     string::size_type str_num)
以字符串或其子串  初始化；str_idx是str中用于初始化的第一个字符；
缺省str_num时默认从str_idx开始到str结束的所有字符 用于初始化。
若str_idx > str.size()会抛出 out_of_range异常。

Nonmanipulating Operation

size_t bitset<bits>::size() const 返回位数；
size_t bitset<bits>::count() const 返回1的个数；
bool bitset<bits>::any() const判断是否有任何位被设立(数值为1)；
bool bitset<bits>::none() const 判断是否没有任何一位被设立；
bool bitset<bits>::test (size_t idx) const 
       判断idx位置的位是否被设立(会检查idx>=size()并抛异常)；
bool bitset<bits>::operator== (const bitset<bits>& bits) const 
       判断*this==bits；
bool bitset<bits>::operator!= (const bitset<bits>& bits) const

manipulating operation

bitset<bits>& bitset<bits>::set() 将所有位置1；
bitset<bits>& bitset<bits>::set(size_t idx);
bitset<bits>& bitset<bits>::set(size_t idx, int value) 
              根据value来设定idx位置的值；
bitset<bits>& bitset<bits>::reset() 将所有位置为0；
bitset<bits>& bitset<bits>::reset(size_t idx);
bitset<bits>& bitset<bits>::flip() 反转所有位，即取反；
bitset<bits>& bitset<bits>::flip(size_t idx);
bitset<bits>& bitset<bits>::operator ^=  (const bitset<bits>& bits) 异或操作；
bitset<bits>& bitset<bits>::operator |= (const bitset<bits>& bits) 或操作；
bitset<bits>& bitset<bits>::operator &= (const bitset<bits>& bits) 与操作；
bitset<bits>& bitset<bits>::operator <<=(size_t num) 左移num位；
bitset<bits>& bitset<bits>::operator >>=(size_t num) 右移num位；

operator[] 存取位

bitset<bits>::reference bitset<bits>::operator [] (size_t idx)
bool bitset<bits>::operator [] (size_t  idx) const
对于reference，允许如下五种操作：
1. reference& operator= (bool) 根据传来的值设置该位；
2. reference& operator= (const reference&) 根据另一个reference设置该位；
3. reference& flip() 翻转；
4.operator bool() const 将该位转换为布尔值；
5. bool operator ~() const 返回该位的补码(翻转值)；
  eg:
    bitset<50> flags;
    flags[42] = true;  
    flags[13] = flags[42];
    flags[42].flip();
    if (flags[13] ) {  flags[10] = ~flags[42];  }

产生新的(经修改的)bitset

bitset<bits> bitset<bits>::operator ~() const
bitset<bits> bitset<bits>::operator <<(size_t num) const
bitset<bits> bitset<bits>::operator >>(size_t num) const
bitset<bits> operator &(const bitset<bits>& bits1, const bitset<bits>& bits2)
bitset<bits> operator | (const bitset<bits>& bits1, const bitset<bits>& bits2)
bitset<bits> operator ^ (const bitset<bits>& bits1, const bitset<bits>& bits2)

型别转换

unsigned long bitset<bits>::to_ulong() const 
    返回所代表的整数(若unsigned long 不足以表示该整数，则抛出overflow_error异常)
string bitset<bits>::to_string() const 
    返回一个string，该string表现该bitset的二进制值

IO 操作

istream& operator >> (istream& strm, bitset<bits>& bits)
  将'0'和'1'读入bits，若不是'0'或'1'则读取结束；
  读入的位少于bits的位数，则前面补0;
ostream& operator<< (ostream& strm, const bitset<bits>& bits)