1. 前言
vector是 C++ STL 中的一个类模板，它是一个动态数组；本篇文章只模拟实现常用的接口，与库中实现的相比，功能类似，但实现方式并不相同
2. 接口
2.1 构造+析构函数
// 无参构造
vector();
// 拷贝构造
vector(const vector<T>& v);
// 用 n 个 val 构造
vector(size_t n, const T& val = T());
// 用 initializer_list 的对象构造
vector(cosnt initializer_list& il);
// 用一段迭代器区间构造
template<class InputIterator>
vector(InputIterator first, InputIterator last);
// 析构
~vector()
2.2 运算符重载
// 赋值运算符重载
vector<T>& operator=(vector<T> v);
2.3 迭代器
// 可读可写
iterator begin();
iterator end();
// 只读
const_iterator begin() const;
const_iterator end() const;
2.4 容量
// 个数
size_t size() const;
// 容量
size_t capacity() const;
// 判空
bool empty() const;
// 扩容
void reserve(size_t n);
// 调整大小
void resize(size_t n, const T& val = T());
2.5 元素访问
T& operator[](size_t pos);
// 只读
const T& operator[](size_t pos) const;
2.6 修改
// 尾插
void push_back(const T& val);
// 尾删
void pop_back();
// pos位置插入
void insert(iterator pos, const T& val);
// pos位置删除
void erase(iteraotr pos);
// 交换
void swap(vector<T>& v);
3. 模拟实现
#pragma once
#include<iostream>
#include<string.h>
#include<assert.h>
using namespace std;
namespace byh
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
vector() {}
vector(const vector<T>& v)
{
reserve(v.capacity());
for (auto& e : v)
{
push_back(e);
}
}
vector(size_t n, const T& val = T())
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
vector(int n, const T& val = T())
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
vector(const initializer_list<T>& il)
{
reserve(il.size());
for (auto& e : il)
{
push_back(e);
}
}
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
reserve(last - first);
while (first != last)
{
push_back(*first);
first++;
}
}
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
bool empty() const
{
return _start == _finish;
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t len = size();
T* temp = new T[n];
for (int i = 0; i < len; i++)
{
temp[i] = _start[i];
}
delete[] _start;
_start = temp;
_finish = temp + len;
_end_of_storage = temp + n;
}
}
void resize(size_t n, const T& val = T())
{
if (n < size())
_finish = _start + n;
else
{
for (int i = size(); i < n; i++)
{
push_back(val);
}
}
}
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& val)
{
if (_finish == _end_of_storage)
reserve(capacity() == 0 ? 4 : capacity() * 2);
(*_finish) = val;
_finish++;
}
void pop_back()
{
assert(_finish > _start);
_finish--;
}
void insert(iterator pos, const T& val)
{
assert(pos <= _finish);
assert(pos >= _start);
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
iterator end = _finish;
while (end > pos)
{
*end = *(end - 1);
end--;
}
*pos = val;
_finish++;
}
void erase(iterator pos)
{
assert(pos < _finish);
assert(pos >= _start);
while (pos < _finish - 1)
{
*pos = *(pos + 1);
pos++;
}
_finish--;
}
void swap(vector<T>& v)
{
std::swap(v._start);
std::swap(v._finish);
std::swap(v._end_of_storage);
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}
4. 迭代器失效
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();
cout << *it << endl;
v.insert(v.begin(), 10);
cout << *it << end;
// 输出：
// 1
// -572662307
当使用insert并且有扩容时，之前定义的迭代器变量就失效，原因是扩容后对象的空间位置改变了
对于这种情况，我们当然可以先更新我们的迭代器变量再使用，但最好不要使用insert后的迭代器
// 删除偶数
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(6);
vector<int>::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
v.erase(it);
it++;
}
print_vector(v);
// 输出：
// 程序崩溃
程序崩溃的原因是erase元素后，it相当于往后走了一步，it++又往后走了一步，最后要么没有删除偶数，要么越界访问，总之也是迭代器失效的问题
std::vector中如果erase后使用迭代器，编译器会报错
对于迭代器失效的问题：
erase或insert后，最好不要使用之前定义的迭代器- 如果要使用，按照规则更新迭代器再使用
