STL源码分析之vector(三)—其它函数 eraser()、operator[]和operator =

说明： STL源码分析系列博客的使用的是https://www.sgi.com/tech/stl/download.html 里面的STL v2.03版.不同的STL或许会有所不同。

其它vector内容请参照本系列其它博客。

1.其它插入函数：

1.1 iterator insert(iterator position,const T& x);

向某个位置插入值X.返回插入位置

   iterator insert(iterator position, const T& x) {
    size_type n = position - begin();
    if (finish != end_of_storage && position == end()) {
        construct(finish, x);
        ++finish;
    } else
        insert_aux(position, x);
    return begin() + n;
}

如果 剩有内存用插入，且插入尾部，则直接使用construct(finish,x)把X的值拷贝到最后一个有效元素的后一个元素，然后让finish自增。
否则 使用inset_aux()函数处理插入中间或需要申请内存的情况。

其它插入函数都是调用这个函数完成插入的。

2.1删除元素：

2.1 void pop_back();把最后一个元素删除

   void pop_back() {
        --finish;
        destroy(finish);
}

先让finish自减，指向最后一个有效元素，然后再调用destroy函数去析构这个元素！
注意！destroy（）的内部只是调用了（*finish）->~T()的析构函数而已，并没有释放这个元素所占有的内存！

2.2 void erase(iterator position);删除指定位置的元素

    void erase(iterator position) {
    if (position + 1 != end())
        copy(position + 1, finish, position);
    --finish;
    destroy(finish);
}

如果是删除最后一个有效元素，则和pop_back()一样。
否则，把postion+1到finish的所有元素都向前移动一个单位，将position原来的元素内容覆盖，最后调用最后一个有效元素的析构函数后让finish自减。

2.3 void erase(iterator first, iterator last);删除从first到last的元素

    void erase(iterator first, iterator last) {
        iterator i = copy(last, finish, first);
    destroy(i, finish);
    finish = finish - (last - first); 
}

类似的，将last到finish的所有元素向前移动，覆盖掉first~last的元素，然后再去析构那些无效的元素，并维护finish的值。

2.4 void clear();删除所有元素；

void clear() { erase(begin(), end()); }

这个代码很直观，就不解释了。

取元素函数：

3.1 reference front() { return *begin(); }

取首元素，返回引用

3.2 reference back() { return *(end() - 1); }

取最后一个有效元素，返回引用

3.3 中括号运算符：[]

reference operator[](size_type n) { return *(begin() + n); }
const_reference operator[](size_type n) const { return *(begin() + n); }

简单粗暴，没毛病！
值得注意的是！！！在更高级的STL实现版本，operator[]内部会对参数n做合理性检查，防止越界访问.
例如：vs2013使用的STL版本中 vector :: operator[]的实现为：

reference operator[](size_type _Pos)
        {   // subscript mutable sequence
 #if _ITERATOR_DEBUG_LEVEL == 2
        if (size() <= _Pos)
            {   // report error
            _DEBUG_ERROR("vector subscript out of range");
            _SCL_SECURE_OUT_OF_RANGE;
            }

 #elif _ITERATOR_DEBUG_LEVEL == 1
        _SCL_SECURE_VALIDATE_RANGE(_Pos < size());
 #endif /* _ITERATOR_DEBUG_LEVEL */
        return (*(this->_Myfirst + _Pos));
        }

可知如果[]中的参数大于等于size()的话，也就是大于等于有效元素个数+1的话，就会抛出异常。

其它函数

4.1 void resize(size_type new_size,const T&x);

重新定义vector的大小,并设置初值：

   void resize(size_type new_size, const T& x) {
      if (new_size < size()) 
        erase(begin() + new_size, end());
      else
        insert(end(), new_size - size(), x);
    }

不带初值的重定义vector的大小：
void resize(size_type new_size) { resize(new_size, T()); };

实现的过程是
1.若新的大小new_size 小于原大小，则把first+new_size到end()的所以元素都erase，此时改变大小后的vector剩下的那些元素保留原来的值。
2.若新的大小new_size大于等于size(),则在vector的所有有效元素后面插入new_size-size()个初值等于x的新元素；

4.2 赋值运算符

template <class T, class Alloc>
vector<T, Alloc>& vector<T, Alloc>::operator=(const vector<T, Alloc>& x);

赋值函数写的是有点厉害的！！！明白的人自然知道其中的妙处

template <class T, class Alloc>
vector<T, Alloc>& vector<T, Alloc>::operator=(const vector<T, Alloc>& x) {
  if (&x != this) 
{
    if (x.size() > capacity()) {
      iterator tmp = allocate_and_copy(x.end() - x.begin(),
                                             x.begin(), x.end());
      destroy(start, finish);
      deallocate();
      start = tmp;
      end_of_storage = start + (x.end() - x.begin());
    }
    else if (size() >= x.size()) {
      iterator i = copy(x.begin(), x.end(), begin());
      destroy(i, finish);
    }
    else {
      copy(x.begin(), x.begin() + size(), start);
      uninitialized_copy(x.begin() + size(), x.end(), finish);
    }
    finish = start + x.size();
  }
  return *this;
}

第3行 if(&x!=this) 这个判断是必不可少的，这个判断即可加快速度，因为两个如果相等则无须复制；更重要的是可以避免当两个操作数一致所导致的一些难以预料的错误；

该细节可参考 博客 http://blog.csdn.net/jmh1996/article/details/76508575 处理“自我复制”的内容。

第 5 行：如果右操作数的大小更大，那么赋值号左边的将存不下那么多内容，则先申请一块与右操作数有效元素所需大小的内存，再把左操作数原来的内存释放。

后面就比较简单了。

总结

上述三篇博客分析了vector的核心代码，受益很多。

0.vector使用start,finish,end_of_storage来维护其内部的数据结构，维护其动态堆。

1.vector在扩展内存的时候使用了二倍法，预先申请了更大的内存，防止频繁的malloc

2.vector使用memmove（）来进行内存的复制，这样做可以正确处理内存有重叠的情况。

3.vector的protected函数 功能很专一，比如 copy(),uninitialized_copy(),initialized_copy()正常复制，未初始化元素的复制，已经初始化元素的复制···等等

4.使用#ifdef等宏指令，有条件的编译，尤其是那些try~catch~用来调试的代码段。这个技巧很棒！

以上5点，可以在自己写程序的时候加以借鉴。

最后一点，通过对vector源码的学习，对vector理解更加深刻一些吧。