STL源码剖析（九）序列式容器之list

以你之姓@ 2023-08-17 16:22 61阅读 0赞

# STL源码剖析（九）序列式容器之list #

### 文章目录 ###

*  STL源码剖析（九）序列式容器之list
 *   *  一、list的数据结构
     *  二、list的迭代器
     *  三、list的操作
     *   *  3.1 构造函数
         *  3.2 析构函数
         *  3.3 添加元素
         *  3.4 删除元素
         *  3.5 其他操作

## 一、list的数据结构 ##

`list`的底层是一个双向链表，下面来看一看list的数据结构

template <class T, class Alloc = alloc>
    class list {
    	typedef __list_node<T> list_node; //节点
    	typedef list_node* link_type; //链接节点
    	
    	typedef simple_alloc<list_node, Alloc> list_node_allocator; //空间配置器
    	
    	typedef __list_iterator<T, T&, T*>             iterator; //迭代器
    	
    protected:
    	link_type node; //成员
    	
    };

`list`内部的成员只有`link_type node`，其类型为`list_node*`，表示链表中的一个节点

下面来看一看`list_node`的定义

template <class T>
    struct __list_node {
      typedef void* void_pointer;
      void_pointer next; //指向下一个元素的指针
      void_pointer prev; //指向上一个元素的指针
      T data; //数据
    };

`list_node`的数据结构非常简单，包含两个指针，还有数据，如下

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70]

`list`内部是一个双向链表，它的成员变量`node`是链表头，其维护的数据结构如下

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 1]

## 二、list的迭代器 ##

list的迭代器定义如下

template<class T, class Ref, class Ptr>
    struct __list_iterator {
    	/* 遵守STL迭代器规范，需要定义这5个类型 */
    	typedef bidirectional_iterator_tag iterator_category; //双向迭代器
    	typedef T value_type;
    	typedef Ptr pointer;
    	typedef Ref reference;
    	typedef ptrdiff_t difference_type;
    	
    	typedef __list_node<T>* link_type; //链表的节点	
    
    	link_type node; //节点指针
    };

list的迭代器含有一个节点指针，指向list维护的链表中的某个节点

看以下list迭代器的自增操作

self& operator++() { 
        node = (link_type)((*node).next); //迭代器的node指针指向链表下一个元素
        return *this;
    }

再看一看取值操作

reference operator*() const { return (*node).data; } //返回所指节点中的数据值

list迭代器的示意图如下

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 2]

## 三、list的操作 ##

在清楚list的数据结构及其迭代器后，我们来看一看list容器的各项操作

### 3.1 构造函数 ###

**默认构造函数**

void empty_initialize() { 
        node = get_node(); //分配内存
        node->next = node;
        node->prev = node;
    }
    
    list() { empty_initialize(); }

`node`是list中的链表头节点，当默认构造的时候，list里面没有元素，所以初始化一个链表头，首先分配内存，然后将首尾指针指向自己

**拷贝构造**

template <class InputIterator>
    void range_initialize(InputIterator first, InputIterator last) {
    	empty_initialize(); //初始化链表头
    	insert(begin(), first, last); //出入所有元素
    }
    
    list(const list<T, Alloc>& x) {
        range_initialize(x.begin(), x.end());
    }

list的拷贝构造会调用`range_initialize`，`range_initialize`函数会先初始化list的链表头，然后再通过`insert`来复制所有的节点，下面来看一看`insert`

template <class T, class Alloc>
    void list<T, Alloc>::insert(iterator position, const T* first, const T* last) {
      for ( ; first != last; ++first)
        insert(position, *first);
    }

list的insert函数会从头到尾，调用全局函数insert来插入，其定义如下

iterator insert(iterator position, const T& x) {
        link_type tmp = create_node(x); //分配内存
        
        /* 双向链表插入元素的过程 */
        tmp->next = position.node;
        tmp->prev = position.node->prev;
        (link_type(position.node->prev))->next = tmp;
        position.node->prev = tmp;
        return tmp;
    }

insert首先会分配一个节点，然后插入双向链表中

### 3.2 析构函数 ###

list的析构函数如下

~list() {
        clear();
        put_node(node);
    }

`clear`的作用是清楚除头节点外的所有节点，其定义如下

template <class T, class Alloc> 
    void list<T, Alloc>::clear()
    {
      link_type cur = (link_type) node->next; //得到第一个元素
      while (cur != node) { //遍历链表
        link_type tmp = cur;
        cur = (link_type) cur->next; //从链表删除节点
        destroy_node(tmp); //释放节点
      }
      node->next = node;
      node->prev = node;
    }

`clear`函数会遍历整个链表，将每个元素从链表中删除，然后释放它，`destroy_node`的定义如下

void destroy_node(link_type p) {
        destroy(&p->data); //析构对象
        put_node(p); //释放节点
    }

`destroy_node`首先通过`destroy`析构对象，然后通过`put_node`释放内存，`put_node`定义如下

/* 通过空间配置器释放内存 */
    void put_node(link_type p) { list_node_allocator::deallocate(p); }

### 3.3 添加元素 ###

可以通过`insert`和`push_front`还有`push_back`插入元素

`insert`表示在指定位置插入节点，上面已经讨论过了，这里不讨论了，下面来看一看`push_front`和`push_back`

`push_front`表示在链表头插入节点，其定义如下

void push_front(const T& x) { insert(begin(), x); }

`push_back`表示在链表尾插入节点

void push_back(const T& x) { insert(end(), x); }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 3]

### 3.4 删除元素 ###

可以通过`erase`、`pop_front`、`pop_back`删除节点

`erase`删除指定节点，`pop_front`删除链表第一个节点，`pop_back`删除链表最后一个节点

`erase`的定义如下

iterator erase(iterator position) {
        /* 双向链表删除节点的过程 */
        link_type next_node = link_type(position.node->next);
        link_type prev_node = link_type(position.node->prev);
        prev_node->next = next_node;
        next_node->prev = prev_node;
        
        destroy_node(position.node); //释放节点
        
        return iterator(next_node);
      }

首先将指定节点从双向链表中删除，然后调用`destroy_node`析构还有释放节点

`pop_front`定义如下

void pop_front() { erase(begin()); }

`pop_back`定义如下

void pop_back() { 
        iterator tmp = end();
        erase(--tmp);
    }

end()指向的是最后一个节点的下一个位置，所以需要–才能得到最后一个节点

### 3.5 其他操作 ###

**begin**

返回指向第一个元素的迭代器

iterator begin() { return (link_type)((*node).next); }

返回第一个元素节点的指针，会通过隐式转换将其转换成`iterator`类型

**end**

返回指向最后一个元素的下一个元素的迭代器

iterator end() { return node; }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70]: /images/20230810/eda22e63889e41609eee14498a260a5e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 1]: /images/20230810/ef1664894107439f8c462d014eee23f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 2]: /images/20230810/50ccbedc3c0b47dbafb1b853044b704f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 3]: /images/20230810/fbc56d1a15c541dfa74ba3069e8326e2.png