个人中心
gpt4 book ai didi

C++模拟实现list功能

转载 作者：qq735679552 更新时间：2022-09-27 22:32:09 39 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章C++模拟实现list功能由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

努力的最大好处，就在于你可以选择你想要的生活，而不是被迫随遇而安.

C++模拟实现list功能

list介绍

1、 list是可以在**常数范围O(1)**内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代，但list容器不适合用来做排序。 2、list的底层是一个循环双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素.

构造函数

在C++98中list的构造函数加上拷贝构造函数为如下四个。下面我们就模拟实现这里的全部的构造函数。当然我们这里并没有像标准库一样使用空间配置器来创建空间，使用的是new运算符，但原理都是创建一块新的空间.

C++模拟实现list功能

无参构造函数

这里我们模拟默认的构造函数，默认值为T()，其含义为：该类型的默认值int类型就为0，char类型为'\0',自定义类型会调用其构造函数来初始化这个匿名对象得到默认值.

?
1
2
3
4
5
6
list()      //无参默认构造函数
{
     this ->m_head = new node(T());
     this ->m_head->m_next = this ->m_head;   //创建头结点，并让头结点的头尾相连形成循环结构
     this ->m_head->m_prev = this ->m_head;
}

有参构造函数

?
1
2
3
4
5
6
7
8
9
10
list( size_t size, const T& val=T()) //n个元素构造函数
{
     this ->m_head = new node(T());    //创建头结点，并让头结点的头尾相连形成循环结构
     this ->m_head->m_next = this ->m_head;
     this ->m_head->m_prev = this ->m_head;
     while (size--)
     {
         this ->push_back(val);
     }
}

注意:

1、该构造函数知道其需要用于存储n个数据的空间，所以我们使用new运算符开辟好空间，后用push_back()函数来尾插入val值。 2、该构造函数还需要实现两个重载函数，如果不实现其重载函数，会导致本来想调用n个元素构造函数时，编译器会调用到我们下面要模拟实现的模板区间构造函数.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
list( long size, const T& val = T()) //n个元素构造函数
{
     assert (size > 0);
     this ->m_head = new node(T());    //创建头结点，并让头结点的头尾相连形成循环结构
     this ->m_head->m_next = this ->m_head;
     this ->m_head->m_prev = this ->m_head;
     while (size--)
     {
         this ->push_back(val);
     }
}
 
list( int size, const T& val = T())  //n个元素构造函数
{
     assert (size > 0);
     this ->m_head = new node(T());    //创建头结点，并让头结点的头尾相连形成循环结构
     this ->m_head->m_next = this ->m_head;
     this ->m_head->m_prev = this ->m_head;
     while (size--)
     {
         this ->push_back(val);
     }
}

可以看到，这两个重载函数与之不同的就是其参数size的类型不同，但这却是必要的，否则当我们使用以下代码时，编译器会优先与模板区间构造函数相匹配.

?
1
ZJ::list< int >L(2,1);  //不实现重载版本会调用到模板区间构造函数

并且因为构造函数2当中对参数first和last进行了解引用(*)（而int类型不能进行解引用操作）而报错.

模板区间构造函数

最后就是我们上面一直说到的模板区间构造函数了，因为该迭代器区间可以是其他容器的迭代器区间，该函数接收到的迭代器的类型是不确定的，所以我们这里需要将该构造函数设计为一个函数模板，在函数体内将该迭代器区间的数据一个个尾插到容器当中即可.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template < class InputIterator>
list(InputIterator first, InputIterator last)       //区间构造
{
     this ->m_head = new node(T());    //创建头结点
     this ->m_head->m_next = this ->m_head;
     this ->m_head->m_prev = this ->m_head;
     while (first != last)
     {
         node* newnode = new node(*first);
         node* tail = this ->m_head->m_prev;
         tail->m_next = newnode;
         newnode->m_prev = tail;
         newnode->m_next = this ->m_head;
         this ->m_head->m_prev = newnode;
         ++first;
     }
}

注意:

1、该区间必须是前闭后开[obj.begin()，obj.end());

拷贝构造函数

拷贝构造的思想是我们是很容易想到的，就是遍历一遍我们要拷贝的对象obj链表，并将obj每个元素的值给this对象的每一个对应的结点，并将其每个结点都链接起来.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
list( const list<T>& obj)      //拷贝构造函数
{
     this ->m_head = new node(T());    //创建头结点，并让头结点的头尾相连形成循环结构
     this ->m_head->m_next = this ->m_head;
     this ->m_head->m_prev = this ->m_head;
     const_iterator it = obj.begin();
     while (it != obj.end())
     {
         node* newnode = new node(it.m_pnode->m_val); //创建新结点并把值赋予给它
 
         node* tail = this ->m_head->m_prev;
         tail->m_next = newnode;
         newnode->m_prev = tail;
         newnode->m_next = this ->m_head;
         this ->m_head->m_prev = newnode;
         ++it;
     }
}

赋值运算符重载

根据我们之前的博客的往历，这里我们采用现代写法，及用obj调用拷贝构造函数创建一个临时对象temp，并将temp与我们的this指针指向的对象的指针交换即可.

?
1
2
3
4
5
6
7
8
9
list<T>& operator=( const list<T>& obj)      //赋值运算符重载
{
     if ( this != &obj)   //防止自我赋值
     {
         list<T>temp(obj);
         this ->swap(temp);
     }
     return * this ;       //返回自己
}

注意:

1、上面的temp临时对象出了if语句时就会自动调用析构函数进行释放内存，故不会造成内存的泄漏等问题。

析构函数

析构函数这里，我就有点偷懒啦，复用了我们下面要模拟实现的pop_front()函数，大致思路就是从头到尾一个一个删除结点，并把头结点也删除并至空.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
~list()     //析构函数
{
     iterator it = this ->begin();
 
     while (it != this ->end())    //复用我们写的头删，一个一个的删除，当然也可以复用尾删pop_back()和erase()
     {
         ++it;
         this ->pop_front();
     }
 
     delete this ->m_head;
     this ->m_head = nullptr;
}

迭代器

在C++中我们的迭代器有如下几种:

C++模拟实现list功能

下面我只模拟begin()和end()迭代器.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
iterator begin()
{
     return iterator( this ->m_head->m_next);
}
 
const_iterator begin()  const
{
     return const_iterator( this ->m_head->m_next);
}
 
iterator end()
{
     return iterator( this ->m_head);
}
 
const_iterator end()    const
{
     return const_iterator( this ->m_head);
}

上面我们模拟实现了我们的迭代器，并且有普通迭代器和const迭代器。但是我们还要了解迭代器的原理是上面，在之前我们的博客中我们说过并不是每个迭代器都是原生指针，其中我们的list就是封装了一个指针变量来达到实现iterator的结果.

?
1
2
typedef list_iterator<T,T&,T*> iterator;      //普通迭代器
typedef list_iterator<T, const T&, const T*> const_iterator;    //常量迭代器

可能有人会疑惑，上面这两个迭代器不都差不多嘛，只是名字不一样，为什么不直接在类型上加const，而是在模板参数上指定加上const属性呢？我们要知道由于const对象只能调用常函数，但是平时我们使用std::list时是不是可以支持 ++、-- 呢？如果是const对象，它只能调用常函数，一旦加上变成const函数，那我们的const迭代器就不能进行++、–、' * '等,而我们要达到的效果是可以进行++、–等，但仅仅是不能其元素的值而已。所以 我们这里封装了一个模板指针。我们通过模板的参数不同来控制它的读取操作.

迭代器构造函数

就是将一个指针传过来，并赋给我们的成员变量m_pnode.

?
1
2
3
list_iterator(node* pnode)
             :m_pnode(pnode)
         {}

迭代器关系运算符重载

因为我们要实现迭代器的相关遍历操作例如下面的代码:

?
1
2
ZJ::list< int >::iterator it = L1.begin();
it != L1.end()
?
1
2
3
4
5
6
7
8
9
bool operator!=( const myself&obj) const     //重载！=号
{
     return this ->m_pnode != obj.m_pnode;
}
 
bool operator==( const myself& obj) const    //重载==号
{
     return this ->m_pnode == obj.m_pnode;
}

迭代器++ --运算符重载

其中下面返回的myself类型其实就是我们的迭代器这个类的类型，只是我们将其typedef了一下代码如下:

?
1
typedef list_iterator<T, Ref, Ptr>myself;

这里重载的前置与后置要分别开来，后置需要使用int占位符来占位，不然会发生错误.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
myself& operator++()        //重载前置++
{
     //由于我们的list是双向循环链表，我们的++，就是指向下一个结点
     this ->m_pnode = this ->m_pnode->m_next;
     return * this ;
}
 
myself operator++( int )      //重载后置++
{
     const myself temp(* this );
     this ->m_pnode = this ->m_pnode->m_next;
     return temp;
}
 
myself& operator--()        //重载前置--
{
     //由于我们的list是双向循环链表，我们的--就是得到它上一个结点的迭代器
     this ->m_pnode = this ->m_pnode->m_prev;
     return * this ;
}
 
myself operator--( int )      //重载后置--
{
     const myself temp(* this );
     this ->m_pnode = this ->m_pnode->m_prev;
     return temp;
}

迭代器 * 运算符重载

由于我们知道Ref是由两种类型的，一种是T&,另一种是const T&,所以当我们的对象是const对象时，我们可以控制它不让其修改.

?
1
2
3
4
Ref operator* ()        //重载  *
{
     return this ->m_pnode->m_val;
}

迭代器 -> 运算符重载

为什么要重载->运算符呢？这是因为如果我们list中存储的是自定义类型时，我们的迭代器无法使用->去得到其成员.

?
1
2
3
4
Ptr operator->()     //重载 ->
{
     return & this ->m_pnode->m_val;
}

总结

到了这里可能会有人会问为什么我们不写迭代器的拷贝构造函数和析构函数呢？ 答：这是因为我们的迭代器是用来遍历容器中的部分或全部元素，每个迭代器对象代表容器中的确定的地址，并且这些结点元素析构和拷贝并不归我们管，结点应该归我们的list管，所以编译器默认提供的浅拷贝就已经足够了.

容量相关函数

empty()

功能：是用来获取容器中是否为空。 返回值：bool.

?
1
2
3
4
bool empty()    const       //判空
{
     return this ->begin() == this ->end();  //就是begin()与end()同时指向头结点时的情况
}

size() 

功能：是用来获取元素的个数。 返回值：size_t(无符号整型)。 注意：但是在链表中这个接口并不常用。如果频繁的调用该接口会造成性能的下降.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//遍历一遍链表来得到元素个数，为什么使用遍历一遍链表呢？
//这是因为我们使用链表时很少会去知道它的元素个数，但如果频繁的调用该接口会造成性能的下降
//此时我们应该在list类中将增加一个记录元素个数的变量size
//如果有元素插入就增加，删除就减少
size_t size()   const   //获得元素个数
{
     size_t size = 0;
     const_iterator it = this ->begin();
     while (it!= this ->end())
     {
         ++it;
         ++size;
     }
     return size;
}

元素访问相关函数

back()

  • 功能：获取最后一个元素的值。
  • 返回值：存储的类型的引用。
?
1
2
3
4
5
6
7
8
9
10
11
T& back()
{
     assert (! this ->empty());
     return this ->m_head->m_prev->m_val;
}
 
const T& back()   const
{
     assert (! this ->empty());
     return this ->m_head->prev->m_val;
}

front() 

  • 功能：获取第一个元素的值。
  • 返回值：存储的类型的引用。
?
1
2
3
4
5
6
7
8
9
10
11
T& front()
{
     assert (! this ->empty());
     return  this ->m_head->m_next->m_val;
}
 
const T& front() const
{
     assert (! this ->empty());
     return this ->m_head->m_next->m_val;
}

修改相关函数

push_back()

  • 功能：在尾部插入一个元素。
  • 返回值：void（无返回值）。
?
1
2
3
4
5
6
7
8
9
void push_back( const T& val)    //尾插
{
     node* tail = this ->m_head->m_prev;    //指向尾部结点
     node* newnode = new node(val);      //创建新结点
     newnode->m_next = tail->m_next;       //将新结点的m_next指向头结点
     newnode->m_prev = tail;              //将新结点m_prev指向tail结点
     tail->m_next = newnode;              //并将原来的尾结点的m_next指向newnode
     this ->m_head->m_prev = newnode;       //并将头结点的m_prev指向新的尾
}

push_front() 

  • 功能：在头部插入一个元素。
  • 返回值：void（无返回值）。
?
1
2
3
4
5
6
7
8
9
void push_front( const T& val)   //头插
{
     node* newnode = new node(val);  //创建新结点
     node*  next = this ->m_head->m_next;   //指向第一个结点
     newnode->m_next = next;      //将创建的新结点newnode的m_next指向我们原来的第一个元素next
     this ->m_head->m_next = newnode;   //在将我们的头结点的m_next指向新创建的结点
     newnode->m_prev = this ->m_head;   //在将新结点的m_prev指向头结点
     next->m_prev = newnode;  //在将原先第一个结点元素的m_prev指向新创建的结点
}

pop_back()

  • 功能：在尾部删除一个元素。
  • 返回值：void（无返回值）。
?
1
2
3
4
5
6
7
8
9
10
11
void pop_back()     //尾删
{
     assert (!empty());   //断言 如果list已经为空，则删除不了
     node* tail = this ->m_head->m_prev;    //先找到我们要删除的尾结点
     node* prev = tail->m_prev;       //再找到要删除的尾结点的前一个结点
     this ->m_head->m_prev = prev;  //将头结点的m_prev指向新的尾prev
     prev->m_next = this ->m_head;  //再将prev的m_next指向头结点
     tail->m_next = tail->m_prev = nullptr;    //把要删除的元素的成员至nullptr
     tail->m_val = T();       //将要删除的元素的值置为匿名对象的默认值
     delete tail;            //删除尾结点
}

pop_front()

  • 功能：在头部删除一个元素。
  • 返回值：void（无返回值）。
?
1
2
3
4
5
6
7
8
9
10
11
void pop_front()    //头删
{
     assert (!empty());   //断言 如果list已经为空，则删除不了
     node* delnode = this ->m_head->m_next; //先找到我们要删除的第一个结点位置
     node* next = delnode->m_next;            //在找到删除结点的下一个结点的位置
     this ->m_head->m_next = next;          //再将头结点的m_next指向我们新的第一个结点
     next->m_prev = this ->m_head;          //再将我们的新的第一个结点的m_prev指向头结点
     delnode->m_next = delnode->m_prev = nullptr;  //把要删除的元素的成员至nullptr
     delnode->m_val = T();        //将要删除的元素的值置为匿名对象的默认值
     delete delnode;     //删除第一个结点
}

insert()

在c++98中我们的insert()函数有如下三种版本:

C++模拟实现list功能

下面我们就将其模拟实现:

指定位置插入一个元素 。

  • 功能：在指定位置插入一个元素。
  • 返回值：插入的元素的位置的迭代器。 
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//插入元素到指定位置，返回的是插入的元素的迭代器
iterator insert(iterator pos, const T& val)
{
     assert (pos.m_pnode != nullptr);     //断言 迭代器是否为空指针错误
     node* newnode = new node(val);      //创建新结点
 
     node* cur = pos.m_pnode;        //记录当前结点的指针
     node* prev = cur->m_prev;        //记录当前结点的前一个结点的指针
 
     newnode->m_next = cur;
     newnode->m_prev = prev;
     prev->m_next = newnode;
     cur->m_prev = newnode;
 
     return iterator(newnode);       //返回一个用当前的插入的元素的结点构建的匿名对象的迭代器
}

指定位置插入n个相同的元素 。

  • 功能：在指定位置插入一个元素。
  • 返回值：void(无返回值)。
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
void insert(iterator pos, size_t n, const T& val)   //插入n个val
{
     assert (pos.m_pnode != nullptr);     //断言 迭代器是否为空指针错误
     while (n--)
     {
         node* newnode = new node(val);
 
         node* cur = pos.m_pnode;
         node* prev = cur->m_prev;
 
         newnode->m_prev = prev;
         prev->m_next = newnode;
         newnode->m_next = cur;
         cur->m_prev = newnode;
     }
}
 
void insert(iterator pos, int n, const T& val)  //插入n个val
{
     assert (pos.m_pnode != nullptr);     //断言 迭代器是否为空指针错误
     assert (n > 0);
     while (n--)
     {
         node* newnode = new node(val);
 
         node* cur = pos.m_pnode;
         node* prev = cur->m_prev;
 
         newnode->m_prev = prev;
         prev->m_next = newnode;
         newnode->m_next = cur;
         cur->m_prev = newnode;
     }
}
 
void insert(iterator pos, long n, const T& val) //插入n个val
{
     assert (pos.m_pnode != nullptr);     //断言 迭代器是否为空指针错误
     assert (n > 0);
     while (n--)
     {
         node* newnode = new node(val);
 
         node* cur = pos.m_pnode;
         node* prev = cur->m_prev;
 
         newnode->m_prev = prev;
         prev->m_next = newnode;
         newnode->m_next = cur;
         cur->m_prev = newnode;
     }
}

注意：这里的insert在指定位置插入为什么要实现三种重载版本呢？这与上面的构造函数问题是相同类型的，都是与模板区间构造有关，这里就不多赘述了。 指定位置插入区间内的元素 。

  • 功能：在指定位置插入区间内的元素。
  • 返回值：void(无返回值)。
  • 注意：

1、该区间必须是前闭后开,

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template < class InputIterator>
void insert(iterator pos, InputIterator first, InputIterator last)  //区间插入
{
     assert (pos.m_pnode != nullptr);     //断言 迭代器是否为空指针错误
     while (first != last)
     {
         node* newnode = new node(*first);
 
         node* cur = pos.m_pnode;
         node* prev = cur->m_prev;
 
         newnode->m_prev = prev;
         prev->m_next = newnode;
         newnode->m_next = cur;
         cur->m_prev = newnode;
         ++first;
     }
}

erase()

在C++98中erase()有两种版本，一个是删除指定位置，另一个是删除区间内的元素。如下图所示:

C++模拟实现list功能

删除指定位置 。

  • 功能：删除指定位置的元素。
  • 返回值：删除指定位置的元素的下一个结点的迭代器。
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//删除指定位置的元素，返回下一个元素的迭代器，但要注意的是：
//如果删除的最后一个元素，此时返回的是头结点也就是end()位置的迭代器
iterator erase(iterator pos)           
{
     assert (pos.m_pnode != nullptr);     //断言 迭代器是否为空指针错误
     assert (pos != end());               //断言 list内元素为空及删除头结点的情况
    
     node* next = pos.m_pnode->m_next;
     node* prev = pos.m_pnode->m_prev;
 
     prev->m_next = next;
     next->m_prev = prev;
 
     pos.m_pnode->m_next = pos.m_pnode->m_prev = nullptr;
     pos.m_pnode->m_val = T();
     delete pos.m_pnode;
 
     return iterator(next);     
}

删除区间内的元素 。

  • 功能：删除区间内的元素。
  • 返回值：删除区间内的元素的下一个结点的迭代器。也就是返回last迭代器这个位置。
  • 注意：

1、该区间必须是前闭后开,

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
iterator erase(iterator first, iterator last)       //区间删除
{
     node* prev = first.m_pnode->m_prev;
     node* next = last.m_pnode;
 
     while (first != last)
     {
         node* cur = first.m_pnode;
         ++first;
         cur->m_next = cur->m_prev = nullptr;
         cur->m_val = T();
         delete cur;
         cur = nullptr;
     }
 
     prev->m_next = next;
     next->m_prev = prev;
 
     return iterator(next);
}

clear()

  • 功能：用于清空我们list中的所有元素的值，但不是要把list对象也删除。
  • 返回值：void（无返回值）。
?
1
2
3
4
5
6
7
8
9
10
11
void clear()        //清空元素，而不是把整个链表删除掉
     {
         iterator it = this ->begin();
 
         while (it != this ->end())   
         //复用我们写的头删，一个一个的删除，当然也可以复用尾删pop_back()和erase()
         {
             ++it;
             this ->pop_front();
         }
     }

swap()

  • 功能：swap顾名思义就是交换的意思，这里我们将这个swap作为我们的成员函数，用来交换两个list链表。
  • 返回值: void（无返回值）。
?
1
2
3
4
5
6
void swap(list<T>& obj)
{
     node* temp = this ->m_head;
     this ->m_head = obj.m_head;
     obj.m_head = temp;
}

完整代码如下

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<assert.h>
using  namespace std;
 
namespace ZJ
{
     template < class T>
     class list_node     //结点
     {
     public :
         list_node(T val=T())        //构造函数
             :m_val(val)
             ,m_prev(nullptr)
             ,m_next(nullptr)
         {}
     public :
         T m_val;        //值
         list_node<T>* m_prev; //指向前一个的指针
         list_node<T>* m_next; //指向下一个的指针
 
     };
 
     template < class T, class Ref, class Ptr>     //封装一个node型指针，制作成迭代器类
     class list_iterator
     {
     public :
         typedef list_node<T> node;
         typedef list_iterator<T, Ref, Ptr>myself;
         list_iterator(node* pnode)
             :m_pnode(pnode)
         {}
 
         Ref operator* ()        //重载  *
         {
             return this ->m_pnode->m_val;
         }
 
         Ptr operator->()     //重载 ->
         {
             return & this ->m_pnode->m_val;
         }
 
         bool operator!=( const myself&obj) const     //重载！=号
         {
             return this ->m_pnode != obj.m_pnode;
         }
 
         bool operator==( const myself& obj) const    //重载==号
         {
             return this ->m_pnode == obj.m_pnode;
         }
 
         myself& operator++()        //重载前置++
         {
             this ->m_pnode = this ->m_pnode->m_next;
             return * this ;
         }
 
         myself operator++( int )      //重载后置++
         {
             const myself temp(* this );
             this ->m_pnode = this ->m_pnode->m_next;
             return temp;
         }
 
         myself& operator--()        //重载前置--
         {
             this ->m_pnode = this ->m_pnode->m_prev;
             return * this ;
         }
 
         myself operator--( int )      //重载后置--
         {
             const myself temp(* this );
             this ->m_pnode = this ->m_pnode->m_prev;
             return temp;
         }
 
     public :
         node* m_pnode;
     };
 
     template < class T>
     class list
     {
     public :
         typedef list_node<T> node;       
         typedef list_iterator<T,T&,T*> iterator;      //普通迭代器
         typedef list_iterator<T, const T&, const T*> const_iterator;    //常量迭代器
 
     public :
         list()      //无参默认构造函数
         {
             this ->m_head = new node(T());
             this ->m_head->m_next = this ->m_head;
             this ->m_head->m_prev = this ->m_head;
         }
 
         list( size_t size, const T& val=T()) //n个元素构造函数
         {
             this ->m_head = new node(T());
             this ->m_head->m_next = this ->m_head;
             this ->m_head->m_prev = this ->m_head;
             while (size--)
             {
                 this ->push_back(val);
             }
         }
 
         list( long size, const T& val = T()) //n个元素构造函数
         {
             assert (size > 0);
             this ->m_head = new node(T());
             this ->m_head->m_next = this ->m_head;
             this ->m_head->m_prev = this ->m_head;
             while (size--)
             {
                 this ->push_back(val);
             }
         }
 
         list( int size, const T& val = T())  //n个元素构造函数
         {
             assert (size > 0);
             this ->m_head = new node(T());
             this ->m_head->m_next = this ->m_head;
             this ->m_head->m_prev = this ->m_head;
             while (size--)
             {
                 this ->push_back(val);
             }
         }
 
         template < class InputIterator>
         list(InputIterator first, InputIterator last)       //区间构造
         {
             this ->m_head = new node(T());
             this ->m_head->m_next = this ->m_head;
             this ->m_head->m_prev = this ->m_head;
             while (first != last)
             {
                 node* newnode = new node(*first);
                 node* tail = this ->m_head->m_prev;
                 tail->m_next = newnode;
                 newnode->m_prev = tail;
                 newnode->m_next = this ->m_head;
                 this ->m_head->m_prev = newnode;
                 ++first;
             }
         }
        
         list( const list<T>& obj)      //拷贝构造函数
         {
             this ->m_head = new node(T());
             this ->m_head->m_next = this ->m_head;
             this ->m_head->m_prev = this ->m_head;
             const_iterator it = obj.begin();
             while (it != obj.end())
             {
                 node* newnode = new node(it.m_pnode->m_val);
 
                 node* tail = this ->m_head->m_prev;
                 tail->m_next = newnode;
                 newnode->m_prev = tail;
                 newnode->m_next = this ->m_head;
                 this ->m_head->m_prev = newnode;
                 ++it;
             }
         }
 
         list<T>& operator=( const list<T>& obj)      //赋值运算符重载
         {
             if ( this != &obj)
             {
                 list<T>temp(obj);
                 this ->swap(temp);
             }
             return * this ;
         }
 
 
         ~list()     //析构函数
         {
             iterator it = this ->begin();
 
             while (it != this ->end())    //复用我们写的头删，一个一个的删除，当然也可以复用尾删pop_back()和erase()
             {
                 ++it;
                 this ->pop_front();
             }
 
             delete this ->m_head;
             this ->m_head = nullptr;
         }
 
         iterator begin()
         {
             return iterator( this ->m_head->m_next);
         }
 
         const_iterator begin()  const
         {
             return const_iterator( this ->m_head->m_next);
         }
 
         iterator end()
         {
             return iterator( this ->m_head);
         }
 
         const_iterator end()    const
         {
             return const_iterator( this ->m_head);
         }
 
         bool empty()    const       //判空
         {
             return this ->begin() == this ->end();  //就是begin()与end()同时指向头结点时的情况
         }
 
         //遍历一遍链表来得到元素个数，为什么使用遍历一遍链表呢？
         //这是因为我们使用链表时很少会去知道它的元素个数，但如果频繁的调用该接口会造成性能的下降
         //此时我们应该在list类中将增加一个记录元素个数的变量size
         //如果有元素插入就增加，删除就减少
         size_t size()   const   //获得元素个数
         {
             size_t size = 0;
             const_iterator it = this ->begin();
             while (it!= this ->end())
             {
                 ++it;
                 ++size;
             }
             return size;
         }
 
         T& back()
         {
             assert (! this ->empty());
             return this ->m_head->m_prev->m_val;
         }
 
         const T& back()   const
         {
             assert (! this ->empty());
             return this ->m_head->prev->m_val;
         }
 
         T& front()
         {
             assert (! this ->empty());
             return  this ->m_head->m_next->m_val;
         }
 
         const T& front() const
         {
             assert (! this ->empty());
             return this ->m_head->m_next->m_val;
         }
 
         void push_front( const T& val)   //头插
         {
             node* newnode = new node(val);
             node*  next = this ->m_head->m_next;
             newnode->m_next = next;
             this ->m_head->m_next = newnode;
             newnode->m_prev = this ->m_head;
             next->m_prev = newnode;
         }
 
         void push_back( const T& val)    //尾插
         {
             node* tail = this ->m_head->m_prev;
             node* newnode = new node(val);
             newnode->m_next = tail->m_next;
             newnode->m_prev = tail;
             tail->m_next = newnode;
             this ->m_head->m_prev = newnode;
         }
 
 
         //插入元素到指定位置，返回的是插入的元素的迭代器
         iterator insert(iterator pos, const T& val)
         {
             assert (pos.m_pnode != nullptr);     //断言 迭代器是否为空指针错误
             node* newnode = new node(val);      //创建新结点
 
             node* cur = pos.m_pnode;        //记录当前结点的指针
             node* prev = cur->m_prev;        //记录当前结点的前一个结点的指针
 
             newnode->m_next = cur;
             newnode->m_prev = prev;
             prev->m_next = newnode;
             cur->m_prev = newnode;
 
             return iterator(newnode);       //返回一个用当前的插入的元素的结点构建的匿名对象的迭代器
         }
 
         void insert(iterator pos, size_t n, const T& val)   //插入n个val
         {
             assert (pos.m_pnode != nullptr);     //断言 迭代器是否为空指针错误
             while (n--)
             {
                 node* newnode = new node(val);
 
                 node* cur = pos.m_pnode;
                 node* prev = cur->m_prev;
 
                 newnode->m_prev = prev;
                 prev->m_next = newnode;
                 newnode->m_next = cur;
                 cur->m_prev = newnode;
             }
         }
 
         void insert(iterator pos, int n, const T& val)  //插入n个val
         {
             assert (pos.m_pnode != nullptr);     //断言 迭代器是否为空指针错误
             assert (n > 0);
             while (n--)
             {
                 node* newnode = new node(val);
 
                 node* cur = pos.m_pnode;
                 node* prev = cur->m_prev;
 
                 newnode->m_prev = prev;
                 prev->m_next = newnode;
                 newnode->m_next = cur;
                 cur->m_prev = newnode;
             }
         }
 
         void insert(iterator pos, long n, const T& val) //插入n个val
         {
             assert (pos.m_pnode != nullptr);     //断言 迭代器是否为空指针错误
             assert (n > 0);
             while (n--)
             {
                 node* newnode = new node(val);
 
                 node* cur = pos.m_pnode;
                 node* prev = cur->m_prev;
 
                 newnode->m_prev = prev;
                 prev->m_next = newnode;
                 newnode->m_next = cur;
                 cur->m_prev = newnode;
             }
         }
 
         template < class InputIterator>
         void insert(iterator pos, InputIterator first, InputIterator last)  //区间插入
         {
             assert (pos.m_pnode != nullptr);     //断言 迭代器是否为空指针错误
             while (first != last)
             {
                 node* newnode = new node(*first);
 
                 node* cur = pos.m_pnode;
                 node* prev = cur->m_prev;
 
                 newnode->m_prev = prev;
                 prev->m_next = newnode;
                 newnode->m_next = cur;
                 cur->m_prev = newnode;
                 ++first;
             }
         }
 
         void pop_front()    //头删
         {
             assert (!empty());   //断言 如果list已经为空，则删除不了
             node* delnode = this ->m_head->m_next;
             node* next = delnode->m_next;
             this ->m_head->m_next = next;
             next->m_prev = this ->m_head;
             delnode->m_next = delnode->m_prev = nullptr;
             delnode->m_val = T();
             delete delnode;
         }
 
         void pop_back()     //尾删
         {
             assert (!empty());   //断言 如果list已经为空，则删除不了
             node* tail = this ->m_head->m_prev;
             node* prev = tail->m_prev;
             this ->m_head->m_prev = prev;
             prev->m_next = this ->m_head;
             tail->m_next = tail->m_prev = nullptr;
             tail->m_val = T();
             delete tail;
         }
 
 
         //删除指定位置的元素，返回下一个元素的迭代器，但要注意的是：
         //如果删除的最后一个元素，此时返回的是头结点也就是end()位置的迭代器
         iterator erase(iterator pos)           
         {
             assert (pos.m_pnode != nullptr);     //断言 迭代器是否为空指针错误
             assert (pos != end());               //断言 list内元素为空及删除头结点的情况
            
             node* next = pos.m_pnode->m_next;
             node* prev = pos.m_pnode->m_prev;
 
             prev->m_next = next;
             next->m_prev = prev;
 
             pos.m_pnode->m_next = pos.m_pnode->m_prev = nullptr;
             pos.m_pnode->m_val = T();
             delete pos.m_pnode;
 
             return iterator(next);     
         }
 
         iterator erase(iterator first, iterator last)       //区间删除
         {
             node* prev = first.m_pnode->m_prev;
             node* next = last.m_pnode;
 
             while (first != last)
             {
                 node* cur = first.m_pnode;
                 ++first;
                 cur->m_next = cur->m_prev = nullptr;
                 cur->m_val = T();
                 delete cur;
                 cur = nullptr;
             }
 
             prev->m_next = next;
             next->m_prev = prev;
 
             return iterator(next);
         }
 
         void clear()        //清空元素，而不是把整个链表删除掉
         {
             iterator it = this ->begin();
 
             while (it != this ->end())    //复用我们写的头删，一个一个的删除，当然也可以复用尾删pop_back()和erase()
             {
                 ++it;
                 this ->pop_front();
             }
         }
 
         void swap(list<T>& obj)
         {
             node* temp = this ->m_head;
             this ->m_head = obj.m_head;
             obj.m_head = temp;
         }
     private :
         node* m_head;       //头指针
     };
}

到此这篇关于C++模拟实现list的文章就介绍到这了,更多相关C++list实现内容请搜索我以前的文章或继续浏览下面的相关文章希望大家以后多多支持我！ 。

原文链接：https://blog.csdn.net/weixin_47812603/article/details/119464645 。

最后此篇关于C++模拟实现list功能的文章就讲到这里了,如果你想了解更多关于C++模拟实现list功能的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

39 4 0
文章推荐： iptables做策略屏蔽QQ与MSN
文章推荐： pandas dataframe的合并实现（append, merge, concat）
文章推荐： 基于Linux网关服务器squid配置过程详解
文章推荐： linux下修改MAC地址问题解决方法
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com