C++常见容器实现原理

引言

• 如果有一天！你骄傲离去！（抱歉搞错了）
• 如果有一天，你在简历上写下了这段话：
  
• 那么你不得不在面试前实现一下STL常见的容器了。
• C++的常用容器有：vector、string、deque、stack、queue、list、set、map。接下来就让我们对每种常用容器进行介绍和实现吧。

一、vector

• vector详细介绍
• 实现代码：

#include<assert.h>
#include<algorithm> // 包含函数std::swap// 模拟实现Vector
template<class T>	// T为容器中元素的类型
class vector
{
public:typedef T* iterator;			  // 统一化指向vector中元素的指针为：iteratortypedef const T* const_iterator;  // const_iterator指针无法修改指向的对象，但可以自增自减// 获取迭代器（const和非const）iterator begin(){return _start;	  // _start指向容器内存储的第一个元素}iterator end(){return _finish;	  // _finish指向容器内最后一个元素之后}const_iterator cbegin()const	// 实现同上即可，返回的类型是const_iterator{return _start;}const_iterator cend()const{return _finish;}// 运算符[]的重载T& operator[](size_t pos){assert(pos < size());	// size()返回容器内容纳的元素个数return _start[pos];		// 根据指针运算，直接索引到Pos索引值即可}const T& operator[](size_t pos)	// 同上{assert(pos < size());return start[pos];}// 构造函数vector() :_start(nullptr), _finish(nullptr), _endOfStorage(nullptr) {}	// 初始化三个成员指针为空指针// 迭代器区间构造函数template<class InputIterator>vector(InputIterator first, InputIterator last) : _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){while (first != last)	// 将区间中的每个元素按照顺序压入容器内即可{push_back(*first);first++;}}// 拷贝构造函数vector(const vector<T>& v) :_start(nullptr), _finish(nullptr), _endOfStorage(nullptr){vector<T> tmp(v.cbegin(), v.cend());	// 先使用区间构造一个同样的容器，然后把其和此容器进行交换即可swap(tmp);}// 使用n个val值的构造函数vector(size_t n, const T& val = T()){reserve(n);						// 将容器扩容到至少n个元素for (size_t i = 0; i < n; ++i)	// 将值压入即可{push_back(val);}}// 重载运算符=vector<T>& operator=(vector<T> v){swap(v);		// 由于v不是引用，是新构造来的，直接交换控制权即可return *this;	// 返回自身}// 析构函数~vector()			{delete[] _start;	// 释放申请的空间_start = _finish = _endOfStorage = nullptr;		// 将所有成员指针重置为空}// 容量调整函数（只扩容）void reserve(size_t n){if (n > capacity())	// 当且仅当需求的容量大于现在容器的最大容量时进行调整{size_t oldSize = size();	// 获取原本的容量T* tmp = new T[n];			// 申请需求的更大容量if (_start != nullptr)		// 如果容器本身中包含元素{for (int i = 0; i < size(); ++i)	// 将本身包含的元素拷贝到新申请的容量中{tmp[i] = _start[i];}delete[] _start;		// 释放原本的内存空间}_start = tmp;				// 将此容器的首地址记录为新申请的空间_finish = tmp + oldSize;	// 计算容器中最后一个元素之后的地址_endOfStorage = _start + n; // 计算容器中最大容量元素之后的地址}}// 元素个数调整函数（只扩容）void reserve(size_t n, T val = T()){if (n > capacity())	// 如果需要扩容则进行扩容{reserve(n);}if (n > size())		// 如果容器包含元素数目少于n，则将包含元素数目-n中的元素设为val{while (_finish < _start + n){*_finish = val;_finish++;}}else{					// 否则容器包含元素数目多于n，则将容器包含元素数目设为n_finish = _start + n;}}// 获取元素个数sizesize_t size()const{return _finish - _start;	// 指针运算}// 获取容量大小size_t capacity()const{return _endOfStorage - _start;	// 指针运算}// 判断是否为空bool empty()const{return _finish == _start;	// 当首元素地址 等于 最后一个元素之后的地址 时，即不存在元素即为空}void clear(){_finish = _start;	// 清空，即最后一个元素之后的地址等于空间首地址}// 尾部插入函数void push_back(const T& x){if (_finish == _endOfStorage)	// 如果空间满了{size_t newCapacity = (capacity() == 0 ? 4 : capacity() * 2);	// 扩容两倍reserve(newCapacity);	// 扩容}*_finish = x;	// 将最后一个之后的元素设为x，即压入x_finish++;		// 尾指针向后移动}// 尾部删除函数void pop_back(){assert(!empty());	// 不为空时删除_finish--;			// 直接将尾指针向前移动即可}// 插入指定位置void insert(iterator pos, const T& val){assert(pos < _finish);	// 插入位置需要位于：[_start,finish)assert(pos >= _start);if (_finish == _endOfStorage) // 如果空间满了{size_t len = pos - _start;		//计算此位置之前有多少元素size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;	// 计算扩容后的容量数目reserve(newCapacity);			// 扩容pos = _start + len;	 // 计算新的对应pos位置 }iterator end = _finish - 1; // 计算尾元素位置while (end >= pos)		// 从尾元素到插入位置之后的位置{*(end + 1) = *end;	// 每个元素向后移动end--;}*pos = val;  // 在pos位置插入val_finish++;	 // 将finish+1 }// 删除指定位置iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator begin = pos;	while (begin < _finish - 1)	 // 从删除位置到最后一个元素{*(begin) = *(begin + 1); // 每个元素向前移动一位begin++;}_finish--;	// 尾指针-1return pos;}// 交换void swap(vector<T>& v)	// 交换对应指针即可{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}private:iterator _start;			// 容器中第一个元素地址，也是容器申请内存空间首地址iterator _finish;			// 容器中最后一个元素之后的地址iterator _endOfStorage;		// 容器申请的内存空间的尾地址，也即是容器能容纳的最多元素之后的地址
};

二、list

• 实现代码：

三、map