十堰網(wǎng)站建設(shè)費(fèi)用怎么給自己的公司做網(wǎng)站
容器簡介
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;
}