vector 源码分析

vector

vector 是 STL 实现的一个动态数组类本文只是分析 vector 的结构以及一些重要的设计方法, 对于一些没有那么重要的方法或者函数将一笔掠过, 如果想仔细了解, 请自行阅读源码

vector 的内容主要定义在 stl_vector.h 中, 该文件只是定义了 vector 对象以及相应类方法, 而且由于不直接透露 vector 的实现, 对其进行了一次封装, 将 stl_vector.h 与它所需要的头文件组合成vector.h, 直接使用 stl_vector.h 会缺少 vector 所依赖的函数或者方法的定义以及实现

定义部分

template <class T, class Alloc = alloc>
class vector {
public:
  typedef T value_type; 
  typedef value_type* pointer; 
  typedef const value_type* const_pointer;
  typedef value_type* iterator;
  typedef const value_type* const_iterator;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;

#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  typedef reverse_iterator<const_iterator> const_reverse_iterator;
  typedef reverse_iterator<iterator> reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  typedef reverse_iterator<const_iterator, value_type, const_reference, 
                           difference_type>  const_reverse_iterator;
  typedef reverse_iterator<iterator, value_type, reference, difference_type>
          reverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
protected:
  typedef simple_alloc<value_type, Alloc> data_allocator;
    ......
}

typedef reverse_iterator<const_iterator> const_reverse_iterator;

typedef simple_alloc<value_type, Alloc> data_allocator;

• reverse_iterator 为反向迭代器, 即 移动方向与正向迭代器相反

• simple_alloc<value_type, Alloc> 进行对象内存的构造以及释放

• 在 SGI_2.91 中 vector 的迭代器就是原始的指针

vector 对象

iterator start;
iterator finish;
iterator end_of_storage;

• start 动态数组的起始地址

• finish 最后一个数据的下一个位置

• end_of_storage 整个动态数组最大容量位置的后一个位置

• 可以看出 vector 本身并不是内含一个数组, 而且指向堆中一块内存的指针

获取基本数据

获取迭代器

iterator begin() { return start; }
  
const_iterator begin() const { return start; }

iterator end() { return finish; }

const_iterator end() const { return finish; }

获取反向迭代器

reverse_iterator rbegin() { return reverse_iterator(end()); }
  
const_reverse_iterator rbegin() const { 
    return const_reverse_iterator(end()); 
}
reverse_iterator rend() { return reverse_iterator(begin()); }

const_reverse_iterator rend() const { 
	return const_reverse_iterator(begin()); 
}

获取容器基本信息

//容器大小
size_type size() const { return size_type(end() - begin()); }

//容器最大大小 最多可以记录 size_type(-1) 个字节 / 单个元素大小 
size_type max_size() const { return size_type(-1) / sizeof(T); }

//当前容器的容量
size_type capacity() const { return size_type(end_of_storage - begin()); }

//容器是否为空
bool empty() const { return begin() == end(); }

//第一个元素
reference front() { return *begin(); }

const_reference front() const { return *begin(); }

//最后一个元素
reference back() { return *(end() - 1); }

const_reference back() const { return *(end() - 1); }

vector 构造方法

无参构造

vector() : start(0), finish(0), end_of_storage(0) {}

这里可以看出 vector 并没有预留出容量, 而是默认容量为空

下面这些构造方法都是调用了 fill_initialize 方法

// 将容器初始化为长度为 n 且值均为 value 
vector(size_type n, const T& value) { fill_initialize(n, value); }

//上面方法的 int 型重载
vector(int n, const T& value) { fill_initialize(n, value); }

//上面方法的 long 型重载
vector(long n, const T& value) { fill_initialize(n, value); }

//构造长度为 n 且所有元素值均为该类型默认构造值, 而且要求在创建对象的时候显示调用该构造方法
explicit vector(size_type n) { fill_initialize(n, T()); }

上面的有参构造全部都调用了 fill_initialize 的辅助方法

void fill_initialize(size_type n, const T& value) {
	start = allocate_and_fill(n, value);
	finish = start + n;
	end_of_storage = finish;
}

这个方法首先使用内存分配函数 allocate_and_fill 建立了一块长度为 $n$ 且值为 $value$ 的空间, 并将其赋值给 $start$ , $finish$ 为最后一个元素的下一个位置, end_of_storage 此时为 $n$ 该容器被初始化为容量为 $n$ 且拥有 $n$ 个值为 $value$ 的元素

拷贝构造方法

vector(const vector<T, Alloc>& x) {
    start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end());
    finish = start + (x.end() - x.begin());
    end_of_storage = finish;
}

• 其本质就是调用 allocate_and_copy 函数来将要被拷贝的 vector 内元素赋值给当前创建的对象, 但是只是接收了被拷贝对象的元素值, 并没有拷贝被拷贝对象的容量(仔细观察一下)

接受一个范围来进行初始化的构造方法

如果定义允许使用类成员模板, 那么该构造方法就为接受一个输入型迭代器所表示的范围进行初始化, 代码如下

template <class InputIterator>
vector(InputIterator first, InputIterator last) :
    start(0), finish(0), end_of_storage(0)
{
    range_initialize(first, last, iterator_category(first));
}

这里调用了 range_initialize 函数来进行范围的初始化 第三个参数表示将会根据迭代种类来实例化合适的范围初始化函数

template <class InputIterator>
void range_initialize(InputIterator first, InputIterator last,
                    input_iterator_tag) {
	for ( ; first != last; ++first)
        //这个方法暂且不表 后文会提到
  		push_back(*first);
}

template <class ForwardIterator>
void range_initialize(ForwardIterator first, ForwardIterator last,
                        forward_iterator_tag) {
    size_type n = 0;
    distance(first, last, n);
    start = allocate_and_copy(n, first, last);
    finish = start + n;
    end_of_storage = finish;
}

• 如果是 InputIterator 类型迭代器, 那么只能采用一次向前移动一个单位

• 如果是 ForwardIterator 类型迭代器, 那么就可以采取范围拷贝的方式来进行范围初始化

如果当前不允许使用类成员模板, 那么构造方法就为接受当前 vector 的迭代器表示的范围进行初始化

vector(const_iterator first, const_iterator last) {
    size_type n = 0;
    // 这里没有直接计算迭代器距离, 而是调用了 distance 因为不是所有迭代器都可以直接做减法来计算距离
    distance(first, last, n);
    start = allocate_and_copy(n, first, last);
    finish = start + n;
    end_of_storage = finish;
}

析构方法

~vector() { 
    destroy(start, finish);
    deallocate();
}

• 没什么特别, 内部调用了内存管理的函数来对内存进行释放 相对没有那么重要

reserve 方法(重新设定容器大小)

void reserve(size_type n) {
    if (capacity() < n) {
        const size_type old_size = size();
        iterator tmp = allocate_and_copy(n, start, finish);
        destroy(start, finish);
        deallocate();
        start = tmp;
        finish = tmp + old_size;
        end_of_storage = start + n;
    }
}

• 该方法仅在要求重新设定的容器大小大于当前容器的最大容量时才会生效, 本质就是将重新开辟一块空间为 $n$ 的空间并将元素复制进去, 同时释放原来指向的空间, 并更新容器内所维护的数组块内存信息

交换方法 swap()

void swap(vector<T, Alloc>& x) {
    __STD::swap(start, x.start);
    __STD::swap(finish, x.finish);
    __STD::swap(end_of_storage, x.end_of_storage);
}

• vector 没有选择交换内存空间的数据, 而是选择了交换维护元素空间的信息, 提高了效率

操作元素

该部分分为 插入数据 和 删除数据 两方面来进行剖析

插入数据

首先先介绍进行辅助插入数据的函数, 或者说 vector 提供的 public 的插入数据方式都是以这些函数为底层实现

insert_aux(iterator position, const T& x);

template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
  if (finish != end_of_storage) {
    construct(finish, *(finish - 1));
    ++finish;
    T x_copy = x;
    copy_backward(position, finish - 2, finish - 1);
    *position = x_copy;
  }
  else {
    const size_type old_size = size();
    const size_type len = old_size != 0 ? 2 * old_size : 1;
    iterator new_start = data_allocator::allocate(len);
    iterator new_finish = new_start;
    __STL_TRY {
      new_finish = uninitialized_copy(start, position, new_start);
      construct(new_finish, x);
      ++new_finish;
      new_finish = uninitialized_copy(position, finish, new_finish);
    }

#       ifdef  __STL_USE_EXCEPTIONS 
    catch(...) {
      destroy(new_start, new_finish); 
      data_allocator::deallocate(new_start, len);
      throw;
    }
#       endif /* __STL_USE_EXCEPTIONS */
    destroy(begin(), end());
    deallocate();
    start = new_start;
    finish = new_finish;
    end_of_storage = new_start + len;
  }
}

参数为要插入的迭代器的位置, 以及要插入的值. 插入要分两种情况

• 如果没有到达了容器的最大容量, 如果没有就将最后一个元素向后移动一个位置, 再将 position 到原来最后一个元素的前一个元素向后复制一个位置, 这样就在 position, 位置置空, 此时再插入要插入的元素即可

• 如果到达了容器的最大容量, 那么就要开辟一块容量大小为当前最大容量两倍的空间作为容器将要管理的空间, 并将 begin 到position - 1 位置的元素复制到新的位置, 同时在 position 位置插入要插入的元素, 再将剩下的元素复制进新的容器内, 并将原容器的内存释放

• 可以发现, vecotr 在扩容时会预留比原来最大容量多一倍的容量以应对之后的元素加入

push_back

void push_back(const T& x) {
    if (finish != end_of_storage) {
        construct(finish, x);
        ++finish;
    }
    else
        insert_aux(end(), 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;
}

这两个方法就是以 insert_aux 为底层来实现, 来实现在指定位置或者最后位置插入数据

insert

下面的 insert 等方法都是将多个元素或者某个范围内的元素插入某个位置

template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) {
  if (n != 0) {
    if (size_type(end_of_storage - finish) >= n) {
      T x_copy = x;
      const size_type elems_after = finish - position;
      iterator old_finish = finish;
      /**
       * 如果 pos 到 finish 的元素数量 > n 那么就可以直接通过移动来空出 n 个元素的位置
       * 否则就先再最后补出 n - elems_after 个元素, 然后将要移动的元素移动补出元素的 end() 
       * 的最后位置, 这样即空出了 n 个元素的位置
       */
      if (elems_after > n) {
        uninitialized_copy(finish - n, finish, finish);
        finish += n;
        copy_backward(position, old_finish - n, old_finish);
        fill(position, position + n, x_copy);
      }
      else {
        uninitialized_fill_n(finish, n - elems_after, x_copy);
        finish += n - elems_after;
        uninitialized_copy(position, old_finish, finish);
        finish += elems_after;
        fill(position, old_finish, x_copy);
      }
    }
    else {
      const size_type old_size = size();        
      const size_type len = old_size + max(old_size, n);
      iterator new_start = data_allocator::allocate(len);
      iterator new_finish = new_start;
      __STL_TRY {
        new_finish = uninitialized_copy(start, position, new_start);
        new_finish = uninitialized_fill_n(new_finish, n, x);
        new_finish = uninitialized_copy(position, finish, new_finish);
      }
#         ifdef  __STL_USE_EXCEPTIONS 
      catch(...) {
        destroy(new_start, new_finish);
        data_allocator::deallocate(new_start, len);
        throw;
      }
#         endif /* __STL_USE_EXCEPTIONS */
      destroy(start, finish);
      deallocate();
      start = new_start;
      finish = new_finish;
      end_of_storage = new_start + len;
    }
  }
}

原理其实与 insert_aux 类似, 都是先检查剩余空间够不够插入要求插入的元素数量, 如果足够就再次考虑需要将多少元素向后移动, 如果剩余空间不足以插入要求插入的元素数量, 那么就将进行扩容, 同时扩容大小是插入数据数量与原容器最大容量的 max

// 上面 insert 方法的重载方法, 都是以调用 insert 方法实现
void insert (iterator pos, int n, const T& x) {
    insert(pos, (size_type) n, x);
}
void insert (iterator pos, long n, const T& x) {
    insert(pos, (size_type) n, x);
}

range_insert

template <class T, class Alloc> template <class InputIterator>
void vector<T, Alloc>::range_insert(iterator pos,
                                    InputIterator first, InputIterator last,
                                    input_iterator_tag) {
  for ( ; first != last; ++first) {
    pos = insert(pos, *first);
    ++pos;
  }
}

该方法调用了上面的 insert 方法来依次将该范围内元素插入 由于是 InputIterator 迭代器所以选择的是一次向前移动一步

该方法还有 ForwardIterator 迭代器的重载方法

template <class T, class Alloc> template <class ForwardIterator>
void vector<T, Alloc>::range_insert(iterator position,
                                    ForwardIterator first,
                                    ForwardIterator last,
                                    forward_iterator_tag) {
  if (first != last) {
    size_type n = 0;
    //比上面的 insert 多了一步通过计算迭代器之间的距离来计算要插入的元素数量
    distance(first, last, n);
    if (size_type(end_of_storage - finish) >= n) {
      const size_type elems_after = finish - position;
      iterator old_finish = finish;
      if (elems_after > n) {
        uninitialized_copy(finish - n, finish, finish);
        finish += n;
        copy_backward(position, old_finish - n, old_finish);
        copy(first, last, position);
      }
      else {
        ForwardIterator mid = first;
        advance(mid, elems_after);
        uninitialized_copy(mid, last, finish);
        finish += n - elems_after;
        uninitialized_copy(position, old_finish, finish);
        finish += elems_after;
        copy(first, mid, position);
      }
    }
    else {
      const size_type old_size = size();
      const size_type len = old_size + max(old_size, n);
      iterator new_start = data_allocator::allocate(len);
      iterator new_finish = new_start;
      __STL_TRY {
        new_finish = uninitialized_copy(start, position, new_start);
        new_finish = uninitialized_copy(first, last, new_finish);
        new_finish = uninitialized_copy(position, finish, new_finish);
      }
#         ifdef __STL_USE_EXCEPTIONS
      catch(...) {
        destroy(new_start, new_finish);
        data_allocator::deallocate(new_start, len);
        throw;
      }
#         endif /* __STL_USE_EXCEPTIONS */
      destroy(start, finish);
      deallocate();
      start = new_start;
      finish = new_finish;
      end_of_storage = new_start + len;
    }
  }
}

实现思想及其原理与多个元素插入方法类似, 这里就不进行赘述

在禁用类成员模板的情况下, vector 也提供了相应的将两个迭代器之间的元素插入当前容器的某个位置的方法

原理思想与上述无异 此处直接展示代码

template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, 
                              const_iterator first, 
                              const_iterator last) {
  if (first != last) {
    size_type n = 0;
    distance(first, last, n);
    if (size_type(end_of_storage - finish) >= n) {
      const size_type elems_after = finish - position;
      iterator old_finish = finish;
      if (elems_after > n) {
        uninitialized_copy(finish - n, finish, finish);
        finish += n;
        copy_backward(position, old_finish - n, old_finish);
        copy(first, last, position);
      }
      else {
        uninitialized_copy(first + elems_after, last, finish);
        finish += n - elems_after;
        uninitialized_copy(position, old_finish, finish);
        finish += elems_after;
        copy(first, first + elems_after, position);
      }
    }
    else {
      const size_type old_size = size();
      const size_type len = old_size + max(old_size, n);
      iterator new_start = data_allocator::allocate(len);
      iterator new_finish = new_start;
      __STL_TRY {
        new_finish = uninitialized_copy(start, position, new_start);
        new_finish = uninitialized_copy(first, last, new_finish);
        new_finish = uninitialized_copy(position, finish, new_finish);
      }
#         ifdef __STL_USE_EXCEPTIONS
      catch(...) {
        destroy(new_start, new_finish);
        data_allocator::deallocate(new_start, len);
        throw;
      }
#         endif /* __STL_USE_EXCEPTIONS */
      destroy(start, finish);
      deallocate();
      start = new_start;
      finish = new_finish;
      end_of_storage = new_start + len;
    }
  }
}

删除元素

pop_back

直接选择移动 end() 位置向前移动一位并将该位置元素摧毁释放掉

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

erase

该方法有重载方法, 第一个是删除某个位置元素, 而第二个是删除 first - last 范围内的元素, 代码很简单清晰

iterator erase(iterator position) {
    if (position + 1 != end())
        copy(position + 1, finish, position);
    --finish;
    destroy(finish);
    return position;
}
iterator erase(iterator first, iterator last) {
    iterator i = copy(last, finish, first);
    destroy(i, finish);
    finish = finish - (last - first);
    return first;
}

重新设置容器容量 resize()

/**
* 如果新设置的容量小于当前容量, 那么就删除掉多余元素 反之则在最后插入不足的元素数量
*/
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);
}

/**
*可以发现该方法只是上面方法的重载方法, 对于没有指定修改容量后元素值的一律按照默认值
*/
void resize(size_type new_size) { resize(new_size, T()); }

重载运算符

operator[]

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

operator=

template <class T, class Alloc>
vector<T, Alloc>& vector<T, Alloc>::operator=(const vector<T, Alloc>& x) {
  //首先判断是不是自己赋值给自己, 如果是就不需要进行后续操作了
  if (&x != this) {
    //如果被赋值对象的最大容量小于 x 对象的当前容量, 就要进行扩容
    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);
    }
    //更新 end()
    finish = start + x.size();
  }
  return *this;
}

operator==

//大小相同且 equal(x.begin(), x.end(), y.begin()) 为真即可
template <class T, class Alloc>
inline bool operator==(const vector<T, Alloc>& x, const vector<T, Alloc>& y) {
  return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
}

operator<

//按照字典序的比较规则进行比较
template <class T, class Alloc>
inline bool operator<(const vector<T, Alloc>& x, const vector<T, Alloc>& y) {
  return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}