標準模板庫(Standard Template Library, STL)是容器和通用算法的強效組合。

漸近復雜度：算法的漸近復雜度是對算法性能的近似估計。它是算法集到特定性能標準集的映射。如果需要對包含N個整數的向量的所有元素求和，那么每個整數必須且僅需檢查一次，因此該算法的復雜度約為N，我們將其稱為O(N)。另一方面，假設需要創建一個包含N個元素的向量，由于某種原因，你需要將這些元素插入到該向量的前端。然而，在向量的前端每插入一個元素便會迫使所有已存在的元素移動1個位置。這就導致了(1+2+3+…+N)次向量元素的移動，也即(N/2)(N+1)次移動。即使需要移動(N*N/2)+(N/2)次，但我們仍說這個算法的復雜度是O(N*N)。這是因為漸近性能標準集將忽略常量倍數和低階因子。因而N*N和7N*N的復雜度相同：均為O(N*N)。STL對其算法漸近復雜度的保證是一個良好的開端。它告訴我們，所使用的算法是同類算法中最好的。

插入：在集合大小事先可知的情況下，在尾部進行元素插入操作，速度，數組>向量>雙向列表>多重集。數組和向量均為占用連續內存塊的順序容器。當無法事先確定集合大小時，向量將會更有用。向量是可以動態增長的，這樣程序員就不用考慮集合的大小。向量的大小是指向量當前擁有元素的數量。向量的容量是指向量能夠容納元素數量的最大值，超過這個值，向量就必須分配更多的內存以適應元素的增長。當往向量中插入第一個元素時，為了使向量的容量超過它的初始大小(值為1)，典型的STL實現將會分配一大塊內存。后續的插入將會增加向量的大小，而容量保持不變。如果集合持續增長，那么向量大小最終將會達到它的容量。下一次插入操作將會迫使向量的實現擴大自身容量。這必須包含以下幾個步驟：(1). 分配更大的內存塊，以便為增加的元素留出空間；(2). 將當前集合中現存的所有元素復制到新分配的內存中。在該過程中，會為舊集合的每一個元素調用拷貝構造函數；(3). 銷毀舊集合并釋放它所占用的空間。在該過程中，會為舊集合中的每一個元素調用析構函數。這些步驟可能會引起巨額開銷。因此，我們希望盡可能少地出現向量大小超過其容量的情況。列表容器并未將元素存儲在連續的內存空間中，所以也就無須應付容量問題和相關的性能開銷問題。向量容器在進行前端插入時的性能極其槽糕。而列表在進行前端插入或后端插入時性能幾乎一致。

刪除：刪除操作的性能情況在很多方面都與插入操作很類似。很多關于插入效率的結論同樣適用于刪除。例如：(1). 向量擅長于在尾部對元素進行插入(或刪除)操作。因為這種操作與集合大小無關，所以它是一種固定時間的操作。(2). 除了尾部操作之外，采用向量進行其它任何位置的插入(或刪除)操作都是一種極為糟糕的選擇。這種插入(或刪除)的代價與插入(或刪除)點到向量的最后一個元素之間的距離成正比例。(3). 雙向隊列在集合的前端和尾部插入(或刪除)元素時效率很高(常數時間)，在其它任何位置插入(或刪除)元素時效率都很低。(4). 列表在集合的任何位置插入(或刪除)元素時效率都很高(固定時間)。

遍歷：對于容器的遍歷操作來說，向量和數組的性能是相同的。它們均遠勝過列表。容器遍歷的關鍵因素似乎為容器內存布局和系統緩存之間的交互作用。

查找：當進行元素查找時，使用成員find方法，多重容器可以勝過其它的所有競爭對手。而多重集是有序集，這使其在插入和刪除操作上遭受了一些性能上的損失。但是，從另一方面來看，有序特性也為多重集容器在查找方面帶來了巨大的優勢。

函數對象：默認情況下，accumulate()函數將operator+操作應用到容器中所有元素，然后返回這些元素相加的累計結果。對于整數集合來說，如果提供給accumulate()函數的初始值為0，那么該函數返回的結果就是集合中所有元素的和。accumulate()函數不僅可以進行對象相加，而且可以對容器元素進行任何操作(前提是元素支持這種操作)，然后返回累計結果。函數指針直到運行時才能被解析，這就使得它們無法被內聯。而函數對象是在編譯時被確定的，這就使得編譯器可以自由地內聯operator()函數并顯著地提升效率。

STL實現在以下幾個方面形成了自己的優勢：(1). STL實現使用最好的算法；(2). STL實現的設計者非常有可能是領域內的專家；(3). 這些領域內的專家完全地致力于提供一個靈活、強大并且高效的庫。這是他們的首要任務。

STL是抽象、靈活性和效率的一種罕見的結合。對于某種特定的應用模式，一些容器比其它的更加高效，這都要隨著實際應用而定。除非了解一些相關領域內STL所忽略的問題，否則你是不可能超過STL實現的。不過，在一些特定的情況下，還是有可能超越STL實現的性能的。

以下是測試代碼(standard_template_library.cpp)：

#include "standard_template_library.hpp"
#include <cstdlib>
#include <iostream>
#include <chrono>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <algorithm>
#include <ctime>
#include <memory>
#include <numeric>
#include <functional>namespace standard_template_library_ {// reference: 《提高C++性能的編程技術》：第十一章：標準模板庫
namespace {
template<class T>
void arrayInsert(T* a, const T* collection, int size)
{for (int k = 0; k < size; ++k) {a[k] = 	collection[k];}
}template<class T>
void arrayTraverse(const T* a, int size)
{T sum = std::accumulate(&a[0], &a[size], 0);
}template<class T>
void arrayFind(const T* a, const T* collection, int size)
{T const value = collection[size/2];T* tmp = const_cast<T*>(a);T* p = std::find(&tmp[0], &tmp[size], value); 
}template<class T>
void vectorInsert(std::vector<T>* v, const T* collection, int size)
{for (int k = 0; k < size; ++k) {v->push_back(collection[k]);}
}template<class T>
void vectorInsertFront(std::vector<T>* v, const T* collection, int size)
{for (int k = 0; k < size; ++k) {v->insert(v->begin(), collection[k]);}
}template<class T>
void vectorDelete(std::vector<T>* v)
{while (!v->empty()) {v->pop_back();}
}template<class T>
void vectorDeleteFront(std::vector<T>* v)
{while (!v->empty()) {v->erase(v->begin());}
}template<class T>
void vectorTraverse(const std::vector<T>* v, int size)
{T sum = std::accumulate(v->cbegin(), v->cend(), 0);
}template<class T>
void vectorFind(const std::vector<T>* v, const T* collection, int size)
{T const value = collection[size/2];auto it = std::find(v->cbegin(), v->cend(), value);
}template<class T>
void listInsert(std::list<T>* l, const T* collection, int size)
{for (int k = 0; k < size; ++k) {l->push_back(collection[k]);}
}template<class T>
void listInsertFront(std::list<T>* l, const T* collection, int size)
{for (int k = 0; k < size; ++k) {l->push_front(collection[k]);}
}template<class T>
void listDelete(std::list<T>* l)
{while (!l->empty()) {l->pop_back();}
}template<class T>
void listDeleteFront(std::list<T>* l)
{while (!l->empty()) {l->pop_front();}
}template<class T>
void listTraverse(const std::list<T>* l, int size)
{T sum = std::accumulate(l->cbegin(), l->cend(), 0);
}template<class T>
void listFind(const std::list<T>*l, const T* collection, int size)
{T const value = collection[size/2];auto it = std::find(l->cbegin(), l->cend(), value);
}template<class T>
void multisetInsert(std::multiset<T>* s, const T* collection, int size)
{for (int k = 0; k < size; ++k) {s->insert(collection[k]);}
}template<class T>
void multisetFind(const std::multiset<T>* s, const T* collection, int size)
{T const value = collection[size/2];// 當查找多重集容器時，使用std::find并不是最佳的選擇//auto it = std::find(s->cbegin(), s->cend(), value);auto it = s->find(value);
}int* genIntData(int size)
{std::srand(std::time(nullptr));int* data = new int[size];std::generate(&data[0], &data[size], std::rand);return data;
}int mult(int x, int y)
{return (x*y);
}class Mult {
public:int operator()(int x, int y) const { return (x*y); }
};} // namespaceint test_standard_template_library_1()
{std::chrono::high_resolution_clock::time_point time_start, time_end;const int count{400000}, count2{10000}, count3{200000000};int* data = genIntData(count);{ // normal array insert back operationstd::unique_ptr<int[]> arr(new int[count]);	time_start = std::chrono::high_resolution_clock::now();arrayInsert(arr.get(), data, count);time_end = std::chrono::high_resolution_clock::now();	fprintf(stdout, "first value: %d, array insert back time spend: %f seconds\n",arr.get()[0], (std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}{ // vector insert back operationstd::vector<int> vec;	time_start = std::chrono::high_resolution_clock::now();vectorInsert(&vec, data, count);time_end = std::chrono::high_resolution_clock::now();	fprintf(stdout, "first value: %d, vector insert back time spend: %f seconds\n",vec[0], (std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}{ // list insert back operationstd::list<int> l;	time_start = std::chrono::high_resolution_clock::now();listInsert(&l, data, count);time_end = std::chrono::high_resolution_clock::now();	fprintf(stdout, "first value: %d, list insert back time spend: %f seconds\n",*(l.cbegin()), (std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}{ // multiset insert back operationstd::multiset<int> s;	time_start = std::chrono::high_resolution_clock::now();multisetInsert(&s, data, count);time_end = std::chrono::high_resolution_clock::now();	fprintf(stdout, "first value: %d, multiset insert back time spend: %f seconds\n",*(s.cbegin()), (std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}{ // vector insert front operationstd::vector<int> vec;	time_start = std::chrono::high_resolution_clock::now();vectorInsertFront(&vec, data, count);time_end = std::chrono::high_resolution_clock::now();	fprintf(stdout, "first value: %d, vector insert front time spend: %f seconds\n",vec[0], (std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}{ // list insert front operationstd::list<int> l;	time_start = std::chrono::high_resolution_clock::now();listInsertFront(&l, data, count);time_end = std::chrono::high_resolution_clock::now();	fprintf(stdout, "first value: %d, list insert front time spend: %f seconds\n",*(l.cbegin()), (std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}{ // vector delete back operationstd::vector<int> vec(data, data+count);time_start = std::chrono::high_resolution_clock::now();vectorDelete(&vec);time_end = std::chrono::high_resolution_clock::now();	fprintf(stdout, "vector size: %d, vector delete back time spend: %f seconds\n",vec.size(), (std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}{ // list delete back operationstd::list<int> l(data, data+count);	time_start = std::chrono::high_resolution_clock::now();listDelete(&l);time_end = std::chrono::high_resolution_clock::now();	fprintf(stdout, "list size: %d, list delete back time spend: %f seconds\n",l.size(), (std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}{ // vector delete front operationstd::vector<int> vec(data, data+count);time_start = std::chrono::high_resolution_clock::now();vectorDeleteFront(&vec);time_end = std::chrono::high_resolution_clock::now();	fprintf(stdout, "vector size: %d, vector delete front time spend: %f seconds\n",vec.size(), (std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}{ // list delete front operationstd::list<int> l(data, data+count);	time_start = std::chrono::high_resolution_clock::now();listDeleteFront(&l);time_end = std::chrono::high_resolution_clock::now();	fprintf(stdout, "list size: %d, list delete front time spend: %f seconds\n",l.size(), (std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}{ // normal array traverse operationtime_start = std::chrono::high_resolution_clock::now();for (int i = 0; i < count2; ++i)arrayTraverse(data, count);time_end = std::chrono::high_resolution_clock::now();	fprintf(stdout, "first value: %d, array traverse time spend: %f seconds\n",data[0], (std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}{ // vector traverse operationstd::vector<int> vec(data, data+count);time_start = std::chrono::high_resolution_clock::now();for (int i = 0; i < count2; ++i)vectorTraverse(&vec, count);time_end = std::chrono::high_resolution_clock::now();	fprintf(stdout, "first value: %d, vector traverse time spend: %f seconds\n",vec[0], (std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}{ // list traverse operationstd::list<int> l(data, data+count);	time_start = std::chrono::high_resolution_clock::now();for (int i = 0; i < count2; ++i)listTraverse(&l, count);time_end = std::chrono::high_resolution_clock::now();	fprintf(stdout, "first value: %d, list traverse time spend: %f seconds\n",*l.cbegin(), (std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}{ // normal array find operationtime_start = std::chrono::high_resolution_clock::now();for (int i = 0; i < count2; ++i)arrayFind(data, data, count);time_end = std::chrono::high_resolution_clock::now();	fprintf(stdout, "first value: %d, array find time spend: %f seconds\n",data[0], (std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}{ // vector find operationstd::vector<int> vec(data, data+count);time_start = std::chrono::high_resolution_clock::now();for (int i = 0; i < count2; ++i)vectorFind(&vec, data, count);time_end = std::chrono::high_resolution_clock::now();	fprintf(stdout, "first value: %d, vector find time spend: %f seconds\n",vec[0], (std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}{ // list find operationstd::list<int> l(data, data+count);	time_start = std::chrono::high_resolution_clock::now();for (int i = 0; i< count2; ++i)listFind(&l, data, count);time_end = std::chrono::high_resolution_clock::now();	fprintf(stdout, "first value: %d, list find time spend: %f seconds\n",*l.cbegin(), (std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}{ // multiset find operationstd::multiset<int> s;	time_start = std::chrono::high_resolution_clock::now();for (int i = 0; i < count2; ++i)multisetFind(&s, data, count);time_end = std::chrono::high_resolution_clock::now();	fprintf(stdout, "first value: %d, multiset find time spend: %f seconds\n",*(s.cbegin()), (std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}int a[10] = {1, 2, 3, 5, 7, 11, 13, 17, 19, 23};int init = 1, product = 0;{ // accumulate operation: function pointer	time_start = std::chrono::high_resolution_clock::now();for (int i = 0; i < count3; ++i)product = std::accumulate(&a[0], &a[10], init, mult);time_end = std::chrono::high_resolution_clock::now();	fprintf(stdout, "value: %d, accumulate function pointer time spend: %f seconds\n",product, (std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}{ // accumulate operation: function objecttime_start = std::chrono::high_resolution_clock::now();for (int i = 0; i < count3; ++i)product = std::accumulate(&a[0], &a[10], init, Mult());time_end = std::chrono::high_resolution_clock::now();	fprintf(stdout, "value: %d, accumulate function object time spend: %f seconds\n",product, (std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}{ // accumulate operation: function object(std)	time_start = std::chrono::high_resolution_clock::now();for (int i = 0; i < count3; ++i)product = std::accumulate(&a[0], &a[10], init, std::multiplies<int>());time_end = std::chrono::high_resolution_clock::now();	fprintf(stdout, "value: %d, accumulate function object(std) time spend: %f seconds\n",product, (std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}delete [] data;return 0;
}} // namespace standard_template_library_

執行結果如下：

GitHub：https://github.com/fengbingchun/Messy_Test?

總結

以上是生活随笔為你收集整理的提高C++性能的编程技术笔记：标准模板库+测试代码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。