Effective STL

• 根据使用场景、操作特点，采用不同的容器。

• 不要试图编写独立于容器类型的代码，另外最好将业务已与数据结构区分开来，使用 using 将数据类型赋予业务意义。

• 保证容器中数据拷贝意义的正确性，比如不能用基类容器存储子类，这样会发生对象切割。

• 使用 empty 检查容器为空，而不是判断容器长度为 0。因为在某些情况下，容器长度需要遍历容器。（链表的 splice 操作与 size 的矛盾）

• 区间成员函数优先于单元素的成员函数。区间成员函数可以避免无意义的拷贝和内存分配。

• 小心编译器将初始化识别为函数声明。参数的括号会被忽略。

int intv(double(v));

上面这个一句会被识别为函数声明。忽略掉 v 两边的括号。而实际上我的本意是将微转为 double，然后用来初始化 int 类型的变量 intv。

int intv(my_type());

上面这个语句呢，本意是使用 my_type 的默认值初始化一个 int，但是他却会将 my_type()识别为一个函数类型声明。所以整个就变成了一个函数声明。

有几种方式可以避免这个问题:1. 不使用匿名的对象初始化。2. 在初始化类型两侧加上括号。3. 使用花括号而不是圆括号

• 这容器中使用 new 关键字分配的对象，一定要手动使用 delete 销毁掉（可以使用智能指针，但是要注意不能使用 unique_ptr）

• 删除容器元素时，一定要注意容器迭代器失效的问题。（可以在删除的时候使用后置递增）■ 要删除容器中有特定值的所有对象：如果容器是 vector、string 或 deque，则使用 erase-remove 习惯用法。如果容器是 list，则使用 list::remove。如果容器是一个标准关联容器，则使用它的 erase 成员函数。■ 要删除容器中满足特定判别式（条件）的所有对象：如果容器是 vector、string 或 deque，则使用 erase-remove_if 的习惯用法。如果容器是 list，则使用 list::remove_if。如果容器是一个标准关联容器，则使用 remove_copy_if 和 swap，或者写一个循环来遍历容器中的元素，记住当把迭代器传给 erase 时，要对它进行后缀递增。■ 要在循环内部做某些（除了删除对象之外的）操作：如果容器是一个标准序列容器，则写一个循环来遍历容器中的元素，记住每次调用 erase 时，要用它的返回值更新迭代器。如果容器是一个标准关联容器，则写一个循环来遍历容器中的元素，记住当把迭代器传给 erase 时，要对迭代器做后缀递增。

• 分配子使的注意事项

1. 容器可能不会使用分配子来分配内存，比如 list，因为他还需要分配的不是对象的内存，而是包含对象的节点

2. 分配子不能有状态，因为对于同一个类型来说，分配的内存可能要在不同的对象之间迁移。在 A 分配子中分配，在 B 分配子中释放。

3. 要提供 rebind 模板，因为标准容器依赖该模板。

4. 不要从头开始，参考现有的代码。

• 如果想要控制对象被创建在指定的内存区域（比如共享内存），分配子是很有用的，但是时刻要注意，统一类型的分配子是等价的（分配子不能有状态）。

• STL 容器多线程读是安全的，多线程对不同的容器写是安全的。所以在多线程操作一个容器的时候，需要加锁（建议使用 RAII）。

• 用 vector 代替数组，用 string 代替 char*，可以避免一系列内存管理问题，同时还可以调用丰富的 STL 函数处理对象。（除非在某些性能要求极高的场景，string 的引用计数机制可能会对性能造成一些影响）

• 使用 reverse 还避免不必要的内存分配与移动（reverse 只会分配内存，不会调用构造函数）。

• 如果要将 vector 和 string 传递给旧的 C API 接口，可以调用 vector 的 data()或者 &v[0]（注意为空的情况），调用 string 的 c_str()函数。

• 使用 swap 可以实现一个容器容量的缩小。

• 避免使用 vector<bool>，因为他不是一个真正的 vector，可以使用 bitset（不能在运行时改变大小）或者 deque<bool>。

• 对于关联容器，find“相同”的定义是相等（基于 operator==），而 insert“相同”的定义是等价（基于 operator<）。

• 使用关联容器存储一个指针的时候，不要期望会按照指针对应的值排序，除非自己定义比较函数。

• 总是让关联容器比较函数等值的情况下返回 false，这并不违反直觉，因为比较函数是<，等值时并不存在小于关系。如果不返回 false，会导致 a<b 和 b<a 同时成立。

• 切勿修改关联容器中的键。因为通过外部手段修改（比如指针）时，容器自身感知不到，会导致容器内部数据的不一致性。如果非要修改，可以通过 删除→插入的方式。

• 使用排序的 vector 往往可以获得比关联容器更好的查找性能（结合 binary_search），因为排序的 vector 具有更好的局部性。

• map 的 operator[]与 insert 具有不同的实现。operator[]会构造一个默认对象，因此对于性能至关重要的场景，使用 insert 而不是 operator[]

• 尽量使用 iterator 而不是 const_iterator 或者 reverse_iterator，因为大多数算法接受的都是 iterator。而且不要在一个表达式中混用这几种类型，因为有些操作符被实现为成员函数而不是全局函数。

• 当需要从 const_iterator 转换为 iterator 时，可以使用 distance 和 advance 来进行，具体如下：

  vector<int>::iterator iter(arr.begin()); // 这里假设arr是一个vector<int>类型的容器  addvance(iter, distance(iter, citer)); // citer 为 vector<int>::const_iterator类型的迭代器

`advance(i, n)`将`i`往后推移`n`个单位。这种方法需要付出时间成本，在使用的时候，先考虑下是否需要这样做。

• reverse_iterator 与其 base()返回的 iterator 之间相差一个元素：

• 这种差别对于 insert 来说，可以得到正确结果，但是对于 erase 来说，结果就不一样了，应该明确偏移 1 个元素再进行删除。

• 如果想把一个流的内容完全读入一个 string 中，可以使用 istreambuf_iterator，istream_iterator 会跳过空白字符。而且 istreambuf_iterator 的性能比 istream_iterator 要更高。

• 在使用 copy 或者这一类算法的时候，一定要保证目标容器有足够的空间。通常可以使用 inserter 来解决。

• 如果需要对 vector、string、deque 或者数组中的元素执行一次完全排序，那么可以使用 sort 或者 stable_sort。

• 如果有一个 vector、string、deque 或者数组，并且只需要对等价性最前面的 n 个元素进行排序，那么可以使用 partial_sort。

• 如果有一个 vector、string、deque 或者数组，并且需要找到第 n 个位置上的元素，或者，需要找到等价性最前面的 n 个元素但又不必对这 n 个元素进行排序，那么，nth_element 正是你所需要的函数。

• 如果需要将一个标准序列容器中的元素按照是否满足某个特定的条件区分开来，那么，partition 和 stable_partition 可能正是你所需要的。

• 如果你的数据在一个 list 中，那么你仍然可以直接调用 partition 和 stable_partition 算法；可以用 list::sort 来替代 sort 和 stable_sort 算法。

• 需要排序的区间作为参数的算法：

• mismatch 可以返回迭代器区间第一对不同的元素，lexicographical_compare 是 strcmp 的泛化版本，shuffle 可以打乱容器。

• 使用 accumulate 或者 for_each 进行区间统计。

• 函数对象应该以值传递或返回。

• 判别式应该是纯函数，不应该有副作用或者引用外部变量，也不应该有状态。

• 算法调用优先于手写循环

• 容器的成员函数优先于同名算法（如 list 的 remove 和 unique）