為人熟知的pair型別

注意：pair對於==, !=, <, >, <=, >=進行了過載，提供first第一關鍵字，second第二關鍵字的比較方法。

再談STL

STL有三大件：

1. 容器
2. 演演算法
3. 迭代器

迭代器的使用

#include <vector>
#include <iostream>
using namespace std;
int main()
{
    vector<int> myv;
    myv.push_back(1);
    myv.push_back(2);
    myv.push_back(3);
    vector<int>::iterator it;
    for(it = myv.begin(); it != myv.end(); it++)
    {
        cout << *it << "  ";
    }
    puts("");
    vector<int>::reverse_iterator rit;
    for(rit = myv.rbegin(); rit != myv.rend(); rit++)
    {
        cout << *rit << "  ";
    }
    return 0;
}

常用的STL容器

順序容器

有四個vector, string, deque, list

vector(向量)

優點：

• 可以在末尾快速插入以及刪除
• 支援隨機存取

缺點：

• 在中間插入或者刪除像 陣列 一樣，移動大量元素
• 當大小不夠時，按照兩倍大小重新分配，並且移動。

構造方式

#include <vector>
#include <iostream>
using namespace std;
#define V v4  //更改這裡可以檢視不同效果！
vector<int> v1;
vector<int> v2(20);//指定了初始的size為20，再執行push_back是從21開始！！前面的20個元素的值是0
vector<int> v3(20, 2);//指定了初始的size為20，再執行push_back是從21開始！！前面的20個元素的值是2
int a[] = {1, 2, 3, 4};
vector<int> v4(a, a+4);//從陣列中獲取
int main()
{
    for(int i = 1; i <= 100; i++)
    {
        V.push_back(i);
        printf("%dsize:%d, cap:%d\n",i,  V.size(), V.capacity());
    }
    for(int i = 0; i < V.size(); i++)
        cout << V[i] << "  ";
    return 0;
}

擁有的常用的成員函數（java人稱方法）

常用的僅僅列舉 不說明！

empty()

size()

[]

reserve(n)分配n個元素的儲存空間
注意：這一個僅僅是修改一開始的capacity，不影響size
使用可以直接給定一個空間，避免空間不夠而進行頻繁增加刪除，當做更加優秀的陣列使用

capacity

resize()調整size，比原來小時，刪除多餘的；比原來大時，補0

push_back()

insert(pos, elem)把某一個值插入到pos之前（注意這要耗費許多時間！）
pos是迭代器！

front()獲取第一個值

back()獲取最後一個值

erase()有過載：

1. 一個引數，迭代器，刪除這一個位置元素
2. 兩個迭代器，刪除後這兩個迭代器的區間中的元素。

clear()

begin(), end(), rbegin(), rend()

string

構造方式

string()
string(char*)
string(string)

成員函數

empty()

size()

length()貌似除了型別與上面的有區別，其他的沒有區別

[]

at()和上面一樣

compare(const string &str)比較
如果自己大，返回1，形參大，返回-1，否則返回0

append(const string &str)在末尾增加字串

insert(pos, elem)把某一個值插入到pos之前（注意這要耗費許多時間！）
pos可以是迭代器，也可以是數位！
但是elem一定是字串！

find(字元或字串， 位置)注意：如果找不到，返回值是一個迷，所以儘量不要用

replace()

例子：

string s1("abcdefg");
    string s2(s1);
    s1.replace(3, 3, "lll");//起始位置，長度，替換內容
    cout << s1;
    string::iterator it1 = s2.begin()+1;
    string::iterator it2 = s2.end()-1;
    s2.replace(it1, it2, "11");//[ , )
    cout << s2 ;

substr並不改變原來的值

 string s1("abcdefg");
    cout << s1.substr(3) << "\n";//defg
    cout << s1.substr(3, 3);//def

clear(), erase清空。

erase(idx);從idx（數位）處刪除之後的內容

erase(idx, len)從idx（數位）處刪除之後的長度為len內容

deque

deque與vector相比，他並不是由一個整體的記憶體儲存的，而是由多個連續的記憶體塊儲存的，所以在頭部以及尾部插入元素比較快，並且也支援隨機存取。

構建方式：

#include <deque>
#include <iostream>
using namespace std;
#define DQ dq3
int main()
{
    deque<int>dq1;
    deque<int>dq2(2);
    deque<int>dq3(2, 3);
    deque<int>dq4(dq1);
    deque<int>dq5(dq1.begin(), dq1.end());
    deque<int>::iterator it;
    DQ.push_back(8);
    DQ.push_front(0);
    for(it = DQ.begin(); it != DQ.end(); it++){
        cout << *it;
    }
    return 0;
}

empty()

size()

front()

back()

push_front()

pop_front()

push_back()

pop_back()

erase()清除一個或者幾個值

clear()全部清除

begin(), end(), rbegin(), rend()

list

可以快速插入以及刪除元素，但是不支援隨機存取。

empty()

size()

push_front()

pop_front()

push_back()

pop_back()

removeRemoves every element in the list equal to value.

list<int> l1({1, 2, 3, 4, 4, 4});
    l1.remove(4);
    list<int>::iterator it;
    for(it = l1.begin(); it != l1.end(); it++)
    {
        cout << *it << "  ";//1  2  3
    }

remove_if()

#include <list>
#include <iostream>
using namespace std;
#define DQ dq3
bool judge(int val)
{
    return val&1;
}
int main()
{
    list<int> l1({1, 2, 3, 4, 5, 6});
    l1.remove_if(judge);
    list<int>::iterator it;
    for(it = l1.begin(); it != l1.end(); it++)
    {
        cout << *it << "  ";//2  4  6  
    }
    return 0;
}

erase()刪除一個或者幾個元素

clear()清除所有的元素

insert(pos, n, elem), insert(pos, elem)注意：這一個插入是瞬間完成的。

insert(pos, 迭代器開始, 迭代器結束)

由於STL中的某些演演算法處理的是順序容器的，所以在list中額外提供了一些功能。

#include <list>
#include <iostream>
using namespace std;
list<int>::iterator it;
int main()
{
    list<int> l1({1, 3, 5, 7,  9, 11});
    list<int> l2({2, 4, 6, 8, 10, 11});
    l1.merge(l2);//************************************
    for(it = l1.begin(); it != l1.end(); it++)
    {
        cout << *it << "  ";
    }
    puts("");
    l1.reverse();//************************************
    for(it = l1.begin(); it != l1.end(); it++)
    {
        cout << *it << "  ";
    }
    puts("");
    l1.sort();//************************************
    for(it = l1.begin(); it != l1.end(); it++)
    {
        cout << *it << "  ";
    }
    puts("");
    l1.unique();//************************************
    for(it = l1.begin(); it != l1.end(); it++)
    {
        cout << *it << "  ";
    }
    puts("");
    return 0;
}

關聯容器

set/multiset

set：集合容器

multiset：多重集合容器

元素值就是關鍵字

優點

1. 預設進行了排序。
2. 可以快速插入，刪除，查詢（全部是logN）。
3. 支援集合的交，差，並

成員函數

empty()

size()

insert()

erase()查詢元素並且刪除（返回值為刪除了的元素的個數（在multiset中可能大於1））

clear()

count返回關鍵字出現的次數

find()如果存在，返回迭代器，否則返回end()

upper_bound()第一個大於num的數位

lower_bound()第一個大於或等於num的數位

begin(), end(), rbegin(), rend()

集合的交集，並集，差集

#include <list>
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

list<int>::iterator it;
int main()
{
    set<int> s1({1, 2, 3, 4, 5, 6, 7, 8});
    set<int> s2({5, 6, 7, 8, 9, 10});
    vector<int> ret;

    //一定要設定大小！
    ret.resize(max(s1.size(), s2.size()));
    vector<int>::iterator tmp = set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), ret.begin());
    ret.resize(tmp - ret.begin());
    //重新設定大小
    for(vector<int>::iterator it = ret.begin(); it != ret.end(); it++)
    {
        cout << *it << "  ";
    }
    return 0;
}

set_intersection              //求兩個容器的交集

set_union                        //求兩個容器的並集

set_difference                //求兩個容器的差集

map/multimap

注意：map/multimap中的元素是以pair<>進行儲存的。

map/multimap的區別

map的key不允許重複，可以使用[]

multimap的key允許重複，不可以使用[]

主要的成員函數

empty()

size()

XX[key]

• 如果存在key，那麼就可以進行參照以及賦值；
• 但是如果不存在key，那麼就會新建立一個key然後插入。

insert(make_pair() 或者 {__, __})

erase()

multimap<int, int> mp;
    mp.insert({1, 2});
    mp.insert({1, 3});
    mp.insert({1, 4});
    int ret = mp.erase(1);
    cout << ret;

當然裡面也可以是迭代器！

clear()

count()返回指定關鍵字的數量

find()查詢關鍵字（如果是Multimap,那麼就會返回第一個關鍵字）

tip:利用find和count就可以找到multimap中的所有的key值元素

雜湊容器：
unorder_map/multimap、unorder_set/multiset

基本的使用與上面的是相同的

• 但是就是沒有排序也不能進行集合的運算。
• 會佔用較大的空間
• 存取的速度也將大大提升

介面卡容器

概述

一般情況下，

stack：deque（常規），list，vector

queue：deque（常規），list

priority_queue：vector（常規），deque

手動指定：

stack<int, deque<int> >s;//預設
stack<int, list<int> >s;
stack<int, vector<int> >s;

queue<int, deque<int> >q;//預設
queue<int, list<int> >q;

priority_queue<int, vector<int> >q;//預設
priority_queue<int, deque<int> >q;

stack

具有

empty()

size()

push

pop

top

queue

具有

empty()

size()

push

pop

front

back

priority_queue

empty()

size()

push

pop

top

---

關係函數物件

標頭檔案：#include<functional>

greater<>

less<>

相關練習

分隔單詞

輸入一堆單詞，分割單詞（沒有標點符號）

#include <bits/stdc++.h>
using namespace std;
void Divide(const string &str, vector<string> &vec)
{
    int i, j;
    i = 0;
    j = str.find(" ");
    while(j != -1)
    {
        vec.push_back(str.substr(i, j-i));
        i = j+1;
        j = str.find(" ", i);
    }
    if(i < str.length())
    {
        vec.push_back(str.substr(i));
    }
}
int main()
{
    char buf[100];
    fgets(buf, 100, stdin);
    string str = string(buf);
    str.erase(str.find("\n"));
    vector<string> vec;
    Divide(str, vec);
    for(int i = 0; i < vec.size(); i++)
        cout << vec[i] << "\n";
    return 0;
}