Hello world

常用链接

统计

最新评论

2009年11月10日 #

经营你的知识资产 - 摘自《程序员修炼之道》

1.       1. 定期投资。就像金融投资一样,你必须定期为你的知识资产投资。即使投资量很少,习惯本身也和总量一样重要。

2.       2. 多元化 你所知道的不同的事情越多,你就越有价值。作为底线,你需要知道你目前所用的特定技术的各种特性。但不要就此止步。计算机技术的面貌变化很快——今天的热门技术明天可能就变得近乎无用(或至少是不再抢手)。你掌握的技术越多,你就越能更好地进行调整。

3.       3. 管理风险。从高风险、可能有高回报,到低风险、低回报,技术存在于这样一条谱带上。把你所有的金钱都投入到可能突然崩盘的高风险股票并不是一个好主意;你也不应太保守,错过了可能的机会。不要把你所有的技术鸡蛋放在一个篮子里。

4.       4. 低买高卖。在新兴的技术流行之前学习它可能就和找到被低估的股票一样困难,但所得到的就和那样的股票带来的收益一样。在Java刚出现时学习它可能有风险,但对于现在已经步入该领域的顶尖行列的早期采用者,这样做得到了非常大的回报。

5.       5. 重新评估和平衡。这是一个非常动荡的行业。你上个月开始研究的热门技术也许现在已经像石头一样冰冷。也许你需要重温你有一阵子没有使用的数据库技术。又或许,如果你之前试用过另外一种语言,你就会更有可能获得那个新职位。。。

posted @ 2009-11-10 19:26 Johnson 阅读(113) | 评论 (0)编辑 收藏

2009年10月14日 #

小心删除容器中元素时的迭代器失效

 

 从一个简单的问题开始,删除数组中某个元素后连续重复的元素,例如 1,1,2,3,3,1,1,1,4,0 ---> 1, 2,3,1,4,0。

考虑了几秒,然后就开始动手写代码了:

#include <iostream>
#include 
<vector>
using namespace std;

int main(int argc, char* argv[])
{
   
int a[] = {11333241110};
   
int size = sizeof(a)/sizeof(a[0]);

   vector
<int> vec(a, a+size);

   vector
<int>::iterator iter, end;
   
int previous = vec[0];
   
for (iter = vec.begin() + 1, end = vec.end(); iter != end; ++iter)
   
{        
      
if(*iter == previous)
      
{
         vec.erase(iter);
      }

      
else
      
{
         previous 
= *iter;
      }
    
   }


   
for(iter = vec.begin(); iter != vec.end(); ++iter)
   
{
      cout 
<< *iter << endl;
   }

   
   
return 0;
}


可是编译一下,出来一大堆error,仔细看一下出错信息,哦,原来自己忘记了,erase容器中元素的时候,迭代器会失效。。。顿时一身冷汗,自己平时迭代容器的时候,一般都保存了容器的end元素,要是此时迭代器失效。。。

Container<int>::iterator iter, end;
for (iter = container.begin() + 1, end = container.end(); iter != end; ++iter)


于是找到收藏的Effective STL,翻开条款9,找到了erase容器中元素的原则。以前曾经看过,不过年深日久,早就忘得一干二净了。现在还是把要点总结一下,记在blog上,供以后参考。

1. 对于关联容器(如map, set, multimap,multiset),删除当前的iterator,仅仅会使当前的iterator失效,只要在erase时,递增当前iterator即可。这是因为map之类的容器,使用了红黑树来实现,插入、删除一个结点不会对其他结点造成影响。

for (iter = cont.begin(); it != cont.end();)
{
   (
*iter)->doSomething();
   
if (shouldDelete(*iter))
      cont.erase(iter
++);
   
else
      
++iter;
}

因为iter传给erase方法的是一个副本,iter++会指向下一个元素。

2. 对于序列式容器(如vector,deque),删除当前的iterator会使后面所有元素的iterator都失效。这是因为vetor,deque使用了连续分配的内存,删除一个元素导致后面所有的元素会向前移动一个位置。还好erase方法可以返回下一个有效的iterator。

for (iter = cont.begin(); iter != cont.end();)
{
   (
*it)->doSomething();
   
if (shouldDelete(*iter))
      iter 
= cont.erase(iter); 
   
else
      
++iter;
}

3. 对于list来说,它使用了不连续分配的内存,并且它的erase方法也会返回下一个有效的iterator,因此上面两种方法都可以使用。


最后给出开始那个问题的一个正确的实现:

#include <iostream>
#include 
<vector>
using namespace std;

int main(int argc, char* argv[])
{
   
int a[] = {11333241110};
   
int size = sizeof(a)/sizeof(a[0]);

   vector
<int> vec(a, a+size);

   vector
<int>::iterator iter = vec.begin();
   
int previous = *iter;
   
++iter;
   
for (; iter != vec.end();)
   
{        
      
if(*iter == previous)
      
{
         iter 
= vec.erase(iter);
      }

      
else
      
{
         previous 
= *iter;
         
++iter;
      }
    
   }


   
for(iter = vec.begin(); iter != vec.end(); ++iter)
   
{
      cout 
<< *iter << endl;
   }

   
   
return 0;
}

PS. 不过实际上这个问题,用vector来实现不是很适合,因为每次删除一个元素,都会引起vector的一个resize操作。resize的时间复杂度是O(n),整个的resize操作要花费O(n^2)。最好是选择list最为容器,list最适合那些需要在容器中间做插入、删除的例子。

PS2. 另外一个可能的方法是remove_if + erase惯用法。remove_if的时间复杂度是O(n). erase的时间复杂度也是O(n),所以整个操作可以在O(n)时间里完成。(当然,对于这个例子,ShouldDeletePred比较难写)

iterator new_end = remove_if(array.begin(), array.end(), ShouldDeletePred());
array.erase(new_end, array.end());

posted @ 2009-10-14 19:47 Johnson 阅读(7425) | 评论 (3)编辑 收藏

仅列出标题