程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> C++STL之ACM相關知識大全

C++STL之ACM相關知識大全

編輯：C++入門知識

C++STL之ACM相關知識大全

vector
在STL 的頭文件中定義了vector（向量容器模板類），vector容器以連續數組的方式存儲元素序列，可以將vector 看作是以順序結構實現的線性表。當我們在程序中需要使用動態數組時，vector 將會是理想的選擇，vector 可以在使用過程中動態地增長存儲空間。
vector 模板類需要兩個模板參數，第一個參數是存儲元素的數據類型，第二個參數是存儲分配器的類型，其中第二個參數是可選的，如果不給出第二個參數，將使用默認的分配器。

1.定義vector 向量對象的方法：

vector s;

定義一個空的vector 對象，存儲的是int 類型的元素。

vector s(n);//定義一個含有n 個int 元素的vector 對象。

vector s(first, last);//定義一個vector 對象，並從由迭代器first 和last 定義的序列[first,last)中復制初值。

vector 的基本操作有：

s[i]; //直接以下標方式訪問容器中的元素。
s.front(); //返回首元素。
s.back(); //返回尾元素。
s.push_back(x); //向表尾插入元素x。
s.size(); //返回表長。
s.empty(); //當表空時，返回真，否則返回假。
s.pop_back(); //刪除表尾元素。
s.begin(); //返回指向首元素的隨機存取迭代器。
s.end(); //返回指向尾元素的下一個位置的隨機存取迭代器。
s.insert(it, x); //向迭代器it 指向的元素前插入新元素val。
s.insert(it, n, x); //向迭代器it 指向的元素前插入n 個x。
s.insert(it, first, last); //將由迭代器first 和last 所指定的序列[first, last)插入到迭代器it指向的元素前面。
s.erase(it); //刪除由迭代器it 所指向的元素。
s.erase(first, last); //刪除由迭代器first 和last 所指定的序列[first, last)。
s.reserve(n); //預分配緩沖空間，使存儲空間至少可容納n 個元素。
s.resize(n); //改變序列的長度，超出的元素將會被刪除，如果序列需要擴展（原空間小於n），元素默認值將填滿擴展出的空間。
s.resize(n, val);//改變序列的長度，超出的元素將會被刪除，如果序列需要擴展（原空間小於n），將用val 填滿擴展出的空間。
s.clear(); //刪除容器中的所有的元素。
s.swap(v); //將s 與另一個vector 對象v 進行交換。
s.assign(first, last); //將序列替換成由迭代器first 和last 所指定的序列[first, last)。[first, last)不能是原序列中的一部分。要注意的是，resize 操作和clear 操作都是對表的有效元素進行的操作，但並不一定會改變緩沖空間的大小。。

vector 上還定義了序列之間的比較操作運算符(>, <, >=, <=, ==, !=)，
可以按照字典序比較兩個序列。還是來看一些示例代碼。輸入個數不定的一組整數，再將這組整數按倒序輸出，
如下所示：

#include 
#include 
using namespace std;
int main()
{
    vectors;
    int x;
    while(cin>>x)
        s.push_back(x);
    for(int i=s.size()-1;i>=0;i--)
        cout<

iterator iterator(迭代器)是用於訪問容器中元素的指示器，從這個意義上說，iterator(迭代器)相當於數據結構中所說的“遍歷指針”，也可以把iterator(迭代器)看作是一種泛化的指針。STL 中關於iterator(迭代器)的實現是相當復雜的，這裡我們暫時不去詳細討論關於iterator(迭代器)的實現和使用，而只對iterator(迭代器)做一點簡單的介紹。簡單地說，STL 中有以下幾類iterator(迭代器)：輸入iterator(迭代器)，在容器的連續區間內向前移動，可以讀取容器內任意值；輸出iterator(迭代器)，把值寫進它所指向的容器中；前向iterator(迭代器)，讀取隊列中的值，並可以向前移動到下一位置(++p,p++)；雙向iterator(迭代器)，讀取隊列中的值，並可以向前向後遍歷容器；隨機訪問iterator(迭代器), 可以直接以下標方式對容器進行訪問，vector 的iterator(迭代器)就是這種iterator(迭代器)；流iterator(迭代器)，可以直接輸出、輸入流中的值；每種STL 容器都有自己的iterator(迭代器)子類，下面先來看一段簡單的示例代碼：

#include 
#include 
using namespace std;
int main()
{
    vector s;
    for(int i=0;i<10;i++)
    {
        s.push_back(i);
    }
    for(vector::iterator it=s.begin();it!=s.end();it++)
    {
        cout<<*it<<" ";
    }
    cout<

vector 的begin()和end()方法都會返回一個vector::iterator 對象，分別指向vector 的首元素位置和尾元素的下一個位置（我們可以稱之為結束標志位置）。對一個iterator(迭代器)對象的使用與一個指針變量的使用極為相似，或者可以這樣說，指針就是一個非常標准的iterator(迭代器)。再來看一段稍微特別一點的代碼：

#include   
#include   
using namespace std;  
main()  
{  
    vector s;  
    s.push_back(1);  
    s.push_back(2);  
    s.push_back(3);  
    copy(s.begin(), s.end(), ostream_iterator(cout, ""));  
    cout <

這段代碼中的copy 就是STL 中定義的一個模板函數，

copy(s.begin(),s.end(), ostream_iterator(cout, " "));

的意思是將由s.begin()至s.end()(不含s.end())所指定的序列復制到標准輸出流cout 中，用” “作為每個元素的間隔。也就是說，這句話的作用其實就是將表中的所有內容依次輸出。iterator(迭代器)是STL 容器和算法之間的“膠合劑”，幾乎所有的STL 算法都是通過容器的iterator(迭代器)來訪問容器內容的。只有通過有效地運用iterator(迭代器)，才能夠有效地運用STL 強大的算法功能。

string 字符串是程序中經常要表達和處理的數據，我們通常是采用字符數組或字符指針來表示字符串。STL 為我們提供了另一種使用起來更為便捷的字符串的表達方式：string。string 類的定義在頭文件中。string 類其實可以看作是一個字符的vector，vector 上的各種操作都可以適用於string，另外，string 類對象還支持字符串的拼合、轉換等操作。

stack stack 模板類的定義在頭文件中。滿足先進後出原則； stack 模板類需要兩個模板參數，一個是元素類型，一個容器類型，但只有元素類型是必要的，在不指定容器類型時，默認的容器類型為deque(雙端隊列)。定義stack 對象的示例代碼如下：

stack s1;
stack s2;

stack 的基本操作有：

入棧，如例：s.push(x); 出棧，如例：s.pop();//注意，出棧操作只是刪除棧頂元素，並不返回該元素。訪問棧頂，如例：s.top()；判斷棧空，如例：s.empty()；，當棧空時，返回true。訪問棧中的元素個數，如例：s.size()；

queue queue 模板類的定義在頭文件中。滿足先進先出原則； stack 模板類很相似，queue 模板類也需要兩個模板參數，一個是元素類型，一個容器類型，元素類型是必要的，容器類型是可選的，默認為deque 類型。

定義queue 對象的示例代碼如下：

queue q1;
queue q2;

queue 的基本操作有：入隊，如例：q.push(x); 將x 接到隊列的末端。出隊，如例：q.pop(); 彈出隊列的第一個元素，注意，並不會返回被彈出元素的值。訪問隊首元素，如例：q.front()，即最早被壓入隊列的元素。訪問隊尾元素，如例：q.back()，即最後被壓入隊列的元素。判斷隊列空，如例：q.empty()，當隊列空時，返回true。訪問隊列中的元素個數，如例：q.size()

根據隊列性質其常用於BFS題目中；

priority_queue 在頭文件中，還定義了另一個非常有用的模板類priority_queue(優先隊列）。優先隊列與隊列的差別在於優先隊列不是按照入隊的順序出隊，而是按照隊列中元素的優先權順序出隊（默認為大者優先，也可以通過指定算子來指定自己的優先順序）。 priority_queue 模板類有三個模板參數，第一個是元素類型，第二個容器類型，第三個是比較算子。其中後兩個都可以省略，默認容器為vector，默認算子為less，即小的往前排，大的往後排（出隊時序列尾的元素出隊）。

定義priority_queue 對象的示例代碼如下：

priority_queue q1;
priority_queue< pair > q2; // 注意在兩個尖括號之間一定要留空格。
priority_queue, greater > q3; // 定義小的先出隊

priority_queue 的基本操作與queue 相同。初學者在使用priority_queue 時，最困難的可能就是如何定義比較算子了。如果是基本數據類型，或已定義了比較運算符的類，可以直接用STL 的less算子和greater 算子——默認為使用less 算子，即小的往前排，大的先出隊。如果要定義自己的比較算子，方法有多種，這裡介紹其中的一種：重載比較運算符。優先隊列試圖將兩個元素x 和y 代入比較運算符(對less 算子，調用x

#include   
#include   
using namespace std;  
class T  
{  
    public:  
        int x, y, z;  
        T(int a, int b, int c):x(a), y(b), z(c){}  
};  
bool operator < (const T &t1, const T &t2)  
{  
    return t1.z < t2.z; // 按照z 的順序來決定t1 和t2 的順序，即小的往前排，大的先出隊。  
}  
int main()  
{  
    priority_queue q;  
    q.push(T(4,4,3));  
    q.push(T(2,2,5));  
    q.push(T(1,5,4));  
    q.push(T(3,3,6));  
    while (!q.empty())  
    {  
        T t = q.top(); q.pop();  
        cout << t.x << " " << t.y << " " << t.z << endl;  
    }  
return 0;   
}  
/*輸出結果為(注意是按照z 的順序從大到小出隊的)： 
3 3 6 
2 2 5 
1 5 4 
4 4 3*/

再看一個按照z 的順序從小到大出隊的例子：

#include   
#include   
using namespace std;  
class T  
{  
    public:  
        int x, y, z;  
    T(int a, int b, int c):x(a), y(b), z(c)  
    {  
    }  
};  
bool operator > (const T &t1, const T &t2)  
{  
    return t1.z > t2.z;  //即大的往前排，小的先出隊。
}  
int main()  
{  
    priority_queue, greater > q;  
    q.push(T(4,4,3));  
    q.push(T(2,2,5));  
    q.push(T(1,5,4));  
    q.push(T(3,3,6));  
    while (!q.empty())  
    {  
        T t = q.top(); q.pop();  
        cout << t.x << " " << t.y << " " << t.z << endl;  
    }  
    return 0;  
}  

/*輸出結果為：
4 4 3
1 5 4
2 2 5
3 3 6*/

如果我們把第一個例子中的比較運算符重載為：

bool operator < (const T &t1, const T &t2)
{
    return t1.z > t2.z; // 按照z 的順序來決定t1 和t2 的順序，即大的往前排，小的先出隊。
}

則第一個例子的程序會得到和第二個例子的程序相同的輸出結果。

例題： POJ1338-丑數 http://poj.org/problem?id=1338

#include   
#include   
using namespace std;  
typedef pair node_type;  
int main( int argc, char *argv[] )  
{  
    unsigned long int result[1500];  
    priority_queue< node_type, vector,  
    greater > Q; 
    //優先隊列的聲明方式：Greater為小的先輸出，less為大的先出 
    Q.push( make_pair(1, 3) );  
    for (int i=0; i<1500; i++)  
    {  
        node_type node = Q.top();  
        Q.pop();  
        switch(node.second)  
        {  
            case 3: Q.push( make_pair(node.first*2, 3) );  
            case 2: Q.push( make_pair(node.first*3, 2) );  
            case 1: Q.push( make_pair(node.first*5, 1) );  
        }  
        result[i] = node.first;  //node.first訪問pair的第一個元素
    }  
    int n;  
    cin >> n;  
    while (n>0)  
    {  
        cout << result[n-1] << endl;  
        cin >> n;  
    }  
    return 0;  
}

map 在STL 的頭文件中定義了模板類map 和multimap，用有序二叉樹來存貯類型為 pair的元素對序列。序列中的元素以const Key部分作為標識，map 中所有元素的Key 值都必須是唯一的，multimap 則允許有重復的Key 值。可以將map 看作是由Key 標識元素的元素集合，這類容器也被稱為“關聯容器”，可以通過一個Key 值來快速確定一個元素，因此非常適合於需要按照Key值查找元素的容器。 map 模板類需要四個模板參數，第一個是鍵值類型，第二個是元素類型，第三個是比較算子，第四個是分配器類型。其中鍵值類型和元素類型是必要的。map 的基本操作有：

1、定義map 對象：

map m;

2、向map 中插入元素對，有多種方法，例如： m[key] = value; [key]操作是map 很有特色的操作，如果在map 中存在鍵值為key 的元素對，則返回該元素對的值域部分，否則將會創建一個鍵值為key 的元素對，值域為默認值。所以可以用該操作向map 中插入元素對或修改已經存在的元素對的值域

m.insert( make_pair(key, value) );

直接調用insert 方法插入元素對，insert 操作會返回一個pair，當map 中沒有與key 相匹配的鍵值時，其first 是指向插入元素對的迭代器，其second 為true；若map 中已經存在與key 相等的鍵值時，其first 是指向該元素對的迭代器，second 為false。

3、查找元素對：

int i = m[key];

要注意的是，當與該鍵值相匹配的元素對不存在時，會創建鍵值為key 的元素對。

map::iterator it = m.find(key);

如果map 中存在與key 相匹配的鍵值時，find 操作將返回指向該元素對的迭代器，否則，返回的迭代器等於map 的end()（參見vector 中提到的begin和end 操作）。

4、刪除元素對：

m.erase(key);//刪除與指定key 鍵值相匹配的元素對，並返回被刪除的元素的個數。
m.erase(it);//刪除由迭代器it 所指定的元素對，並返回指向下一個元素對的迭代器。

舉個簡單的例子：

#include  
#include  
using namespace std;  
typedef map > M_TYPE;  
typedef M_TYPE::iterator M_IT;  
typedef M_TYPE::const_iterator M_CIT;  
int main()  
{  
    M_TYPE MyTestMap;  
    MyTestMap[3] = "No.3";  
    MyTestMap[5] = "No.5";  
    MyTestMap[1] = "No.1";  
    MyTestMap[2] = "No.2";  
    MyTestMap[4] = "No.4";  
    M_IT it_stop = MyTestMap.find(2);  
    cout << "MyTestMap[2] = " << it_stop->second << endl;  
    it_stop->second = "No.2 After modification";  
    cout << "MyTestMap[2] = " << it_stop->second << endl;  
    cout << "Map contents : " << endl;  
    for(M_CIT it = MyTestMap.begin(); it != MyTestMap.end();it++)  
    {  
        cout << it->second << endl;  
    }  
    return 0;  
}  
/*程序執行的輸出結果為： 
MyTestMap[2] = No.2 
MyTestMap[2] = No.2 After modification 
Map contents : 
No.1 
No.2 After modification 
No.3 
No.4 
No.5*/

insert 使用方法：

#include   
#include  
using namespace std;  
int main()  
{  
    map m;  
    m["one"] = 1;  
    m["two"] = 2;  
    // 幾種不同的insert 調用方法  
    m.insert(make_pair("three", 3));//推薦使用  
    m.insert(map::value_type("four", 4));  
    m.insert(pair("five", 5));  
    string key;  
    while (cin>>key)  
    {  
        map::iterator it = m.find(key);  
        if (it==m.end())  
        {  
            cout << "No such key!" << endl;  
        }  
        else  
        {  
            cout << key << " is " << it->second << endl;  
            cout << "Erased " << m.erase(key) << endl;  
        }  
    }  
    return 0;  
}

map的例題：

HDU1263 水果 http://acm.hdu.edu.cn/showproblem.php?pid=1263

用map關聯map：代碼如下：

#include 
#include
#include 
using namespace std;
int main()
{

    int n,m;
    cin>>n;
    while(n--)
    {
        string name,space;
        int num;
        map > mp;
        cin>>m;
        for(int i=0;i>name>>space>>num;
            mp[space][name]+=num;
        }
        for(map > ::iterator it1=mp.begin();it1!=mp.end();it1++)
        {
            cout<first<::iterator it2=it1->second.begin();it2!=it1->second.end();it2++)
            {

                cout<<"   "<<"|----"<first<<"("<second<<")"<

set set集合容器：實現了紅黑樹的平衡二叉檢索樹的數據結構，插入元素時，它會自動調整二叉樹的排列，把元素放到適當的位置，以保證每個子樹根節點鍵值大於左子樹所有節點的鍵值，小於右子樹所有節點的鍵值；另外，還得保證根節點左子樹的高度與右子樹高度相等。平衡二叉檢索樹使用中序遍歷算法，檢索效率高於vector、deque和list等容器，另外使用中序遍歷可將鍵值按照從小到大遍歷出來。構造set集合主要目的是為了快速檢索，不可直接去修改鍵值。

常見用法： begin() 　　 ,返回set容器的第一個元素 end() 　　　　 ,返回set容器的最後一個元素 clear() 　　 ,刪除set容器中的所有的元素 empty() 　　　,判斷set容器是否為空 max_size() 　 ,返回set容器可能包含的元素最大個數 size() 　　　　 ,返回當前set容器中的元素個數 rbegin　　　　 ,返回的值和end()相同 rend()　　　　 ,返回的值和rbegin()相同

更多用法參見： http://www.cnblogs.com/BeyondAnyTime/archive/2012/08/13/2636375.html

直接比較例子：

#include  
#include  
#include  
using namespace std;  
int main(){  
    setstrset;  
    set::iterator it;  
    strset.insert("cantaloupes");  
    strset.insert("apple");  
    strset.insert("orange");  
    strset.insert("banana");  
    strset.insert("grapes");  
    strset.insert("grapes");   
    for(it=strset.begin();it!=strset.end();it++){  
        cout<<*it<<" ";  
    }  
    cout<

運行結果：<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPjxjb2RlIGNsYXNzPQ=="hljs cpp">結構體中元素比較：

#include  
#include  
using namespace std;  
struct Student
{  
  int id;  
  char name[20];  
}stu1,stu2,stu3;  

struct setCmp {    
 bool operator()(Student a,Student b) {    
  return a.id>b.id;    
 }    
};   

int main(){  
    setmys;  
    set::iterator it;  
    stu1.id=1008;  
    strcpy(stu1.name,"zhangsan");  
    mys.insert(stu1);  

    stu2.id=1001;  
    strcpy(stu2.name,"lisi");  
    mys.insert(stu2);  

    stu3.id=1005;  
    strcpy(stu3.name,"wangwu");  
    mys.insert(stu3);  

    for(it=mys.begin();it!=mys.end();++it){  
        cout<id<<" "<name<

min_element/max_element 找出容器中的最小/最大值：

#include 
#include 
#include 
using namespace std;
int main()
{
    vector v;
    int n,m;
    while(cin>>n)
    {
        for(int i=0;i>m;
            v.push_back(m);
        }
        cout<<*max_element(v.begin(),v.end())<<" "<<*min_element(v.begin(),v.end())<

或是：

#include 
#include 
#include 
using namespace std;
int main()
{
    vector v;
    int n,m;
    while(cin>>n)
    {
        for(int i=0;i>m;
            v.push_back(m);
        }
        float max_num=*max_element(v.begin(),v.end());
        float min_num=*min_element(v.begin(),v.end());
        cout<

sort 對容器進行排序

#include   
#include   
#include   
using namespace std;  
void Print(vector &L)  
{  
    for (vector::iterator it=L.begin(); it!=L.end();it++)  
    cout << *it << " ";  
    cout << endl;  
}  
int main()  
{  
    vector L;  
    for (int i=0; i<5; i++)   
        L.push_back(i);  
    for (int i=9; i>=5; i--)   
        L.push_back(i);  
    Print(L);  
    sort(L.begin(), L.end());  
    Print(L);  
    sort(L.begin(), L.end(), greater()); // 按降序排序  
    Print(L);  
    return 0;  
}  
/*
0 1 2 3 4 9 8 7 6 5
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
*/

copy 在容器間復制元素：

#include   
#include   
#include   
using namespace std;  
int main()  
{  
    // 先初始化兩個向量v1 和v2  
    vector  v1, v2;  
    for (int i=0; i<=5; i++)   
        v1.push_back(10*i);  
    for (int i=0; i<=10; i++)   
        v2.push_back(3*i);  
    cout << "v1 = ( " ;  
    for (vector ::iterator it=v1.begin(); it!=v1.end();it++)  
        cout << *it << " ";  
    cout << ")" << endl;  
    cout << "v2 = ( " ;  
    for (vector ::iterator it=v2.begin(); it!=v2.end();it++)  
        cout << *it << " ";  
    cout << ")" << endl;  
    // 將v1 的前三個元素復制到v2 的中間  
    copy(v1.begin(), v1.begin()+3, v2.begin()+4);  
    cout << "v2 with v1 insert = ( " ;  
    for (vector ::iterator it=v2.begin(); it!=v2.end();it++)  
        cout << *it << " ";  
    cout << ")" << endl;  
    // 在v2 內部進行復制，注意參數2 表示結束位置，結束位置不參與復制  
    copy(v2.begin()+4, v2.begin()+7, v2.begin()+2);  
    cout << "v2 with shifted insert = ( " ;  
    for (vector ::iterator it=v2.begin(); it!=v2.end();it++)  
    cout << *it << " ";  
    cout << ")" << endl;  
    return 0;  
}

程序的輸出結果為： v1 = ( 0 10 20 30 40 50 ) v2 = ( 0 3 6 9 12 15 18 21 24 27 30 ) v2 with v1 insert = ( 0 3 6 9 0 10 20 21 24 27 30 ) v2 with shifted insert = ( 0 3 0 10 20 10 20 21 24 27 30 )

僅代表個人觀點，歡迎交流探討，勿噴~~~