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)
网友评论