The|The C++ standard library(侯捷/孟岩译) 03--STL简述一 TheC++standardlibrary(侯捷

5. STL Components(page73) 5.1 STL组件

容器containers:用于管理某类对象的集合。迭代器Iterators:用于在一个对象群集(collection of object)的元素进行遍历操作。优点:为所有容器提供了一组公共接口。迭代器接口和指针差不多，以operator++累进，以operator*提领所指之值。算法Algorithm:用于处理群集内的元素，可以出于不同的目的而搜寻、排序、修改、使用那些元素。

STL基本观念：将数据和操作分离。数据由容器类别管理，操作由定制的算法定义，迭代器在二者之间作为粘合剂，使得任何算法都可和任何容器交互。

The|The C++ standard library(侯捷/孟岩译) 03--STL简述一

文章图片
p74_p5-1.png
5.2 容器(COntainers)(page75)

文章图片
p75_p5-2.png
【The|The C++ standard library(侯捷/孟岩译) 03--STL简述一】总的来说容器可分两类：

1. 序列式容器Sequence containers:可序ordered群集，元素有固定位置且位置取决于插入时机和地点而与元素值无关，vector/deque/list。2. 关联式容器Associative containers:已序sorted群集，元素位置取决于特定的排序准则而与元素值有关，set/multiset/map/multimap。关联式容器可视作特殊的序列式容器，因为已序(sorted)群集是据某个排序准则排列(ordered)而成的。关联式容器自动对元素排序，也可以对序列式容器手动排序。自动排序优点是：搜寻元素时效率更高。

5.2.1 序列式容器(Sequence Containers) STL内部预先定义好了三个序列式容器：Vector、Deque、List。
此外也可将string和array当做一种序列式容器。
5.2.1.1 Vector(page76)

vector将元素置于一个dynamic array中管理。支持随机存取。尾部增删元素很快，但中部和头部增删元素费时。 (因为增删后要保持原本相对次序，需要移动很多元素)。

note:元素增加操作是一种“分摊后的(amortized)”的快速。单一的元素附加操作可能是缓慢的，因为vector可能要重新分配内存并将现有元素拷贝到新位置。但重配内存的情况很少，故元素增加操作总体上很快。
eg:

//对整数型别定义一个vector,插入6个元素并打印 // stl/vector1.cpp #include #include /*包含vector的头文件*/ using namespace std; int main() { vector col1; // vector container for integer elements //由于没有任何初始化参数，缺省构造函数将它构建为空群集// append elements with values 1 to 6 for (int i = 1; i <= 6; ++i) { col1.push_back(i); //push_back函数可为容器附加元素 }// print all elements followed by a space for (int i = 0; i < col1.size(); ++i)// size()返回容器内元素个数 { cout << col1[i] << ' '; } cout << endl; }

所有序列式容器都提供push_back此函数；所有容器都提供size()函数
5.2.1.2 Deque(page78) Deque是 double-ended queue的缩写。

deque是一个dynamic array，可向两端发展——即双端队列，故尾部和头部增删元素很快，而中部增删元素费时。 eg: /*声明一个浮点数型别的deque，并在容器头部插入1.1至6.6共6个元素并打印 */ // stl/deque1.cpp#include #include // 包含deque的头文件 using namespace std; int main() { deque col1; //deque container for floating-point elements // 产生一个空的浮点数群集// 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()，因为在vector头部增加元素需要移动全部元素，其时间性能很差。一般而言，STL容器只提供通常具有良好时间效能的成员函数(所谓“良好时间效能”通常指常数或对数复杂度)，如此可防止程序员调用性能差的函数。
5.2.1.3 List(page79)

List是双向链表(double linked list)。即list内每个元素都以部分内存指示其前驱元素和后继元素。不支持随机存取，存取元素的性能比vector和deque差很多。增删元素操作为常数时间。eg: /* 生成一个空的list，准备放置字符，然后将'a'至'z'的 * 所有字符插入其中，利用循环每次打印并移除群集的 * 第一个元素，从而打印所有元素 */ // stl/list1.cpp#include #include using namespace std; int main() { list 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; }

成员函数empty()返回false表明容器内还有元素；front()返回第一个元素，pop_front()删除第一个元素但不会返回该删除元素。
5.2.1.4 String/Array(page81) 可将string当做STL容器来用,此处string指C++ string类(basic_string<>,string,wstring)的对象，string和vector相似，只是元素为字符，详见p497。
另一种容器不是类别(class)，而是C/C++所支持的型别(type):具有静态或动态大小的array。array不是STL容器，没有size()/empty()等成员函数，但STL的设计允许针对array调用STL算法(详见page218)。
5.2.2 关联式容器(Associative Containers)(page81)

关联式容器依据特定排序准则，自动为元素排序。排序准则以函数形式呈现，用于比较元素值value或元素键key。缺省情况下以 operator< 进行比较，当然也可自定义比较函数。

通常关联式容器是二叉排序树，左子树元素都比自己小，右子树元素都比自己大。
关联式容器差别在于元素类型及处理重复元素的方式。
STL预先定义了四种关联容器，访问元素要用到迭代器(iterator):

set: 内部元素按值自动排序，元素值不能重复。 Multiset: 和set相同，只不过允许重复元素。map:内部元素都是 key/value 所形成的一个对组(key/value pair)。每个元素都有一个key,容器map按key排序且不允许key重复。 map可视为关联式数组，即具有任意索引型别的数组。 Multimap:和map相同，但允许重复key元素。 Multimap可视作 “字典”使用。

所有关联式容器都有个可选择的template参数，用于指明排序准则。缺省是operator<。
排序准则同时用于测试互等性：若两元素都不小于对方，则视两者相等。
可将set视作特殊的map：元素值就是键值。
5.2.3 容器配接器(Container Adapters)(page82) 除了上述几个基本容器(vector/deque/list/set/multiset/map/multimap,string/array也算吧)，C++标准程序库还提供了其它特别的(且预先定义好的)容器配接器(都是根据基本容器修改而定义的)：

stack:栈，内部元素 LIFO(后进先出)。queue:队列，内部元素FIFO(先进先出)，即是一个普通的缓冲区(buffer)。priority queue:内部元素可有不同的优先权，优先权是基于程序员提供的排序准则(缺省为 operator<)而定义。 priority queue相当与一个这样的buffer：下个元素是queue中优先权最高的元素。若同时有多个元素具备最高优先权，则其次序无明确定义。

5.3 迭代器(iterator)(page83)

迭代器：是个“可遍历STL容器内元素”的对象。一个迭代器用来支出容器中一个特定位置。基本操作如下： operator*:返回当前位置上的元素值；若该元素含有成员，可用迭代器以operator-> 取用它们(有些老旧STL不支持)。operator++:将迭代器前进至下一元素；多数迭代器还可使用operator-- 退回前一个元素。operator==和operator!=:判断两个迭代器是否指向同一位置。operator=:为迭代器赋值(将所指元素的位置赋值过去)。迭代器是个所谓的smart pointer，具有遍历复杂数据结构的能力。其下层运行极值取决于所遍历的数据结构，故每种容器型别须提供自己的迭代器。

事实上每种容器都将迭代器以嵌套(nested)方式定义于内部。
故各种迭代器接口相同而型别不同，这直接导出泛型程序设计的概念：型别不同但操作行为使用相同接口。
所有容器类都提供一些成员函数以获得迭代器，从而访问容器内部元素，最重要的是：

begin() :返回一个指向容器起始点的迭代器，即首元素(如果有的话)的位置。 end() :返回一个指向容器结束点的迭代器，结束点在最后一个元素之后。begin()和end()形成一个半开区间(half-open range)。半开区间有两个优点： 1. 为“遍历元素时，循环的结束”提供一个判断依据。只要尚未到达end()，循换就继续。 2. 不必对空区间采取特殊处理。空区间的begin()就等于end()。eg: /* 展现迭代器的用法，打印list容器内的所有元素(即 list1.cpp的改进版) */ // stl/list2.cpp#include #include using namespace std; int main() { list 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::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)效率高。后置式递增需要额外的临时对象，因为它必须存放原值并将其返回。同理递减--操作。
5.3.1 关联式容器示例(page87) 上例list2.cpp中的迭代器循换可应用于任何容器，只需调整迭代器型别即可。
eg1:set和multiset示例

/* 展示如何在set中插入元素，并用迭代器打印出来 */ // stl/set1.cpp#include #include int main() { // type of the collection typedef std::set 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:

既然容器型别要多次用到，可定义个短点的名字，typedef set IntSet; IntSet采用缺省的排序规则即以operator< 为依据对元素排序(递增排序)。若希望是使用其它排序准则，需要将该准则传入作为第二个template参数， eg将元素递减方式排序:typedef set > IntSet; 其中greater<>是一个预先定义好的仿函数。两个“>”之间要有空格，否则">>"会被编译器视为一个右移操作符。

所有关联式容器都提供insert()成员函数用于插入元素。multiset和set的定义位于同一头文件中。插入的新元素会根据排序准则自动安插到正确位置。
迭代器是容器定义的，无论容器内部结构多复杂，它都知道如何行事。
eg:若迭代器指向第三个元素，操作符++便会移动到上端第四个元素，再一次++便会一道下方第五个元素。(关联式容器中迭代器++操作类似于二叉树先序遍历。)

文章图片
p89_p5-6.png
eg2:Map和multimap 示例(page90)
map元素是键值对(key/value)，故声明、插入、存取与set不同。

// stl/mmap1.cpp#include #include #include using namespace std; int main() { // type of the collection typedef multimap 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。(有些老旧环境没实现iterator->)
eg3:map作为关联式数组(associative array)(page91)
若所有键值都是唯一的，可视其为一个关联式数组(即索引可为任何型别)。(详见page205)

// stl/map1.cpp#include #include #include 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 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：

文章图片
map1.png 5.3.2 迭代器分类(Iterator Categories)(page93) 迭代器的能力取决于容器的内部结构，STL只提供效率较好的操作。若容器允许随机存取(如vector、deque)，那么它们的迭代器也能随机操作。

根据能力不同,迭代器划分为 5 类。STL预定义好的容器，均属于以下两种类型： 1. 双向迭代器(Bidirectional iterator) 以递增运算前进或递减运算后退。eg:list、set、multiset、map、multimap 2. 随机存取迭代器(Random access iterator) 具备双向迭代器的所有属性，还具备随机访问能力。即随机存取迭代器提供了“迭代器算术运算”必要的操作符(和“一般指针的算术运算”完全对应)。可对迭代器增减偏移量、处理迭代器间的距离，或用操作符比较两个迭代器。 eg:vector、deque、string其他类型见page251

为了尽可能实现与容器型别无关的泛程序编程，最好不要使用随机存取迭代器的特有操作。(取决于容器元素间地址是否连续)(eg,最好使用 !=col1.end() 而不是 5.4 算法(algorithm)(page94)

STL提供了一些标准算法，含查取、排序、拷贝等算法是一种搭配迭代器使用的全局函数，如此的优势：可以对所有容器操作。即多种型别的容器元素公用一套接口——泛型函数编程。eg: // 展现某些算法的使用方式 // stl/algo1.cpp#include #include #include using namespace std; int main() { vector col1; vector::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()，两个参数，用于定义欲处理元素范围。返回一个指向最小/大元素的迭代器。
若最小/大元素不只一个，返回第一个最小元素的位置。
sort()，将“由两个参数设定”的区间内元素排序。可选择性传入一个排序准则，缺省是operator<。
find()，在给定范围内查找某值。查找成功则返回一个指向目标元素的迭代器，失败则返回一个“逾尾(past-the-end)”迭代器即find()接受的第二参数。
reverse()，将区间内元素反转放置。

5.4.1 区间(ranges)(page97) 算法都用来处理一个或多个区间内的元素。须将区间首尾当做两个参数传给算法。所有算法处理的都是半开区间([begin,end))。
使用半开区间可避免对空集另做处理，但：

// stl/find1.cpp#include #include #include using namespace std; int main() { list col1; list::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::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 处理多个区间(page101)

有些算法可同时处理多个区间，通常要设定第一个区间的起点和终点，而其它区间只需设定起点即可，终点可由第一区间的元素数量推出。 eg:if(equal (coll1.begin(), coll1.end(), coll2.begin())){//...} coll2中参与比较的元素的数量间接取决于coll1内的元素数量。

若某算法用于处理多个区间，务必确保第二(及其它)区间所拥有元素个数大于等于第一区间元素个数。尤其是拷贝操作时，eg:

// stl//copy1.cpp#include #include #include #include using namespace std; int main() { list coll1; vector 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 // ... }

要想让目标空间够大，一开始指定一个正确大小或者显示改变其大小。这两种办法只适用于序列式容器。(因为关联式容器不可能当做覆写型算法的操作目标，见page115)eg:

// 展示如何增加容器大小 // stl/copy2.cpp#include #include #include #include #include using namespace std; int main() { list coll1; vector 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 coll3(coll1.size()); // copy elements from first into third collection copy (coll1.begin(), coll1.end(),// source coll3.begin()); //destination }

coll2.resize(coll1.size()); 和deque coll3(coll1.size()); 都会产生新元素并赋予初值。