【C++进阶】深入STL之list:模拟实现深入理解List与迭代器

简介: 【C++进阶】深入STL之list:模拟实现深入理解List与迭代器

前言: 在STL中,list是一种双向链表,它支持在序列的任何位置进行快速插入和删除操作。与此同时,迭代器是STL中非常重要的一个概念,它使得我们能够以统一的方式遍历和访问STL容器中的元素。在深入了解STL的过程中,模拟实现list和迭代器无疑是一个极有价值的学习过程。

本节我们将从基本的链表结构开始,逐步构建出完整的list类,并实现相应的迭代器类。


📒1. list的基本结构

list是一个个带头双向循环链表,这意味着每个元素(通常称为节点)都有两个指针:一个指向前一个元素,另一个指向后一个元素,因此我们需要单独再定义一个类来表示节点结构,每个节点再串联起来构成list

节点定义(示例):

template<class T>
struct list_node
{
  T _data;
  list_node<T>* _next;
  list_node<T>* _prev;

  list_node(const T& x = T())
    :_data(x)
    ,_next(nullptr)
    ,_prev(nullptr)
  {}
};

而在构建list时,我们成员变量只需要一个头节点。

list定义(示例):

template<class T>
struct list
{
  typedef list_node<T> Node;
public:
  // 构造函数等可能的其他成员函数... 
private:
  Node* _head;
};

📕2. list的模拟实现

注意:关于eraseinsert这两个函数的模拟我们依然作为补充放在末尾

🌈构造函数

在拥有一个list我们只需要将它的头节点初始化一下

list构造(示例):

void empty_init()
{
  _head = new Node;
  _head->_prev = _head;
  _head->_next = _head;
}

// 无参构造
list()
{
  empty_init();
}

🌞析构函数

关于析构函数,我们需要的是将所有节点一 一释放就ok啦!

在模拟析构函数之前,不得不先介绍一下clear这个函数,因为clear可以删除出头节点以外的所有节点,我们可以利用这一点帮助我们优化析构函数

list析构(示例):

void clear()
{
  // 依次清除节点
  itetator it = begin(); // 稍后会提到迭代器的模拟
  while(it != end())
  {
    it = erase(it);
  } 
}

~list()
{
  clear(); // 删除出头节点以外的所有节点
  delete _head; // 单独删除一下头节点
  _head = nullptr;
}

🌙拷贝构造函数

在学习list时,我们发现list不会因为空间不够而需要扩容,因此在使用模拟list时,不用考虑是否会发生浅拷贝

list拷贝构造函数(示例):

//list(const list<T>& lt)
list(list<T>& lt) // 还未实现const迭代器,先使用常规的
{
  empty_init();
  for (auto e : lt)
  {
    push_back(e); // push_back的实现其实是复用insert,文末有补充
  }
}

⭐赋值运算符重载

这里我们以让后传统写法和现代写法两种方法

list赋值运算符重载(示例):

// 传统写法
list<T>& operator=(const list<T>& lt)
{
  clear(); // 先将原来的list清空
  for (auto e : lt)
  {
    push_back(e);
  }
  return *this;
}

// 现代写法
void swap(list<T>& tmp)
{
  std::swap(_head, tmp._head);
}

list<T>& operator=(list<T> lt)
{
  swap(lt);
  return *this;
}

在介绍完list基本的结构后,让我们来看看今天的重点:迭代器


📚3. list的迭代器

在我们模拟实现stringvector时,我们认为迭代器就是一个原生指针,但是在list中迭代器底层不是简单的指针,因此我们要独立定义一个新的类


🍂迭代器的基本结构

迭代器定义(示例):

template<class T>
struct __list_iterator
{
  typedef list_node<T> Node;
  typedef __list_iterator<T> self;
  Node* _node;
  
  // 构造函数
  __list_iterator(Node* node)
    :_node(node)
  {}
};

我们将迭代器单独写作一个类,能解决更多的问题,以及避免其他麻烦


🍁迭代器的运算符重载

因为这些函数和前面差不太多,我们简单看看代码,带过了

代码(示例):

self& operator++() // 前置++
{
  _node = _node->_next;
  return *this;
}

self& operator--() // 前置--
{
  _node = _node->_prev;
  return *this;
}

self operator++(int) // 后置++
{
  self tmp(*this);
  _node = _node->_next;
  return &tmp;
}

self operator--(int) // 后置--
{
  self tmp(*this);
  _node = _node->_prev;
  return &tmp;
}

bool operator!=(const self& tmp)
{
  return _node != tmp._node; 
}

bool operator-=(const self& tmp)
{
  return _node -= tmp._node;
}

而今天着重要强调以下两个运算符重载,因为const非const下这两个是有区别的:

//可读写
T& operator*()
{
  return _node->_data;
}
//可读写
T* operator->()
{
  return &_node->_data;
}
// it.operator->()-> 编译器帮我们省略了一个箭头->  it->

在定义完迭代器类之后,我们可以实现begin()end()来实现list范围for


🌸list的迭代器

迭代器代码(示例):

template<class T>
struct list
{
  typedef list_node<T> Node;
public:
  typedef __list_iterator<T> iterator;
  
  iterator begin()
  {
    //return iterator(_head->_next); // 匿名对象
    return _head->next;
  }
  iterator end()
  {
    //return iterator(_head); // 匿名对象
    return _head;
  }
private:
  Node* _head;
};

当然我们这里还没有实现const迭代器很多需要调用const对象的函数还无法使用,那么接下来让我们来模拟实现const迭代器,见证新的神奇


📙4. list的const迭代器

关于这个list的const迭代器其实有两种写法,常规的写法就是在定义一个新的const迭代器的类,虽然这样可以解决问题,但是会造成代码的冗余,让操作繁琐。而另一种方法就是在原有的迭代器类上进行修改,让它能具有两个迭代器都能使用的特点

🎩方法一

const迭代器实现(示例):

template<class T>
struct __list_const_iterator
{
  typedef list_node<T> Node;
  typedef __list_const_iterator<T> self;
  Node* _node;
  
  // 构造函数
  __list_const_iterator(Node* node)
    :_node(node)
  {}

  //可读不可写
  const T& operator*()
  {
    return _node->_data;
  }
  //可读不可写
  const T* operator->()
  {
    return &_node->_data;
  }
  // 可能的其他成员函数... 
};

🎈方法二

如果我们将这两个差异的内容单独表示出来归于模板中,因为在const与非const之间,无非就是T&,T*上能否读写的区别,不影响其他的函数实现,因此我们可以在模板上加上两个参数

模板参数 实例化类型
Ref T&,(const 变量时) const T&
Ptr T*,(const 变量时) const T*

const迭代器实现(示例):

// 用一个模板来解决 const与非const
template<class T, class Ref, class Ptr>
struct __list_iterator
{
  typedef list_node<T> Node;
  // 会实例化成最匹配的
  typedef __list_iterator<T, Ref, Ptr> self;
  Node* _node;
  
  // 构造函数
  __list_iterator(Node* node)
    :_node(node)
  {}
  
  Ref operator*()
  {
    return _node->_data;
  }

  Ptr operator->()
  {
    return &_node->_data;
  }
  // 可能的其他成员函数... 
};
template<class T>
struct list
{
  typedef list_node<T> Node;
public:
  typedef __list_iterator<T, T&, T*> iterator;
  typedef __list_const_iterator<T, const T&, const T*>  const_iterator;
  
  iterator begin()
  {
    return _head->next;
  }
  iterator end()
  {
    return _head;
  }
  const_iterator begin() const
  {
    return _head->next;
  }
  const_iterator end() const
  {
    return _head;
  }
private:
  Node* _head;
};

关于list的模拟实现我们就讲到这里,让我看看如何以统一的方式遍历和访问STL容器中的元素


📜5. 统一的方式访问STL容器中的元素

在完成对list的模拟实现后,我们试着用来遍历和访问list中的元素

代码实现(示例):

void print_list(const list<int>& lt)
{
  // list<T>没有实例化话,就并不能去遍历寻找
  // 编译器不知道 list<T>::const_iterator 是内嵌类型,还是静态成员变量
  list<int>::const_iterator it = lt.begin();
  while (it != lt.end())
  {
    cout << *it << " ";
    ++it;
  }
}
void test_list()
{
  list<int> lt;
  lt.push_back(1);
  lt.push_back(2);
  print_list(lt);
  cout << endl;
}

编译器不知道 list::const_iterator 是内嵌类型,还是静态成员变量,但是如果实例化成int后,有需要一个成员是string的列表这时我们有犯难了,这时我们就要用到typenametypename 就是告诉编译器,这是一个类型,等list实例化之后再去取

代码实现(示例):

template<typename T>
void print_list(const list<T>& lt)
{
  ......
  // typename 就是告诉编译器,这是一个类型,等list实例化之后再去取
  typename list<T>::const_iterator it = lt.begin();
  ......
}

但是更离谱的来了,这时又有人要求我们打印vector的值,容器都换了我们该怎么办呢?这时模板的作用又双体现出来了,这也体现了模板的本质,让我们能省的活交给编译器完成

代码实现(示例):

// 这里直接搞了一个Container来适配容器
template<typename Container>
void print_container(const Container& con)
{
  typename  Container::const_iterator it = con.begin();
  while (it != con.end())
  {
    cout << *it << " ";
    ++it;
  }
}

它使得我们能够以统一的方式遍历和访问STL容器中的元素


📔6. list与vector的对比

我们可以发现list与之前学的竟然有那么多的差异,我们结合上节学的vector来分析一下它们的差异:vectorlist都是STL中非常重要的序列式容器,由于两个容器的底层结构不同,导致其特性以及应用场景不同

vector list
底 层 结 构 动态顺序表,一段连续空间 带头结点的双向循环链表
随 机 访 问 支持随机访问,访问某个元素效率O(1) 不支持随机访问,访问某个元素效率O(N)
插 入 和 删 除 任意位置插入和删除效率低,需要搬移元素,时间复杂度为O(N),插入时有可能需要增容, 任意位置插入和删除效率高,不需要搬移元素,时间复杂度为O(1)
空 间 利 用 率 底层为连续空间,不容易造成内存碎片,空间利用率高,缓存利用率高 底层节点动态开辟,小节点容易造成内存碎片,空间利用率低,缓存利用率低
迭 代 器 插入删除时触发条件会导致迭代器失效 删除元素时,只会导致当前迭代器失效,其他迭代器不受影响
使 用 场 景 需要高效存储,支持随机访问,不关心插入删除效率 大量插入和删除操作,不关心随机访问

📖7. 总结补充

💧补充:insert和erase的模拟实现

代码实现(示例):

// insert会返回插入位置的一个迭代器
iterator insert(iterator pos, const T& x)
{
  Node* newnode = new Node(x);
  Node* cur = pos._node;
  Node* prev = cur->_prev;

  prev->_next = newnode;
  newnode->_prev = prev;

  cur->_prev = newnode;
  newnode->_next = cur;

  return iterator(newnode); // 匿名对象
}
// erase会返回删除位置的next节点的迭代器
iterator erase(iterator pos)
{
  Node* cur = pos._node;
  Node* prev = cur->_prev;
  Node* next = cur->_next;
      
  delete cur;
  prev->_next = next->_prev;
  next->_prev = prev->_next;

  return iterator(next); // 匿名对象
}
// erase和insert的复用
void push_back(const T& x) // 尾插
{
  insert(end(), x);
}
void push_front(const T& x) // 头插
{
  insert(begin(), x);
}
void pop_back() // 尾删
{
  erase(end());
}
void pop_front() // 头删
{
  erase(begin());
}

🔥总结

通过本次对STL中list和迭代器模拟实现的探索,我们深入了解了双向链表的基本结构、操作原理以及迭代器在遍历和访问链表元素中的重要作用。模拟实现的过程不仅让我们对STL中的list容器有了更深刻的理解,也锻炼了我们的编程能力和解决问题的能力

  • 在模拟实现的过程中,我们学习了如何设计并实现一个双向链表结构,包括节点的定义、链表的插入、删除和遍历等操作。同时,我们也掌握了迭代器的基本概念和实现方法,理解了如何通过迭代器来统一访问和遍历不同的容器类型。
  • 模拟实现STL中的list和迭代器是一个既有趣又富有挑战性的过程。它让我们更加深入地理解了数据结构和算法的基本原理,也为我们日后在实际项目中高效应用STL容器打下了坚实的基础。

最后,感谢大家的耐心阅读和学习。希望本次介绍能够为大家在STL学习和编程实践中提供一些帮助和启示。在未来的学习和工作中,让我们继续深入探索STL的奥秘,不断提升自己的编程能力和解决问题的能力

谢谢大家支持本篇到这里就结束了,祝大家天天开心!


目录
相关文章
|
9天前
|
存储 Java C++
【c++】list详细讲解
【c++】list详细讲解
15 5
|
9天前
|
设计模式 算法 Java
【c++】STL之stack和queue详解
【c++】STL之stack和queue详解
10 1
|
9天前
|
Java C++ Python
【c++】list 模拟
【c++】list 模拟
8 1
|
17天前
|
存储 编译器 C语言
【C++】list模拟实现
本文档介绍了C++ STL中`list`容器的模拟实现,包括`ListNode`节点类、迭代器类和`list`类的详细设计。`ListNode`模板类存储数据并维护前后指针;`ListIterator`是一个复杂的模板类,提供解引用、自增/自减以及比较操作。`list`类包含了链表的各种操作,如插入、删除、访问元素等,并使用迭代器作为访问接口。实现中,迭代器不再是简单的指针,而是拥有完整功能的对象。此外,文档还提到了迭代器的实现对C++语法的特殊处理,使得`it-&gt;_val`的写法成为可能。文章通过分步骤展示`list`的各个组件的实现,帮助读者深入理解STL容器的内部工作原理。
|
17天前
|
算法 搜索推荐 C++
【C++】list的使用(下)
`C++` 中 `std::list` 的 `merge()`、`sort()` 和 `reverse()` 操作: - `merge(x)` 和 `merge(x, comp)`: 合并两个已排序的`list`,将`x`的元素按顺序插入当前`list`,`x`清空。比较可自定义。 - `sort()` 和 `sort(comp)`: 对`list`元素排序,保持等价元素相对顺序。内置排序基于稳定排序算法,速度较慢。 -reverse(): 反转`list`中元素的顺序。 这些操作不涉及元素构造/销毁,直接移动元素。注意,`sort()`不适合`std::list`,因链表结构不利于快速排序
|
17天前
|
C++ 容器
【C++】list的使用(下)
这篇博客探讨了C++ STL中`list`容器的几个关键操作,包括`splice()`、`remove()`、`remove_if()`和`unique()`。`splice()`允许高效地合并或移动`list`中的元素,无需构造或销毁。`remove()`根据值删除元素,而`remove_if()`则基于谓词移除元素。`unique()`则去除连续重复的元素,可选地使用自定义比较函数。每个操作都附带了代码示例以说明其用法。
|
17天前
|
编译器 C++ 容器
【C++】list的使用(上)
迭代器在STL中统一了访问接口,如`list`的`begin()`和`end()`。示例展示了如何使用正向和反向迭代器遍历`list`。注意`list`的迭代器不支持加减操作,只能用`++`和`--`。容器的`empty()`和`size()`用于检查状态和获取元素数。`front()`和`back()`访问首尾元素,`assign()`重载函数用于替换内容,`push_*/pop_*`管理两端元素,`insert()`插入元素,`erase()`删除元素,`resize()`调整大小,`clear()`清空容器。这些接口与`vector`和`string`类似,方便使用。
|
15天前
|
存储 算法 C++
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
24 0
|
9天前
|
设计模式 安全 编译器
【C++11】特殊类设计
【C++11】特殊类设计
28 10
|
14天前
|
C++
C++友元函数和友元类的使用
C++中的友元(friend)是一种机制,允许类或函数访问其他类的私有成员,以实现数据共享或特殊功能。友元分为两类:类友元和函数友元。类友元允许一个类访问另一个类的私有数据,而函数友元是非成员函数,可以直接访问类的私有成员。虽然提供了便利,但友元破坏了封装性,应谨慎使用。
42 9