C++ STL list 的一个问题

catbert

为什么STL的LIST是双向循环链表呢？
“循环”比不循环，而是有一个头一个尾的设计有什么优势呢？
STL用一个头节点，遍历时如果经过必须特别考虑，
所以没有什么方便。

不明白，谢谢！

jaffaz

原帖由 catbert 于 2007-4-24 11:43 发表
为什么STL的LIST是双向循环链表呢？
“循环”比不循环，而是有一个头一个尾的设计有什么优势呢？
STL用一个头节点，遍历时如果经过必须特别考虑，
所以没有什么方便。

不明白，谢谢！

虽然度过它的源代码，不过细节忘了
现在是拿来就用

zwylinux

原帖由 catbert 于 2007-4-24 11:43 发表
为什么STL的LIST是双向循环链表呢？
“循环”比不循环，而是有一个头一个尾的设计有什么优势呢？
STL用一个头节点，遍历时如果经过必须特别考虑，
所以没有什么方便。

不明白，谢谢！

STL 的list只是双向链表而已，没有循环

jaffaz

原帖由 zwylinux 于 2007-4-24 12:13 发表


STL 的list只是双向链表而已，没有循环

有循环哦，我4了一下：

#include <list>
#include <iostream>

using namespace std;

int main(int argc, char * argv[])
{
    list<int> lst;

    for (int i = 0; i < 10; ++i)
        lst.push_back(i);

    list<int>::iterator it = lst.end();
    ++it;
    cout << *it << endl;
    ++it;
    cout << *it << endl;

    return 0;
}

输出

$ ./test
0
1

jaffaz

list基类的定义：

template<typename _Tp, typename _Alloc>
    class _List_base
      : public _List_alloc_base<_Tp, _Alloc,
                                _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
    {
    public:
      typedef _List_alloc_base<_Tp, _Alloc,
                               _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
              _Base;
      typedef typename _Base::allocator_type allocator_type;

      _List_base(const allocator_type& __a)
      : _Base(__a)
      {
        _M_node = _M_get_node();
        _M_node->_M_next = _M_node;
        _M_node->_M_prev = _M_node;
      }

      ~_List_base()
      {
        clear();
        _M_put_node(_M_node);
      }

      void clear();
    };

是头尾相接的链表

zwylinux

哦，之前都没看到哪里有说list是循环的。也没测试过

catbert

这个循环究竟有什么好处讷？

jaffaz

原帖由 catbert 于 2007-4-24 12:57 发表
这个循环究竟有什么好处讷？

对链表首尾不用做特殊处理

catbert

原帖由 jaffaz 于 2007-4-24 00:07 发表

对链表首尾不用做特殊处理

这是指写链表吧？那样写完了就无所谓了。
对于用户来讲，在使用上有什么意义呢？
谢谢！

jaffaz

链表最常用的操作就是插入节点和删除节点了，
不用对链表首尾做特殊处理能提高些效率，实现上也简单些。
stl比较注重效率，我想这个是主要原因。
对于用户来说，尽量不要假设链表是环状的，毕竟文档上没有这个约定，不同版本的stl实现方法可能不一样。

[ 本帖最后由 jaffaz 于 2007-4-26 09:14 编辑 ]