标准模板库（STL）

标准模板库STLSTL 的四个组成与泛型编程标准模板库Standard Template LibrarySTL提供了一组表示容器container、迭代器iterator、函数对象function object和算法algorithm的模板。容器是与数组类似的单元可以存储若干个值STL 容器是同质的存储的值的类型相同算法是完成特定任务如排序、查找的处方迭代器是能够用来遍历容器的对象与能够遍历数组的指针类似是广义指针函数对象是类似于函数的对象可以是类对象或函数指针包括函数名因为函数名被用作指针。STL 不是面向对象编程而是一种不同的编程模式——泛型编程generic programming。泛型编程使 STL 能够构造各种容器数组、队列、链表并执行各种操作搜索、排序、随机排列且同一套算法可复用于任意满足接口要求的容器。#include vector // 容器模板vector #include algorithm // 算法模板sort、for_each、random_shuffle ​ std::vectorint v; // 容器存储同质int值 // 算法对区间 [v.begin(), v.end()) 排序 std::sort(v.begin(), v.end()); // 迭代器v.begin() 返回指向第一个元素的广义指针模板类 vector 与分配器vector 是定义在头文件 vector以前为 vector.h中的模板类计算中的矢量vector对应数组——存储一组可随机访问random access的值即可以用索引直接访问第 N 个元素而不必先访问前面的元素。要创建 vector 模板对象使用通常的 type 表示法指出要使用的类型vector 模板使用动态内存分配可以用初始化参数指出需要多少矢量。把类设计为模板使其成为通用的可存储任意指定类型动态内存分配使长度可随初始化参数与后续操作增长规则限制与 string 类相似各种 STL 容器模板都接受一个可选的模板参数指定使用哪个分配器allocator对象管理内存——templateclass T, class Allocator allocatorT class vector {...};若省略该参数容器默认使用 allocatorT 类它使用 new 和 delete。由于 operator[] 被重载创建对象后可用通常的数组表示法访问元素。迭代器与容器基本方法所有 STL 容器都提供一些基本方法size() 返回容器中元素数目、swap() 交换两个容器的内容、begin() 返回指向容器中第一个元素的迭代器、end() 返回一个表示超过结尾past-the-end的迭代器。迭代器是广义指针可以是指针也可以是可执行类似指针操作如解引用 operator*、递增 operator的对象。每个容器类都定义了一个合适的迭代器其类型是一个名为 iterator 的 typedef作用域为整个类。规则限制超过结尾是一种迭代器指向容器最后一个元素后面的那个元素与 C 风格字符串最后一个字符后面的空字符类似——但空字符是一个值而“超过结尾”是一个指向元素迭代器end() 成员标识超过结尾的位置。C11 的 auto 可省略显式写出迭代器类型。std::vectordouble scores; // vectordouble 对象 std::vectordouble::iterator pd; // 声明迭代器typedef作用域为整个类 pd scores.begin(); // 令 pd 指向第一个元素 *pd 10.5; // 解除引用给第一个元素赋值 pd; // 递增令 pd 指向下一个元素 // C11 自动类型推断 auto pa scores.begin(); // 编译器推断 pa 为迭代器类型push_back、erase 与 insertvector 模板类包含一些只有某些 STL 容器才有的方法。push_back() 将元素添加到矢量末尾它负责内存管理、增加矢量长度以容纳新成员erase() 删除矢量中给定区间的元素接受两个定义区间的迭代器参数insert() 的功能与 erase() 相反接受 3 个迭代器参数——第一个指定新元素的插入位置第二、三个定义被插入区间通常是另一个容器对象的一部分。erase() 与 insert() 的区间都用半开区间 [p1, p2) 指定。vector 提供随机访问功能因此其迭代器定义了诸如 begin() 2 的算术操作。向 old.end() 前插入即在矢量最后一个元素后面追加。std::vectorint old_v; // 目标矢量 std::vectorint new_v; // 源矢量 old_v.push_back(5); // 在末尾添加元素自动增长 // 删除前两个元素begin 与 begin1 指向的元素 old_v.erase(old_v.begin(), old_v.begin() 2); // 把 new_v 除第一个元素外的其余元素插入到 old_v 开头 old_v.insert(old_v.begin(), new_v.begin() 1, new_v.end()); // 在末尾追加 new_v 的全部元素插入到 end() 前 old_v.insert(old_v.end(), new_v.begin(), new_v.end());非成员算法与成员方法的取舍STL 从更广泛的角度定义了非成员non-member函数来执行常见操作——不是为每个容器类定义 find() 成员函数而是定义一个适用于所有容器类的非成员函数 find()。例如 for_each()、random_shuffle() 和 sort() 都是代表性的非成员 STL 函数。这种设计理念省去了大量重复工作——假设有 8 个容器类、需要支持 10 种操作若每个类都有自己的成员函数需定义 80 个函数而采用 STL 方式只需定义 10 个非成员函数定义新容器类时只要遵循正确的指导思想也能使用已有的 10 个非成员函数。即使有执行相同任务的非成员函数STL 有时仍会定义成员函数因为对有些操作而言类特定算法的效率比通用算法高——如 vector 的成员 swap() 效率比非成员 swap() 高但非成员函数能交换两个不同类型容器的内容。规则限制for_each() 接受 3 个参数前两个是定义区间的迭代器最后是指向函数的指针或函数对象把函数应用于区间中的各个元素被指向的函数不能修改容器元素的值random_shuffle() 接受两个指定区间的迭代器参数并随机排列元素要求容器类允许随机访问sort() 也要求容器支持随机访问。#include algorithm // for_each、random_shuffle、sort ​ // for_each把 ShowReview 应用于区间内每个元素不修改元素值 // for_each(books.begin(), books.end(), ShowReview); // random_shuffle随机排列区间元素要求随机访问容器 // random_shuffle(books.begin(), books.end()); // sort按类型定义的 运算符排序要求随机访问容器 // sort(coolstuff.begin(), coolstuff.end());sort 的两个版本与排序概念sort() 有两个版本。第一个版本接受两个定义区间的迭代器参数使用为存储在容器中的类型元素定义的 运算符对区间元素进行排序若容器元素是用户定义的对象则必须定义能处理该类型对象的 operator() 函数。第二个版本接受 3 个参数前两个也是指定区间的迭代器最后一个是函数指针或函数对象返回值可转换为 boolfalse 表示两个参数的顺序不正确。默认按 排序不够灵活——需要按降序、或按其他成员而非 operator 依据的成员排序时用自定义比较函数替代默认比较。两种排序对应两种排序概念按 operator 的全排序total ordering中若 ab 和 ba 都不成立则 a 和 b 必定相同而自定义比较函数的完整弱排序strict weak ordering中并非如此——它们可能相同也可能只是在某方面相同如仅 rating 成员相同此时只能说它们等价equivalent而不是相同。struct Review { // 用户定义类型 std::string title; // 标题成员 int rating; // 评分成员 }; ​ bool operator(const Review r1, const Review r2) { // 全排序按 title if (r1.title r2.title) // 先按标题比较 return true; if (r1.title r2.title) // 标题相同时按评分比较 return r1.rating r2.rating; return false; } ​ bool WorseThan(const Review r1, const Review r2) { // 完整弱排序按 rating return r1.rating r2.rating; // 仅评分相同时视为等价 } ​ // sort(books.begin(), books.end()); // 用 operator 排序 // sort(books.begin(), books.end(), WorseThan); // 用自定义比较函数排序基于范围的 for 循环C11基于范围的 for 循环range-based for loop是为用于 STL 而设计的。括号内的代码声明一个类型与容器存储内容相同的变量然后指出容器的名称循环体使用指定的变量依次访问容器的每个元素。// 基于范围的 for依次访问每个元素 // for (auto x : books) ShowReview(x); // x 推断为 Review按值传递 // 若要修改元素使用引用变量 void InflateReview(Review r) { // 接收引用的函数 r.rating; // 修改元素内容 } // for (auto x : books) InflateReview(x); // 引用方式可修改容器内容泛型编程