C++初阶(十四)list

简介: C++初阶(十四)list

一、 list的介绍


  1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
  2. list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。
  3. list与forward_list非常相似:最主要的不同在于forward_list是单链表,只能朝前迭代,已让其更简单高效。
  4. 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。
  5. 与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,比如:要访问list的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销;list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

d2ac71249b5b498bb26dc0c64ce3a2ee.png



二、list的模拟实现


1、list的节点

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


2、list 的迭代器

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)
    {}
    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& s)
    {
      return _node != s._node;
    }
    bool operator==(const self& s)
    {
      return _node == s._node;
    }
  };


3、list

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;
    iterator begin()
    {
      return _head->_next;
    }
    iterator end()
    {
      return _head;
    }
    const_iterator begin() const
    {
      return _head->_next;
    }
    const_iterator end() const
    {
      return _head;
    }
    void empty_init()
    {
      _head = new Node;
      _head->_next = _head;
      _head->_prev = _head;
      _size = 0;
    }
    list()
    {
      empty_init();
    }
    list(list<T>& lt)
    {
      empty_init();
      for (auto e : lt)
      {
        push_back(e);
      }
    }
    list<T>& operator=(list<T> lt)
    {
      swap(lt);
      return *this;
    }
    void swap(list<T> lt)
    {
      std::swap(_size, lt._size);
      std::swap(_head, lt._head);
    }
    iterator insert(iterator pos, const T& x)
    {
      Node* cur = pos._node;
      Node* newnode = new Node(x);
      Node* prev = cur->_prev;
      prev->_next = newnode;
      newnode->_prev = prev;
      newnode->_next = cur;
      cur->_prev = newnode;
      ++_size;
      return iterator(newnode);
    }
    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;
    }
    size_t size()
    {
      return _size;
    }
    void clear()
    {
      iterator it = begin();
      while (it != end)
      {
        it = erase(it);
      }
    }
    void push_back(const T& x)
    {
      insert(end(), x);
    }
    void push_front(const T& x)
    {
      insert(begin(), x);
    }
    void push_back()
    {
      erase(end());
    }
    void pop_back()
    {
      erase(begin());
    }
  private:
    Node* _head;
    size_t _size;
  };


4、打印

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;
  }
  void test_list()
  {
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(5);
    print_container(lt);
    list<string> lt1;
    lt1.push_back("1111111111111");
    lt1.push_back("1111111111111");
    lt1.push_back("1111111111111");
    lt1.push_back("1111111111111");
    lt1.push_back("1111111111111");
    print_container(lt1);
    vector<string> v;
    v.push_back("222222222222222222222");
    v.push_back("222222222222222222222");
    v.push_back("222222222222222222222");
    v.push_back("222222222222222222222");
    print_container(v);
  }
}
int main()
{
  bit::test_list();
  return 0;
}


5、完整代码

#include<iostream>
#include<string>
#include<vector>
using namespace std;
namespace bit
{
  template<class T>
  struct list_node
  {
    T _data;
    list_node<T>* _prev;
    list_node<T>* _next;
    list_node(const T& x = T())
      :_data(x)
      , _next(nullptr)
      , _prev(nullptr)
    {}
  };
  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)
    {}
    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& s)
    {
      return _node != s._node;
    }
    bool operator==(const self& s)
    {
      return _node == s._node;
    }
  };
  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;
    iterator begin()
    {
      return _head->_next;
    }
    iterator end()
    {
      return _head;
    }
    const_iterator begin() const
    {
      return _head->_next;
    }
    const_iterator end() const
    {
      return _head;
    }
    void empty_init()
    {
      _head = new Node;
      _head->_next = _head;
      _head->_prev = _head;
      _size = 0;
    }
    list()
    {
      empty_init();
    }
    list(list<T>& lt)
    {
      empty_init();
      for (auto e : lt)
      {
        push_back(e);
      }
    }
    list<T>& operator=(list<T> lt)
    {
      swap(lt);
      return *this;
    }
    void swap(list<T> lt)
    {
      std::swap(_size, lt._size);
      std::swap(_head, lt._head);
    }
    iterator insert(iterator pos, const T& x)
    {
      Node* cur = pos._node;
      Node* newnode = new Node(x);
      Node* prev = cur->_prev;
      prev->_next = newnode;
      newnode->_prev = prev;
      newnode->_next = cur;
      cur->_prev = newnode;
      ++_size;
      return iterator(newnode);
    }
    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;
    }
    size_t size()
    {
      return _size;
    }
    void clear()
    {
      iterator it = begin();
      while (it != end)
      {
        it = erase(it);
      }
    }
    void push_back(const T& x)
    {
      insert(end(), x);
    }
    void push_front(const T& x)
    {
      insert(begin(), x);
    }
    void push_back()
    {
      erase(end());
    }
    void pop_back()
    {
      erase(begin());
    }
  private:
    Node* _head;
    size_t _size;
  };
  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;
  }
  void test_list()
  {
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(5);
    print_container(lt);
    list<string> lt1;
    lt1.push_back("1111111111111");
    lt1.push_back("1111111111111");
    lt1.push_back("1111111111111");
    lt1.push_back("1111111111111");
    lt1.push_back("1111111111111");
    print_container(lt1);
    vector<string> v;
    v.push_back("222222222222222222222");
    v.push_back("222222222222222222222");
    v.push_back("222222222222222222222");
    v.push_back("222222222222222222222");
    print_container(v);
  }
}
int main()
{
  bit::test_list();
  return 0;
}


83197b8dd2434ad9ab964c686eb478f7.png

目录
相关文章
|
1月前
|
存储 搜索推荐 C++
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器2
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器
48 2
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器2
|
21天前
|
存储 算法 C++
【C++打怪之路Lv10】-- list
【C++打怪之路Lv10】-- list
14 1
|
1月前
|
存储 C++ 容器
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器1
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器
51 5
|
1月前
|
存储 编译器 C++
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
49 2
|
1月前
|
C++
【C++】C++ STL 探索:List使用与背后底层逻辑(三)
【C++】C++ STL 探索:List使用与背后底层逻辑
|
1月前
|
C++
【C++】C++ STL 探索:List使用与背后底层逻辑(二)
【C++】C++ STL 探索:List使用与背后底层逻辑
|
1月前
|
存储 编译器 C++
【C++】C++ STL 探索:List使用与背后底层逻辑(一)
【C++】C++ STL 探索:List使用与背后底层逻辑
|
1月前
|
存储 缓存 C++
C++番外篇——list与vector的比较
C++番外篇——list与vector的比较
21 0
|
1月前
|
C++
C++番外篇——list的实现
C++番外篇——list的实现
19 0
|
1月前
|
存储 C++ 容器
C++入门9——list的使用
C++入门9——list的使用
18 0