chromium中的LinkedList

为什么使用LinkedList而不是std::list? 使用LinkedList最大的理由是性能。一般来说std:list的erase操作的时间复杂度是O(n),因为std:list要遍历容器获得删除元素的迭代器。 而LinkedList的erase操作的时间复杂度是O(1),因为它直接用LinkNode的RemoveFromList方法去删除。 为什么LinkedList不跟std::list一样需要遍历迭代器呢?这是因为LinkedList中的元素不是复制到到容器中的,LinkedList中存放的是元素的指针,所以元素本身就可以调用RemoveFromList把自己从容器中删除。这个特性带来的另外一个好处:插入新元素的时候,LinkedList不需要从heap中分配内存。 LinkedList就是对元素指针进行简单的封装管理,优点是没有对管理的元素有复制操作,元素加入到容器,元素本身跟放入容器中的元素是一样的。 使用LinkedList 使用LinkedList前,需要用LinkNode把栈中的元素封装起来。如下: MyStruct就是我们要放入LinkedList中管理的真正数据类型。 LinkedList可以管理栈中的元素,也可以管理堆中的元素。  注意 不能从一个函数中返回LinkedList<MyNodeType>,因为LinkedList.root_已经失效。 总结 总体来说使用LinkedList还是挺繁琐的,应用场景也比较特殊,而且不能使用stl中那些标准的算法。所以除非为了追求极致的性能,还是推荐使用std::list。 LinkedList代码: ... Read More | Share it now!