vector
vector 介绍
vector 是 C++ 标准模板库（STL）中的一个动态数组容器，也是 C++ 的顺序表，它提供了动态大小调整和高效的随机访问功能。vector 的元素在内存中是连续存储的，这意味着可以通过指针或索引高效地访问元素。vector 自动管理其内部使用的内存，不需要手动分配和释放，支持常见容器操作，如插入、删除、遍历等。
String 和 vector 区别
String 结尾有\0；vector 要储存其他类型所以没有\0
String 主要用来存储 char 类型；vector 主要用来存储除 char 的其他类型
vector 常见接口
构造函数
存储结构
结构上使用命名空间 wu 进行封装，防止与库冲突，使用 class 封装成为对象 vector。这样 typedef 的一点是和 STL 保持一致。
写 vector 写成类模板，可以支持存贮多种类型数据 _start 表示数据存储的开始地址 _finish 表示数据存贮的下一个地址 _endofstorage 表示数据当前开辟的最大空间的地址
namespace wu {
template<class T> class vector {
public:
typedef T* iterator;
typedef const T* const_iterator;
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
};
}
默认构造函数
初始化
初始化指针都为空
vector() :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) {}
模版的定义，进行初始化
//类模版的成员函数，也可以是一个函数模版
template<class InputIterator> vector(InputIterator first, InputIterator last) {
while (first != last) {
push_back(*first);
++first;
}
}
拷贝构造函数
利用一个对象初始化另外一个对象传引用 new 出和传递的对象一样大小的空间，在 string 类中我们利用了 mencpy 进行拷贝，在 vector 中不采用 mencpy mencpy 拷贝只能进行内置类型的浅拷贝，不能进行自定义类型的深拷贝 在这里面进行依次赋值，或者 push_back 最后进行_finish 和_endofstorage 的初始化
vector(const vector<T>& v) {
_start = new T[v.capacity()];
for (size_t i = 0; i < v.size(); i++) {
_start[i] = v._start[i];
}
_finish = _start + v.size();
_endofstorage = _start + v.capacity();
}
赋值运算符重载
在 operator=的参数中是值传递，是实参的拷贝，这里面利用这个特性进数据的交换
返回 this 指针就是赋值的内容了
void swap(vector<T>& tmp) {
std::swap(_start, tmp._start);
std::swap(_finish, tmp._finish);
std::swap(_endofstorage, tmp._endofstorage);
}
vector<T>& operator=(vector<T> v) {
swap(v);
return *this;
}
析构函数
判断_start 是否为空为空，避免再次析构
~vector() {
if (_start) {
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
}
迭代器（iterator）
本质是指针
const_iterator cbegin() { return _finish; }
const_iterator cend() const { return _start; }
iterator begin() { return _start; }
iterator end() { return _finish; }
const_iterator begin()const { return _start; }
const_iterator end()const { return _finish; }
容量（capacity）
capacity
size_t capacity() const { return _endofstorage - _start; }
size
size_t size() const { return _finish - _start; }
empty
bool empty() { return _start == _finish; }
resize
n<=capacity 直接进行移动_finish n>capacity 进行容量的检查和扩容，依次赋值 val
void resize(size_t n, T val = T()) {
if (n <= size()) {
_finish = _start + n;
} else {
reserve(n);
while (_finish < _start + n) {
*_finish = val;
++_finish;
}
}
}
reserve
开始判断需要扩容的大小是否大于 capacity，以避免重复扩容效率低下 在开始时候记录原始空间的大小，是为了避免迭代器失效 进行空间的扩容，会将原来的空间析构，原始的计算空间大小已经已释放，指向的_start_finish_endofstorage 已经失效 这里还是采用在这里面进行依次赋值，或者 push_back 更新_start _finish _endofstorage
void reserve(size_t n) {
if (n > capacity()) {
size_t oldSize = size();
T* tmp = new T[n];
if (_start) {
//memcpy(tmp, _start, sizeof(T) * oldSize);
for (size_t i = 0; i < oldSize; i++) {
tmp[i] = _start[i];
}
delete[]_start;
}
_start = tmp;
_finish = _start + oldSize;
_endofstorage = _start + n;
}
}
修改（modify）
push_back
**首先进行容量的检查
直接将_finsih位置解引用赋值，++_finsih**
void push_back(const T& x) {
if (_finish == _endofstorage) {
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
++_finish;
}
pop_back
void pop_back() {
assert(!empty());
_finish--;
}
insert
进行断言，防止 pos 越界访问 判断空间的大小_finish == _endofstorage size_t len = pos - _start 用 step 记录，距离 _start 距离，扩容的时候将原空间释放，pos 将无法访问，扩容完成后进行 pos 的恢复 将 pos 位置的数据依次进行移动、 插入 pos 位置的值，修改_finish 为了避免迭代器失效，返回现在的位置 pos
iterator insert(iterator pos, const T& x) {
assert(pos >= _start && pos <= _finish);
if (_finish == _endofstorage) {
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
iterator i = _finish - 1;
while (i >= pos) {
*(i + 1) = *i;
--i;
}
*pos = x;
++_finish;
return pos;
}
erase
进行断言，防止 pos 越界访问
将 pos 后面的元素向前面移动，进行覆盖
为了避免迭代器失效，返回现在的位置 pos
iterator erase(iterator pos) {
assert(pos >= _start);
assert(pos < _finish);
iterator i = pos + 1;
while (i < _finish) {
*(i - 1) = *i;
++i;
}
_finish--;
return pos;
}
swap
void swap(vector<T>& tmp) {
std::swap(_start, tmp._start);
std::swap(_finish, tmp._finish);
std::swap(_endofstorage, tmp._endofstorage);
}
operator[]
实现 const 和 非 const 两种，只读和可读可改
充分利用字符串特性可以进行下标的访问
T& operator[](size_t i) {
assert(i < size());
return _start[i];
}
const T& operator[](size_t i)const {
assert(i < size());
return _start[i];
}
源码
#pragma once
#include<assert.h>
#include<iostream>
using namespace std;
namespace wu {
template<class T> class vector {
public:
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() {}
//类模版的成员函数，也可以是一个函数模版
template<class InputIterator> vector(InputIterator first, InputIterator last) {
while (first != last) {
push_back(*first);
++first;
}
}
vector(size_t n, const T& val = T()) {
reserve(n);
for ( i = ; i < n; i++) {
(val);
}
}
( n, T& val = ()) {
(n);
( i = ; i < n; i++) {
(val);
}
}
(initializer_list<T> il) {
(il.());
(& e : il) {
(e);
}
}
( vector<T>& v) {
(v.());
(& e : v) {
(e);
}
}
{
std::(_start, tmp._start);
std::(_finish, tmp._finish);
std::(_endofstorage, tmp._endofstorage);
}
vector<T>& =(vector<T> v) {
(v);
*;
}
~() {
(_start) {
[]_start;
_start = _finish = _endofstorage = ;
}
}
T& []( i) {
(i < ());
_start[i];
}
{ _finish - _start; }
{ _endofstorage - _start; }
{
(n > ()) {
oldSize = ();
T* tmp = T[n];
(_start) {
( i = ; i < oldSize; i++) {
tmp[i] = _start[i];
}
[]_start;
}
_start = tmp;
_finish = _start + oldSize;
_endofstorage = _start + n;
}
}
{
(n <= ()) {
_finish = _start + n;
} {
(n);
(_finish < _start + n) {
*_finish = val;
++_finish;
}
}
}
{
(_finish, x);
}
{ _start == _finish; }
{
(!());
_finish--;
}
{
(pos >= _start && pos <= _finish);
(_finish == _endofstorage) {
len = pos - _start;
(() == ? : () * );
pos = _start + len;
}
iterator i = _finish - ;
(i >= pos) {
*(i + ) = *i;
--i;
}
*pos = x;
++_finish;
pos;
}
{
(pos >= _start);
(pos < _finish);
iterator i = pos + ;
(i < _finish) {
*(i - ) = *i;
++i;
}
_finish--;
pos;
}
:
iterator _start = ;
iterator _finish = ;
iterator _endofstorage = ;
};
}
