C++STL专题 vector底层实现

---

目录

一， vector的手搓

1.构造函数

2. 拷贝构造的实现

3.析构函数

4.begin() end() 的实现

5.reserve的实现

6.size和capacity的实现

7.push_back的实现

8.pop_back的实现

9.empty的实现

10.insert的实现

11.erase的实现

12.resize的实现

13.clear的实现

14.swap的实现

14. []重载

15.=重载

16. Vector类中的private

二，源码

---

一， vector的手搓

Vector类的定义

template <class T>
class Vector
{
public:typedef T* iterator;typedef const T* const_iterator;Vector(){}private:iterator _start = nullptr;//最开始iterator _finish = nullptr;//内容结尾(并不是容量的结尾)iterator _end_of_storage = nullptr;//容量结尾
};

1.构造函数

template<class InputIterator>
Vector(InputIterator first, InputIterator last)
{while (first != last){Push_back(*first);first++;}
}

(1).在模板类中再定义模板类，使得能够插入不同容器的值。

2. 拷贝构造的实现

Vector(const Vector<T>& v)//拷贝构造
{for (auto& e : v){Push_back(e);}
}

(1).直接使用范围for遍历一次即可。

3.析构函数

~Vector()
{if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}
}

(1).如果_start不空的话，就使用delete[] 释放空间。并且置空。

 

4.begin() end() 的实现

iterator begin()
{return _start;
}iterator end()
{return _finish;
}const_iterator begin() const
{return _start;
}const_iterator end() const
{return _finish;
}

(1).分为const修饰和不加const修饰，构成了函数重载，begin()返回起始_start即可，end()返回_finsih即可。

5.reserve的实现

void Reserve(size_t n)
{if (n > Capacity()){size_t oldsize = Size();T* tmp = new T[n];for (int i = 0; i < oldsize; i++) {tmp[i] = _start[i];}//memcpy(tmp, _start, Size() * sizeof(T));delete[] _start;_start = tmp;_finish = tmp + oldsize;_end_of_storage = tmp + n;}
}

(1).扩容函数，如果要求的空间大于当前的容量，就要扩容，首先存储当先数据个数Size()到oldsize，然后再开辟一个新空间，然后把_start中的全部数据拷贝到tmp中，然后再把_start释放空间，再将tmp赋值给_start，将_finish指向tmp+oldsize的位置。_end_of_storage指向tmp+n的位置。

6.size和capacity的实现

size_t Size()
{return _finish - _start;
}size_t Capacity()
{return _end_of_storage - _start;
}

(1).Size为vector中数据个数，所以直接返回_finish(最后一个数据的地址)减start(第一个数据的地址)即可。

(2).Capacity为vector中容量大小，所以直接返回_end_of_storage(容量的最后一个地址)减start(第一个数据的地址)即可。

7.push_back的实现

void Push_back(const T& x)
{if (_finish == _end_of_storage) // 扩容{Reserve(Capacity() == 0 ? 4 : Capacity() * 2);}*_finish = x;++_finish;
}

(1).push_back前要检查是否需要扩容，这里选择二倍扩容。

(2).直接将*_finish(元素的最后一个位置的下一个位置)赋值为x。再将_finish自加，使其移动到空位置，方便下次赋值。

8.pop_back的实现

void Pop_back()
{assert(!empty());--_finish;
}

(1).首先判断是否为空，如果为空就断言。

(2).直接将_finish自减即可。

9.empty的实现

bool empty()
{return _start == _finish;
}

(1).判断_start 和 _finish是否相等即可，如果相等就为空，否则为不空。

10.insert的实现

iterator insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage) // 扩容{size_t len = pos - _start; // 解决迭代器失效Reserve(Capacity() == 0 ? 4 : Capacity() * 2);pos = _start + len; // 解决迭代器失效}iterator end = _finish - 1;while (end >= pos) // 迭代器失效问题已经扩容了，但是pos还是指向原来的旧空间 野指针{*(end + 1) = *end;end--;}*pos = x;++_finish;return pos;
}

(1).大致思路为把要插入位置(pos)之后的全部向后移动一位，然后再将pos位置赋值为要插入的元素。

(2).要想插入，首先判断是否需要扩容。

(3).定义一个迭代器end，存储vector中最后一个元素的位置，然后循环判断(end >= pos)，每次成立时，就把end+1处赋值为end的元素，然后将end自减。退出循环后，直接将*pos赋值为x并把_finish自加即可。

11.erase的实现

void erase(iterator pos)
{assert(pos >= _start);assert(pos <= _finish);iterator it = pos + 1;while (it != end()){*(it - 1) = *it;++it;}--_finish;
}

(1).大致思路为将pos位置之后的全部元素都向前移动一个位置，最后将_finish自减即可。

12.resize的实现

void resize(size_t n, T val = T())
{// n<size// size<n<capacity// n>capaciityif (n < Size()){_finish = _start + n;}else{Reserve(n);while (_finish < _start + n){*_finish = val;++_finish;}}
}

(1).resize为对字符串大小做改变，当n<size时，就会对当前字符串缩减，其余情况为reserve。

13.clear的实现

void clear()
{_finish = _start;
}

(1).直接将_finish=_start即可。

14.swap的实现

void swap(Vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}

(1).直接交换即可。

14. []重载

T& operator[](size_t i)
{return _start[i];
}const T& operator[](size_t i) const
{return _start[i];
}

(1).由于_start为顺序表，所以直接返回顺序表的值即可。

15.=重载

//方法一：Vector<T>& operator=(const Vector<T>& v)
{if (this != &v){clear();Reverse(v.Size());for (auto& e : v){Push_back(e);}}return *this;
}//方法二：Vector<T>& operator=( vector<T> v){swap(v);return *this;}

(1).有两种方法，第一种方法为先清空_start，然后再对_start重新扩容，扩容置与v相等，然后遍历v，把v中的元素按个插入_start。

(2).方法二：要进行传值传参，不能用传址传参，然后直接交换即可，这样_start就成了v了，由于v为传值传参，并不受影响。

16. Vector类中的private

private:iterator _start = nullptr;//缺省iterator _finish = nullptr;//缺省iterator _end_of_storage = nullptr;//缺省

二，源码

#pragma once
#include <iostream>
#include <vector>
#include <assert.h>
#include<algorithm>namespace hhc
{template <class T>class Vector{public:typedef T* iterator;typedef const T* const_iterator;Vector(){}Vector(const Vector<T>& v)//拷贝构造{for (auto& e : v){Push_back(e);}}~Vector(){if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}void Reserve(size_t n){if (n > Capacity()){size_t oldsize = Size();T* tmp = new T[n];for (int i = 0; i < oldsize; i++) {tmp[i] = _start[i];}//memcpy(tmp, _start, Size() * sizeof(T));delete[] _start;_start = tmp;_finish = tmp + oldsize;_end_of_storage = tmp + n;}}size_t Size(){return _finish - _start;}size_t Capacity(){return _end_of_storage - _start;}void Push_back(const T& x){if (_finish == _end_of_storage) // 扩容{Reserve(Capacity() == 0 ? 4 : Capacity() * 2);}*_finish = x;++_finish;}bool empty(){return _start == _finish;}void Pop_back(){assert(!empty());--_finish;}void insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage) // 扩容{size_t len = pos - _start; // 解决迭代器失效Reserve(Capacity() == 0 ? 4 : Capacity() * 2);pos = _start + len; // 解决迭代器失效}iterator end = _finish - 1;while (end >= pos) // 迭代器失效问题已经扩容了，但是pos还是指向原来的旧空间 野指针{*(end + 1) = *end;end--;}*pos = x;++_finish;}void erase(iterator pos){assert(pos >= _start);assert(pos <= _finish);iterator it = pos + 1;while (it != end()){*(it - 1) = *it;++it;}--_finish;}void resize(size_t n, T val = T()){// n<size// size<n<capacity// n>capaciityif (n < Size()){_finish = _start + n;}else{Reserve(n);while (_finish < _start + n){*_finish = val;++_finish;}}}void clear(){_finish = _start;}void swap(Vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}template<class InputIterator>Vector(InputIterator first, InputIterator last){while (first != last){Push_back(*first);first++;}}T& operator[](size_t i){return _start[i];}const T& operator[](size_t i) const{return _start[i];}//方法一：Vector<T>& operator=(const Vector<T>& v){if (this != &v){clear();Reverse(v.Size());for (auto& e : v){Push_back(e);}}return *this;}//方法二：Vector<T>& operator=( vector<T> v){swap(v);return *this;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};template <class Container>void print_Container(const Container& v){// 没用实例化的类模板里面取东西，编译器不能区分const_iterator是类型还是静态成员变量// 编译器规定不能去没用实例化的模板里面取东西typename Container::const_iterator it = v.begin();auto itt = v.begin(); // 这样也行while (it != v.end()){std::cout << *it << ' ';*it++;}std::cout << std::endl;for (auto num : v){std::cout << num << ' ';}}}

---

本篇完