C#和.Net框架

容器list

• List是一个双端队列

  gcc2.9中list的类图

  

gcc2.9中list的成员变量

template<class T, class Alloc = alloc>
class list {
protected:
    typedef __list_node<T> list_node;
public:
    typedef list_node *link_type;
    typedef __list_iterator<T, T &, T *> iterator;
protected:
    link_type node;
};

template<class T>
struct __list_node {
    typedef void *void_pointer;
    void_pointer prev;
    void_pointer next;
    T data;
};

实现细节

• 为实现前闭后开的特性,在环形链表末尾加入一个用以占位的空节点,并将迭代器list::end()指向该节点.

---

• 对于链表的迭代器的++,--,->,*等操作都是运算符重载.
  • 还定义了iterator_category、value_type、difference_type、pointer和pointer5个关联类型(associated types),这些特征将被STL算法使用.

template<class T, class Ref, class Ptr>
struct __list_iterator {
    typedef __list_iterator<T, Ref, Ptr> self;
    typedef bidirectional_iterator_tag     iterator_category;     // 关联类型1
    typedef T                             value_type;            // 关联类型2
    typedef ptrdiff_t                     difference_type;    // 关联类型3
    typedef Ptr                         pointer;            // 关联类型4
    typedef Ref                         reference;            // 关联类型5

    typedef __list_node <T>*            link_type;
    link_type node;        // 指向的链表节点



    reference operator*() const { return (*node).data; }
    //*ite -> 调用 -> (*ite).dta;

    pointer operator->() const { return &(operator*()); }
    //ite->method() -> 调用 -> (&(*ite))->method();
    //注意对于 -> 运算符,他们一直向后传递一直到可以停止为止

    self& operator++() {
        node = (link_type) ((*node).next);
        return *this;
    }
    //这里是前置++

    self operator++(int) {
        self tmp = *this;
        ++*this;
        return tmp;
    }
    //注意这里后置++中第79行先调用 __list_iterator(const iterator& x) : node(x.node) 的拷贝构造函数,而*this为传入的参数
};

---

• 注意在这里前置++运算符返回左值,而后置++返回右值,这与基础类型的++和—运算一致.
  • 需要强调的是(i++)++的后置++返回的是右值(临时),不能再对其后置++.
    ```cpp
    int i(6);
    i++++; // 被解析为 ++(++i), 能通过编译
    ++++i; // 被解析为 (i++)++, 不能通过编译

list c;
auto ite = c.begin();
++++ite; // 被解析为 ++(++ite), 能通过编译
ite++++; // 被解析为 (ite++)++, 不能通过编译
```

gcc4.9版本list