【原创】浅谈C++容器的效率优化【noip吧】_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：21,270贴子：
【原创】浅谈C++容器的效率优化收藏
用C++容器的程序有时TLE，我来科普一个简单有效的优化方法先说一下优化效果，用NOIP2012提高组的drive测试了一下，其中用到了一个list，最后4个点会超时，最慢的一个用时1.33秒，用下文的方法优化，最慢的一个点仅用时0.62秒，而且这简短的优化比手写链表方便多了，其效率也可与手写链表媲美具体发在2L
码趣学院,专注于6-16岁青少儿noip教育,包括scratch,Python,Javanoip辅导!
在NOIP中，C++的容器的用途非常广泛，但经常因常数过大而超时。怎样才能提高它们的效率呢？我们知道，容器是存储同一类对象的对象，既然“对象”我们无法改变，那么我们只能从“存储”入手，不难想到，不同容器在实现上的根本区别是它们对应着不同的内存组织方式，内存管理无疑是这种实现的核心，所以优化内存管理是加快容器效率的最好途径之一。一、内存分配器简介怎样才能优化内存管理呢？很简单，C++为我们提供了这样的接口，我们可以通过自定义容器模板中的最后一个allocator内存分配器来提高容器效率，在默认情况下，alloc为allocator&T&，allocator&T&是C++的用于泛型化内存分配的模板，它在申请小空间时通常很快（比new运算符快一些），又因为自定义一般化的内存分配器（可自行查询“内存池”的资料）需要较大的代码量，而且效率未必高，所以本文我们只讨论某些特殊情况下的内存分配。二、编写内存分配模板下面我们来编写一个简单的内存分配器，为了简单起见，我们继承C++的allocator&T&：template&typename T&struct myalloc:allocator&T&构造函数是必不可少的：myalloc(){}template&typename T2&//别忘记写模板，下同myalloc(const myalloc&T2& &a){}template&typename T2&myalloc&T&& operator=(const myalloc&T2& &a){return *}由于继承了allocator&T&，所以一定要把rebind覆盖掉，否则other分配器将是allocator&T&，而不是myalloc：template&typename T2&struct rebind{typedef myalloc&T2&};接下来我们将讨论一下：如何实现T* allocate(size_t n)和void deallocate(T* p,size_t n)成员函数。我们只研究内存分配的最简单情况：不回收内存分配和定长内存分配。三、不回收内存分配回想一下链表的写法，在竞赛中最常见的实现往往是用数组模拟链表，存储链表的空间是从一个足够大的数组中得到的，这样编写快、效率也高。于是我们得到了主要思想：化动为静！我们一次性预留足够大的“线性”空间，申请内存时从“线”的开头截掉一部分，记录开头的位置即可。思路很直观，实现也很简单。开一个足够大的数组space，用space_len记录已经分配到的空间大小，注意space必须是全局变量，如果写在类里的话，那么这个类每次实例化都会重复占用空间，很可能超过内存限制。char space[];int space_len=0;可以写allocate函数了，n表示需要的空间大小，函数返回申请到的空间首地址：T* allocate(size_t n){T *result=(T*)(space+space_len);space_len+=n*sizeof(T);}然后把void deallocate(T* p,size_t n){}留空，短短几行代码就完成了一个不回收的内存分配器。四、定长内存分配在要申请的内存长度确定的情况下，我们可以完成内存释放函数以节省内存空间。内存释放的根本目的是将释放的内存用于下一次申请，由于我们要的内存是定长的，所以保存一下刚刚释放掉的内存地址，下次申请时直接返回这个地址不就可以了？我们用栈来保存地址：int stack[],stack_len=0;释放很简单：void deallocate(T* p,size_t n){stack[stack_len++]=(int)p; }再修改一下申请函数：T* allocate(size_t n){if(stack_len!=0)return (T*)stack[--stack_len];else{T *result=(T*)(space+space_len);space_len+=n*sizeof(T);}}五、效率对比大功告成！分配效率如何呢？这里用list进行效率测试：int start=clock();list&int,myalloc&int& & L;for(int i=0;i&800000;++i){L.push_back(500);L.pop_back();}cout && "myalloc:" && (double)(clock()-start)/CLOCKS_PER_SEC &&start=clock();list&int& L2;for(int i=0;i&800000;++i){L2.push_back(500);L2.pop_back();}cout && "allocator:" && (double)(clock()-start)/CLOCKS_PER_SEC &&笔者测试结果：myalloc:0.063allocator:0.203我们的myalloc比默认的allocator快了近三倍！那么它在实际应用中的效果如何呢？笔者用NOIP2012提高组的drive测试了一下，其中用到了一个list，最后4个点会超时，最慢的一个用时1.33秒，用刚刚介绍的定长内存分配器优化，最慢的一个点仅用时0.62秒。六、注意事项上文介绍的内存分配器缺少对内存上限的处理，因为有时我们并不清楚要开多大的space才够，所以当内存不足时通常要进行额外处理，用allocator来分配内存以防止内存泄露是个不错的选择，请读者自己完善代码。另外有些C++容器允许通过reserve成员函数预留内存，避免不必要的重复申请操作，这也是一个很有效的优化方法。
这种贴不加精什么贴才可以加！
此帖不精何为精贴
内存泄露不好玩
此非何精？
此沉何精？
各种手写..
P党弱弱路过……满脸羡慕→_→
业界良心！！
业界良心 火钳留明
我只把本文的最后一句话理解了，reserve。
关于这个……我只说一句……这已经比手写长了……
确实应该加精！！！！！！！！！！！！！！！！11
好帖！！虽然我看不懂——句符咒等於800个字！！！还在为拿不到经验而烦恼吗？赶紧复制粘贴吧看我...
a????????????????????????????????????j?????????????????????????f?????????????????????l??????????????????k??????????????????????;??????????????????s???????????????????????????！l?????????????????????k?????????????????????????????a????????????????????????????????????j?????????????????????????f?????????????????????l??????????????????k??????????????????????;??????????????????s???????????????????????????
——你们不觉得非常绮丽吗？
這好像比手寫長。。。TAT
居然是个坟贴。。。
登录百度帐号推荐应用C++中各种容器的类型与特点 - mu_tou_man - 博客园
随笔 - 77, 文章 - 0, 评论 - 1, 引用 - 0
连续存储结构，每个元素在内存上是连续的；
支持高效的随机访问和在尾端插入/删除操作，但其他位置的插入/删除操作效率低下；
连续存储结构，即其每个元素在内存上也是连续的，类似于vector，不同之处在于，deque提供了两级数组结构，第一级完全类似于vector，代表实际容器；另一级维护容器的首位地址。
这样，deque除了具有vector的所有功能外，还支持高效的首端插入/删除操作。
非连续存储结构，具有双链表结构，每个元素维护一对前向和后向指针，因此支持前向/后向遍历。
支持高效的随机插入/删除操作，但随机访问效率低下，且由于需要额外维护指针，开销也比较大。
4、vector V.S. list V.S. deque：
a、若需要随机访问操作，则选择vector；
b、若已经知道需要存储元素的数目， 则选择vector；
c、若需要随机插入/删除（不仅仅在两端），则选择list
d、只有需要在首端进行插入/删除操作的时候，才选择deque，否则都选择vector。
e、若既需要随机插入/删除，又需要随机访问，则需要在vector与list间做个折中。
f、当要存储的是大型负责类对象时，list要优于vector；当然这时候也可以用vector来存储指向对象的指针，同样会取得较高的效率，但是指针的维护非常容易出错，因此不推荐使用。
5、capacity V.S size
a、capacity是容器需要增长之前，能够盛的元素总数；只有连续存储的容器才有capacity的概念（例如vector，deque，string），list不需要capacity。
b、size是容器当前存储的元素的数目。
c、vector默认的容量初始值，以及增长规则是依赖于编译器的。
6、用vector存储自定义类对象时，自定义类对象须满足：
a、有可供调用的无参构造函数（默认的或自定义的）；
b、有可用的拷贝赋值函数（默认的或自定义的）
7、迭代器iterator
a、vector与deque的迭代器支持算术运算，list的迭代器只能进行++/--操作，不支持普通的算术运算[C++]高效使用容器的一些建议
本文介绍一些在使用容器中常见的问题，并给出其解决方法从而提升对容器的认识和使用。
1. 不要试图编写独立于容器类型的代码
STL是以泛化原则为基础的：数组被泛化为&以其包含的对象的类型为参数&的容器；函数被泛化为&以其使用的迭代器的类型为参数&的算法；指针被泛化为&以其指向的对象的类型为参数&的迭代器。
如果我们试图编写独立于容器类型的代码，例如编写一个既能够满足序列容器又满足关联容器的代码，我们最后会发现我们使用的只是他们功能交集而已，而这个交集几乎没有什么用。
但是对于客户代码却不见得如此。对于客户代码为了提高可维护性，我们需要使用封装的技术。最简单的方法就是通过对容器类型和其迭代器类型使用类定义。因此，不要写：
class Widget {...};
Widget bestW
assign a value to bestWidget
vector::iterator i = find(vw.begin(), vw.end(), bestWidget);
而要写成：
class Widget {...};
typedef vector WidgetC
Widget bestW
WidgetContainer::iterator i = find(cw.begin(), cw.end(), bestWidget);
如此，当你想要改变容器类型时，就会简单很多。尤其是当这种改变只是增加一个自定义的分配子时，就显得更加方便了。
class Widget {...};
SpecialAllocator { ... };
typedef vector& WidgetC
Widget bestW
WidgetContainer::iterator i = find(cw.begin(), cw.end(), bestWidget);
类型定义只不过是其他类型的别名，所以它带来的封装纯粹是词法上的，但可以很有效地减少代码量。
类型定义并不能阻止客户去做他们原本无法做到的事情。如果你不想把自己选择的容器暴露给客户，就得使用类。例如把容器隐藏在一个类中，并尽量减少那些通过类接口可见的，与容器相关的信息。
class CustomerList {
typedef list CustomerC
typedef CustomerConatiner::iterator CCI
CustomerContainer C
当你需要改变类的容器时，需要注意检查类的相关函数是否会受到影响。
2. 确保容器中的对象拷贝正确而高效
容器中保存了对象，但并不是你提供给那些容器的对象，而是他们的拷贝。
无论是对象的赋值，移动，排序都是基于拷贝来实现的。拷贝对象就是STL的工作方式。
值得注意的是，对于存在继承关系的情况下，拷贝动作会导致剥离（slicing）。也就是说，如果你创建了一个存放基类对象的容器，却向其中放入派生类的对象，那么派生类的对象被拷贝进容器时，它的特有部分将会丢失。
剥离问题意味着向含有基类对象的容器中放入派生类对象总是错误的，如果你希望其正确的使用，那么应该使用存放基类指针。（动态绑定）
容器的设计思想是为了避免不必要的拷贝，它的总体目标总是避免创建不必要的对象。例如在内置数组中，只要指定了大小，它总是会调用缺省构造函数来使每一个对象实例化，但对于容器却不一定会如此。
class Widget {
Widget() {
cout && &Widget constructed!& &&
int main(int argc, char *argv[]) {
Widget Widgets[1];
vector Widget_vec(1);
Widget_vec.reserve(12);
cout && Widget_vec.capacity() &&
Widget constructed!
Widget constructed!
从以上代码清楚看出，对于内置数组他会实例了对象，同样地如果在声明容器时提供了容器大小，他也一样会对实例化对象。但对于reserve函数则不会实例化。这是因为reserve只是告诉了这个容器，里面可以存放对象的数量，并没有告诉你已经可以使用这个对象，这有利于让使用者确定需要创建他时才创建他，更加地高效。
3. 调用empty()而不是检查size() == 0
对于任何的容器调用empty总是消耗常数时间。但计算size可并不一定如此。
问题就在于，并不是每个容器都给了size这个变量用来存储对象数量。特别是那些为了提高区间连接函数的执行效率的容器，他们并不会提供size这种常量。
典型的就是list的splice函数衔接功能。
int main(int argc, char *argv[]) {
list l1{1, 2, 3, 4, 5};
list l2{5, 6, 7, 8, 9, 10};
l1.splice(l1.end(), l2, find(l2.begin(), l2.end(), 5), find(l2.rbegin(), l2.rend(), 10).base());
cout && l1.size() &&
for (auto l : l1) {
cout && l && & &;
1 2 3 4 5 5 6 7 8 9 10
在splice函数中，他总是可以直接找到一段区间来完成相应的操作，而这只消耗常数时间，但如果list还有size变量，那么他就必须遍历整个区间来确定size的值，而这会消耗线性时间。
因此，是否为了提高splice的效率而不使用size是STL的编写者需要考虑的。对于不同平台而言，他们的实现可能是不同的。
但是无论有没有size变量，empty()函数总是消耗常数时间的。所以调用empty()总是更高效的。
4. 区间成员函数优先于单元素成员函数
调用区间函数可以极大地提高效率。
我们常常会忘记了赋值函数assign的作用。assign函数可以很快地把一段区间的值赋值给另一个容器，从而提高效率。例如：
int main(int argc, char *argv[]) {
list l1{1, 2, 3, 4, 5};
list l2{5, 6, 7, 8, 9, 10};
l1.assign(l2.begin(), l2.end());
cout && l1.size() &&
for (auto l : l1) {
cout && l && & &;
一个简单赋值操作可以用其他低效率但十分常见的方法完成。
例如，用循环。
int main(int argc, char *argv[]) {
list l1{1, 2, 3, 4, 5};
list l2{5, 6, 7, 8, 9, 10};
l1.clear();
for (list::iterator iter = l2.begin();iter != l2.end();iter++) {
l1.push_back(*iter);
cout && l1.size() &&
for (auto l : l1) {
cout && l && & &;
这种写法即要用大量的代码，同样也非常地低效。后文见说明。
又或则使用copy函数。
int main(int argc, char *argv[]) {
list l1{1, 2, 3, 4, 5};
list l2{5, 6, 7, 8, 9, 10};
l1.clear();
copy(l2.begin(), l2.end(), back_inserter(l1));
cout && l1.size() &&
for (auto l : l1) {
cout && l && & &;
毫无疑问在copy函数里面也同样使用了循环。但更要的问题是，insert函数清晰地说明了数据插入到了l1里，而copy则掩盖了这一点只说明了对象被拷贝。对象被拷贝是显然的，STL就是建立在数据被拷贝的基础上的。
所以说，使用区间函数的原因：
通过区间函数调用，可以减少代码。 使用区间函数通常会得到意图明确清晰和更加直接的代码。
简单地说，就是更加易懂。
除了assign函数之外，还有就是insert函数。
int main(int argc, char *argv[]) {
list l1{1, 2, 3, 4, 5};
list l2{5, 6, 7, 8, 9, 10};
l1.clear();
l1.insert(l1.begin(), l2.begin(), l2.end());
cout && l1.size() &&
for (auto l : l1) {
cout && l && & &;
如果使用循环，则会复杂很多。
int main(int argc, char *argv[]) {
list l1{1, 2, 3, 4, 5};
list l2{5, 6, 7, 8, 9, 10};
l1.clear();
list::iterator iter_1 = l1.begin();
for (list::iterator iter = l2.begin();iter != l2.end();iter++) {
iter_1 = l1.insert(iter_1, *iter);
cout && l1.size() &&
for (auto l : l1) {
cout && l && & &;
又或则使用copy函数。
int main(int argc, char *argv[]) {
list l1{1, 2, 3, 4, 5};
list l2{5, 6, 7, 8, 9, 10};
l1.clear();
copy(l2.begin(), l2.end(), inserter(l1, l1.begin()));
cout && l1.size() &&
for (auto l : l1) {
cout && l && & &;
而后面两个总是低效率的。因为他们是一次一次地往里加入新元素，而这必然会导致大量的元素移动、拷贝和创建的开销。但对于区间函数则可以一次性地往里加入最终需要的元素，减少了不必要的开销。这听起来比较难理解，但仔细想想应该能明白。
总而言之，对于
区间创建 区间插入 区间删除 区间赋值
都不应该使用单元素的操作而应该使用区间函数来完成，这几乎必然会减少开销。
5. C++编译器的分析机制
C++总是把声明尽量理解为函数。
假设你想把一个存有整数的文件的数据存入list中，并写出一下代码：
ifstream dataFile(&ints.dat&);
list data(istream_iterator (dataFile), istream_iterator ());
这种做法的想法是把一对istream_iterator作为区间传入到list中。但问题是，编译器并不会按照我们的想法来做。
首先我们先来解释一些奇怪的现象：
int f(double d);
这是一个函数声明。
int f(double (d));
这同样是个函数声明。参数两边的括号是可以忽略的。
int f(double);
这还是一个函数声明。
int f(double (*pf)());
这是一个函数声明，它的参数是一个指向不带任何参数的函数的指针，该函数返回double值。
int f(double pf());
这和上面的函数的意思是一样的，只不过pf用非指针的形式来声明。
int f(double ());
这是第三种声明，其中参数名pf被忽略了。
请注意围绕参数名的括号和独立的括号的区别。围绕参数名的括号被忽略，而独立的括号则表明参数列表的存在，他们说明存在一个函数指针参数。
所以，对于这段代码
ifstream dataFile(&ints.dat&);
list data(istream_iterator (dataFile), istream_iterator ());
编译器实际上会理解为：
第一个参数的名称是dataFile，它的类型是istream_iterator，dataFile两边的括号是多余的，会被忽略。 第二个参数没有名称，是一个指向不带参数的函数的指针，该函数返回一个istream_iterator。
更常见的错误就是，
Widget() {
cout && &Construct!& &&
Widget w();
这总是会理解为函数声明。
所以对于上述的代码，正确的做法是。
ifstream dataFile(&ints.dat&);
list data((istream_iterator (dataFile)), istream_iterator());
但更加常见的做法是，避免使用匿名的istream_iterator对象。
ifstream dataFile(&ints.dat&);
istream_iterator dataBegin(dataFile);
istream_iterator dataE
list data(dataBegin, dataEnd);
这样可以避免许多的错误。
6. 在容器如何管理自己创建的对象
容器很智能，但并没有智能到可以帮你解决所有的问题，特别是不能帮你避免内存泄露。
典型的例子是，你通过循环给容器中添加创建的对象。
void doSomething() {
for (int i = 0;i != max_i++) {
lw.push_back(new Widget);
这个函数执行结束之后就出现了内存泄露。
当然了，避免内存泄露非常地简单。
void doSomething() {
for (int i = 0;i != max_i++) {
lw.push_back(new Widget);
for (list::iterator iter = lw.begin();iter != lw.end();iter++) {
但这不是异常安全的，只要在填充指针和删除指针过程中有异常抛出一样会有内存泄露。
如果使用for_each函数，则需要先实现一个函数对象。
struct DeleteObject : public unary_function {
void operator()(const T* ptr) const {
void doSomething() {
for (int i = 0;i != max_i++) {
lW.push_back(new Widget);
for_each(lW.begin(), lW.end(), DeleteObject());
但这有个问题就是DeleteObject需要在每次使用时给出模板类型，这是非常不好的。因为在大量的代码过后，你很有可能会忘记类型是什么，所以更好的方法是，让他自己去推断类型。
#define max_num 100
struct DeleteObject {
void operator()(const T* ptr) const {
void doSomething() {
for (int i = 0;i != max_i++) {
lW.push_back(new Widget);
for_each(lW.begin(), lW.end(), DeleteObject());
这样就简单了很多。但这依然不是异常安全的。所以归根结底地方法还是应该选用智能指针，但注意，要使用shared_ptr而不要用auto_ptr.
因为auto_ptr有个很重要的特性是，他会在每一次复制过后把自己定为NULL，从而保证只有一个指针指向它，但实际上在容器中会有大量的复制操作，这会导致容器无法使用，所以不可以在容器中存放auto_ptr对象。
7. 删除元素的方法
对于不同的容器，有不同的删除元素的方法。
对于连续内存容器的删除
(vector, deque, string) 使用erase-remove
c.erase(remove(c.begin(), c.end(), 50), c.end());
bool badvalue(int);
c.erase(remove_if(c.begin(), c.end(), badvalue), c.end());
如果要记录被删除的元素，则一定要使用循环，但问题没那么简单：
for (SeqContainer::iterator i = c.begin(); i != c.end();) {
if (badvalue(*i) {
i = c.erase(i); // 序列容器的erase会返回被删除的下一个迭代器。
list使用remove
c.remove(50);
bool badvalue(int);
c.remove_if(badvalue);
对于关联容器使用erase
c.erase(50);
对于使用函数来判断是否要删除，有两种方法：
AssociateContainer
AssociateContainer
remove_copy_if(c.begin(), c.end(), insert(goodvalue, goodvalue.end()), badvalue);
c.swap(goodvalue);
缺点是需要把所有不需要删除的元素复制一遍。
AssociateContainer
for (AssociateContainer::iterator i = c.begin(); i != c.end(); /* Do nothing. */) {
if (badvalue(*i)) {
如果还需要做其他操作
c.erase(i++);
关联容器的erase函数返回void，所以用后置递增，返回旧值，而作为副作用，i递增。什么是C++容器？_百度知道
什么是C++容器？
容器用来存储数据的，数据可以是用户自定义类型（对象），也可以是预定义类型。 c++中的容器主要使用如vector,list （顺序容器） 这些都是已经封装好了的，包含头文件&vector&,&list&,通过迭代器iterator访问容器中的数据,map,set(关联容器),关联容器map键值对形式出现key-value，key唯一，mutimap多映射可以不唯一；set是一个单一值的集合，如1,2,3,4。vector容器的特点：在内存中是一片连续的存储区域，初始化的时候，可以指定容量，比如如果定义容量50 的容器存储 60个string对象，由于初始容量不足60，容器将会重新定义一个容量是原来的2倍新容器，然后拷贝原容器的对象到新容器. 读取速度快，插入删除效率低.如果仅仅在容器头或尾部 进行增删改，推荐使用deque，专门提供了对首尾的操作.list容器特点：相当数据结构的链表，不是一个连续的存储区域，插入，删除很方便，但是查询速度慢。vector&string& vec 就是定义了一个vector容器,可以通过vec.push_back(), push_font(),insert(position,value) 想vector中添加一个指定值list&int& ilist&初始大小,默认赋值& list&int& ilist(20 -1) 初始20个值为-1的list
采纳率：63%
来自团队：
这也体现了容器类的一个好处C++中容器的定义如下：数据存储上，有一种对象类型，它可以持有其他对象或指向其他对象的指针，这种对象类型叫容器。通俗的说容器就是保存其他对象的对象，这种“对象”还包含了一些列处理其他对象的方法，“容器类对特定代码重用问题的良好的解决方案”。容器另一个好处就是可以自行扩展，解决问题是不知道需要存储多少个对象，数组在这方面是个欠缺。容器可以为申请内存
本回答被网友采纳
为您推荐：
其他类似问题
您可能关注的内容
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。第1章&容器
第1条：慎重选择容器类型。
标准STL序列容器：vector、string、deque和list。
标准STL关联容器：set、multiset、map和multimap。
非标准序列容器slist和rope。slist是一个单向链表，rope本质上是一&重型&string。
非标准的关联容器hash_set、hase_multiset、hash_map和hash_multimap。
vector&char&&作为string的替代。(见第13条)
vector作为标准关联容器的替代。(见第23条)
几种标准的非STL容器，包括数组、bitset、valarray、stack、queue和priority_queue。
你是否关心容器中的元素是如何排序的？如果不关心，选择哈希容器.
容器中数据的布局是否需要和C兼容？如果需要兼容，就只能选择vector。(第16条)
元素的查找速度是否是关键的考虑因素？如果是，就要考虑哈希容器、排序的vector和标准关联容器－或许这就是优先顺序。
对插入和删除操作，你需要事务语义吗？如果是，只能选择list。因为在标准容器中，只有list对多个元素的插入操作提供了事务语义。
deque是唯一的、迭代器可能会变为无效（插入操作仅在容器末尾发生时，deque的迭代器可能会变为无效）而指向数据的指针和引用依然有效的标准STL容器。
第2条：不要试图编写独立于容器类型的代码。
如果你想编写对大多数的容器都适用的代码，你只能使用它们的功能的交集。不同的容器是不同的，它们有非常明显的优缺点。它们并不是被设计用来交换使用的。&
第3条：确保容器中的对象拷贝正确而高效。
copy&in,copy&out，是STL的工作方式，它总的设计思想是为了避免不必要的拷贝。
第4条：调用empty而不是检查size()是否为0。
　　理由很简单：empty对所有的标准容器都是常数时间操作，而对一些list的实现，size耗费线性时间。
第5条：区间成员函数优先于与之对应的单元素成员函数。
区间成员函数写起来更容易，更能清楚地表达你的意图，而且它们表现出了更高的效率。
第6条：当心C＋＋编译器最烦人的分析机制。
把形参加括号是合法的，把整个形参（包括数据类型和形参名）用括号括起来是非法的。
第7条：如果容器中包含通过new操作创建的指针，切记在容器对象析构前将指针delete。
STL很智能，但没有智能到知道是否该删除自己所包含的指针所指向的对象的程度。为了避免资源泄漏，你必须在容器被析构前手工删除其中的每个指针，或使用引用计数形式的智能指针（比如Boost的sharedprt）代替指针。
第8条：切勿创建包含auto_ptr的容器对象。
拷贝一个auto_ptr意味着改变它的值。例如对一个包含auto_ptr的vector调用sort排序，结果是vector的几个元素被置为NULL而相应的元素被删除了。
第9条：慎重选择删除元素的方法。
要删除容器中指定值的所有对象：
如果容器是vector、string或deque，则使用erase-remove习惯用法。
SeqContainer&int&&c;
c.erase(remove(c.begin(),c.end(),1963),c.end());
如果容器是list，则使用list::remove。
如果容器是一个标准关联容器，则使用它的erase成员函数。
要删除容器中满足特定条件的所有对象：
如果容器是vector、string或deque，则使用erase-remove_if习惯用法。
如果容器是list，则使用list::remove_if。
如果容器是一个标准关联容器，则使用remove_copy_if和swap，或者写一个循环遍历容器的元素，记住当把迭代器传给erase时，要对它进行后缀递增。
AssocCOntainer&int&&c;
AssocContainer&int&&goodV
remove_copy_if(c.begin(),&c.end(),&
&&&&&&&&&&&&&&&&&inserter(goodValues,&goodValues.end()),&badValue);
c.swap(goodValues);
for(AssocContainer&int&::iterator&i&=&c.begin();i&!=c.end();/*&do&nothing&*/){
if(badValue(*i))&c.erase(i++);
&&&&&&&&&else&++i;
要在循环内部做某些（除了删除对象之外的）操作：
如果容器是一个标准序列容器，则写一个循环来遍历容器中的元素，记住每次掉用erase时，要用它的返回值更新迭代器。
如果容器是一个标准关联容器，则写一个循环来遍历容器中的元素，记住每次把迭代器传给erase时，要对迭代器做后缀递增。
第12条：切勿对STL容器的线程安全性有不切实际的依赖。
对一个STL实现你最多只能期望：多个线程读是安全的；多个线程对不同的容器写入操作是安全的。
你不能期望STL库会把你从手工同步控制中解脱出来，且你不能依赖于任何线程支持。
第2章&vector和string
第13条：vector和string优先于动态分配的数组。
如果用new，意味着你要确保后面进行了delete。
如果你所使用的string是以引用计数来实现的，而你又运行在多线程环境中，并认为string的引用计数实现会影响效率，那么你至少有三种可行的选择，而且，没有一种选择是舍弃STL。首先，检查你的库实现，看看是否可以禁用引用计数，通常是通过改变某个预处理变量的值。其次，寻找或开发一个不使用引用计数的string实现。第三，考虑使用vector&char&而不是string。vector的实现不允许使用引用计数，所以不会发生隐藏的多线程性能问题。
第14条：使用reserve来避免不必要的重新分配。
通常有两种方式来使用reserve以避免不必要的重新分配。第一种方式是，若能确切知道或大致预计容器中最终会有多少个元素，则此时可使用reserve。第二种方式是，先预留足够大的空间，然后，当把所有的数据都加入后，再去除多余的容量。
第15条：注意string实现的多样性。
如果你想有效的使用STL，那么你需要知道string实现的多样性，尤其是当你编写的代码必须要在不同的STL平台上运行而你又面临着严格的性能要求的时候。
第16条：了解如何把vector和string数据传给旧的API。
如果你有个vector&v，而你需要得到一个只想v中的数据的指针，从而可把数据作为数组来对才，那么只需要使用＆v［0］就可以了，也可以用＆＊v.begin（），但是不好理解。对于string&s，随应的形式是s.c_str()。
如果想用来自C&API的数据来初始化一个vector，那么你可以利用vector和数组的内存布局兼容性，先把数据写入到vector中，然后把数据拷贝到期望最终写入的STL容器中。
第17条：使用&swap技巧&除去多余的容量。
vector&Contestant&(contestants).swap(contestants);
表达式vector&Contestant&(contestants)创建一个临时的矢量，它是contestants的拷贝：这是由&vector的拷贝构造函数来完成的。然而，vector的拷贝构造函数只为所拷贝的元素分配所需要的的内存，所以这个临时矢量没有多余的容量。然后我们把临时矢量中的数据和contestants中的数据作swap操作，在这之后，contestants具有了被去除之后的容量，即原先临时变量的容量，而临时变量的容量则变成了原先contestants臃肿的容量。到这时，临时矢量被析构，从而释放了先前为contestants所占据的内存。
同样的技巧对string也实用：
string&s；
string(s).swap(s);
第3章&关联容器
第19条：理解相等（equality）和等价（equivalence）的区别。
标准关联容器总是保持排列顺序的，所以每个容器必须有一个比较函数（默认为less）。等价的定义正是通过该比较函数而确定的。相等一定等价，等价不一定相等。
第20条：为包含指针的关联容器指定比较类型。
每当你创建包含指针的关联容器时，容器将会按照指针的值（就是内存地址）进行排序，绝大多数情况下，这不是你所希望的。
第21条：总是让比较函数在等值情况下返回false。
现在我给你演示一个很酷的现象。创建一个set，用less_equal作为它的比较类型，然后把10插入到该集合中：
set&int,&less_equal&int&&&&s;&//s&用"&="&来排序
s.insert(10);
s.insert(10);
对于第二个insert，集合会检查下面的表达式是否为真：
!(10a&&=&10b)&&&&!(10b&&=&10a);&//检查10a和10b是否等价，结果为false
结果集合中有两个10！
从技术上讲，用于对关联容器排序的比较函数必须为他们所比较的对象定义个&严格的弱序化&（strict&weak&ordering）。
第22条：切勿直接修改set或multiset中的键。
如果你不关心可移植性，而你想改变set或multiset中元素的值，并且你的STL实现（有的STL实现中，比如set&T&::&iterator&的operator*总是返回const&T&，就不能修改了）允许你这么做，则请继续做下去。只是注意不要改变元素中的键部分，即元素中能够影响容器有序性的部分。
如果你重视可移植性，就要确保set和multiset中的元素不能被修改。至少不能未经过强制类型转换（转换到一个引用类型const_cast&T&&）就修改。
如果你想以一种总是可行而且安全的方式来许该set、multiset、map和multimap中的元素，则可以分5个简单步骤来进行：
1.&找到你想修改的容器的元素。如果你不能肯定最好的做法，第45条介绍了如何执行一次恰当的搜索来找到特定的元素。
2.&为将要被修改的元素做一份拷贝，。在map和multimap的情况下，请记住，不要把该拷贝的第一个部分声明为const。毕竟，你想要改变它。
3.&修改该拷贝，使它具有你期望的值。
4.&把该元素从容器中删除，通常是通过erase来进行的（见第9条）。
5.&把拷贝插到容器中去。如果按照容器的排列顺序，新元素的位置可能与被删除元素的位置相同或紧邻，则使用&提示&（hint）形式的insert，以便把插入的效率从对数时间提高到常数时间。把你从第1步得来的迭代器作为提示信息。
第23条：考虑用排序的vector替代关联容器。
标准关联容器通常被实现为平衡的二叉查找树。也就是说，它所适合的那些应用程序首先做一些插入操作，然后做查找，然后可能又插入一些元素，或许接着删掉一些，随后又做查找，等等。这一系列时间的主要特征是插入、删除和超找混在一起。总的来说，没办法预测出针对这颗树的下一个操作是什么。
很多应用程序使用其数据结构的方式并不这么混乱。他们使用其数据结构的过程可以明显地分为三个阶段，总结如下：
1.&设置阶段。创建一个新的数据结构，并插入大量元素。在这个阶段，几乎所有的操作都是插入和删除操作。很少或几乎没有查找操作。
2.&查找操作。查询该数据结构以找到特定的信息。在这个阶段，几乎所有的操作都是查找操作，很少或几乎没有插入和删除操作。
3.&重组阶段。改变该数据结构的内容，或许是删除所有的当前数据，再插入新的数据。在行为上，这个阶段与第1阶段类似。当这个阶段结束以后，应用程序又回到第2阶段。
第24条：当效率至关重要时，请在map::operator[]与map::insert之间谨慎作出选择。&
&&&&&& 如果要更新一个已有的映射表元素，选择operator[]；如果要添加一个新的元素，选择insert。
第25条：熟悉非标准的哈希容器。
标准C++库没有任何哈希容器，每个人认为这是一个遗憾，但是C++标准委员会认为，把它们加入到标准中所需的工作会拖延标准完成的时间。已经有决定要在标准的下一个版本中包含哈希容器。
第4章&迭代器
第26条：iterator优先于const_iterator、reverse_iterator以及const_reverse_iterator。
减少混用不同类型的迭代器的机会，尽量用iterator代替const_iterator。从const正确性的角度来看，仅仅为了避免一些可能存在的&STL实现缺陷而放弃使用const_iteraor显得有欠公允。但考虑到在容器类的某些成员函数中指定使用iterator的现状，得出&iterator较之const_iterator更为实用的结论也就不足为奇了。更何况，从实践的角度来看，并不总是值得卷入&const_iterator的麻烦中。
第27条：使用distance和advance将容器的const_iterator转换成iterator。
下面的代码试图把一个const_iterator强制转换为iterator：
typedef&deque&int&&IntD&//类型定义，简化代码
typedef&IntDeque::iterator&I
typedeef&IntDeque:;const_iterator&ConstI
ConstIter&&//ci&是一个const_iterator
Iter&i(ci);&//编译错误！从const_iterator&到&iterator没有隐式转换途径
Iter&i(const_cast&Iter&(ci));&//仍然是编译错误！不能将const_iterator强制转换为iterator
包含显式类型转换的代码不能通过编译的原因在于，对于这些容器类型，iterator和const_iterator是完全不同的类，他们之间的关系甚至比string和complex&double&之间的关系还要远。
下面是这种方案的本质。
typedef&deque&int&&IntD&//类型定义，简化代码
typedef&IntDeque::iterator&I
typedeef&IntDeque:;const_iterator&ConstI
IntDeque&d;
ConstIter&&//ci&是一个const_iterator
...&//使ci指向d
Iter&i(d.begin());//使i指向d的起始位置
advance(i,distance&ConstIter&(i,ci));//移动i，使它指向ci所指的位置
这中方法看上去非常简单和直接，也很令人吃惊。为了得到一个与const_iterator指向同一位置的iterator，首先创建一个新的&iterator，将它指向容器的起始位置，然后取得const_iterator距离容器起始位置的偏移量，并将iterator向前移动相同的偏移量即可。这项技术的效率取决于你所使用的迭代起，对于随机迭代器，它是常数时间的操作；对于双向迭代器，以及某些哈希容器，它是线性时间的操作。
第28条：正确理解由reverse_iterator的base()成员函数所产生的iterator的用法。
如果要在一个reverse_iterator&ri指定的位置上插入元素，则只需在ri.base()位置处插入元素即可。对于插入操作而言，ri和ri.base()是等价的，ri.base()是真正与ri对应的iterator。
如果要在一个reverse_iterator&ri指定的位置上删除一个元素，则需要在ri.base()前一个位置上执行删除操作。对于删除操作而言，ri和ri.base()是不等价的。
我们还是有必要来看一看执行这样一个删除操作的实际代码，其中暗藏着惊奇之处：
vector&int&&v;
...&//同上，插入1到5
vector&int&::reverse_iterator&ri&=&find(v.rbegin(),v.rend(),3);//使ri指向3
v.erase(--ri.base());&//试图删除ri.base()前面的元素，对于vector，往往编译通不过
对于vector和string，这段代码也许能工作，但对于vector和string的许多实现，它无法通过编译。这是因为在这样的实现中，&iterator(和vconst_iterator)是以内置指针的方式实现的，所以ri.base()的结果是一个指针。C和C＋＋都规定了从函数返回的指针不应该被修改，所以所以编译不能通过。
既然不能对base()的结果做递减操作，那么只要先递增reverse_iterator，然后再调用base()函数即可！
v.erase((++ri).base());&//删除ri所指的元素，这下编译没问题了！
第29条：对于逐个字符的输入请考虑使用istreambuf_iterator。
假如你想把一个文本文件的内容拷贝到一个string对象中，以下的代码看上去是一种合理的解决方案：
ifstream&inputFile("interestingData.txt");
inputFIle.unsetf(ios::skipws);//istream_iterator使用operator&&函数来完成实际的读操作，而默认情况下operator&&函数会跳过空白字符
string&fileData((istream_iterator&char&&(inputFIle)),istream_iterator&char&());
然而，你可能会发现整个拷贝过程远不及你希望的那般快。istream_iterator内部使用的operator&&实际上执行了格式化的输入，但如果你只是想从输入流中读出下一个字符的话，它就显得有点多余了。
有一种更为有效的途径，那就是使用STL中最为神秘的法宝之一：istreambuf_iterator。&istreambuf_iterator&char&对象使用方法与istream_iterator&char&大致相同，但是istreambuf_iterator&char&直接从流的缓冲区读取下一个字符。（更为特殊的是，&istreambuf_iterator&char&对象从一个输入流istream&s中读取下一个字符的操作是通过s.rdbuf()-&sgetc()来完成的。）
ifstream&inputFile("interestingData.txt");
string&fileData((istreambuf_iterator&char&(inputFile)),istreambuf_iterator&char&());
这次我们用不着清楚输入流的skipws标志，因为istreambuf_iterator不会跳过任何字符。
同样的，对于非格式化的逐个字符输出过程，你也应该考虑使用ostreambuf_iterator。
第5章&算法
第30条：确保目标区间足够大。
当程序员希望向容器中添加新的对象，这里有一个例子：
int&transmogrify(int&x);&//该函数根据x生成一个新的值
vector&int&&
vector&int&&
transform(values.begin(),values.end(),back_inserter(results),transmogrify);
back_inserter返回的迭代起将使得push_back被调用，所以back_inserter可适用于所有提供了push_back方法的容器。同理，front_inserter仅适用于那些提供了push_front成员函数的容器（如deque和list）。
当是使用reserver提高一个序列插入操作的效率的时候，切记reserve只是增加了容器的容量，而容器的大小并未改变。当一个算法需要向&vector或者string中加入新的元素，即使已经调用了reserve，你也必须使用插入型的迭代器。如下代码给出了一种错误的方式：
vector&int&&
vector&int&&
results.reserve(results.size()&+&values.size());
transform(values.begin(),&values.end(),&results.end(),&transmogrify);//变换的结果会写入到尚未初始化的内存，结果将是不确定的
在以上代码中transform欣然接受了在results尾部未初始化的内存中进行复制操作的任务。由于赋值操作重视在两个对象之间而不是在一个对象与一个未初始化的内存块之间进行，所以一般情况下，这段代码在运行时会失败。
假设希望transform覆盖results容器中已有的元素，那么就需要确保results中已有的元素至少和values中的元素一样多。否则，就必须使用resize来保证这一点。
vector&int&&
vector&int&&
if(results.size()&&&values.size()){
results.resize(values.size());
transform(values.begin(),values.end(),results.begin(),transmogrify);
或者，也可以先清空results，然后按通常的方式使用一个插入型迭代起：
results.clear();
results.reserve(values.size());
transform(values.begin(),values.end(),back_inserter(results),transmogrify);
第31条：了解各种与排序有关的选择。
sort(stable_sort)、partial_sort和nth_element算法都要求随即访问迭代器，所以这些算法只能被应用于&vector、string、deque和数组。partion（stable_partion）只要求双向迭代器就能完成工作。
对于标准关联容器中的元素进行排序并没有实际意义，因为它们总是使用比较函数来维护内部元素的有效性。
list是唯一需要排序却无法使用这些排序算法的容器，为此，list特别提供了sort成员函数（有趣的是，list::sort执行的是稳定排序）。如果希望希望一个list进行完全排序，可以用sort成员函数；但是，如果需要对list使用partial_sort或者nth_element算法的话，你就只能通过间接途径来完成了。一种间接做法是，将list中的元素拷贝到一个提供随即访问迭代器的容器中，然后对该容器执行你所期望的算法；另一种简介做法是，先创建一个list::iterator的容器，再对该容器执行相应的算法，然后通过其中的迭代器访问list的元素；第三中方法是利用一个包含迭代器的有序容器的信息，通过反复地调用splice成员函数，将&list中的元素调整到期望的目标位置。可以看到，你会有很多中选择。
第32条：如果确实需要删除元素，则需要在remove这一类算法之后调用erase。
1&2&3&99&5&99&7&8&9&99
调用remove(v.begin(),v.end(),99)；后变成
1&2&3&5&7&8&9&8&9&99
remove无法从迭代器推知对应的容器类型，所以就无法调用容器的成员函数erase，因此就无法真正删除元素。其他两个算法remove_if和&unique也类似。不过list::remove和list::unique会真正删除元素（比用erase-remove和erase-unique&更为高效），这是STL中一个不一致的地方。
第33条：对包含指针的容器使用remove这一类算法时要特别小心。
无论你如何处理那些存放动态分配的指针的容器，你总是可以这样来进行：或者调用remove类算法之前先手工删除指针并将它们置为空，或者通过引用计数的智能指针(&如boost::shared_ptr)，或者你自己发明的其他某项技术。
下面的代码利用第一种方式：
void&delAndNullifyUncertified(Widget*&&pWidget)
if(!pWidget-&isCertified())
pWidget&=&0;
for_each(v.begin(),v.end(),delAndNullifyUndertified);
v.erase(vemove(v.begin(),v.end(),static_cast&Widget*&(0)),v.end());
下面的的代码使用第二中方式：
template&typename&T&&//RSCP&=&"Reference&Counting&Smart&Pointer"
class&RCSP{...};
tpedef&RCSP&Widget&&RCSPW;
vector&RCSPW&&v;
v.push_back(RCSPW(new&Widget));
v.erase(remove_if(v.begin(),v.end(),not1(mem_fun(&Widget::isCertified))),v.end());
第34条：了解哪些算法要求使用排序的区间作为参数。
下面的代码要求排序的区间：
binary_search&lower_bound
upper_bound&equal_range
set_union&set_intersection
set_difference&set_symmetric_difference
merge&inplace_merge
下面的算法并不一定需要排序的区间：
unique&unique_copy
第35条：通过mismatch或lexicographical_compare实现简单的忽略大小写的字符串比较。
用mistatch实现：
//此函数判断两个字母是否相同，而忽略它们的大小写
int&ciCharCompare(char&c1,&char&c2)
int&lc1&=&tolower(static_cast&unsigned_char&(c1));
int&lc2&=&tolower(static_cast&unsigned_char&(c2));
if(lc1&&&lc2)&return&-1;
if(lc1&&&lc2)&return&1;
/*&此函数保证传递给ciStringCompareImpl的s1比s2短，如果s1和s2相同，返回0；如果s1比s2短，返回-1；如果s1比s2长，返回1。*/
int&ciStringCompare(const&string&&s1,&const&string&&s2)
if(s1.size()&&=&s2.size())&return&ciStringCompareImpl(s1,&s2);
else&return&&&ciStringCompareImpl(s2,&s1);&
//如果s1和s2相同，返回0；如果s1比s2短，返回-1；如果s1和s2都是在非结尾处发生不匹配，有开始不匹配的那个字符决定。
int&ciStringCompareImpl(const&string&&s1,&const&string&&c2)
typedef&pair&string::const_iterator,string::const_iterator&&PSCI;
PSCI&p&=&mismatch(s1.begin(),s1.end(),s2.begin(),not2(ptr_fun(ciCharCompare)));
if(p.first&==&s1.end()){
if(p.second&==&s2.end())&return&0;
else&return&-1;
return&ciCharCompair(*p.first,&*p.second);
用lexicographical_compare实现：
bool&ciCharLess(char&c1,&char&c2)
return&tolower(static_cast&unsigned&char&(c1))&&&tolower(static_cast&unsigned&char&(c2));
bool&ciStringCompare(const&string&&s1,const&string&&s2)
return&lexicographical_compare(s1.begin(),&s1.end(),&s2.begin(),&s2.end(),&ciCharLess);
第36条：理解copy_if算法的正确实现。
STL中没有copy_if的算法，下面是一个实现，但是不够完美：
template&typename&INputIterator,typename&OUtputIterator,tpename&Predicate&
OutputIterator&copy_if(INputIterator&begin,INputIterator&end,OutputIterator&destBegin,Predicate&p)
return&remove_copy_if(begin,end,destBegin,&not1(0));
copy_if(widgets.begin(),&widgets.end(),&ostream_iterator&Widget&(cerr,&"\n"),isDefective);//编译错误
因为not1不能被直接应用到一个函数指针上（见41条），函数指针必须先用ptr_fun进行转换。为了调用copy_if的这个实现，你传入的不仅是一个函数对象，而且还应该是一个可配接（adaptable）的函数对象。虽然这很容易做到，但是要想成为STL算法，它不能给客户这样的负担。
下面是copy_if的正确实现：
template&typename&INputIterator,typename&OUtputIterator,typename&Predicate&
OutputIterator&copy_if(INputIterator&begin,INputIterator&end,OutputIterator&destBegin,Predicate&p)
while(begin&!=&end){
if(p(*begin))&*destBegin++&=&*
return&destB
第37条：使用accumulate或者for_each进行区间统计。
确保accumulate的返回类西和初始值类型相同。for_each返回的是一个函数对象。accumulate不允许副作用而for_each允许。（这是一个深层次的问题，也是一个涉及STL核心的问题，待解）
第6章&函数子、函数子类、函数及其他
第38条：遵循按值传递的原则来设计函数子类。
在STL中，函数对象在函数之间来回传递的时候也是像函数指针那样按值传递的。因此，你的函数对象必须尽可能的小，否则拷贝的开销会很大；其次，函数对象必须是单态的，也就是说，它们不得使用虚函数。这是因为，如果参数的类型是基类类型，而实参是派生类对象，那么在传递过程中会产生剥离问题（slicing&problem）：在对象拷贝过程中，派生部分可能会被去掉，而仅保留了基类部分（见第3条）。
试图禁止多态的函数子同样也是不实际的。所以必须找到一种两全其美的办法，既允许函数对象可以很大并且／或保留多态性，又可以与STL所采用的按值传递函数子的习惯保持一致。这个办法就是：将所需要的数据和虚函数从函数子中分离出来，放到一个新的类中，然后在函数子中设一个指针，指向这个新类。
第39条：确保判别式是&纯函数&。
一个判别式（predicate）是一个返回值为bool类型的函数。一个纯函数（pure&function）是指返回值仅仅依赖于其参数的函数。
因为接受函数子的STL算法可能会先创建函数子对象的拷贝，然后使用这个拷贝，因此这一特性的直接反映就是判别式函数必须是纯函数。
template&typename&FwdIterator,typename&Predicata&
FwdIterator&remove_if(FwdIterator&begin,&FwdIterator&end,&Predicate&p)
begin&=&find_if(begin,&end,&p);//可能是p的拷贝
if(begin&==&end&return&
FwdIterator&next&=&
return&remove_copy_if(++next,&end,&begin,&p);//可能是p的另一个拷贝
第40条：若一个类是函数子，则应使它可配接。
4个标准的函数配接器(not1、not2、bind1st和bind2nd）都要求一些特殊的类型定义。提供了这些必要的类型定义（argument_type、first_argument_type、second_argument_type以及result_type）的函数对象被称为可配接的（adaptable）函数对象，反之，如果函数对象缺少这些类型定义，则称为不可配接的。可配接的函数对象能够与其他STL组件更为默契地协同工作。不过不同种类的函数子类所需要提供的类型定义也不尽相同，除非你要编写自定义的配接器，否则你并不需要知道有关这些类型定义的细节。这是因为，提供这些类型定义最简便的办法是让函数子从特定的基类继承，或者更准确的说，如果函数子类的operator()只有一个形参，那么它应该从&std::unary_function模板的一个实例继承；如果函数子类的operator()有两个形参，那么它应该从std::&binary_function继承。
对于unary_function，你必须指定函数子类operator()所带的参数的类型，以及返回类型；对于binary_function，你必须指定三个类型：operator()的第一个和第二个参数的类型，以及operator()的返回类型。以下是两个例子：
template&typename&T&
class&MeetsThreshold:&public&std::unary_function&Widget,&bool&&{
MeetsThreshold(const&T&&threshold);
bool&operator()(const&Widget&)&
struct&WidgetNameCompare:
public&std::binary_function&Widget,&Widget,&bool&&{
bool&operator()&(const&Widget&&lhs,&const&Widget&&rhs)&
你可能已经注意到MeetsThreshold是一个类，而WidgetNameCompare是一个结构。这是因为MeetsThreshold包含了状态信息（数据成员threshold），而类是封装状态信息的一种逻辑方式；与此相反，WidgetNameCompare并不包含状态信息，因而不需要任何私有成员。如果一个函数子的所有成员都是公有的，那么通常会将其声明为结构而不是类。究竟是选择结构还是类来定义函数子纯属个人编码风格，但是如果你正在改进自己的编码风格，并希望自己的风格更加专业一点的话，你就应该注意到，STL中所有无状态的函数子类（如less&T&、&plus&T&等）一般都定义成结构。
我们在看一下WidgetNameCompare：
struct&WidgetNameCompare:
public&std::binary_function&Widget,&Widget,&bool&&{
bool&operator()&(const&Widget&&lhs,&const&Widget&&rhs)&
虽然operator()的参数类型都是const&Widget&，但我们传递给binary_function的类型却是Widget。一般情况下，传递给unary_function或&binary_function的非指针类型需要去掉const和引用（&）部分（不要问其中的原因，如果你有兴趣，可以访问&boost.org，卡可能看他们在调用特性(traits)和函数对象配接器方面的工作）。
如果operator()带有指针参数，规则又有不同了。下面是WidgetNameCOmpare函数子的另一个版本，所不同的是，这次以Widget*指针作为参数：
struct&PtrWidgetNameCompare:
public&std::binary_function&const&Widget*,&const&Widget*,&bool&&{
bool&operator()&(const&Widget*&lhs,&const&Widget*&rhs)&
第41条：理解ptr_fun、mem_fun和mem_fun_ref的来由。
如果有一个函数f和一个对象x，现在希望在x上调用f，而我们在x的成员函数之外，那么为了执行这个调用，C＋＋提供了三种不同的语法：
f(x);&//语法#1：f是一个非成员函数
x.f();&//语法#2：f是一个成员函数，并且x是一个对象或一个对象引用
p-&f();&//语法#3：f是成员函数，并且p是一个指向对象x的指针
现在假设有个可用于测试Widget对象的函数：
void&test(Widget&&w);
另有一个存放Widget对象的容器：
vector&Widget&&
为了测试vw中的每一个Widget对象，自然可以用如下的方式来调用for_each：
for_each(vw.begin(),&vw.end(),&test);&//调用#1&(可以通过编译)
但是，加入test是Widget的成员函数，即Widget支持自测：
class&Widget{
void&test();
那么在理想情况下，应该也可以用for_each在vw中的每个对象上调用Widget::test成员函数：
for_each(vw.begin(),&vw.end(),&&Widget::test);//调用#2（不能通过编译）
实际上，如果真的很理想的话，那么对于一个存放Widget*&指针的容器，应该也可以通过for_each来调用Widget::test：
list&Widget*&&
for_each(lpw.begin(),&lpw.end(),&&Widget::test);//调用#3（也不能通过编译）
这是因为STL中一种和普遍的惯例：函数或函数对象在被调用的时候，总是使用非成员函数的语法形式（即#1）。
现在mem_fun和mem_fun_ref之所以必须存在已经很清楚了－－它们被用来调整（一般是#2和#3）成员函数，使之能够通过语法#1被调用。&mem_fun、mem_fun_ref的做法其实很简单，只要看一看其中任意一个函数的声明就清楚了。它们是真正的函数模板，针对它们所配接的成员函数的圆形的不同，有几种变化形式。我们来看其中一个声明，以便了解它是如何工作的：
template&typename&R,&typename&C&&//该mem_fun声明针对不带参数的非const成员函数，C是类，R是所指向的成员函数的返回类型
mem_fun_t&R,C&
mem_fun(R(C::*pmf)&());
mem_fun带一个指向某个成员函数的指针参数pmf，并且返回一个mem_fun_t类型的对象。mem_fun_t是一个函数子类，它拥有该成员函数的指针，并提供了operator()函数，在operator()中调用了通过参数传递进来的对象上的该成员函数。例如，请看下面一段代码：
list&Widget*&&
for_each(lpw.begin(),lpw.end(),mem_fun(&Widget::test));//现在可以通过编译了
for_each接受到一个类型为mem_fun_t的对象，该对象中保存了一个指向Widget::test的指针。对于lpw中的每一个&Widget*指针，for_each将会使用语法#1来调用mem_fun_t对象，然后，该对象立即用语法#3调用Widget*指针的&Widget::test()。
（ptr_fun是多余的吗？）mem_fun是针对成员函数的配接器，mem_fun_ref是针对对象容器的配接器。
第42条：确保less&T&与operator&具有相同的含义。
operator&不仅仅是less的默认实现方式，它也是程序员期望less所做的事情。让less不调用operator&而去坐别的事情，这会无端地违背程序员的意愿，这与&少&带给人惊奇的原则（the&principle&of&least&astonishment）完全背道而驰。这是很不好的，你应该尽量避免这样做。
如果你希望以一种特殊的方式来排序对象，那么最好创建一个特殊的函数子类，它的名字不能是less。
第7章&在程序中使用STL
第43条：算法调用优于手写的循环。
有三个理由：
效率：算法通常比程序员自己写的循环效率更高。STL实现者可以针对具体的容器对算法进行优化；几乎所有的STL算法都使用了复杂的计算机科学算法，有些科学算法非常复杂，并非一般的C＋＋程序员所能够到达。
正确性：自己写的循环比使用算法容易出错。比如迭代器可能会在插入元素后失效。
可维护性：使用算法的代码通常比手写循环的代码更加简介明了。算法的名称表明了它的功能，而for、while和do却不能，每一位专业的C＋＋程序员都应该知道每一个算法所做的事情，看到一个算法就可以知道这段代码的功能，而对于循环只能继续往下看具体的代码才能懂代码的意图。
第44条：容器的成员函数优先于同名的算法。
第一：成员函数往往速度快；第二，成员函数通常与容器（特别是关联容器）结合得更紧密（相等和等价的差别，比如对于关联容器，count只能使用相等测试）。
第45条：正确区分count、find、binary_search、lower_bound、upper_bound和equal_range。
想知道什么
使用算法使用成员函数未排序排序set或mapmultiset或multimap特定的值存在吗findbinary_searchcountfind特定值存在吗？如果有，第一个在哪findequal_rangefindfind或lower_bound第一个不超过特定值的对象在哪里find_iflower_boundlower_boundlower_bound第一个超过某个特定值的对象在哪里find_ifupper_boundupper_boundupper_bound具有特定值的对象有多少个countequal_range&(然后distance)countcount具有特定值的对象都在哪里find(反复调用)equal_rangeequal_rangeequal_range
第46条：考虑使用函数对象而不是函数指针作为STL算法的参数。
　　函数指针抑制了内联机制，而函数对象可以被编译器优化为内联。
　　另一个理由是，这样做有助于避免一些微妙的、语言本身的缺陷。在偶然的情况下，有些看似合理的代码会被编译器以一些合法但又含糊不清的理由而拒绝。例如，当一个函数模板的实例化名称并不完全等同于一个函数的名称时，就可能会出现这样的问题。下面是一个例子：
template&typename&FPType&
FPType&average(FPType&val1,&FPType&val2)//返回两个浮点的平均值
return&(val1&+&val2)&/&2;
template&typename&InputIter1,typename&InputIter2&
void&writeAverages(InputIter1&begin1,&INputIter1&end1,&InputIter2&begin2,ostream&&s)&//将两个序列的值按顺序对应取平均，然后写到一个流中
transform(begin1,&end1,&begin2,
ostream_iterator&typename&iterator_trais&InputIterl&::value_type(s,"\n")&,
average&typename&iterator_traits&InputIterl&::value_type&　//错误？
许多编译器接受这段代码，但是Ｃ＋＋标准却不认同这样的代码。原因在于，理论上存在另一个名为average的函数模板，它也只带一个类型参数。如果这样的话，表达式average&typename&iterator_traits&InputIterl&::value_type&就会有二义性，因为编译器无法分辨到底应该实例化哪一个模板。换成函数对象就可以了。
第47条：避免产生&直写型&（write-only）的代码。
　　代码被阅读的次数远远大于它被编写的次数。
第48条：总是包含（#include）正确的头文件。
几乎所有的标准STL容器都被声明在与之同名的头文件中。
除了４个STL算法外，其他所有的算法都被声明在&algorithm&中，这4个算法是accumulate、&inner_product、adjacent_difference和partial_sum，它们都被声明在头文件&numeric&&中。
特殊类型的迭代器，包括istream_iterator和istreambuf_iterator（见第29条），被声明在&iterator&中。
标准的函数子（比如less&T&）和函数子配接器（比如not1、bind2nd）被声明在头文件&functional&中。
第49条：学会分析与STL相关的编译器诊断信息。
　　用文本替换（例如用string替换掉basic_string&char,struct&std::char_traits&char&,class&std::allocator&char&&&）。
第50条：熟悉STL相关的Web站点。
站点：http://www.sig.com/tech/stl/
站点：http://stlport.org
站点：http://boost.org
阅读(...) 评论()