STL模板類總結(jié)
一 vector模板類
1 包含在頭文件vector中，內(nèi)部機(jī)理是使用動(dòng)態(tài)內(nèi)存分配。
2 如何定義vector類： vector<string> str(5)//vector<string>::vector(int n);
3 []操作賦被重載，所以可以這樣訪問(wèn)元素：str[n](n>=0 && n<5)。
4 vector模板類(包括STL模板)可以接受一個(gè)可選模板參數(shù)，該參數(shù)指定使用哪個(gè)分配器對(duì)象來(lái)管理內(nèi)存。
templae<class T, class Allocator=allocator<T> >
class vector{ ... } 此參數(shù)可以省略，則容器將默認(rèn)使用 allocator<T>類。這個(gè)類以標(biāo)準(zhǔn)方式使用new 和 delete.
5 size()方法，返回容器中元素?cái)?shù)目。
6 swap()方法，交換兩個(gè)容器的內(nèi)容。vetor<string> a,b;
a.swap(b);//交換a,b容器中的元素
7 begin() ,返回一個(gè)指向容器中第一個(gè)元素的迭代器；end(),返回超過(guò)容器尾的迭代器。
8 如何聲明及使用迭代器。 vector<double>::iterator pd;//將 pd 聲明為 vector 的 double 類型的迭代器
vector<double> scores
pd=scores.begin();
*pd=22.3;
++pd;
迭代器就像指針。
9 push_back()方法，將元素添加到矢量末尾，它負(fù)責(zé)內(nèi)存管理，比如增加矢量長(zhǎng)度，使之可以容納新的成員。
vector<double> scores;
double temp;
scores.push_back(temp);
10 erase()方法，刪除矢量中給定區(qū)間的元素，接受兩個(gè)迭代器參數(shù)，參數(shù)指出要?jiǎng)h除的區(qū)間。
erase(scores.begin(),scores.begin()+3);
11 insert()方法，與erase()功能相反。接受3個(gè)迭代器參數(shù)，第一個(gè)參數(shù)指定新元素的插入位置，第二，第三個(gè)迭代器指定了被插入?yún)^(qū)間。
vector<int> old;
vector<int> new;
old.insert(old.begin(),new.begin()+1,new.end());
12 for_each()函數(shù)，包括3個(gè)參數(shù)，前兩個(gè)定義要執(zhí)行的區(qū)間，最后一個(gè)是一個(gè)函數(shù)指針(函數(shù)對(duì)象)，被指向的函數(shù)不能修改容器元素的值。
如果ShowReview( *pr)為一個(gè)排序函數(shù)
vector<int>::iterator pr;
vector<int> books;
for_each(books.begin(),books.end(),ShowReview);將對(duì)books排序。
13 random_shuffle()函數(shù)接受兩個(gè)指定區(qū)間的迭代器參數(shù)，并對(duì)其隨機(jī)排列，該容器必須支持隨機(jī)訪問(wèn)。
random_shuffle(books.begin(),books.end());
14 sort()函數(shù)重載了兩個(gè)版本，但對(duì)迭代器類必須支持隨機(jī)訪問(wèn)。
一，接受兩個(gè)參數(shù)，這兩個(gè)參數(shù)是區(qū)間的迭代器，功能是對(duì)該區(qū)間的元素進(jìn)行升序排列。但是該容器類必須定義了operator<()函數(shù)。 vector<int>::operator<()const;
vector<int> vector_int;
sort(vector_int.begin(),vector_int.end()),將利用operator<()函數(shù)對(duì)其排序。
二，接受三個(gè)參數(shù)，前兩個(gè)參數(shù)表示區(qū)間的迭代器，第三個(gè)參數(shù)是一個(gè)函數(shù)指針(函數(shù)對(duì)象)，功能是用該函數(shù)指針指向的函數(shù)對(duì)區(qū)間元素進(jìn)行的操作.
struct Review
{
string title;
int rating;
}
bool WorseThan(const Review & r1,const Review &r2)
{
if(r1.rating<r2.rating)
return true;
else
return false;
}
vector<Review> books;
sort(books.begin(),books.end(),WorseThan);將按WorseThan機(jī)制對(duì)books排序。
二 迭代器類型(從程序的角度來(lái)說(shuō)的)
1輸入迭代器：對(duì)程序的輸入，對(duì)容器其實(shí)是輸出。該迭代器重載了*(解除引用操作符),++(遞增操作符)。輸入迭代器必須能夠訪問(wèn)容器中的值。(注意：并不能保證輸入迭代器第二次遍歷容器時(shí)，順序不變。另外，輸入迭代器被遞增后，也不能保證其先前的值仍然可以被解除引用，對(duì)輸入迭代器的任何算法都應(yīng)當(dāng)是單通行的，不依賴前一次遍歷時(shí)的迭代器值，也不依賴于本次遍歷中的前面的迭代器的值，輸入迭代器是單向的，可以遞增，不能倒退)
2 輸出迭代器：對(duì)容器是輸入，操作符同輸入迭代器。解除引用讓程序能修改容器值，而不能讀取。單通行的。
3 正向迭代器：使用++操作符來(lái)遍歷容器，它總是按相同的順序遍歷一系列值。將正向迭代器遞增后，仍然可以對(duì)前面的迭代器解除引用(如果保存了它) ，并可以得到相同的值。正向迭代器既可以讀取和修改數(shù)據(jù)，也可以只能讀取數(shù)據(jù)。
int *pirw; 既可以讀也可以寫
const int *pir;只能讀
4 雙向迭代器：能夠雙向遍歷容器，具有正向迭代器的特征，支持前綴和后綴的遞增，遞減操作符。
5 隨機(jī)訪問(wèn)迭代器，具有雙向迭代器的特征，以下是除雙向迭代器具有的特征之外的特征：
a和b是迭代器值，n為整數(shù)，r為隨機(jī)迭代器變量或引用
a+n,n+a等效(a+n<=a.end())
a-n;r+=n;r-=n;a[n]
b-a為b=a+n中的n值
a<b;a>b;a<=b;a>=b;
三 STL的改進(jìn)和模型
1 將指針用做迭代器：STL算法可用于普通指針。比如可以將sort函數(shù)用于數(shù)組：int a[5]; sort(a,a+4),對(duì)該數(shù)組排序。
2 copy()函數(shù)，3個(gè)參數(shù)，前兩個(gè)表示要復(fù)制的范圍，最后一個(gè)表示要復(fù)制的位置。前兩個(gè)參數(shù)必須是輸入迭代器，最后一個(gè)參數(shù)必須是輸出迭代器。copy()函數(shù)可以覆蓋目標(biāo)容器中已有的數(shù)據(jù)，同時(shí)目標(biāo)容器必須足夠大，能夠容納被復(fù)制的元素。
3 ostream_iterator模板，輸出迭代器的一個(gè)模型，也是適配器，該模板有兩個(gè)參數(shù)。
#include<iterator>
ostream_iterator<int,char> out_iter(cout," ");
out_iter是一個(gè)接口，能夠使用cout來(lái)顯示信息，模板第一個(gè)參數(shù)int指出被發(fā)送給輸出流的數(shù)據(jù)類型，第二個(gè)參數(shù)(char)，指出了輸出流使用的字符類型。構(gòu)造函數(shù)的第一個(gè)參數(shù)，指出要使用的輸出流，第二個(gè)字符串參數(shù)是在發(fā)送給輸出流的每個(gè)數(shù)據(jù)項(xiàng)后顯示的分隔符。 *out_iter++=15; //works like cout<< 15 <<" ";
vector<int> books;
copy(books.begin(),books.end(),out_iter);
4 istream_iterator模板，與ostream_iterator模板類似。
#include<iterator>
istream_iterator<int,char> in_iter(cin,"");模板第一個(gè)參數(shù)指出要輸入的類型，第二個(gè)參數(shù)指出輸入流使用的字符類型，用法同ostream_iterator.構(gòu)造函數(shù)如果省略第二個(gè)參數(shù)，表示從輸入流中讀取，直到文件尾，類型不匹配或出現(xiàn)其他輸入故障為止。
5 reverse_iterator迭代器，對(duì)其執(zhí)行遞增操作將導(dǎo)致被遞減。rbegin()和rend()，前者返回指向超尾的反向迭代器，后者返回指向第一個(gè)元素的反向迭代器，執(zhí)行遞增將被遞減。
ostream_iterator<int,char> out_iter(cout,‘ ‘);
vector<int> dice;
copy(dice.rbegin(),dice.rend(),out);反向輸出dice容器中的元素。
不能對(duì)rbegin()進(jìn)行解除引用。因?yàn)樗赶虺病?br> vector<int>::reverse_iterator rp;
如果rp指向位置6,則*rp為位置5的值。（先遞減，在解除引用）
for(rp=dice.rbegin();rp!=dice.rend();rp++)
cout<<*rp; 反向輸出元素
6 back_insert_iterator,front_insert_iterator,insert_iterator(都使用動(dòng)態(tài)內(nèi)存分配),將元素插入到容器,將復(fù)制轉(zhuǎn)換為插入算法，插入算法比復(fù)制速度快。
back_insert_iterator<vector<int> > back_iter(dice)；
vector<int> book;
copy(book.begin(),book.end(),back_iter); 插入到dice的尾部。
copy(book.begin(),book.end(),insert_iterator<vector<int>>(dice,dice.begin()+1);插入到dice.begin()+1之前。
三 序列容器：元素按特定順序排列，元素按嚴(yán)格的線性順序排列
（一）vector:vector頭文件中聲明的,是數(shù)組的一種表示法，提供自動(dòng)內(nèi)存管理，可以動(dòng)態(tài)改變vector對(duì)象的長(zhǎng)度，提供了元素的隨機(jī)訪問(wèn)，在尾部添加和刪除元素的時(shí)間是固定的，但在中間或頭部插入元素時(shí)間是線性的，vector強(qiáng)調(diào)快速訪問(wèn)。
1 是一個(gè)可反轉(zhuǎn)容器，rbegin(),rend()方法，for_each(dice.rbegin,dice.rend(),Show)，如果Show為顯示函數(shù)，則反向顯示dice容器中的元素。（reverse_iterator)
（二）deque(double-ended queue，雙端隊(duì)列):deque頭文件中聲明，支持隨機(jī)訪問(wèn)。從deque對(duì)象的兩端插入和刪除元素時(shí)間是固定的，中部為線性時(shí)間（但是vector執(zhí)行速度快）
（三）list（雙向鏈表）：list頭文件中聲明，可以雙向遍歷鏈表，在任意位置插入和刪除時(shí)間是固定的，list強(qiáng)調(diào)元素的快速插入和刪除。list是可反轉(zhuǎn)容器，不支持?jǐn)?shù)組表示法和隨機(jī)訪問(wèn)。與其他不同的是：從容器中插入和刪除元素之后，鏈表迭代器指向的元素不變。它是通過(guò)修改鏈表信息，使指向某個(gè)元素的迭代器任指向該元素，但它鏈表的元素可能與以前不同。以下是鏈表專用的成員函數(shù)：
1 void merge(list<T,Alloc> &x) 將鏈表x與調(diào)用鏈表合并，兩個(gè)鏈表必須已經(jīng)排序，合并后，x為空，線性時(shí)間。
2 void remove(const T & val) 從鏈表中刪除val的所有實(shí)例，線性時(shí)間。
3 sort()，使用<操作符對(duì)鏈表進(jìn)行排序；n個(gè)元素的復(fù)雜度為n*log(n).
4 void splice(iterator pos,list<T,Alloc>x)，將鏈表x的內(nèi)容插入到pos前面，x為空，固定時(shí)間。
5 void unique()，將連續(xù)的相同元素壓縮為單個(gè)單元，線性時(shí)間。
（四） queue(適配器模板類，在queue頭文件聲明)，不允許隨機(jī)訪問(wèn)，甚至不允許遍歷隊(duì)列。使用限制在定義隊(duì)列的基本操作上，可以將元素添加到對(duì)尾，從對(duì)首刪除元素，查看對(duì)首和對(duì)尾的值，檢查元素?cái)?shù)目和測(cè)試隊(duì)列是否為空。
1 bool empty()const
2 size_type size()const
3 T& front()
4 T& back()
5 void push(const T&x)，在對(duì)尾插入x
6 void pop()，刪除對(duì)首元素
（五） priority_queue （在queue頭文件中聲明，適配器模板類），最大元素被移到對(duì)首，默認(rèn)底層類是vector，可以修改用于確定哪個(gè)元素放到對(duì)首的比較方式，提供一個(gè)可選構(gòu)造函數(shù)參數(shù)即可。
priority_queue<int> pq1;
priority_queue<int> pq2 (greater<int>);使用greater<int>函數(shù)機(jī)制來(lái)確定。
（六） stack(在stack頭文件中聲明，適配器模板類），不允許隨機(jī)訪問(wèn)，甚至不允許遍歷堆棧，使用限制在定義堆棧的基本操作上。
1 bool empty()const
2 size_type size()const
3 T& top(),返回指向棧頂元素的引用
4 void push(const T&x) ,在堆棧頂部插入x
5 void pop(),刪除堆棧頂部元素。
四 聯(lián)合容器：允許插入新元素，不過(guò)不能指定元素的插入位置,將關(guān)鍵字看作常量，聯(lián)合容器通常包含用于確定數(shù)據(jù)放置位置的算法，以便能很快檢索信息.(set,multiset,map,multimap)
（一）set:值的類型與關(guān)鍵字相同，關(guān)鍵字是唯一的，一個(gè)聯(lián)合集合，可反轉(zhuǎn)，可排序，關(guān)鍵字是唯一的，所以只能存儲(chǔ)同一種類型的值。
set<string> A;
set<string,less<string> > B;第二個(gè)參數(shù)可選，第二個(gè)參數(shù)用來(lái)對(duì)關(guān)鍵字進(jìn)行排序的比較函數(shù)或?qū)ο竽J(rèn)是（less<string> >）。
const int N=6;
string s1[N]={"buffoon","thinkers","for","heave","can","for"};
set<string> A(s1,s1+N);因?yàn)橛袃蓚€(gè)for,所以只有5個(gè)元素
ostream_iterator<string,char> out (cout,‘ ‘);
copy(A.begin(),A.end(),out);輸出結(jié)果為：buffoon can for heavy thinkers 由于關(guān)鍵字是唯一的，集合被排序，for也只出現(xiàn)一次。
1 set_union()函數(shù)(并集)，接受5個(gè)迭代器參數(shù)，前兩個(gè)迭代器定義了一個(gè)集合的區(qū)間，接下來(lái)的兩個(gè)參數(shù)定義了第二個(gè)集合的區(qū)間，最后一個(gè)迭代器是輸出迭代器，指出結(jié)果復(fù)制到什么位置。
set_union(A.begin(),A.end(),B.begin(),B.end(),ostream_iterator<string,char> out (cout,""));顯示A與B的并集
set<string> c;
set_union(A.begin(),A.end(),B.begin(),B.end(),insert_iterator<set<string>> (c,c.begin() ) );把A與B的并集放到C中
2 set_intersection()函數(shù)，查找交集，接口與set_union()相同。
3 set_difference()函數(shù)，獲得兩個(gè)集合的差，接口同set_union()。兩個(gè)集合的差是第一個(gè)集合減去兩個(gè)集合公有的元素。
4 lower_bound()函數(shù)，將關(guān)鍵字作為參數(shù)，并返回一個(gè)迭代器，該迭代器指向集合中第一個(gè)小于關(guān)鍵字參數(shù)的成員。
5 upper_bound()函數(shù)，返回第一個(gè)大于關(guān)鍵字參數(shù)的成員。
6 insert()函數(shù) string s("tennis");
A.insert(s);
B.insert(A.begin(),A.end());因?yàn)榕判驔Q定了插入位置，所以這種類包含只指定要插入 的信息，而不指定位置。
（二）multimap:可反轉(zhuǎn)，經(jīng)過(guò)排序的聯(lián)合容器，關(guān)鍵字類型與值類型不同，聲明方式如下：
multimap<int,string>codes;第一個(gè)模板參數(shù)指出關(guān)鍵字類型，第二個(gè)模板參數(shù)表明存儲(chǔ)類型。還有一個(gè)可選的模板參數(shù)，指出用于對(duì)關(guān)鍵字進(jìn)行排序的比較函數(shù)或?qū)ο?，默認(rèn)使用less<>模板，該模板將關(guān)鍵字作為參數(shù)。
pair<const int,string> item (213,"Los Angeles");
codes.insert(item);將按關(guān)鍵字類型 int排序插入到codes中。
或者：codes.insert(pair<const int,string> (213,"Los Angeles"));
1 count()成員函數(shù)用關(guān)鍵字作為參數(shù)，返回具有該關(guān)鍵字元素的數(shù)目。
2 lower_bound(),upper_bound()，同set中的。
3 equal_range()函數(shù)，用關(guān)鍵字作為參數(shù)，返回表示與該關(guān)鍵字匹配的區(qū)間的迭代器(區(qū)間)
pair<multimap<int, string>::iterator,multimap<int,string>::iterator> range=codes.equal_range(718);
cout << "Cities with area code 718: \n";
for(it=range.first;it!=range.second; ++i)
cout<<(*it).second <<endl;//first是關(guān)鍵字成員名，second是模板第二個(gè)參數(shù)成員名。
五 函數(shù)對(duì)象 :函數(shù)符，可以是函數(shù)方式或重載了()操作符的類對(duì)象
（一）函數(shù)符概念：1 生成器（generator)是不用參數(shù)就可以調(diào)用的函數(shù)符。
2 一元函數(shù)（unary function）是用一個(gè)參數(shù)可以調(diào)用的函數(shù)符。
3 二元函數(shù)（binary function)是用兩個(gè)參數(shù)可以調(diào)用的函數(shù)符。
4 返回bool值的一元函數(shù)是斷言(predicate).
5 返回bool值的二元函數(shù)是二元斷言(binary predicate).
list 模板有一個(gè)將斷言作為參數(shù)的 remove_if()成員，該函數(shù)將斷言應(yīng)用于區(qū)間中的每個(gè)元素，如果斷言為true,則刪除該元素。
bool tooBig(int n){return n>100;}
list<int> scores;
scores.remove_if(tooBigs); 將刪除 scores中大于100的元素。
程序清單16.13 functor.cpp
#include<iostream>
#include<list>
#include<iterator>
template<class T>
class TooBig
{
private:
T cutoff;
public:
TooBig(const T &t):cutoff(t){}
bool operator()(const T &v){return v>cutoff;}
};
int main()
{
using namespace std;
TooBig<int> f100(100);
list<int> yadayada;
list<int> etcetera;
int vals[10] = {50,100,90,180,60,210,415,88,188,201};
yadayada.insert(yadayada.begin(),vals,vals + 10);
etcetera.insert(etcetera.begin(),vals,vals + 10);
ostream_iterator<int, char> out(cout," ");
cout << "Original lists:\n";
copy(yadayada.begin(),yadayada.end(), out);
cout<<endl;
copy(etcetera.begin(), etcetera.end(), out);
cout<<endl;
yadayada.remove_if(f100);//刪除大于100的元素。
etcetera.remove_if(TooBig<int> (200));//刪除大于200的元素。
cout<< "Trivved lists:\n";
copy(yadayada.begin(),yadayada.end(), out);
cout<<endl;
copy(etcetera.begin(),etcetera.end(),out);
cout<<endl;
return 0;
}
（二）預(yù)定義的函數(shù)符
函數(shù)：transform()
第一版本：接受4個(gè)參數(shù)，前兩個(gè)參數(shù)指定容器區(qū)間的迭代器，第3個(gè)參數(shù)指定將結(jié)果復(fù)制到哪里的迭代器，最后一個(gè)參數(shù)是一個(gè)函數(shù)符，它被應(yīng)用與區(qū)間中的每個(gè)元素，生成結(jié)果中的新元素。
第二版本：接受5個(gè)參數(shù)，前兩個(gè)參數(shù)指定第一容器區(qū)間的迭代器，第3個(gè)參數(shù)指定第二個(gè)容器區(qū)間的起始位置，第4個(gè)參數(shù)指定將結(jié)果復(fù)制到哪里，最后一個(gè)參數(shù)是一個(gè)函數(shù)符號(hào)，它被應(yīng)用與兩個(gè)區(qū)間中的每個(gè)元素。
#include<functional>
plus<double> add;
transform(gr8.begin(),gr8.end(),m8.begin(),out,plus<double>());//將gr8和m8中的元素分別相加，將結(jié)果輸出。
操作符和相應(yīng)的函數(shù)符:在 functional 頭文件中
+ plus > greater
- minus < less
* multiplies >= greater_equal
/ divides <= less_equal
% modulus && logical_and
== equal_to
- negate || logical_or
!= not_equal_to ! logical_not
（三） 自適應(yīng)函數(shù)符和函數(shù)適配器
transform(gr8.begin(),gr8.end(),out,bind1st(multiplies<double>(),2.5)//將gr8中的每個(gè)元素乘以2.5，multiplies<double>()是二 元函數(shù)。(bind1s 和 bind2nd 用法相同)
六 算法
（一） algorithm 頭文件中描述的：非修改式序列操作。
修改式序列操作。
排序和相關(guān)操作。
numeric 頭文件中描述的 ：通用數(shù)字運(yùn)算。
（二） STL 和 string 類
包含begin(),end(),rbegin(),rend()等成員，可以使用STL接口。
函數(shù)next_permutation()算法將區(qū)間內(nèi)容轉(zhuǎn)換為下一種排列方式。對(duì)于字符串，排列按照字母遞增順序進(jìn)行，如果成功，返回 true,如果區(qū)間已經(jīng)處于最后序列中，返回 false.
（三） 函數(shù)和容器方法
一般STL方法比STL函數(shù)好，因?yàn)榭梢允褂媚０孱惖膬?nèi)存管理工具，可以自己調(diào)整容器長(zhǎng)度，但STL函數(shù)可以用于數(shù)組，string類，STL容器。
list<int> la;
la.remove(4);//刪除所有為4的元素，自動(dòng)減小容器長(zhǎng)度。
remove(la.begin(),lb.end(),4);//刪除所有為4的元素，將沒(méi)被刪除的排在容器前面，返回一個(gè)指向新的超尾值的迭代器，鏈表長(zhǎng)度不變
七 其他庫(kù)
vector,valarray,都是數(shù)組模板。vector模板類支持面向容器的操作，如排序，插入，重新排列，搜索，將數(shù)據(jù)移到其他容器中等； valarray類模板是面向數(shù)值計(jì)算的，不是STL的一部分，比如，沒(méi)有 push_back(),insert()等等。
valarray 重載了運(yùn)算符。
valarray<double> vad1(10),vad2(10),vad3(10);
vector<double> ved1(10),ved2(10),ved3(10);
vad3=vad1+vad2;//將對(duì)應(yīng)的元素相加
vad3=vad1*vad2;//將對(duì)應(yīng)元素相乘
vad3/=vad1; //重載了/=操作符
transform(ved1.begin(),ved1.end(),ved2.begin(),ved3.begin(),plus<double>());
transform(ved3.begin(),ved3.end(),ved3.begin(),bind1st(multiplies<double>(),2.5));//將ved3中每個(gè)元素乘以2.5
valarray沒(méi)有插入，排序，搜索等方法，有resize()方法，但不能自動(dòng)調(diào)整valarray的大小。sort()函數(shù)用作valarray需要注意。
valarray<double> vad(10);
sort(vad,vad+10);//錯(cuò)誤的，因?yàn)関ad不是數(shù)組名，不能代表地址。
sort(&vad[0],&vad[10]);//錯(cuò)誤的，因?yàn)関ad[10]是不確定的。
sort(&vad[0],&vad[9]);
slice對(duì)象可用做數(shù)組索引，被初始化為3個(gè)整數(shù)值：起始索引，索引數(shù)和跨距。起始索引是第一個(gè)被選中的元素的索引，索引數(shù)指出要選擇多少個(gè)元素，跨距表示元素之間的間隔。
valarray<int> varint;
varint[slice(1,4,3)]=10;//varint[1]=10,varint[4]=10,varint[7]=10,varint[10]=10；
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1594983
聯(lián)系客服
