C++——list和string

list与string

• 前言
• 一、list
• • list.h
  • • List的节点类
    • List的迭代器类
    • list类
    • list.h 完整实现
    • list.cpp
    • • List的节点类
      • List的迭代器类
      • list类
      • list.cpp 完整实现
      • 二、string
      • • string.h
        • string.cpp
        • 总结

          ---

          前言

          C++容器的学习开始啦！

          大家先来学习list！

          紧接着string和vector也会一一呈现！

          大家继续加油吧！

          ---

          一、list

          大家先来认识一下什么是list容器？

          注：列表是序列容器，允许在序列中的任何位置进行恒定时间的插入和擦除操作，以及双向迭代。

          列表容器被实现为双链表；双链接列表可以将它们所包含的每个元素存储在不同且不相关的存储位置。排序是通过与每个元素的关联在内部保持的，其中链接到它前面的元素，链接到它后面的元素。

          对啦，其实list在根本上就是利用链表所实现一个可以装载数据的容器；

          认识之后就是学习使用啦，我们接下来简易模拟实现以下list吧！

          list.h

          List的节点类

          template    struct ListNode    {        ListNode(const T& val = T());        ListNode* _pPre;//前驱结点指针        ListNode* _pNext;//后继节点指针        T _val;    };

          List的迭代器类

              template    class ListIterator    {        typedef ListNode* PNode;        typedef ListIterator Self;    public:        ListIterator(PNode pNode = nullptr);        ListIterator(const Self& l);        T& operator*();        T* operator->();        Self& operator++();        Self operator++(int);        Self& operator--();        Self& operator--(int);        bool operator!=(const Self& l);        bool operator==(const Self& l);    private:        PNode _pNode;    };

          list类

          templateclass list    {        typedef ListNode Node;        typedef Node* PNode;    public:        typedef ListIterator iterator;        typedef ListIterator const_iterator;    public:                // List的构造        list();        list(int n, const T& value = T());        template         list(Iterator first, Iterator last);        list(const list& l);        list& operator=(const list l);        ~list();        // List 迭代器        iterator begin();        iterator end();        const_iterator begin();        const_iterator end();        // List 容器长度        size_t size()const;        // List 判空        bool empty()const;        // 列表访问        T& front();// 访问头结点        const T& front()const;        T& back();// 访问尾结点        const T& back()const;        // 列表修改        void push_back(const T& val) { insert(end(), val); } // 尾插        void pop_back() { erase(--end()); } // 尾删        void push_front(const T& val) { insert(begin(), val); } // 头插        void pop_front() { erase(begin()); } // 头删        // 在pos位置前插入值为val的节点        iterator insert(iterator pos, const T& val);        // 删除pos位置的节点，返回该节点的下一个位置        iterator erase(iterator pos);        void clear();        void swap(list& l);    private:        void CreateHead();        PNode _pHead;    };

          list.h 完整实现

          #includeusing namespace std;namespace bite{    // List的节点类    template    struct ListNode    {        ListNode(const T& val = T());        ListNode* _pPre;        ListNode* _pNext;        T _val;    };    //List的迭代器类    template    class ListIterator    {        typedef ListNode* PNode;        typedef ListIterator Self;    public:        ListIterator(PNode pNode = nullptr);        ListIterator(const Self& l);        T& operator*();        T* operator->();        Self& operator++();        Self operator++(int);        Self& operator--();        Self& operator--(int);        bool operator!=(const Self& l);        bool operator==(const Self& l);    private:        PNode _pNode;    };    //list类    templateclass list    {        typedef ListNode Node;        typedef Node* PNode;    public:        typedef ListIterator iterator;        typedef ListIterator const_iterator;    public:                // List的构造        list();        list(int n, const T& value = T());        template         list(Iterator first, Iterator last);        list(const list& l);        list& operator=(const list l);        ~list();        // List 迭代器        iterator begin();        iterator end();        const_iterator begin();        const_iterator end();        // List 容器长度        size_t size()const;        // List 判空        bool empty()const;        // 列表访问        T& front();// 访问头结点        const T& front()const;        T& back();// 访问尾结点        const T& back()const;        // 列表修改        void push_back(const T& val) { insert(end(), val); } // 尾插        void pop_back() { erase(--end()); } // 尾删        void push_front(const T& val) { insert(begin(), val); } // 头插        void pop_front() { erase(begin()); } // 头删        // 在pos位置前插入值为val的节点        iterator insert(iterator pos, const T& val);        // 删除pos位置的节点，返回该节点的下一个位置        iterator erase(iterator pos);        void clear();        void swap(list& l);    private:        void CreateHead();        PNode _pHead;    };};

          list.cpp

          List的节点类

          template  struct ListNode  {    ListNode(const T& val = T())    : _pPre(nullptr),      _pNext(nullptr),       _val(val)    {}    ListNode* _pPre;    ListNode* _pNext;    T _val;  };

          List的迭代器类

          template  class ListIterator  {    typedef ListNode* PNode;    typedef ListIterator Self;  public:    ListIterator(PNode pNode = nullptr):_pNode(pNode)    {}    ListIterator(const Self& l): _pNode(l._pNode)    {}        T& operator*()    {      return _pNode->_val;    }        T* operator->()    {      return &*this;    }        Self& operator++()    {      _pNode = _pNode->_pNext;      return *this;    }        Self operator++(int)    {      Self temp(*this);      _pNode = _pNode->_pNext;      return temp;    }        Self& operator--()    {      _pNode = _pNode->_pPre;      return *this;    }        Self& operator--(int)    {      Self temp(*this);      _pNode = _pNode->_pPre;      return temp;    }        bool operator!=(const Self& l)    {      return _pNode != l._pNode;    }        bool operator==(const Self& l)    {      return !(*this!=l);    }      private:    PNode _pNode;  };

          list类

          template  class list  {    typedef ListNode Node;    typedef Node* PNode;  public:    typedef ListIterator iterator;    typedef ListIterator const_iterator;  public:        // List的构造    list()    {      CreateHead();    }    list(int n, const T& value = T())    {      CreateHead();      for (int i = 0; i swap(temp);    }    list& operator=(const list l)    {      this->swap(l);      return *this;    }    ~list()    {      clear();      delete _pHead;      _pHead = nullptr;    }        // 列表迭代器    iterator begin()    {      return iterator(_pHead->_pNext);    }    iterator end()    {      return iterator(_pHead);    }    const_iterator begin()const    {      return const_iterator(_pHead->_pNext);    }    const_iterator end()const    {      return const_iterator(_pHead);    }        // 列表大小    size_t size()const    {      size_t size = 0;      ListNode *p = _pHead->_pNext;      while(p != _pHead)      {        size++;        p = p->_pNext;      }      return size;           }    // 判空    bool empty()const    {      return size() == 0;    }       // 列表访问    T& front()// 头结点访问    {      assert(!empty());      return _pHead->_pNext->_val;    }        const T& front()const    {      assert(!empty());      return _pHead->_pNext->_val;    }        T& back()//尾结点访问    {      assert(!empty());      return _pHead->_pPre->_val;    }        const T& back()const    {      assert(!empty());      return _pHead->_pPre->_val;    }       //列表修改    void push_back(const T& val)//尾插    {      insert(end(), val);    }    void pop_back()//尾删    {      erase(--end());    }    void push_front(const T& val)//头插    {      insert(begin(), val);    }    void pop_front()//头删    {      erase(begin());    }    // 在pos位置前插入值为val的节点    iterator insert(iterator pos, const T& val)    {      PNode pNewNode = new Node(val);      PNode pCur = pos._pNode;      // 先将新节点插入      pNewNode->_pPre = pCur->_pPre;      pNewNode->_pNext = pCur;      pNewNode->_pPre->_pNext = pNewNode;      pCur->_pPre = pNewNode;      return iterator(pNewNode);    }    // 删除pos位置的节点，返回该节点的下一个位置    iterator erase(iterator pos)    {      // 找到待删除的节点      PNode pDel = pos._pNode;      PNode pRet = pDel->_pNext;      // 将该节点从链表中拆下来并删除      pDel->_pPre->_pNext = pDel->_pNext;      pDel->_pNext->_pPre = pDel->_pPre;      delete pDel;      return iterator(pRet);    }    //清除容器中的数据    void clear()    {      iterator p = begin();      while(p != end())      {        p = erase(p);      }                      _pHead->_pPrev = _pHead;//头结点前驱指向自己           _pHead->_pNext = _pHead;//头结点后继指向自己    }    //交换容器    void swap(List& l)    {      pNode tmp = _pHead;      _pHead = l._pHead;      l._pHead = tmp;    }  private:    void CreateHead()//创建头节点    {      _pHead = new Node;      _pHead->_pPre = _pHead;      _pHead->_pNext = _pHead;    }    PNode _pHead;  };

          list.cpp 完整实现

          namespace bite{  // List的节点类  template  struct ListNode  {    ListNode(const T& val = T()): _pPre(nullptr), _pNext(nullptr), _val(val)    {}    ListNode* _pPre;    ListNode* _pNext;    T _val;  };  //List的迭代器类  template  class ListIterator  {    typedef ListNode* PNode;    typedef ListIterator Self;  public:    ListIterator(PNode pNode = nullptr):_pNode(pNode)    {}    ListIterator(const Self& l): _pNode(l._pNode)    {}    T& operator*()    {      return _pNode->_val;    }    T* operator->()    {      return &*this;    }    Self& operator++()    {      _pNode = _pNode->_pNext;      return *this;    }    Self operator++(int)    {      Self temp(*this);      _pNode = _pNode->_pNext;      return temp;    }    Self& operator--()    {      _pNode = _pNode->_pPre;      return *this;    }    Self& operator--(int)    {      Self temp(*this);      _pNode = _pNode->_pPre;      return temp;    }    bool operator!=(const Self& l)    {      return _pNode != l._pNode;    }    bool operator==(const Self& l)    {      return !(*this!=l);    }  private:    PNode _pNode;  };  //list类 template  class list  {    typedef ListNode Node;    typedef Node* PNode;  public:    typedef ListIterator iterator;    typedef ListIterator const_iterator;  public:        // List的构造    list()    {      CreateHead();    }    list(int n, const T& value = T())    {      CreateHead();      for (int i = 0; i swap(temp);    }    list& operator=(const list l)    {      this->swap(l);      return *this;    }    ~list()    {      clear();      delete _pHead;      _pHead = nullptr;    }        // 列表迭代器    iterator begin()    {      return iterator(_pHead->_pNext);    }    iterator end()    {      return iterator(_pHead);    }    const_iterator begin()const    {      return const_iterator(_pHead->_pNext);    }    const_iterator end()const    {      return const_iterator(_pHead);    }        // 列表大小    size_t size()const    {      size_t size = 0;      ListNode *p = _pHead->_pNext;      while(p != _pHead)      {        size++;        p = p->_pNext;      }      return size;           }    // 判空    bool empty()const    {      return size() == 0;    }       // 列表访问    T& front()// 头结点访问    {      assert(!empty());      return _pHead->_pNext->_val;    }        const T& front()const    {      assert(!empty());      return _pHead->_pNext->_val;    }        T& back()//尾结点访问    {      assert(!empty());      return _pHead->_pPre->_val;    }        const T& back()const    {      assert(!empty());      return _pHead->_pPre->_val;    }       //列表修改    void push_back(const T& val)//尾插    {      insert(end(), val);    }    void pop_back()//尾删    {      erase(--end());    }    void push_front(const T& val)//头插    {      insert(begin(), val);    }    void pop_front()//头删    {      erase(begin());    }    // 在pos位置前插入值为val的节点    iterator insert(iterator pos, const T& val)    {      PNode pNewNode = new Node(val);      PNode pCur = pos._pNode;      // 先将新节点插入      pNewNode->_pPre = pCur->_pPre;      pNewNode->_pNext = pCur;      pNewNode->_pPre->_pNext = pNewNode;      pCur->_pPre = pNewNode;      return iterator(pNewNode);    }    // 删除pos位置的节点，返回该节点的下一个位置    iterator erase(iterator pos)    {      // 找到待删除的节点      PNode pDel = pos._pNode;      PNode pRet = pDel->_pNext;      // 将该节点从链表中拆下来并删除      pDel->_pPre->_pNext = pDel->_pNext;      pDel->_pNext->_pPre = pDel->_pPre;      delete pDel;      return iterator(pRet);    }    //清除容器中的数据    void clear()    {      iterator p = begin();      while(p != end())      {        p = erase(p);      }                      _pHead->_pPrev = _pHead;//头结点前驱指向自己           _pHead->_pNext = _pHead;//头结点后继指向自己    }    //交换容器    void swap(List& l)    {      pNode tmp = _pHead;      _pHead = l._pHead;      l._pHead = tmp;    }  private:    void CreateHead()//创建头节点    {      _pHead = new Node;      _pHead->_pPre = _pHead;      _pHead->_pNext = _pHead;    }    PNode _pHead;  };}

          二、string

          接下来让我们学习下一个容器string吧！

          注：字符串是表示字符序列的对象。

          接下来就是string的简易模拟啦

          string.h

          #pragma once#include#includeusing namespace std;namespace bit{class string{public:typedef char* iterator;typedef const char* const_iterator;        //string迭代器iterator begin(){return _str;}iterator end(){return _str + _size;}const_iterator begin() const{return _str;}const_iterator end() const{return _str + _size;}        //获取等效的C字符串const char* c_str() const{return _str;}        //获取字符串长度size_t size() const{return _size;}        //string的构造string(const char* str = "");string(const string& s);string& operator=(string s);~string();const char& operator[](size_t pos) const; char& operator[](size_t pos); //[]的重载void reserve(size_t n); //逆置void push_back(char ch); //尾插void append(const char* str); //追加string& operator+=(char ch);string& operator+=(const char* str);void insert(size_t pos, char ch); //插入void insert(size_t pos, const char* str);void erase(size_t pos, size_t len = npos); //删除void swap(string& s); //交换size_t find(char ch, size_t pos = 0); //查找size_t find(const char* str, size_t pos = 0);string substr(size_t pos = 0, size_t len = npos);void clear();private:size_t _capacity = 0;size_t _size = 0;char* _str = nullptr;const static size_t npos = -1;};istream& operator>>(istream& in, string& s);ostream& operatorstring::string(const char* str){_size = strlen(str);_capacity = _size;_str = new char[_capacity + 1];strcpy(_str, str);}string::string(const string& s){string tmp(s._str);swap(tmp);}string& string::operator=(string s){swap(s);return *this;}string::~string(){delete[] _str;_str = nullptr;_size = 0;_capacity = 0;}const char& string::operator[](size_t pos) const{assert(pos assert(pos if (n  _capacity){char* tmp = new char[n + 1];strcpy(tmp, _str);delete[] _str;_str = tmp;_capacity = n;}}void string::push_back(char ch){if (_size == _capacity){size_t newCapacity = _capacity == 0 ? 4 : _capacity * 2;reserve(newCapacity);}_str[_size] = ch;_size++;_str[_size] = '\0';}void string::append(const char* str){size_t len = strlen(str);if (_size + len  _capacity){reserve(_size + len);}strcpy(_str + _size, str);_size += len;}string& string::operator+=(char ch){push_back(ch);return *this;}string& string::operator+=(const char* str){append(str);return *this;}void string::insert(size_t pos, char ch){assert(pos size_t newCapacity = _capacity == 0 ? 4 : _capacity * 2;reserve(newCapacity);}size_t end = _size + 1;while (end  pos){_str[end] = _str[end - 1];--end;}_str[pos] = ch;_size++;}void string::insert(size_t pos, const char* str){assert(pos reserve(_size + len);}int end = _size;while (end = (int)pos){_str[end + len] = _str[end];--end;}strncpy(_str + pos, str, len);_size += len;}void string::erase(size_t pos, size_t len){assert(pos = _size){end = _size;}string str;str.reserve(end - pos);for (size_t i = pos; i  
          总结
           
          这次的模拟实现就到这里啦
          这些只是建议的模拟，目的是让大家更充分的了解容器的使用
          如果对于里面一些知识不了解的话，可以看看前面的博客哟
          大家继续加油吧！