Home > programming > 非侵入式与侵入式 之 链表

非侵入式与侵入式 之 链表

stl中的std::list想必是一个使用率不低的container, 在这里我们称std::list为非侵入式链表,std::list的用户数据并不拥有其在链表中的位置信息。但是当想要删除已被插入的用户数据的时候,就没有那么方便了。因为使用std::list的时候,链表相关的信息是由std::list来管理的,被插入道std::list的用户数据并不知道自己的位置信息,也就是并不知道prev和next指向的是什么地方。所以如果你想把插入的数据从链表上取下,那么首先你需要找到你的数据在std::list中的位置信息,然后通过操作prev和next指针来达到目的。所以为了删除这个数据,你必须要首先找到这个数据在list中的位置,然后调用list::erase来删除这个用户数据。而查找这个动作的时间复杂度为O(n/2)。那么当你需要频繁插入删除数据并且你需要查找才知道数据所在位置的时候,std::list或许并不是一个特别好的选择。(当然你还有其他选择,那就是记录下你的数据插入到list中的iterator,这样的话就可以略过查找这一步了,不过这个不在讨论范围内。)

这个时候也许你就需要侵入式的链表了,我们先来看一下boost中侵入式链表intrusive list.当然了如果直接使用boost::intrusive::list的erase方法的话,那么和std::list之间没有什么差别。所以我们需要使用auto_unlinkmode.代码如下:

#include <iostream>
#include <boost/intrusive/list.hpp>
using namespace boost::intrusive;
typedef list_base_hook<link_mode<auto_unlink> > auto_unlink_hook;
class MyData: public auto_unlink_hook
{
private:
    int data;
public:
    MyData( int i ):data(i){}
    void show( ) const
    {
        std::cout<<data<<std::endl;
    }
};
int main()
{
    typedef list<MyData,constant_time_size<false> > DataList;
    DataList dl;
    MyData d1(1);   MyData d2(2);   MyData d3(3);
    dl.push_front(d1);  dl.push_front(d2);  dl.push_front(d3);
    d2.unlink();
    DataList::const_iterator it = dl.begin();
    for( ; it != dl.end(); it ++ )
        it->show();
    return 0;
}

可以看到当d2调用unlink以后它自己就从dl中删除了引用。以下是unlink的代码:


static node_ptr unlink(const node_ptr &this_node)
{
  node_ptr next(NodeTraits::get_next(this_node));
  if(next){
     node_ptr prev(NodeTraits::get_previous(this_node));
     NodeTraits::set_next(prev, next);
     NodeTraits::set_previous(next, prev);
     return next;
  }
  else{
     return this_node;
  }
}

由于用户数据记录了自己在list中的位置,所以删除的时候就很方便,也就是略过了查找这一步了。

Categories: programming Tags:
  1. No comments yet.
  1. No trackbacks yet.