wzf2000 C/C++ 语法教程（15）——STL 简介（2）
Contents
C++ STL
上次搞完，好像又咕了一个星期？被咕咕猫附体不能怪我
于是继续我们的现学现卖。
顺便提下我的学习网站：C 语言中文网。
我大概会自己选择（并拓展）一部分我觉得较为实用的 STL 进行学习讲解，也就是可能还有很多没有讲的成员函数及使用方法，但这并不影响你使用它。
在使用这里的 STL 时，还是建议先 using namespace std;，否则你可能需要疯狂打 std::。
序列容器
容器种类
- 数组容器：
array<T,N>，长度固定。 - 向量容器：
vector<T>，长度可变，但仅在末尾操作时保证较低复杂度。（常用） - 双向队列容器：
deque<T>，长度可变，自动增长，但在两端均不能高效地增加删除元素。 - 链表容器：
list<T>，长度可变，任何地方均可高效增加删除元素，但访问元素速度慢。 - 正向链表容器：
forward_list<T>，长度可变，基本就是单向链表的实现。
这里我们只讲 vector、deque 和 list。
vector 容器
定义与初始化
创建方法十分简单，如创建一个存放 int 类型的向量容器 v：
vector<int> v;
如果想设定一个初始容量（注意不是大小），比如 $20$，就可以：
vector<int> v(20);
这样会使容器初始有 $20$ 个元素，并且初始值均为 $0$。
如果希望改变初始值（改为 $233$），也可以：
vector<int> v(20,233);
如果想初始化一些数据，比如开始存有 $2,4,8,16$，就可以：
vector<int> v {2,4,8,16};
注意没有等于号。
在定义以及初始化后，如果希望改变容器容量（比如改成 $30$），可以使用 reserve() 方法：
v.reserve(30);
容量和大小
前面特意提到了容量和大小是不同的。
容量是指能容纳最多的元素个数，大小则是当前容纳的元素个数。
可以看出来容量一定大于等于大小。
容量和大小分别可以通过 capacity() 和 size() 函数获知。
比如：
vector<size_t> primes { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 ,43 ,47 };
cout << "The size is " << primes.size() << endl;
cout << "The capacity is" << primes.capacity() << endl;
输出：
The size is 15
The capacity is 15
注意，容量可能通过之后会提到的插入函数等函数改变，并且改变程度无从得知（除非你每一步都输出它的容量以实时监控，而且不同的实现也会导致不同的结果）。
如果你希望获得其内部的指针，也可以使用 data() 函数，这也说明了 vector 本质上还是使用数组实现的。（这段可以忽略）
访问元素
对于现存在的元素（下标小于 size()），可以通过 [] 运算符获得其引用，实现了看上去和数组基本相同的写法。
当然，更安全地，可以使用 at() 方法获取引用防止越界。
除此之外，还可以使用 front() 和 back() 成员函数获取首元素和末尾元素的引用（同样可以作为左值）。
vector<double> values (20);
values[0] = 3.14159;
values[1] = 5.0;
values[2] = 2.0*values[0]*values[1];
cout << values.front () << endl; // Outputs 3.14159
相关迭代器
vector 容器的迭代器同样是随机访问迭代器。
主要就是使用 begin() 和 end() 两种迭代器。
类似还有反向迭代器 rbegin() 和 rend()。
具体指向我相信大家也都知道。
插入元素
最常用的就是 push_back() 函数，作用是在容器末尾添加元素。
此函数会自动改变容器大小，也可能会改变容器的容量。
使用举例：
vector<double> values;
values.push_back(3.1415926);
除此之外，还有 emplace_back() 函数，其更有效率。
emplace_back() 的参数正是添加到容器中的对象对应类型的构造函数所需要的参数。
比如可以这样加入子串：
string str("alleged");
words.emplace_back(str,2,3);
// Create string object corresponding to "leg" in place
理论上还有在指定位置通过迭代器插入元素的 emplace() 和 insert() 函数，然而这些方法使用较为复杂，且复杂度较高，在此不做介绍。
删除元素
可以使用 clear() 方法清空 vector 容器，但是只会将大小清零，而容量不变。
也可以使用 pop_back() 方法来删除尾部元素，同样只会改变大小。
vector<int> data(100, 99);
data.pop_back(); // 大小变为 99，容量不变
data.clear(); // 大小清零，容量不变
除此之外还有 erase() 方法可以通过迭代器删除一个或者一段元素，使用简单但也不常用，不做介绍。
deque 容器
deque 容器最大的优点，就是可以双向插入删除。
定义与初始化
基本与 vector 相同。
但请注意没有了 reserve() 这个函数。
大小和访问元素
基本还是相同，但不再有容量的说法以及 capcity() 这个函数，并且也没有 data() 函数（毕竟不是用数组实现的嘛）。
插入和删除元素
在 vector 容器的基础上，增加了 push_front()、pop_front() 和 emplace_front() 方法，只是从末尾变成 了头部，其他没有任何区别。
相关迭代器
基本一样，但是注意在进行插入删除后，deque 容器的迭代器往往会失效，需要重新生成。
修改元素
可以使用 assign() 函数替换 deque 中现有的所有元素，方法跟 string 十分相似。
list 容器
定义、初始化及大小
与 deque 容器基本相同。
可以通过 resize() 方法改变大小：
- 若变小，则从尾部开始删除元素；
- 若变大，则在尾部加入用容器对象类型的默认构造函数来加入元素。
增加除素
同样含有 push_front() 和 push_back() 两个函数，当然也有更高效的 emplace_front() 和 emplace_back()。
因为是实现链表的功能（配合可能会出的数算学前班教程理解），所以讲一下 insert() 的一些使用：
list<int> data(5,233);
data.insert(++data.begin(),2333);
这样会在第二个元素的位置插入一个元素 $2333$，容器内容为：$233,2333,233,233,233,233$。
再加一个正整数参数可以表示，插入这个元素的几个副本（复制多少遍插入）。
删除元素
可以使用 erase() 和 clear()，方法相同。
也可以使用 remove() 函数移除和参数匹配的元素。
比如：
list<int> numbers {2,5,2,3,6,7,8,2,9};
numbers.remove(2); // List is now 5 3 6 7 8 9
除此之外，甚至还有 remove_if() 方法，其中可以接受一个函数对象或者 lambda 函数，用于描述删除元素的条件，比如：
numbers.remove_if([](int n){return n%2==0;});// Remove even numbers. Result 5 3 7 9
大概就是删除了其中所有的偶数。
还有一个神奇的 unique() 函数，可以移除连续的重复元素，只留下其中的第一个。
当然会用到类型的 == 运算符（如何重载之后会讲）。
如果你将其进行排序后再调用 unique() 函数，便能保证移除序列中所有重复元素。
排序与合并
list 容器有一个 sort() 函数专门用于排序，其可选择传入一个参数（lambda 函数或者函数对象）表示排序比较方法，与前面算法中的 sort() 并无本质区别。
除此之外，还可以使用 merge() 方法合并两个升序 list 容器为新的升序容器，比如：
std::list<int> my_values {2, 4, 6, 14};
std::list<int> your_values { -2, 1, 7, 10};
my_values.merge(your_values); // my_values contains: -2 1 2 4 6 7 10 14
your_values.empty(); // Returns true
注意执行完后，被合并的 list 容器会被清空。
当然，你也可以像 sort() 一样在后面主动提供排序比较方法。
还可以使用 splice() 方法将一个容器中的某个（或者一段，或者全部）元素移动到另一个容器的特定位置，几个例子看一下便知：
list<std::string> my_words {"three", "six", "eight"};
list<std::string> your_words {"seven", "four", "nine"};
my_words.splice(++std::begin(my_words), your_words, ++std::begin(your_words));
your_words.splice(++std::begin(your_words),my_words,++std::begin(my_words), std::end(my_words));
my_words.splice(std::begin(my_words), your_words);
可以自行模拟一下输出结果。
访问元素
同样有 front() 和 back() 返回头尾引用的方法。
访问其他元素，一般会使用相关迭代器（与前面相同）遍历的方法。
总结
到这里，STL 的基本介绍先告一段落。（考虑到后面的容器往往涉及到高级数据结构与算法）
这些容器、算法的最大特点便是，使用方法极其多样，提供函数方法也是纷繁复杂。
但大家千万不要被这些吓到，相反，这么多的方法只是为了满足更多人的需求而设计。
我们重点是理解并应用可能会用到的少数几种方法，即便还会使用别的，到时候再具体学习起来也必然简单许多。
总而言之，不要因为一点记不清楚，或者我少讲了一部分而焦急，记住 STL 到最后都是为你所用的工具而已。
关于 STL 的相关原理等学习，请前往 OOP 系列。
No Comments