AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【C++要笑着学】list 核心框架接口的模拟实现 | 运算符重载实现list迭代器 | 妙用模板实现const迭代器（二）

2022-12-19 85
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 我们在上一章说过，list 其实就是带哨兵位循环双向链表而已，这种链表虽然结构复杂，但是实现起来反而是最简单的，我们在数据结构专栏中有过详细的讲解。

Ⅳ. list 的拷贝构造和赋值重载

0x00 引入：list 的同样涉及深浅拷贝问题

❓ 思考：这里的拷贝构造是深拷贝还是浅拷贝？


void test_list4() {
  list<int> L1;
  L1.push_back(1);
  L1.push_back(2);
  L1.push_back(3);
  list<int> L2(L1);
  for (auto e : L2) cout << e << " ";
  }

🚩 运行结果：

5005bab504d78b2ac1d7f394cac05901_0c494a3a535c416e9f9d655ee8184734.png


💡 这里默认生成的拷贝构造是浅拷贝：

ecf3cf2f79ab52b44cd9b985a55f7f6f_c378175626f1471fac8db1d9ffac9a31.png


比如这里 浅拷贝导致 L1 和 L2 指向同一块地址，析构的时候会导致一块空间被释放两次。


这些知识我们在之前讲解深浅拷贝的时候就说过，这里没崩仅仅是因为我们还没设计析构。


这里只是勉强 "逃过一杰" 。


综上所述，我们这里依然要自己去实现一个拷贝构造，去完成 "深拷贝" 。


我们下面实现一下 ~list，再回来看看。


0x01 clear 清空链表中所有数据

在实现链表 list 的析构函数前，为了方便清空，我们先实现一下 clear()


💬 代码：清空链表数据

/* 清空链表所有数据 */
void clear() {
  // 利用迭代器去遍历整个链表
  iterator cur = begin();
  while (cur != end()) {
  iterator del = cur++;  // 巧妙利用后置++的特性
  delete del._node;      // 删除当前结点，后置++生效
  }
  // 删完之后我们还需要将其恢复到初始状态
  _pHead->_next = _pHead;
  _pHead->_prev = _pHead;
}

🔨 测试代码：


void test_list5() {
  list<int> L;
  L.push_back(1);
  L.push_back(2);
  L.push_back(3);
  cout << "删除前：";
  print_list(L);
  cout << "删除后：";
  L.clear();
  print_list(L);
  }

🚩 运行结果：

fa918edb8cc89174c8b5a10911ce3ea7_712608ded6f8483cac01c59933a2c203.png


当然，这里的删除结点我们也可以用 erase 去完成。


用 erase 可以省去我们将其恢复 _pHead 的前驱和后继指向自己的操作。

e250e9e86ac4bb129e36795a9bf66a3d_69823265f37b4810b4b634f4b131eb3c.png

删除掉最后一个有效元素后， erase 的 "缝合操作" 自然会做到：


💬 代码：用迭代器 + erase 的方式去逐个访问并删除每个节点


void clear() {
  iterator cur = begin();
  while (cur != end()) {
  iterator del = cur++;
  erase(del);           // 直接反复调用erase删除结点
  }
}

⚡ 简化：还可以进一步简化：

/* 清空链表所有数据 */
void clear() {
  iterator cur = begin();
  while (cur != end()) {
  // iterator del = cur++;
  erase(cur++);   // 直接反复调用erase删除结点
  }
}

0x02 ~list 析构

实现了 clear 后，我们再去实现 list 的析构函数就很简单了。


我们只需要把哨兵位头结点 _pHead 给干掉就行了，并且记得要置成空指针。


💬 代码：析构函数的实现

~list() {
  // 清空链表有效数据
  clear();
  // 干掉头结点
  delete _pHead;
  _pHead = nullptr;
}

实现好了析构函数，我们再回过头来测刚才 "逃过一劫" 的浅拷贝导致的两个结点指向同一地址的问题，现在问题就变得严重起来了，因为它会被析构两次：

void test_list4() {
    list<int> L1;
    L1.push_back(1);
    L1.push_back(2);
    L1.push_back(3);
    list<int> L2(L1);
    for (auto e : L2) cout << e << " ";
  }

🚩 运行结果：（崩溃）


刚才得益于我们还没有去实现析构函数，让浅拷贝带来的问题 "逃过一杰" 。


但是现在可谓是在劫难逃了 ——

b8acae8c260ab4d1193ff1f7b947cb4e_30cbef58de654116907ca81977f31c1e.png


自动生成的拷贝构造是浅拷贝，为了解决这个问题，我们需要手动实现一个深拷贝的拷贝构造！


0x03 拷贝构造的实现

💬 代码：传统写法

/* 拷贝构造：L2(L1) */
list(const list<T>& L) {
  _pHead = new Node();
  _pHead->_next = _pHead;
  _pHead->_prev = _pHead;
  for (auto e : L) {
  push_back(e);
  }
}

💬 代码：现代写法


template<class InputIterator> 
list(InputIterator first, InputIterator last) {
  _pHead = new Node();
  _pHead->_next = _pHead;
  _pHead->_prev = _pHead;
  while (first != last) {
  push_back(*first);
  first++;
  }
}
/* 拷贝构造（现代写法）：L2(L1) */
list(const list<T>& L) {
    _pHead = new Node();
  _pHead->_next = _pHead;
  _pHead->_prev = _pHead;
  list<T> tmp(L.begin(), L.end());
  swap(_pHead, tmp._pHead);  // 交换两个结点的指针
}

0x04 赋值重载

💬 代码：传统写法

/* 赋值：L2 = L1 */
list<T>& operator=(list<T> L) {
  if (this != &L) {
  clear();
  for (auto e : L) {
    push_back(e);
  }
  }
  return *this;
}

💬 代码：现代写法


/* 赋值（现代写法）：L2 = L1 */
list<T>& operator=(list<T> L) {
  swap(_pHead, L._pHead);
  return *this;
}

Ⅴ. 完整代码

0x00 list.h

（注：未采用申明与定义分离的形式）


#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <assert.h>
using namespace std;
namespace chaos
{
  /* 定义结点 */
  template<class T>
  struct ListNode {
  T _data;      // 用来存放结点的数据
  ListNode<T>* _next;       // 指向后继结点的指针
  ListNode<T>* _prev;       // 指向前驱结点的指针
  ListNode(const T& data = T())   // 全缺省构造（初始化）
    : _data(data)
    , _next(nullptr)
    , _prev(nullptr)
  {}
  };
  /* 定义迭代器 */
  template<class T, class Ref, class Ptr>
  struct __list_iterator {
  typedef ListNode<T> Node;
  typedef __list_iterator<T, Ref, Ptr> self;    // 为了方便我们重命名为self
  typedef Ref reference;
  typedef Ptr pointer;
  Node* _node;
  __list_iterator(Node* x)
    : _node(x) 
  {}
  /* 解引用 */
  Ref operator*() {
    return _node->_data;       // 返回结点的数据
  }
  Ptr operator->() {
    return &_node->_data;     
  }
  /* ++it */
  self& operator++() {
    _node = _node->_next;  // 让 _node 指向下一个结点
    return *this;  // 返回加加后的值
  }
  /* it++ */
  self operator++(int) {
    self tmp(*this);   // 拷贝构造一个tmp存储原来的值
    _node = _node->_next;
    return tmp;
  }
  /* != */
  bool operator!=(const self& it) {
    return _node != it._node;  // 它们结点的指针不一样吗？T or F
  }
  /* --it */
  self& operator--() {
    _node = _node->_prev;  
    return *this;
  }
  /* it-- */
  self operator--(int) {
    self tmp(*this); 
    _node = _node->_prev;
    return tmp;
  }
  };
  ///* 定义const迭代器 */
  //template<class T>
  //struct __const_list_iterator {
  //  typedef ListNode<T> Node;
  //  Node* _node;
  //  __const_list_iterator(Node* x)
  //  : _node(x)
  //  {}
  //  /* 解引用 */
  //  const T& operator*() {
  //  return _node->_data;       // 返回结点的数据
  //  }
  //  /* ++it */
  //  __const_list_iterator<T>& operator++() {
  //  _node = _node->_next;  // 让 _node 指向下一个结点
  //  return *this;  // 返回加加后的值
  //  }
  //  /* it++ */
  //  __const_list_iterator<T> operator++(int) {
  //  __const_list_iterator<T> tmp(*this);   // 拷贝构造一个tmp存储原来的值
  //  _node = _node->_next;
  //  return tmp;
  //  }
  //  /* != */
  //  bool operator!=(const __const_list_iterator<T>& it) {
  //  return _node != it._node;  // 它们结点的指针不一样吗？T or F
  //  }
  //  /* --it */
  //  __const_list_iterator<T>& operator--() {
  //  _node = _node->_prev;
  //  return *this;
  //  }
  //  /* it-- */
  //  __const_list_iterator<T> operator--(int) {
  //  __list_iterator<T> tmp(*this);
  //  _node = _node->_prev;
  //  return tmp;
  //  }
  //};
  /* 定义链表 */
  template<class T>
  class list {
  typedef ListNode<T> Node;      // 重命名为Node
  public:
  /* 迭代器 */
  typedef __list_iterator<T, T&, T*> iterator;
  typedef __list_iterator<T, const T&, const T*> const_iterator;
  iterator begin() { 
    return iterator(_pHead->_next); 
  }
  iterator end() { 
    return iterator(_pHead); 
  }
  const_iterator begin() const {
    return const_iterator(_pHead->_next);  
  }
  const_iterator end() const {
    return const_iterator(_pHead);
  }
  /* 构造函数：初始化头结点 */
  list() {
    _pHead = new Node();
    _pHead->_next = _pHead;
    _pHead->_prev = _pHead;
  }
  list(size_t n, const T& val = T()) {   // 初始化n个结点
    _pHead = new Node();
    _pHead->_next = _pHead;
    _pHead->_prev = _pHead;
    for (size_t i = 0; i < n; i++) {
    push_back(val);
    }
  }
  list(int n, const T& val = T()) {   // 初始化n个结点
    _pHead = new Node();
    _pHead->_next = _pHead;
    _pHead->_prev = _pHead;
    for (int i = 0; i < n; i++) {
    push_back(val);
    }
  }
  template<class InputIterator> 
  list(InputIterator first, InputIterator last) {
    _pHead = new Node();
    _pHead->_next = _pHead;
    _pHead->_prev = _pHead;
    while (first != last) {
    push_back(*first);
    first++;
    }
  }
  /* 拷贝构造（现代写法）：L2(L1) */
  list(const list<T>& L) {
    _pHead = new Node();
    _pHead->_next = _pHead;
    _pHead->_prev = _pHead;
    list<T> tmp(L.begin(), L.end());
    swap(_pHead, tmp._pHead);
  }
  /* 拷贝构造：L2(L1) */
  /*list(const list<T>& L) {
    _pHead = new Node();
    _pHead->_next = _pHead;
    _pHead->_prev = _pHead;
    for (auto e : L) {
    push_back(e);
    }
  }*/
  ///* 赋值：L2 = L1 */
  //list<T>& operator=(list<T> L) {
  //  if (this != &L) {
  //  clear();
  //  for (auto e : L) {
  //    push_back(e);
  //  }
  //  }
  //  return *this;
  //}
  /* 赋值（现代写法）：L2 = L1 */
  list<T>& operator=(list<T> L) {
    swap(_pHead, L._pHead);
    return *this;
  }
  /* 在pos位置前插入 */
  void insert(iterator pos, const T& x) {
    Node* cur = pos._node;     // 找到pos位置的结点
    Node* cur_prev = cur->_prev;     // 因为要在pos位置前插入，所以要找到当前pos位置的前一个结点
    Node* new_node = new Node(x);  // 创建新节点
    // 缝合： cur_prev <-> new_node <-> cur
    cur_prev->_next = new_node;
    new_node->_prev = cur_prev;
    new_node->_next = cur;
    cur->_prev = new_node;
  }
  /* 尾插：push_back */
  void push_back(const T& x) {
    //Node* pTail = _pHead->_prev;     // pHead的前驱就是pTail
    //Node* new_node = new Node(x);    // 创建新结点（会调用构造，自动创建）
    //
    //pTail->_next = new_node;
    //new_node->_prev = pTail;
    //new_node->_next = _pHead;
    //_pHead->_prev = new_node;
    insert(end(), x);   // 在end(头结点)前插入，即尾插
  }
  /* 头插：push_front */
  void push_front(const T& x) {
    insert(begin(), x);  // 在begin（头结点的下一个结点）前插入，即头插
  }
  /* 任意位置删除 */
  iterator erase(iterator pos) {
    assert(pos != end());   // 防止头结点被删除
    Node* cur = pos._node;   // 找到pos位置的结点
    Node* cur_prev = cur->_prev;   // 找到pos的前驱
    Node* cur_next = cur->_next;   // 找到pos的后继
    // 删除cur
    delete cur;
    // 缝合：  cur_prev <-> cur(删) <-> cur_next
    cur_prev->_next = cur_next;
    cur_next->_prev = cur_prev;
    return iterator(cur_next);
  }
  /* 尾删 */
  void pop_back() {
    erase(--end());  // 删除最后一个元素，即尾结点
  }
  /* 头删 */
  void pop_front() {
    erase(begin());  // 删除头结点的下一个结点（即begin位置的结点）
  }
  /* 清空链表所有数据 */
  void clear() {
    利用迭代器去遍历整个链表
    //iterator it = begin();
    //while (it != end()) {
    //  iterator del = it++;  // 巧妙利用后置++的特性
    //  delete del._node;  // 删除当前结点，后置++生效
    //}
    删完之后我们还需要将其恢复到初始状态
    //_pHead->_next = _pHead;
    //_pHead->_prev = _pHead;
    iterator it = begin();
    while (it != end()) {
    // iterator del = it++;
    erase(it++);   // 直接反复调用erase删除结点
    }
  }
  ~list() {
    // 清空链表有效数据
    clear();
    // 干掉头结点
    delete _pHead;
    _pHead = nullptr;
  }
  private:
  Node* _pHead;
  };
  void print_list(const list<int>& L) {
    list<int>::const_iterator it = L.begin();
    while (it != L.end()) {
    // *it = 100;
    cout << *it << " ";
    it++;
    }
    cout << endl;
  }
  void test_list1() {
    list<int> L;
    L.push_back(1);
    L.push_back(2);
    L.push_back(3);
    L.push_back(4); 
    list<int>::iterator it = L.begin();
    while (it != L.end()) {
    *it *= 2;
    cout << *it << " ";
    it++;
    }
    cout << endl;
  }
  void test_list2() {
    list<int> L;
    L.push_back(2);
    L.push_back(4);
    L.push_back(6);
    L.push_back(8);
    print_list(L);
  }
  struct Date {
    int _year;
    int _month;
    int _day;
    Date(int year = 1, int month = 1, int day = 1) 
    : _year(year)
    , _month(month)
    , _day(day) 
    {}
  };
  void test_list3() {
    list<Date> L;
    L.push_back(Date(2022, 5, 1));
    L.push_back(Date(2022, 5, 2));
    L.push_back(Date(2022, 5, 3));
    list<Date>::iterator it = L.begin();
    while (it != L.end()) {
    cout << it->_year << "/" << it->_month << "/" << it->_day << endl;
    it++;
    }
    cout << endl;
  }
  void test_list4() {
    list<int> L1;
    L1.push_back(1);
    L1.push_back(2);
    L1.push_back(3);
    list<int> L2(L1);
    for (auto e : L2) cout << e << " ";
  }
  void test_list5() {
    list<int> L;
    L.push_back(1);
    L.push_back(2);
    L.push_back(3);
    cout << "删除前：";
    print_list(L);
    cout << "删除后：";
    L.clear();
    print_list(L);
  }
}

0x01 test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include "list.h"
int main(void)
{
  chaos::test_list1();
  return 0;
}

0x02 reverse_iterator.h

#define _CRT_SECURE_NO_WARNINGS 1
#include "list.h"
namespace chaos
{
  // Iterator是哪个容器的迭代器，reverse_iterator<Iterator>就可以
  // 适配出哪个容器的反向迭代器。复用的体现
  //template <class Iterator, class Ref, class Ptr>
  /* 定义反向迭代器 */
  template <class Iterator>
  class reverse_iterator {
  typedef reverse_iterator<Iterator, Ref, Ptr> self;
  typedef typename Iterator::Ref reference;  
  typedef typename Iterator::Ptr pointer;
  public:
  reverse_iterator(Iterator it)
    :_it(it)
  {}
  Ref operator*() {
    //return *_it;
    Iterator prev = _it;
    return *--prev;
  }
  Ptr operator->() {
    return &operator*();
  }
  self& operator++() {
    --_it;
    return *this;
  }
  self& operator--() {
    ++_it;
    return *this;
  }
  bool operator!= (const self& rit) const {
    return _it != rit._it;
  }
  private:
  Iterator _it;
  };
}


文章标签：
C++
关键词：
C++模板
C++ list
C++ const
C++运算符重载
C++框架
柠檬叶子C
目录
相关文章
oioihoii
|
2月前
|
存储 安全 编译器
第二问：C++中const用法详解
`const` 是 C++ 中用于定义常量的关键字，主要作用是防止值被修改。它可以修饰变量、指针、函数参数、返回值、类成员等，确保数据的不可变性。`const` 的常见用法包括：
oioihoii
135 2
百色彭于晏
|
6月前
|
存储 Java
Java学习笔记 List集合的定义、集合的遍历、迭代器的使用
Java学习笔记 List集合的定义、集合的遍历、迭代器的使用
百色彭于晏
101 4
睡觉待开机
|
6月前
|
编译器
【Bug记录】list模拟实现const迭代器类
【Bug记录】list模拟实现const迭代器类
睡觉待开机
47 0
ephemerals__
|
3月前
|
存储 编译器 C++
【c++】类和对象（下）（取地址运算符重载、深究构造函数、类型转换、static修饰成员、友元、内部类、匿名对象）
本文介绍了C++中类和对象的高级特性，包括取地址运算符重载、构造函数的初始化列表、类型转换、static修饰成员、友元、内部类及匿名对象等内容。文章详细解释了每个概念的使用方法和注意事项，帮助读者深入了解C++面向对象编程的核心机制。
ephemerals__
156 5
可能只会写BUG
|
5月前
|
C++
C++(十五) 运算符重载
C++中的运算符重载允许对已有运算符的功能进行重新定义，从而扩展语言功能、简化代码并提升效率。重载遵循特定语法，如 `friend 类名 operator 运算符(参数)`。重载时需注意不可新增或改变运算符数量、语义、优先级、结合性和返回类型。常见示例包括双目运算符 `+=` 和单目运算符 `-` 及 `++`。输入输出流运算符 `&lt;&lt;` 和 `&gt;&gt;` 也可重载。部分运算符只能作为成员函数重载。
可能只会写BUG
88 2
爱你三千遍斯塔克
|
7月前
|
文字识别 Java
文本，文字识别07，SpringBoot服务开发-入参和返回值,编写接口的时候，要注意识别的文字返回的是多行，因此必须是List集合，Bean层，及实体类的搭建
文本，文字识别07，SpringBoot服务开发-入参和返回值,编写接口的时候，要注意识别的文字返回的是多行，因此必须是List集合，Bean层，及实体类的搭建
爱你三千遍斯塔克
70 1
爱你三千遍斯塔克
|
7月前
|
前端开发
若依修改，配置了一个接口路径出现了，如何放通接口{ “msg“: “请求访问：/code/list，认证失败，无法访问系统资源“, “code“: 401}
若依修改，配置了一个接口路径出现了，如何放通接口{ “msg“: “请求访问：/code/list，认证失败，无法访问系统资源“, “code“: 401}
爱你三千遍斯塔克
1651 0
笨笨小乌龟
|
7月前
|
自然语言处理 程序员 C++
C++基础知识（五：运算符重载）
运算符重载是C++中的一项强大特性，它允许程序员为自定义类型（如类或结构体）重新定义标准运算符的行为，使得这些运算符能够适用于自定义类型的操作。这样做可以增强代码的可读性和表达力，使得代码更接近自然语言，同时保持了面向对象编程的封装性。
笨笨小乌龟
90 0
笨笨小乌龟
|
7月前
|
存储 算法 程序员
C++基础知识（八：STL标准库（Vectors和list））
C++ STL (Standard Template Library标准模板库) 是通用类模板和算法的集合，它提供给程序员一些标准的数据结构的实现如 queues(队列), lists(链表), 和 stacks(栈)等. STL容器的提供是为了让开发者可以更高效率的去开发，同时我们应该也需要知道他们的底层实现，这样在出现错误的时候我们才知道一些原因，才可以更好的去解决问题。
笨笨小乌龟
70 0
羑悻的小杀马特
|
2天前
|
编译器 C语言 C++
类和对象的简述（c++篇）
类和对象的简述（c++篇）
羑悻的小杀马特
51 28