STL源码剖析(vector)

在SGI STL中，vector使用的是连续的内存空间，迭代器使用普通指针来实现。

因为使用的是连续的内存空间，在vector容量不足的时候会直接分配一块新的内存，把原来的元素copy进去，回收原来的内存空间。

因此在vector扩容的时候，原来的所有迭代器都会失效。

vector的实现基本都是围绕这start、end、end_of_storage三个指针，首先先看看vector的基本定义

 1 template <class T, class Alloc = alloc>
 2 class vector {
 3 public:
 4     // 基本型别定义
 5     typedef T value_type;
 6     typedef value_type* pointer;
 7     typedef value_type* iterator;
 8     typedef value_type& reference;
 9     typedef size_t size_type;
10     typedef ptrdiff_t difference_type;
11 protected:
12     // 空间配置器 只是对Alloc的进一步封装
13     typedef simple_alloc<value_type, Alloc> data_allocator;
14     // 关键的几个迭代器
15     iterator start;
16     iterator finish;
17     iterator end_of_storage;
18 public:
19     vector() : start(0), finish(0), end_of_storage(0) {}
20     // 回收内存
21     void deallocate() {
22         if (start) data_allocator::deallocate(start, end_of_storage -    start);
23     }
24     ~vector() { 
25         destroy(start, finish); // 对[start, finish)的元素调用相应的析构函数(如果是POD类型则什么都不做)
26         deallocate();
27     }
28     // 提供简单的接口
29     iterator begin() { return start; }
30     iterator end() { return finish; }
31     size_type size() const { return size_type(end() - begin()); }
32     size_type max_size() const { return size_type(-1) / sizeof(T); }
33     size_type capacity() const { return size_type(end_of_storage - begin()); }
34     bool empty() const { return begin() == end(); }
35     reference operator[](size_type n) { return *(begin() + n); }
36 };

View Code

因为vector实现比较简单，所以就不一一的列出全部成员函数的实现了，主要还是关注其关于插入元素的实现。

先看看比较常用的push_back的实现。

1 void push_back(const T& x) {
2     if (finish != end_of_storage) {
3       construct(finish, x); // 调用placement new构造对象
4       ++finish;
5     }
6     else // 容量不足的情况
7       insert_aux(end(), x);
8   }

View Code

insert_aux用于在position中插入元素，该函数还可以处理容量不足的情况

 1 template <class T, class Alloc>
 2 void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
 3     // 有剩余空间
 4     if (finish != end_of_storage) {
 5         construct(finish, *(finish - 1));
 6         ++finish;
 7         T x_copy = x;
 8         copy_backward(position, finish - 2, finish - 1);
 9         *position = x_copy;
10     }
11     // 容量不足
12     else {
13         const size_type old_size = size();
14         // 分配原来的两倍大小
15         const size_type len = old_size != 0 ? 2 * old_size : 1;
16         // 重新分配空间
17         iterator new_start = data_allocator::allocate(len);
18         iterator new_finish = new_start;
19         try {
20             // 将原来的内容复制到新的vector
21             new_finish = uninitialized_copy(start, position, new_start);
22             construct(new_finish, x);
23             ++new_finish;
24             new_finish = uninitialized_copy(position, finish, new_finish);
25         }
26         catch(...) {
27             destroy(new_start, new_finish); 
28             data_allocator::deallocate(new_start, len);
29             throw;
30         }
31         // 析构并释放原来的vector
32         destroy(begin(), end());
33         deallocate();
34         // 调整三个迭代器
35         start = new_start;
36         finish = new_finish;
37         end_of_storage = new_start + len;
38   }
39 }

View Code

普通的insert函数也是通过insert_aux实现的

 1 iterator insert(iterator position, const T& x) {
 2     size_type n = position - begin();
 3     if (finish != end_of_storage && position == end()) {
 4         construct(finish, x);
 5         ++finish;
 6     }
 7     else
 8         insert_aux(position, x);
 9     return begin() + n;
10 }

View Code

对应的erase函数实现更加的简单

 1 iterator erase(iterator position) {
 2     if (position + 1 != end())
 3         copy(position + 1, finish, position); 
 4     --finish;
 5     destroy(finish);
 6     return position;
 7 }
 8 
 9 iterator erase(iterator first, iterator last) {
10     iterator i = copy(last, finish, first);
11     destroy(i, finish);
12     finish = finish - (last - first);
13     return first;
14 }

View Code