《Effective STL》读摘

Scott Meyers大神的Effective C++系列自然是让不少C++爱好者顶礼膜拜的经典之作，读完之后C++的使用技能瞬间飙升好几个档次，其实他还有一本《Effective STL》也是值得品读学习的，可能大家觉得熟悉一些常用的容器基本就足够使用了，所以对STL这个话题也关注的较少。

也的确，平时在面试别人的时候问熟不熟悉STL？各个容器的特点及查找、修改元素的复杂度是什么？容器的内部用什么数据结构实现的？再深一点的时候顺带问一下迭代器失效的问题。除此之外好像也没什么可以深度问下去的了，比如STL的算法函数基本都没有人说用过。不过STL中的容器和基本算法作为最基础的开发组件可以说是将效率优化到极致了的，而对用户而言不同的用法带来的效果可能会相差甚远，而且用STL常常可以用更简洁、更可维护的方式实现业务需求，所以只有彻底熟悉STL才能真正发挥它的强大优势，这就是我读完这本书的感受。

虽然这本书出版的较早，而且很久没有更新了，不过对比新标准的STL实现，对用户来说使用方式基本没有太大的差异，所以这里的知识基本不会太过时。

一、容器

通常STL容器可以分为 连续内存容器 和 基于节点的容器 。 连续内存容器 包括vector、string、deque， 节点类型容器 包括链表类的list、slist(forward_list)和关联类型的容器。这两种类型的容器除了涉及到在中间插入、删除元素的复杂性，元素的排列是否是有序等常见差异外，他们的差异性还表现在迭代器、引用的有效性问题：

序列容器 支持随机访问，只要没有删除操作发生而且插入操作只发生在容器的末尾，则指向数据的指针、引用就不会失效。任何的push操作都会导致deque的所有迭代器失效，不过指针和引用仍然会保持有效。对于vector如果插入节点导致容器重排，则所有的迭代器、指针、引用都会失效，末尾删除元素不会导致迭代器失效。

节点容器 是让迭代器、指针、引用失效次数最小的容器，这类容器的插入、删除操作从来不会使别的迭代器、指针、引用失效，除了直接操作的那个元素之节点。

1.1 使用区间成员函数

区间成员函数是指接收两个迭代器来确定成员操作执行的区间，使用区间成员函数代替手动写循环的理由是：区间函数写起来更容易，比起手写循环能更清楚地表达代码的目的意图，整体还表现出更高的操作效率。

(a). 区间创建

container::container( InputIt first, InputIt last);

(b). 区间插入

所有序列容器都提供了insert区间形式的插入操作。当你的代码中发现需要在循环中调用push_front、push_back的时候，就应该考虑使用区间形式的insert了。

void container::insert( iterator pos, InputIt first, InputIt last);
iterator container::insert( const_iterator pos, InputIt first, InputIt last );

(c). 区间删除

所有容器都提供了区间形式的删除操作，但是对于序列容器和关联容器，他们的返回类型是不一样的：序列容器返回的是指向被删除元素之后的元素，关联容器为了效率考虑不返回任何内容。

iterator container::erase( iterator first, iterator last );  //序列
void container::erase( iterator first, iterator last );      //关联

(d). 区间赋值

void container::assign( InputIt first, InputIt last );

1.2 删除元素的方法

删除元素算是对容器最常用的操作了，删除操作总共可分为三类情况：删除容器中所有具有特定值的对象、提供一个条件谓词删除指定元素、需要在循环中做特定的操作。

(a). 删除所有特定值的对象

对于内存连续容器(vector、deque、string)，最好的删除方式是使用erase-remove习惯用法：

c.erase(remove(c.begin(), c.end(), 2018), c.end());

对于list类型，可以直接调用成员函数list::remove。

标准关联容器都没有remove成员函数，而且使用std::remove可能会覆盖容器的值甚至是破坏容器，所以关联类容器删除元素的方法只能使用容器自己的erase成员函数，而且其基于 等价 的语义也保证删除操作的正确性。

(b). 删除满足判别式谓词的元素

针对内存连续容器以及list类型，上面的remove还有remove_if的版本可以提供一个条件判断谓词predicate，使用方式没什么差别这里就不做演示了。

针对关联容器，使用erase删除元素的时候指向该元素的迭代器就会失效，所以只能用遍历的方式来删除元素。

(c). 使用遍历的方式删除元素

针对不仅仅简单地删除元素，还需要做一些额外的操作的情况下，就只能使用循环体的方式边遍历边操作了。如果是内存连续的容器，我们需要使用erase的返回值，其内容为紧接着删除元素下一个元素的有效迭代器：

for(auto iter=c.begin(); iter!=c.end(); /**/) {
    if(badValue(*iter)) iter = c.erase(iter);
    else ++iter;
}

针对关联容器，erase成员函数返回的是void，所以只能在删除的时候同时执行迭代器前移的操作：

for(auto iter=c.begin(); iter!=c.end(); /**/) {
    if(badValue(*iter)) c.erase(iter++);
    else ++iter;
}

二、vector和string

2.1 和C API工作

vector和string算是C/C++数组和字符数组的最安全替代方案了，不过对于C API他们默认是不兼容的，不过vector和string都可以通过特殊的方式实现C API兼容的需求。

因为标准规定了vector的内存布局一定是连续的，可以通过&v[0]和v.size()实现指针和元素个数的传递，不过针对v可能是空的情况下&v[0]产生的地址可能并不存在，使用时候需要注意判断。不过在C++0x中最好使用data()成员函数，他可以返回兼容的指针类型(即便v是空的)。千万注意，此处 迭代器和指针是完全两码事 ，如果非要使用迭代器，请使用&*v.begin()。

上述方法对string不一定可靠，因为 string中的数据不一定存储在连续内存 中，且string内部不一定是以空字符结尾的。针对string使用c_str()可以返回一个C兼容的空字符结尾的字符串，而且即使string是空的，c_str()也会返回一个指向空字符串的有效指针。不过这里返回的指针不一定指向字符串数据的内部表示，所以不要使用c_str()返回的指针来修改字符串内容(不过该函数本身返回const char*也容不得你修改)。还有，string现在也有一个data()成员函数，在某种情况下和c_str()效果相同。

2.2 回收vector和string多余的内存

如果容器峰值的时候存储了很多的元素，容器就会为此分配很多内存，但是当最后容器只存储很少量元素的时候，这部分内存默认就得不到释放，此时可以通过下面的swap手法将容器的容量缩减到当前实现算法下可以容纳所有元素的默认最小空间分配，从而释放多余的内存。其思路是先使用原数据进行拷贝构造一个临时对象(新建立的对象基本是按需分配的)，然后通过swap的方式进行交换，原先的臃肿对象将会被交换到临时对象并且随后被析构，从而内存就间接释放了。

vector<T>(t).swap(t);
string(s).swap(s);

不过C++0x已经支持shrink_to_fit()成员函数了，所以这个技巧也没什么价值了。

三、关联容器

3.1 相等和等价的区别

关联容器是依照 等价 (而不是相等)的语义来对待自己管理的元素的。

std::find和很多算法默认依照 相等 的语义处理相同元素判定的，他们本质上是以operator==操作为基础的，如果表达式”x==y”返回true，则x和y的值是相等的。这里需要了解，x和y有相等的值并不一定意味着他们的所有数据成员都具有相等的值，尤其在对operator==操作符进行重载的时候，这种差异性就更明显了。

3.2 指定比较类型和比较函数

对于自定义类型，如果想在关联容器中使用那么为其指定比较器是必须的。在对关联容器指定比较器的时候，一定要确保对相等值的情况返回false，否则会破坏关联容器的特性。比如针对

std::set<int, std::less_equal<int>> s;

将是可怕的，举例来说对于同一个整形值，其会检查!(x<=y)&&!(y<=x)，即!(true)&&!(true)，那么返回的结果必然是false，那么同一个整形此处返回false表示他们不等价，在容器中就会被插入两次。

或许大家平时写代码也不会这么白痴，但是有些情况是隐藏很深的，比如很多时候图省事针对某个类型想按照降序排列，此时如果直接!(x =，根本不是我们所期待的>。所以任何情况下，相等的值从来不会有前后顺序关系，针对 相等的值比较函数必须始终返回 false 才可以，术语上叫做严格的弱序化。

3.3 operator[]和insert插入新元素

对于关联容器map的operator[]，计上履行了“添加和更新”两项功能，其内部设计的原理是：当操作operator[]的时候，该操作返回一个指向与k相关值对象的引用，然后v被赋值给该引用所指向的对象，此时如果k已经有了相关联的值，则该值将会被更新，如果此时k还不存在，则会使用该值类型的默认构造函数构建一个新的对象，然后再返回指向这个新建对象的引用，并进行后续的赋值更新操作。

所以如果我们的意图是要插入新的元素，则推荐直接使用insert(C::value_type(k, v))的方式来操作，其效果上会节省以下调用开销：一个V临时对象的构造、临时对象的析构、V类型的赋值运算符。

但是如果明确要覆盖某个存在值的话，这时候情况就需要反过来考虑了，使用operator[]的效率是最高的，而如果使用上面显式插入的话，就需要付出一个pair 类型的构造和析构函数的代价，而且操作意图也没那么明确。

3.4 使用vector来替代关联容器

程序员不要一想到有序存放元素就直接使用关联容器来实现，如果排序只是为了快速查找，那还有很多种的解决方法可供参考，比如hash总是查找速度最快的(设计不好的hash函数导致碰撞严重不在此讨论范围)，虽然会导致一些空间的浪费。

其实对于不需要修改的数据，或者数据经过热阶段后就持续稳定的情况，还可以使用vector来有序存储这类元素，其理由有：a. 对于排序的vector，标准库有binary_search、lower_bound、equal_range等算法，其查找效率也是非常高的；b. vector的数据组织比较简单而且是物理连续的，占用内存空间小，根据局部性原理这类数据也更容易被缓存，而且不会造成内存碎片，而且关联容器的数据如果不在内存中发生缺页错误开销就更大了。

对于vector替代set，操作将会很清晰不必多言。如果使用vector来模拟map，则vector需要存储的元素就必须是pair 这种形式了，我们就需要为这种情况编写自定义的比较器以适配只考虑K排序的需求，因为默认的pair 是键和值都会比较的。

四、标准库算法

4.1 排序算法

STL中的sort是一个了不起的算法，能够满足大多数排序要求而且使用简单，除此之外还有其他的 排序算法 可以关注。

partial_sort(first, middle, last, cmp)

这个函数会保证在[first, last)范围中的所有元素进行比较后，在[first, middle)位置的元素是严格排序了的，这个算法可以快速解决topN这类问题，而不用对所有元素执行排序操作。

nth_element(first, middle, last, cmp)

partial_sort函数保证[first, middle)是严格排序的，但是如果对topN是否排序返回不关心，则可以使用nth_element算法。该算法保证执行完成之后第n个元素正好是完全排序情况下该元素所在的位置，而按照排序规则所有排在n位置之前的元素也都在n之前，所有按照排序规则需要排在n之后的元素也恰好都在n之后。这个算法不仅仅可以用于选出topN这类的应用，还可以用于选出中位数、选出某个 百分比的阈值数 等需求。

不过上面的sort、partial_sort、nth_element都是不稳定的排序，意味着对于 等价 元素他们结果的顺序是未定义的，如果一定需要稳定排序的特性，请使用stable_sort的方式来进行全排序。

partition(first, last, up)

这个函数根据up可以对[first, last)之间的数据进行分组，并返回一个迭代器作为分割点，这个函数还有一个stable_partition的稳定版本。并且partition和stable_partition只需要容器具有双向迭代器即可使用，所以除了slist(forward_list)基本所有的标准容器都可以使用他们。

小结

sort、stable_sort、partial_sort、nth_element都要求随机迭代器支持，所以这些算法只能用于vector、string、deque和数组。关联容器因为本身就是有序的了，所以关联容器没有排序方面的需求。除此之外如果需要对list进行排序，则直接调用list::sort成员函数就可以了。

上面的排序算法，其比较语义都是使用 等价 来实现的，除此之外依赖于排序的算法，比如：binary_search、lower_bound、upper_bound、equal_range也都是依据等价的语义来执行快速查找的，不过unique和unique_copy是个例外，虽然他们用于已经排序的容器，但是他们是基于 相等 的语义来执行元素比较的。

4.2 std::remove

std::remove(first, last, value)

C++中的std::remove接收迭代器参数但是不接受容器作为参数，所以它肯定无法知道元素被存在于哪个容器中，而且从迭代器类型根本无法推断出所对应的容器类型，那么std::remove怎么样从容器中删除元素呢？其实std::remove根本没有办法删除容器中的元素，调用std::remove不会使迭代器指向的容器数目减少，容器的元素的真正删除只能通过调用容器本身的成员函数实现。

其实std::remove所做的事情，就是将容器中不应该被删除的元素移动到区间的前部(并保持原来的相对位置)，并最终返回一个迭代器指向最后一个不用被删除的元素之后的位置，相当于逻辑删除后的end()位置。其实实现起来，更像是一个遍历数据然后进行压缩的过程，将需要删除的元素的空洞用后面元素来进行填充。

v.erase(std::remove(v.begin(), v.end(), 100), v.end());

std::remove通常需要和erase结合使用，其惯用模式如上面所描述。除了std::remove，类似的std::remove_if、std::unique的使用情形也类似，后者删除排序后相邻的重复元素。

上面的删除是通用方法，不过关联容器直接使用其成员函数erase更高效，而list通常使用成员函数remove来执行删除操作，接收这种不一致的命名吧。

4.3 数据分区统计

int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>());
std::string s 
    = std::accumulate(std::next(v.begin()), v.end(),
                            std::to_string(v[0]), // start with first element
                            [](std::string a, int b) {
                                  return a + '-' + std::to_string(b);
                            });

另外一个常用算法是std::for_each，这个算法的op没有上面std::accumulate那么严格的限制，执行的时候对区间中的每个元素调用执行这个函数，关键点是op参数可以是T&，这样就可以直接修改原迭代器所指向的值，当然你也可以const T&放弃这个权利。

五、其他使用注意事项

5.1 标准算法中的函数子

确保以传值的方式设计函数子类

按照惯例，C/C++标准库函数都是通过传值的方式(发生拷贝)来传递函数子的，如果函数子是普通函数则将函数指针按照传值的方式进行拷贝传递，如果你的函数子使用引用的方式来传递，那么很多标准算法可能无法通过编译正常使用。既然函数对象是按值传递的，那么要求最好：函数对象必须尽可能的小以减少拷贝开销，同时函数对象还必须是单态的，因为形参类型和实参类型不一致，按值传递可能会导致对象切割的问题。如果你的函数类确实有上述需求，那么建议将数据、虚函数从类中剥离出来放到一个新类中，然后函数子类使用一个指针指向这个复杂类(pImpl)。

确保函数子是纯函数

在C++判别式的设计中，好的设计习惯是保证判别式的返回值只依赖于参数和常量，应该避免对类成员变量、全局变量的修改造成副作用，所以判别式类的operator通常被声明为const的。

虽然我们只在标准算法函数中传递函数对象一次，但是其实际执行的次数是无法预估的，很多算法内部实现会依赖调用其他的算法，而这个调用过程可能可能会把你的函数对象传递给别人执行多次，如果函数对象的operator()有副作用，那么其副作用的影响是我们无法预估的，所以不要做这样的事情。

从unary_function和binary_function中进行派生然后实现

在写函数子的时候，虽然只要保证operator的签名满足算法库的需求就可以了，但是根据函数子参数的个数还是推荐通过继承std::unary_function 、std::binary_function

struct less_than_7 : std::unary_function<int, bool> {
    bool operator()(int i) const { return i < 7; }
};

struct same : std::binary_function<int, int, bool> {
    bool operator()(int a, int b) const { return a == b; }
};

struct WidgetBin: std::binary_function<T1, T2, R> {
    R operator()(T1 t1, T2 t2) const { ... }
    R operator()(const T1& t1, const T2& t2) const { ... }
};

5.2 优先使用算法替代手写循环，以函数对象代替普通函数作为函数子

通过上面的学习可以感觉到在程序开发中，很多for循环都可以直接用标准算法的调用来实现，虽然很多标准算法的内部也可能是使用循环遍历来实现的，但是使用标准算法的好处有：

a. 通常标准算法的循环效率更高，比如每次不需要计算size()或者end()终止条件。而且，标准算法会对遍历性能做极致的优化，比如连续容器中标准算法很可能会使用指针替换迭代器因而可以获得更高的迭代效率。

b. 标准算法调用的形式使其意义更明确容易被理解，而且正确性也容易得到保证，比如某些循环改变容器的时候需要考虑迭代器失效的问题，但是有标准算法的时候，这个锅就可以让标准算法库来背了。

优先使用函数对象代替普通函数，是因为C++中我们无法以一个实际的函数作为参数传递给标准算法，即使这个函数被申明为inline的，C++还是会以函数指针的方式传递该函数，那么在标准算法多次迭代的时候就需要承担每次进行函数调用的开销。不过函数对象没有这个限制，通常在类中定义的函数都默认是内联的，而这个类对象是可以作为参数直接传递给标准算法，因此使用函数对象通常比普通函数作为函数子的效率要高。

本文完！