文档章节

STL 源码注释(2)——Vector

突然帅了
 突然帅了
发布于 2015/04/19 15:02
字数 1645
阅读 18
收藏 0

(为了保证代码的简洁性,源码中若干地方省去了异常处理环节,后续还有其他容器的源码注释)

1、vector的初始化和回收机制:

2、vector内存的动态增长

3、vector的API如下:

构造函数:

      vector() : start(0), finish(0), end_of_storage(0) {}"初始化的vector为空"
      vector(size_type n, const T& value) { fill_initialize(n, value); }
      vector(int n, const T& value) { fill_initialize(n, value); }
      vector(long n, const T& value) { fill_initialize(n, value); }
      explicit vector(size_type n) { fill_initialize(n, T()); }
      vector(const vector<T, Alloc>& x) {"把另一个vector中每一个元素都拷贝到新的vector(先分配空间再拷贝容器中元素)"
        start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end());"见初始位置"
        finish = start + (x.end() - x.begin());
        end_of_storage = finish;
      }
      template <class InputIterator>
      vector(InputIterator first, InputIterator last) :"按迭代器所指的范围拷贝,注意:迭代器的类型应覆盖所有迭代器的类型"
        start(0), finish(0), end_of_storage(0)
      {
        range_initialize(first, last, iterator_category(first));"见初始位置"
      }

      内部函数:    fill_initialize(赋初值初始化方式)

                          allocate_and_fill

                          range_initialize(拷贝元素初始化方式)

                          allocate_and_copy

void fill_initialize(size_type n, const T& value) {"批量分配并初始化,然后修改vector的位置元素"
        start = allocate_and_fill(n, value);
        finish = start + n;
        end_of_storage = finish;
      }
      iterator allocate_and_fill(size_type n, const T& x) {"批量分配n个value_type大小的空间,并赋值初始化"
        iterator result = data_allocator::allocate(n);
          uninitialized_fill_n(result, n, x);
          return result;
      }
  template <class InputIterator>
      void range_initialize(InputIterator first, InputIterator last,"一次分配一个空间并初始化(重复n次),每一次都修改vector的位置元素"
                            input_iterator_tag) {
        for ( ; first != last; ++first)
          push_back(*first);""
      }
      template <class ForwardIterator>
      void range_initialize(ForwardIterator first, ForwardIterator last,"批量分配n个空间并初始化,再修改vector的位置元素"
                            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;
      }
      template <class ForwardIterator>
      iterator allocate_and_copy(size_type n,"批量分配n个value_type大小的空间,并进行拷贝初始化"
                                 ForwardIterator first, ForwardIterator last) {
        iterator result = data_allocator::allocate(n);
        __STL_TRY {
          uninitialized_copy(first, last, result);
          return result;
        }
        __STL_UNWIND(data_allocator::deallocate(result, n));
      }

析构函数:

      ~vector() { "析构函数"
        destroy(start, finish);""
        deallocate();
      }

      内部函数:destroy(析构函数)

                       deallocate(释放空间)

template <class T>
inline void destroy(T* pointer) {
    pointer->~T();
}
template <class ForwardIterator>
inline void
__destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) {
  for ( ; first < last; ++first)
    destroy(&*first);
}
template <class ForwardIterator> 
inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {}
template <class ForwardIterator, class T>
inline void __destroy(ForwardIterator first, ForwardIterator last, T*) {
  typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;
  __destroy_aux(first, last, trivial_destructor());
}
template <class ForwardIterator>"依次调用每一个迭代器指向元素的析构函数"
inline void destroy(ForwardIterator first, ForwardIterator last) {
  __destroy(first, last, value_type(first));
}
void deallocate() {"空间释放"
        if (start) data_allocator::deallocate(start, end_of_storage - start);
      }

重载操作符:=、==、!=、>、<、>=、<=、[]

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;
}
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());
}

        内部函数:equal

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());
}

        内部函数:lexicographical_compare

reference operator[](size_type n) { return *(begin() + n); }"下标操作"
      const_reference operator[](size_type n) const { return *(begin() + n); }

begin():

iterator begin() { return start; }"begin函数"
      const_iterator begin() const { return start; }

end():

      iterator end() { return finish; }"end函数"
      const_iterator end() const { return finish; }

rbegin():

      reverse_iterator rbegin() { return reverse_iterator(end()); }"rbegin函数"
      const_reverse_iterator rbegin() const { 
        return const_reverse_iterator(end()); 
      }

rend():

      reverse_iterator rend() { return reverse_iterator(begin()); }"rend函数"
      const_reverse_iterator rend() const { 
        return const_reverse_iterator(begin()); 
      }

front():

      reference front() { return *begin(); }"返回第一个元素的值"
      const_reference front() const { return *begin(); }

back():

      reference back() { return *(end() - 1); }"返回最后一个元素的值"
      const_reference back() const { return *(end() - 1); }

insert():

iterator insert(iterator position, const T& x) {"在指定的位置插入一个新元素,值为x"
        size_type n = position - begin();
        if (finish != end_of_storage && position == end()) {"恰好插入位置是end位置"
          construct(finish, x);
          ++finish;
        }
        else
          insert_aux(position, x);
        return begin() + n;
      }
      
      iterator insert(iterator position) { return insert(position, T()); }"在指定的位置插入一个新元素,值为默认"
      
      template <class InputIterator>
      void insert(iterator position, InputIterator first, InputIterator last) {"从指定的位置开始插入一段新元素"
        range_insert(position, first, last, iterator_category(first));
      }

      内部函数:range_insert

  void insert (iterator pos, size_type n, const T& x){"在指定的位置插入n个值为x的新元素"
  if (n != 0) {
    if (size_type(end_of_storage - finish) >= n) {"剩余空间足够用于插入n个元素"
      T x_copy = x;
      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);
        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);
      }
      destroy(start, finish);
      deallocate();
      start = new_start;
      finish = new_finish;
      end_of_storage = new_start + len;
    }
  }
}
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 InputIterator>"range_insert函数"
void range_insert(iterator pos,
                                    InputIterator first, InputIterator last,
                                    input_iterator_tag) {
  for ( ; first != last; ++first) {
    pos = insert(pos, *first);
    ++pos;
  }
}
template <class ForwardIterator>
void range_insert(iterator position,
                                    ForwardIterator first,
                                    ForwardIterator last,
                                    forward_iterator_tag) {
  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 {
        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);
      }
      destroy(start, finish);
      deallocate();
      start = new_start;
      finish = new_finish;
      end_of_storage = new_start + len;
    }
  }
}

push_back():

  void push_back(const T& x) {"push_back函数"
        if (finish != end_of_storage) {
          construct(finish, x);"调用元素的构造函数并初始化"
          ++finish;
        }
        else
          insert_aux(end(), x);
      }

pop_back():

      void pop_back() {"pop_back函数"
        --finish;
        destroy(finish);
      }

clear():

      void clear() { erase(begin(), end()); }"clear函数"

at():

assign():

erase():

    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;
      }

capacity():

  size_type capacity() const { return size_type(end_of_storage - begin()); }"capacity函数"

size():

   size_type size() const { return size_type(end() - begin()); }"size函数"

resize():

    void resize(size_type new_size, const T& x) {"resize改变了vector的capacity同时也增加了它的size"
        if (new_size < size()) 
          erase(begin() + new_size, end());//并不做赋值初始化动作
        else
          insert(end(), new_size - size(), x);
      }

max_size():

  size_type max_size() const { return size_type(-1) / sizeof(T); }"max_size函数"(疑惑)

empty():

  bool empty() const { return begin() == end(); }"empty函数"

swap():

template <class T, class Alloc>
inline void swap(vector<T, Alloc>& x, vector<T, Alloc>& y) {"只交换位置元素而已"
  x.swap(y);
}
      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);
      }

reserve():

void reserve(size_type n) {"reserve增加了vector的capacity,但是它的size没有改变"
        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;
        }
      }

    

    注:由于本人水平有限,若有不对的地方,欢迎指正!谢谢


© 著作权归作者所有

共有 人打赏支持
突然帅了
粉丝 8
博文 90
码字总数 28698
作品 0
西安
私信 提问
C++ STL学习——vector

学过C++的人肯定会很熟悉STL标准模板库,STL其实就是封装了一系列的接口,供我们调用。很多函数或者算法的实现不需要我们从头开始写,大大提高我们的编程效率。这篇博客在简单介绍STL的情况下...

chenyufeng1991
2016/08/21
0
0
Bjarne Stroustrup's C++ Style and Technique FAQ

Bjarne Stroustrup's C++ Style and Technique FAQ Modified October 4, 2009 Source: http://www2.research.att.com/~bs/bs_faq2.html#void-main ========================================......

长平狐
2013/01/06
179
0
STL系列之九 探索hash_set

Title: STL系列之九 探索hash_set Author: MoreWindows Blog: http://blog.csdn.net/MoreWindows E-mail: morewindows@126.com KeyWord: C++ STL set hash_set 哈希表 链地址法 本文将着重探......

长平狐
2012/12/10
84
0
STL系列之九 探索hash_set

Title: STL系列之九 探索hash_set Author: MoreWindows Blog: http://blog.csdn.net/MoreWindows E-mail: morewindows@126.com KeyWord: C++ STL set hash_set 哈希表 链地址法 本文将着重探......

彭博
2012/04/12
181
0
C语言/C++程序员编程学习:版权和版本

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
05/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

微服务分布式事务实现

https://www.processon.com/view/link/5b2144d7e4b001a14d3d2d30

WALK_MAN
今天
2
0
《大漠烟尘》读书笔记及读后感文章3700字

《大漠烟尘》读书笔记及读后感文章3700字: 在这个浮躁的社会里,你有多久没有好好读完一本书了? 我们总觉得自己和别人不一样,所以当看到别人身上的问题时,很少有“反求诸己”,反思自己。...

原创小博客
今天
3
0
大数据教程(9.5)用MR实现sql中的jion逻辑

上一篇博客讲解了使用jar -jar的方式来运行提交MR程序,以及通过修改YarnRunner的源码来实现MR的windows开发环境提交到集群的方式。本篇博主将分享sql中常见的join操作。 一、需求 订单数据表...

em_aaron
今天
3
0
十万个为什么之什么是resultful规范

起源 越来越多的人开始意识到,网站即软件,而且是一种新型的软件。这种"互联网软件"采用客户端/服务器模式,建立在分布式体系上,通过互联网通信,具有高延时(high latency)、高并发等特点...

尾生
今天
3
0
Terraform配置文件(Terraform configuration)

Terraform配置文件 翻译自Terraform Configuration Terraform用文本文件来描述设备、设置变量。这些文件被称为Terraform配置文件,以.tf结尾。这一部分将讲述Terraform配置文件的加载与格式。...

buddie
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部