AI 助理
备案控制台
开发者社区 云原生 文章 正文

C++初阶--list

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

list

C++的list是标准模板库中的一个容器，用于存储和管理元素的双向链表。提供了一系列访问和修改数据的函数；

使用时需要包含头文件

#include< list >

下面演示下它的一些基础功能

使用list

list的遍历

int main()
{
  list<int> lt;
  
  lt.push_back(1);//尾插
  lt.push_back(2);
  lt.push_back(3);
  lt.push_back(4);
  list<int>::iterator it = lt.begin();
  while (it != lt.end())
  {
    *it += 10;
    cout << *it << " ";
    it++;
  }
  cout << endl;
  for (auto e : lt)
  {
    cout << e << " ";
  }
  cout << endl;
  lt.reverse();//倒置
  for (auto e : lt)
  {
    cout << e << " ";
  }
  cout << endl;
}

对于list的遍历，常用迭代器来进行访问遍历，list没有vector的[]访问符，也就不通过下标来进行访问；

去重复值

int main()
{
  list<int> lt;
  lt.push_back(1);
  lt.push_back(1);
  lt.push_back(2);
  lt.push_back(2);
  lt.push_back(3);
  lt.push_back(4);
  lt.push_back(4);
  lt.push_back(4);
  lt.unique();//去重复值
  for (auto e : lt)
  {
    cout << e << " ";
  }
  cout << endl;
}

splice

int main()
{
  list<int> lt;
  lt.push_back(1);
  lt.push_back(2);
  lt.push_back(3);
  lt.push_back(4);
  lt.push_back(5);
  for (auto e : lt)
  {
    cout << e << " ";
  }
  cout << endl;
  lt.splice(lt.end(), lt, find(lt.begin(), lt.end(), 2));
  for (auto e : lt)
  {
    cout << e << " ";
  }
  cout << endl;
}

自我实现list

初始化

push_back()

list的迭代器

list提供了迭代器，用来遍历列表中的元素。可以通过解引用来进行访问元素。

测试1结果：

insert和erase

析构、拷贝构造、赋值

当时为什么要将初始化empty_init()单独分离出来，就是因为也要让拷贝构造也要初始化，如果拷贝构造没有初始化，将会报错；

赋值还是利用了创建一个临时对象，该对象拷贝实参对象的内容，然后让临时对象与*this进行交换,就完成了赋值；

#pragma once
#include<assert.h>
#include"reverse_iterator.h"
namespace fnc
{
  //链表结构
  template <class T>
  struct ListNode
  {
    ListNode<T>* _next;
    ListNode<T>* _prev;
    T _Data;
    //对链表结构的初始化
    ListNode(const T& x = T())
      :_next(nullptr),
      _prev(nullptr),
      _Data(x)
    {
    }
  };
  //链表的迭代器
  template <class T, class Ref, class Ptr>
  struct __list_iterator
  {
    typedef ListNode<T> Node;
    typedef __list_iterator<T, Ref, Ptr> self;
    Node* _node;
    __list_iterator(Node* x)
      :_node(x)
    {}
    //前置++
    self& operator++()
    {
      _node = _node->_next;
      return *this;
    }
    //后置++
    self operator++(int)
    {
      self tmp(*this);
      _node = _node->_next;
      return tmp;
    }
    self& operator--()
    {
      _node = _node->_prev;
      return *this;
    }
    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& s)
    {
      return _node != s._node;
    }
    bool operator==(const self& s)
    {
      return _node == s._node;
    }
  };
  template <class T>
  class list
  {
    typedef ListNode<T> Node;
  public:
    //typedef __list_iterator<T, T&, T*> iterator;
    //typedef __list_iterator<T, const T&, const T*> const_iterator;
    //typedef ReverseIterator<iterator, T&, T*> RIterator;
    //typedef ReverseIterator<const_iterator, const T&, const T*> const_RIterator;
    iterator begin()
    {
      //return iterator(_head_next);
      return _head->_next;//隐式类型转换
    }
    iterator end()
    {
      return _head;
    }
    void empty_init()
    {
      _head = new Node;
      _head->_next = _head;
      _head->_prev = _head;
    }
    list()
    {
      empty_init();
    }
    void clear()
    {
      iterator it = begin();
      while (it != end())
      {
        it = erase(it);
      }
    }
    ~list()
    {
      clear();
      delete _head;
      _head = nullptr;
    }
    //拷贝构造
    list(list<T>& lt)
    {
      empty_init();
      for (const auto& e : lt)
      {
        push_back(e);
      }
    }
    void swap(list<T>& tmp)
    {
      std::swap(_head, tmp._head);
    }
    //赋值
    list<T>& operator=(list<T> lt)//?
    {
      swap(lt);
      return *this;
    }
    void push_back(const T& x)
    {
      /*Node* newnode = new Node(x);
      Node* tail = _head->_prev;
      tail->_next = newnode;
      newnode->_prev = tail;
      newnode->_next = _head;
      _head->_prev = newnode;*/
      insert(end(), x);
    }
    void push_front(const T& x)
    {
      insert(begin(), x);
    }
    void pop_back()
    {
      erase(--end());
    }
    void pop_front()
    {
      erase(begin());
    }
    //在pos位置前插入
    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;
      newnode->_next = cur;
      cur->_prev = newnode;
      return newnode;
    }
    //删除pos结点的
    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 next;
    }
    void func()
    {
      //内置类型
      Node* it1 = _head->_next;
      //自定义类型
      iterator it2 = _head->_next;
      *it1;
      it1++;
      *it2;
      it2++;
    }
  private:
    Node* _head;
  };
  void print_list(const list<int>& lt)
  {
    list<int>::const_iterator it = lt.begin();
    while (it != lt.end())
    {
      cout << *it << " ";
      it++;
    }
    cout << endl;
  }
  void test_list3()
  {
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    cout << "原链表:";
    for (auto e : lt)
    {
      cout << e << " ";
    }
    cout << endl;
    lt.push_back(66);
    lt.push_front(44);
    cout << "前插后插：";
    for (auto e : lt)
    {
      cout << e << " ";
    }
    cout << endl;
    list<int> lt2;
    lt2.push_back(12);
    lt2.push_back(23);
    lt2.push_back(34);
    lt2.push_back(45);
    lt = lt2;
    cout << "lt赋值之后:";
    for (auto e : lt)
    {
      cout << e << " ";
    }
    cout << endl;
    list<int> lt3(lt);
    cout << "lt3拷贝构造";
    for (auto e : lt3)
    {
      cout << e << " ";
    }
    cout << endl;
  }
  
}

const迭代器

运算符->

解释：

原始指针与迭代器

反向迭代器

反向迭代器是一种特殊类型的迭代器，用于逆序遍历容器中的元素。

#pragma once
namespace fnc
{
  template <class iterator, class Ref, class Ptr>
  struct ReverseIterator
  {
    typedef ReverseIterator<iterator,Ref,Ptr> Self;
    iterator cur;
    ReverseIterator(iterator it)
      :cur(it)
    {}
    Self& operator++()
    {
      --cur;
      return *this;
    }
    Self& operator++(int)
    {
      Self tmp = *this;
      --cur;
      return tmp;
    }
    Ref operator*()
    {
      iterator tmp = cur;
      return *--tmp;
    }
    Ptr operator->()
    {
      iterator tmp = cur;
      return  &(*--tmp);
    }
    bool operator!=(const Self& s)
    {
      return cur != s.cur;
      
    }
    bool operator==(const Self& s)
    {
      return cur == s.cur;
    }
  };
}

文章标签：
C++
容器
存储
关键词：
C++ list
C++初阶
C++初阶list
诡异森林。
目录
相关文章
chian-ocean
|
1月前
|
存储 缓存 C语言
【C++】list介绍以及模拟实现（超级详细）
【C++】list介绍以及模拟实现（超级详细）
chian-ocean
47 5
大柏怎么被偷了
|
1月前
|
存储 缓存 算法
【C++】list的模拟实现
【C++】list的模拟实现
大柏怎么被偷了
18 0
大柏怎么被偷了
|
1月前
|
存储 C++ 容器
【C++】list的认识与使用
【C++】list的认识与使用
大柏怎么被偷了
23 0
დ旧言~
|
2月前
|
存储 Java C++
【c++】list详细讲解
【c++】list详细讲解
დ旧言~
33 5
დ旧言~
|
2月前
|
Java C++ Python
【c++】list 模拟
【c++】list 模拟
დ旧言~
20 1
ForcibleBugMaker
|
2月前
|
存储 编译器 C语言
【C++】list模拟实现
本文档介绍了C++ STL中`list`容器的模拟实现，包括`ListNode`节点类、迭代器类和`list`类的详细设计。`ListNode`模板类存储数据并维护前后指针；`ListIterator`是一个复杂的模板类，提供解引用、自增/自减以及比较操作。`list`类包含了链表的各种操作，如插入、删除、访问元素等，并使用迭代器作为访问接口。实现中，迭代器不再是简单的指针，而是拥有完整功能的对象。此外，文档还提到了迭代器的实现对C++语法的特殊处理，使得`it-&gt;_val`的写法成为可能。文章通过分步骤展示`list`的各个组件的实现，帮助读者深入理解STL容器的内部工作原理。
ForcibleBugMaker
24 2
ForcibleBugMaker
|
2月前
|
算法 搜索推荐 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`，因链表结构不利于快速排序
ForcibleBugMaker
26 2
ForcibleBugMaker
|
2月前
|
C++ 容器
【C++】list的使用（下）
这篇博客探讨了C++ STL中`list`容器的几个关键操作，包括`splice()`、`remove()`、`remove_if()`和`unique()`。`splice()`允许高效地合并或移动`list`中的元素，无需构造或销毁。`remove()`根据值删除元素，而`remove_if()`则基于谓词移除元素。`unique()`则去除连续重复的元素，可选地使用自定义比较函数。每个操作都附带了代码示例以说明其用法。
ForcibleBugMaker
27 2
ForcibleBugMaker
|
2月前
|
编译器 C++ 容器
【C++】list的使用（上）
迭代器在STL中统一了访问接口，如`list`的`begin()`和`end()`。示例展示了如何使用正向和反向迭代器遍历`list`。注意`list`的迭代器不支持加减操作，只能用`++`和`--`。容器的`empty()`和`size()`用于检查状态和获取元素数。`front()`和`back()`访问首尾元素，`assign()`重载函数用于替换内容，`push_*/pop_*`管理两端元素，`insert()`插入元素，`erase()`删除元素，`resize()`调整大小，`clear()`清空容器。这些接口与`vector`和`string`类似，方便使用。
ForcibleBugMaker
40 1
芯动大师
|
2月前
|
存储 C++
C++的list-map链表与映射表
```markdown C++ 中的`list`和`map`提供链表和映射表功能。`list`是双向链表，支持头尾插入删除（`push_front/push_back/pop_front/pop_back`），迭代器遍历及任意位置插入删除。`map`是键值对集合，自动按键排序，支持直接通过键来添加、修改和删除元素。两者均能使用范围for循环遍历，`map`的`count`函数用于统计键值出现次数。 ```
芯动大师
26 1