STL模板類總結(jié)
一 vector模板類
1 包含在頭文件vector中，內(nèi)部機理是使用動態(tài)內(nèi)存分配。
2 如何定義vector類： vector<string> str(5)//vector<string>::vector(int n);
3 []操作賦被重載，所以可以這樣訪問元素：str[n](n>=0 && n<5)。
4 vector模板類(包括STL模板)可以接受一個可選模板參數(shù)，該參數(shù)指定使用哪個分配器對象來管理內(nèi)存。
templae<class T, class Allocator=allocator<T> >
class vector{ ... } 此參數(shù)可以省略，則容器將默認使用 allocator<T>類。這個類以標準方式使用new 和 delete.
5 size()方法，返回容器中元素數(shù)目。
6 swap()方法，交換兩個容器的內(nèi)容。vetor<string> a,b;
a.swap(b);//交換a,b容器中的元素
7 begin() ,返回一個指向容器中第一個元素的迭代器；end(),返回超過容器尾的迭代器。
8 如何聲明及使用迭代器。 vector<double>::iterator pd;//將 pd 聲明為 vector 的 double 類型的迭代器
vector<double> scores
pd=scores.begin();
*pd=22.3;
++pd;
迭代器就像指針。
9 push_back()方法，將元素添加到矢量末尾，它負責內(nèi)存管理，比如增加矢量長度，使之可以容納新的成員。
vector<double> scores;
double temp;
scores.push_back(temp);
10 erase()方法，刪除矢量中給定區(qū)間的元素，接受兩個迭代器參數(shù)，參數(shù)指出要刪除的區(qū)間。
erase(scores.begin(),scores.begin()+3);
11 insert()方法，與erase()功能相反。接受3個迭代器參數(shù)，第一個參數(shù)指定新元素的插入位置，第二，第三個迭代器指定了被插入?yún)^(qū)間。
vector<int> old;
vector<int> new;
old.insert(old.begin(),new.begin()+1,new.end());
12 for_each()函數(shù)，包括3個參數(shù)，前兩個定義要執(zhí)行的區(qū)間，最后一個是一個函數(shù)指針(函數(shù)對象)，被指向的函數(shù)不能修改容器元素的值。
如果ShowReview( *pr)為一個排序函數(shù)
vector<int>::iterator pr;
vector<int> books;
for_each(books.begin(),books.end(),ShowReview);將對books排序。
13 random_shuffle()函數(shù)接受兩個指定區(qū)間的迭代器參數(shù)，并對其隨機排列，該容器必須支持隨機訪問。
random_shuffle(books.begin(),books.end());
14 sort()函數(shù)重載了兩個版本，但對迭代器類必須支持隨機訪問。
一，接受兩個參數(shù)，這兩個參數(shù)是區(qū)間的迭代器，功能是對該區(qū)間的元素進行升序排列。但是該容器類必須定義了operator<()函數(shù)。
vector<int>::operator<()const;
vector<int> vector_int;
sort(vector_int.begin(),vector_int.end()),將利用operator<()函數(shù)對其排序。
二，接受三個參數(shù)，前兩個參數(shù)表示區(qū)間的迭代器，第三個參數(shù)是一個函數(shù)指針(函數(shù)對象)，功能是用該函數(shù)指針指向的函數(shù)對區(qū)間元素進行的操作.
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機制對books排序。
二 迭代器類型(從程序的角度來說的)
1
輸入迭代器：對程序的輸入，對容器其實是輸出。該迭代器重載了
*(解除引用操作符),++(遞增操作符)。輸入迭代器必須能夠訪問容器中的值。(注意：并不能保證輸入迭代器第二次遍歷容器時，順序不變。另外，輸入迭
代器被遞增后，也不能保證其先前的值仍然可以被解除引用，對輸入迭代器的任何算法都應當是單通行的，不依賴前一次遍歷時的迭代器值，也不依賴于本次遍歷中
的前面的迭代器的值，輸入迭代器是單向的，可以遞增，不能倒退)
2 輸出迭代器：對容器是輸入，操作符同輸入迭代器。解除引用讓程序能修改容器值，而不能讀取。單通行的。
3 正向迭代器：使用++操作符來遍歷容器，它總是按相同的順序遍歷一系列值。將正向迭代器遞增后，仍然可以對前面的迭代器解除引用(如果保存了它) ，并可以得到相同的值。正向迭代器既可以讀取和修改數(shù)據(jù)，也可以只能讀取數(shù)據(jù)。
int *pirw; 既可以讀也可以寫
const int *pir;只能讀
4 雙向迭代器：能夠雙向遍歷容器，具有正向迭代器的特征，支持前綴和后綴的遞增，遞減操作符。
5 隨機訪問迭代器，具有雙向迭代器的特征，以下是除雙向迭代器具有的特征之外的特征：
a和b是迭代器值，n為整數(shù)，r為隨機迭代器變量或引用
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的改進和模型
1 將指針用做迭代器：STL算法可用于普通指針。比如可以將sort函數(shù)用于數(shù)組：int a[5]; sort(a,a+4),對該數(shù)組排序。
2 copy()函數(shù)，3個參數(shù)，前兩個表示要復制的范圍，最后一個表示要復制的位置。前兩個參數(shù)必須是輸入迭代器，最后一個參數(shù)必須是輸出迭代器。copy()函數(shù)可以覆蓋目標容器中已有的數(shù)據(jù)，同時目標容器必須足夠大，能夠容納被復制的元素。
3 ostream_iterator模板，輸出迭代器的一個模型，也是適配器，該模板有兩個參數(shù)。
#include<iterator>
ostream_iterator<int,char> out_iter(cout," ");
out_iter是一個接口，能夠使用cout來顯示信息，模板第一個參數(shù)int指出被發(fā)送給輸出流的數(shù)據(jù)類型，第二個參數(shù)(char)，指出了輸出流使
用的字符類型。構(gòu)造函數(shù)的第一個參數(shù)，指出要使用的輸出流，第二個字符串參數(shù)是在發(fā)送給輸出流的每個數(shù)據(jù)項后顯示的分隔符。
*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,"
");模板第一個參數(shù)指出要輸入的類型，第二個參數(shù)指出輸入流使用的字符類型，用法同ostream_iterator.構(gòu)造函數(shù)如果省略第二個參數(shù)，表
示從輸入流中讀取，直到文件尾，類型不匹配或出現(xiàn)其他輸入故障為止。
5 reverse_iterator迭代器，對其執(zhí)行遞增操作將導致被遞減。rbegin()和rend()，前者返回指向超尾的反向迭代器，后者返回指向第一個元素的反向迭代器，執(zhí)行遞增將被遞減。
ostream_iterator<int,char> out_iter(cout,‘ ‘);
vector<int> dice;
copy(dice.rbegin(),dice.rend(),out);反向輸出dice容器中的元素。
不能對rbegin()進行解除引用。因為它指向超尾。
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(都使用動態(tài)內(nèi)存分配),將元素插入到容器,將復制轉(zhuǎn)換為插入算法，插入算法比復制速度快。
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之前。
三 序列容器：元素按特定順序排列，元素按嚴格的線性順序排列
（一）vector:vector頭文件中聲明的,是數(shù)組的一種表示法，提供自動內(nèi)存管理，可以動態(tài)改變vector對象的長度，提供了元素的隨機訪問，在尾部添加和刪除元素的時間是固定的，但在中間或頭部插入元素時間是線性的，vector強調(diào)快速訪問。
1 是一個可反轉(zhuǎn)容器，rbegin(),rend()方法，for_each(dice.rbegin,dice.rend(),Show)，如果Show為顯示函數(shù)，則反向顯示dice容器中的元素。（reverse_iterator)
（二）deque(double-ended queue，雙端隊列):deque頭文件中聲明，支持隨機訪問。從deque對象的兩端插入和刪除元素時間是固定的，中部為線性時間（但是vector執(zhí)行速度快）
（三）
list（雙向鏈表）：list頭文件中聲明，可以雙向遍歷鏈表，在任意位置插入和刪除時間是固定的，list強調(diào)元素的快速插入和刪除。list是可反
轉(zhuǎn)容器，不支持數(shù)組表示法和隨機訪問。與其他不同的是：從容器中插入和刪除元素之后，鏈表迭代器指向的元素不變。它是通過修改鏈表信息，使指向某個元素的
迭代器任指向該元素，但它鏈表的元素可能與以前不同。以下是鏈表專用的成員函數(shù)：
1 void merge(list<T,Alloc> &x) 將鏈表x與調(diào)用鏈表合并，兩個鏈表必須已經(jīng)排序，合并后，x為空，線性時間。
2 void remove(const T & val) 從鏈表中刪除val的所有實例，線性時間。
3 sort()，使用<操作符對鏈表進行排序；n個元素的復雜度為n*log(n).
4 void splice(iterator pos,list<T,Alloc>x)，將鏈表x的內(nèi)容插入到pos前面，x為空，固定時間。
5 void unique()，將連續(xù)的相同元素壓縮為單個單元，線性時間。
（四） queue(適配器模板類，在queue頭文件聲明)，不允許隨機訪問，甚至不允許遍歷隊列。使用限制在定義隊列的基本操作上，可以將元素添加到對尾，從對首刪除元素，查看對首和對尾的值，檢查元素數(shù)目和測試隊列是否為空。
1 bool empty()const
2 size_type size()const
3 T& front()
4 T& back()
5 void push(const T&x)，在對尾插入x
6 void pop()，刪除對首元素
（五） priority_queue （在queue頭文件中聲明，適配器模板類），最大元素被移到對首，默認底層類是vector，可以修改用于確定哪個元素放到對首的比較方式，提供一個可選構(gòu)造函數(shù)參數(shù)即可。
priority_queue<int> pq1;
priority_queue<int> pq2 (greater<int>);使用greater<int>函數(shù)機制來確定。
（六） stack(在stack頭文件中聲明，適配器模板類），不允許隨機訪問，甚至不允許遍歷堆棧，使用限制在定義堆棧的基本操作上。
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ān)鍵字看作常量，聯(lián)合容器通常包含用于確定數(shù)據(jù)放置位置的算法，以便能很快檢索信息.(set,multiset,map,multimap)
（一）set:值的類型與關(guān)鍵字相同，關(guān)鍵字是唯一的，一個聯(lián)合集合，可反轉(zhuǎn)，可排序，關(guān)鍵字是唯一的，所以只能存儲同一種類型的值。
set<string> A;
set<string,less<string> > B;第二個參數(shù)可選，第二個參數(shù)用來對關(guān)鍵字進行排序的比較函數(shù)或?qū)ο竽J是（less<string> >）。
const int N=6;
string s1[N]={"buffoon","thinkers","for","heave","can","for"};
set<string> A(s1,s1+N);因為有兩個for,所以只有5個元素
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個迭代器參數(shù)，前兩個迭代器定義了一個集合的區(qū)間，接下來的兩個參數(shù)定義了第二個集合的區(qū)間，最后一個迭代器是輸出迭代器，指出結(jié)果復制到什么位置。
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ù)，獲得兩個集合的差，接口同set_union()。兩個集合的差是第一個集合減去兩個集合公有的元素。
4 lower_bound()函數(shù)，將關(guān)鍵字作為參數(shù)，并返回一個迭代器，該迭代器指向集合中第一個小于關(guān)鍵字參數(shù)的成員。
5 upper_bound()函數(shù)，返回第一個大于關(guān)鍵字參數(shù)的成員。
6 insert()函數(shù) string s("tennis");
A.insert(s);
B.insert(A.begin(),A.end());因為排序決定了插入位置，所以這種類包含只指定要插入
的信息，而不指定位置。
（二）multimap:可反轉(zhuǎn)，經(jīng)過排序的聯(lián)合容器，關(guān)鍵字類型與值類型不同，聲明方式如下：
multimap<int,string>
codes;第一個模板參數(shù)指出關(guān)鍵字類型，第二個模板參數(shù)表明存儲類型。還有一個可選的模板參數(shù)，指出用于對關(guān)鍵字進行排序的比較函數(shù)或?qū)ο?，默認使用
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是模板第二個參數(shù)成員名。
五 函數(shù)對象 :函數(shù)符，可以是函數(shù)方式或重載了()操作符的類對象
（一）函數(shù)符概念：1 生成器（generator)是不用參數(shù)就可以調(diào)用的函數(shù)符。
2 一元函數(shù)（unary function）是用一個參數(shù)可以調(diào)用的函數(shù)符。
3 二元函數(shù)（binary function)是用兩個參數(shù)可以調(diào)用的函數(shù)符。
4 返回bool值的一元函數(shù)是斷言(predicate).
5 返回bool值的二元函數(shù)是二元斷言(binary predicate).
list 模板有一個將斷言作為參數(shù)的 remove_if()成員，該函數(shù)將斷言應用于區(qū)間中的每個元素，如果斷言為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;
}
（二）預定義的函數(shù)符
函數(shù)：transform()
第一版本：接受4個參數(shù)，前兩個參數(shù)指定容器區(qū)間的迭代器，第3個參數(shù)指定將結(jié)果復制到哪里的迭代器，最后一個參數(shù)是一個函數(shù)符，它被應用與區(qū)間中的每個元素，生成結(jié)果中的新元素。
第二版本：接受5個參數(shù)，前兩個參數(shù)指定第一容器區(qū)間的迭代器，第3個參數(shù)指定第二個容器區(qū)間的起始位置，第4個參數(shù)指定將結(jié)果復制到哪里，最后一個參數(shù)是一個函數(shù)符號，它被應用與兩個區(qū)間中的每個元素。
#include<functional>
plus<double> add;
transform(gr8.begin(),gr8.end(),m8.begin(),out,plus<double>());//將gr8和m8中的元素分別相加，將結(jié)果輸出。
操作符和相應的函數(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
（三） 自適應函數(shù)符和函數(shù)適配器
transform(gr8.begin(),gr8.end(),out,bind1st(multiplies<double>(),2.5)
//將gr8中的每個元素乘以2.5，multiplies<double>()是二
元函數(shù)。(bind1s 和 bind2nd 用法相同)
六 算法
（一） algorithm 頭文件中描述的：非修改式序列操作。
修改式序列操作。
排序和相關(guān)操作。
numeric 頭文件中描述的 ：通用數(shù)字運算。
（二） STL 和 string 類
包含begin(),end(),rbegin(),rend()等成員，可以使用STL接口。
函數(shù)next_permutation()算法將區(qū)間內(nèi)容轉(zhuǎn)換為下一種排列方式。對于字符串，排列按照字母遞增順序進行，如果成功，返回 true,如果區(qū)間已經(jīng)處于最后序列中，返回 false.
（三） 函數(shù)和容器方法
一般STL方法比STL函數(shù)好，因為可以使用模板類的內(nèi)存管理工具，可以自己調(diào)整容器長度，但STL函數(shù)可以用于數(shù)組，string類，STL容器。
list<int> la;
la.remove(4);//刪除所有為4的元素，自動減小容器長度。
remove(la.begin(),lb.end(),4);//刪除所有為4的元素，將沒被刪除的排在容器前面，返回一個指向新的超尾值的迭代器，鏈表長度不變
七 其他庫
vector
,valarray,都是數(shù)組模板。vector模板類支持面向容器的操作，如排序，插入，重新排列，搜索，將數(shù)據(jù)移到其他容器中等；
valarray類模板是面向數(shù)值計算的，不是STL的一部分，比如，沒有 push_back(),insert()等等。
valarray 重載了運算符。
valarray<double> vad1(10),vad2(10),vad3(10);
vector<double> ved1(10),ved2(10),ved3(10);
vad3=vad1+vad2;//將對應的元素相加
vad3=vad1*vad2;//將對應元素相乘
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中每個元素乘以2.5
valarray沒有插入，排序，搜索等方法，有resize()方法，但不能自動調(diào)整valarray的大小。sort()函數(shù)用作valarray需要注意。
valarray<double> vad(10);
sort(vad,vad+10);//錯誤的，因為vad不是數(shù)組名，不能代表地址。
sort(&vad[0],&vad[10]);//錯誤的，因為vad[10]是不確定的。
sort(&vad[0],&vad[9]);
slice對象可用做數(shù)組索引，被初始化為3個整數(shù)值：起始索引，索引數(shù)和跨距。起始索引是第一個被選中的元素的索引，索引數(shù)指出要選擇多少個元素，跨距表示元素之間的間隔。
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
