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

【C++初阶】STL详解（八）List的模拟实现

2024-04-12 70
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【C++初阶】STL详解（八）List的模拟实现


list的再认识：

在之前List的介绍与使用中，我们知道list容器是一个带头双向循环链表，那么我们在模拟实现中，能不能先证明一下List是否是一个双向循环链表呢？

我们参考一下stl中list的源码：

我们看到，在源码中，list中有一个__list_node的节点，我们将这个链表的节点定义打开发现定义两个指针next，prev.

再来看一下它的空初始化：

通过观察源码中list的初始化，确实是一个双向循环链表。

接下来。我们就来自己实现一下里面的接口函数。

注意：在模拟实现中，我们采取用与与源码中相同的命名风格。

为防止与库里面的list重复，我们模拟实现将定义在自己的命名空间中。

初始化与定义节点：

首先，我们需要定义三个类，并用摸版进行封装：分别是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:

template<class T>
class list
{
  typedef list_node<T> Node;
public:
  //空初始化：
  void empty_init()
  {
    _head = new Node;
    _head->_next = _head;
    _head->_prev = _head;
  }
  //无参构造：
  list()
  {
    empty_init();
  }
  void push_Back(const T& x)
  {
    Node* tail = _head->_prev;
    Node* newnode = new Node(x);
    tail->_next = newnode;
    newnode->_prev = tail;
    newnode->_next = _head;
    _head->_prev = newnode;
  }
private:
  Node* _head;
};

这里我们写的是无参构造，以及实现了一个尾插接口：

尾插双向链表实现已经再简单不过了：

现在我们测试一下：

现在还不能进行遍历，因此我们自己要实现一个迭代器：

迭代器实现：

那么这个迭代器我们要作为怎么实现呢？

我们可以先回顾一下，在vector中，我们实现迭代器就是实现原生指针。

在vector中，给it解引用就可以访问到里面的数据，但是链表不行，因为链表中空间不是连续的。

那么应该怎么实现呢？其实这个就和我们之前的日期类一样，在日期类中我们用运算符重载与封装实现了对日期类的++操作。而我们的迭代器也使这样实现的。

这里我们需要实现迭代器的！=，*与++操作：

我们先看一下库里面的操作：

构造：

看一下库里面的操作：

库里面用了一个节点的指针进行构造，这是因为：单参数的构造函数支持隐式类型转换。

所以我们的构造就可以这样写：

__list_iterator(Node* node)
  :_node(node)
{
}

++

实现迭代器++，就是指针往后走的过程，注意返回的是迭代器。我们可以将迭代器重命名一下：

typedef __list_iterator<T> self;

实现代码：

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

解引用：*

返回节点里面的数据即可：

T& operator*()
{
  return _node->_data;
}

！=

两个迭代器进行比较，实质两个指针比较。

//两个迭代器进行比较，两个指针比较
bool operator!=(const self& s)
{
  return _node  !=  s._node;
}

基本框架搭建：

这样基本上迭代器的基本架子就完成了：

typedef __list_iterator<T> iterator;
iterator begin()
{
  return _head->_next;
}
iterator end()
{
  return _head;
}

在list中定义一下迭代器。迭代器开始位置就是返回哨兵位头节点的下一个位置，结束位置就是返回哨兵位的地址。

测试一下：

void test_list1()
  {
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(5);
    list<int>::iterator it = lt.begin();
    while (it != lt.end())
    {
      //*it += 20;
      cout << *it << " ";
      ++it;
    }
    cout << endl;
}

测试结果：

有了迭代器就有范围for：

for (auto e : lt)
{
  cout << e << " ";
}
cout << endl;

总结：其实会发现就是在模拟指针，但他的底层细节很大。所以迭代器体现了封装的强势之处。封装屏蔽底层差异和实现细节，提供统一的访问修改遍历方式。这样我们就不用关注他的底层是什么.

举个例子：

set<int> s;
  s.insert(1);
  s.insert(3);
  s.insert(2);
  s.insert(4);
  set<int>::iterator sit = s.begin();
  while (sit != s.end())
  {
    cout << *sit << " ";
    ++sit;
  }
  cout << endl;
}

这里的set就是树，我们也可以依然用这个迭代器进行遍历。

–

实现迭代器++，就是指针往前走的过程，注意返回的是迭代器。

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;
}

->

在讲->重载之前，先看一下这个示例：

struct AA
{
  AA(int a1 = 0, int a2 = 0)
    :_a1(a1)
    , _a2(a2)
  {}
  int _a1;
  int _a2;
};
list<AA> lt;
lt.push_back(AA(1, 1));
lt.push_back(AA(2, 2));
lt.push_back(AA(3, 3));
list<AA>::iterator it = lt.begin();
while (it != lt.end())
{
    cout << *it << endl;
  ++it;
}
cout << endl;

在这里就访问不了，因为自定义类型不支持类型。

这里我们回顾一下之前的知识，对与内置类型的指针，我们可以采用*来进行解引用。对于自定义类型的指针，我们要用->来进行解引用。

int* p = new int;
*p = 1;
AA* ptr = new AA;
ptr->_a1 = 1;

实现->

T* operator->()
{
  return &_node->_data;
}

==

两个迭代器进行比较，就是两个指针比较

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

const迭代器

在实现const迭代器之前，首先要知道一点，const迭代器是一个完全不一样的类，所以不能将非const迭代器前加const就变成const迭代器。

因此我们可以list类中在定义一个const迭代器：

typedef __list_const_iterator<T> const_iterator;
const_iterator begin() const
{
  return _head->_next;
}
const_iterator end() const
{
  return _head;
}

在单独实现一个const迭代器的类：

template<class T>
struct __list_const_iterator
{
   ....
}

const迭代器基本的功能与非const迭代器相似，只有在解引用时不同：

// *it = 10
const T& operator*()
{
  return _node->_data;
}
// it->a1 = 10
const T* operator->()
{
  return &_node->_data;
}

测试一下：

void print_list(const list<int>& lt)
{
  list<int>::const_iterator it = lt.begin();
  while (it != lt.end())
  {
    //*it = 10;
    cout << *it << " ";
    ++it;
  }
  cout << endl;
  for (auto e : lt)
  {
    cout << e << " ";
  }
  cout << endl;
}
void test_list4()
{
  list<int> lt;
  lt.push_back(1);
  lt.push_back(2);
  lt.push_back(3);
  lt.push_back(4);
  lt.push_back(5);
  print_list(lt);
}

但是这样实现，还是太冗余了，因为非const和const只有返回值不同，那么还有优化的空间吗？

我们看一下库里面的实现:

库里面定义只定义了同一个类模版的迭代器，只是这两个迭代器之间的摸版参数不同，实例化的参数不同，就是完全不一样的类型。也就是说把能靠模版实现的就写一份，让编译器搞。

所以我们可以将我们的迭代器进行进一步优化：

template<class T>
class list
{
  typedef list_node<T> Node;
public:
  typedef __list_iterator<T,T&,T*> iterator;
  typedef __list_iterator<T,const T&,const T*> const_iterator;
  ....
}
// T T& T*
// T cosnt T& const T*
template<class T, class Ref, class Ptr>
struct __list_iterator
{
  typedef list_node<T> Node;
  /*typedef __list_iterator<T> self;*/
  typedef __list_iterator<T, Ref, Ptr> self;
  Node* _node;
  ...
}

到这里，我们的迭代器就全部实现完了。

拓展：

在刚才的测试函数中，有一个print_list函数，但是这个测试函数里面的数据我们给定的是int,那我要是其他类型的呢，这个函数又该如何修改呢？

其实很简单：我们加一个摸版参数即可：

template<typename T>
void print_list(const list<T>& lt)
{
  typename list<T>::const_iterator it = lt.begin();
  while (it != lt.end())
  {
    //*it = 10;
    cout << *it << " ";
    ++it;
  }
  cout << endl;
}

测试一下：

注意：这里我们没有用class这个摸版参数，这是因为：

list是一个未实例化的类模板，编译器不能去他里面去找

编译器就无法确定：list::const_iterator是内嵌类型，还是静态成员变量

前面加一个typename就是告诉编译器，这里是一个类型，等list实例化后再去类里面去取

拓展2：

如果要是将刚才的类在改造一下呢？

比如：

我要打印以下内容：

vector<string> v;
v.push_back("222222222222222222222");
v.push_back("222222222222222222222");
v.push_back("222222222222222222222");
v.push_back("222222222222222222222");

这个函数对于我们的printf_list就不适用了，因为我们的print_list就只适用于链表。

这里我们就可以写一个容器（container）的打印函数：

template<typename Container>
void print_Container(const Container& con)
{
  typename Container::const_iterator it = con.begin();
  while (it != con.end())
  {
    cout << *it << " ";
    ++it;
  }
  cout << endl;
}

测试结果：

总结一下：

摸版实现了泛型编程，而泛型编程的本质，就是本来我们干的活，交给了编译器。

相关函数接口：

有了迭代器的实现，我们就可以实现一下链表的相关接口：

Insert：

Insert:在pos位置之前插入：

iterator insert(iterator pos, const T& x)
{
  Node* cur = pos._node;
  Node* newnode = new Node(x);
  Node* prev = cur->_prev;
  // prev newnode cur
  prev->_next = newnode;
  newnode->_prev = prev;
  
  newnode->_next = cur;
  cur->_prev = newnode;
  
  ++_size;
  return iterator(newnode);
}

Insert迭代器不会产生失效的问题，因为没有扩容。

erase:

在指定位置删除：

iterator erase(iterator pos)
{
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* next = cur->_next;
      delete cur;
      prev->_next = next;
      next->_prev = prev;
      --_size;
      return iterator(next);
}

注意：erase的迭代器会失效，所以我们加个返回值。

实现了insert和erase后，我们就可以服用来实现头插，头删，尾插，尾删。

push_front与pop_fronr

具体实现：

头插：

//头插
void push_front(const T& x)
{
  insert(begin(), x);
}

头删：

//头删
void pop_front()
{
  erase(begin());
}

push_back与pop_back

具体实现：

尾插：

void push_back(const T& x)
{
  insert(end(), x);
}

尾删：

//尾删
void pop_back()
{
  erase(--end());
}

size:

为了方便计算大小，我们还可以再实现一个函数：

size_t size()
{
  return _size;
}

clear与析构：

clear：清理空间，我们可以采取迭代器访问的方式，逐个将节点释放。

//清理空间：
void clear()
{
  iterator it = begin();
  while (it != end())
  {
    it = erase(it);
  }
}

析构：我们可以先清理空间，在将头节点释放即可。

//析构
~list()
{
  clear();
  delete _head;
  _head = nullptr;
}

拷贝构造：

我们可以采用范围for来进行拷贝构造：

//拷贝构造：
// lt2(lt1)
//list(const list<T>& lt)
list(list<T>& lt)
{
  empty_init();
  for (auto e : lt)
  {
    push_back(e);
  }
}

赋值重载：

传统写法：

list<int>& operator=(const list<int>& lt)
{
  if (this != &lt)
  {
    clear();
    for (auto e : lt)
    {
      push_back(e);
    }
  }
  return *this;
}

现代写法：

void swap(list<T>& lt)
{
  std::swap(_head, lt._head);
  std::swap(_size, lt._size);
}
// lt3 = lt1
list<int>& operator=(list<int> lt)
{
  swap(lt);
  return *this;
}

对比vector与list

文章标签：
C++
编译器
容器
关键词：
C++ list
C++ stl
stl List
C++ stl list
C++初阶
小小unicorn
目录
相关文章
羑悻的小杀马特
|
2天前
|
算法 C++ 容器
模拟实现c++中的list模版
模拟实现c++中的list模版
羑悻的小杀马特
30 23
ephemerals__
|
24天前
|
C++ 容器
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器：栈（stack）和队列（queue）。容器适配器是在已有容器基础上添加新特性或功能的结构，如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数（empty、size、top/front/back、push/pop、swap），并提供了使用示例和模拟实现代码。通过这些内容，读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后，作者鼓励读者点赞支持。 总结：本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现，帮助读者掌握这两种容器适配器的特性和应用场景。
ephemerals__
55 21
ephemerals__
|
2月前
|
编译器 C语言 C++
【c++丨STL】list模拟实现（附源码）
本文介绍了如何模拟实现C++中的`list`容器。`list`底层采用双向带头循环链表结构，相较于`vector`和`string`更为复杂。文章首先回顾了`list`的基本结构和常用接口，然后详细讲解了节点、迭代器及容器的实现过程。 最终，通过这些步骤，我们成功模拟实现了`list`容器的功能。文章最后提供了完整的代码实现，并简要总结了实现过程中的关键点。 如果你对双向链表或`list`的底层实现感兴趣，建议先掌握相关基础知识后再阅读本文，以便更好地理解内容。
ephemerals__
42 1
ephemerals__
|
2月前
|
算法 C语言 C++
【c++丨STL】list的使用
本文介绍了STL容器`list`的使用方法及其主要功能。`list`是一种双向链表结构，适用于频繁的插入和删除操作。文章详细讲解了`list`的构造函数、析构函数、赋值重载、迭代器、容量接口、元素访问接口、增删查改操作以及一些特有的操作接口如`splice`、`remove_if`、`unique`、`merge`、`sort`和`reverse`。通过示例代码，读者可以更好地理解如何使用这些接口。最后，作者总结了`list`的特点和适用场景，并预告了后续关于`list`模拟实现的文章。
ephemerals__
69 7
蓝易云
|
2月前
|
存储 编译器 C++
C++ initializer_list&&类型推导
在 C++ 中，`initializer_list` 提供了一种方便的方式来初始化容器和传递参数，而右值引用则是实现高效资源管理和移动语义的关键特性。尽管在实际应用中 `initializer_list&&` 并不常见，但理解其类型推导和使用方式有助于深入掌握现代 C++ 的高级特性。
蓝易云
28 4
ephemerals__
|
2月前
|
存储 编译器 C语言
【c++丨STL】vector模拟实现
本文深入探讨了 `vector` 的底层实现原理，并尝试模拟实现其结构及常用接口。首先介绍了 `vector` 的底层是动态顺序表，使用三个迭代器（指针）来维护数组，分别为 `start`、`finish` 和 `end_of_storage`。接着详细讲解了如何实现 `vector` 的各种构造函数、析构函数、容量接口、迭代器接口、插入和删除操作等。最后提供了完整的模拟实现代码，帮助读者更好地理解和掌握 `vector` 的实现细节。
ephemerals__
67 0
好奇的菜鸟
|
8月前
|
安全 Java
java线程之List集合并发安全问题及解决方案
java线程之List集合并发安全问题及解决方案
好奇的菜鸟
1120 1
2G冲浪词条
|
7月前
|
Java API Apache
怎么在在 Java 中对List进行分区
本文介绍了如何将列表拆分为给定大小的子列表。尽管标准Java集合API未直接支持此功能，但Guava和Apache Commons Collections提供了相关API。
2G冲浪词条
77 1
嘟嘟嘟嘟嘟嘟
|
7月前
|
运维 关系型数据库 Java
PolarDB产品使用问题之使用List或Range分区表时，Java代码是否需要进行改动
PolarDB产品使用合集涵盖了从创建与管理、数据管理、性能优化与诊断、安全与合规到生态与集成、运维与支持等全方位的功能和服务，旨在帮助企业轻松构建高可用、高性能且易于管理的数据库环境，满足不同业务场景的需求。用户可以通过阿里云控制台、API、SDK等方式便捷地使用这些功能，实现数据库的高效运维与持续优化。
嘟嘟嘟嘟嘟嘟
52 3
一颗小谷粒
|
7月前
|
存储 安全 Java
详解Java中集合的List接口实现的ArrayList方法 | Set接口实现的HashSet方法
详解Java中集合的List接口实现的ArrayList方法 | Set接口实现的HashSet方法
一颗小谷粒
85 3