侯捷STL课程及源码剖析学习1

1.C++标准库和STL

　　C++标准库以header files形式呈现：

1. C++标准库的header files不带后缀名（.h），例如#include <vector>
2. 新式C header files 不带后缀名.h，例如#include<cstdio>
3. 旧式C header files （带有后缀名.h）仍然可用，例如#include <stdio.h>
4. 新式headers内的组件封装于namespace “std”。     using namespace std；或者以 using std::cout;的形式
5. 旧式headers 内的组件不封装于namespace "std"

　　在标准库中，标准模板库STL（Standard Template Library），占据了标准库70%，80%以上的内容。

C++ 标准库的范围大于STL的范围。STL的核心思想是泛型编程（Generic Programming）。

重要资源：

网站：

• http://en.cppreference.com/w/
• http://www.cplusplus.com/
• https://gcc.gnu.org/

书籍：

• The C++ standard Library second edition；
• STL 源码剖析

2.STL 六大组件

STL分为六大组件：

• 容器(container)：常用数据结构，大致分为两类，序列容器，如vector，list，deque，关联容器，如set，map。在实现上，是类模板(class template)
• 迭代器(iterator)：一套访问容器的接口，行为类似于指针。它为不同算法提供的相对统一的容器访问方式，使得设计算法时无需关注过多关注数据。（“算法”指广义的算法，操作数据的逻辑代码都可认为是算法）
• 算法(algorithm)：提供一套常用的算法，如sort，search，copy，erase … 在实现上，可以认为是一种函数模板(function template)。
• 配置器(allocator)：为容器提供空间配置和释放，对象构造和析构的服务，也是一个class template。
• 仿函数(functor)：作为函数使用的对象，用于泛化算法中的操作。
• 配接器(adapter)：将一种容器修饰为功能不同的另一种容器，如以容器vector为基础，在其上实现stack，stack的行为也是一种容器。这就是一种配接器。除此之外，还有迭代器配接器和仿函数配接器。

STL 六大组件的交互关系

• Container 通过 Allocator 取得数据储存空间
• Algorithm 通过 Iterator 存取 Container 内容
• Functor 可以协助 Algorithm 完成不同的策略变化
• Adapter 可以修饰或套接 Functor、Iterator。

#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>

using namespace std;

int main()
{
    int ia[6] = { 27, 210, 12, 47, 109, 83 }；
        vector<int, allocator<int>> vi(ia, ia + 6);

    cout << count_if(vi.begin(), vi.end(),
        not1(bind2nd（less<int>(), 40)));

    return 0;
}

上述这段代码用到了STL的六大部件：

allocator 是分配器，vector 是容器，count_if 是算法

vi.begin() 是迭代器

not1，bind2nd是适配器

less<int> 是仿函数

• 理解容器的前闭后开的设计。迭代器类似于指针，很多操作和指针差不多++,--运算。vec.begin(),vec.end()指向容器最后一个元素的下一个位置，解引用*（vec.end()）错误！
• auto关键字的应用

 c++知识点

临时对象

//临时对象的产生与运用
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

template <typename T>
class print
{
public:
  void operator()(const T& elem) // operator()重载
  {
    cout<<elem<<' ';
  }
};

int main()
{
    int ia[6] = {0,1,2,3,4,5};
    vector<int> iv(ia, ia+6);

    // print<int>() 是一个临时对象，不是函数调用
    for_each(iv.begin(), iv.end(), print<int>());

    cout<<endl;

  return 1;
}

静态整数成员变量

//静态常量整数初始化
#include <iostream>
using namespace std;

template <typename T>
class testClass
{

public:

    static const int _datai = 5;
    static const long _datal = 3L;
    static const char _datac = 'c';
};

int main()
{
    cout<<testClass<int>::_datai<<endl;
    cout<<testClass<long>::_datal<<endl;
    cout<<testClass<char>::_datac<<endl;

    return 0;
}

重载自增、自减、操作符

#include <iostream>
using namespace std;

class INT
{
    friend ostream& operator<<(ostream& os, const INT& i);

public:
    INT(int i) : m_i(i) { };

    //  prefix : increment and then fetch
    //  ++INT
    INT& operator++()
    {
        ++(this->m_i);
        return *this;
    }

    //  postfix : fetch and then increment
    //  INT++
    const INT operator++(int)
    {
        INT temp = *this;
        ++(*this);
        return temp;
    }

    //  prefix  :   decrement and then fetch
    //  --INT
    INT& operator--()
    {
        --(this->m_i);
        return *this;
    }

    //  prefix  :   fetch and then decrement
    const INT operator--(int)
    {
        INT temp = *this;
        --(*this);
        return temp;
    }

    int& operator*() const
    {
        return (int&)m_i;
    }

private:
    int m_i;
};

ostream& operator<<(ostream& os, const INT& i)
{
    os <<'[' <<i.m_i <<']';
    return os;
}

int main()
{
    INT I(5);
    cout <<I++ <<endl;
    cout <<++I <<endl;
    cout <<I-- <<endl;
    cout <<--I <<endl;
    cout <<*I <<endl;

  return 1;
}

operator() 重载

#include <cstdlib>
#include <iostream>

using namespace std;

int fcmp(const void *elem1, const void *elem2);

int main( )
{
    int ia[] = {32, 92, 67, 58, 10, 4, 25, 52, 59, 54};

    for(int i = 0; i < 10; i++)
    {
        cout <<ia[i] <<" ";
    }
    cout <<endl;

    qsort(ia, sizeof(ia)/sizeof(ia[0]), sizeof(ia[0]), fcmp);


    for(int i = 0; i < 10; i++)
    {
        cout <<ia[i] <<" ";
    }
    cout <<endl;

}

int fcmp(const void *elem1, const void *elem2)
{
    const int *i1 = (const int *)elem1;
    const int *i2 = (const int *)elem2;

    return (*i1 - *i2);
}

仿函数，函数对象

#include <iostream>
using namespace std;

//  由于将operator()重载了, 因此plus成了一个仿函数
template <class T>
struct myplus
{
    T operator()(const T& x, const T& y) const
    {
        return x + y;
    }
};

//  由于将operator()重载了, 因此minus成了一个仿函数

template <class T>
struct myminus
{
    T operator()(const T& x, const T& y) const
    {
        return x - y;
    }
};

int main()
{
    //  创建仿函数对象
    myplus<int> plusobj;
    myminus<int> minusobj;

    cout<<plusobj(3,5)<<endl;
    cout<<minusobj(3,5)<<endl;

    cout<<myplus<int>()(43,50)<<endl;
    cout<<myminus<int>()(43,50)<<endl;

    return 1;
}

3.容器的相关知识

3.1容器的结构与分类

容器按在内存中的存储结构分为三种：顺序容器（Sequence Container）、关联容器（Associative Container）、和无序容器（Unordered Container）。其中的无序容器是C++ 11提出的，实际上无序容器也属于关联容器，使用哈希表构成。

• Array数组容器，大小固定的
• Deque:两段都可以进行插入删除操作，但是从内存上讲不通，怎么实现的要从后面的学习知道。
• List:是一个双向的循环链表，注意是双向的。
• Forward-List:单向链表，当能用单向链表的时候尽量用，可以减少内存空间，一个指针在32位pc上占4个字节，当数据量很多上百万，不可忽略！
• Set键值都一样，MultiSet允许元素有重复。
• Set/Map用红黑树实现，RB-tree是自平衡的二叉树。
• Unorder Containers:是C++标准库里卖的内容。
• 根据这些图例，可以知道这些容器在内存用到的数据结构是什么样的。
• HashTable实现方法很多，但基本都用Separate Chaining(分离链地址法实现)。

容器测试辅助函数 

using std::cin;
using std::cout;
using std::string;

long get_a_target_long()
{
    long target = 0;

    cout << "target (0~" << RAND_MAX << "): ";
    cin >> target;
    return target;
}

string get_a_target_string()
{
    long target = 0;
    char buf[10];

    cout << "target (0~" << RAND_MAX << "): ";
    cin >> target;
    snprintf(buf, 10, "%d", target);
    return string(buf);
}

int compareLongs(const void* a, const void* b)
{
    return (*(long*)a - *(long*)b);
}

int compareStrings(const void* a, const void* b)
{
    if (*(string*)a > *(string*)b)
        return 1;
    else if (*(string*)a < *(string*)b)
        return -1;
    else
        return 0;
}

 注：Windows环境下 应使用函数：_snprintf(buf, 10, "%d", target);

3.2顺序容器

顺序容器：它将单一类型元素聚集起来成为容器，然后根据位置来存储和访问这些元素。

标准库提供了一下几种顺序容器：array、vector、list、forward_list、slist、deque、stack和queue，他们的差别在于访问元素访问元素的方式，以及添加或删除元素相关操作的运行代价。array是C++11的新内容，功能比内置数组更加强大，可以以对象为单位存储数据，vector支持快速随机访问，list支持快速插入/删除，deque是一个双端队列，queue和stack在STL中都是基于deque来实现。

顺序容器类型

vector

• 可变大小数组；
• 支持快速随机访问；
• 在尾部之外的位置插入或删除元素可能很慢；       

deque

• 双端队列；
• 支持快速随机访问；
• 在头尾位置插入/删除速度很快；

list

• 双向链表；
• 只支持双向顺序访问；
• 在list中任何位置进行插入/删除操作速度都很快；

forward_list

• 单向链表；
• 只支持单向顺序访问；
• 在链表任何位置进行插入/删除操作速度都很快；

array

• 固定大小数组；
• 支持快速随机访问；
• 不能添加或删除元素；

string

• 与vector相似的容器，但专门用于保存字符；
• 随机访问快；
• 在尾部插入/删除速度快；

• array 测试代码

#include <array>
#include <iostream>
#include <ctime> 
#include <cstdlib> //qsort, bsearch, NULL
#include <cstdio>  
namespace jj01
{
    void test_array()
    {
        cout << "
test_array().......... 
";
 
        array<long, ASIZE> c;
 
        clock_t timeStart = clock();
        for (long i = 0; i< ASIZE; ++i) {
            c[i] = rand();
        }
        cout << "milli-seconds : " << (clock() - timeStart) << endl;  //
        cout << "array.size()= " << c.size() << endl;
        cout << "array.front()= " << c.front() << endl;
        cout << "array.back()= " << c.back() << endl;
        cout << "array.data()= " << c.data() << endl;
 
        long target = get_a_target_long();
 
        timeStart = clock();
        ::qsort(c.data(), ASIZE, sizeof(long), compareLongs);
        long* pItem = (long*)::bsearch(&target, (c.data()), ASIZE, sizeof(long), compareLongs);
        cout << "qsort()+bsearch(), milli-seconds : " << (clock() - timeStart) << endl;   //    
        if (pItem != NULL)
            cout << "found, " << *pItem << endl;
        else
            cout << "not found! " << endl;
    }
}

　　注：array 为c++11 新增容器，档测试数据 ASIZE 较大时，在vs2013运行时报出堆栈溢出错误，需要在工程属性中更改堆栈默认大小（默认为1M）。

测试结果

test_array()..........
milli-seconds : 32
array.size()= 500000
array.front()= 41
array.back()= 29794
array.data()= 0x47970
target (0~32767): 123
qsort()+bsearch(), milli-seconds : 263
found, 123

• vector 测试

#include <vector>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime> 
#include <algorithm>     //sort()
namespace jj02
{
    void test_vector(long& value)
    {
        cout << "
test_vector().......... 
";

        vector<string> c;
        char buf[10];

        clock_t timeStart = clock();
        for (long i = 0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                c.push_back(string(buf));
            }
            catch (exception& p) {
                cout << "i=" << i << " " << p.what() << endl;
                //曾经最高 i=58389486 then std::bad_alloc
                abort();
            }
        }
        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "vector.max_size()= " << c.max_size() << endl;    //1073747823
        cout << "vector.size()= " << c.size() << endl;
        cout << "vector.front()= " << c.front() << endl;
        cout << "vector.back()= " << c.back() << endl;
        cout << "vector.data()= " << c.data() << endl;
        cout << "vector.capacity()= " << c.capacity() << endl << endl;


        string target = get_a_target_string();
        {
            timeStart = clock();
            auto pItem = find(c.begin(), c.end(), target);
            cout << "std::find(), milli-seconds : " << (clock() - timeStart) << endl;

            if (pItem != c.end())
                cout << "found, " << *pItem << endl << endl;
            else
                cout << "not found! " << endl << endl;
        }

        {
            timeStart = clock();
            sort(c.begin(), c.end());
            cout << "sort(), milli-seconds : " << (clock() - timeStart) << endl;

            timeStart = clock();
            string* pItem = (string*)::bsearch(&target, (c.data()),
                c.size(), sizeof(string), compareStrings);
            cout << "bsearch(), milli-seconds : " << (clock() - timeStart) << endl;

            if (pItem != NULL)
                cout << "found, " << *pItem << endl << endl;
            else
                cout << "not found! " << endl << endl;
        }

        c.clear();
        test_moveable(vector<MyString>(), vector<MyStrNoMove>(), value);
    }
}

 ::find()模板函数，加冒号表明是全局函数，当没有冒号时，编译器在当前没有找到，到全局去找。

测试结果

how many elements: 1000000

test_vector()................
milli-seconds : 750
vetor.max_size() = 576460752303423487
vector.size() = 1000000
vector.front() = 41
vetor.back() = 12679
vector.data() = 0x42c0040
vector.capacity()= 1048576

target (0~32767): 23456
std::find(),milli-seconds : 5
find , 23456

sort(), milli-seconds : 6069
bsearch(), milli-seconds : 1
found, 23456

• list 测试

#include <list>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <algorithm> //find()
#include <iostream>
#include <ctime> 
namespace jj03
{
    void test_list(long& value)
    {
        cout << "
test_list().......... 
";

        list<string> c;
        char buf[10];
        
        clock_t timeStart = clock();
        for (long i = 0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                c.push_back(string(buf));                
            }
            catch (exception& p) {
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "list.size()= " << c.size() << endl;
        cout << "list.max_size()= " << c.max_size() << endl;    //357913941
        cout << "list.front()= " << c.front() << endl;
        cout << "list.back()= " << c.back() << endl;

        string target = get_a_target_string();
        timeStart = clock();
        auto pItem = find(c.begin(), c.end(), target);
        cout << "std::find(), milli-seconds : " << (clock() - timeStart) << endl;

        if (pItem != c.end())
            cout << "found, " << *pItem << endl;
        else
            cout << "not found! " << endl;

        timeStart = clock();
        c.sort();
        cout << "c.sort(), milli-seconds : " << (clock() - timeStart) << endl;
        
    }
}

 测试结果

test_list()..........
milli-seconds : 496
list.size()= 1000000
list.max_size()= 38430716820228232
list.front()= 21384
list.back()= 1461
target (0~32767): 23456
std::find(), milli-seconds : 1
found, 23456
c.sort(), milli-seconds : 4701

• forward_list 测试 

#include <forward_list>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime> 
namespace jj04
{
    void test_forward_list(long& value)
    {
        cout << "
test_forward_list().......... 
";

        forward_list<string> c;
        char buf[10];

        clock_t timeStart = clock();
        for (long i = 0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                c.push_front(string(buf));
            }
            catch (exception& p) {
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "forward_list.max_size()= " << c.max_size() << endl;  //536870911
        cout << "forward_list.front()= " << c.front() << endl;


        string target = get_a_target_string();
        timeStart = clock();
        auto pItem = find(c.begin(), c.end(), target);
        cout << "std::find(), milli-seconds : " << (clock() - timeStart) << endl;

        if (pItem != c.end())
            cout << "found, " << *pItem << endl;
        else
            cout << "not found! " << endl;

        timeStart = clock();
        c.sort();
        cout << "c.sort(), milli-seconds : " << (clock() - timeStart) << endl;

        c.clear();
    }
}

 测试结果

how many elements: 1000000

test_forward_list()..........
milli-seconds : 701
forward_list.max_size()= 461168601842738790
forward_list.front()= 12679
target (0~32767): 23456
std::find(), milli-seconds : 4
found, 23456
c.sort(), milli-seconds : 5310

• slist 测试 （非c++标准） 

Gnu C之前的单链表,forward-list是C++11才出现的

#include<extslist>头文件

#include <extslist>
//注意, 上一行并没有引发警告讯息如 #include <exthash_set> 所引发者： 
//...4.9.2includec++ackwardackward_warning.h    
//[Warning] ...

#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime> 
namespace jj10
{
    void test_slist(long& value)
    {
        cout << "
test_slist().......... 
";

        __gnu_cxx::slist<string> c;
        char buf[10];

        clock_t timeStart = clock();
        for (long i = 0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                c.push_front(string(buf));
            }
            catch (exception& p) {
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock() - timeStart) << endl;
    }
}

•  deque 测试 

#include <deque>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime> 
namespace jj05
{
    void test_deque(long& value)
    {
        cout << "
test_deque().......... 
";

        deque<string> c;
        char buf[10];

        clock_t timeStart = clock();
        for (long i = 0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                c.push_back(string(buf));
            }
            catch (exception& p) {
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "deque.size()= " << c.size() << endl;
        cout << "deque.front()= " << c.front() << endl;
        cout << "deque.back()= " << c.back() << endl;
        cout << "deque.max_size()= " << c.max_size() << endl;    //1073741821    

        string target = get_a_target_string();
        timeStart = clock();
        auto pItem = find(c.begin(), c.end(), target);
        cout << "std::find(), milli-seconds : " << (clock() - timeStart) << endl;

        if (pItem != c.end())
            cout << "found, " << *pItem << endl;
        else
            cout << "not found! " << endl;

        timeStart = clock();
        sort(c.begin(), c.end());
        cout << "sort(), milli-seconds : " << (clock() - timeStart) << endl;

        c.clear();
        test_moveable(deque<MyString>(), deque<MyStrNoMove>(), value);
    }
}

 测试结果

how many elements: 100000

test_deque()..........
milli-seconds : 49
deque.size()= 100000
deque.front()= 41
deque.back()= 1629
deque.max_size()= 576460752303423487
target (0~32767): 3456
std::find(), milli-seconds : 9
found, 3456
sort(), milli-seconds : 668

• stack 测试 

#include <stack>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime> 
namespace jj17
{
    void test_stack(long& value)
    {
        cout << "
test_stack().......... 
";

        stack<string> c;
        char buf[10];

        clock_t timeStart = clock();
        for (long i = 0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                c.push(string(buf));
            }
            catch (exception& p) {
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "stack.size()= " << c.size() << endl;
        cout << "stack.top()= " << c.top() << endl;
        c.pop();
        cout << "stack.size()= " << c.size() << endl;
        cout << "stack.top()= " << c.top() << endl;


        {
            stack<string, list<string>> c;        //以 list 为底层 
            for (long i = 0; i< 10; ++i) {
                snprintf(buf, 10, "%d", rand());
                c.push(string(buf));
            }
            cout << "stack.size()= " << c.size() << endl;
            cout << "stack.top()= " << c.top() << endl;
            c.pop();
            cout << "stack.size()= " << c.size() << endl;
            cout << "stack.top()= " << c.top() << endl;
        }

        {
            stack<string, vector<string>> c;    //以 vector 为底层 
            for (long i = 0; i< 10; ++i) {
                snprintf(buf, 10, "%d", rand());
                c.push(string(buf));
            }
            cout << "stack.size()= " << c.size() << endl;
            cout << "stack.top()= " << c.top() << endl;
            c.pop();
            cout << "stack.size()= " << c.size() << endl;
            cout << "stack.top()= " << c.top() << endl;
        }

        {
            stack<string, set<string>> c;    //以 set 为底层 
            /*!
            for(long i=0; i< 10; ++i) {
            snprintf(buf, 10, "%d", rand());
            c.push(string(buf));
            }
            cout << "stack.size()= " << c.size() << endl;
            cout << "stack.top()= " << c.top() << endl;
            c.pop();
            cout << "stack.size()= " << c.size() << endl;
            cout << "stack.top()= " << c.top() << endl;

            //[Error] 'class std::set<std::basic_string<char> >' has no member named 'push_back'
            //[Error] 'class std::set<std::basic_string<char> >' has no member named 'back'
            //[Error] 'class std::set<std::basic_string<char> >' has no member named 'pop_back'
            */
        }

        //!stack<string, map(string>> c5;    ////以 map 为底层, [Error] template argument 2 is invalid
        //!stack<string>::iterator ite1;      //[Error] 'iterator' is not a member of 'std::stack<std::basic_string<char> >'

    }
}

•  queue 测试 

#include <queue>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime> 
namespace jj18
{
    void test_queue(long& value)
    {
        cout << "
test_queue().......... 
";

        queue<string> c;
        char buf[10];

        clock_t timeStart = clock();
        for (long i = 0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                c.push(string(buf));
            }
            catch (exception& p) {
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "queue.size()= " << c.size() << endl;
        cout << "queue.front()= " << c.front() << endl;
        cout << "queue.back()= " << c.back() << endl;
        c.pop();
        cout << "queue.size()= " << c.size() << endl;
        cout << "queue.front()= " << c.front() << endl;
        cout << "queue.back()= " << c.back() << endl;


        {
            queue<string, list<string>> c;        //以 list 为底层 
            for (long i = 0; i< 10; ++i) {
                snprintf(buf, 10, "%d", rand());
                c.push(string(buf));
            }
            cout << "queue.size()= " << c.size() << endl;
            cout << "queue.front()= " << c.front() << endl;
            cout << "queue.back()= " << c.back() << endl;
            c.pop();
            cout << "queue.size()= " << c.size() << endl;
            cout << "queue.front()= " << c.front() << endl;
            cout << "queue.back()= " << c.back() << endl;
        }

        {
            queue<string, vector<string>> c;    //以 vector 为底层 
            for (long i = 0; i< 10; ++i) {
                snprintf(buf, 10, "%d", rand());
                c.push(string(buf));
            }
            cout << "queue.size()= " << c.size() << endl;
            cout << "queue.front()= " << c.front() << endl;
            cout << "queue.back()= " << c.back() << endl;
            //!c.pop();  //[Error] 'class std::vector<std::basic_string<char> >' has no member named 'pop_front'
            cout << "queue.size()= " << c.size() << endl;
            cout << "queue.front()= " << c.front() << endl;
            cout << "queue.back()= " << c.back() << endl;
        }

        {
            queue<string, set<string>> c;        //以 set 为底层 
            /*!
            for(long i=0; i< 10; ++i) {
            snprintf(buf, 10, "%d", rand());
            c.push(string(buf));
            }
            cout << "queue.size()= " << c.size() << endl;
            cout << "queue.front()= " << c.front() << endl;
            cout << "queue.back()= " << c.back() << endl;
            c.pop();
            cout << "queue.size()= " << c.size() << endl;
            cout << "queue.front()= " << c.front() << endl;
            cout << "queue.back()= " << c.back() << endl;
            //[Error] 'class std::set<std::basic_string<char> >' has no member named 'push_back'
            //[Error] 'class std::set<std::basic_string<char> >' has no member named 'front'
            //[Error] 'class std::set<std::basic_string<char> >' has no member named 'pop_front'
            */
        }

        //! queue<string, map<string>> c5;    //以 map 为底层, [Error] template argument 2 is invalid
        //! queue<string>::iterator ite1;      //[Error] 'iterator' is not a member of 'std::queue<std::basic_string<char> >'    
    }
}

3.3关联容器

　　在STL中关联容器使用红黑树来实现，因为不是顺序结构，因而不能使用上面提到的push和pop函数，使用insert和erase函数来实现元素的插入删除操作。

　　关联容器支持通过键来高效地查找和读取元素，两个基本的关联容器类型是map和set。map的元素以键-值（key-value）对的形式组织：键用于元素在map中的索引，而值则表示所存储和读取的数据。set仅包含一个键，并有效地支持关于某个键是否存在的查询。map可理解为字典，set可理解为一类元素的集合。

关联容器和顺序容器的本质差别在于：关联容器通过键（key）存储和读取元素，而顺序容器则通过元素在容器中的位置顺序存储和访问元素。

set 和 map 类型的对象所包含的元素都具有不同的键，不允许为同一个键添加第二个元素。如果一个键必须对应多个实例，则需使用 multimap 或 multiset，这两种类型允许多个元素拥有相同的键。

• multiset ,set测试 

void test_multiset(long& value)
    {
        cout << "
test_multiset().......... 
";

        multiset<string> c;
        char buf[10];
        clock_t timeStart = clock();
        for (long i = 0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                c.insert(string(buf));
            }
            catch (exception& p) {
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "multiset.size()= " << c.size() << endl;
        cout << "multiset.max_size()= " << c.max_size() << endl;    //214748364

        string target = get_a_target_string();
        {
            timeStart = clock();
            auto pItem = find(c.begin(), c.end(), target);    //比 c.find(...) 慢很多
            cout << "std::find(), milli-seconds : " << (clock() - timeStart) << endl;
            if (pItem != c.end())
                cout << "found, " << *pItem << endl;
            else
                cout << "not found! " << endl;
        }

        {
            timeStart = clock();
            auto pItem = c.find(target);        //比 std::find(...) 快很多
            cout << "c.find(), milli-seconds : " << (clock() - timeStart) << endl;
            if (pItem != c.end())
                cout << "found, " << *pItem << endl;
            else
                cout << "not found! " << endl;
        }

//        c.clear();
//        test_moveable(multiset<MyString>(), multiset<MyStrNoMove>(), value);
    }

void test_set(long& value)
    {
        cout << "
test_set().......... 
";

        set<string> c;
        char buf[10];

        clock_t timeStart = clock();
        for (long i = 0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                c.insert(string(buf));
            }
            catch (exception& p) {
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "set.size()= " << c.size() << endl;
        cout << "set.max_size()= " << c.max_size() << endl;       //214748364

        string target = get_a_target_string();
        {
            timeStart = clock();
            auto pItem = find(c.begin(), c.end(), target);    //比 c.find(...) 慢很多
            cout << "std::find(), milli-seconds : " << (clock() - timeStart) << endl;
            if (pItem != c.end())
                cout << "found, " << *pItem << endl;
            else
                cout << "not found! " << endl;
        }

        {
            timeStart = clock();
            auto pItem = c.find(target);        //比 std::find(...) 快很多
            cout << "c.find(), milli-seconds : " << (clock() - timeStart) << endl;
            if (pItem != c.end())
                cout << "found, " << *pItem << endl;
            else
                cout << "not found! " << endl;
        }
    }

• multimap,map 测试 

void test_unordered_map(long& value)
    {
        cout << "
test_unordered_map().......... 
";

        unordered_map<long, string> c;
        char buf[10];

        clock_t timeStart = clock();
        for (long i = 0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                c[i] = string(buf);
            }
            catch (exception& p) {
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "unordered_map.size()= " << c.size() << endl;    //357913941
        cout << "unordered_map.max_size()= " << c.max_size() << endl;

        long target = get_a_target_long();
        timeStart = clock();
        //! auto pItem = find(c.begin(), c.end(), target);    //map 不适用 std::find()
        auto pItem = c.find(target);

        cout << "c.find(), milli-seconds : " << (clock() - timeStart) << endl;
        if (pItem != c.end())
            cout << "found, value=" << (*pItem).second << endl;
        else
            cout << "not found! " << endl;
    }

void test_map(long& value)
    {
        cout << "
test_map().......... 
";

        map<long, string> c;
        char buf[10];

        clock_t timeStart = clock();
        for (long i = 0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                c[i] = string(buf);
            }
            catch (exception& p) {
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock() - timeStart) << endl;
        cout << "map.size()= " << c.size() << endl;
        cout << "map.max_size()= " << c.max_size() << endl;        //178956970

        long target = get_a_target_long();
        timeStart = clock();
        auto pItem = c.find(target);
        cout << "c.find(), milli-seconds : " << (clock() - timeStart) << endl;
        if (pItem != c.end())
            cout << "found, value=" << (*pItem).second << endl;
        else
            cout << "not found! " << endl;

        c.clear();
    }

3.4无序容器

　　严格意义上讲，无序容器也属于关联容器。

unordered_set,unordered_map,unordered_multiset,unordered_multimap