【C++/STL】:list容器的深度剖析及模拟实现

简介: 【C++/STL】:list容器的深度剖析及模拟实现

🚀前言

点击跳转到文章:【list的基本使用】

要模拟实现list,必须要熟悉list的底层结构以及其接口的含义,list的底层是带头双向循环链表,通过上一篇文章的学习,这些内容已基本掌握,现在我们来模拟实现list容器的主要接口。

与前面的vector类似,由于使用了模板,也只分成.cpp和.h两个文件。

.cpp文件里放节点类,迭代器类,list类及其成员函数,测试函数的实现,在.h文件里进行测试

本文的重点是:对三个类的区分与理解,迭代器类的实现

🚀一,节点类

1.为什么定义节点结构体时使用struct而不是class?

答:(1)其实用class也可以,但是class与struct默认的访问限定不同,当没有声明公有,私有时,struct内容默认是公有,class内容默认的私有,所以用class要加上public

(2)当我们用class没有加上public,也没有实例化对象时,编译不会报错(报私有成员的错误),因为模版是不会被细节编译的。只有当我们实例化出对象,模版才会被编译,并且类的实例化并不是对所有成员函数都实例化,而是调用哪个成员函数就实例化哪个。这叫做按需实例化

2.可用匿名对象初始化。如果T是自定义类型,则调用其默认构造,并且T是内置类型也升级成了有默认构造的概念了。

template <class T>
struct ListNode
{
  ListNode<T>* _next;
  ListNode<T>* _prev;
  T _data;
  ListNode(const T& data = T())
    :_next(nullptr)
    ,_prev(nullptr)
    ,_data(data)
  {}
};

🚀二,迭代器类

前面学习的string类和vector的迭代器用的是原生指针类型,即T*。但是在list容器中是不能这样的,因为前面两者的底层物理空间是连续的,符合迭代器++与- -的行为。但是list是由一个一个节点构成的,物理空间不连续,Node*的++和- -不符合迭代器的行为,无法变遍历

所以用一个类把Node* 封装,就可以重载运算符,使得用起来像内置类型,但会转换成函数调用,继而控制Node*的行为

1,普通迭代器类的实现

遍历需要的核心运算符重载是 *,!=,++ 和 ->。所以只需要利用带头双向循环链表的特性,对Node * 进行封装,从而控制Node * 的行为。

class ListIterator
{
  typedef ListNode<T> Node;
  typedef ListIterator<T> Self;//名字变得简短
public:
  Node* _node;//定义一个节点指针
  ListIterator(Node* node)
    :_node(node)
  {}
  //前置:返回之后的值
  //++it;//返回与自己一样的类型
  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;
  }
  T& operator*()
  {
    return _node->_data;
  }
  
  //返回的是数据的地址
  T* operator->()
  {
    return &_node->_data;
  }
  bool operator!=(const Self& it)
  {
    return _node != it._node;
  }
  bool operator==(const Self& it)
  {
    return _node == it._node;
  }
};

2,->运算符的使用场景

假设某个场景下存在一个坐标类:

struct Pos
{
  int _row;
  int _col;
  Pos(int row = 0,int col = 0)
    :_row(row)
    ,_col(col)
  {}
};

如果我们插入坐标,并且想要打印出坐标,该如何遍历?

错误示范

void test_list2()
{
  list<Pos> lt1;
  lt1.push_back(Pos(100, 100));//使用匿名对象
  lt1.push_back(Pos(200, 200));
  lt1.push_back(Pos(300, 300));
  
  //这里的it是Pos*,是结构体指针
  list<Pos>::iterator it = lt1.begin();
  while (it != lt1.end())
  {
    cout << *it << " ";//err
    ++it;
  }
  cout << endl;
}

原因:因为这里的*it返回的是Pos自定义类型,而访问自定义类型需要需要在类中自己重载流插入(<<),这里并没有重载,所以报错

正确操遍历的两种方式

方式1:通过.操作符直接访问结构体的成员变量(一般不这样访问数据)。

cout << (*it)._row << ":" << (*it)._col << endl;//ok

方式2:通过重载->运算符,对结构体指针进行解引用。

cout << it.operator->()->_row << ":" << it.operator->()->_col << endl;//ok

注意:其实这里严格来说是有两个箭头,第一个运算符重载的调用 it.operator->() 返回的是 Pos*,第二个箭头才是原生指针,Pos*再用箭头访问。为了可读性,省略了一个->

void test_list2()
{
  list<Pos> lt1;
  lt1.push_back(Pos(100, 100));//使用匿名对象
  lt1.push_back(Pos(200, 200));
  lt1.push_back(Pos(300, 300));
  
  //这里的it是Pos*,是结构体指针
  list<Pos>::iterator it = lt1.begin();
  while (it != lt1.end())
  { 
    //方式1:
    //cout << (*it)._row << ":" << (*it)._col << endl;//ok
    //*it就是Pos结构体,再用.操作符访问成员
    
    //方式2:
    cout << it->_row << ":" << it->_col << endl;//ok
    //cout << it.operator->()->_row << ":" << it.operator->()->_col << endl;//ok
    
    ++it;
  }
  cout << endl;
}

3,const迭代器类的实现

在我们遍历数据时,有时会写一个打印函数,引用传参,一般建议加const,这就出现了一个const链表

void Func(const list<int>& lt1)
{
  list<int>::const_iterator it = lt1.begin();
  while (it != lt1.end())
  {
    cout << *it << " ";
    ++it;
  }
  cout << endl;
}

const迭代器不是在普通迭代器前面加const,即不是const iterator

//err 这样使it本身也不能++了
const list< int >::iterator it = it.begin();

const 迭代器目的:本身可以修改,指向的内容不能修改,类似const T* p。

所以我们要再定义一个类,控制*和->的返回值就可以了。

template <class T>
class ListConstIterator
{
  typedef ListNode<T> Node;
  typedef ListConstIterator<T> Self;//名字变得简短
public:
  Node* _node;//定义一个节点指针
  ListConstIterator(Node* node)
    :_node(node)
  {}
  //前置:返回之后的值
  //++it;//返回与自己一样的类型
  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;
  }
  // 所以我们要再定义一个类,使用const控制*和->的返回值就可以
  const T& operator*()
  {
    return _node->_data;
  }
  const T* operator->()
  {
    return &_node->_data;
  }
  bool operator!=(const Self& it)
  {
    return _node != it._node;
  }
  bool operator==(const Self& it)
  {
    return _node == it._node;
  }
};

4,通过模板参数,把两个类型的迭代器类结合

可以发现,其实普通迭代器和const迭代器的本质区别是 * 和 ->,这两个运算符的返回类型的变化。两个类冗余,所以可以通过模板,给不同的模板参数,让编译器自己实例化两个类

template <class T,class Ref,class Ptr>
struct ListIterator
{
  typedef ListNode<T> Node;
  typedef ListIterator<T, Ref, Ptr> Self;//名字变得简短
  Node* _node;//定义一个节点指针
  ListIterator(Node* node)
    :_node(node)
  {}
  //前置:返回之后的值
  //++it;//返回与自己一样的类型
  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;
  }
  Ref operator*()
  {
    return _node->_data;
  }
  Ptr operator->()
  {
    return &_node->_data;
  }
  bool operator!=(const Self& it)
  {
    return _node != it._node;
  }
  bool operator==(const Self& it)
  {
    return _node == it._node;
  }
};

5,迭代器类的一些问题的思考

(1) 类中是否需要写析构函数

这个迭代器类不要写析构函数,因为这里的节点不是迭代器的,是链表的,不用把它释放。我们使用begin,end返回节点给迭代器,是借助迭代器修改,访问数据,所以我们不需要释放

(2) 类中是否需要写拷贝构造进行深拷贝和写赋值拷贝

这里也不需要写拷贝构造进行深拷贝,因为这里要的就是浅拷贝。begin返回了第一个节点的迭代器给it,这里就是用默认生成的拷贝构造,浅拷贝给it,那这两个迭代器就指向同一个节点,所以这里用默认的拷贝构造和赋值拷贝就可以了

🚀三,list 类

1,list类的结构

template <class T>
class list
{
  typedef ListNode<T> Node;
public:
  //物理空间不是连续的,不符合迭代器的行为,无法遍历
  //typedef Node* iterator;
  //规范命名
  //typedef ListIterator<T> iterator;
  //typedef ListConstIterator<T> const_iterator;
  typedef ListIterator<T, T&, T*> iterator;
  typedef ListIterator<T, const T&, const T*> const_iterator;
  //………………
private:
  Node* _head;
};

2,迭代器的实现

包含普通迭代器和const迭代器

iterator begin()
{
  //iterator it(_head->_next);
  //return it;
  return iterator(_head->_next);//使用匿名对象
}
iterator end()
{
  return iterator(_head);
}
const_iterator begin()const
{
  return const_iterator(_head->_next);
}
const_iterator end()const
{
  return const_iterator(_head);
}

3,插入数据insert

iterator insert(iterator pos, const T& x)
{
  Node* cur = pos._node;//找到当前节点
  Node* newnode = new Node(x);//申请节点
  Node* prev = cur->_prev;//找到前一个节点
  //prev newnode cur 进行链接
  newnode->_next = cur;
  cur->_prev = newnode;
  prev->_next = newnode;
  newnode->_prev = prev;
  return iterator(newnode);
}

注意:链表的insert没有迭代器失效问题,因为没有扩容的概念,pos位置的节点不会改变。但是STL库里insert也给了返回值,返回的是新插入位置的迭代器

4,删除数据erase

iterator erase(iterator pos)
{
  assert(pos != end());//防止删除头节点
  Node* cur = pos._node;//找到当前节点
  Node* prev = cur->_prev;//找到前一个节点
  Node* next = cur->_next;//找到后一个节点
  prev->_next = next;
  next->_prev = prev;
  delete cur;
  return iterator(next);
}

注意:链表的erase后有迭代器失效问题,pos失效了,因为pos指向的节点被释放了。所以也要返回值,返回的是删除节点的下一个节点的迭代器

5,头插,头删,尾插,尾删

可以复用前面的 insert和 erase

//尾插:end()的下一个位置
void push_back(const T& x)
{
  //Node* newnode = new Node(x);//申请节点并且初始化
  //Node* tail = _head->_prev;
  链接节点
  //tail->_next = newnode;
  //newnode->_prev = tail;
  //_head->_prev = newnode;
  //newnode->_next = _head;
  insert(end(), x);
}
//尾删
void pop_back()
{
  erase(--end());//注意:前置--
}
//头插:在begin前面插入
void push_front(const T& x)
{
  insert(begin(), x);
}
//头删
void pop_front()
{
  erase(begin());
}

6,常见构造函数的实现

主要包含:构造函数,拷贝构造,initializer_list构造(列表构造)

注意:由于这些都是在有哨兵位节点的前提下实现的,所以可以把申请哨兵位头节点这一步骤提取出来。

//空初始化,申请哨兵位头节点
void empty_init()
{
  _head = new Node();
  _head->_next = _head;
  _head->_prev = _head;
}
list()
{
  empty_init();
}
//拷贝构造:直接复用尾插,前提要有哨兵位头节点
//lt2(lt1)
list(const list<T>& lt)
{
  empty_init();
  //注意:使用范围for时加上const和&
  for (const auto& e : lt)
  {
    push_back(e);
  }
}
//initializer_list构造,前提要有哨兵位头节点
list(initializer_list<T> il)
{
  empty_init();
  for (const auto& e : il)
  {
    push_back(e);
  }
}

7,析构函数

析构函数的作用是:删除整个链表结构,包括哨兵位节点

//清空当前数据 留头节点,其余节点释放
void clear()
{
  auto it = begin();
  while (it != end())
  {
    //返回删除节点的下一个节点的迭代器
    it = erase(it);
  }
}
//析构:销毁整个链表
~list()
{
  clear();
  delete _head;
  _head = nullptr;
}
目录
相关文章
|
7天前
|
算法 C语言 C++
【c++丨STL】list的使用
本文介绍了STL容器`list`的使用方法及其主要功能。`list`是一种双向链表结构,适用于频繁的插入和删除操作。文章详细讲解了`list`的构造函数、析构函数、赋值重载、迭代器、容量接口、元素访问接口、增删查改操作以及一些特有的操作接口如`splice`、`remove_if`、`unique`、`merge`、`sort`和`reverse`。通过示例代码,读者可以更好地理解如何使用这些接口。最后,作者总结了`list`的特点和适用场景,并预告了后续关于`list`模拟实现的文章。
22 7
|
16天前
|
存储 编译器 C++
C++ initializer_list&&类型推导
在 C++ 中,`initializer_list` 提供了一种方便的方式来初始化容器和传递参数,而右值引用则是实现高效资源管理和移动语义的关键特性。尽管在实际应用中 `initializer_list&&` 并不常见,但理解其类型推导和使用方式有助于深入掌握现代 C++ 的高级特性。
16 4
|
28天前
|
存储 设计模式 C++
【C++】优先级队列(容器适配器)
本文介绍了C++ STL中的线性容器及其适配器,包括栈、队列和优先队列的设计与实现。详细解析了`deque`的特点和存储结构,以及如何利用`deque`实现栈、队列和优先队列。通过自定义命名空间和类模板,展示了如何模拟实现这些容器适配器,重点讲解了优先队列的内部机制,如堆的构建与维护方法。
35 0
|
2月前
|
存储 搜索推荐 C++
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器2
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器
62 2
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器2
|
2月前
|
存储 算法 C++
【C++打怪之路Lv10】-- list
【C++打怪之路Lv10】-- list
23 1
|
2月前
|
存储 编译器 C++
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
78 2
|
2月前
|
存储 缓存 C++
C++番外篇——list与vector的比较
C++番外篇——list与vector的比较
26 0
|
2月前
|
C++
C++番外篇——list的实现
C++番外篇——list的实现
22 0
|
2月前
|
存储 C++ 容器
C++入门9——list的使用
C++入门9——list的使用
21 0
|
6月前
|
安全 Java
java线程之List集合并发安全问题及解决方案
java线程之List集合并发安全问题及解决方案
1027 1