begin和end

vector当中的begin函数返回容器的首地址，end函数返回容器当中有效数据的下一个数据的地址。

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

还需要重载一对适用于const对象的begin和end函数，使得const对象调用begin和end函数时所得到的迭代器只能对数据进行读操作，而不能进行修改。

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

此时再让我们来看看vector使用迭代器的代码也就一目了然了，实际上就是使用指针遍历容器。

vector<int> v(5, 3);
vector<int>::iterator it = v.begin();
while (it != v.end())
{
  cout << *it << " ";
  it++;
}
cout << endl;

现在我们实现了迭代器，实际上就可以使用范围for遍历容器了，因为编译器在编译时会自动将范围for替换成迭代器的形式。

vector<int> v(5,3);
for(auto e:v)
{
  cout<<e<<" ";
}
cout<<endl;

容量和大小相关函数

size和capacity

对照着vector当中三个成员遍历各自的指向，我们可以很容易得出当前容器中的有效数据个数和最大容量。由于两个指针相减的结果，就是这两个指针之间对应类型的数据个数，所以size可以由_finish - _start得到，而capacity可以由_endofstorage - _start得到。

size_t size()const
{
  return _finish - _start; //返回容器当中有效数据的个数
}
size_t capacity()const
{
  return _endofstorage - _start; //返回当前容器的最大容量
}

reserve

reserve规则：

1、当n大于对象当前的capacity时，将capacity扩大到n或大于n。

2、当n小于对象当前的capacity时，什么也不做。

reserve函数的实现思路也是很简单的，先判断所给n是否大于当前容器的最大容量（否则无需进行任何操作），操作时直接开辟一块可以容纳n个数据的空间，然后将原容器当中的有效数据拷贝到该空间，之后将原容器存储数据的空间释放，并将新开辟的空间交给该容器维护，最好更新容器当中各个成员变量的值即可。

void reserve(size_t n)
{
  if (n > capacity()) //判断是否需要进行操作
  {
    size_t sz = size(); //记录当前容器当中有效数据的个数
    T* tmp = new T[n]; //开辟一块可以容纳n个数据的空间
    if (_start) //判断是否为空容器
    {
      for (size_t i = 0; i < sz; i++) //将容器当中的数据一个个拷贝到tmp当中
      {
        tmp[i] = _start[i];
      }
      delete[] _start; //将容器本身存储数据的空间释放
    }
    _start = tmp; //将tmp所维护的数据交给_start进行维护
    _finish = _start + sz; //容器有效数据的尾
    _endofstorage = _start + n; //整个容器的尾
  }
}

在reserve函数的实现当中有两个地方需要注意：

1）在进行操作之前需要提前记录当前容器当中有效数据的个数。

因为我们最后需要更新_finish指针的指向，而_finish指针的指向就等于_start指针加容器当中有效数据的个数，当_start指针的指向改变后我们再调用size函数通过_finish - _start计算出的有效数据的个数就是一个随机值了。

2）拷贝容器当中的数据时，不能使用memcpy函数进行拷贝。

可能你会想，当vector当中存储的是string的时候，虽然使用memcpy函数reserve出来的容器与原容器当中每个对应的string成员都指向一个字符串空间，但是原容器存储数据的空间不是已经被释放了，相当于现在只有一个容器维护这这些字符串空间，这还有什么影响。

但是不要忘了，当你释放原容器空间的时候，原容器当中存储的每个string在释放时会调用string的析构函数，将其指向的字符串也进行释放，所以使用memcpy函数reserve出来的容器当中的每一个string所指向的字符串实际上是一块已经被释放的空间，访问该容器时就是对内存空间进行非法访问。

所以说我们还是得用for循环将容器当中的string一个个赋值过来，因为这样能够间接调用string的赋值运算符重载，实现string的深拷贝。

resize

resize规则：

1、当n大于当前的size时，将size扩大到n，扩大的数据为val，若val未给出，则默认为容器所存储类型的默认构造函数所构造出来的值。

2、当n小于当前的size时，将size缩小到n。

根据resize函数的规则，进入函数我们可以先判断所给n是否小于容器当前的size，若小于，则通过改变_finish的指向，直接将容器的size缩小到n即可，否则先判断该容器是否需要增容，然后再将扩大的数据赋值为val即可。

void resize(size_t n, const T& val = T())
{
  if (n < size()) //当n小于当前的size时
  {
    _finish = _start + n; //将size缩小到n
  }
  else //当n大于当前的size时
  {
    if (n > capacity()) //判断是否需要增容
    {
      reserve(n);
    }
    while (_finish < _start + n) //将size扩大到n
    {
      *_finish = val;
      _finish++;
    }
  }
}

注意： 在C++当中内置类型也可以看作是一个类，它们也有自己的默认构造函数，所以在给resize函数的参数val设置缺省值时，设置为T( )即可。

empty

empty函数可以直接通过比较容器当中的_start和_finish指针的指向来判断容器是否为空，若所指位置相同，则该容器为空。

1. bool empty()const
2. {
3.  return _start == _finish;
4. }

修改容器内容相关函数

push_back

要尾插数据首先得判断容器是否已满，若已满则需要先进行增容，然后将数据尾插到_finish指向得位置，再将_finish++即可。

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

使用memcpy拷贝问题

假设模拟实现的vector中的reserve接口中，使用memcpy进行的拷贝，以下代码会发生什么问题？

int main()
{
qk::vector<qk::string> v;
v.push_back("1111");
v.push_back("2222");
v.push_back("3333");
return 0;
}

问题分析：

1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中

2. 如果拷贝的是自定义类型的元素，memcpy即高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。

结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

pop_back

尾删数据之前也得先判断容器是否为空，若为空则做断言处理，若不为空则将_finish--即可。

1. void pop_back()
2. {
3. assert(!empty());
4.   _finish--;
5. }

insert

insert函数可以在所给迭代器pos位置插入数据，在插入数据前先判断是否需要增容，然后将pos位置及其之后的数据统一向后挪动一位，以留出pos位置进行插入，最后将数据插入到pos位置即可。

void insert(iterator pos, const T& x)
{
  if (_finish == _endofstorage) 
  {
    size_t len = pos - _start; 
    size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); 
    reserve(newcapacity); 
    pos = _start + len; 
  }
  iterator end = _finish;
  while (end > pos + 1)
  {
    *end = *(end - 1);
    end--;
  }
  *pos = x; 
  _finish++; 
}

erase

erase函数可以删除所给迭代器pos位置得数据，在删除数据前需要判断容器释放为空，若为空则需做断言处理，删除数据时直接将pos位置之后得数据同一向前挪动一位，将pos位置的数据覆盖即可。

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

swap

swap函数用于交换两个容器的数据，我们可以直接调用库当中的swap函数将两个容器当中的各个成员变量进行交换即可。

//交换两个容器的数据
void swap(vector<T>& v)
{
  //交换容器当中的各个成员变量
  ::swap(_start, v._start);
  ::swap(_finish, v._finish);
  ::swap(_endofstorage, v._endofstorage);
}

注意:在此处调用库当中的swap需要在swap之前加上“::”（作用域限定符），告诉编译器这里优先在全局范围寻找swap函数，否则编译器会认为你调用的就是你正在实现的swap函数（就近原则）。

访问容器相关函数

operator[]

vector也支持我们使用"下标+[]"的方式对容器当中的数据进行访问，实现时直接返回对应位置的数据即可。

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

注意： 重载运算符[ ]时需要重载一个适用于const容器的，因为const容器通过“下标+[ ]”获取到的数据只允许进行读操作，不能对数据进行修改。

C++学习笔记(十四)——vector的模拟实现（二）