1. 容器簡介

1.1 容器的分類

• 序列容器 vector, list, deque

• 容器適配器 queue, stack, priority_queue

• 關(guān)聯(lián)容器 set, map, multiset, multimap

序列容器是提供一組線性儲(chǔ)存的容器，而容器適配器負(fù)責(zé)將它們按照數(shù)據(jù)結(jié)構(gòu)的方式組織起來，關(guān)聯(lián)容器提供關(guān)鍵字與值之間的關(guān)系可以用來快速訪問。

vector是一種允許快速隨機(jī)訪問其中元素的線性序列,在末尾添加新的元素比較快

deque是雙端隊(duì)列，兩邊可以同時(shí)添加元素，而且訪問速度與vector差不多快

list是雙向鏈表，插入操作比vector和deque要快，但是隨機(jī)訪問要慢得多

1.2 容器與指針

在容器中存放指針，容器并不會(huì)幫忙調(diào)用指針的析構(gòu)函數(shù)，所以程序員必須自己管理存放的指針。

vector<int> v;

v.push_back(new int(4));

必須自己去刪除里面的指針?biāo)赶虻膬?nèi)存

delete v[i];

2.迭代器

2.1 普通迭代器

一般來講，容器都有用于遍歷的迭代器，除了容器適配器外，因?yàn)槿萜鬟m配器的行為和迭代器的行為是沖突的。

定義一個(gè)用于某種容器的迭代器的方法如下：

<ContainerType>::iterator

<ContainerType>::const_iterator

第一個(gè)是普通迭代器，第二個(gè)是只讀迭代器

容器的begin和end方法分別會(huì)產(chǎn)生一個(gè)指向開頭和指向超越末尾的迭代器，如果容器是const，則產(chǎn)生的迭代器也會(huì)是const

迭代器支持++和!=，==，等運(yùn)算，可以用迭代器遍歷容器

#include <iostream>
#include<vector>
#include<iterator>
using namespace std;
int main(int argc, char** argv) {int buf[] = {1,2,3,4,5,6,7,8,9,10};vector<int> v;copy(begin(buf), end(buf), back_inserter(v));vector<int>::iterator v_it = v.begin();while(v_it != v.end()){cout << *v_it << " "; v_it++;}cout << endl;return 0;
}

2.2可逆迭代器

可逆迭代器從末尾反向移動(dòng)，產(chǎn)生可逆迭代器的方法:

<ContainerType>reverse_iterator

<ContainerType>const_revese_iterator

容器的rbegin和rend會(huì)產(chǎn)生相應(yīng)的反向迭代器

#include <iostream>
#include<vector>
#include<iterator>
using namespace std;
int main(int argc, char** argv) {int buf[] = {1,2,3,4,5,6,7,8,9,10};vector<int> v;copy(begin(buf), end(buf), back_inserter(v));vector<int>::reverse_iterator v_it = v.rbegin();while(v_it != v.rend()){cout << *v_it << " "; //輸出10 9 8 7 6 5 4 3 2 1v_it++;}cout << endl;return 0;
}

2.3迭代器的種類

1.輸入迭代器

定義：istream_iterator 和 istreambuf_iterator

只能讀取，而是是一次傳遞，只對(duì)每一個(gè)值做一次解析，只允許前向移動(dòng)。

2.輸出迭代器

ostream_iterator,ostreambuf_iterator

基本輸入迭代器一樣，只是用于寫入的

3.前向迭代器

它既可以讀，也可以寫，而且支持多次讀寫解析，但是只允許前向移動(dòng)

4.雙向迭代器

它比前向迭代器多一個(gè)后向移動(dòng)的功能

5.隨機(jī)訪問迭代器

它和普通指針一樣，但是沒有空的概念

輸入輸出迭代器的程序案例：

    istream_iterator<int> it(cin);istream_iterator<int> eof;vector<int> v;copy(it, eof, back_inserter(v));ostream_iterator<int> out(cout," ");copy(v.begin(), v.end(), out);

2.4迭代器的定義與繼承體系

struct input_iterator_tag{};//輸入迭代器

struct output_iterator_tag{};//輸出迭代器

struct forward_iterator_tag: public input_iterator{};//前向迭代器

struct bidirectional_iterator_tag: public forward_iterator_tag{};//雙向迭代器

struct random_access_iterator_tag: public bidirectional_iterator_tag{};//隨機(jī)迭代器

2.5預(yù)定義迭代器

C++STL有一個(gè)便利的預(yù)定義迭代器集合，比如rend和rbegin會(huì)返回一個(gè)reverse_iterator迭代器。

而插入迭代器則替代operator=給容器賦值，它是一種插入或者壓入容器的操作。比如當(dāng)容器已經(jīng)滿了的時(shí)候，這種操作就會(huì)分配新的空間。

back_insert_iterator和 front_insert_iterator迭代器的構(gòu)造函數(shù)的參數(shù)就是一個(gè)序列，然后調(diào)用push_back和push_front進(jìn)行賦值。

back_insert和front_insert函數(shù)會(huì)產(chǎn)生這樣這樣對(duì)應(yīng)的迭代器

2.6 流迭代器

istream_iterator有一個(gè)默認(rèn)的構(gòu)造函數(shù)，指向流的末尾的迭代器，所以可用默認(rèn)的流迭代器對(duì)象標(biāo)注末尾的位置

ostream_iterator沒有末尾迭代器，需要一個(gè)辦法指示末尾

    int main(int argc, char** argv) {ifstream in("main.cpp");if(!in)return 0;istream_iterator<char> in_it(in), in_end;ostream_iterator<char> out_it(cout);while(in_it != in_end){*out_it = *in_it++;}return 0;}

2.7 操作未初始化的儲(chǔ)存區(qū)

raw_storage_iterator是一個(gè)輸出迭代器，它可以把未初始化的去儲(chǔ)存區(qū)賦值

    int* ptr = new int[10];raw_storage_iterator<int* , int> raw_int_ptr(ptr);for(int i = 0; i < 10; i++)*raw_int_ptr++ = i*i;copy(ptr, ptr+10, ostream_iterator<int>(cout, " "));delete [] ptr

raw_storage_iterator使用的是operator=來給未初始化的儲(chǔ)存區(qū)賦值，同時(shí)，儲(chǔ)存區(qū)的類型必須與寫入的對(duì)象要一致，不一致就要進(jìn)行類型轉(zhuǎn)化。

3.基本序列容器

3.1 vector

這個(gè)容器是一個(gè)連續(xù)的數(shù)組，可以快速訪問，但是向其中插入新的元素，是基本不可能的，除了push_back()，使用插入算法會(huì)造成巨大的代價(jià)

并且，vector儲(chǔ)存區(qū)滿了的時(shí)候，也會(huì)有很多令人詬病的問題.

當(dāng)vector滿了的時(shí)候，會(huì)自動(dòng)擴(kuò)充容量，然后把原來儲(chǔ)存的對(duì)象復(fù)制到新的儲(chǔ)存區(qū)，原來如果使用迭代器做了某些操作，迭代器將會(huì)失效。

當(dāng)然，這里不是指不能對(duì)vector進(jìn)行刪除和插入，而是代價(jià)過大，相對(duì)而言不值得。

對(duì)容器末尾使用插入和刪除是可以的。對(duì)其他地方，則會(huì)造成巨大的開銷，比如在vector中間部分插入一個(gè)元素，則會(huì)導(dǎo)致vector中間開始的元素全體向后移動(dòng)。

    struct ex* p = (struct ex*)malloc(sizeof(struct ex));p->s = (char*)malloc(sizeof(char) * 10);free(p->s);free(p);

3.2 deque

這是一種類似于vector的容器，但是和vector的不同之處在于,deque實(shí)際上不是連續(xù)的儲(chǔ)存區(qū)，而是分散的若干連續(xù)塊儲(chǔ)存，然后用一個(gè)映射關(guān)系來記錄各部分。

它可以在兩端進(jìn)行插入和刪除，vector只能進(jìn)行末端的插入的刪除。除此之外，deque的push_back要比vector更為高效。vector的隨機(jī)訪問要比deque更快

3.3 序列之間的轉(zhuǎn)換

比如要把deque的內(nèi)容放到vector之中

這些基本序列都有一個(gè)函數(shù)assign,只需要傳入起點(diǎn)迭代器和終點(diǎn)迭代器，就可以復(fù)制給新的容器

3.4 迭代器失效

比如對(duì)vector插入一個(gè)值，原本的迭代器將會(huì)出現(xiàn)未知的錯(cuò)誤

template<typename Container>
void print(Container first, Container last, const string& title = "", const string& space = " "){if(title != "")cout << title << ":";while(first != last){cout << *first++ << space;}cout << endl;
}int main(int argc, char** argv) {int buf[] = {1,2,3,4,5,6,7,8,9,10};vector<int> v;v.assign(begin(buf), end(buf));vector<int>::iterator first, last;first = v.begin(), last = v.end();print(first,last);v.push_back(11);//使用push_back之后，迭代器將會(huì)失效 print(first,last);return 0;
}

3.5 隨機(jī)訪問

vector和deque都可以通過operator[]，和at方法訪問，但是operator[]沒有邊界檢查，at有邊界檢查，如果超過邊界，則會(huì)拋出異常，但是operator[]的訪問速度要比at快

3.6 list

這是一個(gè)雙向鏈表，它沒辦法進(jìn)行隨機(jī)訪問，也就是不能存在operator[]，但是它方便進(jìn)行刪除和插入，這方面的效率遠(yuǎn)高于vector和deque，list對(duì)象被創(chuàng)建之后，絕對(duì)不會(huì)

被移動(dòng)，也不會(huì)被刪除，因?yàn)橐苿?dòng)意味著鏈表的結(jié)構(gòu)會(huì)被改變。

template<typename Container>
void print(Container first, Container last, const string& title = "", const string& space = " "){if(title != "")cout << title << ":";while(first != last){cout << *first++ << space;}cout << endl;
}int main(int argc, char** argv) {int buf[] = {1,2,3,4,5,6,7,8,9,10};list<int> v;v.assign(begin(buf), end(buf));list<int>::iterator first, last;first = v.begin(), last = v.end();print(first,last);v.push_back(11);//list即使是使用了push_back也不會(huì)失效 print(first,last);return 0;
}

對(duì)list的排序和反轉(zhuǎn)，最好使用其自帶的方法，這樣效率更高

3.7 鏈表與集合

對(duì)鏈表使用sort和unique之后，鏈表其實(shí)就有了集合的性質(zhì)，不同的是，鏈表的效率沒有集合高，集合是使用平衡樹。

3.8 交換序列

這里的交換序列，指的是類型相同的序列進(jìn)行交換，雖然STL有通用的swap算法，但是，自帶的效率要更高一些

4.集合

集合只保留一份副本，按照順序?qū)υ剡M(jìn)行排序，底層使用平衡樹，查找速度是對(duì)數(shù)級(jí)。

#include <iostream>
#include<vector>
#include<iterator>
#include<string>
#include<algorithm>
#include<fstream>
#include<memory> 
#include<list>
#include<set> 
#include<cctype>
#include<cstring>
#include<sstream>
using namespace std;template<typename Container>
void print(Container first, Container last, const string& title = "", const string& space = " "){if(title != "")cout << title << ":";while(first != last){cout << *first++ << space;}cout << endl;
}
//用空格替換字母和'以外的字符 
char replaceJunk(char c){return isalpha(c) || c=='\'' ? c : ' '; 
}int main(int argc, char** argv) {ifstream in("test.txt",ios::in);if(!in){cerr << "open fail\n";return 0;}set<string> wordList;string line;while(getline(in, line)){transform(line.begin(), line.end(), line.begin(), replaceJunk);istringstream is(line);string word;while(is >> word){wordList.insert(word);}}print(wordList.begin(), wordList.end(),"set","\n");return 0;

下面的程序?qū)⑹褂酶雍唵蔚霓k法，引入流緩沖迭代器

#include <iostream>
#include<iterator>
#include<string>
#include<algorithm>
#include<fstream>
#include<memory> 
#include<set> 
#include<cctype>
#include<cstring>
#include<sstream>
using namespace std;template<typename Container>
void print(Container first, Container last, const string& title = "", const string& space = " "){if(title != "")cout << title << ":";while(first != last){cout << *first++ << space;}cout << endl;
}int main(int argc, char** argv) {ifstream in("test.txt",ios::in);if(!in){cerr << "open fail\n";return 0;}set<string> wordList;istreambuf_iterator<char> p(in),end;//輸入流迭代器沒有末尾迭代器的標(biāo)志while(p != end){string word;insert_iterator<string> ii(word,word.begin());//這個(gè)迭代器需要一個(gè)容器和插入容器中的起始位置while(p != end && !isalpha(*p)) //跳過所有的空格++p;while(p != end && isalpha(*p))//如果是字符，則插入到word中*ii++ = *p++;if(word.size() != 0)wordList.insert(word);} print(wordList.begin(), wordList.end(),"set","\n");return 0;
}

istreambuf_iterator是一個(gè)輸入流迭代器，所以需要一個(gè)默認(rèn)構(gòu)造的迭代器作為結(jié)束的標(biāo)志，而插入迭代器是輸出迭代器，它包含了容器的指針和一個(gè)指向容器的某處的迭代器，

初始化之后，對(duì)迭代器的輸入，則是從指向此處的迭代器的位置開始的。

5.可完全重用的標(biāo)識(shí)符識(shí)別器

創(chuàng)建自己的迭代器

關(guān)于迭代器的定義

  template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,typename _Pointer = _Tp*, typename _Reference = _Tp&>struct iterator{/// One of the @link iterator_tags tag types@endlink.typedef _Category  iterator_category;/// The type "pointed to" by the iterator.typedef _Tp        value_type;/// Distance between iterators is represented as this type.typedef _Distance  difference_type;/// This type represents a pointer-to-value_type.typedef _Pointer   pointer;/// This type represents a reference-to-value_type.typedef _Reference reference;};
//創(chuàng)建自己的迭代器需要以上的類型說明

#ifndef __MY_ITERATOR__
#define __MY_ITERATOR__
#include <iostream>
#include<algorithm>
#include<functional>
#include<iterator>
#include<string>
#include<cctype>
using namespace std;
//這個(gè)程序可以在一個(gè)字符流上運(yùn)算，可以根據(jù)分割符來提取單詞 //判定字符是否為數(shù)字或者字母 
struct Isalpha : public unary_function<char, bool>{bool operator()(char c){return isalpha(c);}
};//分割符合的判定 
class Delimiters : public unary_function<char, bool>{
private:string exclude;
public:Delimiters(){}Delimiters(string excl) : exclude(excl){}bool operator()(char c){return exclude.find(c) == string::npos;}    
};//類型，函數(shù)對(duì)象 
template<class InputIter, class Pred = Isalpha>
class TokenIterator : public iterator<input_iterator_tag,string, ptrdiff_t>{
private:InputIter first;InputIter last;string word;Pred predicate;
public:TokenIterator(){}//End sentialTokenIterator(InputIter begin, InputIter end, Pred pred = Pred()) : first(begin), last(end), predicate(pred){}//i++TokenIterator& operator++(){word.resize(0);first = std::find_if(first, last, predicate);while(first != last && predicate(*first)){word += *first++;}return *this;}//new classclass CaptureState{private:string word;public:CaptureState(string& w): word(w){}string operator*(){    return word;}    };//++iCaptureState operator++(int){CaptureState d(word);++*this;return d;}//取值 string operator*() const{return word;}string* operator->()const{return &word;} //比較迭代器 --這里只關(guān)心是否到了迭代器的末尾bool operator==(const TokenIterator&){return word.size() == 0 && first == last;} bool operator!=(const TokenIterator& rv){return !(*this == rv);}
};
#endif

int main(int argc, char** argv){ifstream in("test.txt");assert(in != NULL);istreambuf_iterator<char> cBegin(in), end;Delimiters delimiters(" ,.\t\n\\?!");TokenIterator<istreambuf_iterator<char>, Delimiters> wordIter(cBegin, end, delimiters), tend;vector<string> v;copy(wordIter, tend, back_inserter(v));print(v.begin(), v.end(),"vector","\n");return 0;
}

以上程序?qū)嶋H上是做了一個(gè)單詞的讀取程序，test.txt文檔中讀取單詞，迭代器會(huì)自動(dòng)查詢delimiters對(duì)象，這個(gè)對(duì)象會(huì)存放固定的分隔符號(hào)，比如空格，讀取到這個(gè)分隔符，代表一個(gè)單詞就結(jié)束了，然后寫入word，然后插入vector中，vector負(fù)責(zé)存放單詞。

TokenIterator類是一個(gè)封裝好的迭代器，它的是從iterator類繼承而來，只使用了一個(gè)輸入迭代器，由于輸入迭代器沒有指示末尾的標(biāo)志，所以需要一個(gè)last迭代器來指示末尾

下面將要介紹適配器，適配器有stack, priority_queue, queue三種， 他們是通過調(diào)整某一適配器來符合自己的性質(zhì)，容器適配器不能使用迭代器進(jìn)行遍歷，因?yàn)檫@與他們的性質(zhì)不符。

5. 堆棧stack

stack適配器的默認(rèn)容器是deque,定義如下，這是直接復(fù)制粘貼的源代碼。

template<class T,class Container = std::deque<T>
> class stack;
template<typename _Tp, typename _Sequence = deque<_Tp> >class stack{// concept requirementstypedef typename _Sequence::value_type _Sequence_value_type;template<typename _Tp1, typename _Seq1>friend booloperator==(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);template<typename _Tp1, typename _Seq1>friend booloperator<(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);public:typedef typename _Sequence::value_type                value_type;typedef typename _Sequence::reference                 reference;typedef typename _Sequence::const_reference           const_reference;typedef typename _Sequence::size_type                 size_type;typedef          _Sequence                            container_type;protected://  See queue::c for notes on this name._Sequence c;public:explicitstack(const _Sequence& __c = _Sequence()): c(__c) { }explicitstack(_Sequence&& __c = _Sequence()): c(std::move(__c)) { }/***  Returns true if the %stack is empty.*/boolempty() const{ return c.empty(); }/**  Returns the number of elements in the %stack.  */size_typesize() const{ return c.size(); }/***  Returns a read/write reference to the data at the first*  element of the %stack.*/referencetop(){__glibcxx_requires_nonempty();return c.back();}/***  Returns a read-only (constant) reference to the data at the first*  element of the %stack.*/const_referencetop() const{return c.back();}/***  @brief  Add data to the top of the %stack.*  @param  __x  Data to be added.**  This is a typical %stack operation.  The function creates an*  element at the top of the %stack and assigns the given data*  to it.  The time complexity of the operation depends on the*  underlying sequence.*/voidpush(value_type&& __x){ c.push_back(std::move(__x)); }template<typename... _Args>voidemplace(_Args&&... __args){ c.emplace_back(std::forward<_Args>(__args)...); }/***  @brief  Removes first element.**  This is a typical %stack operation.  It shrinks the %stack*  by one.  The time complexity of the operation depends on the*  underlying sequence.**  Note that no data is returned, and if the first element's*  data is needed, it should be retrieved before pop() is*  called.*/void pop(){c.pop_back();}void swap(stack& __s){using std::swap;swap(c, __s.c);}};

它使用的方式是has-a，也就是內(nèi)部的容器定義為_Swqueue c;

可以使用一個(gè)容器對(duì)其初始化

我們也可以更改它的底層容器

固定需要的方法如下：

(1)T& top()獲取棧頂元素

(2)void pop() 彈出棧頂元素

(3)void push()向棧頂添加元素

(4)bool empty() 判斷是否為空

(5)int size() 返回元素個(gè)數(shù)

int buf[10] = {1,2,3,4,5,6,7,8,9,10};vector<int> v(begin(buf), end(buf));stack<int,vector<int>> s(v);while(!s.empty()){cout << s.top() << endl;s.pop();}

棧的概念就是先進(jìn)后出。所以對(duì)棧的操縱都是對(duì)棧頂?shù)牟僮?/p>

6.隊(duì)列 queue

隊(duì)列的除了行為和棧不一樣，實(shí)現(xiàn)方式其實(shí)和stack差不多，所以這里就不寫定義了。它默認(rèn)使用deque,一般來講，也不需要改變默認(rèn)容器

隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，其行為如下

(1)bool empty()判斷是否為空

(2)size_type size() 獲取元素?cái)?shù)量

(3)T& front() 獲取隊(duì)列首位的元素

(4)T& back()獲取隊(duì)列的末尾元素

(5)void push()入隊(duì)

(6)void swap()交換兩個(gè)序列

(7)void pop()刪除首個(gè)元素

7.優(yōu)先隊(duì)列 priority_queue

定義如下：

template<typename _Tp, typename _Sequence = vector<_Tp>,typename _Compare  = less<typename _Sequence::value_type> >class priority_queue；

其中的保護(hù)成員是：

protected:

_Sequence c;//優(yōu)先隊(duì)列使用的容器--我們可以通過公有繼承來獲取這個(gè)序列

_Compare comp;//優(yōu)先隊(duì)列使用的比較函數(shù)

以上是優(yōu)先隊(duì)列的定義，默認(rèn)容器是vector，默認(rèn)使用的比較函數(shù)對(duì)象是less<T>，所以默認(rèn)的優(yōu)先隊(duì)列是升序排列

內(nèi)部使用的底層算法全都是make_heap, push_heap,pop_heap;

優(yōu)先隊(duì)列實(shí)際上就是一個(gè)堆

常用的方法如下:

(1)bool empty()
(2)size_type size()
(3)const T& top()const 獲取堆頂?shù)脑?(4)void push() 插入堆
(5)void pop() 刪除堆頂?shù)脑?(5)void swap() 交換兩個(gè)隊(duì)列

需要注意的是，優(yōu)先隊(duì)列所比較函數(shù)的比較函數(shù)operator<在沒有默認(rèn)提供的前提下必須自己提供，

    int buf[10] = {1,2,3,4,5,6,7,8,9,10};priority_queue<int,vector<int>,greater<int>> q(begin(buf), end(buf));//修改比較函數(shù)，使其升序排列while(!q.empty()){cout << q.top() << endl;q.pop();}

接下來是直接輸出優(yōu)先隊(duì)列的容器內(nèi)容，這里我們使用公有繼承

template<typename Container>
void print(Container first, Container last, const string& title = "", const string& space = " "){if(title != "")cout << title << ":";while(first != last){cout << *first++ << space;}cout << endl;
}class Test_priority_queue: public priority_queue<int>{
public:vector<int>& getContainer(){return c;}
};int main(int argc, char** argv){int buf[10] = {1,2,3,4,5,6,7,8,9,10};Test_priority_queue testQ;for(int i =0 ; i < 10; i++){testQ.push(i);}vector<int> v = testQ.getContainer();print(begin(v), end(v));return 0;
}

8.持有二進(jìn)制位

C++提供了bitset和vector<bool>來表示二進(jìn)制，但是bitset和STL實(shí)際上沒有多大關(guān)系，和其他的STL組織方式相去甚遠(yuǎn)，只有vector<bool>是vector的一種特殊形式

8.1 bitset<n>

bitset模板接受一個(gè)無符號(hào)整型的參數(shù)，參數(shù)n用來表示二進(jìn)制的位數(shù)，另外參數(shù)不同就代表類型不同，兩者相當(dāng)于屬于不同的類。

將bitset轉(zhuǎn)換為整數(shù)的方法是to_ulong

超出設(shè)置范圍會(huì)拋出異常

(1)可以只含有01的字符串初始化,如果超出了范圍n，則只取前面的部分

(2)支持各種位移運(yùn)算，>> << | & ^~

移位運(yùn)算會(huì)補(bǔ)0

(3)bitset& set() 全部置為1， set(N)左邊第N位置位1

(4)bool test(n) 第n位如果置位了，則返回true

(5)flip() 反轉(zhuǎn)全部的位 flip(N)第N位反轉(zhuǎn)

(6)count 置位的位數(shù)

(7)none() 不存在置位的二進(jìn)制嗎？存在則返回0，不存在返回1

(8)any() 是否存在置位的二進(jìn)制

(9)all() 是否全置位

(10)operator[] 返回第N位的結(jié)果

constexpr int SZ = 32;
typedef bitset<SZ> BS;//產(chǎn)生隨機(jī)的32位bit 
template<int bit>
bitset<bit> randBitset(){bitset<bit> r(rand());for(int i = 0; i < bit/16-1; i++){r <<= 16;r |= bitset<bit>(rand());}return r;
}int main(int argc, char** argv){srand(time(NULL));cout << " sizeof(bitset<16>) " << sizeof(bitset<16>) << endl;//4cout << " sizeof(bitset<32>) " << sizeof(bitset<32>) << endl;//4cout << " sizeof(bitset<48>) " << sizeof(bitset<48>) << endl;//8cout << " sizeof(bitset<64>) " << sizeof(bitset<64>) << endl;//8cout << " sizeof(bitset<65>) " << sizeof(bitset<65>) << endl;//12//因?yàn)樽畹?個(gè)字節(jié)，一個(gè)字節(jié)8位BS a(randBitset<SZ>()), b(randBitset<SZ>());cout <<"a = " << a << endl;cout <<"b = " << b << endl;unsigned long ul = a.to_ulong();//轉(zhuǎn)化為整數(shù) cout << ul << endl;//用只含有01的字符串初始哈string cbits("0101");cout << BS(cbits) << endl;//不足32位則會(huì)補(bǔ)0cout << BS(cbits,0,3) << endl;//設(shè)置0-2位a>>=1;cout <<"右移一位 = "<< a <<endl; cout << "a.set() = " << a.set() << endl;//全部置為1 bitset<10> c;cout <<"c = " << c << endl;cout << "c.set(2) = " << c.set(2) << endl;cout << "c.test(2) =" << c.test(2) << " c.test(1) = "<< c.test(1) << endl;cout << " c.flip() = " << c.flip() << endl; cout << " ~c = " << ~c << endl;cout <<"c.count() = " <<c.count()<<endl;cout <<"c.any() = "<< c.any() << endl;cout <<"c.none() = " << c.none() << endl;cout << "c.reset() = " << c.reset() << endl;return 0;
}

8.2 vector<bool>

里面的內(nèi)容不是按字節(jié)存放的，而是按位存放，所以它的性質(zhì)與其他STL不相同，比如以下方式就無法用

T& r = vb.front();

T* = &vb[0];

因?yàn)樗祷氐氖且粋€(gè)二進(jìn)制的位，無法索引這個(gè)位置

它比普通的vector多一個(gè)flip函數(shù)。

建議不要使用這個(gè)東西

9.關(guān)聯(lián)容器

set， map, multiset， multimap被稱為關(guān)聯(lián)式容器，而set可以看作沒有關(guān)鍵字只有值的map

關(guān)聯(lián)式容器都有方法count(value),返回有多少個(gè)value，對(duì)于set和map會(huì)返回0或者1,但是杜宇multimap和multiset則會(huì)返回多個(gè)

set底層的數(shù)據(jù)結(jié)構(gòu)是平衡樹，根據(jù)它的定義我們知道，它的鍵與值是一樣的，所以也算是關(guān)聯(lián)容器

template<typename _Key, typename _Compare = std::less<_Key>,

typename _Alloc = std::allocator<_Key> >

class set{

public:

typedef _Key key_type;//鍵的類型

typedef _Key value_type;//值的類型--set的鍵和值的類型一樣

typedef _Compare key_compare;//鍵的比較函數(shù)

typedef _Compare value_compare;//值的比較函數(shù)--比較函數(shù)也是一樣的

typedef _Alloc allocator_type;//空間分配器

private://下面是空間分配的類型和性質(zhì)

typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template

rebind<_Key>::other _Key_alloc_type;

typedef _Rb_tree<key_type, value_type, _Identity<value_type>,

key_compare, _Key_alloc_type> _Rep_type;

_Rep_type _M_t; // Red-black tree representing set.--set的核心數(shù)據(jù)，一棵紅黑樹

typedef __gnu_cxx::__alloc_traits<_Key_alloc_type> _Alloc_traits;

......

}；

set和map都有insert方法。

而對(duì)于operator[],map如果使用這個(gè)方法的時(shí)候，超出范圍，則是在這里創(chuàng)建一個(gè)關(guān)聯(lián)值

#include<iostream>
#include<fstream>
#include<deque>
#include<vector>
#include<list>
#include<set> 
#include<cassert>
#include<stack>
#include<queue>
#include<map>
#include<functional>
#include"p4.h"
#include<bitset>
#include<ctime>
#include<cstdlib>
using namespace std;template<typename Container>
void print(Container first, Container last, const string& title = "", const string& space = " "){if(title != "")cout << title << ":";while(first != last){cout << *first++ << space;}cout << endl;
}class Noisy{
private:static long create, assign, copycons, destroy;long id;
public:Noisy(): id(create++){cout << "d[" << id << "]" << endl;}Noisy(const Noisy& rv): id(rv.id){cout << "c[" << id << "]" << endl;copycons++;}~Noisy(){cout << "~[" << id << "]" << endl;++destroy;}Noisy& operator=(const Noisy& rv){cout << "(" << id << ")=[" << rv.id << "]" << endl;id = rv.id;++assign;return *this;}friend bool operator<(const Noisy& lv, const Noisy& rv){return lv.id < rv.id;}friend bool operator>(const Noisy& lv, const Noisy& rv){return lv.id > rv.id;}friend bool operator==(const Noisy& lv, const Noisy& rv){return lv.id == rv.id;}friend ostream& operator<<(ostream& out, const Noisy& n){return out << n.id;}friend class NoisyReport;
};long Noisy::create = 0;
long Noisy::assign = 0;
long Noisy::copycons = 0;
long Noisy::destroy = 0;struct NoisyGen{Noisy operator()(){return Noisy();}
};class NoisyReport{static NoisyReport nr;NoisyReport(){}NoisyReport& operator=(NoisyReport&);NoisyReport(const NoisyReport&);
public:~NoisyReport(){cout <<"Noisy create:" << Noisy::create<<endl;cout <<"Noisy copy:" << Noisy::copycons<<endl;cout << "Noisy assignments: " << Noisy::assign << endl;cout << "Noisy Destroy:" << Noisy::destroy << endl;}        
};int main(int argc, char** argv){Noisy na[7];//構(gòu)造setset<Noisy> ns(na, na + sizeof(na)/sizeof(Noisy));Noisy n;//set插入一個(gè)新元素 ns.insert(n); //count查看某個(gè)元素存在多少個(gè) cout << "ns.count(n) = " << ns.count(n) << endl;//findif(ns.find(n) != ns.end()) cout << n <<  "存在" << endl;//打印全部元素copy(ns.begin(), ns.end(), ostream_iterator<Noisy>(cout," "));cout << endl;//map容器map<int,Noisy> nm;for(int i = 0; i < 10;i++){//自動(dòng)創(chuàng)建鍵值對(duì)nm[i]; }for(int i = 0; i < 10; i++){cout << "nm["<<i<<"]"<<nm[i] << endl;}//自動(dòng)創(chuàng)建一個(gè)鍵值對(duì)nm[10] = n;//插入一個(gè)鍵值對(duì) nm.insert(make_pair(47,n));//輸出map<int, Noisy>::iterator it;for(it = nm.begin(); it != nm.end(); ++it)cout << it->first << it->second << endl;return 0;
}

map和pair一樣有兩個(gè)迭代器，first指向鍵，second指向值

而map的insert返回一個(gè)pair迭代器，first指向被插入對(duì)的迭代器，second指向bool元素，如果插入成功，則bool值為真

9.1 對(duì)關(guān)聯(lián)式容器使用生成器和填充器

對(duì)于普通的填充器fill,fill_n,generate,generate_n，用在基本容器上有效，但是對(duì)于關(guān)聯(lián)式容器就無法使用了。這里就需要根據(jù)實(shí)際情況來構(gòu)造自己的生成器

比如下面的程序。實(shí)際上c++已經(jīng)有很多相近的方法了，可以使用類似的方式來

#include<iostream>
#include<deque>
#include<vector>
#include<list>
#include<set> 
#include<cassert>
#include<stack>
#include<queue>
#include<map>
#include<functional>
#include"p4.h"
#include<bitset>
#include<ctime>
#include<cstdlib>
using namespace std;int randInt(){int i = rand() %10;return i;
}//針對(duì)map容器的插入 
template<typename Assoc, typename Count, typename key_type, typename value_type>
void assocFill_n(Assoc& a, Count n, const key_type& key, const value_type& val){while(n > 0){a.insert(make_pair(key,val));--n;}
}//針對(duì)set容器的插入 
template<typename Assoc, typename Count, typename value_type>
void assocFill_n(Assoc& a, Count n, const value_type& val){while(n > 0){a.insert(val);--n;}
}int main(int argc, char** argv){int buf[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};vector<int> v(10);list<int> l(10);deque<int> d(10); srand(time(0));generate(begin(v), end(v), randInt); generate(begin(l), end(l), randInt); generate(begin(d), end(d), randInt); copy(begin(v), end(v), ostream_iterator<int>(cout," "));cout << endl;copy(begin(l), end(l), ostream_iterator<int>(cout," "));cout << endl;copy(begin(d), end(d), ostream_iterator<int>(cout," "));cout << endl;//上面是使用基本容器//但是使用關(guān)聯(lián)容器則是一個(gè)難點(diǎn) ，則需要自己定義類似得生成算法//但是，generate和fill這樣的算法是一種復(fù)制方法，對(duì)于關(guān)聯(lián)式容器沒有效果//可以使用類似generate_n和fill_n map<int, int> m;assocFill_n(m, 10, 10, 10);map<int, int>::iterator it = m.begin();for( ;it != m.end(); ++it){cout <<it->first  << " " << it->second << endl;}//同樣的方法可以用在set上 set<int> s;assocFill_n(s, 10, 7);copy(s.begin(), s.end(), ostream_iterator<int>(cout," "));return 0;
}

9.2多重映像和重復(fù)的關(guān)鍵字 multimap

這是一個(gè)包含重復(fù)關(guān)鍵字的關(guān)聯(lián)容器，這就好像身份證一樣，身份證號(hào)碼是唯一的，但是人名卻可以重復(fù)

//生成值
template <class Map_type, class Key_type, class Value_type>
void MapGenerate(Map_type& m,const Key_type* keyArr, const Value_type* valueArr, int n){while(n > 0){m.insert(pair<Key_type,Value_type>(keyArr[n-1],valueArr[n-1]));--n;}
}//輸出模板
template<class key_type, class  value_type>
void print(const pair<key_type, value_type>& p){cout << p.first << " " << p.second << endl;
}int main(int argc, char** argv){
//假設(shè)有這么幾個(gè)名字 string name[] = {"aaa", "bbb", "aaa", "aaa", "ccc","fff","ddd"};int number[] = {1,2,3,4,5,6,7};multimap<string, int> person;MapGenerate(person, name, number, 7);for_each(begin(person), end(person), print<string, int>);    //查找關(guān)鍵字--返回值是multimap指向開頭和末尾的迭代器 //而每一個(gè)map存儲(chǔ)的是一個(gè)pair<first,second>//所以返回值的first是一個(gè)map<pair,pair> typedef multimap<string, int>::iterator RangeIterator;pair<RangeIterator,RangeIterator> ptr = person.equal_range("aaa");auto it = ptr.first;while(it!= ptr.second){cout<< it->first << " " << it->second <<endl;it++;}}

對(duì)于multiset其實(shí)差不多，沒有什么好說的了

10 STL的擴(kuò)充

STL用其他方式實(shí)現(xiàn)了set,map 這是因?yàn)楝F(xiàn)在的set和map使用的是紅黑樹，查找方面已經(jīng)是對(duì)數(shù)級(jí)別的速度，但是仍然顯得不盡如人意，而使用hash算法，索引速度能達(dá)到常數(shù)級(jí)，

但是這種方式消耗的內(nèi)存要高于紅黑樹。hash算法實(shí)現(xiàn)的STL有hash_map, hash_set, hash_multiset, hash_multimao,slist(單鏈表), rope(這是一個(gè)string的變種，相當(dāng)于string的優(yōu)化)

11.非STL容器

前面說過的bitset就是一種非STL容器，另外還有valarray容器，這是一種類vector容器，非STL容器都不支持迭代器，這兩個(gè)容器的作用是對(duì)數(shù)值計(jì)算進(jìn)行的特化

#include <iostream>
#include <valarray>
#include <cstddef>using namespace std;template <class T>
void print(const valarray<T>& a, const string& s = ""){if(s != "")cout << s << ":";for(size_t i = 0; i < a.size(); ++i){cout << a[i] << " ";} cout << endl;
}double f(double x){return 2.0 * x - 1;}int main(){double n[] = {1.0, 2.0, 3.0, 4.0};valarray<double> v(n, sizeof(n)/sizeof(n[0]));//數(shù)組+數(shù)組數(shù)量初始化 print(v, "v");valarray<double> sh(v.shift(1));///左移動(dòng),空出來的位置補(bǔ)0，cshift是循環(huán)移動(dòng) print(sh,"sh");valarray<double> acc(v + sh);///維度相同的相加 print(acc,"acc");valarray<double> trig(sin(v) + sin(sh));//所有的數(shù)學(xué)函數(shù)和運(yùn)算符號(hào)都進(jìn)行了重載 print(trig, "trig");valarray<double> p(pow(v, 3.0));//同類型初始化 print(p, "p");valarray<double> app(v.apply(f));//apply調(diào)用函數(shù) print(app, "app");valarray<bool> eq(v == app);//比較返回一個(gè)結(jié)果數(shù)組 print(eq, "bool eq");double x = v.max();double y = v.min();double z = v.sum();cout << x << " " << y << " " << z << endl; return 0; 
}

切片

#include <iostream>
#include <valarray>
#include <cstddef>using namespace std;template <class T>
void print(const valarray<T>& a, const string& s = ""){if(s != "")cout << s << ":";for(size_t i = 0; i < a.size(); ++i){cout << a[i] << " ";} cout << endl;
}double f(double x){return 2.0 * x - 1;}int main(){int data[] = {1,2,3,4,5,6,7,8,9,10,11,12};valarray<int> v(data, 12); //數(shù)組初始化 print(v,"v");valarray<int> r(v[slice(0,4,3)]);//起點(diǎn)，個(gè)數(shù)，距離 print(r, "v[slice[0,4,3]");valarray<int> r2(v[v>6]);//只能用在初始化中 print(r2, "v>6");int buf[] = {1, 4, 7, 10};valarray<int> save(buf, 4);v[slice(0,4,3)] = save;print(v,"v");//valarray<size_t> siz(2);siz[0] = 2;siz[1] = 3;print(siz,"siz"); valarray<size_t> gap(2);gap[0] = 6;gap[1] = 2;print(gap,"gap"); //相當(dāng)于提取一個(gè)2D數(shù)組/**/ valarray<int> r3(v[gslice(0,siz,gap)]); print(r3,"v[gslice(0,siz,gap)");return 0; 
}