C++ STL Container Vector

Vector

• based on gnu 2.9

Container

vector

/*
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;
typedef simple_alloc<value_type, Alloc> data_allocator;
*/
template <class T, class Alloc = alloc>
class vector {
    iterator start;
    iterator finish;
    iterator end_of_storage;
    // iterator
    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()); 
    }
    // reference
    reference front() { return *begin(); }
    const_reference front() const { return *begin(); }
    reference back() { return *(end() - 1); }
    const_reference back() const { return *(end() - 1); }
    // []重载, 随机访问
    reference operator[](size_type n) { return *(begin() + n); }
    const_reference operator[](size_type n) const { return *(begin() + n); }
    // size
    size_type size() const { return size_type(end() - begin()); }
    // size_type是unsigned int, size_type(-1)==4294967295==2^32-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(); }
    // 添加元素
    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;
    }
    // 删除元素
    void pop_back() {
        --finish;
        destroy(finish);
    }

    iterator erase(iterator position) {
        // 删除的不是最后一个元素, 需要移动元素
        if (position + 1 != end()) copy(position + 1, finish, position);
        --finish;
        destroy(finish);
        return position;
    }
}

vector扩容

template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
  // 为insert使用
  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();
    // 2倍扩容
    const size_type len = old_size != 0 ? 2 * old_size : 1;
    iterator new_start = data_allocator::allocate(len);
    iterator new_finish = new_start;
    try {
      new_finish = uninitialized_copy(start, position, new_start);
      construct(new_finish, x);
      ++new_finish;
      new_finish = uninitialized_copy(position, finish, new_finish);
    }
    destroy(begin(), end());
    deallocate();
    start = new_start;
    finish = new_finish;
    end_of_storage = new_start + len;
  }
}