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<class T>struct ListNode{ListNode(const T& val = T());ListNode<T>* _pPre;//前驱结点指针ListNode<T>* _pNext;//后继节点指针T _val;};
List的迭代器类
template<class T, class Ref, class Ptr>class ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> 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类
template<class T>
class list{typedef ListNode<T> Node;typedef Node* PNode;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T&> const_iterator;public:// List的构造list();list(int n, const T& value = T());template <class Iterator>list(Iterator first, Iterator last);list(const list<T>& l);list<T>& operator=(const list<T> 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<T>& l);private:void CreateHead();PNode _pHead;};
list.h 完整实现
#include<iostream>
using namespace std;namespace bite
{// List的节点类template<class T>struct ListNode{ListNode(const T& val = T());ListNode<T>* _pPre;ListNode<T>* _pNext;T _val;};//List的迭代器类template<class T, class Ref, class Ptr>class ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> 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类template<class T>
class list{typedef ListNode<T> Node;typedef Node* PNode;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T&> const_iterator;public:// List的构造list();list(int n, const T& value = T());template <class Iterator>list(Iterator first, Iterator last);list(const list<T>& l);list<T>& operator=(const list<T> 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<T>& l);private:void CreateHead();PNode _pHead;};
};
list.cpp
List的节点类
template<class T>struct ListNode{ListNode(const T& val = T()): _pPre(nullptr),_pNext(nullptr), _val(val){}ListNode<T>* _pPre;ListNode<T>* _pNext;T _val;};
List的迭代器类
template<class T, class Ref, class Ptr>class ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> 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 T>class list{typedef ListNode<T> Node;typedef Node* PNode;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T&> const_iterator;public:// List的构造list(){CreateHead();}list(int n, const T& value = T()){CreateHead();for (int i = 0; i < n; ++i)push_back(value);}template <class Iterator>list(Iterator first, Iterator last){CreateHead();while (first != last){push_back(*first);++first;}}list(const list<T>& l){CreateHead();// 用l中的元素构造临时的temp,然后与当前对象交换list<T> temp(l.cbegin(), l.cend());this->swap(temp);}list<T>& operator=(const list<T> 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<T>& 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<class T>struct ListNode{ListNode(const T& val = T()): _pPre(nullptr), _pNext(nullptr), _val(val){}ListNode<T>* _pPre;ListNode<T>* _pNext;T _val;};//List的迭代器类template<class T, class Ref, class Ptr>class ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> 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 T>class list{typedef ListNode<T> Node;typedef Node* PNode;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T&> const_iterator;public:// List的构造list(){CreateHead();}list(int n, const T& value = T()){CreateHead();for (int i = 0; i < n; ++i)push_back(value);}template <class Iterator>list(Iterator first, Iterator last){CreateHead();while (first != last){push_back(*first);++first;}}list(const list<T>& l){CreateHead();// 用l中的元素构造临时的temp,然后与当前对象交换list<T> temp(l.cbegin(), l.cend());this->swap(temp);}list<T>& operator=(const list<T> 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<T>& 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<assert.h>
#include<iostream>using 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& operator<<(ostream& out, const string& s);
}
string.cpp
#include"string.h"namespace bit{string::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 <= _size);return _str[pos];}char& string::operator[](size_t pos){assert(pos <= _size);return _str[pos];}void string::reserve(size_t n){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);if (_size == _capacity){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 <= _size);size_t len = strlen(str);if (_size + len > _capacity){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);if (len == npos || pos + len >= _size){_str[pos] = '\0';_size = pos;}else{strcpy(_str + pos, _str + pos + len);_size -= len;}}void string::swap(string& s){std::swap(_str, s._str);std::swap(_size, s._size);std::swap(_capacity, s._capacity);}size_t string::find(char ch, size_t pos){for (size_t i = pos; i < _size; i++){if (_str[i] == ch){return i;}}return npos;}size_t string::find(const char* str, size_t pos){const char* ptr = strstr(_str + pos, str);if (ptr == nullptr){return npos;}else{return ptr - _str;}}string string::substr(size_t pos, size_t len){assert(pos < _size);size_t end = pos + len;if (len == npos || pos + len >= _size){end = _size;}string str;str.reserve(end - pos);for (size_t i = pos; i < end; i++){str += _str[i];}return str;}void string::clear(){_size = 0;_str[0] = '\0';}ostream& operator<<(ostream& out, const string& s){for (auto ch : s){out << ch;}return out;}istream& operator>>(istream& in, string& s){s.clear();char buff[128];char ch = in.get();int i = 0;while (ch != ' ' && ch != '\n'){buff[i++] = ch;if (i == 127){buff[i] = '\0';s += buff;i = 0;}ch = in.get();}if (i > 0){buff[i] = '\0';s += buff;}return in;}};
总结
这次的模拟实现就到这里啦
这些只是建议的模拟,目的是让大家更充分的了解容器的使用
如果对于里面一些知识不了解的话,可以看看前面的博客哟
大家继续加油吧!