摘要：，，C++中的list和string是常用的数据结构，list是一种动态数组，可以存储不同类型的元素，支持双向链表操作，具有插入、删除、遍历等功能。而string则是一种用于存储字符序列的类，支持字符串的创建、赋值、拼接、查找、替换等操作。两者都是C++中重要的数据结构，广泛应用于各种编程场景。
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类
template class 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 完整实现
#include using 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类 template class 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 #include 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 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 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总结
这次的模拟实现就到这里啦
这些只是建议的模拟，目的是让大家更充分的了解容器的使用
如果对于里面一些知识不了解的话，可以看看前面的博客哟
大家继续加油吧！
文章版权声明：除非注明，否则均为VPS857原创文章，转载或复制请以超链接形式并注明出处。
还没有评论，来说两句吧...