《STL源码剖析》---list容器insert操作的个人理解

系统管理员 2021-12-15 01:01 245阅读 0赞

最近在看STL源码剖析，感觉还是挺深奥的，感觉看不太懂。今天在看list容器这块，讲到了insert操作，便记录一番自己的理解吧。  
 摘抄书上的：

iterator insert (iterator position,const T& x)
    {
         link_type tmp = create_node(x); //产生一个节点（初始化内容为x）
         //调整双向指标，使tmp安插进去
         tmp->next = position.node;
         tmp->prev = position.node->prev;
         (link_type(position.node->prev))->next = tmp;
         position.node->prev = tmp;
         return tmp;
    }

一开始看这个一直看不懂，因为之前学C++的时候，list容器没怎么掌握，现在的话对其具体的认识还是不够的，只是例如：push\_back()等操作知道是干什么。这个insert操作里面的东西一开始不清楚，后来仔细理解了一番不知道是不是对的。

1.

create_node(x)；    //<span style="font-size: 18px; font-family: Arial;">创建一个新的节点这个知道。</span>

2.

tmp->next = position.node;
    position.node->prev = tmp;

这里我的理解是，因为list是双向的。在position的位置插入元素x，现在创建了一个新的节点tmp，其data为x，要实现双向，首先该新节点要链接到下一个节点。因为是在position的位置插入新的元素，因此这个新节点的下一个节点自然而然就是position这个节点，所以：

tmp->next = position.node;

以上操作就是建立tmp与position的链接；然后实现双向，则position的前一个节点需为tmp，所以：

position.node->prev = tmp;

以上操作就使得tmp与position这个位置的节点之间建立了双向链接；

3.

然后就是要实现tmp与position位置节点原来的前一个节点直接实现双向链接，因此就需要：

tmp->prev = position.node->prev; 
    (link_type(position.node->prev))->next = tmp;

首先第一步，position位置节点原来指向的前一个节点，现在转变为tmp指向的前一个，所以：

tmp->prev = position.node->pref;

这样就实现了tmp与前一个节点的单向链接；第二步，position位置节点原来的那个节点与tmp的链接，所以：

(link_type(position.node->prev))->next = tmp;

得到其原先的前一个节点：link\_type(position.node->pref)，然后该节点的next指向tmp。

以上便实现了list容器插入元素并且建立双向链接。个人理解。

转载于:https://www.cnblogs.com/zhong-dev/p/4044583.html

发表评论取消回复

表情：

评论列表（有 0 条评论，245人围观）

还没有评论，来说两句吧...

相关阅读

相关 C++(STL):15--- list源码剖析

一、list概述总的来说：环形双向链表特点：底层是使用链表实现的，支持双向顺序访问在list中任何位置进行插入和删除的速度都

我会带着你远行/ 2022年12月29日 09:53/ 0 赞/ 100 阅读

相关 STL源码剖析——关联容器之multimap

前言 multimap的特性及其用法和map完全相同，唯一的区别就是multimap允许键值key重复，因此multimap的插入操作采用的是底层RB-Tree的ins

╰半橙微兮°/ 2022年08月12日 12:59/ 0 赞/ 141 阅读

相关 STL源码剖析——关联容器之map

前言在SGI STL中的容器map，底层实现机制是RB-Tree，是因为map的操作RB-Tree都能实现，有关RB-Tree的剖析请看《[STL源码剖析——RB-T

悠悠/ 2022年08月12日 12:00/ 0 赞/ 128 阅读

相关 STL源码剖析——关联容器之set

前言在SGI STL中的容器set，其实现基本上是在RB-Tree的基础上，把RB-Tree作为其底层的实现机制，是因为set的操作RB-Tree都能实现，有关RB-

朱雀/ 2022年08月12日 11:30/ 0 赞/ 144 阅读

相关 STL源码剖析——序列容器之list

前言在SGI STL中，list容器是一个循环的双向链表，它的内存空间效率较前文介绍的vector容器高。因为vector容器的内存空间是连续存储的，且在分配内存空间

一时失言乱红尘/ 2022年08月12日 02:59/ 0 赞/ 147 阅读

相关 STL源码剖析——list容器的排序算法sort()

前言由于STL本身的排序算法sort接受的输入迭代器是随机访问迭代器，但是双向list链表容器的访问方式是双向迭代器，因此，不能使用STL本身的排序算法sort，必须

朴灿烈づ我的快乐病毒、/ 2022年08月12日 02:00/ 0 赞/ 148 阅读

相关 STL源码剖析——序列容器之vector

前言在STL编程中，我们最常用到的就是容器，容器可分为序列容器和关联容器；本文记录的是我们经常使用的序列容器之vector，vector的数据安排和操作方式类似于C+

心已赠人/ 2022年08月12日 01:20/ 0 赞/ 163 阅读

相关【STL源码剖析】关联式容器

set map multiset multimap hashtable hash\_set hash\_map hash\_mult

冷不防/ 2022年08月03日 05:27/ 0 赞/ 166 阅读

相关【STL源码剖析】序列式容器

本文重点在于介绍读STL过程中，要注意的知识点。不在于如何使用STL。 vector vector是动态增加大小，当已有空间长度无法满足新的插入时的处理方式并不仅

朱雀/ 2022年08月03日 05:26/ 0 赞/ 125 阅读

相关《STL源码剖析》---list容器insert操作的个人理解

最近在看STL源码剖析，感觉还是挺深奥的，感觉看不太懂。今天在看list容器这块，讲到了insert操作，便记录一番自己的理解吧。摘抄书上的： iterat

系统管理员/ 2021年12月15日 01:01/ 0 赞/ 246 阅读