The C++ Standard Library 学习笔记（一）第5章

5. 标准模板库

5.1 STL组件

容器，泛型容器，管理对象的集合

迭代器，遍历容器对象的辅助对象，由各个容器提供。

算法，与具体容器分离，运用迭代器操作容器内对象。

STL主张将容器与算法分离，使得算法可以抽象与容器之上，同时操作不同类型的容器，但需要容器提供迭代器。

STL容器只提供效率高的方法，因此不同容器提供的方法可能不一样。

STL是最好的泛型编程的参考资料。

5.2 容器

两种容器

1. 顺序容器（Sequence Containers），元素的位置是确定的，和插入容器的顺序一致。这类容器有：vector, deque, list.

2. 关联容器（Associative Containers），元素是经过排列的，位置和元素的值，排序算法相关，这类容器有：set, multiset, map, multimap.

5.2.1 顺序容器（Sequence Containers）

vector

可以把vector看成是动态数组，在很多实现中，vector的数据部分就是动态数组。它的元素可以随机访问，可以用下标操作符访问。在它的末尾添加和删除元素的速度非常快，而在开始或中间就比较耗时，因为它需要移动元素。适合于访问频繁，而插入、删除操作较少的需求。

Deque

deque是双向队列（double-ended queue）的缩写。顾名思义，deque在头和尾插入元素是非常快的，而在中间则较慢。

List

list这里是双向链表，它不能被随机访问，因此它的访问时间是线性的，而它在任何位置插入和删除元素的时间却是常数时间。

5.2.2 关联容器（Associative Containers）

关联容器会自动将它的元素按某个条件（比较各个元素的key的大小）排序。关联容器一般都是以二叉树（binary tree）为基础实现

关联容器有：set，mutiset, map, mutimap.

5.2.3 容器适配器（Container Adapters）

STL提供了下面三种容器适配器：

Stack, Queue, Priority Queue.

5.3迭代器

容器的基本操作，适合于所有容器：

operator*，operator++，operator==，operator!=，and operator=。

容器同时也提供了基本的方法去初始化和遍历容器：

begin(), end()。

容器都有两种迭代器：

container::iterator，和container::const_iterator。

5.3.2 迭代器分类

一般情况下，如果容器可以随机访问，那么它的迭代器也可以随机访问。

迭代器根据其访问规则可分为：

1． 双向迭代器（Bidirectional iterator）

它只能递增或递减来向前或向后访问，这些迭代器的容器有：list，set，mutiset，map，和mutimap。

2． 随机访问迭代器（Random access iterator）

它除了能像双向迭代器一样前后访问外，它还能通过算数运算随机访问元素，并且能使用比较操作符如< 和>，这些迭代器的容器有：vector，deque，以及string。

5.4 算法

算法是STL中的全局函数，它可以通过迭代器操作STL的不同容器，甚至用户自定义的容器。

5.4.1 范围

算法所操作的元素都是以迭代器所表示的一个范围，它使得算法的运用更加灵活，但同时带来了危险：越界，这个需要程序员去保证。

算法所接受的范围都是一个迭代器指定的半开半闭的区间，即：[begin，end）

5.5 迭代器适配器

5.5.1 输入迭代器（Insert Iterator）

输入迭代器常用于算法的输出参数，它使得算法输出到一个能自动扩展空间的容器中，插入这个容器的位置由该迭代器指定。

1. Back Inserter

back_inserter调用容器的push_back方法，将元素追加到容器中，因此它只能适用于支持push_back方法的容器，如：vector。

2. Front Inserter

同样，front_inserter调用容器的push_front方法，将元素添加到容器开始，只适用于支持push_front方法的容器，如：deque，list。

3. Inserter

inserter将元素插入到，第二个参数指定的元素之前。只有他是可以用于关联容器的。

5.5.2 流迭代器（Stream Iterator）

流迭代器是一种从流（标准输入/输出，文件流等）中读取元素，或向流中写入元素。

5.5.3 反向迭代器（Reverse Iterator）

顾名思义，它逆向访问元素。所有的容器可以用rbegin()，和rend()来创建反向迭代器。

5.5.4 迭代器的例子

#include <iostream>

#include <vector>

#include <list>

#include <deque>

#include <set>

#include <algorithm>

using namespace std;

int main(int argc, char* argv)

{

const int N = 10;

//prepare elements

vector<int> ivec;

ivec.reserve(N);

for (int i = 0; i < N; ++i)

{

ivec.push_back(i);

}

//inserter iterator

list<int> il;

copy(ivec.begin(), ivec.end(), back_inserter(il));

deque<int> id;

copy(il.begin(), il.end(), front_inserter(id));

set<int> is;

copy(id.begin(), id.end(), inserter(is, is.begin()));

//stream iterator

//output will be: 0 1 2 3 4 5 6 7 8 9

copy(is.begin(), is.end(), ostream_iterator<int>(cout, " "));

cout << endl;

//reverse iterator

//output will be: 9 8 7 6 5 4 3 2 1 0

copy(il.rbegin(), il.rend(), ostream_iterator<int>(cout, " "));

cout << endl;

getchar();

return 0;

};

输出：

0 1 2 3 4 5 6 7 8 9

9 8 7 6 5 4 3 2 1 0

5.6 操作算法

5.6.1 删除元素

算法remove实际并不删除元素，而是将等于删除值的 位置用后面的元素覆盖掉，然后返回剩余元素的最后一个位置的迭代器。真正要删除元素，则要调用容器（顺序容器）的erase方法

例子：

#include <algorithm>

#include <list>

#include <iostream>

template<class Container>

void print(const Container& c, const char* promption)

{

cout << promption << endl;

copy(c.begin(), c.end(), ostream_iterator<Container::value_type>(cout, " "));

cout << endl;

}

using namespace std;

int main()

{

list<int> il;

//prepare elements

for (int i = 0; i < 6; ++i)

{

il.push_back(i);

il.push_front(i);

}

//print the original elements

print(il, "original elements:");

//call remove

list<int>::iterator end = remove(il.begin(), il.end(), 3);

//print the elements after remove

print(il, "after remove:");

//print number of elements

cout << "Number of removed elements: " << distance(end, il.end()) << endl;

//remove the removed elements

il.erase(end, il.end());

//print the elements after real remove

print(il, "after erase:");

//for 5.6.3

//call member function to get better performance

il.remove(4);

//print the elements after remove 4

print(il, "removed 4:");

getchar();

return 0;

}

输出：

original elements:

5 4 3 2 1 0 0 1 2 3 4 5

after remove:

5 4 2 1 0 0 1 2 4 5 4 5

Number of removed elements: 2

after erase:

5 4 2 1 0 0 1 2 4 5

removed 4:

5 2 1 0 0 1 2 5

5.6.2 操作算法和关联容器

注意不能将关联容器作为算法操作的目标容器，因为关联容器的元素的位置是自动排序后的树形结构，操作算法会破坏它的结构。

而关联容器提供了成员函数做诸如remove之类的操作。

5.6.3 成员函数vs 算法

结论：成员函数优先于算法的调用。

5.8 算法的函数参数

5.8.2 Predicates

Predicates即是返回bool值的函数参数，它可能是二元的，也可能是一元的，他们通常是排序或搜索的条件。STL对predicates有特定的要求，对同一个值predicate必须返回同样的结果。

5.9 函数对象（Function Object）

函数对象又称为仿函数（Functor），它也可以作为算法的函数参数。

5.9.1 什么是函数对象

函数对象是行为像函数的对象，因此它必须可以想调用函数那样调用它，也因此它必须重载括号（（））操作符。

函数对象的定义格式：

class Functor

{

public:

//overload operator ()

return_type operator()(arguments) const

{

...

}

};

为什么要使用函数对象，他的优势在哪里呢

1. 函数对象是智能函数

因为它是一个对象，因此它可以有成员函数，和成员变量，同时可以被实例化以应对不同的需求。

2. 每个函数对象有它自己的类型

普通的函数如果是不同的类型，那么只能它的函数原型不同，而函数对象可以通过传递不同的模板参数来生成不同的类型，尽管它们的原型都相同。

3. 通常情况下，函数对象的效率更高

模板在编译时定义了更多的细节，相对于普通函数更容易实现为内联函数。

例子：

#include <algorithm>

#include <iostream>

#include <vector>

#include <cstdlib>

using namespace std;

bool is_prime(int number)

{

//ignore the sign

number = abs(number);

//0 and 1 are prime numbers

if (0 == number || 1 == number)

return true;

//find divisor that divides without a reminder

int divisor;

for (divisor = number / 2; 0 != number % divisor; --divisor)

{

//nothing

}

return (1 == divisor);

}

template<class InputIterator, class OutputIterator, class Predicate>

void copy_if(InputIterator first, InputIterator last, OutputIterator begin, Predicate p)

{

while(first != last)

{

if (p(*first))

*(begin++) = *first;

++first;

}

}

template<class T>

class Greater

{

public:

Greater(T value_)

:_value(value_)

{

//empty

}

bool operator()(T in_) const

{

return (in_ > _value);

}

private:

T _value;

};

int main()

{

//prepare the elements

vector<int> ivec;

for (int i = 0; i <= 30; ++i)

{

ivec.push_back(i);

}

//search for prime elements

vector<int> primes;

copy_if(ivec.begin(), ivec.end(), back_inserter(primes), is_prime);

cout << "Primes:" << endl;

copy(primes.begin(), primes.end(), ostream_iterator<int>(cout, " "));

cout << endl;

//output the primes bigger than 5

cout << "Primes bigger than 5:" << endl;

copy_if(primes.begin(), primes.end(), ostream_iterator<int>(cout, " "), Greater<int>(5));

cout << endl;

getchar();

return 0;

}

输出：

Primes:

0 1 2 3 5 7 11 13 17 19 23 29

Primes bigger than 5:

7 11 13 17 19 23 29

5.9.2 预定义函数对象

STL提供了许多预定义的函数对象支持基本的操作，例如：set<int>的确实比较函数less<int>， 以及前面例子中的Greater，也有对应的greater<T>，还有作为取反操作的negate<T>，乘法运算的mutiplies<T>

例子：

#include <iostream>

#include <set>

#include <deque>

#include <algorithm>

using namespace std;

template<class Container>

void print(const Container& c, const char* promption)

{

cout << promption << endl;

copy(c.begin(), c.end(), ostream_iterator<Container::value_type>(cout, " "));

cout << endl;

}

int main()

{

set<int, greater<int> > iset;

deque<int> ide;

//prepare elements

for (int i = 1; i < 10; ++i)

{

iset.insert(i);

}

print(iset, "orignal set:");

//transform all elements to ide by multiplying 10

transform(iset.begin(), iset.end(),

back_inserter(ide), bind2nd(multiplies<int>(), 10));

print(ide, "transformed:");

//replace the value 30 to 200

replace_if(ide.begin(), ide.end(),

bind2nd(equal_to<int>(), 30), 200);

print(ide, "replaced:");

getchar();

return 0;

}

输出：

orignal set:

9 8 7 6 5 4 3 2 1

transformed:

90 80 70 60 50 40 30 20 10

replaced:

90 80 70 60 50 40 200 20 10

5.10 容器元素

5.10.1 容器元素的要求

容器元素必须满足以下条件：

1. 元素是可拷贝的，容器会在插入元素时创建元素的拷贝，因此元素的拷贝应该是高效的；

2. 元素是可通过复制操作符复制的；

3. 元素是可以被析构的，且析构函数应不抛出异常；

这些条件是所有容器通用的，此外一些特别的容器还有一些特别的需求：

1. 顺序容器的元素必须有缺省构造函数；

2. 很多操作需要 == 操作符；

3. 对于关联容器，作为排序条件操作必须要有，缺省是 <，由less<> 调用；

5.11 STL中的错误和异常

5.11.1 错误处理

STL的设计目标是更高的效率而不是安全性，因此STL没有引入更多的错误检查，而是由程序员来保证这一点。

5.11.2 异常处理

STL几乎不会因逻辑错误而抛出异常，标准唯一指出一个函数会抛出异常：at()，除此之外，则是标准C++的异常，如bad_alloc。

C++标准库保证：不会在异常发生时泄露资源或违反容器的不变性。

基于节点（node）的容器（如：list，map，set）在很多情况下（除开 remove，remove_if，merge，sort和unique）能保证操作的原子性。