C++ 之 STL

STL系列之一 deque双向队列

deque双向队列是一种双向开口的连续线性空间，可以高效的在头尾两端插入和删除元素，deque在接口上和vector非常相似，下面列出deque的常用成员函数：

 

deque的实现比较复杂，内部会维护一个map（注意！不是STL中的map容器）即一小块连续的空间，该空间中每个元素都是指针，指向另一段（较大的）区域，这个区域称为缓冲区，缓冲区用来保存deque中的数据。因此deque在随机访问和遍历数据会比vector慢。具体的deque实现可以参考《STL源码剖析》，当然此书中使用的SGI STL与VS2008所使用的PJ STL的实现方法还是有区别的。下面给出了deque的结构图：

 

由于篇幅问题，deque的实现细节就不再深入了，下面给出deque的使用范例：

[cpp] view plaincopyprint?
  1. //双向队列 deque   
  2. //by MoreWindows https://blog.csdn.net/morewindows   
  3. #include <deque>   
  4. #include <cstdio>   
  5. #include <algorithm>   
  6. using namespace std;  
  7. int main()  
  8. {  
  9.     deque<int> ideq(20); //Create a deque ideq with 20 elements of default value 0   
  10.     deque<int>::iterator pos;  
  11.     int i;  
  12.   
  13.     //使用assign()赋值  assign在计算机中就是赋值的意思   
  14.     for (i = 0; i < 20; ++i)  
  15.         ideq[i] = i;  
  16.       
  17.     //输出deque   
  18.     printf("输出deque中数据:\n");  
  19.     for (i = 0; i < 20; ++i)  
  20.         printf("%d ", ideq[i]);  
  21.     putchar('\n');  
  22.   
  23.     //在头尾加入新数据   
  24.     printf("\n在头尾加入新数据...\n");  
  25.     ideq.push_back(100);  
  26.     ideq.push_front(i);  
  27.   
  28.     //输出deque   
  29.     printf("\n输出deque中数据:\n");  
  30.     for (pos = ideq.begin(); pos != ideq.end(); pos++)  
  31.         printf("%d ", *pos);  
  32.     putchar('\n');  
  33.   
  34.     //查找   
  35.     const int FINDNUMBER = 19;  
  36.     printf("\n查找%d\n", FINDNUMBER);  
  37.     pos = find(ideq.begin(), ideq.end(), FINDNUMBER);  
  38.     if (pos != ideq.end())  
  39.         printf("find %d success\n", *pos);  
  40.     else  
  41.         printf("find failed\n");  
  42.   
  43.     //在头尾删除数据   
  44.     printf("\n在头尾删除数据...\n");  
  45.     ideq.pop_back();  
  46.     ideq.pop_front();  
  47.   
  48.     //输出deque   
  49.     printf("\n输出deque中数据:\n");  
  50.     for (pos = ideq.begin(); pos != ideq.end(); pos++)  
  51.         printf("%d ", *pos);  
  52.     putchar('\n');  
  53.     return 0;  
  54. }  

运行结果如下：

另外要注意一点。对于deque和vector来说，尽量少用erase(pos)和erase(beg,end)。因为这在中间删除数据后会导致后面的数据向前移动，从而使效率低下。

 

 

转载请标明出处，原文地址：https://blog.csdn.net/morewindows/article/details/6946811

STL系列之三 queue 单向队列

queue单向队列与栈有点类似，一个是在同一端存取数据，另一个是在一端存入数据，另一端取出数据。单向队列中的数据是先进先出（First In First Out,FIFO）。在STL中，单向队列也是以别的容器作为底部结构，再将接口改变，使之符合单向队列的特性就可以了。因此实现也是非常方便的。下面就给出单向队列的函数列表和VS2008中单向队列的源代码。单向队列一共6个常用函数（front()、back()、push()、pop()、empty()、size()），与栈的常用函数较为相似。

    

STL系列之二 stack栈

栈（statck）这种数据结构在计算机中是相当出名的。栈中的数据是先进后出的（First In Last Out, FILO）。栈只有一个出口，允许新增元素（只能在栈顶上增加）、移出元素（只能移出栈顶元素）、取得栈顶元素等操作。在STL中，栈是以别的容器作为底部结构，再将接口改变，使之符合栈的特性就可以了。因此实现非常的方便。下面就给出栈的函数列表和VS2008中栈的源代码，在STL中栈一共就5个常用操作函数（top()、push()、pop()、 size()、empty() ），很好记的。

 

VS2008中栈的源代码

友情提示：初次阅读时请注意其实现思想，不要在细节上浪费过多的时间。

[cpp] view plaincopyprint?
  1. //VS2008中 stack的定义 MoreWindows整理(https://blog.csdn.net/MoreWindows)   
  2. template<class _Ty, class _Container = deque<_Ty> >  
  3. class stack  
  4. {   // LIFO queue implemented with a container   
  5. public:  
  6.     typedef _Container container_type;  
  7.     typedef typename _Container::value_type value_type;  
  8.     typedef typename _Container::size_type size_type;  
  9.     typedef typename _Container::reference reference;  
  10.     typedef typename _Container::const_reference const_reference;  
  11.   
  12.     stack() : c()  
  13.     {   // construct with empty container   
  14.     }  
  15.   
  16.     explicit stack(const _Container& _Cont) : c(_Cont)  
  17.     {   // construct by copying specified container   
  18.     }  
  19.   
  20.     bool empty() const  
  21.     {   // test if stack is empty   
  22.         return (c.empty());  
  23.     }  
  24.   
  25.     size_type size() const  
  26.     {   // test length of stack   
  27.         return (c.size());  
  28.     }  
  29.   
  30.     reference top()  
  31.     {   // return last element of mutable stack   
  32.         return (c.back());  
  33.     }  
  34.   
  35.     const_reference top() const  
  36.     {   // return last element of nonmutable stack   
  37.         return (c.back());  
  38.     }  
  39.   
  40.     void push(const value_type& _Val)  
  41.     {   // insert element at end   
  42.         c.push_back(_Val);  
  43.     }  
  44.   
  45.     void pop()  
  46.     {   // erase last element   
  47.         c.pop_back();  
  48.     }  
  49.   
  50.     const _Container& _Get_container() const  
  51.     {   // get reference to container   
  52.         return (c);  
  53.     }  
  54.   
  55. protected:  
  56.     _Container c;   // the underlying container   
  57. };  

可以看出，由于栈只是进一步封装别的数据结构，并提供自己的接口，所以代码非常简洁，如果不指定容器，默认是用deque来作为其底层数据结构的（对deque不是很了解？可以参阅《STL系列之一 deque双向队列》）。下面给出栈的使用范例：

[cpp] view plaincopyprint?
  1. //栈 stack支持 empty() size() top() push() pop()   
  2. // by MoreWindows(https://blog.csdn.net/MoreWindows)   
  3. #include <stack>   
  4. #include <vector>   
  5. #include <list>   
  6. #include <cstdio>   
  7. using namespace std;  
  8. int main()  
  9. {  
  10.     //可以使用list或vector作为栈的容器，默认是使用deque的。   
  11.     stack<int, list<int>>      a;  
  12.     stack<int, vector<int>>   b;  
  13.     int i;  
  14.       
  15.     //压入数据   
  16.     for (i = 0; i < 10; i++)  
  17.     {  
  18.         a.push(i);  
  19.         b.push(i);  
  20.     }  
  21.   
  22.     //栈的大小   
  23.     printf("%d %d\n", a.size(), b.size());  
  24.   
  25.     //取栈项数据并将数据弹出栈   
  26.     while (!a.empty())  
  27.     {  
  28.         printf("%d ", a.top());  
  29.         a.pop();  
  30.     }  
  31.     putchar('\n');  
  32.   
  33.     while (!b.empty())  
  34.     {  
  35.         printf("%d ", b.top());  
  36.         b.pop();  
  37.     }  
  38.     putchar('\n');  
  39.     return 0;  
  40. }  

 

转载请标明出处，原文地址：https://blog.csdn.net/morewindows/article/details/6950881

 

STL系列之三 queue 单向队列

分类： STL 他山之石 2011-11-09 09:20 7902人阅读 评论(10) 收藏 举报
reference数据结构classinsertlist

queue单向队列与栈有点类似，一个是在同一端存取数据，另一个是在一端存入数据，另一端取出数据。单向队列中的数据是先进先出（First In First Out,FIFO）。在STL中，单向队列也是以别的容器作为底部结构，再将接口改变，使之符合单向队列的特性就可以了。因此实现也是非常方便的。下面就给出单向队列的函数列表和VS2008中单向队列的源代码。单向队列一共6个常用函数（front()、back()、push()、pop()、empty()、size()），与栈的常用函数较为相似。

 

VS2008中queue单向队列的源代码

友情提示：初次阅读时请注意其实现思想，不要在细节上浪费过多的时间。

[cpp] view plaincopyprint?
  1. <SPAN style="FONT-SIZE: 18px">//VS2008中 queue的定义 MoreWindows整理(https://blog.csdn.net/MoreWindows)   
  2. template<class _Ty, class _Container = deque<_Ty> >  
  3. class queue  
  4. {   // FIFO queue implemented with a container   
  5. public:  
  6.     typedef _Container container_type;  
  7.     typedef typename _Container::value_type value_type;  
  8.     typedef typename _Container::size_type size_type;  
  9.     typedef typename _Container::reference reference;  
  10.     typedef typename _Container::const_reference const_reference;  
  11.   
  12.     queue() : c()  
  13.     {   // construct with empty container   
  14.     }  
  15.   
  16.     explicit queue(const _Container& _Cont) : c(_Cont)  
  17.     {   // construct by copying specified container   
  18.     }  
  19.   
  20.     bool empty() const  
  21.     {   // test if queue is empty   
  22.         return (c.empty());  
  23.     }  
  24.   
  25.     size_type size() const  
  26.     {   // return length of queue   
  27.         return (c.size());  
  28.     }  
  29.   
  30.     reference front()  
  31.     {   // return first element of mutable queue   
  32.         return (c.front());  
  33.     }  
  34.   
  35.     const_reference front() const  
  36.     {   // return first element of nonmutable queue   
  37.         return (c.front());  
  38.     }  
  39.   
  40.     reference back()  
  41.     {   // return last element of mutable queue   
  42.         return (c.back());  
  43.     }  
  44.   
  45.     const_reference back() const  
  46.     {   // return last element of nonmutable queue   
  47.         return (c.back());  
  48.     }  
  49.   
  50.     void push(const value_type& _Val)  
  51.     {   // insert element at beginning   
  52.         c.push_back(_Val);  
  53.     }  
  54.   
  55.     void pop()  
  56.     {   // erase element at end   
  57.         c.pop_front();  
  58.     }  
  59.   
  60.     const _Container& _Get_container() const  
  61.     {   // get reference to container   
  62.         return (c);  
  63.     }  
  64.   
  65. protected:  
  66.     _Container c;   // the underlying container   
  67. };</SPAN>  

可以看出，由于queue只是进一步封装别的数据结构，并提供自己的接口，所以代码非常简洁，如果不指定容器，默认是用deque来作为其底层数据结构的（对deque不是很了解？可以参阅《STL系列之一deque双向队列》）。下面给出单向队列的使用范例：

[cpp] view plaincopyprint?
  1. //单向队列 queue支持 empty() size() front() back() push() pop()   
  2. //By MoreWindows(https://blog.csdn.net/MoreWindows)   
  3. #include <queue>   
  4. #include <vector>   
  5. #include <list>   
  6. #include <cstdio>   
  7. using namespace std;  
  8.   
  9. int main()  
  10. {  
  11.     //可以使用list作为单向队列的容器，默认是使用deque的。   
  12.     queue<int, list<int>> a;  
  13.     queue<int>        b;  
  14.     int i;  
  15.   
  16.     //压入数据   
  17.     for (i = 0; i < 10; i++)  
  18.     {  
  19.         a.push(i);  
  20.         b.push(i);  
  21.     }  
  22.   
  23.     //单向队列的大小   
  24.     printf("%d %d\n", a.size(), b.size());  
  25.   
  26.     //队列头和队列尾   
  27.     printf("%d %d\n", a.front(), a.back());  
  28.     printf("%d %d\n", b.front(), b.back());  
  29.   
  30.     //取单向队列项数据并将数据移出单向队列   
  31.     while (!a.empty())  
  32.     {  
  33.         printf("%d ", a.front());  
  34.         a.pop();  
  35.     }  
  36.     putchar('\n');  
  37.   
  38.     while (!b.empty())  
  39.     {  
  40.         printf("%d ", b.front());  
  41.         b.pop();  
  42.     }  
  43.     putchar('\n');  
  44.     return 0;  
  45. }  

 

转载请标明出处，原文地址：https://blog.csdn.net/morewindows/article/details/6950917

 

 

 

STL系列之四 heap 堆

下面再介绍STL中与堆相关的4个函数——建立堆make_heap()，在堆中添加数据push_heap()，在堆中删除数据pop_heap()和堆排序sort_heap()：

头文件 #include <algorithm>

下面的_First与_Last为可以随机访问的迭代器（指针），_Comp为比较函数（仿函数），其规则——如果函数的第一个参数小于第二个参数应返回true，否则返回false。

建立堆

make_heap(_First, _Last, _Comp)

默认是建立最大堆的。对int类型，可以在第三个参数传入greater<int>()得到最小堆。

 

在堆中添加数据

push_heap (_First, _Last)

要先在容器中加入数据，再调用push_heap ()

 

在堆中删除数据

pop_heap(_First, _Last)

要先调用pop_heap()再在容器中删除数据

 

堆排序

sort_heap(_First, _Last)

排序之后就不再是一个合法的heap了

 

有关堆与堆排序的更详细介绍请参阅——《白话经典算法系列之七 堆与堆排序》

 

下面给出STL中heap相关函数的使用范例：

[cpp] view plaincopyprint?
  1. //by MoreWindows( https://blog.csdn.net/MoreWindows )   
  2. #include <cstdio>   
  3. #include <vector>   
  4. #include <algorithm>   
  5. #include <functional>   
  6. using namespace std;  
  7. void PrintfVectorInt(vector<int> &vet)  
  8. {  
  9.     for (vector<int>::iterator pos = vet.begin(); pos != vet.end(); pos++)  
  10.         printf("%d ", *pos);  
  11.     putchar('\n');  
  12. }  
  13. int main()  
  14. {  
  15.     const int MAXN = 20;  
  16.     int a[MAXN];  
  17.     int i;  
  18.     for (i = 0; i < MAXN; ++i)  
  19.         a[i] = rand() % (MAXN * 2);  
  20.   
  21.     //动态申请vector 并对vector建堆   
  22.     vector<int> *pvet = new vector<int>(40);  
  23.     pvet->assign(a, a + MAXN);  
  24.   
  25.     //建堆   
  26.     make_heap(pvet->begin(), pvet->end());  
  27.     PrintfVectorInt(*pvet);  
  28.   
  29.     //加入新数据 先在容器中加入，再调用push_heap()   
  30.     pvet->push_back(25);  
  31.     push_heap(pvet->begin(), pvet->end());  
  32.     PrintfVectorInt(*pvet);  
  33.   
  34.     //删除数据  要先调用pop_heap()，再在容器中删除   
  35.     pop_heap(pvet->begin(), pvet->end());  
  36.     pvet->pop_back();  
  37.     pop_heap(pvet->begin(), pvet->end());  
  38.     pvet->pop_back();  
  39.     PrintfVectorInt(*pvet);  
  40.   
  41.     //堆排序   
  42.     sort_heap(pvet->begin(), pvet->end());  
  43.     PrintfVectorInt(*pvet);  
  44.   
  45.     delete pvet;  
  46.     return 0;  
  47. }  

掌握其基本用法后，我们用这个堆排序和《白话经典算法系列》中的堆排序、快速排序，归并排序来进行个性能测试（Win7 + VS2008 Release下），测试代码如下：

[cpp] view plaincopyprint?
  1. // by MoreWindows( https://blog.csdn.net/MoreWindows )   
  2. #include <cstdio>   
  3. #include <algorithm>   
  4. #include <ctime>   
  5. using namespace std;  
  6. //------------------------快速排序----------------------------   
  7. void quick_sort(int s[], int l, int r)  
  8. {  
  9.     if (l < r)  
  10.     {  
  11.         int i = l, j = r, x = s[l];  
  12.         while (i < j)  
  13.         {  
  14.             while(i < j && s[j] >= x) // 从右向左找第一个小于x的数   
  15.                 j--;    
  16.             if(i < j)   
  17.                 s[i++] = s[j];  
  18.   
  19.             while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数   
  20.                 i++;    
  21.             if(i < j)   
  22.                 s[j--] = s[i];  
  23.         }  
  24.         s[i] = x;  
  25.         quick_sort(s, l, i - 1); // 递归调用    
  26.         quick_sort(s, i + 1, r);  
  27.     }  
  28. }  
  29. //------------------------归并排序----------------------------   
  30. //将有二个有序数列a[first...mid]和a[mid...last]合并。   
  31. void mergearray(int a[], int first, int mid, int last, int temp[])  
  32. {  
  33.     int i = first, j = mid + 1;  
  34.     int m = mid,   n = last;  
  35.     int k = 0;  
  36.   
  37.     while (i <= m && j <= n)  
  38.     {  
  39.         if (a[i] < a[j])  
  40.             temp[k++] = a[i++];  
  41.         else  
  42.             temp[k++] = a[j++];  
  43.     }  
  44.   
  45.     while (i <= m)  
  46.         temp[k++] = a[i++];  
  47.   
  48.     while (j <= n)  
  49.         temp[k++] = a[j++];  
  50.   
  51.     for (i = 0; i < k; i++)  
  52.         a[first + i] = temp[i];  
  53. }  
  54. void mergesort(int a[], int first, int last, int temp[])  
  55. {  
  56.     if (first < last)  
  57.     {  
  58.         int mid = (first + last) / 2;  
  59.         mergesort(a, first, mid, temp);    //左边有序   
  60.         mergesort(a, mid + 1, last, temp); //右边有序   
  61.         mergearray(a, first, mid, last, temp); //再将二个有序数列合并   
  62.     }  
  63. }  
  64. bool MergeSort(int a[], int n)  
  65. {  
  66.     int *p = new int[n];  
  67.     if (p == NULL)  
  68.         return false;  
  69.     mergesort(a, 0, n - 1, p);  
  70.     return true;  
  71. }  
  72. //------------------------堆排序---------------------------   
  73. inline void Swap(int &a, int &b)  
  74. {  
  75.     int c = a;  
  76.     a = b;  
  77.     b = c;  
  78. }  
  79. //建立最小堆   
  80. //  从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2   
  81. void MinHeapFixdown(int a[], int i, int n)  
  82. {  
  83.     int j, temp;  
  84.   
  85.     temp = a[i];  
  86.     j = 2 * i + 1;  
  87.     while (j < n)  
  88.     {  
  89.         if (j + 1 < n && a[j + 1] < a[j]) //在左右孩子中找最小的   
  90.             j++;  
  91.   
  92.         if (a[j] >= temp)  
  93.             break;  
  94.   
  95.         a[i] = a[j];     //把较小的子结点往上移动,替换它的父结点   
  96.         i = j;  
  97.         j = 2 * i + 1;  
  98.     }  
  99.     a[i] = temp;  
  100. }  
  101. //建立最小堆   
  102. void MakeMinHeap(int a[], int n)  
  103. {  
  104.     for (int i = n / 2 - 1; i >= 0; i--)  
  105.         MinHeapFixdown(a, i, n);  
  106. }  
  107. void MinheapsortTodescendarray(int a[], int n)  
  108. {  
  109.     for (int i = n - 1; i >= 1; i--)  
  110.     {  
  111.         Swap(a[i], a[0]);  
  112.         MinHeapFixdown(a, 0, i);  
  113.     }  
  114. }  
  115. const int MAXN = 5000000;  
  116. int a[MAXN];  
  117. int b[MAXN], c[MAXN], d[MAXN];  
  118. int main()  
  119. {  
  120.     int i;  
  121.     srand(time(NULL));  
  122.     for (i = 0; i < MAXN; ++i)  
  123.         a[i] = rand() * rand(); //注rand()产生的数在0到0x7FFF之间   
  124.   
  125.     for (i = 0; i < MAXN; ++i)  
  126.         d[i] = c[i] = b[i] = a[i];  
  127.   
  128.     clock_t ibegin, iend;  
  129.   
  130.     printf("--当前数据量为%d--By MoreWindows(https://blog.csdn.net/MoreWindows)--\n", MAXN);  
  131.     //快速排序   
  132.     printf("快速排序:  ");  
  133.     ibegin = clock();  
  134.     quick_sort(a, 0, MAXN - 1);  
  135.     iend = clock();  
  136.     printf("%d毫秒\n", iend - ibegin);  
  137.   
  138.       
  139.     //归并排序   
  140.     printf("归并排序:  ");  
  141.     ibegin = clock();  
  142.     MergeSort(b, MAXN);  
  143.     iend = clock();  
  144.     printf("%d毫秒\n", iend - ibegin);  
  145.   
  146.     //堆排序   
  147.     printf("堆排序:  ");  
  148.     ibegin = clock();  
  149.     MakeMinHeap(c, MAXN);  
  150.     MinheapsortTodescendarray(c, MAXN);  
  151.     iend = clock();  
  152.     printf("%d毫秒\n", iend - ibegin);  
  153.   
  154.     //STL中的堆排序   
  155.     printf("STL中的堆排序: ");     
  156.     ibegin = clock();  
  157.     make_heap(d, d + MAXN);  
  158.     sort_heap(d, d + MAXN);  
  159.     iend = clock();  
  160.     printf("%d毫秒\n", iend - ibegin);  
  161.     return 0;  
  162. }  

对100000（十万）个数据的测试结果：

对500000（五十万）个数据的测试结果：

对1000000（一百万）个数据的测试结果：

对5000000（五百万）个数据的测试结果：

从中可以看出快速排序的效率确实要比其它同为O(N * logN)的排序算法要高，而STL中堆操作函数的性能与《白话经典算法系列之七 堆与堆排序》一文中堆操作函数的性能是相差无几的。

 

转载请标明出处，原文地址：https://blog.csdn.net/morewindows/article/details/6967409