【C++】几个基本容器的模拟实现（string,vector,list,stack,queue,priority

一.string

二.vector

三.list

四.stack

五.queue

六.priority_queue

一.string

#pragma oncenamespace hebre
{class string{public:typedef char* iterator;typedef const char* const_iterator;//Member functionsstring():_str(new char[1]{'\0'}),_size(0),_capacity(0){}string(const string& str){_size = str._size;_capacity = str._capacity;_str = new char[_size + 1];strcpy(_str, str._str);}string(const string& str, size_t pos, size_t len = npos){if (len > _size - pos){len = _size - pos;}_str = new char[len + 1];_capacity = _size = len;size_t i = 0;size_t n = len;while (n--){_str[i] = str._str[pos];i++;pos++;}_str[len] = '\0';}string(const char* s){_size = strlen(s);_capacity = _size;_str = new char[_size + 1];strcpy(_str, s);}string(const char* s, size_t n){_size = n;_capacity = n;_str = new char[n + 1];size_t i = 0;while (i < n){_str[i] = s[i];i++;}_str[_size] = '\0';}string(size_t n, char c){_size = n;_capacity = n;_str = new char[n + 1];size_t i = 0;while (i < n){_str[i] = c;}_str[_size] = '\0';}template<class InputIterator>string(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}~string(){delete[] _str;_str = nullptr;_size = 0;_capacity = 0;}string& operator= (const char* s){string tmp(s);swap(tmp);return *this;}string& operator=(string s){swap(s);return *this;}//Iteratorsiterator begin(){return _str;}const_iterator begin() const{return _str;}iterator end(){return _str + _size;}const_iterator end() const{return _str + _size;}//Capacitysize_t size() const{return _size;}void resize(size_t n, char c = '\0'){if (n <= _size){_str[n - 1] = '\0';_size = n;}else{if (n > _capacity){reserve(n);}for (size_t i = _size; i < n; i++){_str[i] = '\0';_size = n;}}}size_t capacity() const{return _capacity;}void reserve(size_t n = 0){if (n > _capacity){char* newstr = new char[n + 1];// 避免浅拷贝，允许自定义类型的使用// 联系string(InputIterator first, InputIterator last)for (int i = 0; i < _size; i++){newstr[i] = _str[i];}delete[] _str;_str = newstr;_capacity = n;}}void clear(){_str[0] = '\0';_size = 0;}bool empty() const{return _size == 0;}//Element accesschar& operator[] (size_t pos){assert(pos <= _size);return _str[pos];}const char& operator[] (size_t pos) const{assert(pos <= _size);return _str[pos];}char& at(size_t pos){assert(pos <= _size);return _str[pos];}const char& at(size_t pos) const{assert(pos <= _size);return _str[pos];}char& back(){return _str[_size - 1];}const char& back() const{return _str[_size - 1];}char& front(){return _str[0];}const char& front() const{return _str[0];}//Modifiers:string& operator+= (char c){push_back(c);return *this;}string& operator+= (const char* s){insert(_size, s);return *this;}string& append(const char* s){insert(_size, s);return *this;}void push_back(char c){insert(_size, 1, c);}string& assign(const char* s){clear();insert(0, s);return *this;}string& insert(size_t pos, size_t n, char c){assert(pos <= _size);if (_size == _capacity){size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2;reserve(newcapacity);}size_t end = _size + n;while (end >= pos + n){_str[end] = _str[end - n];end--;}for (int i = 0; i < n; i++){_str[pos + i] = c;}_size++;return *this;}string& insert(size_t pos, const char* s){assert(pos <= _size);size_t len = strlen(s);size_t newcapacity = len+_size;if (newcapacity > _capacity){reserve(newcapacity);}size_t end = _size + len;while (end >= pos+len){_str[end] = _str[end - len];end--;}for (int i = 0; i < len; i++){_str[pos+i] = s[i];}_size += len;return *this;}string& erase(size_t pos = 0, size_t len = npos){if (len > _size - pos){len = _size - pos;}size_t end = pos + len;while (end <=_size){_str[end - len] = _str[end];end++;}_size -= len;return *this;}void pop_back(){erase(_size - 1);}void swap(string& str){std::swap(_str, str._str);std::swap(_size, str._size);std::swap(_capacity, str._capacity);}//String operationsconst char* c_str() const{return _str;}size_t find(char c, size_t pos = 0) const{assert(pos < _size);size_t i = pos;while (i <= _size - 1){if (_str[i] == c){return _str[i];}}return npos;}size_t find(const char* s, size_t pos = 0) const{assert(pos < _size);char* ptr = strstr(_str, s);if (ptr != nullptr){return ptr - _str;}return npos;}string substr(size_t pos = 0, size_t len = npos) const{assert(pos < _size);if (len > _size - pos){len = _size - pos;}string str(_str + pos, len);return str;}private:size_t _size;size_t _capacity;char* _str;public:static size_t npos;};size_t string::npos = -1;//Non-member function overloadsvoid swap(string& s1, string& s2){s1.swap(s2);}bool operator== (const string& lhs, const string& rhs){return strcmp(lhs.c_str(), rhs.c_str()) == 0;}bool operator!= (const string& lhs, const string& rhs){return !(lhs == rhs);}bool operator< (const string& lhs, const string& rhs){return strcmp(lhs.c_str(), rhs.c_str()) < 0;}bool operator<= (const string& lhs, const string& rhs){return lhs < rhs || lhs == rhs;}bool operator> (const string& lhs, const string& rhs){return !(lhs <= rhs);}bool operator>= (const string& lhs, const string& rhs){return !(lhs < rhs);}ostream& operator << (ostream& out, const string& str){for (size_t i = 0; i < str.size(); i++){out << str[i];}return out;}istream& operator>>(istream& in, string& str){str.clear();char c;char buffer[256];size_t i = 0;c = in.get();while (c != ' ' && c != '\n'){buffer[i++] = c;if (i == 255){buffer[i] = '\0';str += buffer;i = 0;}c = in.get();c = in.get();}if (i > 0){buffer[i] = '\0';str += buffer;}return in;}istream& getline(istream& is, string& str, char delim = '\n'){str.clear();int i = 0;char buffer[256];char ch;ch = is.get();while (ch != delim){// 放到buffbuffer[i++] = ch;if (i == 255){buffer[i] = '\0';str += buffer;i = 0;}ch = is.get();}if (i > 0){buffer[i] = '\0';str += buffer;}return is;}
}

二.vector

#pragma oncenamespace hebre
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//Member functionsvector(){}//initializer_list是一个类，支持迭代器//底层相当于开了一块数组的空间vector(initializer_list<T> il){reserve(il.size());for (auto e : il){push_back(e);}}// 这里的第一个参数必须是一个int类型// 如果参数类型是size_t的话// 调用函数会与vector(InputIterator first, InputIterator last)函数更加的适配// 编译器就会优先调用vector(InputIterator first, InputIterator last)函数// 我们如果使用int类型的话，才会更加适配 vector(int n, const T& val = T()){while (n--){push_back(val);}}vector(const vector<T>& v){size_t len = v.capacity();reserve(len);for (auto& e : v){push_back(e);}}// 类模板的成员函数，也可以是一个函数模板。例如：list，stringtemplate <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}~vector(){delete[] _start;_start = nullptr;_finish = nullptr;_endofstorage = nullptr;}vector& operator= (const vector& x){for (auto e : x){push_back(e);}return *this;}//Iterators:iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}//Capacity:size_t size(){return _finish - _start;}const size_t size() const{return _finish - _start;}void resize(size_t n, T val = T()){if (n <= size()){_finish = _start + n;}else{if (n > capacity){reserve(n);}while (_finish < _start + n){*_finish = val;++_finish;}}}size_t capacity() const{return _endofstorage - _start;}void reserve(size_t n){if (n > capacity()){size_t oldsize = size();//size()在过程中会出错，因为_start会改变，_finish还保留着原来的值T* tmp;tmp = new T[n];if (_start){// 浅拷贝，不能拷贝自定义类型// memcpy(tmp, _start, sizeof(T) * oldSize);for (int i = 0; i < size(); i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + oldsize;_endofstorage = _start + n;}}bool empty() const{return _start == _finish;}//Element access:T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}T& at(size_t i){assert(i < size());return _start[i];}const T& at(size_t i) const{assert(i < size());return _start[i];}T& front(){return _start[0];}const T& front() const{return _start[0];}T& back(){return _start[size() - 1];;}const T& back() const{return _start[size() - 1];}//Modifiers:iterator insert(const_iterator pos, const T& x){assert(pos >= _start && pos <= _finish);size_t len = pos - _start;iterator p = _start + len;if (_finish == _endofstorage){size_t len = p - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);p = _start + len;}iterator i = _finish - 1;while (i >= p){*(i + 1) = *i;--i;}*p = x;++_finish;return p;}iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator i = pos + 1;while (i < _finish){*(i - 1) = *i;++i;}_finish--;return pos;}void push_back(const T& x){insert(_finish, x);}void pop_back(){assert(!empty());--_finish;}void swap(vector<T>& x){std::swap(_start, x._start);std::swap(_finish, x._finish);std::swap(_endofstorage, x._endofstorage);}void clear(){_finish = _start;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};//Non-member function overloadstemplate <class T>void swap(vector<T>& x, vector<T>& y){x.swap(y);}template<class T>void swap(T& x, T& y){std::swap(x, y);}
}

三.list

#pragma oncenamespace hebre
{template<class T>struct list_node{T _data;list_node<T>* _prev;list_node<T>* _next;list_node(const T& val = T()): _data(val), _next(nullptr), _prev(nullptr){}};template<class T,class Dereference,class Ptr>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T, Dereference, Ptr> Self;Node* _node;list_iterator(Node* node):_node(node){}Dereference operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}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;}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;void empty_init(){_node = new Node();_node->_next = _node;_node->_prev = _node;_size = 0;}list(){empty_init();}template <class InputIterator>list(InputIterator first, InputIterator last){empty_init();while (first != last){push_back(*first);first++;}}//注意：n的数据类型必须是int,原因在上面的构造函数list(int n, const T& val = T()){empty_init();while (n--){push_back(val);}}list(const list& x){empty_init();for (auto e : x){push_back(e);}}list(initializer_list<T> il){empty_init();for (auto e : il){push_back(e);}}~list(){clear();delete _node;_node = nullptr;}list<T>& operator=(list<T> lt){swap(lt);return *this;}//Iterators:iterator begin(){return iterator(_node->_next);}const_iterator begin() const{return const_iterator(_node->_next);}iterator end(){return iterator(_node);}const_iterator end() const{return const_iterator(_node);}//Capacity:bool empty() const{return _node->_next == _node;}size_t size() const{return _size;}T& front(){return _node->_next;}const T& front() const{return _node->_next;}T& back(){return _node->_prev;}const T& back() const{return _node->_prev;}//Modifiers:template <class InputIterator>void assign(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}iterator insert(iterator position, const T& val){Node* cur = position._node;Node* newnode = new Node(val);Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;return iterator(newnode);}iterator erase(iterator position){Node* cur = position._node;Node* next = cur->_next;Node* prev = cur->_prev;prev->_next = next;next->_prev = prev;_size--;delete cur;cur = nullptr;return iterator(prev);}void swap(list<T>& x){std::swap(_node, x._node);std::swap(_size, x._size);}void resize(size_t n, T val = T()){if (n < _size){size_t x = _size - n;while (x--){pop_back();}}else{size_t x = n - _size;while (x--){push_back(val);}}}void clear(){while (_node->_next != _node){pop_back();}}private:Node* _node;size_t _size;};
}

四.stack

#pragma once
#include<deque>
namespace hebre
{template<class T, class Container = deque<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top() const{return _con.back();}T& top(){return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}void swap(stack& x){_con.swap(x);}private:Container _con;};
}

五.queue

#pragma once
#include<deque>namespace hebre
{template<class T, class Container = deque<T>>class queue{public:void push(const T& val){_con.push_back(val);}void pop(){_con.pop_front();}size_t size(){return _con.size();}T& front(){return _con.front();}const T& front() const{return _con.front();}T& back(){return _con.back();}const T& back() const{return _con.back();}bool empty(){return _con.empty();}private:Container _con;};
}

六.priority_queue

#pragma once
#include<deque>namespace hebre
{//默认为升序排序template<class T, class Container = deque<T>>class priority_queue{public:void AdjustUp(int child){int parent = (child - 1) / 2;while (child > 0){if (_con[child] < _con[parent]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void AdjustDown(int parent){int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child] > _con[child + 1]){child++;}if (_con[parent] > _con[child]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const T& val){_con.push_back(val);AdjustUp(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}bool empty() const{return _con.empty();}T& top(){return _con[0];}const T& top() const{return _con[0];}size_t size() const{return _con.size();}private:Container _con;};
}