1.關(guān)聯(lián)容器map與set

關(guān)聯(lián)容器（Associative containers）支持通過鍵來高效地查找和讀取元素。兩個基本的關(guān)聯(lián)容器類型是 map 和 set。

關(guān)聯(lián)容器和順序容器的本質(zhì)差別在于：關(guān)聯(lián)容器通過鍵（key）存儲和讀取元素，而順序容器則通過元素在容器中的位置順序存儲和訪問元素。

map 的元素以鍵－值（key-value）對的形式組織：鍵用作元素在 map 中的索引，而值則表示所存儲和讀取的數(shù)據(jù)。set 存儲的對象本身既是key又是value。

set 和 map 類型的對象所包含的元素都具有不同的鍵，不允許為同一個鍵添加第二個元素。如果一個鍵必須對應(yīng)多個實(shí)例，則需使用 multimap 或 multiset，這兩種類型允許多個元素?fù)碛邢嗤逆I。

map與set存儲的對象必須是具備可排序性的，它們均默認(rèn)采用less定義排序行為，存儲對象必須具備operator<行為。

• set需要注意的問題
  例如

struct Programmer
{
    Programmer(const int id,const std::wstring name)
        :Id(id),Name(name){}    
    int Id;
    void set_name(const std::wstring name)
    {
        Name = name;
    }
    std::wstring Name;
};

struct ProgrammerIdGreater:public std::binary_function<Programmer,Programmer,bool>
{
    bool operator() (const Programmer& p1,const Programmer& p2) const 
    {
        return p1.Id > p2.Id ? true : false;
    }
};
int main(){
    std::set<Programmer,ProgrammerIdGreater> set1 = {
        Programmer(1,L"Scott Meyers"),
        Programmer(2,L"Martin Fowler"),
        Programmer(3,L"Bill Gates"),
        Programmer(4,L"P.J. Plaught"),
        Programmer(5,L"Stanley B. Lippman"),
        Programmer(6,L"Andrei Alexandrescu")    
    };
...
}

用于排序的成員（比如Programmer對象的Id，也就是“真正的key”）不可改變。
除了“真正的key”，其他成員可以改變但需要特殊手段。比如將上面set1中Programmer(3,L"Bill Gates")對象的Name重新設(shè)置為“Tom”：

    std::set<Programmer,ProgrammerIdGreater>::iterator it1 = set1.find(Programmer(3,L"Bill Gates"));
    if(it1 != set1.end())
        it1->set_name(L"Tom");
//上述代碼無法通過編譯

可行的方法是：

    std::set<Programmer,ProgrammerIdGreater>::iterator it1 = set1.find(Programmer(3,L"Bill Gates"));
    if(it1 != set1.end())
        const_cast<Programmer&> (*it1).set_name(L"Tom");
//成功編譯

2.仿函數(shù)（Functors）

仿函數(shù)又稱為函數(shù)對象，其作用相當(dāng)于一個函數(shù)指針。前面例中

std::set<Programmer,ProgrammerIdGreater> set1 = {...};

參數(shù)ProgrammerIdGreater即為仿函數(shù)

仿函數(shù)本質(zhì)上是一種具有函數(shù)特質(zhì)的對象， 也即可以像使用函數(shù)一樣使用該對象。怎么樣做？重載operator()運(yùn)算符即可，有了這個運(yùn)算符，我們就可以在仿函數(shù)對象后面加上一對小括號，以此調(diào)用仿函數(shù)所定義的perator()。

為什么要有仿函數(shù)？
在算法的設(shè)計過程中，我們會發(fā)現(xiàn)其本質(zhì)往往是不變的（例如排序算法的思想），變化的除了數(shù)據(jù)之外還有操作（例如排序中不一定是比較大小，也可以是兩兩之間滿足某種關(guān)系），仿函數(shù)就是為了這種情況產(chǎn)生的，它替代原來需要函數(shù)指針的地方，把這種操作或者策略傳給算法，使得算法抽象性更高，也就更通用。

為什么不用函數(shù)指針？
很簡單的解釋是抽象性不夠，更進(jìn)一步說是它無法配接，也就是可以將操作配接在一起變換為更復(fù)雜的操作，仿函數(shù)則可以輕松實(shí)現(xiàn)這些配接，使得其功能異常強(qiáng)大。

仿函數(shù)在實(shí)現(xiàn)上是一個對象，并且如上所述重載了operator()運(yùn)算符，所有的仿函數(shù)如果是一元的都繼承自unary_function，二元則繼承自binary_function,因?yàn)槔^承自這兩個函數(shù)的仿函數(shù)均定義了相應(yīng)型別供配接時使用，也就具有了配接能力。

自定義的仿函數(shù)必須重載operator()，例如前面

struct ProgrammerIdGreater:public std::binary_function<Programmer,Programmer,bool>
{
    bool operator() (const Programmer& p1,const Programmer& p2) const 
    {
        return p1.Id > p2.Id ? true : false;
    }
};