5. STL Components(page73)
5.1 STL組件
容器containers:用于管理某類對象的集合。
迭代器Iterators:用于在一個對象群集(collection of object)的元素進(jìn)行遍歷操作。
優(yōu)點(diǎn):為所有容器提供了一組公共接口。
迭代器接口和指針差不多，以operator++累進(jìn)，以operator*提領(lǐng)所指之值。
算法Algorithm:用于處理群集內(nèi)的元素，可以出于不同的目的而搜尋、排序、修改、使用那些元素。
STL基本觀念：將數(shù)據(jù)和操作分離。數(shù)據(jù)由容器類別管理，操作由定制的算法定義，迭代器在二者之間作為粘合劑，使得任何算法都可和任何容器交互。
5.2 容器(COntainers)(page75)
總的來說容器可分兩類：
1. 序列式容器Sequence containers:可序ordered群集，
元素有固定位置且位置取決于插入時機(jī)和地點(diǎn)而與元素值無關(guān)，vector/deque/list。
2. 關(guān)聯(lián)式容器Associative containers:已序sorted群集，
元素位置取決于特定的排序準(zhǔn)則而與元素值有關(guān)，set/multiset/map/multimap。
關(guān)聯(lián)式容器可視作特殊的序列式容器，因?yàn)橐研?sorted)群集是據(jù)某個排序準(zhǔn)則排列(ordered)而成的。
關(guān)聯(lián)式容器自動對元素排序，也可以對序列式容器手動排序。
自動排序優(yōu)點(diǎn)是：搜尋元素時效率更高。
5.2.1 序列式容器(Sequence Containers)
STL內(nèi)部預(yù)先定義好了三個序列式容器：Vector、Deque、List。
此外也可將string和array當(dāng)做一種序列式容器。
5.2.1.1 Vector(page76)
vector將元素置于一個dynamic array中管理。
支持隨機(jī)存取。尾部增刪元素很快，但中部和頭部增刪元素費(fèi)時。
(因?yàn)樵鰟h后要保持原本相對次序，需要移動很多元素)。
note:元素增加操作是一種“分?jǐn)偤蟮?amortized)”的快速。單一的元素附加操作可能是緩慢的，因?yàn)関ector可能要重新分配內(nèi)存并將現(xiàn)有元素拷貝到新位置。但重配內(nèi)存的情況很少，故元素增加操作總體上很快。
eg:
//對整數(shù)型別定義一個vector,插入6個元素并打印
// stl/vector1.cpp
#include <iostream>
#include <vector> /*包含vector的頭文件*/
using namespace std;
int main()
{
vector<int> col1; // vector container for integer elements
//由于沒有任何初始化參數(shù)，缺省構(gòu)造函數(shù)將它構(gòu)建為空群集
// append elements with values 1 to 6
for (int i = 1; i <= 6; ++i)
{
col1.push_back(i); //push_back函數(shù)可為容器附加元素
}
// print all elements followed by a space
for (int i = 0; i < col1.size(); ++i) // size()返回容器內(nèi)元素個數(shù)
{
cout << col1[i] << ' ';
}
cout << endl;
}
所有序列式容器都提供push_back此函數(shù)；所有容器都提供size()函數(shù)
5.2.1.2 Deque(page78)
Deque是 double-ended queue的縮寫。
deque是一個dynamic array，可向兩端發(fā)展——即雙端隊(duì)列，
故尾部和頭部增刪元素很快，而中部增刪元素費(fèi)時。
eg:
/*聲明一個浮點(diǎn)數(shù)型別的deque，并在容器頭部插入1.1至6.6共6個元素并打印
*/
// stl/deque1.cpp
#include <iostream>
#include <deque> // 包含deque的頭文件
using namespace std;
int main()
{
deque<float> col1; //deque container for floating-point elements
// 產(chǎn)生一個空的浮點(diǎn)數(shù)群集
// insert elements from 1.1 to 6.6 each at the front
for (int i = 1; i <= 6; ++i)
{
col1.push_front(i*1.1); // insert at the front
}
// print all elements followed by a space
for (int i = 0; i < col1.size(); ++i)
{
cout << col1[i] << ' ';
}
cout << endl;
}
vector并未提供push_front()，因?yàn)樵趘ector頭部增加元素需要移動全部元素，其時間性能很差。一般而言，STL容器只提供通常具有良好時間效能的成員函數(shù)(所謂“良好時間效能”通常指常數(shù)或?qū)?shù)復(fù)雜度)，如此可防止程序員調(diào)用性能差的函數(shù)。
5.2.1.3 List(page79)
List是雙向鏈表(double linked list)。
即list內(nèi)每個元素都以部分內(nèi)存指示其前驅(qū)元素和后繼元素。
不支持隨機(jī)存取，存取元素的性能比vector和deque差很多。
增刪元素操作為常數(shù)時間。
eg:
/* 生成一個空的list，準(zhǔn)備放置字符，然后將'a'至'z'的
* 所有字符插入其中，利用循環(huán)每次打印并移除群集的
* 第一個元素，從而打印所有元素
*/
// stl/list1.cpp
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<char> col1; // list container for character elements
// append elements from 'a' to 'z'
for (char c = 'a'; c <= 'z'; ++c)
{
col1.push_back(c);
}
/* print all elements
* - while there are elements
* - print and remove the first element
*/
while (! col1.empty())
{
cout << col1.front() << ' ';
col1.pop_front();
}
cout << endl;
}
成員函數(shù)empty()返回false表明容器內(nèi)還有元素；front()返回第一個元素，pop_front()刪除第一個元素但不會返回該刪除元素。
5.2.1.4 String/Array(page81)
可將string當(dāng)做STL容器來用,此處string指C++ string類(basic_string<>,string,wstring)的對象，string和vector相似，只是元素為字符，詳見p497。
另一種容器不是類別(class)，而是C/C++所支持的型別(type):具有靜態(tài)或動態(tài)大小的array。array不是STL容器，沒有size()/empty()等成員函數(shù)，但STL的設(shè)計(jì)允許針對array調(diào)用STL算法(詳見page218)。
5.2.2 關(guān)聯(lián)式容器(Associative Containers)(page81)
關(guān)聯(lián)式容器依據(jù)特定排序準(zhǔn)則，自動為元素排序。
排序準(zhǔn)則以函數(shù)形式呈現(xiàn)，用于比較元素值value或元素鍵key。
缺省情況下以 operator< 進(jìn)行比較，當(dāng)然也可自定義比較函數(shù)。
通常關(guān)聯(lián)式容器是二叉排序樹，左子樹元素都比自己小，右子樹元素都比自己大。
關(guān)聯(lián)式容器差別在于元素類型及處理重復(fù)元素的方式。
STL預(yù)先定義了四種關(guān)聯(lián)容器，訪問元素要用到迭代器(iterator):
set: 內(nèi)部元素按值 自動排序，元素值不能重復(fù)。
Multiset: 和set相同，只不過允許重復(fù)元素。
map:內(nèi)部元素都是 key/value 所形成的一個對組(key/value pair)。
每個元素都有一個key,容器map按key排序且不允許key重復(fù)。
map可視為 關(guān)聯(lián)式數(shù)組，即具有任意索引型別的數(shù)組。
Multimap:和map相同，但允許重復(fù)key元素。
Multimap可視作 “字典”使用。
所有關(guān)聯(lián)式容器都有個可選擇的template參數(shù)，用于指明排序準(zhǔn)則。缺省是operator<。
排序準(zhǔn)則同時用于測試互等性：若兩元素都不小于對方，則視兩者相等。
可將set視作特殊的map：元素值就是鍵值。
5.2.3 容器配接器(Container Adapters)(page82)
除了上述幾個基本容器(vector/deque/list/set/multiset/map/multimap,string/array也算吧)，C++標(biāo)準(zhǔn)程序庫還提供了其它特別的(且預(yù)先定義好的)容器配接器(都是根據(jù)基本容器修改而定義的)：
stack:棧，內(nèi)部元素 LIFO(后進(jìn)先出)。
queue:隊(duì)列，內(nèi)部元素FIFO(先進(jìn)先出)，即是一個普通的緩沖區(qū)(buffer)。
priority queue:內(nèi)部元素可有不同的優(yōu)先權(quán)，
優(yōu)先權(quán)是基于程序員提供的排序準(zhǔn)則(缺省為 operator<)而定義。
priority queue相當(dāng)與一個這樣的buffer：下個元素是queue中優(yōu)先權(quán)最高的元素。
若同時有多個元素具備最高優(yōu)先權(quán)，則其次序無明確定義。
5.3 迭代器(iterator)(page83)
迭代器：是個“可遍歷STL容器內(nèi)元素”的對象。
一個迭代器用來支出容器中一個特定位置。基本操作如下：
operator* :返回當(dāng)前位置上的元素值；
若該元素含有成員，可用迭代器以operator-> 取用它們(有些老舊STL不支持)。
operator++ :將迭代器前進(jìn)至下一元素；多數(shù)迭代器還可使用operator-- 退回前一個元素。
operator==和operator!= :判斷兩個迭代器是否指向同一位置。
operator= :為迭代器賦值(將所指元素的位置賦值過去)。
迭代器是個所謂的smart pointer，具有遍歷復(fù)雜數(shù)據(jù)結(jié)構(gòu)的能力。
其下層運(yùn)行極值取決于所遍歷的數(shù)據(jù)結(jié)構(gòu)，故每種容器型別須提供自己的迭代器。
事實(shí)上每種容器都將迭代器以嵌套(nested)方式定義于內(nèi)部。
故各種迭代器接口相同而型別不同，這直接導(dǎo)出泛型程序設(shè)計(jì)的概念：型別不同但操作行為使用相同接口。
所有容器類都提供一些成員函數(shù)以獲得迭代器，從而訪問容器內(nèi)部元素，最重要的是：
begin() :返回一個指向容器起始點(diǎn)的迭代器，即首元素(如果有的話)的位置。
end() :返回一個指向容器結(jié)束點(diǎn)的迭代器，結(jié)束點(diǎn)在最后一個元素之后。
begin()和end()形成一個半開區(qū)間(half-open range)。半開區(qū)間有兩個優(yōu)點(diǎn)：
1. 為“遍歷元素時，循環(huán)的結(jié)束”提供一個判斷依據(jù)。只要尚未到達(dá)end()，循換就繼續(xù)。
2. 不必對空區(qū)間采取特殊處理?？諈^(qū)間的begin()就等于end()。
eg:
/* 展現(xiàn)迭代器的用法，打印list容器內(nèi)的所有元素(即 list1.cpp的改進(jìn)版)
*/
// stl/list2.cpp
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<char> col1; // list container for character elements
// append elements from 'a' to 'z'
for (char c = 'a'; c <= 'z'; ++c)
{
col1.push_back(c);
}
/* print all elements
* - iterator over all elements
*/
list<char>::const_iterator pos;
for (pos = col1.begin(); pos != col1.end(); ++pos)
{
cout << *pos << ' ';
}
cout << endl;
}
任何容器都定義有兩種迭代器型別：(page85)
- container::iterator 以“讀/寫”模式遍歷元素。
- container::const_iterator 以“只讀”模式遍歷元素。
為什么使用++pos而不是pos++:
note:前置式遞增(preincrement)比后置式遞增(postincrement)效率高。后置式遞增需要額外的臨時對象，因?yàn)樗仨毚娣旁挡⑵浞祷?。同理遞減--操作。
5.3.1 關(guān)聯(lián)式容器示例(page87)
上例list2.cpp中的迭代器循換可應(yīng)用于任何容器，只需調(diào)整迭代器型別即可。
eg1:set和multiset示例
/* 展示如何在set中插入元素，并用迭代器打印出來
*/
// stl/set1.cpp
#include <iostream>
#include <set>
int main()
{
// type of the collection
typedef std::set<int> IntSet;
IntSet col1; // set container for int values
/* insert elements from 1 to 6 in arbitrary order
* - value 1 gets inserted twice
*/
col1.insert(3);
col1.insert(1);
col1.insert(5);
col1.insert(4);
col1.insert(1);
col1.insert(6);
col1.insert(2);
/* print all elements
* - iterate over all elements
*/
IntSet::const_iterator pos;
for (pos = col1.begin(); pos != col1.end(); ++pos)
{
std::cout << *pos << ' ';
}
std::cout << std::endl;
}
tips:
既然容器型別要多次用到，可定義個短點(diǎn)的名字，typedef set<int> IntSet;
IntSet采用缺省的排序規(guī)則即以operator< 為依據(jù)對元素排序(遞增排序)。
若希望是使用其它排序準(zhǔn)則，需要將該準(zhǔn)則傳入作為第二個template參數(shù)，
eg將元素遞減方式排序:typedef set<int , greater<int> > IntSet;
其中g(shù)reater<>是一個預(yù)先定義好的仿函數(shù)。
兩個“>”之間要有空格，否則">>"會被編譯器視為一個右移操作符。
所有關(guān)聯(lián)式容器都提供insert()成員函數(shù)用于插入元素。multiset和set的定義位于同一頭文件中。插入的新元素會根據(jù)排序準(zhǔn)則自動安插到正確位置。
迭代器是容器定義的，無論容器內(nèi)部結(jié)構(gòu)多復(fù)雜，它都知道如何行事。
eg:若迭代器指向第三個元素，操作符++便會移動到上端第四個元素，再一次++便會一道下方第五個元素。(關(guān)聯(lián)式容器中迭代器++操作 類似于 二叉樹 先序遍歷。)
eg2:Map和multimap 示例(page90)
map元素是鍵值對(key/value)，故聲明、插入、存取與set不同。
// stl/mmap1.cpp
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
// type of the collection
typedef multimap<int, string> IntStringMMap;
IntStringMMap col1; // container for int/string values
// insert some elements in arbitrary order
// - a value with key 1 gets inserted twice
col1.insert(make_pair(5,"tagged"));
col1.insert(make_pair(2,"a"));
col1.insert(make_pair(1,"this"));
col1.insert(make_pair(4,"of"));
col1.insert(make_pair(6,"strings"));
col1.insert(make_pair(1,"is"));
col1.insert(make_pair(3,"multimap"));
/* print all element values
* - iterate over all elements
* - element member second is the value
*/
IntStringMMap::iterator pos;
for (pos = col1.begin(); pos != col1.end(); ++pos)
{
cout << pos->second << ' ';
}
cout << endl;
}
由于"this"和"is"的鍵相同，二者順序可能反過來。
迭代器所指的是鍵值對(key/value pair)，需要先取出pair，再pos->second或(*pos).second取出value，同理pos->first。(有些老舊環(huán)境沒實(shí)現(xiàn)iterator->)
eg3:map作為關(guān)聯(lián)式數(shù)組(associative array)(page91)
若所有鍵值都是唯一的，可視其為一個關(guān)聯(lián)式數(shù)組(即索引可為任何型別)。(詳見page205)
// stl/map1.cpp
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
/* type of the container:
* -map: elements key/value pairs
* -string: keys have type string
* -float: values have type float
*/
typedef map<string,float> StringFloatMap;
StringFloatMap col1;
// insert some elements into the collection
col1["VAT"] = 0.15;
col1["Pi"] = 3.1415;
col1["an arbitrary number"] = 4983.233;
col1["Null"] = 0;
/* print all elements
* -iterator over all elements
* -element member first is the key
* -element member second is the value
*/
StringFloatMap::iterator pos;
for (pos = col1.begin(); pos != col1.end(); ++pos)
{
cout << "key: \"" << pos->first << "\" "
<< "value: " << pos->second << endl;
}
}
map1.cpp output：
5.3.2 迭代器分類(Iterator Categories)(page93)
迭代器的能力取決于容器的內(nèi)部結(jié)構(gòu)，STL只提供效率較好的操作。若容器允許隨機(jī)存取(如vector、deque)，那么它們的迭代器也能隨機(jī)操作。
根據(jù)能力不同,迭代器劃分為 5 類。STL預(yù)定義好的容器，均屬于以下兩種類型：
1. 雙向迭代器(Bidirectional iterator)
以遞增運(yùn)算前進(jìn)或遞減運(yùn)算后退。 eg:list、set、multiset、map、multimap
2. 隨機(jī)存取迭代器(Random access iterator)
具備雙向迭代器的所有屬性，還具備隨機(jī)訪問能力。
即隨機(jī)存取迭代器提供了“迭代器算術(shù)運(yùn)算”必要的操作符(和“一般指針的算術(shù)運(yùn)算”完全對應(yīng))。
可對迭代器增減偏移量、處理迭代器間的距離，或用</>操作符比較兩個迭代器。
eg:vector、deque、string
其他類型見page251
為了盡可能實(shí)現(xiàn)與容器型別無關(guān)的泛程序編程，最好不要使用隨機(jī)存取迭代器的特有操作。(取決于容器元素間地址是否連續(xù))(eg,最好使用 !=col1.end() 而不是 <col1.end())
5.4 算法(algorithm)(page94)
STL提供了一些標(biāo)準(zhǔn)算法，含查取、排序、拷貝等
算法是一種搭配迭代器使用的全局函數(shù)，如此的優(yōu)勢：可以對所有容器操作。
即多種型別的容器元素公用一套接口——泛型函數(shù)編程。
eg:
// 展現(xiàn)某些算法的使用方式
// stl/algo1.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> col1;
vector<int>::iterator pos;
// insert elements from 1 to 6 in arbitrary order
col1.push_back(2);
col1.push_back(5);
col1.push_back(4);
col1.push_back(1);
col1.push_back(6);
col1.push_back(3);
// find and print minimum and maximum elements
pos = min_element (col1.begin(), col1.end());
cout << "min: " << *pos << endl;
pos = max_element (col1.begin(), col1.end());
cout << "max: " << *pos << endl;
// sort all element
sort (col1.begin(), col1.end());
// find the first element with value 3
pos = find (col1.begin(), col1.end(), 3);
// reverse the order of the found element with value 3
// and all following elements
reverse (pos, col1.end());
// print all elements
for (pos = col1.begin(); pos != col1.end(); ++pos)
{
cout << *pos << ' ';
}
cout << endl;
}
- min_element()/max_element()，兩個參數(shù)，用于定義欲處理元素范圍。返回一個指向最小/大元素的迭代器。
若最小/大元素不只一個，返回第一個最小元素的位置。 - sort()，將“由兩個參數(shù)設(shè)定”的區(qū)間內(nèi)元素排序?？蛇x擇性傳入一個排序準(zhǔn)則，缺省是operator<。
- find()，在給定范圍內(nèi)查找某值。查找成功則返回一個指向目標(biāo)元素的迭代器，失敗則返回一個“逾尾(past-the-end)”迭代器即find()接受的第二參數(shù)。
- reverse()，將區(qū)間內(nèi)元素反轉(zhuǎn)放置。
5.4.1 區(qū)間(ranges)(page97)
算法都用來處理一個或多個區(qū)間內(nèi)的元素。須將區(qū)間首尾當(dāng)做兩個參數(shù)傳給算法。所有算法處理的都是半開區(qū)間([begin,end))。
使用半開區(qū)間可避免對空集另做處理，但：
// stl/find1.cpp
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int main()
{
list<int> col1;
list<int>::iterator pos;
// insert elements from 20 to 40
for (int i = 20; i <=40 ; ++i)
{
col1.push_back(i);
}
/* find position of element with value 3
* - there is none,so pos gets col1.end()
*/
pos = find (col1.begin(),col1.end(), // range
3); //value
/* reverse the order of elements between found element and the
* end --because pos is col1.end() if reverses an empty range
*/
reverse (pos, col1.end());
// find position of values 25 and 35
list<int>::iterator pos25,pos35;
pos25 = find (col1.begin(),col1.end(),25);
pos35 = find (col1.begin(),col1.end(),35);
/* print the maximum of the correspongding range
* - note: including pos25 but excluding pos35
*/
cout << "max: " << *max_element(pos25,pos35) << endl;
// process the elements including the last position
cout << "max: " << *max_element(pos25,++pos35) << endl;
}
為了使搜尋范圍包含35，須將元素35的下一位置傳入即++pos35。
5.4.2 處理多個區(qū)間(page101)
有些算法可同時處理多個區(qū)間，通常要設(shè)定第一個區(qū)間的起點(diǎn)和終點(diǎn)，
而其它區(qū)間只需設(shè)定起點(diǎn)即可，終點(diǎn)可由第一區(qū)間的元素數(shù)量推出。
eg:if(equal (coll1.begin(), coll1.end(), coll2.begin())){ //...}
coll2中參與比較的元素的數(shù)量間接取決于coll1內(nèi)的元素數(shù)量。
若某算法用于處理多個區(qū)間，務(wù)必確保第二(及其它)區(qū)間所擁有元素個數(shù)大于等于第一區(qū)間元素個數(shù)。尤其是拷貝操作時，eg:
// stl//copy1.cpp
#include <vector>
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int main()
{
list<int> coll1;
vector<int> coll2;
// insert elements from 1 to 9
for (int i = 1; i <= 9; ++i)
{
coll1.push_back(i);
}
// runtime error
// - overwrites nonexisting elements in the destination
copy (coll1.begin(), coll1.end(), // source
coll2.begin()); //destination
// ...
}
要想讓目標(biāo)空間夠大，一開始指定一個正確大小或者顯示改變其大小。這兩種辦法只適用于序列式容器。(因?yàn)殛P(guān)聯(lián)式容器不可能當(dāng)做覆寫型算法的操作目標(biāo)，見page115)eg:
// 展示如何增加容器大小
// stl/copy2.cpp
#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <algorithm>
using namespace std;
int main()
{
list<int> coll1;
vector<int> coll2;
// insert elements from 1 to 9
for (int i = 1; i <= 9; ++i)
{
coll1.push_back(i);
}
// resize destination to have enough room for the
// overwriting algorithm
coll2.resize(coll1.size());
/* copy elements from first into second collection
* - overwrites existing elements in destination
*/
copy (coll1.begin(), coll1.end(), // source
coll2.begin()); //destination
/* creates third collection with enough room
* - initial size is passed as parameter
*/
deque<int> coll3(coll1.size());
// copy elements from first into third collection
copy (coll1.begin(), coll1.end(), // source
coll3.begin()); //destination
}
coll2.resize(coll1.size());和deque<int> coll3(coll1.size());都會產(chǎn)生新元素并賦予初值。
