往期内容回顾
一、String类型的自实现
1、string基本结构-- 构造，析构函数，成员变量
class my_string{ public: //列表的初始化，析构函数 my_string() :_str(nullptr) ,_size(0) ,_capacity(0) { cout<<"using Constructor: "<<endl; } void clean(){ delete _str; _size = 0; _capacity = 0; } ~my_string(){ clean(); _str = nullptr; cout<<"using Deonstructor: "<<endl; } private: char* _str; size_t _size; size_t _capacity; };
测试函数
void test1(){ my_string s1; }输出：
using Constructor:
using Deonstructor:
2、string的基本属性--> size, capacity, empty
size_t size()const{ return _size; } size_t capacity()const{ return _capacity; } bool empty(){ return bool(size() == 0); }测试函数：
void test2(){ my_string s1; cout<<s1.capacity()<<endl; cout<<s1.size()<<endl; cout<<s1.empty()<<endl; }输出描述：
using Constructor:
0
0
1
using Deonstructor:
3、内存管理函数：resize，reserve实现
void reserve(size_t n){ if(n > capacity()){ char* tmp = new char[n+1]; // memcpy(tmp,_str,size()); if(_str){ strcpy(tmp,_str); delete[] _str; } _str = tmp; _capacity = n; } } void resize (size_t n, char c = '\0'){ size_t sz = size(); if(n > size()){ if(n>capacity()){ reserve(n); } while (sz!= n) { _str[sz++] = c; } } _str[n] = '\0'; _size = n; }测试函数：
void test3(){ my_string s1; s1.reserve(4); cout<<s1.capacity()<<endl; s1.resize(10,'g'); Print_string(s1);输出描述：
using Constructor:
4
g g g g g g g g g g
using Deonstructor:
4、string类的增删查改
//增删查改 void push_back (char c){ if(_size == _capacity){ //增容 size_t new_capacity = (_capacity == 0)?2: 2*_capacity; reserve(new_capacity); } _str[_size] = c; ++_size; } my_string& insert (size_t pos, const char c){ assert(pos <= size()); if(_size == _capacity){ //增容 size_t new_capacity = (_capacity == 0)?2: 2*_capacity; reserve(new_capacity); } size_t end = size(); while (end >= pos) { _str[end+1] = _str[end]; if(end == 0){ break; } --end; }; ++_size; _str[pos] = c; _str[_size] = '\0'; return *this; }; my_string& insert(size_t pos, const char* str){ assert(pos <= size()); size_t len = strlen(str); size_t sz = len + size(); if(sz > capacity()){ reserve(sz); } size_t end = size(); while (end >= pos) { _str[end+len] = _str[end]; if(end == 0){ break; } --end; }; // strncpy() for(size_t i = 0;i< len;i++){ _str[pos+i] = str[i]; }; _size = sz; _str[_size] = '\0'; return *this; } // void insert(size_t pos, const my_string& str); my_string& append (const char* s){ size_t sz = strlen(s); size_t num = sz + size(); if(num > capacity()){ reserve(num); } strcat(_str,s); _size = num; return *this; } my_string& erase (size_t pos = 0, size_t len = npos){ assert(pos < size()); size_t sz = size(); if(pos + len >= sz){ _size = pos; } else{ size_t write = pos; size_t read = pos + len; while ( _str[read] != '\0') { _str[write++] = _str[read++]; } _size = sz-len; _str[_size] = '\0'; } return *this; } size_t find(char ch, size_t pos = 0){ assert(pos < size()); while (pos < size()) { if(_str[pos] == ch){ return pos; } ++pos; } return npos; }; size_t find(const char* str, size_t pos = 0){ assert(pos < size()); while (pos < size()) { if(_str[pos] == str[0]){ size_t len = strlen(str); size_t index; for(index = 1;index<len;index++) { if(str[index] != _str[pos+index]){ break; } } if(index == len){ return pos; } } ++pos; } return npos; }测试代码：
void test4(){ my_string s1; s1.push_back('a'); s1.push_back('b'); s1.push_back('c'); s1.append("def"); s1.insert(0,'x'); Print_string(s1); s1.erase(3,2); Print_string(s1); size_t ind = s1.find("xa"); cout<< "index = " << ind<<endl;输出描述：
using Constructor:
x a b c d e f
x a b e f
index = 0
using Deonstructor:
5、赋值运算符和拷贝构造
my_string(const my_string& s1) { if(this != &s1){ char* tmp = new char[s1._capacity+1]; memcpy(tmp,s1._str,s1._size); _str = tmp; _capacity = s1._capacity; _size = s1._size; } }; my_string& operator = (my_string s1){ ::swap(_str,s1._str); _size = s1._size; _capacity = s1._capacity; return *this; }测试函数：
void test5(){ my_string s1; s1.push_back('a'); s1.push_back('b'); s1.push_back('c'); my_string s2(s1); Print_string(s2); my_string s3; s3 = s2; Print_string(s3); }输出描述：
using Constructor:
a b c
using Constructor:
using Deonstructor:
a b c
using Deonstructor:
using Deonstructor:
using Deonstructor:
6、遍历运算符重载
char& operator[](size_t i){ assert(i<_size); return _str[i]; } const char& operator[](size_t i) const{ assert(i<_size); return _str[i]; }测试代码：
void test6(){ my_string s1; s1.append("abcdef"); for(size_t i = 0; i<s1.size();i++){ cout<< s1[i]<<" "; } cout<<endl;输出描述：
using Constructor:
a b c d e f
using Deonstructor:
二、Vector类型的自实现
1、Vector基本结构-- 构造，析构函数，成员变量
#include<iostream> #include<assert.h> using namespace std; template <typename T> class my_vector{ public: my_vector() :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr) { cout<<"Using Constructor!"<<endl; } ~my_vector() { cout<<"Using Destructor!"<<endl; delete[] _start; _start = nullptr; _finish = nullptr; _endofstorage = nullptr; } private: T* _start; T* _finish; T* _endofstorage; };测试函数：
void test1(){ my_vector<int> v; }输出描述：
Using Constructor!
Using Destructor!
2、Vector的基本属性--> size, capacity, empty
size_t size()const { return _finish - _start; } size_t capacity()const { return _endofstorage - _start; } bool empty(){ if(_start == _finish){ return true; } return false; }测试函数：
void test2(){ my_vector<int> v; v.push_back(1); cout<< v.capacity()<<endl; v.push_back(2); v.push_back(3); v.push_back(4); cout<< v.capacity()<<endl; if(v.empty()){ cout<< "Vector is not empty!"<<endl; } Print_vector(v); }输出描述：
2
4
Vector is not empty!
1 2 3 4
3、内存管理函数：resize，reserve实现
void reserve(size_t n){ size_t sz = size(); if(n > capacity()){ T* tmp = new T[n]; if(_start){ std::copy(_start,_finish,tmp); delete[] _start; } _start = tmp; _finish = _start +sz; _endofstorage = _start + n; } } void resize(size_t n, const T& val){ size_t sz = size(); if(n <= sz){ _finish = _start + n; } else{ if(n > capacity()){ reserve(n); } while (_finish != _endofstorage) { *_finish = val; ++_finish; } } }测试函数：
void test2(){ my_vector<int> v; v.push_back(1); v.reserve(10); cout<<"capacity is "<<v.capacity()<<endl; v.push_back(2); v.push_back(3); v.push_back(4); v.resize(12,5); Print_vector(v); }输出描述：
capacity is 10
1 2 3 4 5 5 5 5 5 5 5 5
4、string类的增删查改
void push_back(const T& x){ // if(_finish == _endofstorage){ // //增容 // size_t new_capacity = (capacity() == 0)? 2 : 2* capacity(); // reserve(new_capacity); // } // *_finish = x; // ++_finish; insert(_finish,x); } void pop_back(){ erase(_finish-1); } iterator insert (iterator position, const T& val){ assert(position <= _finish && _start <= position); if(_finish == _endofstorage){ size_t num = position - _start; size_t new_capacity = (capacity() == 0) ? 2 : 2*capacity(); reserve(new_capacity); position = _start + num; } for(T* end = _finish; end > position; --end){ *end = *(end-1); }; *position = val; ++_finish; return position; } iterator erase (iterator pos){ assert(pos < _finish && _start <= pos); if(_start != _finish){ T* _init = pos; for(T* _init = pos;_init < _finish-1;++_init){ *(_init) = *(_init + 1); } --_finish; } return pos; } iterator erase (iterator first, iterator last){ assert(first >= _start && last <= _finish && _start); size_t num = last - first; size_t res = _finish - last; T* end = last; T* begin = first; while (res--) { *begin = *end; ++end; ++begin; } _finish -= num; return first; }测试函数：
void test3(){ my_vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.insert(v.begin(),0); Print_vector(v); v.insert(v.end(),5); Print_vector(v); v.erase(v.begin()); Print_vector(v); v.erase(v.begin(),v.end()); Print_vector(v); }输出描述：
0 1 2 3 4
0 1 2 3 4 5
1 2 3 4 5
5、赋值运算符和拷贝构造
my_vector(const my_vector<T>& v){ if(this != &v){ size_t new_capacity = v.capacity(); T* tmp = new T[v.capacity()]; ::copy(v._start,v._finish,tmp); _start = tmp; _finish = _start + v.size(); _endofstorage = _start+new_capacity; }; } my_vector<T>& operator = (my_vector<T> v){ swap(v); return *this; }测试函数：
void test4(){ my_vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); my_vector<int> v2; v2 = v; Print_vector(v2); }输出描述：
1 2 3 4
6、遍历运算符重载
typedef T* iterator; typedef T* const_iterator; iterator begin(){ return _start; } iterator end(){ return _finish; } const_iterator begin()const{ return _start; } const_iterator end()const{ return _finish; } template <typename T> void Print_vector(const my_vector<T> & v){ typename my_vector<T>::const_iterator it = v.begin(); while (it != v.end()) { cout<< *it <<" "; ++it; } cout<< endl; }
三、List类型的自实现
1、List基本结构-- 构造，析构函数，成员变量
#include<iostream> #include<assert.h> using namespace std; template<typename T> struct ListNode { ListNode* prev; ListNode* next; T data; ListNode(const T& val = T()) :prev(nullptr) ,next(nullptr) ,data(val) {} }; template<typename T> class mylist { typedef ListNode<T> Node; public: mylist() :head(new ListNode<T>()) //自动调用构造函数 { cout<<"Using Constructor!"<<endl; head->next = head; head->prev = head; } void clear(){ Node* cur = head->next; while (cur != head) { Node* Next = cur->next; delete cur; cur = Next; } head->prev = head; head->next = head; } ~mylist(){ cout<<"Using Destructor!"<<endl; clear(); delete head; head = nullptr; } private: Node* head; };测试函数：
void test1(){ mylist<string> l1; cout<<"size = "<<l1.size()<<endl; if(l1.empty()){ cout<<"List l1 is empty!"<<endl; } }输出描述：
Using Constructor!
Using Destructor!
2、List的基本属性--> size, empty
size_t size(){ size_t num = 0; Node* cur = head->next; while (cur != head) { ++num; cur = cur -> next; } return num; } bool empty(){ return(head == head->next &&head == head->prev); }测试函数：
void test1(){ mylist<string> l1; cout<<"size = "<<l1.size()<<endl; if(l1.empty()){ cout<<"List l1 is empty!"<<endl; } }输出描述：
Using Constructor!
size = 0
List l1 is empty!
Using Destructor!
3、List的专属迭代器实现
template<class T, class Ref, class Ptr> struct list_iterator { typedef ListNode<T> Node; Node* _node; typedef list_iterator<T,Ref,Ptr> Self; list_iterator(Node* node = nullptr) :_node(node) {} Ref operator *() { return _node->data; } Ptr operator->() { return &(_node->data); } Self& operator++(){ _node = _node->next; return *this; } Self operator++(int){ list_iterator tmp = *this; ++(*this); return tmp; } Self& operator--(){ _node = _node ->prev; return *this; } Self operator--(int){ list_iterator tmp = _node; --(*this); return tmp; } bool operator ==(const Self& it){ return(_node == it._node); } bool operator !=(const Self& it){ return !(_node == it._node); } } 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; }测试函数：
template<typename T> void Print_List(const mylist<T>& l1){ typename mylist<T>::const_iterator it = l1.begin(); while (it != l1.end()) { cout<< *it << " "; ++it; } cout<<endl;
4、List类的增删查改, 拼接
T& front(){ return (head->next)->data; } T& back(){ return (head->prev)->data; } void push_front(const T& val){ Node* newnode = new Node(val); Node* cur = head->next; head->next = newnode; newnode->prev = head; cur->prev = newnode; newnode->next = cur; } void push_back(const T& val){ Node* newnode = new Node(val); Node* last = head->prev; head->prev = newnode; newnode->next = head; last->next = newnode; newnode->prev = last; } iterator insert(iterator position, const T& val) { Node* cur = position._node; // 要插入的位置 Node* newnode = new Node(val); Node* Prev = cur->prev; newnode->next = cur; newnode->prev = Prev; Prev->next = newnode; cur->prev = newnode; return iterator(newnode); // 返回新节点的迭代器 } iterator erase(iterator position) { assert(position != end()); Node* cur = position._node; Node* Prev = cur->prev; Node* Next = cur->next; Prev->next = Next; Next->prev = Prev; delete cur; return iterator(Next); // 返回删除节点之后的位置 } void splice (iterator position, mylist& x){ if(x.empty()) return; Node* cur = position._node; Node* Prev = cur->prev; Prev->next = x.head->next; (x.head->next)->prev = Prev; cur->prev = x.head->next; (x.head->prev)->next = cur; x.head->next = x.head; x.head->prev = x.head; }
5、赋值运算符和拷贝构造
mylist(const mylist<T>& l1){ head = new Node(); head->_next = head; head->_prev = head; const_iterator start = l1.begin(); while (start!= l1.end()) { push_back(start._node->_data); ++start; } }
四、总结
string：本质是一个特殊的 vector<char>，底层是动态数组，提供了方便的字符串处理接口，解决了 C 风格字符串不安全、不易管理的问题。
vector：底层是动态数组，支持高效随机访问和良好的缓存局部性，是最常用的顺序容器，但扩容和中间插入删除的代价较大。
list：底层是双向链表，插入删除高效且迭代器稳定，但不支持随机访问，遍历性能不如 vector。
👉 实现的重要性：
自己实现这些容器，可以深入理解 内存管理、指针操作、迭代器机制 等 C++ 核心知识，同时体会 STL 设计背后的权衡（性能、内存、灵活性），这是学习现代 C++ 的重要一环。