C++---vector模拟实现

一、准备

1、使用模板

在类外部使用模板，保证模拟实现的vector是通用的

template<class T>
class vector
{}；

2、重命名迭代器

typedef T* iterator;
typedef const T* const_iterator;

3、打印

vector类没有流提取功能，手动实现打印

在类外部实现

template<class T>
void print_vector(const vector<T>& v)
{for (auto e : v){cout << e << " ";}cout << endl;
}
template<class Container>
void print_container(const Container& v)
{for (auto e : v){cout << e << ' ';}cout << endl;
}

二、私有成员

vector使用指针

private:iterator _start = nullptr;iterator _finish = nullptr;//相当于sizeiterator _end_of_storage = nullptr;//相当于capacity

三、构造与赋值

1、默认构造

vector() = default;//默认值
vector(size_t n, const T& val = T())
{ reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}
}

2、拷贝构造

①

vector(const vector<T>& v)
{reserve(v.size());for (auto& e : v){push_back(e);}
}

②迭代器拷贝

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

3、析构函数

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

5、赋值重载

void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}
vector<T>& operator=(vector<T> v)
{swap(v);return *this;
}

四、功能实现

1、迭代器

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

2、size和capacity

指针相减

size_t size() const
{return _finish - _start;
}
size_t capacity() const
{return _end_of_storage - _start;
}

3、[]重载

T& operator[](size_t i)
{assert(i < size());return _start[i];
}
//const 版本
const T& operator[](size_t i) const
{assert(i < size());return _start[i];
}

4、开空间

迭代器失效:给tmp开空间，然后将start中的数据移入tmp，delete start，size是由指针相减返回的，start=tmp，导致start指向的空间改变，但是finish还在原来的位置，最后导致size不再是原来的size，所以在删除start之前要保存old_size；

void reserve(size_t n)
{if (n > capacity()){size_t old_size = size();T* tmp = new T[n];for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}
}

5、尾插

void push_back(const T& x)
{if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finish = x;++_finish;
}

6、任意位置插入

如果空间已经满了，就要先保存pos于start的相对位置，因为开空间的话，start改变，pos的位置就失效了，开空间后要更新pos

iterator insert(iterator pos, const T& val)
{assert(pos >= _start);assert(pos <= _finish);//判断空间是否已满if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}iterator it = _finish;while (it != pos){*it = *(it - 1);--it;}*pos = val;++_finish;return pos;
}

7、尾删

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

8、resize

n<size：start保留前n个数据

n>pos：在start后追加数据val使数据个数到n

void resize(size_t n, const T& val = T())
{if (n <= size()){_finish = _start + n;}else{//直接开n的空间//reserve(n);if (capacity() < n){reserve(n < 2 * capacity() ? 2 * capacity() : n);}while (_finish < _start + n){*_finish = val;++_finish;}}
}

9、删除任意位置数据

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