侯捷STL课程及源码剖析学习3: 深度探索容器list

一、容器概览

　　上图为 GI STL 2.9的各种容器。图中以内缩方式来表达基层与衍生层的关系。所谓的衍生，并非继承（inheritance）关系，而是内含（containment）关系。例如 heap 内含一个 vector，priority-queue 内含一个 heap，stack 和 queue 都含一个 deque，set/map/multiset/multimap 都内含一个 RB-tree，hast_x都内含一个 hashtable.

二、序列式容器（sequential containers）

所谓序列式容器，其中的元素都可序（ordered），但᳾排序（sorted）。C++ 语言本身提供了一个序列式容器array，STL另外再提供vector,list,deque, stack,queue,priority-queue等等序列式容器。其中stack和queue由于只是将deque改头换面而成，技术上被归类为一种适配（adapter）。

list 容器

文件依赖结构图

list概览

list 内实现了其迭代器(G2.9)

注意操作符++重载

　　虽然iterator也重载operator*(), 但是这里面的*this并没有使用这个重载；例如self tmp = *this, return *this;这两次*this已经被解释为拷贝构造的参数了 ++*this也没有使用重载的operator*();也是已经把*this解释成了operator++()的参数了

简化修改代码

 #include <iostream>

 #include <cstdio>

 namespace sk

 {

     template <class T>

 struct __list_node {

   typedef void* void_pointer;

   void_pointer next;

   void_pointer prev;

   T data;

 };

 template<class T, class Ref, class Ptr>

 struct __list_iterator {

   typedef __list_iterator<T, T&, T*>             iterator;

   typedef __list_iterator<T, const T&, const T*> const_iterator;

   typedef __list_iterator<T, Ref, Ptr>           self;

   typedef T value_type;

   typedef Ptr pointer;

   typedef Ref reference;

   typedef __list_node<T>* link_type;

   typedef size_t size_type;

   link_type node;

   __list_iterator(link_type x) : node(x) { printf("__list_iterator(link_type x) \n"); }

   __list_iterator() { printf("__list_iterator() \n"); }

   __list_iterator(const iterator& x) : node(x.node) {printf("__list_iterator(const link_type x) \n");}

   bool operator==(const self& x) const { return node == x.node; }

   bool operator!=(const self& x) const { return node != x.node; }

   reference operator*() const {  printf(" operator*() \n");return (*node).data; }

 #ifndef __SGI_STL_NO_ARROW_OPERATOR

   pointer operator->() const { return &(operator*()); }

 #endif /* __SGI_STL_NO_ARROW_OPERATOR */

   self& operator++() {

       printf("prev ++ \n");

     node = (link_type)((*node).next);

     return *this;

   }

   self operator++(int) {

        printf("post ++ \n");

     self tmp = *this;

     ++*this;

     return tmp;

   }

   self& operator--() {

     node = (link_type)((*node).prev);

     return *this;

   }

   self operator--(int) {

     self tmp = *this;

     --*this;

     return tmp;

   }

    void operator=(const self &test)

      {

          printf("operator=\n");

      }

 };

 }

 typedef sk::__list_iterator<int,int&,int*>

     list_iterator_int;

 list_iterator_int

 testassign(list_iterator_int t)

 {

     return t;

 }

 int main()

 {

     sk::__list_node<int> node1;

     sk::__list_node<int> node2;

     sk::__list_node<int> node3;

     sk::__list_node<int> node4;

     sk::__list_node<int> node5;

     node1.next = &node2;

     node2.next = &node3;

     node3.next = &node4;

     node4.next = &node5;

     node2.prev = &node1;

     node3.prev = &node2;

     node4.prev = &node3;

     node5.prev = &node4;

     sk::__list_iterator<int,int&,int*> iter1;

     iter1.node = &node2;

     printf("-------------------iter1++----------------------\n");

     iter1++;

     printf("-------------------++iter1----------------------\n");

     ++iter1;

     printf("\n");

     printf("-------------------1----------------------\n");

     list_iterator_int iter_test;

     printf("-------------------2----------------------\n");

     iter_test = iter1;

     printf("-------------------3----------------------\n");

     list_iterator_int iter2 = iter1;

     printf("-------------------4----------------------\n");

     iter_test = testassign(iter1);

     printf("-------------------5----------------------\n");

     testassign(iter1);

     printf("------------------------------------------\n");

     return ;

 }

test

测试结果

传参的过程中，要调用一次复制构造函数: iter1入栈时会调用复制构造函数创建一个临时对象，与函数内的局部变量具有相同的作用域.
函数返回值时，也会构造一个临时对象；调用重载赋值操作符赋值给iter_test.

内容参考整理：侯捷STL课程

巴特西

侯捷STL课程及源码剖析学习3: 深度探索容器list

一、容器概览

二、序列式容器（sequential containers）

list 容器

最新文章

热门文章