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