Hidden tmp Blog of Sandy - 文章

关于time_t

sandy_sp@163.com(sandy1) — Fri,20 Nov 2009 15:42:30 +0800

关于time_t

1. time_t用于表示一个绝对时间。其本质是一个unsigned int，保存的是自1970年1月1日0点0分0秒起所经过的秒数。

2.Unix中的世界末日：2038年1月19日,凌晨3点14分07秒。
嗯，因为32位字长的Unix，其unsigned int最多只能表示到2^32，于是从1970年1月1日0点0分0秒开始数够2^32秒后便到了头——这是Unix能表示的时间最大值。

3.__time32_t和__time64_t：由于2^32秒只能保存到2038年，因此你如果想让你的电脑在2039年还工作正常，你最好还是将保存时间的变量由32位扩充至64位。于是原来的time_t被搞成两种类型：__time32_t是老式的和Unix兼容的32位时间，__time64_t则是64位的时间。这样就可以保存到1970年以后的2^64秒的年月。不过鉴于我们还用不了那么遥远，于是windows下限定__time64_t最多表示到23:59:59, December 31, 3000。嗯，我想应该是够用了。

time_t会根据是否定义了_USE_32BIT_TIME_T宏来决定自己到底是到底是__time32_t还是__time64_t。
和TCHAR很像，两面派呵呵。

4.tm。鉴于time_t保存的秒数让大多数人使用困难（比如我给你345639你能说出是哪一年哪一月吗？），于是定义了一个tm类型来表示人能看懂的时间：

C++ 代码：

struct tm {
        int tm_sec;     /* seconds after the minute - [0,59] */
        int tm_min;     /* minutes after the hour - [0,59] */
        int tm_hour;    /* hours since midnight - [0,23] */
        int tm_mday;    /* day of the month - [1,31] */
        int tm_mon;     /* months since January - [0,11] */
        int tm_year;    /* years since 1900 */
        int tm_wday;    /* days since Sunday - [0,6] */
        int tm_yday;    /* days since January 1 - [0,365] */
        int tm_isdst;   /* daylight savings time flag */
        };

这个就把时间按照年月日时分秒分的很清楚了，人们使用起来就直观了。
关于最后一个字段tm_isdst解释下：这个是一个标志，表示是否启用夏令时。1表示启用，0表示不启用，国内一般不怎么用了。（你那里用夏令时吗？）

5.tm <---> time_t
提供了这么几个函数来达到二者的互相转换：


gmtime	将time_t转换成tm。传入一个time_t，传出一个tm。
localtime	将time_t转换成tm。不过这里假定time_t是一个UTC（世界标准时间），转换出来的tm是当地时间，已经经过了时区调整。（比如你在中国，是东8区，因此+8个小时）
mktime	将tm转换成time_t。传入一个tm，传出一个time_t。假定传入的是当地时间，会将其调整成UTC。（注意这时tm中的tm_wday和tm_yday两项会被忽略）
_mkgmtime*	将tm转换成time_t。不进行时区调整。不过此函数只有VC才带有，标准time.h中没有。

6.mktime的实现。
想想mktime干了些什么：将年月日时分秒换算成了自1970年1月1日以来的秒数。这其中有多少需要考虑的：年有闰年和非闰年之分，而一个月有31天的，还有30天的，还有28、29天的……真是复杂。
不过自有牛人来完成这个壮举：

C++ 代码：

static inline unsigned long mktime (unsigned int year, unsigned int mon,
    unsigned int day, unsigned int hour,
    unsigned int min, unsigned int sec)
        ...{
    if (0 >= (int) (mon -= 2)) ...{    /**//* 1..12 -> 11,12,1..10 */
         mon += 12;      /**//* Puts Feb last since it has leap day */
         year -= 1;
    }

    return (((
             (unsigned long) (year/4 - year/100 + year/400 + 367*mon/12 + day) +
             year*365 - 719499
          )*24 + hour /**//* now have hours */
       )*60 + min /**//* now have minutes */
    )*60 + sec; /**//* finally seconds */
}

这是Linux下的mktime实现，就在这么短短几行之内完成了如此复杂的换算。里面一些magic number估计都会让你眼花缭乱了。如果想仔细剖析这个代码的原理，请看这里：http://blog.csdn.net/axx1611/archive/2007/09/20/1792827.aspx

迭代器之入门介绍（下）

sandy_sp@163.com(sandy1) — Wed,28 Oct 2009 14:15:21 +0800

迭代器之入门介绍（下）

我们又见面了~~
或许之前的内容你觉得都比较简单，那么这次得有点心理准备，我打算讲稍微深入一些的东西。
而且可能也不会讲那么详细，或者说废话那么多了，点到为止，剩下的，你最好还是自己去查一查。

哎呀，没心理准备？
那就在此之前先聊个最简单的小玩意吧。

最简单的迭代器：指针

呵呵，是的没错，最简单的迭代器就是我们早已打交道n久老伙计——指针。语言的原生（native）指针。
不信？想想指针可以做啥：

可以指向一个内存区域中的位置。
可以通过++、--前后移动
可以通过*来访问其指向地方的数据。
可以用=赋值，可以用==、!=比较。

完全和我们（上）篇中介绍的迭代器的特性一样嘛！

事实上，如果你记得我之前说过的一句话：“迭代器就是对指针这个概念的抽象”，应该就明白了。迭代器在广义上说就是一种容器内元素的指针，现在语言原生指针何有不算迭代器之理？

再不信，你可以把指针传给STL那些需要迭代器的算法函数中，保证工作正常：

C++ 代码：

int arr[5]={5,3,9,-4,12};
int* begin=&arr[0];
int* end=&arr[4];

sort(begin,end);

这段代码会将这个数组排序……会非常顺利的通过编译，而且工作很正常。
现在信了吧？呵呵。
不过这里有一个小陷阱：虽然你发现之后的数组完全排序了，但是只不过是恰巧而已。事实上你只对数组的前4个元素排序了。为什么？想想你end指向的位置，再想想STL的区间是怎么一回事吧，呵呵。

其实可以写的更简单点：

C++ 代码：

int arr[5]={5,3,9,-4,12};

sort(arr,arr+5);

这样就可以对整个数组完全排序了。因为指针还支持相加运算，可以把一个指针+n来得到这个指针之后n个位置的地方。多么强大的功能，很多迭代器也不支持的。

是的，你之后就会看到，虽然指针是“最简单的迭代器”，但是它却属于迭代器分类中最强大的一种。

最后稍微透露你一个内幕消息：
嘿嘿，其实一些版本的STL中，vector的迭代器就是一个指针。只不过你一直在用vector::iterator这种写法而被蒙在鼓里而已，呵呵。不过你可千万别写：int *p= v.begin();这种代码啊，我都说了，只是有一些STL版本是这么干的，不保证其它版本也是用的指针啊。你如果实在无聊的话倒是可以测试一下，呵呵。

怎么样，“最简单的迭代器”，的确够简单吧！那么下面就来聊个更复杂的：

更复杂的迭代器：迭代器之配接器(Adapter)

配接器（Adapter，或者译为适配器），该怎么理解？
搞过DIY的朋友可能经常见到这个词汇，显卡适配器、网络适配器……
其实说白了，就是一个满足某一接口（或者说条件），而实际内容可以有所不同的一类东西。

还是有点晕？继续往下看：
在这里，接口或条件就值得是迭代器的各种行为。

于是我们的迭代器配接器就可以这么理解：
它是这么一类东西：提供和普通迭代器完全一样的操作——以至于我们使用的时候都感觉不到差别，但是他们做的事情却和普通迭代器有所不同。

好了具体点，说说STL中提供的三类Adapter吧：

反向（逆向，Reverse）迭代器
插入（安插，Insert）迭代器
流（Stream）迭代器

先别急着头晕，我慢慢来介绍。嗯，要收中介费。。

反向（逆向，Reverse）迭代器
顾名思义，这种特殊的迭代器提供一种逆向的访问——它是倒着走的。
它的++操作符是往前回退，而--操作符是往后移动，与正常的迭代器刚好相反。
除此之外，你使用这种迭代器和普通的迭代器并无二致。

为啥要搞这么一个迭代器出来呢？
比如我们想反向遍历一个容器，你用普通迭代器怎么写？

C++ 代码：

 for(Cont::iterator it=v.end();it!=v.begin();--it)
 {
     //... ?????!!
 }

这样写吗？
显然是错的。你也看出来了，你访问了不该访问的end位置，却没有访问本该访问的begin位置。

而有了逆向迭代器就很好办了：

C++ 代码：

for(Cont::reverse_iterator it=v.rbegin(); it!=v.rend(); ++it)
{
  //...
}

这样我们就可以逆向遍历了！和正向遍历的时候完全一样，只是把迭代器换成了逆向迭代器而已。

我知道你这时候想问一些东西了，不过还是先看我列的一张表吧：


reverse_iterator	类型，代表这个容器适用的逆向迭代器的类型。
const_reverse_iterator	类型，代表这个容器适用的常量逆向迭代器的类型。
rbegin()	成员函数，返回这个容器的逆向起始位置。（可以理解为最后一个元素的位置）
rend()	成员函数，返回这个容器的逆向结束位置。（可以理解为第一个元素之前的位置）

这是STL中所有标准容器提供的成员，你可通过它们来方便的使用逆向迭代器。

如何？还有问题吗？

介绍下一位：

插入（安插，Insert）迭代器

还记得我在（中）篇里面最开始介绍的那个错误的例子吗？
不记得了？好吧，我做一次搬运工。。就是这段代码啦：

C++ 代码：

vector v;
//... 然后向v里面添加了些数据

list li;
copy(v.begin(),v.end(),li.begin());

当时我说了这个有严重的问题。list可能没有足够的空间，需要事先resize一下。
但是我那时候也说了，上述方法不够优雅。优雅的做法是：将copy默认进行的拷贝操作变成插入操作。
当时卖了个关子，没说具体方法。现在想必你也猜到了：对，就是使用这个配接器。

insert iterator，插入型迭代器，又称inserter（插入器），就是这么一个配接器：它将普通迭代器的赋值操作变成插入操作。
来看看上面的那个例子如何优雅的解决：

C++ 代码：

vector v;
//... 然后向v里面添加了些数据

list li;
copy(v.begin(),v.end(),back_inserter(li));

这样，这个copy算法默认的赋值操作就被适配（Adapt）成了一个插入操作：插入型迭代器将调用list的push_back()方法来将数据一个个插入到容器尾部。

你看到back_inserter这个名字，想必也猜出来了：对，插入迭代器有三种类型，分别使用三个函数来创建：


back_inserter(container)	返回尾部插入型迭代器，内部会调用容器container的push_back()方法来将数据插入容器的尾部
front_inserter(container)	返回头部插入型迭代器，内部会调用容器container的push_front()方法来将数据插入容器的头部
inserter(container,pos)	返回通用插入型迭代器，内部会调用容器container的insert(pos)方法将数据插入到pos位置。

不过这里要清楚，不是所有的容器都可以适用上述三种方法来创建插入型迭代器的。事实上vector不能创建front inserter，map和set不能创建back inserter 和front inserter ——对，你猜出来了：
如果容器没有push_back()方法，那你就不能创建back inserter，不然这些配接器内部怎么调用那些函数？其它插入迭代器也是一样。
对于通用型插入迭代器，由于所有标准容器都提供了insert方法，因此所有标准容器都可以创建。不过效率未必很高——取决于容器的insert方法的效率。

最后一位出场：

流（Stream）迭代器

这个配接器有点诡异，他事实上可以为一个流（stream）创建一个迭代器从而实现对流的读取或写入。
个人感觉，这玩意的用处不是特别大，主要是用于将各种流适配到STL的那些针对迭代器的算法上。
有些时候还是非常好玩的。
最常见的流就是标准输入输出流了：
istream_iterator(cin);
这一句，创建了一个输入流迭代器，可以从cin中读取整数（int）。

最后给出一个经典的例子，也是很多书上被拿来展现STL强大之处的一个例子：

三句话实现从屏幕中输入单词，按字母顺序排序，剔除重复单词后，输出到屏幕上。

嘿嘿，先想想如果你用C写的话得写多少代码……

那么来看看在C++中如何写：

C++ 代码：

vector v1((istream_iterator(cin)),(istream_iterator()));
sort(v1.begin(),v1.end());
unique_copy(v1.begin(),v1.end(),ostream_iterator(cout," "));

用STL实现就这么一点，恰三行代码。
来稍微解释下：
第一句定义了一个vector v1，并且在构造函数中传入两个输入流迭代器，这两个迭代器构成一个区间，表示输入的所有单词，直到输入终止（EOF）。这样v1就在创建的时候里面填满了输入的各个单词。

第二句，使用sort对这个vector里面的元素进行排序。是的，不需要你写复杂的字符串比较函数，string内部带有operator < 的定义。而sort，只需要一个小于号即可运作。排序完毕后，所有单词就按照字母顺序从小到大整齐排列了。

第三句，使用unique_copy来将v1中的数据拷贝到目标区间。unique_copy和copy的不同之处就在于，它可以将连续的n个相同元素剔除掉其中的n-1个，只留下一个元素，从而实现unique的功能。这次拷贝的目标区间的起始又是流迭代器——这次是输出流迭代器，它将算法给它的数据输出到cout中，于是就显示在屏幕上了。

很神奇，很强大吧。我觉得用这个例子来作为迭代器配接器介绍的结尾，挺好的。

ok，STL中的三大迭代器配接器已经粗略介绍完了。其实它们每一个都有很多细节，如果你想自如的使用的话，可能需要额外研究。鉴于你没有付我介绍费（^_^），这里就只做一些简单的介绍啦，剩下的自己去研究吧。

迭代器的分类(Category)

好吧，其实我觉得用了这么久如果你还没感觉到迭代器有几个明显的类别，这是一个悲剧。。
而我将迭代器的分类放在这么靠后的位置介绍，恐怕又是一个悲剧。。

还是老办法，先从一段代码开始吧，一段非常非常简单的代码：

C++ 代码：

list li;
// ...然后在这里像li中添加了一些数据
sort(li.begin(),li.end());

你心想这下这段代码肯定悲剧了，既然被揪出来就是要拿来批斗的。。嘿嘿。
可是貌似真没啥问题啊，我不过就是想对list排个序么。有啥不对的。。？
如果你还抱有这种想法，不妨编译一下，看看编译器是怎么说的。。

编译器会上书几百行错误来向你抱怨写出了如此代码。

如果你实在看不出这个代码中有何问题，那么你不妨把list换成vector、deque、map、set甚至string等等，一个个试下，看看编译器会不会都抱怨……

而你会发现这些被抱怨的容器在另外一些算法上却不会遭到抱怨，比如find、copy、transform……

而如果你非常细心的话，又会发现，有些迭代器可以做加减法，有些不可以；有些可以比较大小，有些不可以……

而如果你是既细心又严谨的模范的话，或许某天你会发现，同样的算法，比如distance，在有些迭代器上会很快，有些迭代器上会很慢……

哦哦哦，说到这里，或许你已经大概可能似乎有那么一点点感觉了：迭代器是不一样的。有某种分类。

是的。在STL中，迭代器的确是有明确的分类，同一类的迭代器有着相同的特性和相似的用法。而且迭代器的类别之间有着一定的关系。

在STL中，迭代器分为这么几个类别：

我想这张图片已经很能说明问题了。是的，有五种迭代器，从上往下分别是：
input iterator，输入迭代器
output iterator，输出迭代器
forward iterator，前向迭代器
bidirectional iteraotr，双向迭代器
random access iterator，随机存取迭代器

在图上从上往下，它们有一个继承关系（用箭头来表示）：下层的迭代器继承了上层迭代器的能力，因此越下面的迭代器功能越强。（注意：这里的继承不是指OOP中类的继承关系，事实上不同迭代器的类型完全不同，根本无法用类继承来实现。这里的继承仅仅是概念上的功能继承，在C++0x中就可以表示为Concept的继承关系了）

●output iterator，顾名思义，可以向这个迭代器中写入数据。可以++，可以向后挪动位置。
●input iterator，也顾名思义，可以从这个迭代器中读取数据。可以++，可以向后挪动位置。两个此类迭代器之间可以比较是否相等。
这俩迭代器的“读取、写入”功能是所有迭代器的基础。
●forward迭代器，是上述俩迭代器的功能的集大成者，可以读取可以写入（理论上如此，当然实际上还看你是否const）。这是一个具有完整读写功能的向前走的迭代器。
●bidirectional迭代器，更加顾名思义了，在forward迭代器的基础上增加了-- 操作，还可以向前回退位置了。
●random access iterator迭代器，嗯，不用我说了吧。可以随机存取访问。也就是说可以任意跳转。它支持算数运算，也就是operator +、operator -，可以直接从当前位置跳转到之后n个位置或者之前m个位置，而且还支持比较运算符（operator <等），两个迭代器位置之间可以比较大小，看谁在前谁在后。

嗯，你已经发现了，output iterator 到 forward iterator之间为啥是虚箭头啊？呵呵，挺眼尖的。其实这是因为一个细节：forward iterator没有完全继承output iterator的所有功能，只是继承了大部分功能而已。具体细节这里暂不讨论，如果你实在有兴趣的话，可以找找专门的资料看看。

再回头看看上面那个代码的问题，或许你应该猜到了：
是的，list上的迭代器是双向迭代器，而sort算法要求的迭代器却是随机存储迭代器。这样就导致了编译错误。不过由于C++的模版机制的一些不完善性（这其实也怨不得C++，当初所有设计者都想不到之后模版技术居然能被使用的淋漓尽致到这个地步吧……），导致编译器对这种错误极其感冒：一错就错出几百个喷嚏出来。而你在这些四溅的喷嚏飞沫中估计很难找到病原体……只有有经验的医师可以从它打喷嚏的动作猜出可能是啥原因。。
（不过在C++0x中将Concept引入了语法层面，就可以解决这个问题，那时候编译器就会简单的报一句：迭代器类型不对，而不是像现在一样打几百个喷嚏。不过这是额外的话题了，这次不谈）

在STL的标准容器中，所有容器的迭代器都至少提供了双向迭代器的功能。
其中vector、deque的迭代器更进一步——他们是随机存取迭代器。

而我这篇最开始讲的，C++语言原生支持的指针，虽然是最简单的迭代器，但是却最强大的一种——这里你也就明白了，是的，原生指针属于最强大的随机存取迭代器。

之前介绍的那些迭代器配接器，在这里也稍微提下：
reverse iterator：取决于你这个容器本身的迭代器是什么类型。但是至少是bidirectional的（不然我怎么逆向啊？）
insert iterator：属于output iterator；
istream iterator：属于input iterator；
ostream iterator：属于output iterator。
你可以自己对比下这些配接器的功能，就会明白他们为啥归类于这些了。

哎？可是开头的问题还没解决：我如何对一个list排序？
嗯，其实对于这种特殊的无法提供通用算法的容器，只好特殊定制排序算法了。
不过不用担心，不用你来写，大师们已经替你写好了：list本身就有一个成员函数sort()来进行排序。
因此，那个代码这样改就ok啦：

C++ 代码：

list li;
// ...然后在这里像li中添加了一些数据
li.sort(); //使用成员函数来进行排序

哦……那我要对map排序也就可以调用map::sort()了？——罚你做100个俯卧撑……算了俯卧撑比较危险还是改练叉腰肌算了……
呃，为啥罚你？map是什么容器？关联式容器——根本无需也不能排序。这种容器内部的元素一经插入，就已经处于有序状态！

好了，先说这么多，我该睡了~~

之后再慢慢补充吧。

假设你还是上面的那个细心而又严谨的你，那么你可能还记得在distance()这种算法中，除了output迭代器，其它类型的迭代器都可以适用，但是效率却有所差别。。这又是怎么一回事呢？

不熟悉distance()的同学，就顺便在这里介绍一下：distance(it1,it2)返回两个迭代器的距离。其实也就是区间[it1,it2)的长度。

显然，对于input、forward和bidirectional迭代器，我们只好一步步往后走同时计数，直到走到终点，看下计数器走了多少步，于是就知道了这俩迭代器的距离。时间复杂度O(n)。
但是对于random access iterator，显然再这么做就太傻B了，既然可以随机访问，我直接相减就可以立即求出二者的距离啊，时间复杂度只要O(1)。

假如你是distance()算法的作者，你会怎么写？
到底用上述哪种方法来实现求距离呢？前一种？不错，这样可以适用于多种迭代器，通用性挺好。可惜对于随机存储迭代器，太浪费时间了。后一种？很好，随机存储迭代器可以非常快的求出距离，但是你却让其它迭代器彻底与你的算法无缘了。

怎么办啊啊啊啊？？难道这就是传说中的鱼与熊掌不可得兼？

——谁说的！我明明一边吃着烤鱼一边看着熊掌（在动物园里）……
STL提供的distance就是这么神奇：一方面保证了通用性，另一方面又保证了针对特殊的迭代器，提供最好的效率。

它是怎么实现的呢？对了，你肯定猜到了它的第一步——首先得通过某种方式来识别迭代器的类型。这样才能针对不同的类型来写不同的算法。

类型萃取

是的，就是这个听起来很玄乎的技术——类型萃取技术，或者称为特征（Traits）获取技术。
很神奇的一个技术，你会见识到一些比较高级的模版技巧。

事先提个醒，这里可能有点深，你得需要事先了解模版的偏特化等一些特性，才能比较好的理解这里的内容。

好了我们开始尝试实现这个鱼+熊掌版的distance。
为了能够知道迭代器的类型，我们首先想到了一个办法，那就是和容器一样，要求所有迭代器都遵循一种约定——在迭代器中加入一个枚举变量作为类型标识：

C++ 代码：

enum IteratorType
{
  input_iterator_type,
  output_iterator_type,
  forward_iterator_type,
  bidirectional_iterator_type,
  random_access_iterator_type
};

struct XXXIterator
{
  IteratorType type; //定义一个枚举来保存当前迭代器的类型信息，我们便可通过这个变量来知道它的类型
  //...其它内容
};

嗯……如果是Java这些动态性比较强的语言这么做也就罢了。。可是C++明明是一个强静态语言，编译器在编译代码时知道的信息很多，这样许多东西完全可以在编译期解决——从而完全不耗费运行时的资源。
特别是模版技术的引入，让我们拥有了能够在编译期完成某些事情的能力。

于是我们再想想，能不能不用上面那种需要运行时判断的方法，把这些工作全部在编译期完成。试着这么尝试下吧：
假设我们先定义这么几个类：

C++ 代码：

struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag{};
struct bidirectional_iterator_tag{};
struct random_access_iterator_tag{};

定义这么多struct干嘛？而且都是空的？有什么用吗？
嘿嘿，这就是我们利用C++强大的类型系统的第一步：将信息类型化。
不太明白？不要紧，接着往下看：
这样我在迭代器的类里面，就可以这么写啦：

C++ 代码：

XXXIterator
{
  typedef  forward_iterator_tag  iterator_category;
  //...其它内容
};

这样，我们就成功的将之前的那个枚举变量type变成了一个静态的类型iterator_category——你只需查看这个iterator_category到底是哪个类型（它是我们上面定义的那五个空struct类型之一）——你就可以知道这个iterator是什么类别！

你或许会问，这个和一个枚举变量相比有什么好处？
呵呵，好处大大地：首先，枚举变量会占用空间，而这个iterator_category只是一个typedef，换句话说只是一个类型定义，完全不占空间；其次，类型信息是在编译期就可以被确定的，因此编译器可以利用这些信息在编译阶段就完成这些识别和分类工作，这样完全不会耗费运行时的时间来做判断（后面你会看到）；再下来就是这个理由：使用类型，便可以清晰的表示迭代器类别之间的继承关系——我们将上面那一堆struct的定义稍微改一下，加点料：

C++ 代码：

struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag:public input_iterator_tag{};
struct bidirectional_iterator_tag:public forward_iterator_tag{};
struct random_access_iterator_tag:public bidirectional_iterator_tag{};

看见了没有？这样这些单纯用来表示类别差异的空struct或class（我们称之为tag类——因为他们就像blog文章中的tag一样，没别的用途，仅用于给别的类标识类型），现在有了明确的继承关系：random_access_iterator_tag继承自bidirectional_iterator_tag，bidirectional_iterator_tag继承自forward_iterator_tag……是不是和之前介绍的迭代器类别那里的图上的关系一样？没错，就是用这种方法，表示了类别的继承特性。（同时你也可以注意到forward_iterator_tag并没有继承自output_iterator_tag，呵呵）

好了，我们这样便可以在一个迭代器中定义一个typedef来标明它所属的迭代器类别了！但是如何识别呢？
if(XXXIterator::iterator_category ==input_iterator_tag)
这样写吗？
显然是错的。类型之间不能用==比较。其实你要换思路：我们根本就不该用if语句——if语句是运行时执行的，而我们要做的是让它在编译期就决定谁是谁，谁该调用谁。
想想吧，C++有什么东西可以在编译期间根据一个类型的不同来决定不同的行为呢？
没错！函数重载！

C++ 代码：

void func(int a); //#1
void func(const char*b); //#2
//...
func(1);  //这里便可根据参数的不同类型来选择#1或#2不同的版本。
func("a");

我们可以构造一个tag类的变量，然后作为参数传入，便可以利用函数重载来自动绑定到不同的行为了！
来看看distance（可能）是怎么做的吧：

C++ 代码：

//先写出distance的两种不同版本的算法：#1和#2

//#1. 这是针对普通迭代器的通用版本
template
size_t distance(Iterator it1, Iterator it2, input_iterator_tag tag) //注意最后一个参数
{
  size_t d=0;
  for( ; it1!=it2; ++it1) //通过循环计数得到距离
  {
    ++d;
  }
  return d;
}

//#2. 这是针对随机存取迭代器的特殊版本
template
size_t distance(Iterator it1, Iterator it2, random_access_iterator_tag tag) //注意最后一个参数
{
  return it2 - it1; //直接相减得到距离
}

//#3. 这个才是我们平常调用的那个只有俩参数的distance
template
inline size_t distance(Iterator it1, Iterator it2)
{
  return distance(it1, it2, Iterator::iterator_category()); //这里，传入一个tag对象，便进行了函数重载
}

aha！太巧妙了！
（如果你没有喊出“aha！”而是喊出了“huh？”，那么请往下看，并在看完下面几段之后再回头仔细看一遍上面的代码）

我们这次人肉运行一下试试：
●第一次人肉运行：
我有两个输入型迭代器（假设类型名叫InputIterator）：it1和it2，我想调用distance求他们的距离，于是我这样写：
distance(it1,it2);
然后发生了什么？编译器一看，俩参数的，于是，调用了上面代码中的#3，并自动推导出模版中的Iterator就是InputIterator。
接下来进入函数，函数内部直接调用了另外一个仨参数的distance，于是编译器开始检查这三个参数。前两个都没啥变化，最后一个多出来的那个参数是什么呢？
编译器一看，Iterator::iterator_category()，哦，原来是构造了一个对象，这个对象是Iterator内部的iterator_category类型啊——那到底是什么类型？
再翻一翻户口簿，记录着：Iterator在这里就是InputIterator，而InputIterator内部有一个：
typedef input_iterator_tag iterator_category;
于是编译器明白了，这个Iterator::iterator_category到头来原来是input_iterator_tag这个类啊。
接下来编译器就好办了：找有没有哪个函数名叫distance，有三个参数，其中第三个参数是input_iterator_tag类型的？哦，有，#1不就是一个吗？于是编译器就决定调用它啦。
这样我们最终就进入了#1的函数内部，然后使用了普通的那种走一步记一步的方式计算出了it1和it2的距离。

●第二次人肉运行：
我有两个前向迭代器（假设类型名叫FowardIterator）：it1和it2，我想调用distance求他们的距离，我还是这样写：
distance(it1,it2);
编译器照样照样找到了#3，调进去一看，还是一样，要找三个参数的函数。不过这次经过查户口，这个FowardIterator里的iterator_category是foward_iterator_tag类型的。编译器大略搜了一下，没发现第三个参数是foward_iterator_tag类型的函数啊，这可咋办捏？又查了查，哦，原来foward_iterator_tag是继承自input_iterator_tag嘛，它俩差不多算一类，就当作input_iterator_tag 处理吧！于是调用了#1，之后就和第一次人肉运行后面的情况一样啦。

●第二点五次人肉运行：
我有两个双向迭代器要求距离……呃呃，鉴于和第二次人肉运行差不多，就不人肉了吧。。

●第三次人肉运行：
这次我拿了俩随机存取迭代器过来了（假设类型名叫RAIterator）：it1, it2。还是想通过distance求距离：
distance(it1,it2);
这次你作为编译器（啊？我啥时候开始人肉编译了？），应该驾轻就熟了，直接找到#3，然后找里面那个函数的第三个参数。这次查户口，发现RAIterator里的iterator_category是random_access_iterator_tag，接着去搜函数，哎呦，正好有一个嘛：#2不就是一个名叫distance并且第三个参数要random_access_iterator_tag类的函数嘛。就是他了，去吧年轻人~~~！
于是我们第三次就用上了it2-it1这种高效的算法。

怎么样？“aha！”了没有？还没有的话再回头去仔细看看代码~~

啊，太帅了，不愧是巧妙的类型萃取技术啊……
别忙！这还不算是类型萃取呢，才是第一步。（啊？？搞错没有？！才第一步？）

是啊。虽然目前我们的这种方法工作很好，但是你想想，还有一类最常见最简单的迭代器被我们遗忘了呢——噢……难道是它……
没错，就是它——最简单却最强大的迭代器，指针。上述算法对指针一点用都没有。

为啥没有用？你想想，我们这个方法要区分类型，必须依靠迭代器内部的那个iterator_category类型。自定义的迭代器倒好办，标准一声令下，所有人都得遵守。但是指针你怎么办？你如何给指针加一个iterator_category类型？这下没辙了。。

嘿嘿，有时候你不得不承认有些人不愧是大师，来看看他们拿出的解决方案——类型萃取：

对，到这里才是真正类型萃取的主体，之前的都是前戏~~呵呵。
大师们定义了这么一个东西：

C++ 代码：

template 
struct iterator_traits
{
  typedef typename T::value_type  value_type;  //萃取值的类型
  typedef typename T::reference  reference_type; //萃取引用的类型
  typedef typename T::difference_type  difference_type; //萃取距离的类型
  typedef typename T::pointer  pointer;  //萃取指针的类型
  typedef typename T::iterator_category  iterator_category;//萃取迭代器特征(分类)
};

这个名叫iterator_traits的神奇的struct，你可以称之为迭代器类型萃取器，它可以像化学实验中的那些检测器一样把每个迭代器的各种特征全部检测出来。

于是便可以获取各种迭代器的特征了！
哎，等等——这不过是多了一个typedef而已，有什么用吗？对指针貌似还是没有用啊！

哦，忘了忘了，抱歉，其实上述的iterator_traits仍然是个不完整的，还没有给你们看traits真正强大的一面呢：
iterator_traits强就强在，它可以利用模版特化，为指针单独定制一个版本的萃取器！

C++ 代码：

template 
struct iterator_traits
{
  typedef typename T   value_type;  //萃取值的类型：就是T 
  typedef typename T&   reference_type; //萃取引用的类型：就是T&
  typedef typename ptrdiff_t   difference_type; //萃取距离的类型：就是ptrdiff_t
  typedef typename T*   pointer;  //萃取指针的类型：就是T*
  typedef typename random_access_iterator_tag  iterator_category;//萃取指针迭代器特征(分类)：就是随机存取迭代器tag
};

看到没有？模版特化在此处体现了它的强大：假如是指针类型，就会被自动特化成这个版本——而这个版本为指针定义好了各种特性，包括迭代器的类型是随机存取迭代器——因此就轻而易举的获取了指针这种最简单的迭代器的各种特征！

回到之前那个distance的例子：
有了这个iterator_traits，我们就可以将上面的distance代码#3处这么改进：

C++ 代码：

template
inline size_t distance(Iterator it1, Iterator it2)
{
  return distance(it1, it2, iterator_traits::iterator_category()); //使用Traits来获取迭代器的tag
}

还是#3的代码，这次使用iterator_traits来获取iterator_category，如果这个Iterator是一个复杂的迭代器，那么就和之前没有区别；如果这个Iterator是一个简单的指针，那么就会被特化为random_access_iterator_tag，从而一举解决所有的问题！哈哈，爽吧。

这就是类型萃取的魅力所在。

ok，关于它的内容就介绍到这里。如果你还没有看的很懂的话，建议先去温习下函数重载和模版特化的相关知识，然后再回头把这一小节重新仔细看一遍。

另外再做个说明：上述的distance代码有很多不严谨之处，比如返回值不应该简单的写size_t类型，而也应该使用traits来获取当前迭代器的距离类型（difference_type）。但是因为本小节只是为了给大家介绍一下类型萃取技术的原理，因此将这些东西都做了简化以方便阅读。

针对迭代器编程

还记得在（上）篇中我们最后的那个小小的遗憾么？我们想写一个迭代器版的findMin，可是因为无法得知迭代器指向的数据类型而只好作罢。

现在有了类型萃取技术，利用iterator_traits，问题就迎刃而解啦：

C++ 代码：

template
iterator_traits::value_type  findMin(Iterator begin,Iterator end)
{
  iterator_traits::value_type tmp;  // now it works!!
  for(Iterator it=begin;it!=end;++it)
  {
    if(tmp>(*it)){tmp=(*it);}
  }
  return tmp;
}

通过简单的使用iterator_traits，我们便可以从迭代器的类型中萃取出更多的信息：比如这次萃取出了迭代器指向位置的元素的类型。

所以说，类型萃取技术，是针对迭代器编程的基础。STL里面大量的算法都使用了这个技术。如果你想针对迭代器编程，那么你也就好好利用这一利器吧！

就像上面iterator_traits定义的那样，迭代器有五种特征。虽然上面的定义已经写明了，不过为了清楚，还是在这里专门列一下吧：


value_type	这个迭代器指向的元素的类型
reference_type	这个迭代器指向的元素的引用类型
difference_type	两个此类迭代器之间的距离的类型
pointer	这个迭代器指向的元素的指针类型
iterator_category	这个迭代器迭代器的特征(分类)

来一个自己的迭代器怎么样？

嗯，这次介绍了这么多内容，终于把整个《迭代器入门介绍》系列差不多讲完了。如果你看到这里，并且把之前的内容差不多都搞懂的话，我想其实也就差不多理解了一点GP以及STL中针对迭代器编程的思想了吧。

就像最开始说的，STL是一个开放的框架，你可以在遵循一些Concept的前提下扩展这个框架，写自己的算法，写自己的容器，使它们与现有的STL成员良好的协调工作。真是一件美妙的事情啊，不是么？

看了上一小节“针对迭代器编程”，你或许已经大略知道如何为STL扩展算法了。

现在貌似还差如何写一个自己的、可以被STL算法所用的迭代器？

呵呵，那我就在本文的最后，告诉你一个简便的方法吧。

其实STL的最初设计者们就考虑到了之后的扩展性，专门为后人提供了一个类，就叫做：iterator。

你可以通过继承这个类，来实现各种各样的迭代器：

C++ 代码：

//我来定义一个指向int型元素的双向迭代器吧~
class MyIterator : public std::iterator
{
  MyIterator();
  MyIterator(const MyIterator& val);
  ~MyIterator();
  MyIterator& operator++();
  MyIterator& operator--();
  MyIterator& operator++(int);
  MyIterator& operator--(int);
  MyIterator& operator =(const MyIterator& val);
  bool operator ==(const MyIterator& val) const ;
  //...你可以继续加……呵呵
}

就像上面的例子，通过iterator后面的模版参数就可以指定你要实现的迭代器的类型和其指向元素的类型。

呵呵，很简单吧。手痒了？那就自己来一个试试吧！

嘘~~~~~~~~~ 极其长的迭代器介绍废话，终于被我唠叨完了。介绍系列就到此为止吧~！
还有很多细节没有讲到，就靠大家自己去学习了。我么，还是偷偷懒算了~~（砖~！）

嗯……砖也行啊，还是那句话：如果觉得写的好请顶一下，如果觉得写的搓也请拍一下啊。

到此为止，闪也~

迭代器之入门介绍（中）

sandy_sp@163.com(sandy1) — Thu,22 Oct 2009 22:54:53 +0800

占位置。。

迭代器的使用

这次，我们继续聊迭代器的使用。
不过这次，还是老规矩（啥时成规矩了？）先从STL聊起吧。
STL处处是以效率优先的。
也就是说，只要使用得当，STL绝对足够快，如果你的程序使用STL很慢，先考虑考虑是不是自己的代码的问题或者是不是误用了STL。因为在大多数情况下，你手写的算法是比不过诸如Stepanov和Plauger这些世界级大师的水准的。
不过其实我真正想说的是这句：STL竭尽所能给你提供最高的效率，因此他假定你是一个高素质的程序员。
什么意思？
更直白点说，STL假定你不会犯一些（它认为的）低级错误，它认为你给它的东西都是完全没有隐患的，它可以不加验证放心使用，总之，它信任了你。
因此你要对得起这种信任。
你心想这算什么话，我没事给它一个有问题的数据干吗？

呵呵，来看看下面的代码吧：

C++ 代码：

vector v;
//... 然后向v里面添加了些数据

list li;
copy(v.begin(),v.end(),li.begin());

你在想，STL的确方便啊，迭代器的确大显神威啊，一个copy就可以将数据从一个容器中拷贝到另外一个结构完全不相同、数据类型也完全不相同的容器中，太好用了。
且慢，不妨运行下试试。
什么？运行了一切ok？那算你走……，不，算你倒霉。
上面那段代码中有非常严重的问题，如果你RP好的话会立刻导致你的程序崩掉，这样你还可以知道你写错了。但是很不幸，你的RP没有那么高——这次没有崩。于是你还以为你的程序一切ok，哼着小曲将它交给用户，直到有一天崩溃终于来临，你就要被客户死缠烂打了……——这还算好的，问题是你回去之后在代码的海洋中寻找问题的时候，可能根本就记不起到底是什么地方的问题导致你的程序挂掉了。

扯远了。。回到上面的代码。仔细看一看。。哦。。。原来如此。
对的。
copy这个函数执行的是拷贝操作，将源区间中的内容拷贝到目标区间。关键就在于它的参数：它有三个参数，前两个是源区间的起始和末尾，最后一个是目标区间的起始——注意，没有目标区间的末尾。那它怎么知道目标区间有多大呢？显然，copy知道源区间有多大，因此它当然可以猜出来要拷贝到的目标区间至少有多大。
问题就在这里出现了：它猜的不一定是对的。像上面的例子，那个li明明还是一个空容器，显然长度无法容纳要拷贝的数据，但是copy不知道。依然老老实实的执行着拷贝，于是便会导致不可预料的结果。

你心说，这个copy真笨，不会看看目标容器空间够不够啊？但是这怨得着copy吗？copy根本不知道目标容器啊，它只知道一个目标迭代器。
那你又说了，copy为啥不传四个参数，把目标区间的起始和末尾都传进去，这样它就能知道目标区间够不够大了。好吧，想想我最开始说的话：“STL竭尽所能给你提供最高的效率，因此他假定你是一个高素质的程序员”是的，为了检测区间够不够大会耗费额外时间，而这本身是应该由你来保证的。

其实这个问题，很容易解决：事先为那个list留够足够的空间不就可以了吗？只要li.resize(n);这么一下，li这个容器中就有n个空位了，再拷贝就ok啦。
不过上面的方法还不是很优雅，一来n必须得足够大，不然仍然可能出现区间长度不够的问题，二来resize(n)相当于一次性创建并初始化了n个元素，这些元素还没来得及使用就被copy覆盖了，浪费啊。
其实有个很简单且很方便的办法，让这个问题更优雅的解决。那就是将copy默认进行的拷贝操作变成插入操作。插入和拷贝是有本质的差别的，只要内存足够，插入操作便永远不会出问题。那如何变呢？呵呵，再卖个关子（我拍~），后面讲。

我们从STL谈起，谈到了在使用迭代器时的一些问题。是的，这段我就是打算谈一些很小的不起眼的问题——这些问题有时候出现的频率很高。

区间的有效性

来看看这代码有啥问题：

C++ 代码：

vector cont1;
deque cont2;
//... 在这里给cont1和cont2添加一些东西
sort(cont1.begin(),cont2.end());

很显然，这样使用sort并不能帮你把cont1和cont2都排序，事实上会导致编译错误。
更隐蔽一点：

C++ 代码：

vector cont1,cont2;
//... 在这里给cont1和cont2添加一些东西
sort(cont1.begin(),cont2.end());

这段代码会很顺利的通过编译，但是会导致未定义行为：你的程序可能完蛋，也可能啥事没有，取决于你的RP -_-
是的，你必须保证前后两个参数都是同一个容器上的迭代器。
你或许会说，谁会犯这么弱智的错误啊？是的，这个例子不是很好，或许只是不小心把cont1打错成cont2而已，但是假如复杂一点的情况，说不定就很容易犯错了：

C++ 代码：

vector cont1,cont2;
vector::iterator it1,it2;
//假设接下来对it1和it2做了许多操作，写了很复杂的分支等语句.

sort(it1,it2);//到这里你恐怕就不容易看出来it1和it2到底谁是哪个容器上的了。

要构成一个有效的区间，必须首先保证区间起始和末尾的迭代器都是同一个容器上的。
如果说上面这种保证还是比较容易的话，那么下面这个恐怕就不那么容易了：
同时你还得保证区间起始的迭代器位置不能在区间末尾的迭代器的后面。
也就是说，区间[begin,end)，begin的位置要么在end前面，要么和end在同一位置，总之绝对不能跑到end后面去。
你心里嘀咕，这个天经地义啊，谁都会保证的。
未必。
看看这段代码有啥问题：

C++ 代码：

list li;
for(int i=20;i<=50;++i)  //给li中插入20~50
{
  li.push_back(i); 
}
list::iterator it1,it2;
it1=find(li.begin(),li.end(),30); //在li中寻找30的位置
it2=find(li.begin(),li.end(),40); //在li中寻找40的位置

reverse(it1,it2);//反转[it1,it2)这个区间中的元素

看起来很不错的代码啊，先使用find找到30和40的位置，然后调用reverse将其之间的元素顺序反转，最后li中的元素就应该是20,21,22....28,29,39,38,37...32,31,30,40,41,42....49,50。
没错，这次你的代码工作的非常正常，最后结果也如你预期！
既然如此我还揪它出来批斗是干啥？

呵呵，你不妨试试将 li.push_back(i); 改为li.push_front(i); ，也就是说我们这次反向插入20~50，这样li中的元素应该是倒过来的。
呃。。那么这次最终结果应该是50,49,48...42,41,31,32,33...38,39,40,30,29,28...20吧？
呵呵，别急着做预言家，这次你先运行下试试？啊？乱七八糟的数据？！啊？完全不一样的序列？！啊？程序挂掉了！
都有可能。
问题就在于这段代码在不经意间违背了我上面说的保证有效区间的原则的第二条。
“保证区间起始的迭代器不在区间末尾的迭代器的后面”
回头看看代码吧，你怎么知道it1一定在it2前面？it1和it2都是通过find动态找到的位置，没有任何人能够保证找到的位置就一定如你假设那么顺利啊！
因此，这类错误虽然不太容易犯，但是一旦犯了，大都很隐蔽。

最后小小的总结一下：
在使用迭代器的时候一定要小心，要保证给算法的区间是有效的，即：
从区间起始的迭代器开始，一直往下走，可以到达区间末尾的迭代器。
如果不能满足这个条件，那么会导致未定义行为。

迭代器失效

不要过于长久的保存一个迭代器，应该现取现用，因为它可能失效。
而且即使你现取现用，如果不注意一些细节的话，仍然可能导致手上的迭代器失效。
对失效的迭代器，你做除了赋值之外的任何操作都是未定义的，也就是说一旦做了其下场要看你的RP……

因此我们有必要搞清楚迭代器在什么情况下失效。
先来看一个简单的例子，某天你写了这么一堆代码：

C++ 代码：

//如果你看不懂这一段代码，建议回去看一看《迭代器之入门介绍（上）》
template 
int deleteElement(Container& cont,Container::value_type val)
{
  int deleteTimes=0;
  for(Container::iterator it=cont.begin();it!=cont.end();++it)
  {
    if((*it)==val)
    {
      cont.erase(it); //#1
      ++deleteTimes;
    }
  }
  return deleteTimes;
}

嗯，通过对迭代器的学习，你已经能写出这样的函数了，不错不错。这个函数对一个容器遍历，发现元素有等于val的便毫不留情的删除掉，并且最后返回被咔嚓掉的元素数量。
可是不要高兴的太早，这个代码是要挨批的。它有严重的错误：不信你试着运行下……哦，算了，反正是看RP。。
呃，这次其实我不用看你的RP也大体上可以猜出你的状况：如果是一个vector的话，这个函数很可能不会出错，但是执行结果恐怕会是乱七八糟；如果是一个list的话，嘿嘿，基本上可以确定这个函数可以连你的程序一起给咔嚓了。

怎么回事？错在哪里呢？
就错在#1处。这里不过是调用了erase删除了一个迭代器所指向的的元素，这有什么不对吗？
呵呵，删除本身没有啥问题。问题在于，删除了这个元素，那么它所在的位置就无效了，指向它的迭代器也应失效。
失效了也没啥，如果你的函数立刻返回的话。但是偏偏你这个函数冷酷无情，咔嚓了一个元素还不停手，于是继续进入下一轮循环——对，调用了++it ——这是一个未定义行为。于是，自己给挂了。活活，刽子手都没啥好下场……
至于为啥vector就可能不崩而list会崩，呵呵，想想数据结构吧，不过这个也不绝对。不过注意一点：即使vector没有崩，也不代表没有问题，迭代器仍然失效了，执行结果不如你所愿就是证明。
那么该如何正确的实现这个函数呢？

C++ 代码：

template 
int deleteElement(Container& cont,Container::value_type val)
{
  int deleteTimes=0;
  for(Container::iterator it=cont.begin();it!=cont.end();)
  {
    if((*it)==val)
    {
      cont.erase(it++); //#1
      ++deleteTimes;
    }else
    {
      ++it;
    }
  }
  return deleteTimes;
}

还是看#1处，这次怎么就对了呢？
注意it++是什么意思：
让it向后移动一个位置，但是返回的是之前的it的位置。
于是在erase的时候那个返回的临时位置倒是被咔嚓了，但是这时候我it已经移动到后面去啦，躲过一劫~

既然说到这里，就顺便提下前置自增和后置自增。
刚才也说了it++返回的是自增前的值，++it返回的是自增后的值，这个相信只要C语言过关的人都没问题。

然而你也应该注意到了：虽然在上例中我用了一次it++，但是我前面写的所有代码，for循环中的自增全都是++it而不是it++。

为什么要优先用前置自增？

“为啥你在循环中总写++it呢？”你问，“我从小都写it++，有区别吗？”
呃……其实也没啥大不了的，就是我的上面那些写法……效率可能更高一些而已。
“啊？凭啥++it就比it++效率高啊？”
嗯。。这样看吧：
++i相当于这么一个函数：

C++ 代码：

T operator++(T& val)
{
  val+=1;
  return val;
}

而i++相当于这么一个函数：

C++ 代码：

T operator++(T& val,int) //这里的int没有实际意义，只是为了区分
{
  T tmp=val;
  val+=1;
  return tmp;
}

看到了吗？
后置自增，需要事先用一个临时变量来保存自增前的值，然后再自增，自增完毕将这个临时变量返回；这里的临时变量就是一个额外的开销。而前置自增就没有这么麻烦，自增后直接将自己返回即可。

因此我们在写循环的时候，那些控制变量的递增什么的，如果可以，尽量用前置递增，特别对于一些如list、map等容器的迭代器，前置递增的效率要高不少。

好了，回来，回来~我们继续谈迭代器失效。

这里有另外一个迭代器失效的例子，更加隐蔽：
今天你想练习下vector的使用，于是写了这么一堆代码：

C++ 代码：

void Fib(int n,vector& ret)
{
    vector::iterator it1,it2;
    ret.clear();         //先清空vector
    ret.push_back(1); //数列第一个数是1
    if(n==1){return;}
    ret.push_back(1); //数列第二个数还是1
    it1=it2=ret.begin();//让it1指向第一个位置
    ++it2; //让it2指向第二个位置
    for(int i=2;i    {
        ret.push_back((*it1)+(*it2));//每次取出最后的两个数相加后放在队列的尾部
        ++it1;
        ++it2;
    }
}

你不过是想写一个求斐波那契数列的函数：参数n给定想要的数列的长度，参数ret返回装满了斐波那契数列的vector。
想法很好，代码也很简单。可惜运行的时候，输出了一堆乱七八糟的数据。（可能就前几个数还是对的）
你晕，就这么两行代码都给出问题，太不给面子了！难道又是迭代器失效？你哭丧着脸：这次没有删除迭代器指向的位置啊？？？我不过是往里面添加新元素而已，旧元素连动都没动过啊！

呃，冷静一下嘛，你的算法思路是没有问题的。简单的说，你只要把vector换成list就完全ok了，不信试试？
咦？真的耶。可是这到底是什么个鬼缘由啊？凭什么list可以vector不可以？

嗯，其实你猜的没错，还是因为迭代器失效。不过这次造成失效的原因不是因为删除，而是添加。
“哎哎，我添加个数据关原来的那些迭代器X事啊，为啥就平白无故失效？vector你给个说法。。”
呃。。vector是不会说话的，不过list说话了：
“嘿嘿，怎么着老兄，知道我的好了吧。告诉你吧，只有像俺list一样这种用指针串起来的容器，才会有这个好处……”

还记得list是个链表吧。内部的元素都是像串腊肉一样一个一个串起来的。这样你添加元素就不会对其它元素造成影响：因为你不过是把一串新腊肉又串上去了而已。

vector内部的故事

可是vector呢？你该不会不知道它内部是个数组吧。数组怎么能平白无故改变大小呢？显然这里有玄机。其实，vector为了达到动态改变数组的大小的能力，内部偷偷的做了点小动作：虚报经费与偷梁换柱。
先别急着把vector送交检察机关了，容我来为其辩护一下：虚报经费是怎么回事呢？假如你需要vector能容纳10个int，这么算在32位系统下应该耗费40Byte的空间，可是vector向系统申请的时候，一般会偷偷多报一点上去，比如64Byte。这样申请下来的空间就有24Byte空余了。别打！其实vector还是很无私的，这些空间它不会自己霸占，而是原原本本留在那里，假如你下次又添加一个int进来，这下不就立刻有地方放啦？不用再找系统申请了。。你知道现在社会，审批个东西多麻烦啊，呵呵。

那偷梁换柱是怎么回事呢？还是继续上面的故事吧。继上次安排了一个int之后，这次你又安排了10个int到vector那里去。这下vector犯愁了，还剩20Byte了，只够容纳5个的，另外5个咋办？踢回去？哎呀于心不忍，于是只好再找系统批一块更大的区域，比如128Byte，然后把原来那个小区域里面的住户一个个请出来，原样不动的搬到新地皮上，再把小区域交还系统（为啥要把老住户搬迁到新地皮上？你应该知道这些住户都想住在同一块地皮上吧——数组在空间上必须是连续的）。经过这私下偷偷的一换，地皮就增大了，就可以容纳更多的伙计啦。

原来如此啊，虽然vector是个好人，哦……好容器，但是他的偷梁换柱行为还是引起了我们的问题：原来指向旧地方的迭代器，现在全都不能用啦（大家都搬到新地方去了，旧地皮都被回收了，当然这些“老位置”都不能用啦）。唉，虽然你很想打，但是念在vector辛劳的份上，算了。

现在搞明白了vector的小动作，你应该就明白了：给vector中添加元素，可能会引起迭代器失效。因此如果你不想在出错的时候大挠头，你最好事先假定每次添加东西进vector迭代器都会失效；要么，你就用一些措施来保证它绝不会失效。

因此，对于刚才那个斐波那契数列的程序，我们就可以这样改：

C++ 代码：

//既然迭代器可能失效，我干脆不用迭代器了
void Fib(int n,vector& ret)
{
    ret.clear();
    ret.push_back(1);
    if(n==1){return;}
    ret.push_back(1);
    for(int i=2;i    {
        ret.push_back(ret[i-1]+[i-2]); //改用下标操作符，虽然可能会稍稍慢一点
    }
}

或者这样改：

C++ 代码：

//假如我还是想用迭代器
void Fib(int n,vector& ret)
{
    vector::iterator it1,it2;
    ret.clear();
    ret.reserve(n); //让它一次性申请个足够大的地方，保证下次再不需要重新申请
    ret.push_back(1);
    if(n==1){return;}
    ret.push_back(1);
    it2=it1=ret.begin();
    ++it2;
    for(int i=2;i    {
        ret.push_back((*it1)+(*it2));
        ++it1;
        ++it2;
    }
}

通过这个例子就知道了：不仅是删除元素会导致迭代器失效，对于vector、deque这种连续或分段连续的容器，添加元素也可能导致迭代器失效。

上面唠叨了那么多，其实这里有一个列表可以详细的总结一下迭代器失效的情况（啥？为啥不早说？）
适用于一般情况的STL：


任何容器的erase操作	被erase的位置的迭代器失效；
vector的push_back操作	可能没事，但是一旦引发内存重分配，所有迭代器都会失效；
vector的insert操作	插入点之后的所有迭代器失效；但一旦引发内存重分配，所有迭代器都会失效；
vector的erase操作	插入点之后的所有迭代器失效；
vector的reserve操作	所有迭代器失效（因为它导致内存重分配）；
deque的insert操作	所有迭代器失效；
deque的erase操作	所有迭代器失效；

其实从列表看出来，大量迭代器失效主要都集中在vector和deque这种要求内部空间连续或者分段连续的容器上。（都是偷梁换柱的结果，嘿嘿）顺带一提，deque的push_back和push_front不会引起迭代器失效，因为它的内存重分配不涉及“搬家”问题。
而像list、map、set这些用指针互相串起来的结构的容器，一般很少发生迭代器失效的情况。除了erase那个位置，一般不会影响其它位置的迭代器。

好了这次就讲这么多，总结一下吧：

这次我们聊了迭代器的使用以及可能碰到的一些问题，包括：
-- copy时注意目标区间的大小；
-- 区间的有效性：
------ 起始末尾必须是同一容器上的迭代器；
------ 起始必须保证不在末尾之后；
-- 迭代器失效：
------ 删除引起失效；
------ 添加引起失效；
另外顺便穿插了些小内容比如前置迭代器的效率、vector内部的管理等。
希望大家有所收获。

本来还有些内容的，考虑之后再慢慢添加吧。

引用内容

最简单的迭代器：指针

更复杂的迭代器：迭代器之配接器(Adapter)

迭代器的分类(Category)

附录：

上文中出现的一些STL算法和容器的简要说明：

话说我本来以为这篇文章写的很简单了，结果还是有人说内容有点多，想想可能是因为涉及了一些STL算法和容器的原因。呵呵，我觉得这些应该是看此文之前先去做点大致了解的，不过为了方便，还是在这里添加一个附录列一下吧。

上文中出现的一些算法：


名称	参数	说明
copy	(srcBegin,srcEnd,dstBegin)	拷贝。将区间[srcBegin,srcEnd)拷贝到以dstBegin开始的一个区间中
sort	(begin,end)	排序。将区间[begin,end)内的元素排序。默认从小到大
reverse	(begin,end)	反转。将区间[begin,end)内的元素顺序反转。比如区间内的元素是1,2,3,4,5，调用后变成5,4,3,2,1

以上算法全部包含在algorithm头文件中

上文中出现的一些容器：


vector	序列容器，相当于一个大小可变的动态数组（你完全可以把它当作普通数组那么用）。内部的存储空间是连续的。可以以非常快的速度向尾部添加数据。
list	序列容器，本质上是一个双向链表。可以在任何地方高效的插入数据。但是不允许随机访问。
deque	双端队列，很神奇的一个序列容器，和vetor用法差不多，但是可以从两头高效的追加数据。
map	关联式容器，其中的元素是一个“两人组”，key和value。key是索引，value是值，元素在容器中的位置取决于key的值。可以用key快速索引到value。map内部是一个树状结构（平衡二叉树或者红黑树）
set	关联式容器，和map很像，不过元素是单身——只有value，相当于用value自身来作为索引的map。set内部也是一个树状结构（平衡二叉树或者红黑树）

以及这些容器提供的一些成员函数：


aaaaaaaaaaaaa
push_back(i)	向容器尾部追加数据i。适用于所有序列容器（vector、deque、list，还有string）
push_front(i)	正如其名，这次是向容器头部添加。适用于deque、list。
insert(pos,i)	看名字也知道，向容器的pos位置插入数据i。适用于所有STL标准容器。不过对于关联式容器（map、set），pos只是提示，没有实际效果（因为关联式容器元素的顺序是取决于元素本身，你不能随意指定位置）。
erase(pos)	删除pos位置的元素。

其实我觉得这些列表中的各个函数，看名字就能猜出它是啥意思了啊。。应该不用我说了嘛。。（砖~）

还是那句话，写的好了顶一下，写的不好了拍一下啊，呵呵。

迭代器之入门介绍（上）

sandy_sp@163.com(sandy1) — Wed,21 Oct 2009 15:19:09 +0800

迭代器之入门介绍

什么是迭代器(iterator)？对于没有接触过STL或类似模式的库的同学们可能会觉得摸不着头脑，而刚刚接触STL的同学们这个概念也可能会让他们迷惑，迭代？器？貌似挺复杂的啊。

其实一点也不复杂。我们先不管它们具体的写法、用法，先来看看到底迭代器是个什么东西。

其实它还有另外一种更加形象的翻译名字：“游标”。这个名称对初学者来说其实更能帮助他们理解。游标卡尺见过吧？（什么？没见过？你们初中物理不上实验课的吗？……）游标卡尺上面就有一个可以来回移动的游标，通过移动它指向不同的地方我们就可以测量出物体的长度。

其实这里的STL，和你中学实验课手上拿的那个家伙的概念是一样的。

如果你不是急躁到非游标不听，那么还是听我从STL娓娓道来吧……

算法和容器，迭代器之由来

大家都知道STL的大三主体：算法、容器、迭代器。（不知道？不要紧，慢慢往下看）

容器顾名思义，就是可以存放东西的东西。本质是一堆封装好的数据结构，比如常见的数组、链表、队列、栈等等。（什么？没听过这些？那还是赶快回去找本书恶补下吧-_-）
还记得自己大学数据结构课程上被要求写一个链表时调试的那难受劲么？呵呵，有了STL封装好的这些常用数据结构，我们就不用自己头疼写那些玩意啦，这里有世界大师们写好的东西供我们使用。（什么？你当时一点也不难受不头疼？好吧，算你talent）
有现成的容器当然很爽啦，不过我怎么又想起了大学算法课上写快速排序的时候那一个难受啊。。（喂喂，有完没完？）哎呀这些算法也是最常用的嘛，怎么就没人写好一个来供我用呢？想得美。的确我想的很美，STL果然就有大师们写好的算法了，嘿嘿，用就是啦。

好了啰嗦了这么多，估计你会认为我是个弱智，同时你也会发现貌似有了容器和算法，STL已经很完整了，还要搞个迭代器这么难听的名字的东西干吗？

嗯，接下来我们设想你非常talent，于是成为了大师，负责来写这些STL的算法。
就来写一个最简单的算法吧：在一个容器中找到最小的那个元素。
你一想这还不简单：

C++ 代码：

template //Cont是容器的类型，T是容器中元素的类型，如果你不知道什么是模版，建议还是先回去找本书补一补
T findMin(Cont& v)
{
  T tmp;
  for(int i=0;i  {
     if(tmp>v[i]){tmp=v[i];}
  }
  return tmp;
}

ok，很好。但是又有人说，啊呀，这个只对数组类的容器有用，对链表没用啊，你再为链表写一个吧。
你皱皱眉头，说，行。于是又操起键盘敲敲打打，ok了。
结果第二天又有人来，说，啊呀啊呀，这个还不够啊，对二叉树没用啊，你再写一个吧……
后来，老大干脆过来，拍拍你的肩，说，STL是可以扩展的，以后还会有更多的容器，你的算法都得跟上啊……
是不是想吐血？
好吧我相信你的实力，你不会吐血，这些对你来说小菜一碟，这个算法写n遍你都没问题。可是算法多着呢，求距离、排序、稳定排序、变序、剔除重复、上界、下界、建堆……不下m个，你怎么办？写m×n个算法版本？好吧再算你毅力如夸父逐日，但是扩展怎么办啊？更多的用户写的新容器、更多的用户写的新算法，你怎么兼容？

我承认我上面废话那么多是为了练习语文老师教我的作文欲扬先抑的写法。
其实你知道我写这么多只是为了引出一句话：
STL的一个基本思想就是，采取某种措施将算法与容器分开。
这样我们就不必为每个容器单独写算法了。

对，它采用的措施就是迭代器。
使用一个小小的游标来指明一个元素在容器中的位置。这样我们就可以针对这个游标来写算法，完全不用管容器是什么啦。

比如上面那个算法，我们现在就可以这么写：

C++ 代码：

//如果你编译这段代码出现错误，请看本文最后附注
template
T findMin(Cont& v)
{
  T tmp;
  for(Cont::iterator it=v.begin();it!=v.end();++it)
  {
    if(tmp>(*it)){tmp=(*it);}
  }
  return tmp;
}

慢着，这都是什么啊？
别急，我来仔细解释下
Cont是容器的类型，容器中定义了一个此容器所用的游标（迭代器）的类型，叫iterator，于是Cont::iterator it;就定义了一个名叫it的迭代器。
啥？我咋知道容器中怎么定义了iterator这个类型？嘿嘿，这就是一个Concept了。这是约定，这是规矩！STL中所有的容器都定义了一个名叫iterator的类型来表示它所用的迭代器，下文中的begin()、end()成员函数也是，所有容器都有，未来要适用于STL的容器也得有，因此你就不用担心啦。（即使实在没有，也有一些办法）
现在我们有了游标，还要让它指向正确的位置。v.begin()就是这么一个位置。它代表容器的起始位置，返回值是一个游标，指向容器的头部。于是Cont::iterator it=v.begin();这句就是定义一个迭代器并且让它指向容器的第一个元素的位置啦。
那么v.end()也就很好理解了，它返回容器的最后一个元素的位置……错！是最后一个元素后面的一个位置。
有点绕口？记得文件读取的时候有一个EOF位置么？和那个很相似，也就是越过最后一个元素(pass the end)，它后方的这么一个“虚”位置。
为啥要搞这么复杂？返回最后一个元素的位置多简单直白啊？嗯，STL是有它的考虑的。

区间
这个考虑就是，为了方便表示区间这个概念。
大师们比你考虑的要全面。他们想很多算法不仅仅是作用于一个容器之上，而是作用于容器的某一部分。
比如我只想找容器中前30个元素中最小的。那么上面那个算法就没办法啦，它只能一股脑的把整个容器扫描一遍。这时候是不是就想起了中学数学中“区间”这个概念？如果我指明一个区间，指定区间起始，区间末尾，那么算法就可以针对这个区间上元素进行操作。这也就是迭代器概念引入STL的另外一个原因——有了迭代器，就可以不针对容器写算法，而是针对迭代器写算法。
我们现在再把上面的那个寻找最小值代码改一下：

C++ 代码：

template
T findMin(Iterator begin,Iterator end)
{
  T tmp;
  for(Iterator it=begin;it!=end;++it)
  {
    if(tmp>(*it)){tmp=(*it);}
  }
  return tmp;
}

好了，现在函数传入的参数不再是一个容器，而是两个迭代器，这两个迭代器分别代表区间的起始和末尾，
这样我们的算法也就可以完成上面所说的局部扫描的功能啦。

而STL规定的区间，就是用两个迭代器来表示：一个指向区间的第一个元素位置，作为区间的起始，一个指向区间的最后一个元素的后面的那个位置（pass the end），作为区间的末尾。

如果你还没有把你的中学数学都忘光的话，你一定会觉得这个概念和数学上的半开半闭区间的概念很相似。是的，它们是一致的。事实上STL中的区间都是左闭右开区间。区间[1,5)中有1、2、3、4，但是没有5。同样[begin,end)中没有end这个位置，end是最后一个元素后面的那个虚位置，很好理解了吧？

为啥要这样做呢？一个主要的好处是，空区间就很容易表示了，起始和末尾都是同一个位置的区间就是空区间，不需要做任何特殊处理。同时还有一些其它好处，比如一些搜寻算法，如果没有找到符合条件的元素，可以返回这个区间的末尾来表示“没有找到”的概念，而如果没有末尾这个特殊的位置的话就会很难办。

迭代器的基本操作

好了我们扯了个大圈子，虽然搞清楚了那个诡异的end位置以及区间的概念，但是貌似还是有些不对劲的地方，这个游标（迭代器）光指向一个位置有屁用啊，不能操作元素还不是废物一个。
好好不要这么FQ，回到上面的代码。
  for(Iterator it=begin;it!=end;++it)
  {
    if(tmp>(*it)){tmp=(*it);}
  }
你肯定也看出来了，迭代器貌似和指针很相似。通过*操作符可以取到它所指的位置的元素的值。
you are right。事实上，迭代器就是对指针这个概念的高层抽象。
而且和指针一样，如果这个迭代器不是常量迭代器（后文会讲），那么一般情况下也是可以修改它所指向位置的值的。例如(*it)=5;

这样，我们就可以掌握基本的迭代器操作了：
假设有一个迭代器 it，我们一般都可以做这些操作：


it++ 或++it	迭代器自增，也就是将游标向后移动一个位置
it-- 或 --it	迭代器自减，也就是将游标向前移动一个位置
it1 == it2	比较两个迭代器是否相等，也就是说它们俩指向的位置是否是同一个位置
it1 != it2	同上，是否不等
it1 = it2	将it2赋值给it1，也就是让it1指向it2的位置。
*it	取迭代器指向的元素。
it->XXX	调用it指向的元素的某成员（如果有的话）。

一切都和C/C++语言中的指针那么相似，真是太好用了，嘿嘿。

不过不要高兴的太早，有时候有些迭代器是没有这里面的一些功能的（后文会讲）。
不过对于STL中的所有标准容器（vector、list、deque、map、set……），它们的迭代器全都支持上面的操作，尽情地去用吧。

容器的迭代器

到此，你已经大致了解了迭代器的由来、迭代器的意义，迭代器的基本操作。
那么想要更好的配合STL中的容器使用，还是来看一个列表。
STL中的每个容器都遵循一些Concept，也就是说是一种概念约定，容器必须带有一些东西，以配合迭代器这个概念来使用。
上文已经说到了一些，这次用一个列表明确的列出来：


value_type	类型，表示这个容器保存的元素的类型
iterator	类型，表示这个容器适用的迭代器
const_iterator	类型，表示这个容器适用的常量迭代器
begin()	成员函数，表示这个容器的起始位置（第一个元素的位置）
end()	成员函数，表示这个容器的结束位置（最后一个元素的后面的那个位置）

什么是常量迭代器？
既然迭代器和指针很像，你肯定会想到有像const char* p这样的一种“只读”指针，指针本身指向的位置可以变换，但是你却不能通过它来改动它指向的地方的数据。
常量迭代器就是这么一种“只读”迭代器。可以移动它，但是不能改变它指向的元素，很简单吧。
大家都知道从char *转化成const char*是“无缝的”，也就是说不需要强制类型转换，可以直接把char *当作const char*来用，但是反之则不行。常量迭代器也是一样的，因此你可以将一个普通迭代器赋值给常量迭代器，但是反之则不能。
因此：

C++ 代码：

vector::const_iterator it=v.begin(); //ok
vector::iterator it2=it; //Error：不能把常量迭代器赋值给普通迭代器

最后再说下这个value_type类型。正如上面表格中所说，它代表的是这个容器中元素的类型：
vector::value_type 等价于int
vector::value_type 等价于double*
list::value_type 等价于string
而且不仅是容器有这个类型，一些迭代器也有：
list::iterator::value_type 等价于int （但请注意并不是所有迭代器都有，而且即使同一种迭代器在不同版本的STL中也可能不同）

如果我想定义一个容器中的元素类型的变量，就可以使用value_type来定义了。

C++ 代码：

vector v;
vector::value_type val=5; //这里的val就是int类型的变量
v.push_back(val);

你可能会疑惑，这不是写起来更麻烦吗？明明简单的int，非得搞成XXX::value_type这副模样，有啥用啊？
呵呵，在这里看起来的确没什么用，但是当你去写一个通用（泛型）算法的时候就会非常有用了：

C++ 代码：

void func(T container)
{
  T::value_type val; //在这里你可根本不知道T到底是vector还是list啊，呵呵
  //...
}

你是不是马上想起之前写的那个寻找最小元素的算法了？
我们之前写的那个针对容器的版本：

C++ 代码：

template
T findMin(Cont& v)
{
  T tmp;
  for(Cont::iterator it=v.begin();it!=v.end();++it)
  {
    if(tmp>(*it)){tmp=(*it);}
  }
  return tmp;
}

为了定义一个临时变量，不得不在模版中多加入一个类型T，使得使用起来非常不方便：
findMin >(v);
太麻烦了！我的容器类型都告诉你是vector了，容器里面的元素类型肯定就是int了嘛！还非要我再告诉你一遍吗？不会自己去容器里面查一下啊？
于是我们现在就可以这样改进：

C++ 代码：

//如果你编译这段代码出现错误，请看本文最后附注
template
Cont::value_type findMin(Cont& v)
{
  Cont::value_type tmp; //here，我们现在终于可以丢掉那个该死的T了
  for(Cont::iterator it=v.begin();it!=v.end();++it)
  {
    if(tmp>(*it)){tmp=(*it);}
  }
  return tmp;
}

不错吧，这样你使用这个函数的时候就可以直接调用：findMin(v);函数就可以自动知道容器的类型、元素的类型，而不必像以前一样臃肿的写findMin >(v);了。
（啥？为啥连vector也省了？忘了C++强大的类型机制可以帮我们推导出函数参数的类型吗？）

你或许一拍脑袋，说既然如此那个迭代器版本的findMin也可以这么改了：

C++ 代码：

template
Iterator::value_type findMin(Iterator begin,Iterator end)
{
  Iterator::value_type tmp;  // !! may not work!
  for(Iterator it=begin;it!=end;++it)
  {
    if(tmp>(*it)){tmp=(*it);}
  }
  return tmp;
}

哦不，不行。你头脑太热了，还是赶快去水龙头把脑袋冲5分钟吧，冷静下来是不是想起刚才说过的：只有一些迭代器才有value_type成员类型，并不是所有的迭代器都有，因此这么写可能导致编译错误哦。
但是要想得到迭代器指向的元素的类型，办法还是有的，不然STL里面那么多需要迭代器的算法是怎么搞出来的？嘿嘿，有一个巧妙的技巧，不过这里暂且不谈~~（卖什么关子，砸~）

好啦，这次就说这么多，作为新人迭代器的基础入门介绍呵呵，如果觉得写的好请顶一下，如果觉得写的搓也请拍一下啊。

（当然写的搓极了，这么简单的东西废话了这么多才讲完……@#￥%&）

下次（如果有下次的话），我们可以一起来聊一聊稍微进阶一点的内容啦。（砖~~）

-----------------------------------------------------------------

附注：

可能有的伙计编译上面的一些代码出现错误。
如果排除你的头文件包含问题的话，可能是因为编译器对类型的识别错误导致的：

比如下面这句：
for( Cont::iterator it=v.begin();it!=v.end();++it)
在有些编译器中，由于编译器无法正确判别Cont::iterator到底是一个类型还是Cont的一个静态成员，可能就会导致错误：如果Cont::iterator被编译器误判为静态成员，那么当然这就不符合定义的语法了，会报编译错误。这时候可以通过加入typename关键字来强制指明这是一个类型来解决：
for(typename Cont::iterator it=v.begin();it!=v.end();++it)
当编译器看到那个typenme的时候，就知道Cont::iterator在这里应被看做类型而不是静态成员，于是就不会再出现上面的问题了。

如果还发现其它问题，欢迎你留言告诉我~

关于命名空间

sandy_sp@163.com(sandy1) — Fri,02 Oct 2009 16:51:36 +0800

关于命名空间

原来我以为我对命名空间了解已经很完全了，前几天还给学弟学妹们讲过这些东西呢，结果发现还是有一些被遗漏的地方。

1、命名空间别名

C++ 代码：

namespace WuhanUniversityComputerConsortium
{
   void PrintMemberList();
}
int main()
{
  namespace WHUCC=WuhanUniversityComputerConsortium;
  WHUCC::PrintMemberList();
  return 0;
}

2、动态命名空间
有了命名空间别名，动态命名空间就很好理解了：

C++ 代码：

namespace WHUCC
{
   void PrintPresidentName();
}
namespace WHUMSTC
{
   void PrintPresidentName();
}
int main()
{
  namespace currentMainT=WHUCC; //明年可以换WHUMSTC，^_^
  currentMainT::PrintPresidentName();
  return 0;
}

3、Koenig查找
其实这个我以前也是知道的，只是那时候没有仔细确认过。这次就仔细记录下吧。

C++ 代码：

namespace WHUCC
{
   class Member;
   void PayMembershipFees(Member& sbd);
}

int main()
{
  WHUCC::Member wkk;
  PayMembershipFees(wkk); //乖乖交钱吧~~ 
  return 0;
}

某郁闷地说：“我没有using namespace WHUCC啊？？怎么还要收钱？”要怪就去怪Andrew Koenig吧！你可以找他要回那￥10，也可以建议他取消Koenig查找，不过如果这样的话你就不能这样写代码了：
std::cout<<"Give my money back!"; //Koenig查找在此大显神威
而必须改成：
std::operator <<(std::cout,"Give my money back!");

4、匿名命名空间
这个听起来有点诡异，可是事实上的确可以这么搞：

C++ 代码：

namespace
{
  void func()
  {
     //...
  } 
}
int main()
{
  func();
  return 0;
}

至于作用，在代码层面上和static修饰符差不多——你在其它的编译单元中无法使用func()，因为你根本不知道它所在的命名空间到底是啥名字！

5、std命名空间不可改变
咋听起来天经地义，但是实际上很容易被忽略。并不是所有的命名空间都是开放的、可扩展的。
不要抱念头去给std里面私自添点什么——这不一定会报错，但是很可能会产生未定义行为。
如果你真想往里面搞点东西进去——把你想搞进去的东西写成一份提案，交给C++标准委员会比较好。。嗯。

6、new和delete与命名空间
new和delete是一种特殊的运算符，其特殊之处之一就是不能丢在命名空间里面。
虽然单纯从理论上说它俩即使放进去也没啥问题（如果100%正确匹配使用的话），但是事实上一旦允许这种行为，极有可能引发可怕的错误。想想看在某个命名空间内部new出来的一个变量被传到命名空间外面然后delete，是啥后果？（是不是和我与Felix写的某篇文章中的第4点很像？没错，其实就是一回事）
事实上你在一个命名空间里面定义new或delete函数不一定会报错，但是任何支持标准的编译器都不会让你去使用它。

发现一个超牛B的开方函数

sandy_sp@163.com(sandy1) — Mon,21 Sep 2009 18:34:58 +0800

发现一个超牛B的开方函数

因为以前搞过ARM上的游戏开发，因此那时专门自己研究了开平方的算法，写出了一个高效的定点数开方函数，

当时还有点沾沾自喜呢，结果今天碰到一个更牛B的（当然这个是x86上用的）：

C++ 代码：

float SquareRootFloat(float number)
{
    long i;
    float x, y;
    const float f = 1.5f;
    x = number * 0.5f;
    y = number;
    i = * ( long * ) &y;
    i = 0x5f3759df - ( i >> 1 ); //注意这一行 
    y = * ( float * ) &i;
    y = y * ( f - ( x * y * y ) );
    y = y * ( f - ( x * y * y ) );
    return number * y;
}

整个函数就这么一点，连个循环迭代都没有，一次执行完就出结果。太牛B了，我都没看懂。。

测试结果标明精度与标准C库提供的sqrt十分接近，可以完全保证5位有效数字。
特别是那个诡异的magic number的取值，简直神了。
这在绝大多数游戏中足以满足精度而且速度肯定比迭代快多了，不过遗憾的是我目前还没看出如何能改造成定点的以适用于ARM平台。。（我还是继续用我自己写的那个玩意吧，hoho~）

要说这个函数出自哪里，出自卡马克大神之手。。。。

[转]windows mobile部分技术总结

sandy_sp@163.com(sandy1) — Mon,31 Aug 2009 10:41:36 +0800

[转]windows mobile部分技术总结

• ActiveSync 的原理
    使用 USB 驱动把 PC 与设备之间的链接模拟成一个网络，在 PC 上可以看到一个虚拟的网络适配器（网卡），手机设备上运行着 ActiveSync 的设备端程序，可以看作服务器，PC 上运行客户端程序，两者可以通过虚拟网卡进行 TCP/IP 通讯。

• SP 与 PPC 编程的区别
1. PPC 有触摸屏，需要考虑鼠标消息的处理，SP 没有。
2. PPC 需要考虑同时支持横屏和竖屏，除非是正方形的屏幕。
3. SP 有键盘，需要考虑键盘消息的处理，比如加速键、热键、后退键等，PPC 一般没有，但也可以有。
4. 电源管理不同，SP 可以完全关闭，PPC 没有设计关闭系统的功能。
5. Shell 不同，一些 Shell API 在两者之上的支持不同。
6. 界面风格不同，SP 有传统的九宫格和翻页式的列表菜单，PPC 则更像桌面，使用带滚动条的列表菜单，PPC 还有弹出式菜单，SP 因为没有触摸屏，所以没有弹出式菜单。
7. SP 大量应用 COM，比如“设置”里的控制面板项，PPC 的控制面板项则使用普通的 DLL。
8. SP 有大量配置信息是保存在 XML 文件里的，PPC 更多是使用数据库和注册表。

d 将参数以十进制的形式输出
o 将参数以无正负号八进制的形式输出
x 将参数以无正负号的十六进制的形式输出
u 将参数以无正负号的十进制的形式输出

SHCloseApps()
  必须是这样的程序才会被关闭：

1. 有窗体，并没有隐藏
2. 包含 WS_OVERLAPPED（不能包含 WS_POPUP）
3. 所有程序响应 WM_HIBERNATE 后依然内存不足
4. 不是 SAN 不关闭程序，比如 WMP 就是不会关闭的，怎么整都不会关 WMP。

• UTF8 和 Unicode 编码的互相转换
    在英文字符占大多数的情况下，使用 UTF8 可以节省存储空间，一般 XML 文件都是 UTF8 编码的。以前做 GSM6702 时，发现 Smartphone 里的 XML 文件是没有 BOM 的 UTF8 编码格式，如果只有英文，则和 ANSI 编码没有差别。

    LdapUnicodeToUTF8 和 LdapUTF8ToUnicode 这两个 API 就是用来做转换的。编码格式其实很简单，不多说了，这里提出来只是想建议大家，如果自己的模块里遇到需要把数据保存成文件的话，刚好大部分字符都是英文时，记得使用 UTF8 编码。当然，在 PC 上也是建议这样做的，只是移动设备存储空间比较小，更应该这样做。
• 更新待机界面
    用 PostMessageW( GetDesktopWindow(), WM_SETTINGCHANGE, 242, 0L ); 可以更新待机界面，包括重载主题、墙纸、待机插件等。如果要写待机插件的 Release 安装包，可以使用 SetupDll 调用这一语句，来确保安装后马上生效，不用再进入“开始-设置-今日-项目”里设置。

    我是这样研究出这个语句的：“开始-设置-今日-项目”这个控制面板页是有这个功能的，我猜测它是发送某个消息给桌面窗口，就用 Remote Spy 截取桌面窗口的消息，发现了这个消息，测试后确定。

• 注册我们的应用程序
    比较一下微软的快捷方式文件和我们自己的就会发现，有一个明显的不同之处：微软大部分应用程序的快捷方式并不是直接写路径名的，而是一个以 : 开头的化名（半角的冒号），为什么微软要这样绕弯子？用化名很明显还要先解析，比直接用路径名慢。

    答案还是和 WM 特殊的内存管理有关，系统最多只能跑 32 个进程，我们来想像一下这样的苛刻条件：系统里已经跑了 32 个进程，其中必定有 Shell32.exe，“开始-程序”这个界面是 shell32.exe 的窗口，假设其中最不常用的进程是 Windows Media，“最不常用”说明有新进程要跑时，被关掉的就会是这个“最不常用”的进程。那么，用户在“开始-程序”里选择运行 Windows Media 时会发生什么？Windows Media 会先被关闭，然后又新建了 Windows Media 的进程。

    所以，我们常常写的“兼容程序”靠运行时检测系统里有没有同样类名的窗体来判断前例的方法是不健壮的！因为即使这样检测，程序依然有一段时间是存在两个实例的，有两个进程，就说明可能在新进程跑起来时，由于 32 个进程的限制，而导致前例被关闭，这样就变成一个程序先关掉再运行一次，浪费时间，浪费系统资源。

    那为什么用化名就不会这样？还是以 Windows Media 为例，Windows Media 的化名是 :WMPLAYER，打开注册表 [HKEY_LOCAL_MACHINE\Software\Microsoft\Shell\Rai\:WMPLAYER] 会发现这个键下面有一个名为 0 的字符串值，其数据是 WMP for Mobile Devices，这刚好是 Windows Media 主窗体的类名，还有一个名为 1 的字符串值，数据是其程序名。当某个进程用 ShellExecuteEx 运行 :WMPLAYER 或者指向 :WMPLAYER 的文件时，ShellExecuteEx 会先查找系统里有没有类名为 WMP for Mobile Devices 的窗体，如果找到就激活，不会再新建 Windows Media 的进程，这个过程，是在调用者进程里完成的，没有新建被调用者进程。

    建议大家都注册一下自己的模块，以后快捷方式里统一都用化名，例如：AmoiTest.exe 的注册信息为：

[HKEY_LOCAL_MACHINE\Software\Microsoft\Shell\Rai\:AMOITEST]
"0"="AmoiTestClassName"
"1"="AmoiTest.exe"

    另外还有 2 和 3 的 DWORD 值，我还没完全研究清楚（SAN Based App 用的），不过只要有 1 和 2 就可以完成这个机制了。

• DPI Aware Text and Fonts

    电脑显示器也有 DPI 的概念，但一般不被关心，而移动设备屏幕的 DPI 相对就很重要，微软文档里有一篇 DPI Aware Text and Fonts，建议大家看看，代码可以参考 SDK Sample 里的 BasicApp。

    设置 - 系统 - 屏幕 - 文字大小，这个控制面板页可以设置系统部分应用的文字大小，为了支持从这个页改变字体大小，应用程序需要遵守一定的规范。

    遵守 DPI Aware Fonts 规范的程序，例如：微软联系人（列表界面）、信息（列表界面）、待机插件等，规范请参考 DPI Aware Text and Fonts 文中的 Getting the User Font Size 节，下面简单提一下：
1. 调用 SHGetUIMetrics 取得字体高度
2. LONG  dwFontSize = 12;
3. SHGetUIMetrics(SHUIM_FONTSIZE_PIXEL, &dwFontSize, sizeof(dwFontSize), NULL);
lf.lfHeight = -dwFontSize;
4. 如果是普通窗体应用程序，则要处理字体大小改变的通知消息，这个消息是 String Message，要先注册：

UINT      g_uMsgMetricChange = RegisterWindowMessage(SH_UIMETRIC_CHANGE);

然后再 WndProc 里加入对这个消息的处理，重建字体，刷新界面，具体参考 BasicApp。
5. 如果是待机插件则不用处理 SH_UIMETRIC_CHANGE 消息，因为待机插件管理器会处理这个消息，把所有插件销毁，再重建，字体也就重建了。

• Handle WM_HIBERNATE
    We get this message when the device is running low on memory. All applications should free any memory and resources that they can.

    我看了很多我们自开发的应用，还没看到一个有处理这个消息的。请参考 SDK 带的 Sample 里的 BasicApp。
1. 如果程序没必要跑了，直接销毁窗体，退出进程，这样的程序，例如：大字体、关机、照相机（最小化时）。
2. 如果程序不在前台，可以销毁软键行（MenuBar，这也是一种窗体，耗的资源挺大的），但记得要设计成窗体激活时还可以重建：
// 销毁
CommandBar_Destroy(g_hWndMenuBar);
g_hWndMenuBar = NULL;

// 重建
if( !g_hWndMenuBar )
{
    g_hWndMenuBar = SHCreateMenuBar ...
}
3. 释放所有没必要的 GDI 资源，BasicApp 就是例子。
相关资料：

低内存环境
      当系统运行在一个低RAM环境中，应用程序将调整并最小化它们的内存使用。Windows CE运行在一个几乎永久的低内存环境中。Pocket PC被特意设计为运行低内存环境。在Pocket PC中的应用程序没有关闭按钮，当系统需要更多内存时，外壳（shell）自动关闭这些程序。正因为如此，Windows CE有许多方法来管理运行在低内存系统中的程序。
WM_HIBERNATE 消息
      Windows CE 第一个最明显的变化时是增加了 WM_HIBERNATE 消息。Windows CE 的 shell 发送消息给最顶层的有WS_OVERLAPPED 式样（那就是说，既没有 WS_POPUP 也没有 WS_CHILD 式样）和 WS_VISIBLE 式样的窗口。这些限制将允许大多数程序至少有一个窗口可以接受 WM_HIBERNATE 消息。有一个例外就是，当应用程序不能真正结束程序而只是简单隐藏所有窗口。这种方式允许应用程序可以快速启动，因为它下次只是显示窗口。但是这就意味着，当用户想关闭它们的时候仍然占据着 RAM。这对程序设计来说是正确的，但是不应用在 Windows CE 中，这种方式会造成程序被隐藏时总处在冬眠（hibernate）模式，因为它们永远接收不到 WM_HIBERNATE 消息。
      Shell 发送 WM_HIBERNATE 消息给最顶层的窗口在 Z 轴相反的位置（reverse Z-order）直到内存被释放，使可用内存超过系统预先的限制。当应用程序接收到一个WM_HIBERNATE消息，它会尽可能减少内存占有程度。这包括释放被缓冲（cached）的数据；释放 GDI 对象，例如字体，位图和画刷；并销毁任何窗口控件。从本质上来说，应用程序将会减少内存到维持它内部状态的最小值。
      如果发送 WM_HIBERNATE 消息给后台的应用程序不能释放足够的内存以便使系统离开内存被限制的状态。WM_HIBERNATE 消息将会发送给前台程序。如果你正在冬眠的程序开始销毁窗口的控件，你必须确保它不是前台的程序，控件消失不会给用户带来兴奋的感觉而是困惑。
内存限度
      Windows CE 监视系统自由的 RAM，并对越来越少的 RAM 作出响应。当很少内存可用时，Windows CE 首先发送 WM_HIBERNATE 消息，接下来会限制可能的内存分配。下面的两个表显示了 Explorer shell 和 Pocket PC 引发的低内存事件的自由内存级别。Windows CE 定义了是个内存状态：normal，limited，low 和 critical。系统的内存状态依赖于整个系统有多少内存可用。这些限制都比 4-KB 页要高，因为系统具有内存最小分配限制，就像 7-1 和 7-2 的表。
表 7-1 Explorer Shell 的内存限度
事件自由内存
1024-Page Size 自由内存
4096-Page Size 注解
Limited-memory state 128 KB 160 KB 发送 WM_HIBERNATE 消息给in reverse Z-order的应用程序。释放栈空间并回收利用。
Low-memory state 64 KB 96 KB 限制虚拟内存分配为16 KB。显示Low-memory对话框。
Critical-memory state 16 KB 48 KB 限制虚拟内存分配为8KB。
表7-2 Pocket PC的内存限度
事件自由内存
1024-Page Size 自由内存
4096-Page Size 注解
Hibernate threshold 200 KB 224 KB 发送 WM_HIBERNATE 消息给in reverse Z-order的应用程序。
Limited-memory state 128 KB 160 KB 开始关闭在 reverse Z-order上的应用程序。释放栈空间并回收利用。
Low-memory state 64 KB 96 KB 限制虚拟内存分配为16 KB。
Critical-memory state 16 KB 48 KB 限制虚拟内存分配为8 KB。

      这些内存状态的影响是共享剩余的财富。首先，WM_HIBERNATE 消息被发送给应用程序，并请求减少它们的内存占有率，当应用程序被发送了一个 WM_HIBERNATE 消息后，系统将检测内存级别，确认是否可用内存在限度之上，如果可用内存不足，WM_HIBERNATE 消息将被发送给下一个程序。这会持续到所有程序被发送了 WM_HIBERNATE 消息。
      Exlporer shell 和 Pocket PC 的低内存策略在这点上有区别。如果 Explorer shell 运行时，系统会显示 OOM（out of memory）对话框，并请用户确认是否关闭一个应用程序或把对象存储区的RAM重新划分给程序内存。如果用户选择了其中之一，仍然没有足够的内存，out of memory 对话框将会再次出现，这个过程会重复，直到H/PC有足够的在限度之上的内存。
      对 Pocket PC 来说，操作稍微有些不同。Pocket PC shell 自动开始关闭最近最少使用的应用程序，而不询问用户。如果关闭除了前台程序和 shell 之外的所有程序，仍然没有足够内存，系统将会使用其他的技术来从栈开始清理自由的页，并限制虚拟内存分配。
      如果在任何一个系统上，应用程序被请求关闭却没有关闭，系统在 8 秒钟后将会清理该应用程序。这就是一个应用程序不要分配大量的栈空间的原因。如果应用程序被关闭而导致低内存环境，很可能是栈空间不能分配，应用程序将被挂起。如果发生在系统请求应用程序关闭以后，可能是清除内存以后没有适当的恢复状态。
      在 low 和 critical-memory 状态，应用程序被限制了内存分配的大小。在这些情况下，甚至还有可以满足要求的内存剩余情况下，请求分配大过允许限度的虚拟内存将会被拒绝。记住，并不止是虚拟内存分配被限制，堆分配和栈分配也被禁止，要满足分配请求，那么分配时需要虚拟内存在可允许的限制之上。
      我这里要指出，发送 WM_HIBERNATE 消息和自动关闭应用程序是由系统的 shell 执行的。在一个 OEM 自己可以编写 shell 的嵌入式系统中，实现 WM_HIBERNATE 消息和其他内存管理技术是 OEM 厂商的责任。幸运的是，Microsoft Windows CE PlatForm Builder 提供了 Exlporer shell 实现 WM_HIBERNATE 消息的源码。
      这里不言而喻，应用程序要检查任何内存分配调用的返回代码，但是因为这里还没说，所以我还是要说。检查内存分配调用的返回代码。在 Windows CE 中比在桌面版本的 Windows 中可能有更多的机会导致内存分配失败。应用程序必须很好地实现拒绝内存分配。
      Windows CE 不支持完全的 Win32 内存管理 API，但是很清楚这里有对 WindowsCE 设备受限制内存的足够支持。
o 尽量用 ShellExecuteEx 代替 CreateProcess
理由：
1. WM 目前最多只能运行 32 个进程，如果已经达到 32 个进程了，用 CreateProcess 去调用外部程序，必定失败，而 ShellExecuteEx 则会先检查当前系统的进程数，如果已经满了，就先关掉一些窗体，等待进程退出后再新建进程。
2. CreateProcess 只能用来运行可执行文件，而 ShellExecuteEx 支持所有注册类型的文件，并且可以解析运行 RAI Based 程序。
(*) RAI Based 程序是指有在注册表里注册自己的程序，例如 :MSPIE。

心得：如果有 Shell API 和 Core API 可以完成同样的任务，应该选择用 Shell API，因为 Shell API 更高层，会考虑更多高层的异常处理。

ChangeDisplaySettingsEx

切换屏幕旋转模式通过调用 ChangeDisplaySettingsEx 来实现，如：
DEVMODE devmode = {0};
devmode.dmSize = sizeof(DEVMODE);
devmode.dmDisplayOrientation = DMDO_90; //水平模式
devmode.dmFields = DM_DISPLAYORIENTATION;
ChangeDisplaySettingsEx(NULL, &devmode, NULL, 0, NULL);

取得当前模式的代码如下：
DEVMODE devmode = {0};
devmode.dmSize = sizeof(DEVMODE);
devmode.dmFields = DM_DISPLAYORIENTATION;
ChangeDisplaySettingsEx(NULL, &devmode, 0, CDS_TEST, NULL);
通过 devmode.dmDisplayOrientation 的值可以判断当前模式。

值得注意的是，这样切换模式并不是永久的，当设备重新起动后，就会还原为初始状态。
如果你需要在保留切换的屏幕模式，可以通过设置注册表中

HKEY_LOCAL_MACHINE\System\GDI\Rotation 下的两个键值实现
Angle - DWORD (0, 90, 180, 270)
LandscapeMode - DWORD (0,1)

---------------------------------------------------------------------------
Windows Mobile上怎么调出发短信（彩信，邮件）的界面，并把相应的字段用程序填写
Mobile, 短信, 彩信, 字段, 邮件
BOOL LanchSystemSmsEditor(const TCHAR* SmsReceiver, const TCHAR* SmsContent, TCHAR* SmsSubject)
{
  TCHAR commandLine[MAX_PATH];
  TCHAR szAppName[MAX_PATH];
  lstrcpy(szAppName, _T("tmail.exe"));
  PROCESS_INFORMATION procInfo;

  if( ! CreateProcess(szAppName, _T("-service \"Sms\""), NULL,NULL, FALSE,

Create_NEW_CONSOLE, NULL, NULL, NULL, &procInfo) )
  {
    return FALSE;
  }

  swprintf(commandLine, _T("mailto:%s?body=%s&subject=%s"), SmsReceiver, SmsContent,

SmsSubject);

  if( ! CreateProcess(szAppName, commandLine, NULL,NULL, FALSE, Create_NEW_CONSOLE, NULL,

NULL, NULL, &procInfo) )
  {
    return FALSE;
  }
  WaitForSingleObject(procInfo.hProcess, INFINITE);

  return TRUE;
}

BOOL LanchSymtemEmailEditor(const TCHAR* EmailAddress, const TCHAR* Subject, const TCHAR*

EmailBody)
{
  TCHAR commandLine[MAX_PATH];
  TCHAR szAppName[MAX_PATH];
  lstrcpy(szAppName, _T("tmail.exe"));

  PROCESS_INFORMATION procInfo;
  if( ! CreateProcess(szAppName, _T("-service \"ActiveSync\""), NULL,NULL, FALSE,

Create_NEW_CONSOLE, NULL, NULL, NULL, &procInfo) )
  {
    return false;
  }

  swprintf(commandLine, _T("mailto:%s?subject=%s&body=%s"), EmailAddress,Subject,

EmailBody);

  if( ! CreateProcess(szAppName, commandLine, NULL,NULL, FALSE, Create_NEW_CONSOLE, NULL,

NULL, NULL, &procInfo) )
  {
    return false;
  }
  WaitForSingleObject(procInfo.hProcess, INFINITE);
  return TRUE;
}

BOOL LanchSystemMMSEditor(const TCHAR* SmsReceiver, const TCHAR* SmsContent, TCHAR*

SmsSubject)
{
  TCHAR commandLine[MAX_PATH];
  TCHAR szAppName[MAX_PATH];
  lstrcpy(szAppName, _T("tmail.exe"));
  PROCESS_INFORMATION procInfo;

  if( ! CreateProcess(szAppName, _T("-service \"MMS\""), NULL,NULL, FALSE,

Create_NEW_CONSOLE, NULL, NULL, NULL, &procInfo) )
  {
    return FALSE;
  }
  swprintf(commandLine, _T("mailto:%s?body=%s&subject=%s"), SmsReceiver, SmsContent,

SmsSubject);

  if( ! CreateProcess(szAppName, commandLine, NULL,NULL, FALSE, Create_NEW_CONSOLE, NULL,

NULL, NULL, &procInfo) )
  {
    return FALSE;
  }
  WaitForSingleObject(procInfo.hProcess, INFINITE);

  return TRUE;

----------------------------------------------------------------------------------------
控制设备进入锁屏状态(转自devdiv)

一个编码方法
// By default, wait 100 milliseconds between key press and release.
const int KEYSIM_DEFWAIT = 100;

// **************************************************************************
//  FUNCTION: void GenKeyEvent( BYTE bVkCode )
//
//  PURPOSE: Simulates a key with virtual key code bVkCode being pressed
//    and released.
// **************************************************************************
void GenKeyEvent( BYTE bVkCode )
{
    // Press the key down
    keybd_event( bVkCode, 0, KEYEVENTF_SILENT, 0 );

    // To make the simulation more realistic, we actually need to wait for
    // a little while before faking the upwards keypresses, since real users
    // won't be lightning fast.
    Sleep(KEYSIM_DEFWAIT);

    // Let go of the key
    keybd_event(bVkCode, 0, KEYEVENTF_SILENT | KEYEVENTF_KEYUP, 0);
}

调用的时候：
GenKeyEvent( VK_KEYLOCK );

[想法]关于STL里面增加BOF迭代器位置的想法

sandy_sp@163.com(sandy1) — Fri,28 Aug 2009 10:51:48 +0800

[想法]关于STL里面增加BOF迭代器位置的想法

STL的容器有一个end()位置，用过的人都知道其代表的并不是容器的最后一个元素，而是最后一个元素之后的位置，即所谓的EOF（套用数据库里面的说法）位置。

然后STL里面却没有一个与EOF对应的BOF位置，即第一个元素之前。begin()指的是第一个元素，却不允许begin()再--。
这样导致的问题就是在写很多遍历算法的时候会很麻烦。因为它导致了++和--的不对称。从某种程度上来说，STL搞一个reverse_iterator这个配接器，其实就是默认了++和--的不对等地位，通过把各种--的迭代转换成++的迭代来缓解这个问题。

但是这毕竟不是一个简洁直白的解决方案，而且也不是任何时候都奏效。

C++：在迭代中删除map的成员

sandy_sp@163.com(sandy1) — Tue,25 Aug 2009 13:37:30 +0800

C++：在迭代中删除map的成员

首先要清楚一点，迭代器相当于是容器上的指针，容器可以自己管理内存，因此迭代器可能失效。
如果你在不知情的情况下使用了失效的迭代器，后果是不可预料的。可能程序立即崩掉，也可能什么事都没有发生。崩掉了算你幸运，因为你至少知道出了问题，不然有你受的。

回到正题，我想说什么呢？
比如：

复制内容到剪贴板程序代码

map theMap;
// add something to theMap...

for(auto iter1 = theMap.begin(); iter1 != theMap.end(); ++iter1)
{
    if(iter1->second == xxx)
   {
        theMap.erase(iter1);  //#1 erase the element ??!!
   }
}

看样子貌似非常正常的一段代码。在一个map中寻找值为xxx的项并删除。
但是实际上这个代码是完全错误的，会导致无法预料的结果。

问题就在#1处。一旦你erase了一个iterator指向的内容，这个iterator就无效了。
这时候你再对这个iterator做任何操作其结果都是未定义的。

那么该怎么办呢？
还好，对于map这种以指针构建起来的容器来说，可以保证一个元素删除了，不影响指向其它元素的迭代器。
因此就可以这样做（《C++Standard Library》上建议的正确做法）：

复制内容到剪贴板程序代码

for(auto iter1 = theMap.begin(); iter1 != theMap.end(); )
{
    if(iter1->second == xxx)
   {
        theMap.erase(iter1++);  //#1
   }else
   {
        ++iter1;
   }
}

这个遍历把迭代器的自增从for头部中取出，丢到循环体中去。#1处，iter1++这个运算先自增，但是却返回了自增前的迭代器的一个临时拷贝。然后这个临时迭代器指向的内容被删除了，但是iter1本身已经自增到下一个位置了，不受影响。

===============================================================
我彻底搓了，居然犯这种低级错误，iterator的位置只有EOF没有BOF……
因此以下的内容作废！有严重bug。
===============================================================

引用内容

但是这个遍历还是有点不好看。毕竟把for头部的递增运算丢到循环体中并不是个漂亮的做法，不够清晰，容易让人疑惑这个循环到底在做什么。而且假如这个循环中有continue之类的语句，就比较郁闷了，因为这样你无法保证循环体里面的那个++iter1执行，迭代就无法进行下去了。难道在每个continue前都加一句++iter1？那也太罗索了，而且容易疏忽，毕竟我只是想删除map中的一个元素而已，没必要让其它地方跟着改啊。局部化局部化，应该把问题放在局部解决不让它扩散。啥地方删除啥地方就地解决，别拖累了其它哥们~~

我是这么做的：

复制内容到剪贴板程序代码

for(auto iter1 = theMap.begin(); iter1 != theMap.end(); ++iter1)
{
    if(iter1->second == xxx)
   {
        --iter1;
        theMap.erase(???);  //#1
   }
}

嗯，在需要删除的地方，先将迭代器后退一步，然后将其下一个内容删掉，这个想法不错，但是#1处那个???处该填什么呢？++iter1？肯定不行啦，iter自己不能往前走了，得要一个临时值。 iter1+1？看起来不错，可惜map的iterator仅仅是个双向迭代器，不支持算数运算。只好自己写临时值了：

复制内容到剪贴板程序代码

for(auto iter1 = theMap.begin(); iter1 != theMap.end(); ++iter1)
{
    if(iter1->second == xxx)
   {
        --iter1;
        auto tmpIter = iter1;
        theMap.erase(++tmpIter);  //#1
   }
}

这样解决问题了。
只是还是有点不够雅观，毕竟还定义了个临时变量。而且在C++0x里面有auto还好办些，C++98/03中可是得写：map::iterator tmpIter = iter1; ……
啊，好麻烦好罗索，而且一旦map变，这里都得跟着变，违背了DRY原则。

于是我就写了个辅助函数，专门用于产生临时值：

复制内容到剪贴板程序代码

template
inline T AutoCopy(const T& val)
{
return val;
}

函数非常简单，就是传入一个参数然后原样不动返回。看似是废话，但是却产生了一个临时右值可以供我们差遣（AutoCopy的“Copy”的寓意），同时利用了模版的自动推导能力，无需再明确指定类型（AutoCopy的“Auto”的寓意），呵呵。
有了它，就可以这么写了：

复制内容到剪贴板程序代码

for(auto iter1 = theMap.begin(); iter1 != theMap.end(); ++iter1)
{
    if(iter1->second == xxx)
   {
        --iter1;
        theMap.erase(++AutoCopy(iter1));  // now it's ok.
   }
}

一个不错的解决方案。
大家还有没有更好的想法？

继续摘录C++中一些细节

sandy_sp@163.com(sandy1) — Fri,21 Aug 2009 16:00:53 +0800

1.关于union中的类型
union内可以包含各种基本数据类型、指针、struct和class等
但是struct 和class是有限制的：
1.不能包含自定义构造/析构函数；
2.不能包含自定义赋值操作符；
3.其成员如果有struct和class的话也不能包含上述东西。
否则的话在编译时会报错。
其实稍稍想下就知道为啥了，union是一种非常低层的数据类型，里面的各个成员都是共用存储空间的。如果包含了构造函数和赋值操作符，则编译器不能保证它们一定会在该调用的地方被调用（它根本就不能确定union中哪个成员正在使用）。而且更可怕的是这些函数之间会彼此冲突，互相覆盖影响，从而导致各种麻烦。

引用B.S的话：

引用内容

         命名联合的定义方式同struct，其中的各个成员将具有同样的地址。联合可以有成员函数，但却不能有静态成员。
          一般来说，编译器无法知道被使用的是联合的哪个成员;也就是说，无法知道存储在联合中的对象的类型。因此，联合就不能带构造函数或析构函数的成员，因为无法保护其中的对象以防止破坏，也不可能保证在联合离开作用域时能调用正确的析构函数。
          最好是仅仅将联合用于底层代码，或者作为某个类的实现中的一部分，由这个类去维护有关在联合中存储着什么的信息。