前言：vector是顺序表（本质也是数组）
文档参考网站：https://legacy.cplusplus.com/reference/vector/vector/vector/
//底层代码
#include<assert.h>
#include<iostream>
#include<vector>
#include<string>
using namespace std;
namespace bit
{
template<typename T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
template <typename InputIterator>
vector(InputIterator first, InputIterator last)
{
reserve(last - first);
while (first != last)
{
push_back(*first);
first++;
}
}
vector(int size = 1)
{
_begin = _end = new T[size];
_endofstorage = _begin + size;
}
~vector()
{
delete[] _begin;
_begin = _end = _endofstorage = nullptr;
}
vector(const vector<T>& s)
{
reserve(s.capacity());
for (auto& e : s)
push_back(e);
}
int size() const
{
return _end - _begin;
}
int capacity() const
{
return _endofstorage - _begin;
}
void reserve(int newcapacity)
{
if (newcapacity > capacity())
{
int old_size = size();
iterator tmp = new T[newcapacity];
for(int i = 0 ; i < old_size ; i++)
{
tmp[i] = _begin[i];
}
//不能用memcpy,防止数据进行浅拷贝
_begin = tmp;
_end = tmp + old_size;
_endofstorage = tmp + newcapacity;
}
}
void push_back(T val)
{
int old_size = size();
if (_end == _endofstorage)
{
reserve(2 * old_size);
}
*_end = val;
_end++;
}
iterator begin() //返回临时变量
{
return _begin;
}
iterator end()
{
return _end;
}
const_iterator begin() const
{
return (const_iterator)_begin;
}
const_iterator end() const
{
return (const_iterator)_end;
}
void pop_back()
{
_end--;
}
iterator insert(iterator position, const T& val)
{
assert(position < _end);
iterator tmp = _end;
if (_end == _endofstorage) {
size_t len = position - _begin;
reserve(2 * size());
position = _begin + len;
}
while (_end != position)
{
*_end = *(_end - 1);
_end--;
}
iterator k = _end;
*_end = val;
_end = tmp;
_end++;
return k;
}
T& operator[] (int n)
{
assert(n < size());
return _begin[n];
}
const T& operator[] (int n) const
{
assert(n < size());
return _begin[n];
}
iterator erase(iterator position)
{
assert(position < _end);
iterator tmp = position;
while (position != _end)
{
*(position) = *(position + 1);
position++;
}
_end--;
return tmp;
}
iterator erase(iterator first, iterator last)
{
assert(last < _end && first < _end);
int a = last - first;
iterator tmp = last;
iterator k = first;
while (tmp != _end)
{
*first = *tmp;
tmp++;
first++;
}
_end -= a;
return k;
}
void clear()
{
_end = _begin;
}
void resize(int n, const T& val = T())
{
int _size = size();
if (n > _size)
{
reserve(n);
iterator t = _begin + n;
while (_end != t)
{
*_end = val;
_end++;
}
}
else
{
_end = _begin + n;
}
}
private:
iterator _begin = nullptr;//初始化列表
iterator _end = nulptr;
iterator _endofstorage;
};
}构造函数
第一种方式： vector( int size = 1 )// 全缺省，作为默然构造函数
开10个整形的数组
第二个方式：vector( int size , const T& val = T() )
解释 T() 当T为自定义类型时，调用T的默然构造函数
但对于内置类型，编译器会自动调用内置类型的默然构造（纯粹为了符合类模版）
对于int 为 0 ， 对于double 为 0.0 ，对于char 为 '\0' , 对于指针为nullptr等
第三种方式：运用类成员函数模版
template <class InputIterator> vector (InputIterator first, InputIterator last) 左闭右开
第四种方式：C++11提出的（用初始化链表初始化）
e的类型是初始化链表
初始化链表只有四个接口函数 ， 初始化链表只能支持遍历 ，不能支持赋值，初始化链表中的数据储存在常量区中（不能被修改）
析构函数
底层实现简单 （ clear 函数 + 指针置为空指针 ）
这里补充一下clear函数
void clear()
{
_end = _begin;
}
~vector()
{
clear();
delete[] _begin;
_begin = _end = _endofstorage = nullptr;
}
拷贝构造函数（深拷贝）
现代写法：
vector( const vector<T> & s )
{
reserve(s.capacity());//提前开好空间
for( auto& e : s )//使用引用，防止拷贝构造，提升效率
{
push_bakc(e);//注意数据要进行深拷贝
}
}
迭代器
由于物理空间上连续，与指针的行为相似
typedef T* iterator ;
typedef const T* const_iterator;
要注意*this是const成员还是非const成员
iterator begin()
{
return _begin;
}
iterator end()
{
return _end;
}
const_iterator begin()const
{
return (const T*) _begin;
}
const_iterator end() const
{
return (const T*)_end;
}
const T& operator[](int npos) const
{
assert( npos < size() );//注意未初始化的地方不能使用
return _begin[npos];
}
T& operator[](int npos)
{
assert( npos < size() );
return _begin[npos];
}
运算符重载
vector<T>& operator=( vector<T> s) (构造 加 交换 )
{
swap(s,*this);
return *this;
}
insert函数
主要是在某个位置之前插入一个值或一段区间
样列：
#include<string>
#include<vector>
#include<iostream>
using namespace std;
int main()
{
vector<int> s;
s.push_back(1);
s.push_back(2);
s.push_back(3);
s.push_back(4);
s.push_back(5);
s.insert(s.begin() + 1, 10);
for (auto& e : s)
{
cout << e << " ";
}
cout << endl;
}
样列：
#include<string>
#include<vector>
#include<iostream>
using namespace std;
int main()
{
vector<int> s;
s.push_back(1);
s.push_back(2);
s.push_back(3);
s.push_back(4);
s.push_back(5);
string k("asdfasfsaf");
s.insert(s.begin() + 1, k.begin() + 2 , k.end() - 4);
for (auto& e : s)
{
cout << e << " ";
}
cout << endl;
}
erase函数（一般不会缩容）
删除某个位置的值 ， 或删除一段区间的值（左闭右开）
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> s;
s.push_back(1);
s.push_back(1);
s.push_back(1);
s.push_back(1);
s.push_back(1);
s.push_back(1);
s.push_back(1);
s.erase(s.begin(), s.end() - 1);
for (auto& e : s)
{
cout << e << " ";
}
cout << endl;
return 0;
}
注意在使用insert函数和erase函数会造成迭代器失效，所以在使用完迭代器之后，就不能在使用，
如果你就要使用，则要更新迭代器
举个例子：（删除顺序表中的偶数）
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> s;
s.push_back(1);
s.push_back(2);
s.push_back(3);
s.push_back(4);
s.push_back(4);
s.push_back(9);
s.push_back(11);
s.push_back(11);
s.push_back(11);
auto it = s.begin();
while (it != s.end())
{
if (*it % 2 == 0)it = s.erase(it);
else it++;
}
for (auto& e : s)cout << e << " ";
cout << endl;
return 0;
}
push_back 和 pop_back
尾增 和 尾删
reserve和resize函数
reserve函数时扩容,reserve使用完，不能用[]赋值
resize函数是扩容（当newcapacity > newcapacity） + 初始化
要注意reserve函数在完成扩容时，是对数据进行深拷贝（不能使用memcpy）
