vecctor是动态顺序表
一、了解vector的相关接口及其功能
1.构造函数相关接口
| 函数声明 | 功能介绍 |
| vector() | 无参构造 |
| vector(size_type n,const value_type& val=value_type()) | 构造并初始化n个val |
| vector(const value& x) | 拷贝构造 |
| vector(InputIterator first, InputIterator last) | 使用迭代器进行构造 |
上面不认识的类型如size_type、value_type等都是被typedef过的，可以根据英文意思直接理解，或者找相关的文档进行查询
void test1()
{
vector<int> v;
for (auto x : v)
{
cout << x << " ";
}
cout << endl;
vector<int> v1(5, 2);
for (auto x : v1)
{
cout << x << " ";
}
cout << endl;
vector<int> v2(v1);
//vector<int> v2(v1.begin(),v1.end());和上一行代码等价
for (auto x : v2)
{
cout << x << " ";
}
cout << endl;
string s = "hello world";
vector<char> v3(s.begin(), s.end());//不同类型的迭代器也能初始化
for (auto x : v3)
{
cout << x << " ";
}
cout << endl;
}
2.vector iterator的使用
| iterator的使用 | 接口说明 |
| begin()+end() | 获取第一个数据位置的iterator/const_iterator，获取最后一个数据的下一个位置的iterator/const_iterator |
| rbegin()+rend() | 获取第一个数据位置的reverse_iterator/const_reverse_iterator，获取最后一个数据的下一个位置的reverse_iterator/const_reverse_iterator |
void test2()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
vector<int>::iterator it = v.begin();
//注意如果写类型名，那么一定要写正确，如加不加reverse、const一定要写对
//如果不想写这么长的类型，可以写auto自动类型推导
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
vector<int>::reverse_iterator it1 = v.rbegin();
while (it1 != v.rend())
{
cout << *it1 << " ";
it1++;
}
cout << endl;
}
3.vector空间增长问题
| 函数名称 | 接口说明 |
| size | 获取数据个数 |
| capacity | 获取容量大小 |
| empty | 判断是否为空 |
| resize | 改变vector的size |
| reserve | 改变vector的capacity |
void test3()
{
vector<int> v;
cout << v.size() << endl;
cout << v.capacity() << endl;
cout << v.empty() << endl;
cout << "----------" << endl;
vector<int> v1(5, 2);
cout << v1.size() << endl;
cout << v1.capacity() << endl;
cout << v1.empty() << endl;
cout << "----------" << endl;
//vector<int> v2(v1);
vector<int> v2(v1.begin(),v1.end());
cout << v2.size() << endl;
cout << v2.capacity() << endl;
cout << v2.empty() << endl;
cout << "----------" << endl;
string s = "hello world";
vector<char>v3(s.begin(), s.end());
cout << v3.size() << endl;
cout << v3.capacity() << endl;
cout << v3.empty() << endl;
}
结论：构造函数创建对象时，有多少个数据开多少空间
void test4()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
int n = sizeof(arr) / sizeof(int);
vector<int> v(arr, arr + n);//vector迭代器本质就是指针，所以这里传指针没问题
cout << v.size() << ":" << v.capacity() << endl;
v.reserve(100);
v.resize(20);
cout << v.size() << ":" << v.capacity() << endl;
v.reserve(50);
v.resize(5);
cout << v.size() << ":" << v.capacity() << endl;
}
结论：resize控制size()的大小，空间不够会扩容，reserve申请预留的空间如果小于已经开出的空间capacity()，则空间大小不变，如果大于，则会扩容（至于扩多大的容，主要看编辑器，但是至少保证空间够用）
4.vector的增删查改
| 函数名称 | 接口说明 |
| push_back() | 尾插 |
| pop_back() | 尾删 |
| find | 查找（vector没有find成员函数，这个find是算法库中的），如果找到find |
| insert | 在pos之前插入val，返回新插入元素位置的迭代器 |
| erase | 删除pos位置的数据，返回被删除元素的下一个元素位置的迭代器 |
| swap | 交换两个vector的数据空间 |
| operator[] | 像数组一样用下标访问数据 |
void test6()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
v.pop_back();
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
v.insert(v.begin() + 1, 10);
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
v.erase(v.begin() + 2);
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
auto itx = find(v.begin(), v.end(), 10);//返回迭代器
if (itx != v.end())//没找到返回end()
cout << *itx;
}
5.迭代器失效（重点）
由于vector的迭代器底层是指针，所以vector迭代器失效本质就是野指针问题
对于vector可能会导致其迭代器失效的操作有
1.在插入元素的过程中，导致扩容，而导致原本的空间被释放，那么在扩容之前获取的迭代器就会失效（这是一个例子，其实只要引发扩容，都可能导致迭代器失效）
2.删除操作，一般来说删除元素不会出现问题，但是如果删除的元素是最后一个元素，那么最后一个元素（即被删除元素位置）的迭代器就会失效
（如果没看懂的，可以看看后面对插入删除功能的模拟实现）
以下代码的功能是删除vector中所有的偶数，请问while循环的代码是正确的
void test7()
{
vector<int> v{ 1, 2, 3, 4 };
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
v.erase(it);
++it;
}
while (it != v.end())
{
if (*it % 2 == 0)
v.erase(it);
else
++it;
}
while (it != v.end())
{
if (*it % 2 == 0)
it = v.erase(it);
else
++it;
}
}很显然第一个while循环错误，因为删除是将后面的元素整体往前移动，所以删除完成之后，it就已经指向了后一个元素，不需要++，
而第二个while循环逻辑上没有问题，但是不同的编辑器会有不同的结果，在vs上，编辑器会严格检查在可能导致迭代器失效的操作之后使用之前的迭代器，直接报错，而在g++上就不会报错
第三个while循环才是标准的写法，而这也是对迭代器失效问题的解决---为erase函数设置了返回值，返回删除元素后面一个元素的迭代器，这样就确保不会发生迭代器失效的问题了
二、模拟实现vector的基本功能
namespace zxws
{
template<class T>
class vector
{
public:
// Vector的迭代器是一个原生指针
typedef T* iterator;
typedef const T* const_iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
// 构造和析构
vector()
{}
vector(int n, const T& value = T())
{
reserve(n);
while (n--)
{
push_back(value);
}
}
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
first++;
}
}
vector(const vector<T>& v)
{
reserve(v.capacity());
for (auto& x : v)
{
push_back(x);
}
}
vector<T>& operator= (vector<T> v)
{
swap(v);
return *this;
}
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endOfStorage = nullptr;
}
}
// capacity
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endOfStorage - _start;
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_endOfStorage = _start + n;
}
}
void resize(size_t n, const T& value = T())
{
if (n > size())
{
reserve(n);
for (size_t i = size(); i < n; i++)
{
_start[i] = value;
}
}
_finish = n + _start;
}
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos)const
{
assert(pos < size());
return _start[pos];
}
void push_back(const T& x)
{
if (_finish == _endOfStorage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
_finish++;
}
void pop_back()
{
assert(size() > 0);
_finish--;
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endOfStorage, v._endOfStorage);
}
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _endOfStorage)
{
size_t l = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + l;
}
iterator it = _finish;
while (it > pos)
{
*it = *(it - 1);
--it;
}
*pos = x;
_finish++;
return pos;
}
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos;
while (it < _finish - 1)
{
*it = *(it + 1);
it++;
}
_finish--;
return pos;
}
private:
iterator _start = nullptr;// 指向数据块的开始
iterator _finish = nullptr; // 指向有效数据的尾
iterator _endOfStorage = nullptr; // 指向存储容量的尾
};
void test()
{
//vector<int> v;
vector<int> v(10);
vector<int> v(10,2);
//v.push_back(1);
//v.push_back(2);
//v.push_back(3);
//v.push_back(4);
//for (auto x : v)
//{
// cout << x << " ";
//}
//cout << endl;
//vector<int>v1(v);
//for (auto x : v1)
//{
// cout << x << " ";
//}
//cout << endl;
string s = "hello world";
vector<char> s1(s.begin(), s.end());
for (auto x : s1)
{
cout << x << " ";
}
cout << endl;
vector<char> s2;
s2 = s1;
for (auto x : s2)
{
cout << x << " ";
}
cout << endl;
}
void test1()
{
vector<string>v;
v.push_back("11111111");
v.push_back("11111111");
v.push_back("11111111");
v.push_back("11111111");
v.push_back("11111111");
v.push_back("11111111");
v.push_back("11111111");
v.push_back("11111111");
v.push_back("11111111");
for (auto x : v)
{
cout << x << " ";
}
cout << endl;
}
void test2()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(4);
vector<int>::iterator it = v.begin();
while(it!=v.end())
{
if (*it % 2 == 0)
it = v.erase(it);
else
it++;
}
for (auto x : v)
{
cout << x << " ";
}
cout << endl;
v.pop_back();
for (auto x : v)
{
cout << x << " ";
}
cout << endl;
}
void test3()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.insert(v.begin()+2, 0);
v.insert(v.end(),0);
for (auto x : v)
{
cout << x << " ";
}
cout << endl;
}
}
