C++ - Standard Template Library (STL)

Table of Contents

标准模板库(standard template library, STL)是C++标准库的子集, 其大量使用了模板.

容器

  • STL中的所有容器都是模板, 是泛型结构, 因此可以通过这些容器保存任意类型的数据. 除 array 和 bitset 外, 大部分STL容器的大小灵活多变, 都能自动增长或收缩, 以容纳更多或者更少的元素.
  • STL容器是同构的, 每个容器实例只允许一种类型的元素.
  • STL容器对元素使用值语义(value semantic)。因此，编写要用于STL的类时，一定要保证它们是可复制的。如果需要引用语义，必须自己实现。实现方法是保存元素指针，而不是保存元素本身。可以使用 unique_ptr, 使容器成为该指针所指对象的拥有者；或者使用 shared_ptr, 使容器与其他拥有者共享拥有权。
  • STL容器的一个模板类型参数是分配器(allocator)。该容器可以使用该分配器来为元素分配内存或释放内存。有些容器(例如 map)也接受将一个比较器(comparator)作为一个模板类型参数。比较器用作顺序元素。
  • 所有的STL容器都包含了移动构造函数和移动赋值运算符, 从而实现了移动语义.
  • 移动语义要正确地用于STL容器，必须把移动构造函数和移动复制运算符标记为 noexcept.
  • C++11在大部分STL容器中添加了对 emplace 操作的支持. emplace 的意思是放置到位, 就地构件对象.

顺序容器(sequential container)

顺序容器是元素的序列。

vector

  • 定义在头文件 <vector> 中.
  • 提供对元素的随机访问.
  • 元素保存在连续的内存中.
  • 能够在尾部快速插入和删除元素, 在其他部位插入和删除操作比较慢.
  • 可以在本来需要使用数组的地方使用 vector.
  • 在任何可能的情况下使用 vector 而不是C风格的数组.
  • vector 的默认构造函数会创建一个带有0个元素的 vector. 此外, 还提供了一个可以指定元素数量的构造函数, 和同时指定元素数目和元素值的构造函数. 如果没有提供默认值, 那么新对象通过0初始化——将原始的整型类型初始化为0, 将原始浮点类型初始化为0.0, 将指针类型初始化为 nullptr.
  • vector 存储对象的副本, 其析构函数调用每个对象的析构函数. vector 类的复制构造函数和赋值运算符对 vector 中的所有元素执行深度复制.
  • assign() 方法删除所有现有的元素, 并添加任意数目的新元素.
  • swap() 方法可以交换两个 vector 的内容.
  • vector 的 operator[] 没有提供边界检查功能. C++标准指出通过 operator[] 访问边界外元素得到的结果是未定义的. 不同的是, at() 方法会执行边界检查, 越界会抛出异常(out_of_range).
  • front() 和 back() 分别返回 vector 的第一个元素和最后一个元素的引用.
  • size() 返回 vector 中元素的数目.
  • capacity() 返回 vector 在重分配之前可以保存的元素个数. 因此, 在重分配之前还能插入的元素个数为 capacity() - size().
  • resize() 可以指定 vector 要保存的元素数目.
  • reserve() 可以预分配空间.
  • push_back() 可以向 vector 追加元素.
  • pop_back() 可以删除 vector 最后一个元素. 注意, 该方法不会返回已删除的元素. 如果要访问这个元素, 必须首先通过 back() 获得这个元素.
  • insert() 方法可以在 vector 中任意位置插入元素.
  • erase() 方法可以在 vector 中任意位置删除元素.
  • clear() 方法可以删除所有元素.

list (双向链表)

  • 定义在头文件 <list> 中.
  • 元素查找和访问很慢.
  • 元素不一定保存在连续的内存中.
  • 插入和删除很快.
  • 不支持元素的随机访问, 访问元素的方法只有 front() 和 back(), 分别返回第一个元素和最后一个元素的引用. 访问其他的元素必须通过迭代器.
  • 应该尽量使用 list 方法而不是泛型STL算法, 因为前者更高效.

forward_list (单向链表)

  • 只支持前向迭代.
  • 没有提供快速的随机访问.
  • 内存需求比 list 小.

deque (双头队列)

  • 定义在头文件 <deque> 中.
  • 不要求元素保存在连续内存中.
  • 提供了快速的元素访问.
  • 在序列两端提供了快速的插入和删除(常量时间).
  • 在序列中间插入和删除的速度较慢.
  • 提供了 push_front(), pop_front() 和 emplace_front().

array

  • 定义在头文件 <array> 中.
  • 标准C风格数组的替代品, 实际上是对C风格数组的简单包装.
  • 适合大小固定的集合. 不能增加或收缩.
  • 没有提供插入和删除操作.
  • 元素的访问速度极快.
  • 要求两个模板参数: 第一个参数指定了元素类型; 第二个参数指定了元素的固定数量.

容器适配器(adaptor)

容器适配器只是构建在某种标准顺序容器上的简单接口。

queue

  • 定义在头文件 <queue> 中.
  • 提供了标准的先入先出(FIFO)语义.
  • 从一端插入元素, 从另一端取出元素.
  • 插入元素和删除元素都很快.
  • push() 和 emplace() 方法在 queue 尾部添加一个新元素
  • pop() 移除头部元素.
  • front() 和 back() 分别返回第一个元素和最后一个元素的引用, 而不会删除元素.

priority_queue

  • 定义在头文件 <queue> 中.
  • 插入删除比 queue 要慢.
  • 其头元素的优先级最高。
  • push() 和 emplace() 方法可以插入元素。
  • pop() 可以删除元素。
  • top() 可以返回头元素的const引用。
  • 支持 size(), empty 和 swap() 方法。

stack

  • 定义在头文件 <stack> 中.
  • 提供了标准的先入后出(FILO)语义，也称为后入先出语义.
  • push() 在stack顶部添加一个新元素。
  • pop() 从stack顶部删除一个元素。
  • top() 返回顶部元素的引用。
  • 最新插入的元素第一个被删除.
  • 提供了快速的元素插入和删除.
  • 支持 size(), empty 和 swap() 方法和标准的比较运算符。

关联容器

关联容器是关联了键和值的容器。

pair 工具类

  • pair 是一个类模板， 将两个可能属于不同类型的值组合起来。
  • 通过 first 和 second 公共数据成员访问这两个值。
  • 定义了 operator== 和 operator< ， 用于比较 first 和 second 元素。
  • 工具函数模板 make_pair() 用于从两个值构造一个 pair 。
  • 在 pair 中使用一般指针是危险的，因为 pair 复制构造函数和赋值运算符只对指针类型进行浅复制和赋值。然而，在 pair 中保存 shared_ptr 这样的智能指针则是很安全的。

排序关联容器或有序关联容器

map 和 multimap
  • 定义在头文件 <map> 中，保存的是键/值对。
  • map
    • 向 map 添加元素的方法是 insert() ，其允许判断键是否已经存在。该方法必须将键/值指定为 pair 对象或 initializer_list ，返回值为迭代器和布尔值组成的 pair() 。布尔值指示是否真的插入了新的键/值对，迭代器引用的是 map 中带有指定键的元素。如果指定的键已经存在，那么 insert() 不会改写元素值。
    • operator[] 也可以插入元素。但是 operator[] 总是成功。如果给定键没有对应的元素值，就会创建带有对应键值的新元素。如果具有给定键的元素已经存在，那么 operator[] 会将元素值替换为新指定的值。
    • find() 方法可以查找给定键值的元素。如果元素存在，这个方法返回指向具有指定键值的元素的迭代器；如果元素不存在，则返回 end() 迭代器。此外， operator[] 可以查找给定键值的元素，但是如果不知道元素是否存在，就不能使用 operator[] 。因为如果元素不存在， operator[] 就会插入一个包含相应键值的新元素。
  • multimap
    • multimap 是一个允许多个元素使用同一个键值的 map 。
    • multimap 不提供 operator[]. 其将所有带有同一个键值的元素保存在一起, 并提供了方法获得这个子范围的迭代器: lower_bound() 和 upper_bound() 方法分别返回满足给定键值的第一个元素和最后一个元素之后一个元素的迭代器. 如果没有元素匹配这个键值, 那么 lower_bound() 和 upper_bound() 相等. 此外, equal_range() 方法返回两个迭代器的 pair, 分别是 lower_bound() 和 upper_bound() 返回的迭代器.
set 和 multiset
  • 定义在头文件 <set> 中。
  • multiset 和 set 的关系等同于 multimap 和 map 的关系. multiset 支持 set 的所有操作, 但允许容器中同时保存多个相等的元素.

无序关联容器或哈希表(hash table)

  • unordered_map 和 unordered_multimap 定义在头文件 <unordered_map> 中, 都是类模板. unordered_multimap 是允许多个元素带有同一个键值的 unordered_map.
  • unordered_set 和 unordered_multiset 定义在头文件 <unordered_set> 中. 二者分别类似于 set 和 multiset.
  • 无序关联容器使用了哈希函数(hash function), 所以也称为哈希表.
  • 哈希表的实现通常会使用某种形式的数组, 数组中的每个元素都称为桶(bucket).
  • 哈希函数的结果未必是唯一的. 两个或多个键哈希到同一个桶索引, 称为冲突(collision).
  • C++标准为指针和所有基本数据类型(例如 bool, char, int, float, double 等)提供了哈希函数, 也为 error_code, bitset, unique_ptr, shared_ptr, type_index, string, vector<bool> 和 thread 提供了哈希函数.

其他容器

  • 定义在头文件 <bitset> 中的 bitset 并不是一个真正的STL容器: 固定大小(声明时指定大小), 不支持迭代器.
  • string 也可看做字符的顺序容器.
  • STL提供了名为 istream_iterator 和 ostream_iterator 的特殊迭代器, 用于"遍历"输入和输出流.

算法

算法之美在于算法不仅独立于底层元素的类型, 而且还独立于操作的容器的类型. 算法仅使用迭代器作为接口来操作容器, 而不是直接操作容器本身. 而对大部分容器来说, 迭代器范围都是半开半闭区间(包含第一个元素却不包含最后一个元素), 尾迭代器实际上是跨越最后一个元素(past-the-end)的标记. 大部分算法都接受回调(callback), 回调可以是一个函数指针, 也可以是行为上类似于函数指针的对象(例如重载了运算符 operator() 的对象, 或者内嵌lambda表达式). 为了方便起见, STL还提供了一组类, 用于创建算法使用的回调对象. 这些回调对象称为函数对象, 或仿函数(functor).

  • 大部分算法定义在头文件 <algorithm> 中, 一些数值算法定义在头文件 <numeric> 中. 它们都在名称空间std中.
  • 算法一般不属于容器的一部分. STL采取了一种分离数据(容器)和功能(算法)的方式. 正交性的指导原则使算法和容器分离开, (几乎)所有算法都可以用于(几乎)所有容器.
  • 泛型算法并不是直接对容器操作, 而是使用迭代器(iterator). 迭代器是算法和容器之间的中介, 提供了顺序遍历容器中的元素的标准接口, 因此任何算法都可以操作任何容器.

函数适配器(function adaptor)对函数组合(function composition)提供了支持, 能够将函数组合在一起, 以精确提供所需的行为.

绑定器(binder)

绑定器可用于将函数的参数绑定至特定的值. 为此要使用头文件 <functional> 中定义的 std::bind(). 它允许采用灵活的方式绑定函数的参数. 既可以将函数的参数绑定至固定值, 甚至还能够重新安排函数参数的顺序. bind() 函数的返回类型比较复杂, 但是可以使用 auto 关键字, 无须指定准确的返回类型. 没有绑定至指定值的参数应该标记为 _1, _2, 和 _3 等. 这些都定义在 std::placeholders 名称空间中.

头文件 <functional> 定义了辅助函数 std::ref() 和 std::cref(), 它们分别用于绑定引用和const引用.

取反器(negator)

取反器是类似于绑定器的函数, 但是取反器计算谓词结果的反结果. 如果操作函数是一元函数, 需要使用 not1(); 如果操作函数是二元函数, 那么必须改用 not2().

调用成员函数

对于一个对象容器, 有时需要传递一个指向类方法的指针作为算法的回调. 但是算法无法知道接受的是指向方法的指针, 而不是普通函数指针或仿函数. 调用方法指针的代码和调用普通函数指针的代码是不一样的, 因为前者必须在对象的上下文内调用. C++提供了 mem_fn() 转换函数, 在传递给算法之前可以对函数指针调用这个函数.

如果容器内保存的不是对象本身, 而是对象指针, mem_fn() 的使用方法也完全一样.

非修改序列算法

搜索算法

find 和 find_if
  • find 在一个迭代器范围内查找特定元素. 可将其用于任意容器类型的元素. 这个算法返回所找到元素的迭代器引用. 如果没有找到元素, 则返回迭代器范围的尾迭代器.
  • 如果容器提供的方法具有与泛型算法同样的功能, 那么应该使用相应的方法, 那样速度更快.
  • find_if 和 find 类似, 区别在于 find_if 接受谓词函数回调作为参数, 而不是简单地匹配元素. 谓词返回 true 或 false. find_if 算法对范围内的每个元素调用谓词, 直到谓词返回 true. 如果返回了 true, find_if 返回引用这个元素的迭代器引用.

比较算法

下列算法主要用于比较不同容器内的范围1.

  • equal()
  • mismatch()
  • lexicographical_compare()

工具算法

  • all_of()
  • any_of()
  • none_of()
  • count()
  • count_if()

修改序列算法

修改算法通常返回一个引用目标范围最后一个值后一个位置(past-the-end)的迭代器.

转换

  • transform() 算法对一个范围内的每个元素应用回调, 期望回调生成一个新元素, 并保存在指定的目标范围内. 如果希望 transform() 将范围内的每个元素替换为调用回调产生的结果, 那么源范围和目标范围可以是同一范围. 其参数是源序列的首尾迭代器, 目标序列的首迭代器和回调.
  • transform() 的另一种形式对范围内的元素对调用二元回调, 它需要第一个范围内的首尾迭代器, 第二个范围的首迭代器和模板范围的首迭代器作为参数.

复制

  • copy() 算法可将一个范围内的元素复制到另一个范围中, 从范围中的第一个元素开始一直到最后一个元素. 源范围和目标范围必须不同, 但可以重叠.
  • copy() 不会向目标范围插入元素, 只是改写已有的元素. 因此, 不能通过 copy() 直接向容器插入元素, 只能改写容器中已有的元素.
  • copy_backward() 将源范围内的元素反向复制到目标范围内. 换句话说, 这个算法从源范围的最后一个元素开始, 将这个元素放在目标范围的最后一个位置, 然后在每一次复制之后反向移动.
  • copy_if() 需要一个由两个迭代器指定的的输入范围, 由一个迭代器指定的输出目标, 以及一个谓词(函数或lambda表达式). 对每个准备复制的元素执行这个函数或lambda表达式. 如果返回值为true, 那么复制这个元素, 并且递增目标迭代器; 如果返回值为false, 那么不复制这个元素, 也不递增目标迭代器. 因此, 目标中包含的元素可能少于源范围. 对于一些容器来说, 由于肯定已经创建了足够的空间来保存最大可能数目的元素(要记住, 复制不会创建或扩大容器, 只是替换现有元素), 因此, 可能需要删除超出最后一个元素复制位置的空间. 为便于达到这个目的, copy_if() 返回了目标范围中最后一个复制的元素后一个位置(one-past-the-last-copied element)的迭代器, 以便确定需要从目标容器中删除的元素个数.
  • copy_n() 从源范围复制n个元素到目标范围. 其第一个参数是起始迭代器, 第二个参数是一个指定要复制的元素个数的整数, 第三个参数为目标迭代器. 该算法不执行任何边界检查, 因此一定要确保起始迭代器递增了n个要复制的元素后, 不会超过集合的end(), 否则程序会产生未定义的行为.

移动

  • 有两个和移动相关的算法: move() 和 move_backward(). 它们都使用了移动语义. 如果要在自定义类型元素的容器中使用这些算法, 那么需要在元素类中提供移动赋值运算符.
  • move_backward() 使用了和 move() 同样的移动机制, 但是按照从最后一个元素向第一个元素的顺序移动.

替换

  • replace() 和 replace_if() 将一个范围中匹配某个值或满足某个谓词的元素替换为新的值. 比如 replace_if() 算法的前两个参数指定了容器中元素的范围. 第三个参数是一个返回true或false的函数或lambda表达式. 如果这个函数返回true, 那么容器中的对应值被替换为第四个参数指定的值; 如果返回false, 则保留原始值.
  • replace() 也有称为 replace_copy() 和 replace_copy_if() 的变体, 这些变体将结果复制到不同的目标范围中. 它们类似于 copy(), 要求目标范围必须足够大, 以容纳新元素.

删除

  • 算法只能访问迭代器抽象, 不能访问容器. 因此删除算法不能真正地从底层容器中删除元素, 而是把匹配给定值或谓词的元素替换为下一个不匹配给定值或谓词的元素. 结果是将集合分为两个集合: 一个用于保存要保留的元素, 另一个保存要删除的元素.
  • 如果真的需要从容器中删除这些元素, 正确的解决方案为: 先使用 remove() 算法, 然后调用容器的 erase() 方法, 将从返回的迭代器到范围尾部的所有元素删除. 这就是 删除-擦除法 (remove-erase-idiom).
  • remove() 的 remove_copy() 和 remove_copy_if() 变体不会改变源范围, 而是将所有未删除的元素复制到另一个目标范围中. 这些算法和 copy() 类似, 要求目标范围必须足够大, 以便保存新元素.

唯一化

  • unique() 算法是特殊的 remove(), 将所有重复的连续元素删除. list容器提供了自己的具有同样语义的 unique() 方法.
  • 通常情况下, 应该对有序序列使用 unique(), 但是 unique() 也能用于无序序列.
  • unique() 的基本形式就地操作数据, 还有一个名为 unique_copy() 的版本, 其将结果复制到一个新的目标范围.

反转

  • reverse() 算法反转一个范围内元素的顺序. 范围内的第一个元素和最后一个元素交换, 第二个和倒数第二个交换, 依次类推.
  • reverse() 最基本的形式就地运行, 要求两个参数: 范围的起始迭代器和终止迭代器.
  • reverse_copy() 将结果复制到新的目标范围, 它需要三个参数: 源范围的首尾迭代器, 以及目标范围的起始迭代器. 目标范围必须足够大, 以便保存新元素.

乱序

  • shuffle() 以随机顺序重新安排范围内的元素, 其复杂度为线性时间. 它可以用于实现洗牌等任务.
  • shuffle() 的参数为要乱序的范围的首尾迭代器, 和一个统一的随机数生成器对象, 它指定如何生成随机数.

分区算法

  • partition() 算法给序列排序, 使谓词返回true的所有元素放在前面, 谓词返回false的所有元素放在后面, 在每个分区中不保留元素最初的顺序.
  • partition_copy() 算法将一个来源的元素复制到两个不同的目标. 选择每个元素特定目标的依据是谓词的结果: true或false. 其返回值是一对迭代器: 一个迭代器引用第一个目标范围最后一个复制的元素的后一个位置(one-past-the-last-copied element), 另一个迭代器引用第二个目标范围最后一个复制的元素的后一个位置. 将这些返回的迭代器与 erase() 结合使用, 可以删除两个目标范围中多余的元素(与 copy_if() 类似).

排序算法

  • 排序算法只能应用于顺序容器. 排序和关联容器无关, 因为关联容器已经维护了元素的顺序.
  • 在一般情况下, 函数 sort() 在 $O(N\logN)$时间内将一个范围内的元素排序. 根据运算符 operator<, 这个范围内的元素以非递减顺序排列(最小到最大). 如果不需要使用这个顺序, 可以指定一个不同的比较回调.
  • stable_sort() 能够保持范围内相等元素的相对顺序, 所以效率比 sort() 低.

集合算法

  • 集合算法可以用于任意有序的迭代器范围.
  • include() 函数实现了标准的子集判断功能, 检查一个有序范围的所有元素是否包含在另一个有序范围中, 顺序任意.
  • 下列算法实现了这些操作的标准语义
    • set_union()
    • set_intersection
    • set_difference
    • set_symmetric_difference
  • merge() 函数可将两个排好序的范围归并在一起, 并保持排序的顺序. 结果是一个包含两个源范围中所有元素的有序范围. 其复杂度为线性时间. 该算法需要以下参数
    • 第一个源范围的起止迭代器.
    • 第二个源范围的起止迭代器.
    • 目标范围的起始迭代器.
    • 比较回调(可选)

最大/最小算法

  • min() 和 max() 算法通过运算符 operator< 或用户提供的二元谓词比较两个任意类型的元素, 分别返回一个引用较小或较大元素的const引用.
  • minmax() 算法返回一个包含两个或更多元素中最小值和最大值的pair.

数值处理算法

  • 头文件 <numeric> 中定义的 inner_product() 计算两个序列的内积.
  • 头文件 <numeric> 中定义的 iota() 生成一个指定范围内的序列值, 从给定的值开始, 并应用 operator++ 生成每个后续值.
...
vector<int> v(3);
iota(begin(v), end(v), 7); // v中元素的值依次为7, 8, 9.
...

accumulate

  • 定义在头文件 <numeric> 中.
  • 最基本形式是计算指定范围中元素的总和.
  • 第二种形式允许指定要执行的操作, 而不是默认的加法操作. 这个操作的形式是二元回调.
  • 最多有4个参数
    1. 开始迭代器
    2. 终止迭代器
    3. 初始值
    4. 函数回调或lambda表达式

std::function

  • 定义在头文件 <functional> 中. 可以用来创建指向函数, 函数对象或lambda表达式的类型.
  • 语法为 std::function<R(ArgTypes...)>, 其中 R 是函数返回值的类型, ArgTypes 是一个逗号分隔的函数参数类型的列表.
  • 从根本上来讲, std::function 是一个多态的函数对象包装(多态函数包装器), 类似于函数指针, 既可以当成函数指针来使用, 又可以用作实现回调的函数参数. 他可以绑定至任何能调用的对象(仿函数, 成员函数指针, 函数指针和lambda表达式), 只要参数和返回类型符合包装的类型即可.
  • 由于 std::function 类型的行为和函数指针一致, 因此可以传递给STL算法.

generate

该算法需要一个迭代器范围, 它把该范围的值替换为从函数(第三个参数)返回的值.

迭代器

  • STL通过迭代器模式提供了访问容器元素的泛型抽象. 每个容器都提供了容器特定的迭代器, 迭代器实际上是增强版的智能指针, 这种指针知道如何遍历特定容器的元素, 所有不同容器的迭代器都遵循C++标准中定义的特定接口.
  • 迭代器的实现类似于智能指针类，因为它们都重载了特定的运算符。基本的迭代器操作类似于普通指针(dumb pointer)支持的操作, 因此普通指针可以合法用作特定容器的迭代器. 可以将迭代器想象为指向容器中某个元素的指针. 与指向数组元素的指针一样, 迭代器可以通过 operator++ 移动到下一个元素. 还可以在迭代器上使用 operator* 和 operator-> 来访问实际元素或元素中的字段. 有些迭代器支持通过 operator== 和 operator!= 进行比较, 还支持通过 operator-- 转移到前一个元素.
  • 所有迭代器都必须可以通过复制来构建，赋值，且可以析构。
  • 可以使用 std::distance() 计算容器的两个迭代器之差。
  • 只有顺序容器，关联容器和无序关联容器提供了迭代器，容器适配器和 bitset 类都不支持迭代元素。
  • STL中每个支持迭代器的容器类都为其迭代器类型提供了名为 iterator 和 const_iterator 的公共 typedef 。允许反向迭代元素的容器还提供了名为 reverse_iterator 和 const_reverse_iterator 的公共 typedef 。其中， const_iterator 和 const_reverse_iterator 提供了容器元素的只读访问。普通的 iterator 支持读和写, 可以转换为 const_iterator, 然而 const_iterator 不能转换为 iterator. 如果不需要修改容器中的元素, 那么应该使用 const_iterator.
  • 容器的 begin() 方法返回容器中第一个元素的迭代器, end() 方法返回的迭代器是在容器中最后一个元素的迭代器上执行 operator++ 后的结果. begin() 和 end() 在一起提供了一个左开右闭区间——包含第一个元素却不包含最后一个元素. 采用这种方式的原因是为了支持空容器——不包含任何元素的容器, 此时 begin() 等于 end(). 类似的还有返回 const 迭代器的 cbegin() 和 cend() 方法, 返回反向迭代器的 rbegin() 和 rend() 方法, 以及返回 const 反向迭代器的 crbegin() 和 crend() 方法. 标准库还支持全局非成员函数 std::begin() 和 std::end(), C++14又添加了 std::cbegin(), std::cend, std::rbegin(), std::rend(), std::crbegin(), std::crend(). 建议使用这些非成员函数, 而不是其成员函数.
  • 只要可能, 尽量使用前递增而不要使用后递增, 因为前递增至少效率不会差, 一般更为高效. iter++ 必须返回一个新的迭代器对象, 而 ++iter 只是返回对 iter 的引用.

不足

  • 在通过多线程同时访问容器时, STL不能保证任何线程安全.
  • STL没有提供任何泛型的树结构或图结构.

Footnotes:

1

如果要比较两个同类型容器的元素, 可以使用运算符 operator== 和运算符 operator<, 而不是 equal() 和 lexicographical_compare().