技術文章 » STL是什麼（STL簡介）

STL是什麼（STL簡介）

2020-07-16 10:04:42
本節主要講述 STL 歷史、STL 元件、STL 基本結構以及 STL 程式設計概述。

STL 歷史可以追溯到 1972 年 C 語言在 UNIX 計算機上的首次使用。直到 1994 年，STL 才被正式納入 C++ 標準中。

STL 元件主要包括容器，疊代器、演算法和仿函數。STL 基本結構和 STL 元件對應。

STL 主要由疊代器、演算法、容器、彷函數、記憶體設定器和配接器六部分組成，可幫助程式設計師完成許多功能完善、形式多樣的程式。

STL歷史

C 語言是 1972 年由美國的 Dennis Ritchie 設計發明的，並首次在 UNIX 作業系統的計算機上使用。C 語言由早期的組合語言 BCPL 發展演變而來。隨著微型計算機的日益普及，C 語言出現了許多其他版本，由於沒有統一的標準，各版本之間出現了不一致之處。ANSI 因此為 C 語言制定一套 ANSI 標準，後來成為現行的 C 語言標準。

早期的 C 語言主要用於 UNIX 系統。因其強大的功能和各方面的優點逐漸被人們認識。20 世紀 80 年代，C 語言開始應用於其他作業系統，並很快在各種計算機上得到廣泛應用，成為當代最優秀的程式設計語言之一。

C 語言的表現能力和處理能力極強。它不僅具有豐富的運算子和資料型別，便於實現各類複雜的資料結構，還可以直接存取記憶體實體地址，甚至進行位元運算。此外，C 語言還可實現對硬體的程式設計操作，十分便捷方便。

1983 年，貝爾實驗室的 BjameStrou-strup 推出了 C++。C++ 進一步擴充和完善了 C 語言，成為物件導向的程式設計語言。最初 C++ 主要用於小型計算機系統。1988 年，出現了第一個用於 PC 的 Z0RTECH C++ 2.0 編譯系統；1989 年，出現了 Turbo C++2.0 編譯器。

從 1991 年開始，Borland 公司陸續推出了 Borland C++ 2.0/3.0/4.0 系統。而微軟公司直到 1992 年，才推出基於 DOS 的 MS C/C++ 7.0 系統。

1993 年，微軟推出了面向 Windows 的 Visual C++ 1. 0 系統，並於 1998 年推出 了 Visual C++6. 0。

C 語言提供了具有可適應性的、強大的抽象機制，用於對問題進行抽象。這種語言結構允許程式設計師建立和使用新的型別，而這些新的型別則可以與實際應用中所包含的概念相適應。在 C++ 的最新發展過程中，C++ 新增了模板新特性。通過使用模板，程式具備更好的程式碼重用效能。

1994 年 7 月，美國國家標準與技術研究院通過投票決定，將 STL 納入 C++ 標準，使之成為 C++ 庫的重要組成部分。1997 年，C++ 標準完成了最近一次的修改，官方名稱為 ISO/IEC 14882。

STL 從根本上講是“容器”的集合，也是元件的集合。容器包括 list、vector、set、map 等；元件包括疊代器等。STL 的目的是標準化元件，與 Visual C++ 中的 ATL 相似。

STL 是 C++ 的一部分，不用額外安裝，被內建在支援 C++ 的編譯器中。

STL 的演算法是標準演算法，其實現了將已經定義好的演算法應用在容器的物件上。

STL 元件

STL 是 C++ 標準程式庫的核心。STL 內的所有元件都由模板構成，其元素可以是任意型別。程式設計師通過選用恰當的群集類別呼叫其成員函數和演算法中的資料即可，但代價是 STL 晦澀難懂。

STL 元件主要包括容器，疊代器、演算法和彷函數。

容器

容器即用來儲存並管理某類物件的集合。例如魚缸是用來盛放金魚的容器。

每一種容器都有其優點和缺點。為滿足程式的各種需求，STL 準備了多種容器型別，容器可以是 arrays 或是 linked lists，或者每個元素有特別的鍵值。

疊代器

疊代器用於在一個物件群集的元素上進行遍歷動作。物件群集可能是容器，也可能是容器的一部分。

疊代器的主要用途是為容器提供一組很小的公共介面。利用這個介面，某項操作可以行進至群集內的下一個元素。

每種容器都提供了各自的疊代器。疊代器了解該容器的內部結構，所以能夠正確行進。疊代器的介面和一般指標類似。

演算法

演算法用來處理群集內的元素，可以出於不同目的搜尋、排序、修改、使用那些元素。所有容器的疊代器都提供一致的介面，通過疊代器的協助，演算法程式可以用於任意容器。

STL 的一個特性是將資料和操作分離。資料由容器類別加以管理，操作則由可客製化的演算法定義。疊代器在兩者之間充當“黏合劑”，以使演算法可以和容器互動運作。

STL 的另一個特性即元件可以針對任意型別運作。“標準模板庫”這一名稱即表示“可接受任意型別”的模板，並且這些型別均可執行必要操作。

在 STL 中，容器又分為序列式容器和關聯式容器兩大類，而迭代器的功能主要是遍歷容器內全部或部分元素的物件。疊代器可劃分為 5 種類屬，這 5 種類屬歸屬兩種型別：雙向疊代器和隨機存取疊代器。

SIL 中提供的演算法包括搜尋、排序、複製、重新排序、修改、數值運算等。

仿函數

STL中大量運用了仿函數。彷函數具有泛型程式設計強大的威力，是純粹抽象概念的例證。

STL基本結構

STL 是 C++ 通用庫，由疊代器、演算法、容器、仿函數、配接器和設定器（即記憶體設定器）組成。

容器

STL 包含諸多容器類。容器類是可以包含其他物件的類，就像陣列和佇列堆疊等資料結構包含整數、小數、類等資料成員一樣。STL 可以包含常見的向量類、連結串列類、雙向佇列類、集合類、圖類等，每個類都是一種模板，這些模板可以包含各種型別的物件。

下述程式碼是常用的 vector 賦值方法：
vector <int> l;
for (int i =0;i <100;i++ )
    l.push_back (i);
下述程式碼採用 map 容器進行二維元素的管理：
map <string, string, less <string>> cap; //按從小到大序
cap ["Ark"] ="Little Rock";
cap ["New"] ="Albany";
map 類似於二維陣列，但比二維陣列靈活得多。

目前，STL 中已經提供的容器主要如下：
  • vector <T>：一種向量。
  • list <T>：一個雙向連結串列容器，完成了標準 C++ 資料結構中連結串列的所有功能。
  • queue <T>：一種佇列容器，完成了標準 C++ 資料結構中佇列的所有功能。
  • stack <T>：一種棧容器，完成了標準 C++ 資料結構中棧的所有功能。
  • deque <T>：雙端佇列容器，完成了標準 C++ 資料結構中棧的所有功能。
  • priority_queue <T>：一種按值排序的佇列容器。
  • set <T>：一種集合容器。
  • multiset <T>：一種允許出現重複元素的集合容器。
  • map <key, val>：一種關聯陣列容器。
  • multimap <key, val>：一種允許出現重複 key 值的關聯陣列容器。

以上容器設計高效，還提供了介面。程式設計師可以在任何適當的地方使用它們。

容器可以分為序列式容器和關聯式容器兩大類。序列式容器主要有 vector、list 和 deque；關聯式容器包括 set、map、multiset 和 multimap 等容器模板類。

演算法

STL 提供了非常多的資料結構演算法。這些演算法在名稱空間 std 的範圍內定義，通過包含標頭檔案 <algorithm> 來獲得使用權。

常見的部分演算法如下：
  • for_each()；
  • find()；
  • find_if()；
  • count()；
  • count_if()；
  • replace()；
  • replace_if()；
  • copy()；
  • unique_copy()；
  • sort()；
  • equal_range()；
  • merge()；

STL 中的所有演算法都是基於模板實現的。

疊代器

通俗來講，疊代器就是指示器。疊代器技術能夠使程式非常快捷地實現對 STL 容器中內容的反復存取。反復存取意味著一次可以存取一個或多個元素。

疊代器為存取容器提供了通用的方法，類似於 C++ 的指標。當引數化型別是 C++ 內部型別時，疊代器即 C++ 指標。

STL 定義了 5 種型別的指示器，並根據其使用方法予以命名。每種容器都支援某種類別的疊代器。常見的疊代器包括輸入、輸出、前向、雙向和隨機接入等類別：
  • 輸入疊代器主要用於為程式中需要的資料來源提供輸入介面，此處的資料來源一般指容器、資料流等。輸入疊代器只能從一個序列中讀取數值。該疊代器可以被修改和被參照。
  • 輸出疊代器主要用於輸出程式中已經得到的資料結果（容器，資料流）。輸出疊代器只能向一個序列寫入資料。該疊代器也可以被修改和被參照。
  • 雙向疊代器既可以用來讀又可以用來寫，它與前向疊代器相類似。雙向疊代器可以同時進行前向和後向元素操作。所有 STL 容器都提供了雙向疊代器功能，這既有利於資料的寫入和讀出，又有利於提供更加靈活的資料操作。
  • 有的容器甚至提供了隨機接入疊代器。隨機接人疊代器可以通過跳躍的方式存取容器中的任意資料，使資料的存取非常靈活。隨機存取疊代器具有雙向疊代器的所有功能，是功能最強大的疊代器型別。

疊代器的誕生使演算法和容器分離成為可能。演算法是模板，其型別依賴於迭代器，不會侷限於單一容器。不同的 STL 演算法需要不同型別的疊代器來實現相應的功能。因為不同型別的 STL 容器支援不同型別的疊代器，所以不能對所有容器使用相同的演算法。

仿函數

STL 包含了大量仿函數。彷函數可以理解為函數的一般形式。對於程式設計來說，彷函數非常重要，並有幾種約束。在 C++ 標準中，函數呼叫一般使用指標，當需要呼叫函數時，只需要提供函數的地址即可。例如：
static int cmp (int* i, int* j)
{
    return (*i - *j);
}
上述程式碼定義了一個 cmp() 函數，當需要呼叫此函數時，只需提供函數的地址即可。例如：

qsort(a,10,sizeof(int), cmp);

此方法的最大缺陷是效率低。為提高效率，STL 定義了仿函數這種概念。下述程式碼定義了一個仿函數，其特徵是使用 operator 實現定義。
struct three_mul
{
    bool operator() (int& v)
    {
        return (v%3 ==0)
    }
}
通過運算子定義顯著提高效率。例如，

for_each (myvector.begin (), myvector.end(), three_mul);

記憶體設定器和配接器

STL 包括底層的記憶體分配和釋放。記憶體設定器非常少見，在此可以忽略，在後面章節專門介紹。

配接器可以實現不同類之間的資料轉換。最常用的配接器有 istream_temtor，它提供了函數複製的介面。配接器對於 STL 技術來說非常重要。

STL 提供了 3 種容器配接器，分別是： 
stack <Container>;
queue <Container>;
deque <Container>;
看這樣一個程式： 
#include <iostream>
#include <stack>
using namespace std;
int main ()
{
    stack <int> st; //定義堆疊物件
    for (int i = 0;i <10;i ++ )
        st.push (i); //將資料壓入堆錢
    while (!st.empty())
    {
        cout << st.top() << " "; //彈出堆找的第一個元素，並輸出
        st.pop(); //彈出堆疊元素
    }
    cout<< endl;
    cin.get();    //任意鍵退出
    return 0;
}
程式執行結果為：

9 8 7 6 5 4 3 2 1 0

STL 使用方法

STL 作為 C++ 通用庫，主要由疊代器、演算法、容器、仿函數、記憶體設定器和配接器等六大部分組成。程式設計師使用 STL 容器能夠實現多種標準型別且操作便捷的容器。

對於程式設計人員，標準化元件意味著直接使用現成的元件，不用重複開發。使用 STL 最重要的是掌握基本理論和程式設計方法，了解 STL 程式設計技術，必須深刻掌握 STL 容器技術和 STL 疊代器技術。

STL 提供了一組表示容器、疊代器、仿函數和演算法的模板：
  • 容器是類似陣列的單元，可儲存 若干個值，且STL容器是同質的，即儲存的值型別相同；
  • 演算法是完成特定任務的處方；
  • 疊代器能夠用來遍歷容器的物件，與能夠遍歷陣列的指標類似，是廣義指標；
  • 仿函數是類似於函數的物件，可以是類物件或函數指標。

STL 使程式設計師能夠構造各種容器和執行各種操作。

下面以向量為例，簡要講述向量模板的使用。

在數學計算和 STL 模板中，vector 對應陣列，提供與 valarray 和 ArrayTP 類似的操作。而 STL 為使 vector 向量具備通用性，在標頭檔案 <vector> 中定義了 vector 模板。具體方法為：建立 vector 模板物件，使用通常的 <type> 表示法指出要使用的型別；然後使用初始化引數決定向量的大小，並定義向量動態記憶體。例如：
#include <vector>
using namespace std;    //使用名稱空間 std
vector <int> ratings (5);    //定義向量物件 int n;
cin >> n;    //輸入向量大小
vector <double> scores (n);    //定義向量動態記憶體
記憶體分配器是用來管理物件記憶體的。在 STL 容器模板中，一般都有一個可選的模板引數。例如：
template <class T, class Allocator = allocator <T>>//向量模板
class vector {
    ...
}
若省略該模板引數的值，則容器模板將預設使用 allocator<T> 類。類 allocator 以標準形式使用 new 和 delete 記憶體管理方式。

下面舉例說明，建立兩個 vector 物件：一個是 int 規範；另一個是 string 規範： 
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int NUM = 5;
int main ()
{
    vector <string>names(NUM);    //定義向量物件
    vector <int> sexs (NUM);    //同上
    cout<<"Please Do Exactly As Told You Will enter n"<<NUM<<" Personal Name and Their Sex.n";
    int i =0;
    for (i = 0;i <NUM;i++)    //輸入資訊
    {
        cout << "Enter title # " << i +1 << ": ";
        getline (cin, names[i]) ; //獲取輸入資訊
        cout << "Enter sex (0/1) #";
        cin >> sexs [i];    //獲取輸入資訊
        cin.get ();    //等待
    }
    cout << "Thank you. You entered the following:    n"<< "name/sex" << endl;
    for (i = 0; i <NUM; i++ )    //輸出資訊
    {
        cout <<names[i] << "t" << sexs[i] << endl;
    }
    return 0;
}
程式執行結果為：

Please Do Exactly As Told You Will enter
5 Personal Name and Their Sex.
Enter title # 1: A
Enter sex (0/1) #1
Enter title # 2: B
Enter sex (0/1) #1
Enter title # 3: D
Enter sex (0/1) #0
Enter title # 4: E
Enter sex (0/1) #1
Enter title # 5: E
Enter sex (0/1) #1
Thank you. You entered the following:
name/sex
A       1
B       1
D       0
E       1
E       1