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

1.C++标准库和STL

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

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

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

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

重要资源：

网站：

书籍：

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课程及源码剖析学习1

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[] = { , , , , ,  }；

        vector<int, allocator<int>> vi(ia, ia + );

    cout << count_if(vi.begin(), vi.end(),

        not1(bind2nd（less<int>(), )));

    return ;

}

上述这段代码用到了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[] = {,,,,,};

     vector<int> iv(ia, ia+);

     // print<int>() 是一个临时对象，不是函数调用

     for_each(iv.begin(), iv.end(), print<int>());

     cout<<endl;

   return ;

 }

temp obj

静态整数成员变量

 //静态常量整数初始化

 #include <iostream>

 using namespace std;

 template <typename T>

 class testClass

 {

 public:

     static const int _datai = ;

     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 ;

 }

static constant

重载自增、自减、操作符

 #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();

     cout <<I++ <<endl;

     cout <<++I <<endl;

     cout <<I-- <<endl;

     cout <<--I <<endl;

     cout <<*I <<endl;

   return ;

 }

operator() 重载

 #include <cstdlib>

 #include <iostream>

 using namespace std;

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

 int main( )

 {

     int ia[] = {, , , , , , , , , };

     for(int i = ; i < ; i++)

     {

         cout <<ia[i] <<" ";

     }

     cout <<endl;

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

     for(int i = ; i < ; 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);

 }

qsort

仿函数，函数对象

 #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(,)<<endl;

     cout<<minusobj(,)<<endl;

     cout<<myplus<int>()(,)<<endl;

     cout<<myminus<int>()(,)<<endl;

     return ;

 }

functor

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 = ;

     cout << "target (0~" << RAND_MAX << "): ";

     cin >> target;

     return target;

 }

 string get_a_target_string()

 {

     long target = ;

     char buf[];

     cout << "target (0~" << RAND_MAX << "): ";

     cin >> target;

     snprintf(buf, , "%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 ;

     else if (*(string*)a < *(string*)b)

         return -;

     else

         return ;

 }

注：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 << "\ntest_array().......... \n";

         array<long, ASIZE> c;

         clock_t timeStart = clock();

         for (long i = ; 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

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

测试结果

test_array()..........

milli-seconds :

array.size()=

array.front()=

array.back()=

array.data()= 0x47970

target (~):

qsort()+bsearch(), milli-seconds :

found,

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 << "\ntest_vector().......... \n";

         vector<string> c;

         char buf[];

         clock_t timeStart = clock();

         for (long i = ; i< value; ++i)

         {

             try {

                 snprintf(buf, , "%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;    //

         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);

     }

 }

vector

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

测试结果

how many elements: 

test_vector()................

milli-seconds :

vetor.max_size() =

vector.size() =

vector.front() =

vetor.back() =

vector.data() = 0x42c0040

vector.capacity()= 

target (~):

std::find(),milli-seconds :

find , 

sort(), milli-seconds :

bsearch(), milli-seconds :

found,

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 << "\ntest_list().......... \n";

         list<string> c;

         char buf[];

         clock_t timeStart = clock();

         for (long i = ; i< value; ++i)

         {

             try {

                 snprintf(buf, , "%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;    //

         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;

     }

 }

list

测试结果

test_list()..........

milli-seconds :

list.size()=

list.max_size()=

list.front()=

list.back()=

target (~):

std::find(), milli-seconds :

found,

c.sort(), milli-seconds :

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 << "\ntest_forward_list().......... \n";

         forward_list<string> c;

         char buf[];

         clock_t timeStart = clock();

         for (long i = ; i< value; ++i)

         {

             try {

                 snprintf(buf, , "%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;  //

         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();

     }

 }

forward_list

测试结果

how many elements: 

test_forward_list()..........

milli-seconds :

forward_list.max_size()=

forward_list.front()=

target (~):

std::find(), milli-seconds :

found,

c.sort(), milli-seconds :

slist 测试（非c++标准）

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

#include<ext\slist>头文件

 #include <ext\slist>

 //注意, 上一行并没有引发警告讯息如 #include <ext\hash_set> 所引发者：

 //...\4.9.2\include\c++\backward\backward_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 << "\ntest_slist().......... \n";

         __gnu_cxx::slist<string> c;

         char buf[];

         clock_t timeStart = clock();

         for (long i = ; i< value; ++i)

         {

             try {

                 snprintf(buf, , "%d", rand());

                 c.push_front(string(buf));

             }

             catch (exception& p) {

                 cout << "i=" << i << " " << p.what() << endl;

                 abort();

             }

         }

         cout << "milli-seconds : " << (clock() - timeStart) << endl;

     }

 }

slist

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 << "\ntest_deque().......... \n";

         deque<string> c;

         char buf[];

         clock_t timeStart = clock();

         for (long i = ; i< value; ++i)

         {

             try {

                 snprintf(buf, , "%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);

     }

 }

deque

测试结果

how many elements: 

test_deque()..........

milli-seconds :

deque.size()=

deque.front()=

deque.back()=

deque.max_size()=

target (~):

std::find(), milli-seconds :

found,

sort(), milli-seconds :

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 << "\ntest_stack().......... \n";

         stack<string> c;

         char buf[];

         clock_t timeStart = clock();

         for (long i = ; i< value; ++i)

         {

             try {

                 snprintf(buf, , "%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 = ; i< ; ++i) {

                 snprintf(buf, , "%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 = ; i< ; ++i) {

                 snprintf(buf, , "%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> >'

     }

 }

stack

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 << "\ntest_queue().......... \n";

         queue<string> c;

         char buf[];

         clock_t timeStart = clock();

         for (long i = ; i< value; ++i)

         {

             try {

                 snprintf(buf, , "%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 = ; i< ; ++i) {

                 snprintf(buf, , "%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 = ; i< ; ++i) {

                 snprintf(buf, , "%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> >'

     }

 }

queue

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 << "\ntest_multiset().......... \n";

         multiset<string> c;

         char buf[];

         clock_t timeStart = clock();

         for (long i = ; i< value; ++i)

         {

             try {

                 snprintf(buf, , "%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;    //

         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 << "\ntest_set().......... \n";

         set<string> c;

         char buf[];

         clock_t timeStart = clock();

         for (long i = ; i< value; ++i)

         {

             try {

                 snprintf(buf, , "%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;       //

         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;

         }

     }

set

multimap,map 测试

 void test_unordered_map(long& value)

     {

         cout << "\ntest_unordered_map().......... \n";

         unordered_map<long, string> c;

         char buf[];

         clock_t timeStart = clock();

         for (long i = ; i< value; ++i)

         {

             try {

                 snprintf(buf, , "%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;    //

         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 << "\ntest_map().......... \n";

         map<long, string> c;

         char buf[];

         clock_t timeStart = clock();

         for (long i = ; i< value; ++i)

         {

             try {

                 snprintf(buf, , "%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;        //

         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();

     }

map

3.4无序容器

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

unordered_set,unordered_map,unordered_multiset,unordered_multimap

秒客网

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

1.C++标准库和STL

2.STL 六大组件

STL 六大组件的交互关系

c++知识点

3.容器的相关知识

3.1容器的结构与分类

容器测试辅助函数

3.2顺序容器

3.3关联容器

3.4无序容器

相关文章