vector 的文档介绍1. vector 是表示可变大小数组的序列容器。2. 就像数组一样， vector 也采用的连续存储空间来存储元素。也就是意味着可以采用下标对 vector 的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。3. 本质讲， vector 使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候， vector 并不会每次都重新分配大小。4. vector 分配空间策略： vector 会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。5. 因此， vector 占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。6. 与其它动态序列容器相比（ deque, list and forward_list ）， vector 在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起 list 和 forward_list统一的迭代器和引用更好。使用 STL 的三个境界：能用，明理，能扩展 ，那么下面学习 vector ，我们也是按照这个方法去学习
简单了解vector过后，这个博客我们主要经行string的常见函数的常见接口的模拟实现，这可以有效帮助大家理解vector。
#pragma once
#include<iostream>
#include<assert.h>
using std::cout;
using std::endl;
namespace king
{
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()) {
_start = new T[n];
_endOfStorage = _start + n;
_finish = _start;
while (_finish != _endOfStorage) {
*_finish = value;
_finish++;
}
}
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
}
vector(const vector<T>& v)
{
reserve(v.capacity());
for (auto& e : v) { //引用减少拷贝
push_back(e);
}
}
vector<T>& operator= (vector<T> v)
{
_finish = _start;
reserve(v.capacity());
for (auto& e : v) { //引用减少拷贝
push_back(e);
}
return *this;
}
~vector() {
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 newcapacity) {
if (_start+newcapacity > _endOfStorage) {
size_t oldsize = _finish - _start;
iterator tmp = new T[newcapacity];
memcpy(tmp, _start, sizeof(T) * oldsize);
delete[] _start;
_start = tmp;
_finish = _start + oldsize;
_endOfStorage = _start + newcapacity;
}
return;
}
void resize(size_t n, const T& value = T())
{
if (n > size()) {
int count = n-size();
while (count) {
push_back(value);
count--;
}
}
else {
_finish = _start + n;
}
}
///access///
T& operator[](size_t pos) {
return *(_start + pos);
}
const T& operator[](size_t pos)const
{
return *(_start + pos);
}
///modify/
void push_back(T val) {
if (_finish == _endOfStorage) {
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
}
*_finish = val;
_finish++;
return;
}
void pop_back() {
_finish--;
}
void swap(vector<T>& v) {
std::swap(v._start,_start);
std::swap(v._finish,_finish);
std::swap(v._endOfStorage,_endOfStorage);
}
iterator insert(iterator pos, const T& x) {
assert(_start <= pos && pos <= _finish);
iterator cur = _finish;
while (cur > pos-1) {
*cur = *(cur - 1);
cur--;
}
_finish++;
*pos = x;
return pos;
}
iterator erase(iterator pos) {
assert(_start <= pos && pos <= _finish);
iterator cur = pos;
while (cur < _finish-1) {
*cur = *(cur + 1);
cur++;
}
_finish--;
return pos;
}
private:
iterator _start=nullptr;
iterator _finish=nullptr;
iterator _endOfStorage=nullptr;
};
void test1() {
vector<int> t1;
t1.push_back(4);
t1.push_back(4);
t1.push_back(4);
for (auto e : t1) {
cout << e << ' ';
}
cout << endl;
}
void test2() {
vector<int> t2(10, 1);
for (auto e : t2) {
cout << e << ' ';
}
cout << endl;
}
void test3() {
vector<int> t3(5,1);
vector<int> t4(t3);
vector<int> t5;
t5 = t3;
cout << "t3:";
for (auto e : t3) {
cout << e << ' ';
}
cout << endl;
cout << "t4:";
for (auto e : t4) {
cout << e << ' ';
}
cout << endl;
cout << "t5:";
for (auto e : t5) {
cout << e << ' ';
}
cout << endl;
}
void test4() {
vector<int> t3(5, 1);
vector<int> t4(5, 2);
cout << "t3:";
for (auto e : t3) {
cout << e << ' ';
}
cout << endl;
cout << "t4:";
for (auto e : t4) {
cout << e << ' ';
}
cout << endl;
t3.pop_back();
t4.pop_back();
cout << "t3:";
for (auto e : t3) {
cout << e << ' ';
}
cout << endl;
cout << "t4:";
for (auto e : t4) {
cout << e << ' ';
}
cout << endl;
t3.swap(t4);
cout << "t3:";
for (auto e : t3) {
cout << e << ' ';
}
cout << endl;
cout << "t4:";
for (auto e : t4) {
cout << e << ' ';
}
cout << endl;
}
void test5() {
vector<int> t1(10,9);
for (auto e : t1) {
cout << e << ' ';
}
cout << endl;
t1.resize(5);
for (auto e : t1) {
cout << e << ' ';
}
cout << endl;
t1.resize(10, 1);
for (auto e : t1) {
cout << e << ' ';
}
cout << endl;
}
void test6() {
vector<int> t6;
for (int i = 0; i < 10; i++) {
t6.push_back(i);
}
for (auto e : t6) {
cout << e << ' ';
}
cout << endl;
t6.erase(t6.begin());
for (auto e : t6) {
cout << e << ' ';
}
cout << endl;
t6.erase(t6.begin());
for (auto e : t6) {
cout << e << ' ';
}
cout << endl;
t6.erase(t6.end());
for (auto e : t6) {
cout << e << ' ';
}
cout << endl;
}
void test7() {
vector<int> t6;
for (int i = 0; i < 10; i++) {
t6.push_back(i);
}
for (auto e : t6) {
cout << e << ' ';
}
cout << endl;
t6.insert(t6.begin(), 0);
for (auto e : t6) {
cout << e << ' ';
}
cout << endl;
}
}
