5.容器（下）

Stack

Stack是一種先進后出（First In Last Out）的數(shù)據(jù)結(jié)構(gòu)，只有一個出口：

• 支持push、pop和top
• 只能訪問頂層元素，不能遍歷
• #include<stack>

template<class _Ty, class _Container = deque<_Ty>>
class stack{
    ...
};

默認(rèn)使用的容器為deque。top范圍棧頂元素，但是不會彈出去，如果使用pop，則彈出棧頂元素。

Queue

Queue是一種先進先出（First In First Out）的數(shù)結(jié)構(gòu)

• 支持push，pop，front和back操作
• 只能訪問最前或最后元素，不允許遍歷
• #include<queue>

template<class _Ty, class _Container = deque<_Ty>>
class queue{
    ...
};

默認(rèn)使用的容器為deque。不允許遍歷，沒有迭代器。

Map and Multimap

Map

• 關(guān)聯(lián)式容器，存儲的對象是Key/Value pair
• 不允許有重復(fù)的key
• 對象必須具有可排序性能（Key）

template<class _Kty, class _Ty, class _Pr = less<_Kty>, 
    class _Alloc = allocator<pair<const _Kty, _Ty>>>
    class map{ ... };

• 默認(rèn)采用less排序
• 可通過仿函數(shù)自定義排序
• #include<map>

map.png

插入元素：

map1.insert(std::make_pair(4, Employee(L"Brown")));
map1[5] = Empolyee(L"Fisher");

刪除元素：

std::map<Person, PersonIdComparer>::iterator it = map1.begin();
map1.erase(it);

operator[]存取元素：

Employee& e = map1[2];
e.SetName(L"...");
...

Multimap

• 類似map的容器
• 允許key重復(fù)

Set and Multiset

Set

• 關(guān)聯(lián)式容器，存儲的對象是即是Key又是Value
• 不允許有重復(fù)的key
• 對象必須具有可排序性能

template<class _Kty, class _Pr = less<_Kty>, 
    class _Alloc = allocator<_Kty>>
    class set{ ... };

• 默認(rèn)采用less排序，存儲對象必須具有operator<行為
• 可通過仿函數(shù)自定義排序
• #include<set>

set.png

插入元素：

ps1.insert(Person(L"Bill", 4));

刪除元素：

std::set<Person, PersonIdComparer>::iterator it = ps1.begin();
std::advance(it, 1); //it開始指向begin，通過advance增加1，之后指向第二個元素
ps1.erase(it);

相關(guān)算法：

set_union，合并兩個set（具有相同的存儲對象型別）

std::set<Person, PersonIdComparer> dest;
std::insert_iterator<std::set<Person, PersonIdComparer>> ii(dest, dest.begin());
std::set_union(ps1.begin(), ps1.end(), ps2.begin(), ps2.end(), ii, PersonIdComparer());

set_union.png

set_intersection，將連個set中相同的元素拿出來，放到新的set中。

std::set<Person, PersonIdComparer> dest;
std::insert_iterator<std::set<Person, PersonIdComparer>> ii(dest, dest.begin());
std::set_intersection(ps1.begin(), ps1.end(), ps2.begin(), ps2.end(), ii, PersonIdComparer());

set_intersection.png

set_difference，包含在[first1,last1)中而不包含在[first2,last2)中的元素。

std::set<Person, PersonIdComparer> dest;
std::insert_iterator<std::set<Person, PersonIdComparer>> ii(dest, dest.begin());
std::set_difference(ps1.begin(), ps1.end(), ps3.begin(), ps3.end(), ii, PersonIdComparer());

set_difference.png

特別注意：

• 用于排序的成員（在Person中對象的Id，是真正的Key）不可改變
• 出了真正的Key，其他成員可以改變但是需要特殊手法

std::set<Person, PersonIdCompare>::iterator it = ps1.find(Person(L"Bill", 4));
if(it != ps1.end()){
    it->SetName(L"Bill Gates"); //看上去沒有問題，但是錯誤，編譯不通過
}

set的實現(xiàn)方式不允許通過迭代器改變對象成員！

通過如下方式改變：

std::set<Person, PersonIdCompare>::iterator it = ps1.find(Person(L"Bill", 4));
if(it != ps1.end()){
    const_cast(Person&)<*it>.SetName(L"Bill Gates"); //通過const_cast將it轉(zhuǎn)化為Person 的引用，在修改Person的名字。
}

一定要cast為對象的引用，如下兩種方式可以編譯通過，但是無法改變對象的成員：

static_cast(Person)<*it>.SetName(L"Bill Gates");
((Person)(*it)).SetName(L"Bill Gates");

因為上面兩個方法的行為等同于下面的語句：

Person tempCopy(*it);
tempCopy.SetName(L"Bill Gates"); //改變的只是臨時對象，并非set中的對象

擴展測試代碼

#include <iostream>
#include <algorithm>
#include <string>
#include <set>

class Person{
public:
    Person(int id, std::string name): id(id), name(name){}
    std::string GetName() const{ return name; }
    void SetName(std::string n){ name = n; }
    int GetId() const{ return id; }
    void SetId(int i){ id = i; }
private:
    int id;
    std::string name;
};

std::ostream& operator<< (std::ostream& os, const Person& p){
    return os << "Id: " << p.GetId() << ", Name: " << p.GetName();
}

template<typename T>
struct PrintContainer{
    PrintContainer(std::ostream& out, std::string partition = "\n") : os(out), partition(partition){}
    void operator()(const T& x){ os << x << partition;}
    std::ostream& os;
    std::string partition;
};

template<class _Kty, class _Pr, class _Alloc>
void PrintSet(std::set<_Kty, _Pr, _Alloc> s){
    std::for_each(s.begin(), s.end(), PrintContainer<_Kty>(std::cout));
}

struct PersonIdCompare : public std::binary_function<Person, Person, bool>{
    bool operator()(Person p1, Person p2){
        return (p1.GetId() < p2.GetId()) ? true : false;
    }
};

struct PersonNameCompare : public std::binary_function<Person, Person, bool>{
    bool operator()(Person p1, Person p2){
        return (p1.GetName() < p2.GetName()) ? true : false;
    }
};

int main(){
    Person personArray1[3]={
        Person(1, "z_name"),
        Person(2, "y_name"),
        Person(3, "x_name")
    };

    std::set<Person, PersonIdCompare> psid1(personArray1, personArray1 + 3);
    std::cout << "psid1:" << std::endl;
    PrintSet(psid1);
    std::set<Person, PersonNameCompare> psname1(personArray1, personArray1 + 3);
    std::cout << "psname1:" << std::endl;
    PrintSet(psname1);

    std::set<Person, PersonIdCompare>::iterator it = psid1.find(Person(1, "z_name"));
    if(it != psid1.end()){
        std::cout << "((Person)(*it)).SetName(\"123\");" << std::endl;
        ((Person)(*it)).SetName("123");
        PrintSet(psid1);
        std::cout << "static_cast<Person>(*it).SetName(\"123\");" << std::endl;
        static_cast<Person>(*it).SetName("123");
        PrintSet(psid1);
        std::cout << "const_cast<Person&>(*it).SetName(\"123\");" << std::endl;
        const_cast<Person&>(*it).SetName("123");
        PrintSet(psid1);
    }
    getchar();
    return 0;
}

輸出結(jié)果：

psid1:
Id: 1, Name: z_name
Id: 2, Name: y_name
Id: 3, Name: x_name
psname1:
Id: 3, Name: x_name
Id: 2, Name: y_name
Id: 1, Name: z_name
((Person)(*it)).SetName("123");
Id: 1, Name: z_name
Id: 2, Name: y_name
Id: 3, Name: x_name
static_cast<Person>(*it).SetName("123");
Id: 1, Name: z_name
Id: 2, Name: y_name
Id: 3, Name: x_name
const_cast<Person&>(*it).SetName("123");
Id: 1, Name: 123
Id: 2, Name: y_name
Id: 3, Name: x_name

6&7.STL整體結(jié)構(gòu)，仿函數(shù)，仿函數(shù)適配器

STL整體結(jié)構(gòu)

• 內(nèi)存分配器 Allocator
• 容器 Containers
• 算法 Algorithms
• 迭代器 Iterators
• 仿函數(shù) Functors
• 適配器 Adapters

stl組件關(guān)系.png

仿函數(shù)

又稱作函數(shù)對象（Function Object），其作用相當(dāng)于一個函數(shù)指針。

std::remove_if(v.begin(), v.end(), ContainsString(L"C+="));

STL中將這種行為函數(shù)指針定義為所謂的仿函數(shù)，其實現(xiàn)是一個class，再以仿函數(shù)產(chǎn)生一個對象作為算法的參數(shù)。

仿函數(shù)與算法之間的關(guān)系

Algorithm(Iterator first, Iterator last, ..., Functor func){
    ...
    func(...)//其實相當(dāng)于調(diào)用對象中的operator()
    ...
}

仿函數(shù)的類別定義中必須重載函數(shù)調(diào)用（function call）operator()。

為什么要用仿函數(shù)而不用普通函數(shù)指針？

• 普通函數(shù)指針不能滿足STL的抽象要求
• 函數(shù)指針無法和STL其他組件交互

仿函數(shù)可以作為模板實參用于定義對象的某種默認(rèn)行為

class Person{...};
std::set<Person, std::less<Person>> set1, set2; //operator< 排序
std::set<Person, std::greater<Person>> set1, set2; //operator> 排序
...
if(set1 === set2)...//正確，相同的型別
if(set1 === set3)...//錯誤，不同的型別！

仿函數(shù)適配器

將無法匹配的仿函數(shù)“套接”成可以匹配的型別

• binder1st/binder2nd
• mem_fun/mem_fun_ref

binder1st

給定一個vector，其元素為[0, 0, 0, 0, 0, 0, 0, 0, 10, 0],通過not_equal_to來匹配第一個非0元素。

std::not_equal_to<int> f; //適配前的仿函數(shù)

typename std::not_equal_to<int>::first_argument_type nonZeroElement(0);
    //本例中實際為int，在not_equal_to<T> 中，typedef first_argument_type為T類型，并賦初值0

std::vector<int>::iterator it = std::find_if(v.begin(), b.end(),
    std::binder1st<std::not_equal_to<int>>(f，nonZeroElement));
    //注意此處為binder1st

在實際使用時，標(biāo)準(zhǔn)庫封裝了一個模板函數(shù)，bind1st，這個函數(shù)把定義nonZeroElement和f的過程封裝掉了，因此以上三條語句可以簡化為一條：

std::find_if(v.begin(), b.end(),
    std::bind1st(std::not_equal_to<int>()，0));
    //注意此處為bind1st

binder2nd

和binder1st有所區(qū)別的是，binder2nd綁定的是右值，而binder1st綁定的是左值，因此以下兩條語句等價：

std::bind1st(std::less<int>(), 0);
std::bing2nd(std::greater<int>(), 0);

mem_fun

這個適配器用來適配對象的成員函數(shù)。

class Person{
public:
    Person(int id, std::string name): id(id), name(name){}
    std::string GetName() const{ return name; }
    void SetName(std::string n){ name = n; }
    int GetId() const{ return id; }
    void SetId(int i){ id = i; }
    void Print() const{ std::cout << "Id: " << id << ", Name: " << name << std::endl; }
private:
    int id;
    std::string name;
};

std::vector<Person*> v;
    v.push_back(new Person(1, "z_name"));
    v.push_back(new Person(2, "y_name"));
    v.push_back(new Person(3, "x_name"));
    
std::for_each(v.begin(), v.end(), &Person::Print);//編譯錯誤，for_each不接受這種形式的參數(shù)

通過如下方式可以正常調(diào)用：

std::for_each(v.begin(), v.end(), std::mem_fun(&Person::Print));

mem_fun_ref

與mem_fun不同的是，mem_fun_ref采用引用，調(diào)用成員函數(shù)時，使用reference而不是指針。

std::vector<Person> v;
    v.push_back(Person(1, "z_name"));
    v.push_back(Person(2, "y_name"));
    v.push_back(Person(3, "x_name"));
    
    std::for_each(v.begin(), v.end(), std::mem_fun_ref(&Person::Print));

其他需要注意的問題

• std::string/std::wstring與vector<char>/vector<wchar_t>
  • 單線程情況下首選std::string/std::wstring
  • 多線程需注意string是否帶reference count，多線程下，避免分配和拷貝的reference count省下的開銷轉(zhuǎn)到了并發(fā)控制上，因此可考慮使用vector<char>/vector<wchar_t>，vector不帶reference conut
• new出的對象放入容器后，要在銷毀容器前delete那些對象
• 盡量用算法來替代手寫循環(huán)
• 容器的size（大?。┖蚦apacity（容量）是不一樣的，可以使用swap為容器縮水
• 在有對象繼承的情況下，建立指針的容器而不是對象的容器

8.泛型算法 非變易算法

非變易算法

非變易算法是一系列模板函數(shù)，在不改變操作對象的前提下對元素進行處理。查找、子序列搜索、統(tǒng)計、匹配等等。

• for_each

template<class _InIt, class _Fn1> inline
_Fn1 for_each(_InIt _First, _InIt _Last, _Fn1 _Func)

在區(qū)間[First，_Last)上對每一個元素應(yīng)用_Func函數(shù)。

• find

template<class _InIt, class _Ty> inline
_InIt find(_InIt _First, _InIt _Last, const _Ty& _Val)

在區(qū)間[First，_Last)中，如果*it=Value則返回該it，沒有找到則返回_Last。

• find_if

template<class _InIt, class _Pr> inline
_InIt find_if(_InIt _First, _InIt _Last, _Pr _Pred)

在區(qū)間[First，_Last)中，如果_Pred(*it)=true 則返回該it，沒有找到則返回_Last。

• adjacent_find(1)

template<class _FwdIt> inline
_FwdIt adjacent_find(_FwdIt _First, _FwdIt _Last)

在區(qū)間[First，_Last)中，如果*it==*(it + 1)則返回該it，沒有找到則返回_Last。

• adjacent_find(2)

template<class _FwdIt, class _Pr> inline
_FwdIt adjacent_find(_FwdIt _First, _FwdIt _Last, _Pr _Pred)

在區(qū)間[First，_Last)中，如果_Pred(*it, *(it + 1))==true 則返回該it，沒有找到則返回_Last。相當(dāng)于adjacent_find(1)的_Pred默認(rèn)使用的是equal_to。

• find_first_of(1)

template<class _FwdIt1, class _FwdIt2> inline
_FwdIt1 find_first_of(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2)

在區(qū)間[First1，_Last1)中的it1，使得對于區(qū)間[First2，_Last2)中某個it2，滿足 *it1 == *it2 則返回it1，如果沒有找到則返回_Last1。

• find_first_of(2)

template<class _FwdIt1, class _FwdIt2， class _Pr> inline
_FwdIt1 find_first_of(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred)

在區(qū)間[First1，_Last1)中的it1，使得對于區(qū)間[First2，_Last2)中某個it2，滿足 _Pred(*it1, *it2) == true, 則返回it1，如果沒有找到則返回_Last1。

• count

template<class _InIt, class _Ty> inline
typename iterator_traits<_InIt>::difference_type count(_InIt _First, _InIt _Last, const _Ty& _Val)

返回在區(qū)間[First，_Last)中滿足 *it==—Val 的迭代器的個數(shù)。

• count_if

template<class _InIt, class _Pr> inline
typename iterator_traits<_InIt>::difference_type count_if(_InIt _First, _InIt _Last, _Pr _Pred

返回在區(qū)間[First，_Las1)中滿足 _Pred(*it)==true 的迭代器的個數(shù)。

• mismatch(1)

template<class _InIt1, class _InIt2> inline pair<_InIt1, _InIt2>
mismatch(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _InIt2 _Last2)

在區(qū)間[First1，_Last1)中的it1，滿足 *it1 != *(_First2 + (it1 - _First1)), 返回pair<it1, _First2 + (it1 - _First1)>，如果找不到則返回pair<_Last1, _First2 + (_Last1 - _First1)>。

• mismatch(2)

template<class _InIt1, class _InIt2, class _Pr> inline pair<_InIt1, _InIt2>
mismatch(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _InIt2 _Last2, _Pr _Pred)

在區(qū)間[First1，_Last1)中的it1，滿足 _Pred(*it1 ,*(_First2 + (it1 - _First1)))==false, 返回pair<it1, _First2 + (it1 - _First1)>，如果找不到則返回pair<_Last1, _First2 + (_Last1 - _First1)>。

• equal(1)

template<class _InIt1, class _InIt2> inline 
bool equal(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _InIt2 _Last2)

在區(qū)間[First1，_Last1)中滿足*it1 == *(_First2 + (it1 - _First1))則返回true，否則返回false。

• equal(2)

template<class _InIt1, class _InIt2, class _Pr> inline 
bool equal(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _InIt2 _Last2, _Pr _Pred)

在區(qū)間[First1，_Last1)中滿足_Pred(*it1, *(_First2 + (it1 - _First1)))==true,則返回true，否則返回false。

• search(1)

template<class _FwdIt1, class _FwdIt2> inline
_FwdIt1 search(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2)

在區(qū)間[First1，_Last1)中的it1，對于每一個在區(qū)間[First2，_Last2)中的it2，滿足*(it1 + (it2 - _First2)) == *it2; 則返回it1，否在返回_Last1。

• search(2)

template<class _FwdIt1, class _FwdIt2, class _Pr> inline
_FwdIt1 search(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred)

在區(qū)間[First1，_Last1)中的it1，對于每一個在區(qū)間[First2，_Last2)中的it2，滿足_Pred(*(it1 + (it2 - _First2)), *it2) == true; 則返回it1，否在返回_Last1。