注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

gmd20的个人空间

// 编程和生活

 
 
 

日志

 
 

C++ std list 是可以做到像linux 内核的list一样O(1)复杂度把元素从链表里面删掉的(std iterator的用法)  

2012-06-14 17:51:06|  分类: 程序设计 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

之前不知道iterator 还可以这样使用啊,搞到我想自己写了类似Linux内核的一个list的实现。

可以把 list<Request*>::iterator   其实就是链表节点来的,整个list的其他元素的添加删除不会影响到你这个iterator 的。所以插入元素到list容器的时候,顺便把:iterator  这个也保存到元素自己一个子变量。然后需要删除的时候,根据iterator来删除就可以了。

vector那些的iterator 类似普通的数组指针,但vector会自动重新分配内存,所以插入元素字号后,以前的iterator 可能无效了,但list应该没有这个问题。 这个 stl 不理解底下实现细节,也不能写出好看的代码来啊。像不同的容器 的iterator  的行为就差别很大,最好写个简单代码,跟踪一下,看看到底都怎么实现的才行。


下面 的示例代码,用list来做queue使用的。
struct Request {
list<Request*>::iterator  pos;
int data;
};
----------
  list<Request *> queue;
  for( int i=0; i<10; i++ ) {
Request * req = new Request();
req->data = i;
queue.push_back (req);
req->pos = --queue.end();
  }

  list<Request*>::iterator  list_it =  queue.begin();
 
  while(list_it != queue.end()) {
Request * req = *list_it;
if (req->data  == 8 )
{
queue.erase(req->pos);
break;
}  
list_it ++;
  }
   
  list_it =  queue.begin(); 
  while(list_it != queue.end()) {
Request * req = *list_it;
cout << " " << req->data;
list_it ++;
  }
  评论这张
 
阅读(898)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017